Minimax is an algorithm where two players (min and max) play against each other for minimizing loss and maximizing gain. The following picture illustrates minimax with a game of tic-tac-toe.

The algorithm uses a tree for the moves and scores of each player. In some cases, it is unnecessary for the algorithm to check certain subtrees. For example, if a certain player has already gained the best score in the subtree. A technique called alpha-beta pruning can be applied to let the algorithm ‘prune’ certain subtrees.

The following snippet contains the minimax algorithm with alpha-beta pruning.

public class AlphaBeta { bool MaxPlayer = true; public AlphaBeta() { } public int Iterate(Node node, int depth, int alpha, int beta, bool Player) { if (depth == 0 || node.IsTerminal(Player)) { return node.GetTotalScore(Player); } if (Player == MaxPlayer) { foreach (Node child in node.Children(Player)) { alpha = Math.Max(alpha, Iterate(child, depth - 1, alpha, beta, !Player)); if (beta < alpha) { break; } } return alpha; } else { foreach (Node child in node.Children(Player)) { beta = Math.Min(beta, Iterate(child, depth - 1, alpha, beta, !Player)); if (beta < alpha) { break; } } return beta; } } }

The Node class contains methods which can vary per game.

public class Node { public Node() { } public List<Node> Children(bool Player) { List<Node> children = new List<Node>(); // Create your subtree here and return the results return children; } public bool IsTerminal(bool Player) { terminalNode = false; // Game over? return terminalNode; } public int GetTotalScore(bool Player) { int totalScore = 0; // This method is a heuristic evaluation function to evaluate // the current situation of the player // It depends on the game. For example chess, tic-tac-to or other games suitable // for the minimax algorithm can have different evaluation functions. return totalScore; } }

## One Trackback

[...] trying to implement Pentago AI and found the code snippet below in the : “http://snipd.net/minimax-algorithm-with-alpha-beta-pruning-in-c” about alpha beta pruning and evaluation function . As you see in code snippet a subtree can [...]