I hope that you have already read my previous article. And if you haven’t, please read it so you can get a better idea what I’m talking about. 😀

In this article, we’ll see how to implement these game trees.

Let’s consider the following Game Tree and assume the root node is for Player 1.

If you do the min-max I explained, you’ll get a Game Tree like below and you’ll realize the 3rd move (from the left) is the best one (with utility of 4).

Special Notes:

• Root represents a single move in the real game and each of the other node represent the predicted move.
• Only leaf nodes have calculated utility values according to a heuristic function.
• (+) Nodes represents the same player’s move who owns the root and (-) nodes represents the opponent’s move.
• When going up in the tree, root owner assumes that the opponent will take the move with minimum utility to root owner, that’s why he selects the minimum value at the (-) node.

The algorithm used for this task is called Min-Max algorithm. The idea is to create a game tree for the current configuration and find heuristically best possible move.

Mini-Max Algorithm

To do that, we need a tree data structure.You can use any preferred way to create one, but at this point “I don’t care how you do that”. 😀

So the algorithm says:

When traversing the tree,

• If the current node is a leaf, then calculate the utility value for that configuration, for the player at the root. Then return the value to the parent node.
• If the current node is a (+) node, return the maximum utility value of children nodes of this node.
• If the current node is a (-) node, return the minimum utility value of children nodes of this node.

When we combine all those possibilities, we can get the pseudo code for the algorithm as:

function MINIMAX(node s)
  if s is a leaf node then
    return utility(s)
  end if
  if s is a max node then
    return max(MINIMAX(t)) : t is a child of s
  end if
  if s is a min node then
    return min(MINIMAX(t)) : t is a child of s
  end if
end function

NOTE :

You may notice that you’ll obtain the best utility value for the root value, but not the best move. To fix this you can create game trees for each option at the root and apply the mini-max for each of them.

For example, in the above game tree, we create 3 sub-game trees for each of the moves. Then we apply Mini-Max for each sub tree.

Please remember, in these sub-trees, root node does NOT belong to the original owner, and it’s his opponent’s. Hence, the root of the sub-trees must remain as (-) nodes and you calculate the utility at leaves for the original player, not the opponent (who owns the sub-trees).

It is really inefficient to create a tree at the beginning. It uses a LOT of memory. Even if you create the nodes on-the-fly, it still is computationally expensive. Then we have to optimize the tree traversal by limiting the number of branches we visit.

For that we use, Alpha-Beta pruning. You have read my next post to know about that. 🙂