Thank you for your thoughtful response! I agree that looking into further heuristics would be interesting, and more realistically represent strategies that players can relate to. If you refer to my other comment, I did some exploration into the final distributions of scores. However, that is just the beginning of what we could dive into deeper.

I came across some Othello articles when reading up on the Alpha-Beta Search algorithm that me and Brad will implement this semester that accounts for some of the ideas you mentioned. This includes what they call a “piece differential” (maximizing your own pieces and lessening your opponent’s) and disc positioning (frontier versus interior, corners/edges/buffers), which would affect your choices and mobility later on. If we create a scoring system for spots on the board with these criteria to do the minimaxing, maybe we can update you on conclusions about their effectiveness.

Link to the source (section two mentions their “evaluation function” that rates how good a move is):

https://ai.stanford.edu/~chuongdo/papers/demosthenes.pdf

Very interesting and thorough!

4x4 reversi was an excellent choice - simple enough to keep things tractable & computable, yet intricate enough to generate interesting distributions/graphs.

• Thank you for discussing the problem of canonicalization. I ran into this issue during my own summer school project - you dive in much more detail here. I think there are multiple open questions here that need reflection and disentangling. Maybe we should even write a separate post about this, highlighting what problems it presents in different games. The end-goal could be some specialized version of NestWhileGraph[] that automatically canonicalizes - maybe something we could call NestWhileGameGraph[].

• Did you happen to look at how the number of available moves changes through the game? Is "playing to maximize my own choice-set/minimize that of my opponent" a good heuristic? (maybe you did, and I am overlooking it right now).

• How about a greedy "turn-over-as-many-pieces-as-I-can" heuristic? Is this often good, or does it lead one down a primrose path?

• If the answer to the latter two questions is "No", I think it would be a good exercise pointing in the direction of Brad's question regarding extant research on different types of human-realistic vertex functions. (Unfortunately, I'm not aware of such work combining psychology and combinatorial game theory. Andrea, here's a whole field for the taking!)

• I fully agree with Bob that taking score into account would be interesting. (Incindentally, Bob, is there a way to see your Mancala talk? On the link you provided, it says "All presentations will be recorded and posted to the conference platform for on-demand viewing" - but where is this on-demand viewing accessible?)

• This is not directly relevant to your post, I'd just like to remark that I don't like the term "fairness" - I think its connotations in natural language are misleading. If we'd like to name any games/game states 'fair', I believe it should be those where no-one can force a win.

• I also need a bit of time to read Brad's response. Overall, I agree that implementing alpha-beta-search is very much a worthy endeavour.

• Is 6x6 Reversi computationally completely intractable with these tools? For 8x8, Takizawa's paper found by Brad does not seem overly complicated - though we may not immediately have access to the kind of computational powers/supercomputers that he did.

I'll start playing with the code now.

P.S. I dare barely include this, but you may find this useful whenever dealing with players 1 and 2:

opp = 3 - player;

-- you have earned Featured Contributor Badge Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!