Message Boards Message Boards

Measuring 4x4 Reversi: Canonicalization & Impartiality Functions on Multiway Graphs

Attachments:
POSTED BY: Andrea Li
8 Replies

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;

POSTED BY: Zsombor Méder

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

POSTED BY: Andrea Li

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?

POSTED BY: Robert Nachbar

Thanks Bob, good ideas there. Yusuke Endoh also did some interesting calculations about the 6x6 Reversi, which Zsombor and I found quite nice. Yusuke's dominance function has added point differentials, which you can see written down on the squares in his 3D environment.

Obtaining such labels should only require a very minor change in the code we have so far, so it might be worthwhile to continue in that direction. This could even be an avenue to exploring different imperfect measurements. If instead of just choosing Max or Min, the vertex function could assign probabilities according to point-differential ratios. That would give us mistakes, and put us somewhere on the spectrum between structural fairness and dominance. However, it still assumes the players have a superpower for infinite look-aheads, which we all know is delusional.

More original thought is needed here. Unless someone has a relevant book or article about different types of human-realistic vertex functions? It might be out there, who knows...

POSTED BY: Brad Klee

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:

POSTED BY: Andrea Li

POSTED BY: Brad Klee

POSTED BY: Brad Klee

enter image description here -- you have earned Featured Contributor Badge enter image description here 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!

POSTED BY: Moderation Team
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract