Game Theory Application to Nine Men’s Morris
In 2012, a study was done by Martin Boyd and Christopher Hirunthanakorn on the game of Nine Men’s Morris – a board game played between two players – in order to find an optimal strategy that could ideally guarantee a win or a draw. The Nine Men’s Morris game involves a board with twenty-four spaces (depicted as “dots” or intersections on the board as seen below), and each player is given nine pieces each to place on the board (Boyd & Hirunthanakorn 2). Player “white” always moves first, and the players start taking turns placing one of their nine pieces onto an open space on the board; the objective here is to achieve a “mill”, which is a term for a connected row of three pieces (The Rules of Merels or Nine Men’s Morris, MasterOfGames.com). When a player achieves a mill, they are to steal and remove any one of the opponent’s pieces on the board that is not part of the mill (Note: a mill can only be a vertical or horizontal row). Once all pieces have been placed on the board, each player will take turns to move one of their on-the-board pieces to a different space in an attempt to achieve a mill. A player wins the game when the opponent has less than three pieces left on the board or cannot move any pieces (The Rules of Merels or Nine Men’s Morris, MasterOfGames.com).
Image of Nine Men’s Morris Board with Twenty-Four Spaces.
(Image Source: https://www.researchgate.net/figure/Nine-Mens-Morris-game-board-left-and-its-symmetry-axes-right_fig1_323059294)
In the study, several steps were taken to understand the game intuitively and search for an optimal strategy. The most interesting step taken, also the most relevant regarding what we’ve learned in this course, is the utilization of the Minimax algorithm for building an AI program that determines and plays the most advantageous move at each turn. According to the authors of the research paper, Boyd and Hirunthanakorn, the Minimax algorithm is an algorithm that uses game theory, a topic we’ve learned about in ECON 2040. The Minimax algorithm takes the approach of associating values to possible game positions or game states; the algorithm goes through all the game states that a player can arrive at via some move given the current game state and chooses the move with the optimal value (Boyd & Hirunthanakorn 5). The Minimax algorithm can be succinctly defined as an algorithm that finds the smallest payoff value that a player can force the opposing player to receive, given that we do not know the opposing player’s chosen strategy (Katz & Ross, Brilliant Math & Science Wiki). To give a better idea of how the Minimax works and how it relates to our course, examine the simple payoff matrix for a Nine Men’s Morris game that I drew below.
| (Player White, Player Black) | Mill | No Mill |
| Mill | (0, 0) | (-1, 1) |
| No Mill | (1, -1) | (0, 0) |
The payoff matrix above shows the quantified payoffs for two players playing a game of Nine Men’s Morris. Let us say that for a given pair of consecutive turns (white’s turn first), both player white and player black are able to achieve a mill. In a minimax algorithm, the strategy for player white that minimizes the payoff for player black regardless of the strategy that black chooses is the Mill strategy since it forces player black to only be able to receive one of the two lowest possible payoffs. In this case, the Mill strategy is not only the Minimax strategy for player white, but it is also the dominant strategy (we learned about this in the course) for player white. In many cases, you may see that the Minimax strategy in a game is also the dominant strategy. However, this is not always the case. Remember: the strategy that will lead to a minimum payoff value for a certain player is not necessarily the same as the strategy that maximizes the payoff for the opposing player. Additionally, we can see that the Minimax pair of strategies in favor of player white is (Mill, No Mill), since this makes player black receive the lowest possible payoff it can receive. What is especially interesting, though, is that the pair of strategies Mill and No Mill are a Nash Equilibrium, which we have already defined in this course. However, it should be stated that the Minimax strategies do not always form a Nash Equilibrium (Katz & Ross, Brilliant Math & Science Wiki).
In the 2012 study, with the use of the Minimax algorithm, the AI program was able to beat 7,000 out of 10,000 games against a player using a random strategy (Boyd & Hirunthanakorn 6). This means that the AI achieved a 70% win rate, which shows that this Minimax approach gives the player a favorable edge over the opposition in this board game.
Primary source: https://www.math.uci.edu/icamp/summer/research_12/student_research/nine_mens_morris/nine_mens_morris.pdf (M. Boyd & C. Hirunthanakorn, Analyzing Nine Men’s Morris For a Optimal Strategy. August 18, 2012)
Supplemental Sources:
“The Rules of Merels or Nine Mens Morris.” The Rules of Nine Mens Morris / Merrills / Mill / Merels, https://www.mastersofgames.com/rules/morris-rules.htm.
“Minimax.” Brilliant Math & Science Wiki, Alexander Katz and Eli Ross, https://brilliant.org/wiki/minimax/