Minimax algorithm with alpha-beta pruning in C#

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.

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;
        }

    }