Studying game theory to understand how competing players make strategic decisions has potential applications in fields of economics and political science involving the interactions of businesses and governments, along with modeling quantum mechanics as mentioned in Stephen Wolfram's writings of games as multicomputational systems. In this paper, we generated a simplified game graph of Reversi on a 4x4 grid and calculated game-theoretical measures of complexity and impartiality in the Wolfram Language. Various approaches to building the complete game graph are shown, including brute force and methods of canonicalization — when reflections and rotations of board states are considered duplicates and one is taken to be the default. Path counting, fairness, and dominance functions were implemented to analyze properties of the final game graph. We found that in this 4x4 variation, with 10,128 possible traversals of the graph, the second player is always able to force a win given optimal play. Future directions such as implementation of an Alpha-Beta pruning search algorithm, simulating realistic human decision-making, and alternative variations to the game including a hexagonal grid are discussed.
Introduction: Modeling the Game
Introduction: Modeling the Game
Rules
Rules
◼
The black player goes first
◼
A valid move must “flip” at least one of the opponent’s pieces
◼
In order to “flip” a piece, the current player must flank at least one of the opponent’s pieces with their own color on both sides (can be horizontally, vertically, or diagonally)
◼
All of the flanked pieces are flipped over to the opposite color
◼
The game continues until there are no more valid moves. Player with most pieces of their color wins.
◼
Typically played on an 8x8 board (64 disks that are black on one side, white on the other).
Initial Configuration
Initial Configuration
This is the starting board state, where gray pieces indicate potential opening moves for player 1 (black).
Out[]=
Sample Game
Sample Game
Here is a randomly selected Reversi game from our full game graph (shown later).
Out[]=
|
Representing the Board
Representing the Board
In this paper, a simplified Reversi with a 4x4 board will be used in order to make large computations possible.
The game board is represented using an association, where the keys represent the players: 1 is black, 2 is white, and 0 is empty. The values are the coordinate points of pieces on the board corresponding to its key. The following code creates the initial state of the board.
In[]:=
initializeReversi[]:=<|1->{{2,3},{3,2}},2->{{2,2},{3,3}},0->{{1,1},{1,2},{1,3},{1,4},{2,1},{2,4},{3,1},{3,4},{4,1},{4,2},{4,3},{4,4}}|>
Displaying the Board
Displaying the Board
The following function takes in an association relating to the board data and displays the board graphics.
In[]:=
displayBoard[board_,opts:OptionsPattern[Graphics]]:=Module[{background,coordinateReplacements,blackLocations,whiteLocations},background=Graphics[{Darker[Blend[{Green,Blue},4/10],.1],Rectangle[{0,0},{4,4}],Thick,Darker[Gray],Line[{{#,0},{#,4}}]&/@Range[3],Darker[Gray],Line[{{0,#},{4,#}}]&/@Range[3]},Background->Black,opts];coordinateReplacements=Flatten[Table[{i,#}->{-0.5+#,4.5-i}&/@Range[4],{i,4}]];whiteLocations=board[2]/.coordinateReplacements;blackLocations=board[1]/.coordinateReplacements;Show[background,Graphics[{Black,Disk[#,0.38]&/@blackLocations,White,Disk[#,0.38]&/@whiteLocations}]]]
Making Moves
Making Moves
Finding Flips (Determining Valid Moves)
Finding Flips (Determining Valid Moves)
The following function takes the coordinate point of single empty spot on the board and a direction to check. It returns either a list of coordinates of the pieces that would be flipped or an empty list if there's no valid moves.
In[]:=
findFlips[board_,player_,spot_,direction_]:=Module[{flips,loc,opp},flips={};loc=spot;opp=Mod[player+1,2,1];While[MemberQ[board[opp],loc=loc+direction],AppendTo[flips,loc];];If[MemberQ[board[player],loc],flips,{}]]
This function utilizes the previous findFlips function in order to check all directions and returns all the pieces that would be flipped given a specific spot on the board.
In[]:=
findAllFlips[board_,player_,spot_]:=Module[{directions},directions=DeleteCases[Tuples[{0,1,-1},2],{0,0}];Catenate[findFlips[board,player,spot,#]&/@directions]]
Now that we can find all the flips given a certain spot in the board, we are able to find all the possible valid moves. This function utilizes the findAllFlips function for all the empty spots on the board, considering it a valid move if there are more than zero flips possible. It returns a list of all the possible moves on a given board.
In[]:=
findMoves[board_]:=Module[{flips,player},player=Mod[Length[Lookup[board,0,{}]]+1,2,1];Map[Function[loc,If[SameQ[{},flips=findAllFlips[board,player,loc]],Nothing,<|"player"->player,"move"->loc,"flips"->flips|>]],Lookup[board,0,{}]]]
Aside from finding all the moves, we need to be able to actually make a move and edit the board state. The following function takes in a board and a move location, and returns a new board with that move made.
In[]:=
makeMove[board_,move_]:=Module[{newBoard,player,opp},newBoard=board;player=move["player"];opp=Mod[player+1,2,1];newBoard[0]=Complement[newBoard[0],{move["move"]}];newBoard[player]=Union[newBoard[player],Append[move["flips"],move["move"]]];newBoard[opp]=Complement[newBoard[opp],move["flips"]];newBoard]
For example, we can now make all the possible first moves from the initial board:
In[]:=
displayBoard[makeMove[initializeReversi[],#],ImageSize->60]&/@findMoves[initializeReversi[]]
Out[]=
,
,
,
Creating the Multiway Graph (“Brute force”)
Creating the Multiway Graph (“Brute force”)
Now that we are able to represent board states and make moves on them, now we can create a multiway game graph using “brute force.” Essentially, we can find every possible move at every single state until the game is over.
The following “naive” iterator creates one layer of the multiway graph by simply making all the possible moves on a given board state.
Pairing our iterator with NestGraph, we can look at the first 2 moves on the multiway.
By the third move, we can already see crossing over where multiple states can have a shared successor.
Selecting for these scenarios, we see that the crossing over occurs at these board states:
We can also isolate the subgraph that leads to them:
Evaluating the entirety of the game graph, we can see that it has 41, 497 vertices and 57324 edges.
Canonicalization & Reduced Multiway Graph
Canonicalization & Reduced Multiway Graph
With brute force, evaluating the full game graph gets computationally expensive (with just a 4x4 board, there are 41,497 vertices and 57,324 edges). One way of minimizing of the nodes in the graph is to consider states that are rotations and reflections of one another the same. Therefore, each state could potentially have up to 7 other duplicates of itself (squares have 4 rotations + 4 reflections). We need methods of canonicalization to stay consistent and choose one state out of all the duplicate forms to be the “default.”
Before we canonicalize, we need to be able to translate between the board states in their association form and a nested list format so that we can use the resource function ArrayRotations. FromGroupedPositions takes in an association and makes it a nested list. GroupedPositions takes in a nested list and makes it an association.
This following function generates the duplicate forms of a given board state, and sorts them so that we can consistently take the first board in the list as our canonical form.
Now, if we run canonicalSignature on the first move of the game, we can see the 8 states considered duplicates and our canonical form, the first board.
We can also find some interesting states in which there are not all 8 duplicates, due to inherent symmetry or the impossibility of the game board reaching that state. Examining end states in our full game graph, we find two scenarios that only have one canonical signature:
If you’re wondering what sort of game would lead to these end states, here is a randomly selected game that would lead to the first end state.
Random game for the second end state:
The subgraphs that lead to these end states have a structure that is non-random as well. The second end state has 8 clear paths, which is consistent being a multiple of a possible number of canonical signatures. The first end state has a more complicated subgraph, with some crossing over occurring.
Naive Canonicalization
Naive Canonicalization
Now that we can generate canonical signatures given any game board, we can try to create the multiway graph of Reversi again, but this time filtering out the duplicates to reduce the complexity of the game. The first method of canonicalization involves creating a “unique” iterator that can be paired with NestGraph.
Here, we see that the function is similar to the previous iterator — given a board, it finds which player’s turn it is and generates all the possible next moves. The catch is that we evaluate canonicalSignature on all the moves and take the Union of that list, thus only generating unique board states at every level.
Using this unique iterator, we can create the first 3 moves of the multiway. Interestingly, we can note that there is only one unique first move.
This gets the full game graph all the way down to 9617 vertices and 13,719 edges, which is roughly a factor of four smaller than the previous.
To better understand what is happening with the canonicalization, we can go back to the selected “weird” subgraphs from before (the ends with only one canonical signature). However, the nature of our unique iterator means all the ends in this graph will only have one canonical signature, so we have to select for the previous scenarios specifically:
Visually counting, it looks like the number of nodes in these graph have decreased by a factor of four from the ones shown earlier, as the larger graphs seem to be made up of four copies of these new subgraphs. We will prove whether this is true or not later on through path counting in the Functions On Graphs section.
“Extra Effort” Canonicalization
“Extra Effort” Canonicalization
Although naive canonicalization appears to work, we can quickly observe an alignment issue in the multiway —not every new move in the next layer would be a possible play from the previous board. Instead, they may be pointed at the canonical version of an actual possible move. We can notice this by the 3rd layer of the graph, as the white squares appear to have shifted and the black plays in a nonsensical spot.
In order to fix this alignment issue, we need to keep track of the moves generated from the previous state separately from their duplicates. This first attempt to do so is based on creating a new iterator that maintains a dictionary of “good moves” to keep track of which states we have already seen before.
The following function is a unique iterator that aligns the moves properly. We check every valid new move and all its duplicates to see if it is already in the list of “good moves.” If it is, we know we’ve seen this move or a variation of it already, so we do nothing and keep checking. If it isn’t, we add it to the list of “good moves” because we know we haven’t seen it yet.
This is simply a helper function to the extra effort iterator and a modified version of MemberQ. It checks if an element and all its canonical signatures are a member of the list, rather than only the element itself.
Surely enough, now we can create the multiway graph with only unique moves and proper alignment. The first three moves:
Now, evaluating the entire game graph again, we get 12, 957 vertices and 16, 874 edges:
This is more than the naive canonicalized graph, which reveals a scoping problem. Our extraEffortIterator only considers canonical duplicates local to its own branch, rather than globally on the entire layer. Thus, it ends up missing some merging scenarios. This means that the canonical dictionary we maintain through our list of “good moves” should be a level higher than the iterator itself. This can be accomplished through the Module function:
Now, the vertex and edge count is consistent with our previous canonical game graph. We can ensure they are the same with IsomorphicGraphQ:
Looking at the previous code, it seems to be a big solution for a little problem of alignment. Why shouldn’t this be done by simply passing the canonicalizer as an option to NestWhileGraph? The following functions are written to generalize canonical graph creation from Reversi to any situation.
The CanonicalizeBy function takes in a function such as our canonicalSignatures from above as one of it’s arguments and sorts the given states by their duplicates.
This function MultiIterate is similar to the other iterators we’ve already created in that it generates the next layer of new moves on a state. However, it takes in an iterator as one of its arguments and acts on an entire level of the graph rather than individual branches by mapping that iterator over all the states in a level. Inside the function, it sows the directed edges of the input state to it’s outputs to be reaped when we create the multiway graph later. Finally, it returns only the output states.
Finally, we can put these two generalized functions together with our Reversi functions create our canonical game graph again.
Verifying the graphs are the same:
Functions on Graphs
Functions on Graphs
Having generated our game graph, we are now able to answer more interesting questions about Reversi. How many possible paths are there through the game? Is the game fair for player 1 and player 2? Games with trivial “solutions” become far less fun for a player destined to lose. With Reversi, is there an optimal strategy such that one player is guaranteed to win? Or is it impartial, meaning optimal plays from both sides could result in a tie? We will be using our canonical game graph for these calculations.
Path Counting
Path Counting
The first quality of the graph we can look at is the number of possible paths, or ways the game could play out, which is a better way of quantifying complexity than simply examining the number of nodes and edges on the multiway graph.
The following path count function utilizes the resource function DirectedAcyclicEvaluate with the vertex function set to Total in order to accumulate the total of the number of paths. We first find the root node of the graph (the initial board configuration) and call it “ins,” and all the leaf nodes (all the end states) and call it “outs,” which will both be inputs into DirectedAcyclicEvaluate. DirectedAcyclicEvaluate is able to sort vertices into lists depending on their level (same as the number of moves that have been played). It returns an association and we select for VertexWeights, which is assigned by accumulating all the previous levels above it into a list of rules that we can then Total to find the paths.
Using this new function on our graph, we get the number of paths:
The number is greatly reduced from the brute force game graph, which has roughly 4x as many paths:
We can also plot the frequencies of path counts throughout the game graph. The x-axis represents the frequencies (number of nodes) of each number of paths and the y-axis represents the number of paths:
Finally, we can prove our hypothesis on the “weird” subgraphs where the ends only had one canonical signature. The number of possible paths to traverse the full game graph should be four times the path count of the canonicalized version.
Surely enough, the canonicalized subgraph is exactly 1/4 of the original brute force subgraph. This is also true for the other example:
Fairness
Fairness
The next way to analyze the game is the notion of “fairness,” which in this case we would examine the likelihoods of each player winning. In this situation, we are assuming random play and the weight of each branch is equal — at a given state, a player simply chooses a random valid move without thinking about strategy or looking ahead at future scenarios. While this isn’t realistic, it could be useful in modeling a choice when the player can’t foresee one move being better than another.
The following helper function counts the number of wins associated with each player. 1 represents a black win, -1 represents a white win, and 0 represents a tie.
Looking at the canonicalized game graph, we calculate the following counts of wins from each player (1 is black, -1 is white, 0 is a tie):
Interestingly, the number of win scenarios for black, the player that goes first, is slightly larger than the win scenarios for white. There are also a surprisingly significant number of ties. However, we are more interested in “fairness”:
The following function is similar to PathCounts in that we are utilizing DirectedAcyclicEvaluate. However this time, the vertex function we accumulate is Mean. By assigning 1 to the first player and -1 to the second player, taking the mean will allow us to determine the skew. For example, if there were two paths to a vertex, one being a win for player #1 (assigned 1) and one being a win for player #2 (assigned -1), that vertex would get a mean of 0, which is neutral since there are equal paths to either side winning. But if there were two paths to a win for 1 and one path to a win for -1, the mean would be 1/3, showing that it is slightly skewed towards 1. We run this calculation on the reverse graph, to simulate “looking ahead” when we accumulate all the levels above the current — this gives us a final fairness value at the root node that takes into account every possible move that could ensue throughout the game.
Running the fairness calculation on our game graph, we get the value -0.159073, meaning the game is actually slightly skewed towards white, player 2.
Additionally, we can examine subgraphs of the game graph to see how fairness changes after a pivotal decision on the board. One scenario we can examine is the 2nd move, where we can clearly see the game graph split off in three directions when player 1 (black) makes a decision. Here are the moves:
What if we wanted to figure out which move out of these three is the best move? We could look at fairness as one indicator:
Clearly, the first move where white plays in a corner spot is the most advantageous, as the fairness skews heavy towards -1. This makes sense from a logical standpoint, as all corner and edge pieces aren’t able to be “surrounded” by an opponent piece and therefore cannot be flipped. After making a corner move, a player can almost guarantee their win even when they play randomly.
Dominance
Dominance
Perhaps more applicable to real outcomes of the game is the notion of dominance — when one player is able to ensure a win by making the best possible moves at every stage of the game. The typical player does not play randomly, and instead tries to think ahead (maybe 1-3 moves) and make advantageous decision so that they can win. With dominance, we are assuming the capacity of the player’s “look-ahead” ability is the length of the entire game.
The following function continues to utilize DirectedAcyclicEvaluate on the reverse graph. Now, we use Min and Max as the vertex functions. This is because each win scenario is mapped to 1 or -1 by findWins, so Max would represent an advantageous move for player 1, and Min would represent an advantageous move for player 2. The #1, and #3 in the function are part of DirectedAcyclicEvaluate. #1 is a list of the vertex weights for all the vertices on a level before the current vertex, which is why we would take the Min or Max or them to simulate making a decision based on compounded values.
Now, we can consider the same 2nd move scenario we did with fairness but with dominance:
It appears as though player 2 (white) should definitely make the corner move, or else they give a chance for the other player to dominate. We can visualize these subgraphs of how the rest of the game plays out after that move, where the domination scenarios for the 1st player are colored in red, domination for the 2nd player in blue, and neutral games are light gray:
We notice that the first graph is almost entirely blue, meaning that making a corner move causes later game scenarios to favor player 2. This explains why the dominance for the full game graph is the second player, as the first player has no way of preventing the second player from taking the corner.
Comparing Fairness & Dominance
Comparing Fairness & Dominance
Overall, for a realistic human player in the game, their choices are probably on a spectrum between fairness and dominance — strategizing sometimes, but also making mistakes and choosing randomly when unsure of what to do. By mixing in fairness and dominance, we can start to simulate human-decision making. To gain further intuition for the relationship between the two, we can attempt to compare the difference between the fairness value and the average of the dominance values.
The following graph shows how the difference between fairness and dominance decreases the further along the game proceeds. The x-axis is the number of moves that have been played, or the level in the graph. The y-axis shows the average of differences across all vertices in a particular level. The difference refers to the absolute difference between the fairness of a vertex and the mean of the dominance values of the subgraph from that vertex.
Future Directions
Future Directions
While we were able generate simplified, multiway game graphs for 4x4 Reversi and discuss game theory-related functions on them, we plan to make further progress regarding this topic in a subsequent paper.
We hope to implement search algorithms such as Alpha-beta pruning to solve 4x4 Reversi. In October 2023, Hiroki Takizawa published a paper claiming to have found a weak solution to 8x8 Reversi, proving that perfect play from both players can lead to do a draw. While there is discussion regarding the credibility of his findings, we aim to take inspiration from his methods and optimize Alpha-Beta search in the Wolfram Language. In the process of examining Reversi, the code could be generalized to a Alpha-Beta search function for the Wolfram Function Repository.
We propose the addition of an “ExtraEffort” option to NestGraph to fix alignment issues when attempting to canonicalize game states and minimize the complexity of the directed graph. Our findings of globalizing a duplicates dictionary while iterating can be applied to do so.
Another consideration is slight rule variations of the game. In this paper, any scenario in which there are no valid moves for the current player results in the game ending. However, some Reversi games state that no valid moves results in a double turn for the opponent. This means that the game board must always be completely full before the game ends — with different end states, graph calculations such as path counts, fairness, and dominance may change from what was discussed in this paper. To incorporate the rule in the future, our game association must also keep track of the current player, as simply counting pieces on the board is no longer valid.
Using our fairness and dominance functions as basis, we can create a method of simulating human players’ decision-making for any game. Potential routes could be varying the degrees to which we prioritize dominance over random play, so that we are able to mimic a beginner, proficient, and advanced player. Additionally, the ability to model decision-making in simple adversarial games could be applied to game theory and economics research. Our work can be generalized to create advanced models that predict self interest-motivated decision-making in the real world, such as that of businesses and governments.
Finally, we hope to explore more board variations, such as a hexagonal grid, and generalize potential differences in gameplay based on board geometry.
We hope to implement search algorithms such as Alpha-beta pruning to solve 4x4 Reversi. In October 2023, Hiroki Takizawa published a paper claiming to have found a weak solution to 8x8 Reversi, proving that perfect play from both players can lead to do a draw. While there is discussion regarding the credibility of his findings, we aim to take inspiration from his methods and optimize Alpha-Beta search in the Wolfram Language. In the process of examining Reversi, the code could be generalized to a Alpha-Beta search function for the Wolfram Function Repository.
We propose the addition of an “ExtraEffort” option to NestGraph to fix alignment issues when attempting to canonicalize game states and minimize the complexity of the directed graph. Our findings of globalizing a duplicates dictionary while iterating can be applied to do so.
Another consideration is slight rule variations of the game. In this paper, any scenario in which there are no valid moves for the current player results in the game ending. However, some Reversi games state that no valid moves results in a double turn for the opponent. This means that the game board must always be completely full before the game ends — with different end states, graph calculations such as path counts, fairness, and dominance may change from what was discussed in this paper. To incorporate the rule in the future, our game association must also keep track of the current player, as simply counting pieces on the board is no longer valid.
Using our fairness and dominance functions as basis, we can create a method of simulating human players’ decision-making for any game. Potential routes could be varying the degrees to which we prioritize dominance over random play, so that we are able to mimic a beginner, proficient, and advanced player. Additionally, the ability to model decision-making in simple adversarial games could be applied to game theory and economics research. Our work can be generalized to create advanced models that predict self interest-motivated decision-making in the real world, such as that of businesses and governments.
Finally, we hope to explore more board variations, such as a hexagonal grid, and generalize potential differences in gameplay based on board geometry.
Author Contributions
Author Contributions
I would like to thank my mentor Brad his expertise, willingness to help at any time, and fun time playing games over these past few months. If not mentioned below, the code and visualizations were co-written by the two of us. Here are our specific contributions:
Andrea Li:
Andrea Li:
◼
Conceptualizing the idea of working with Reversi
◼
Drafting and editing the paper, including images and function explanations
Brad Klee:
Brad Klee:
◼
Provided the functions MultiIterate & CanonicalizeBy and code for generating the game graphs rgg/rgg2
◼
Reviewing and providing feedback on the writing
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Measuring 4x4 Reversi: Canonicalization & Impartiality Functions on Multiway Graphs
by Andrea Li & Brad Klee
Wolfram Community, STAFF PICKS, December 27, 2023
https://community.wolfram.com/groups/-/m/t/3092013
by Andrea Li & Brad Klee
Wolfram Community, STAFF PICKS, December 27, 2023
https://community.wolfram.com/groups/-/m/t/3092013