Exploring Alternatives: Using Self Balancing Trees for Tic Tac Toe Beyond the Minimax Algorithm

In the realm of classic games, Tic Tac Toe stands as a timeless challenge. Tic Tac Toe has been a staple of algorithmic learning for decades. Traditionally, the Minimax algorithm has been the go-to method for implementing AI in this game. However, as we explore new approaches, I’ve tried a different method using a self balancing binary tree to store player's moves, which promises more efficient performance, especially in real-time game scenario with a 3X3 board. In this post, I've tried to compare this new approach with the standard Minimax algorithm.

Classic Minimax Algorithm Overview

The classic Minimax algorithm is a decision-making strategy used in two-player, zero-sum games to determine the optimal move. It operates by recursively evaluating all possible game states and choosing the move that maximizes the player's minimum possible loss, assuming the opponent also plays optimally.

Game Tree Construction:

• Tree Expansion: Minimax constructs a complete game tree where each node represents a game state. The tree expands to all possible moves and outcomes from the current state.

Tree Nodes

• Minimax Function: The algorithm recursively evaluates each node using the Minimax function, which computes the value of each game state by assuming both players play optimally. The function alternates between maximizing and minimizing values at different levels of the tree.
• Max Nodes: Represent the player's turn trying to maximize the score.
• Min Nodes: Represent the opponent's turn trying to minimize the score.

Evaluation

• Backpropagation or Backtracking: After evaluating all terminal states (end-game scenarios), the algorithm backpropagates the values up the tree to determine the optimal move at the root node. The chosen move is the one that maximizes the player's advantage while minimizing potential losses.
• The algorithm recursively evaluates the game tree. At the leaf nodes (end states), it assigns a score based on the outcome (win, lose, or draw).
• Max Nodes propagate the maximum score up the tree.
• Min Nodes propagate the minimum score up the tree.

Complexity:

• Computational Expense: Minimax can be computationally expensive, especially for large game trees, due to its exponential time complexity. Optimization techniques like Alpha-Beta pruning can be used to improve efficiency by eliminating redundant branches in the tree.
• Alpha-Beta Pruning: An optimization technique to reduce the number of nodes evaluated by the Minimax algorithm. It prunes branches that cannot influence the final decision.

Pseudo-Code

function minimax(node, depth, isMaximizingPlayer):
    if depth == 0 or node is a terminal node:
        return the heuristic value of node

    if isMaximizingPlayer:
        bestValue = -∞
        for each child of node:
            value = minimax(child, depth - 1, false)
            bestValue = max(bestValue, value)
        return bestValue

    else:
        bestValue = ∞
        for each child of node:
            value = minimax(child, depth - 1, true)
            bestValue = min(bestValue, value)
        return bestValue        

The Minimax algorithm is widely used in classic games like Tic Tac Toe, Chess, and Checkers, where it ensures optimal play by evaluating all possible outcomes and making the best decision based on the assumption of perfect play from both players. While effective, the classic Minimax algorithm can be computationally expensive, especially for games with a high branching factor or depth, with complexity generally being O(b^d), where b is the branching factor and d is the depth.

Self balancing Binary Trees approach

The approach to solving Tic Tac Toe presented here utilizes a binary tree to efficiently track player moves and determine game outcomes. This method leverages tree balancing and equidistant path checks to ensure optimal performance, particularly for a 3x3 board. The approach contrasts with the classic Minimax algorithm by focusing on specific game conditions and tree operations rather than exploring all possible game states.

Construction of the Tree:

• Node Representation: Each node in the binary tree represents a game move by storing a position value. The tree is designed to maintain balance, ensuring that operations such as insertion and balancing are efficient.
• Balancing: The binary tree is balanced after each move to ensure that its height remains logarithmic relative to the number of nodes. This balancing is crucial for maintaining efficient operation times, particularly for insertion and path checking.

Inserting Moves:

• Insertion Process: When a player makes a move, the corresponding position value is inserted into the binary tree. The tree structure is updated to include this new move, and the tree is balanced to maintain its efficiency.
• Balancing: After insertion, the tree undergoes a balancing process to ensure that it does not become skewed. Balancing operations include rotations (left and right) to adjust the tree structure based on the values of the nodes.

Equidistant Path Checking:

• Definition: An equidistant path is a sequence of moves where the positions are evenly spaced, effectively forming a straight line. The goal is to check if the current player has achieved such a path to determine if they have won.
• Checking Method: After each insertion, the binary tree is checked for equidistant paths. This involves evaluating the difference between node values along paths to determine if they satisfy the criteria for a winning condition.

Performance Characteristics:

• Complexity: The approach provides logarithmic complexity for insertion and balancing operations, generally O(logn), where n is the size of the board. The equidistant path check also benefits from efficient tree traversal.
• Scalability: While this approach is efficient for a 3x3 Tic Tac Toe board, it may require adaptations for larger boards or more complex scenarios. Self balancing tree method may not scale directly to larger grids without additional modifications or optimizations.

Insertion and Win-Checking code:

class Node
{
    internal int Value { get; set; }
    internal Node Left { get; set; }
    internal Node Right { get; set; }

    internal Node(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }

    internal bool HasEquidistantChildren
    {
        get
        {
            if (Left == null || Right == null)
                return false;

            return Value - Left?.Value == Right?.Value - Value;
        }
    }
}

class PlayerPath
{
    internal Node _root;

    internal PlayerPath()
    {
        _root = null;
    }

    internal void Insert(int value)
    {
        _root = InsertRecursively(_root, value);
        BalanceTree();
    }

    private Node InsertRecursively(Node root, int value)
    {
        if (root == null)
        {
            root = new Node(value);
            return root;
        }

        if (value < root.Value)
        {
            root.Left = InsertRecursively(root.Left, value);
        }
        else if (value > root.Value)
        {
            root.Right = InsertRecursively(root.Right, value);
        }

        return root;
    }

    internal void BalanceTree()
    {
        _root = Balance(_root);
    }

    private Node Balance(Node root)
    {
        if (root == null) return root;

        root.Left = Balance(root.Left);
        root.Right = Balance(root.Right);

        if (root.Left != null && root.Right == null)
        {
            root = RightRotate(root);
        }
        else if (root.Right != null && root.Left == null)
        {
            root = LeftRotate(root);
        }
        else if (root.Left != null && root.Right != null)
        {
            if (root.Left.Value > root.Value)
            {
                root = RightRotate(root);
            }
            if (root.Right.Value < root.Value)
            {
                root = LeftRotate(root);
            }
        }

        return root;
    }

    private Node LeftRotate(Node node)
    {
        Node newRoot = node.Right;
        node.Right = newRoot.Left;
        newRoot.Left = node;
        return newRoot;
    }

    private Node RightRotate(Node node)
    {
        Node newRoot = node.Left;
        node.Left = newRoot.Right;
        newRoot.Right = node;
        return newRoot;
    }

    internal bool HasWon()
    {
        return CheckEquidistantChildren(_root);
    }

    private bool CheckEquidistantChildren(Node node)
    {
        if (node == null)
        {
            return false;
        }

        if (node.HasEquidistantChildren)
        {
            return true;
        }

        return CheckEquidistantChildren(node.Left) || CheckEquidistantChildren(node.Right);
    }
}        

Example moves

• P1 moves to position 1
• P2 moves to position 9
• P1 moves to position 2
• P2 moves to position 3
• P1 moves to position 6
• P2 moves to position 8
• P1 moves to position 4
• P2 moves to position 7
• P2 wins

Let's visualize the tree after each move!

You can get the complete console client code here

Considerations

Minimax approach:

• Optimal Play: Guarantees the best move but at the cost of higher computational time.
• Complexity: Can become computationally prohibitive for larger boards. But Pruning can help solve this problem. Requires significant optimization (like alpha-beta pruning) to be viable in real-time applications.
• AI Implementation: Can be very effective in computer vs human or computer vs computer scenarios.

Self balancing tree approach:

• Efficiency: Insertion and balancing operations are generally O(log n)
• Scalability: While effective for a 3x3 board, larger boards may require a more advanced data structure like a B-tree or a modified algorithm. Minimax algorithm has some proven optimizations and support for large boards.
• Real-Time Play: Suitable for real-time play due to faster insertion and win-checking.

To enhance scalability and performance for more complex scenarios, further research into advanced data structures and algorithms may be needed. Adapting the approach to incorporate heuristic evaluations or parallel processing could also be considered.

Note: In exploring alternative strategies for solving Tic Tac Toe, I examined a self balancing binary tree approach that diverges from the well-known Minimax algorithm. While this method offers a novel perspective, it’s important to acknowledge that similar concepts might exist in academic or niche contexts. This approach, focusing on dynamic balancing and efficient equidistant checks, presents a fresh take but may not be universally established or documented. Therefore, while it provides an innovative alternative, further research and comparison with existing scholarly work are necessary to confirm its uniqueness and effectiveness. This exploration is intended to stimulate discussion and consideration of new strategies rather than claim groundbreaking originality.