AI-Based-Three-Player-Ludo-Game-Using-Minimax-and-Alpha-Beta-Pruning-in-Python

Instead of returning a single integer value (where a high number helps one side and a low number helps the other), our evaluation function returns a 3-element vector of utilities:

$$U = [U_{\text{human}}, U_{\text{AI1}}, U_{\text{AI2}}]$$

During a simulated search tree layer, the player whose turn it is calculates moves aiming solely to maximize their own index in that utility vector, operating under the assumption that subsequent opposing nodes will optimize their own respective metrics.

2. Detailed Breakdown of the Pure Minimax Algorithm (Max-N)

The Pure Minimax engine in this project evaluates moves by building a lookahead tree of depth 3 ($D=3$). It assumes that every player is perfectly rational and will choose moves that yield the best possible outcome for themselves.

• Step 1: Deep Copy Simulation: When an AI receives a dice roll, it clones the current game state for each of its movable tokens. It applies the move to the cloned state and passes this hypothetical layout to the next layer down in the tree.
• Step 2: Turn Rotation: Minimax simulates the game sequentially. If it is AI_1's turn at Layer 0, the engine simulates AI_2's best responses at Layer 1, and the Human's best counters at Layer 2.
• Step 3: Bottom-Up Evaluation: When the algorithm hits its maximum depth ($D=0$), it calls the evaluate_state() function. This calculates a static vector score for that specific board arrangement.
• Step 4: Vector Maximization: As the scores bubble back up the tree, each player maximizes their own index:
  • At a layer where it is AI_1's turn, it scans all child branches and picks the move that results in the highest value for index 1 ($U_{\text{AI1}}$).
  • At a layer where it is AI_2's turn, it picks the move that results in the highest value for index 2 ($U_{\text{AI2}}$).
• The Cost: Minimax is exhaustive. It forces the computer to visit every single branch, including terrible moves where the AI would completely expose itself to being captured, just to see what happens next.

3. Detailed Breakdown of the Alpha-Beta Pruning Algorithm

Alpha-Beta Pruning is an optimization layer built over the Minimax engine. Its sole purpose is to skip calculating branches that are mathematically proven to be useless to the players, saving immense amounts of CPU work.

• The Pruning Mechanism ($\alpha$ and $\beta$ Bounds): The engine maintains lower bounds ($\alpha$) and upper bounds ($\beta$) across the 3-player vector stream.
• The Intercept: When exploring a branch, the AI looks at the score it has already guaranteed for itself on an earlier branch. If it begins evaluating a new branch and discovers that a player further down the tree can force an outcome that makes this new path worse than the fallback path it already secured, the AI stops looking.
• Early Break (The Cut-off): In the code, this is handled by the conditional block:

  if beta >= alpha and alpha != -float('inf') and beta != -float('inf'):
      break # Pruning happens here
  

Once this condition triggers, the loop immediately terminates (break). The engine completely throws away the rest of that branch's sub-tree, refusing to waste time deep-copying states or calculating lookaheads for moves that will never be chosen in real gameplay.

4. Heuristic Evaluation Function (Eval)

The static estimation weight calculates structural advantages for individual states:

• Goal Weights: $+2000$ points for every token safely locked in GOAL (Tile 52).
• Home Safe Pathing: $+1000$ base points $+ (\text{tile position} \times 10)$ to prioritize driving tokens up the private safety track.
• Track Velocity: $+100$ base points $+ (\text{relative progress} \times 5)$ to incentivize continuous directional travel and prioritize hunting.

📊 Side-by-Side Evaluation Suite

To solve the issue of randomized dice rolls skewing algorithm metrics, the script contains a Side-by-Side Algorithm Comparison Mode. "Activate Side-by-Side Algorithm Comparison Mode? (y/n): y"

The Testing Methodology

• When enabled, a fixed random seed (Seed 42) locks the dice array sequence, ensuring that restarting or running tests repeats the exact same sequence of dice rolls.
• Every time an AI player takes a turn, the engine creates two independent deep-copies of the identical active board layout.
• Engine 1 (Pure Minimax) evaluates the roll and returns a choice.
• Engine 2 (Alpha-Beta) evaluates the exact same roll on the identical layout.
• The terminal updates a comparative profile displaying node traversal counts, processing time up to six decimal places, and the total mathematical efficiency gain.

🚀 Performance Comparison Data (Test Cases)

Below is an empirical analysis compiled from runtime testing configurations utilizing a lookahead depth limit of 3 layers ($D=3$). The scenarios evaluate three distinct phases of a live match under a locked seed:

📈 Analytical Breakdown & Final Conclusion

Which Method Performed Better?

The Alpha-Beta Pruning variant clearly outperformed the standard Pure Minimax algorithm across every test case environment.

Why Did Alpha-Beta Work Better?

• Dramatically Lower Node Counts: As shown in the data, Alpha-Beta consistently explores a tiny fraction of the search tree compared to Pure Minimax. In complex mid-to-late game scenarios (Test Cases 2 and 3), Alpha-Beta successfully prunes away over 75% of the paths.
• Exponential Branching Dampened: In Ludo, when multiple tokens exit the yard, the branching factor grows rapidly because each player has up to 3 tokens to choose from. Pure Minimax experiences exponential growth ($O(b^d)$) because it evaluates every single branch. Alpha-Beta mitigates this by eliminating irrelevant branches early.
• Identical Decision Output with 4x Speed Gain: Because Alpha-Beta only cuts branches that are mathematically proven to be worse than currently known choices, the final chosen token move is 100% identical to Minimax. It provides the exact same intelligence while computing roughly 4 times faster.
• Impact of the Goal State Rule: Because our game framework locks tokens permanently once they land on Goal Tile 52, the late-game state space naturally narrows. Alpha-Beta takes massive advantage of this by immediately prioritizing branches leading directly to high-scoring Goal states ($+2000$ points) and pruning alternative lower-scoring defensive maneuvers instantly.