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;

Very nice set of posts (although I'll need more time to go through Brad's Part B)!

In the discussion of "fairness" you mention the the number of tied games was surprisingly large. I also found the number of ties in my analysis of the Mancala game surprisingly large. I think we both draw that conclusion because we're both used to playing the game to win rather than exploring all possible games.

I downloaded the notebook and did a little exploration. The number of terminal game states (outs in the PathCount function) is quite large: 1988. Or more than 20% of the vertices in the canonical game graph of 9617 vertices. Only 567 of these terminal game states completely fill the game board, and the least filled game board has eight empty squares.

Have you explored other characteristics of the game, such as the distribution of the final scores, or the distribution of the number of flipped pieces, or the distribution of score reversals?

The number of pieces of each color for a given game state defines a point in the first quadrant of the Euclidean plane, so a game could be plotted as the scores along a path from the root vertex to some terminal vertex. The same technique could also be used to visualize the distribution of final game scores with Histogram3D.

I'm glad to see that you would like to examine different game rules. That was very enlightening for the Mancala game.

The operation of the PathCount function is a bit obscure. Perhaps a small worked example would help readers follow the logic.

I also found the plot of the frequencies of the path counts confusing. The association pcData has an element 4 -> 126, what does the 4 represent (there are 126 4s in the output of PathCount)?

I'm sure there are a great many papers published on this game and the larger version Othello. Do you know if there are any unanswered questions in these papers that might be attacked with multiway analysis?

Thank you for your detailed response! Here are some (very delayed, sorry about that) thoughts. Looking at some characteristics of the final game states seemed like a good idea, so I attached a notebook showing some distributions of final scores:

-- 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!