Intelligent Chess bot

A chess engine built on classical adversarial search: minimax with alpha-beta pruning at its base, then a stack of refinements — iterative deepening, transposition tables, move ordering, null-move pruning, aspiration windows, and quiescence search — that make the textbook algorithm play well under a real clock.

Chess is a zero-sum game, so one number scores every position: the engine (MAX) picks the child of highest value, assuming the opponent (MIN) always answers with the lowest. Minimax computes that value by recursing to the leaves,

but the full tree is $O(b^m)$ — and chess branches at $b\approx 35$. Searching it outright is hopeless; every refinement below reduces how much of it is searched.

Alpha-beta pruning keeps minimax's answer while skipping subtrees that cannot matter. The search carries a window $[\alpha ,\beta ]$ — the best score each side can already force — and cuts off the moment a node's value falls outside it:

With perfect move ordering, alpha-beta examines only $O(b^{m/2})$ nodes — the same horizon for half the exponent, which in practice doubles the reachable search depth.

Each refinement past alpha-beta strengthens either the pruning or the evaluation:

• Iterative deepening searches depth $1,2,3,\dots$ until time runs out — and each pass's best line seeds the next pass's move ordering.
• Transposition tables memoize positions reached by different move orders, so a position is searched once, not once per path.
• Move ordering tries captures and killer moves first, pushing real play toward that $O(b^{m/2})$ best case.
• Null-move pruning gives the opponent a free move; if the position is still winning, the subtree is cut without a full search.
• Aspiration windows start each iteration with a narrow $[\alpha ,\beta ]$ guessed from the last one, re-searching only when the score lands outside it.
• Quiescence search extends the search at the horizon until the position is quiet, so the evaluation never scores a board mid-capture.