Chess
The rules engine decides which moves are legal. The computer, playing Black, picks a move by looking a few moves ahead and scoring the resulting boards.
What happens after you move
flowchart TD
A["You play a White move"] --> B["Apply it and check for checkmate or stalemate"]
B --> C{"Game over?"}
C -- yes --> D["Show the result"]
C -- no --> E["Search for the best Black move"]
E --> F["Wait until 2 seconds have passed since your move"]
F --> G["Play the move and check the result again"]
G --> H["Your turn"]
Which moves are legal
flowchart LR
A["Generate every move the piece's movement rules allow"] --> B["Try each on a copy of the board"]
B --> C{"Is the mover's own king in check afterward?"}
C -- yes --> D["Discard it"]
C -- no --> E["Keep it"]
E --> F["Add castling and en passant when their conditions hold"]
Applying a move always produces a new board and leaves the old one untouched, which is what lets the search try thousands of hypothetical moves without disturbing the game on screen.
How the computer chooses: negamax with alpha-beta pruning
flowchart TD
A["For each legal Black move"] --> B["Play it on a copy of the board"]
B --> C["Search White's reply, then Black's answer, to a depth of 3 half-moves in all"]
C --> D{"Out of depth?"}
D -- no --> E["Try each reply, best-looking captures first"]
E --> F{"Can this branch still beat a line already found?"}
F -- no --> G["Prune: stop exploring it"]
F -- yes --> C
D -- yes --> H["Quiescence: keep following captures until the position is quiet"]
H --> I["Score the board"]
I --> J["Scores travel back up, each side choosing the best for itself"]
G --> J
J --> K["Pick randomly among moves within 10 centipawns of the best"]
The score
A board is worth the material on it plus a small bonus or penalty for where each piece stands.
| Piece | Value |
|---|---|
| Pawn | 100 |
| Knight | 320 |
| Bishop | 330 |
| Rook | 500 |
| Queen | 900 |
Piece-square tables add or subtract a few points depending on the square, which rewards developing pieces, controlling the center, and keeping the king sheltered. Checkmate scores far above any material count, and a faster mate scores higher than a slower one.
Three ideas that make the search practical
- Negamax. One function scores a position for the side to move, and the opponent's score is the negative of it. Both players use the same code.
- Alpha-beta pruning. Once a reply proves a move is worse than an option already found, the remaining replies to that move are skipped. Trying captures first finds strong lines early, so more branches get skipped.
- Quiescence search. At the depth limit the search keeps following captures. Without this, it could score a board right after its queen takes a pawn, before the recapture.