The Six AI Engines

Copy the legal-move list into an ArrayList, call Collections.shuffle(), return index 0. No evaluation. No lookahead. The engine is literally rolling dice.

A perfect baseline. Any algorithm must beat Random to be considered a chess AI at all. Also useful for variety in self-play training games.

For every legal move: execute it on a trial board, call the evaluator (material + piece-square tables), undo. Keep the highest-scoring move. No recursion.

Greedy always takes the queen — even if you'll lose your own queen on the very next move. It cannot see one move ahead. MiniMax solves this.

Alternate between MAX (your best move) and MIN (opponent's best reply) until a fixed depth. Every leaf is scored. Scores propagate back up — MAX nodes keep the largest, MIN nodes keep the smallest.

MiniMax visits every node in the tree — b^d nodes at depth d with branching factor b. At depth 3 with ~30 moves, that's 27,000 nodes. Alpha-Beta dramatically cuts this.

Root=MAX. Three MIN children (A, B, C) each with three leaves. Leaf scores: A=[3,1,7]→MIN=1 · B=[4,9,5]→MIN=4 · C=[2,8,6]→MIN=2. Root picks MAX(1,4,2)=4 → plays B.

Two bounds travel through the tree: α (best MAX has found) and β (best MIN has found). When α ≥ β at any node, that branch can never affect the result — stop searching it immediately.

After searching A=1 and B=4, root α=4. When C's first leaf returns 2, MIN at C will never exceed 2 — which can't beat 4. Leaves C2 and C3 are pruned (red ✕). Same answer, fewer nodes.

Alpha-Beta prunes most aggressively when the best moves are searched first. MVV-LVA capture ordering (big piece captured by small piece first) brings pruning close to the theoretical √b^d speedup.

Each completed depth is a guaranteed best move. If time runs out mid-depth-4, the depth-3 result is returned. Restarting is cheap because the Transposition Table caches all positions, so depth 3 re-search takes milliseconds.

A 1M-entry hash map keyed by Zobrist hash (64-bit XOR fingerprint). Stores: score, search depth, bound type (EXACT / LOWER / UPPER). A cache hit avoids re-searching an entire subtree.

Instead of searching (−∞, +∞), search a narrow ±50 centipawn window around the previous iteration's score. If the result falls outside the window, re-search with a wider window. Saves ~20% of nodes on average.

Before searching a node, try passing the move (opponent plays twice). If the position is still better than beta after this "free gift" to the opponent, the branch is pruned with reduction R=2. Skips ~30% of nodes in the middlegame.

Moves ordered later in the list are statistically worse. Search them at depth−2 first. Only if they raise alpha do we re-search at full depth. Applied to non-captures, non-promotions, after the 4th move at depth≥3.

At depth=0, keep searching captures until the position is "quiet." Prevents the horizon effect: the engine won't stop right before an obvious recapture that loses a piece.

At depth 1 (margin 200cp) and depth 2 (margin 400cp), if the static evaluation + margin < α, skip the move entirely — it can't possibly raise alpha. Jump straight to quiescence.