What is a min-max game tree?
Every two-player game which is also zero-sum can be represented as a min-max tree wherein one player assumes the role of "max" and another is assumed to be "min". This type of assumption is ideal for zero-sum games because the best move for "max" will be the worst move for "min". Every zero-sum game has only one governing utility function that decides the "goodness" of a move for a player. If the value returned by that function for a move for max is 'a', then the value for the same move for min will be '-a' and vice versa. Thus, at any state of the game, the total utility value for both players is zero.
We maintain a tree structure wherein the nodes of the tree represent the player's (either min or max) state, and the edges represent the move it takes to go from one such state to another.
The Nim game:
Since this was intended to be a lesson on min-max tree, we started with a simple game. Our implementation of the Nim game has one pile of 'x' number of stones, where 'x' is taken as an input to our program. Each player can pick up at most 2 stones (i.e either 1 stone or 2 stones). The player which picks up the last stone(s) loses i.e. the player for which there are no more stones left to pick wins.
Our Implementation:
We keep a global static variable 'remStones' which holds the number of stones left in the pile. Since there are at most 2 possible moves (one wherein the player picks 1 stone and another wherein he picks 2), our GameNode data structure can have maximum 2 children (left and right). The left child signifies the state which occurs after the player picks 2 stones, and the right occurs after he picks 1 stone. The left child may be null (in case there is only 1 stone left), or both the children may be null. By linking nodes with its children, we indirectly maintain a tree in the memory space.
Remember that in the code, the program acts as the "max" player and the opposite person, whose moves will be inputs to the console during run-time acts as "min". Thus, inside the tree, every move is scored from our perspective i.e. if the move benefits us, we give it a high score. Also, the root node will always signify our(max's) turn. We use a simple utility function:
For every leaf node:
if max wins:
score +1 to that node
else:
score -1 to that node
We now also propagate the score to the parents and eventually to the entire tree. The method makeMove() takes the current node as input and makes the move that give a state with the highest score. Thus, as the game progresses, a subset of the tree is traversed along a particular path and at every max turn, we calculate the next move based on the utility function.
Below is a commented code of the same program. Any doubts/suggestions/comments are most welcome.
Every two-player game which is also zero-sum can be represented as a min-max tree wherein one player assumes the role of "max" and another is assumed to be "min". This type of assumption is ideal for zero-sum games because the best move for "max" will be the worst move for "min". Every zero-sum game has only one governing utility function that decides the "goodness" of a move for a player. If the value returned by that function for a move for max is 'a', then the value for the same move for min will be '-a' and vice versa. Thus, at any state of the game, the total utility value for both players is zero.
We maintain a tree structure wherein the nodes of the tree represent the player's (either min or max) state, and the edges represent the move it takes to go from one such state to another.
The Nim game:
Since this was intended to be a lesson on min-max tree, we started with a simple game. Our implementation of the Nim game has one pile of 'x' number of stones, where 'x' is taken as an input to our program. Each player can pick up at most 2 stones (i.e either 1 stone or 2 stones). The player which picks up the last stone(s) loses i.e. the player for which there are no more stones left to pick wins.
Our Implementation:
We keep a global static variable 'remStones' which holds the number of stones left in the pile. Since there are at most 2 possible moves (one wherein the player picks 1 stone and another wherein he picks 2), our GameNode data structure can have maximum 2 children (left and right). The left child signifies the state which occurs after the player picks 2 stones, and the right occurs after he picks 1 stone. The left child may be null (in case there is only 1 stone left), or both the children may be null. By linking nodes with its children, we indirectly maintain a tree in the memory space.
Remember that in the code, the program acts as the "max" player and the opposite person, whose moves will be inputs to the console during run-time acts as "min". Thus, inside the tree, every move is scored from our perspective i.e. if the move benefits us, we give it a high score. Also, the root node will always signify our(max's) turn. We use a simple utility function:
For every leaf node:
if max wins:
score +1 to that node
else:
score -1 to that node
We now also propagate the score to the parents and eventually to the entire tree. The method makeMove() takes the current node as input and makes the move that give a state with the highest score. Thus, as the game progresses, a subset of the tree is traversed along a particular path and at every max turn, we calculate the next move based on the utility function.
Below is a commented code of the same program. Any doubts/suggestions/comments are most welcome.
