![]() In many cases, you may see that the Minimax strategy in a game is also the dominant strategy. 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 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. 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. The payoff matrix above shows the quantified payoffs for two players playing a game of Nine Men’s Morris. ![]() 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. 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). 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). 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 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. In the study, several steps were taken to understand the game intuitively and search for an optimal strategy. Image of Nine Men’s Morris Board with Twenty-Four Spaces. 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, ). 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. 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). 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, ). 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). 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. ![]() To run the game type: python3 main.Game Theory Application to Nine Men’s Morris The difficulty level of the game can also be changed by changing the heuristic function in the code. You can set the heuristics you use through the code. For the AI vs AI game we use two different heuristics. The second way is to watch a AI vs AI game. The first way is to play a human vs AI game. Our Nine Mens Morris game can be played in two ways. (optional phase) Moving men to any vacant point when the player has been reduced to three men.A player wins by reducing the opponent to two pieces (where they could no longer form mills and thus be unable to win), or by leaving them without a legal move. Players try to form 'mills'-three of their own men lined horizontally or vertically-allowing a player to remove an opponent's man from the game. Each player has nine pieces, or "men", usually coloured black and white. The board consists of a grid with twenty-four intersections or points. Nine men's morris is a two player strategy board game dating back to at least the Roman Empire.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |