Chess AI

Overview

Being an avid Chess player, I challenged myself to build a chess AI from scratch. The AI can look 3 or 4 moves ahead, depending on the difficulty chosen by the user.

There's a beautiful art in algorithms.

The Algorithms

Minimax

A recursive backtracking algorithm as the foundation for the AI. While its functionality is to search every possible board configuration to determine the best move, it uses brute force, and thus wildly inefficient for a game such as chess.

For example, the computer will have to calculate:

This means relying solely on the minimax algorithm is impractical. (Unless you like blowing up computers).

Alpha Beta Pruning

Prune certain branches in the search tree that are deemed irrelevant and unnecessary to search which speeds up minimax.

Alpha-beta pruning reduces the computational time by a "square root", but only in the best case scenario. What would have taken minimax 100 seconds to determine the best move, will be shortened to only 10 seconds when adding alpha-beta pruning. Sadly, alpha-beta pruning will not typically perform this well, taking an intermediate amount of time to run... unless optimized.

Heuristic Boards

Prioritize move ordering via priority queues to optimize the effectiveness of alpha-beta pruning. We provide the algorithm with moves that are most likely the best for each chess piece to help alpha-beta better determine which branches to immediately eliminate, cutting down computations significantly.

Transposition Table

Even though we use an optimized version of alpha-beta pruning to eliminate branches, the minimax algorithm computes many duplicate board configurations in other branches. To eliminate duplicates, we hash every unique board configuration as a key-value pair (Map).

Each board configuration is represented as a long numeric value called a Zobrist key. This Zobrist key is hashed, and the next board configuration is formed by taking an empty string and perfoming bitwise operation, XOR, on it with the previous Zobrist key to cut down on computation time. XOR operation is reversible which makes this hash useful - we can add and remove pieces from the board efficiently by simply XOR the hash with the Zobrist key.

The minimax algorithm gives a numeric score for each board configuration which is stored as the value for each Zobrist key. If we come across a board with the same key that is already hashed, then we return the score given to that position. After the AI finds the best move, we clear the key-value pair Map to save memory.

Goals

Build a functioning chess game where a player can drag and drop pieces (legally) on a board, take pieces, put a King in check, checkmate, en passant, promote pawns, and castle.

Implement a functioning chess AI that plays legal moves.

Have the AI look 3 or 4 moves ahead (depth of 6 or 8 respecitvely).

Optimize the minimax algorithm through alpha-beta pruning, heuristic boards, and transposition tables.

Test each algorithm incrementally to determine proper behavior and if optimization is taking place.

Next Steps

Redo completely - build a fullstack application that calculates the moves on a server and sends the best move as a response.

Optimize the algorithm further by integrating a magic bit board and quiescence search.

Train the AI on openings, book moves, etc.

Tweak the AI - fix weird repetitive King moves, and if AI is in check, either have pieces protect the King or have the King move.

Allow for checkmate or draw against AI.

Implement a responsive design and an emphasis on mobile.

More options for difficulty (AI ELO level), as well as an option to play as the black pieces.