98 lines
4.0 KiB
Markdown
98 lines
4.0 KiB
Markdown
# chess
|
|
|
|
An artificially intelligent chess player: full rules, legal move generation,
|
|
and an alpha-beta search engine with a UCI interface.
|
|
|
|
## Install
|
|
|
|
```sh
|
|
go install github.com/zg/chess/cmd/chess@latest
|
|
```
|
|
|
|
## Use
|
|
|
|
```sh
|
|
chess # play against the engine (you are white)
|
|
chess -uci # run as a UCI engine for a GUI
|
|
chess -perft 5 # validate move generation
|
|
chess -perft 4 -divide # nodes per root move, for debugging
|
|
chess -fen "8/2p5/..." -depth 8
|
|
```
|
|
|
|
In the interactive game, moves are long algebraic (`e2e4`, `e7e8q`), plus
|
|
the commands `fen`, `undo` and `quit`.
|
|
|
|
## Correctness
|
|
|
|
Move generation is verified by **perft** — counting the leaf nodes of the
|
|
move tree to a given depth and comparing against counts that are exactly
|
|
known from the chess programming literature:
|
|
|
|
| position | depth | nodes |
|
|
|---|---|---|
|
|
| starting position | 5 | 4,865,609 |
|
|
| kiwipete | 4 | 4,085,603 |
|
|
| endgame (position 3) | 5 | 674,624 |
|
|
| promotions (position 4) | 4 | 422,333 |
|
|
| rook capture (position 5) | 4 | 2,103,487 |
|
|
| middlegame (position 6) | 4 | 3,894,594 |
|
|
|
|
This matters more than any hand-written case: a single missing or spurious
|
|
move anywhere in the tree changes the count. The six positions are the
|
|
standard set precisely because each stresses a different corner — en
|
|
passant, promotion, castling through check, pins, and castling rights lost
|
|
when a rook is captured on its home square. `-divide` reports counts per
|
|
root move, which is how a mismatch is traced to the move that causes it.
|
|
|
|
## Design notes
|
|
|
|
**Legality is checked by making the move.** Moves are generated
|
|
pseudo-legally, then each is played and the mover's king tested for attack.
|
|
Computing pins and check evasions directly would be faster, but this is
|
|
correct by construction — there is no second rule to keep in sync with the
|
|
first.
|
|
|
|
**Attacks are computed outward from the square**, not by iterating every
|
|
enemy piece: from the square in question, look along each ray and knight
|
|
jump and ask what is sitting there. That makes `isAttacked` independent of
|
|
how many pieces are on the board.
|
|
|
|
**File wrapping is checked explicitly.** Move offsets are applied as
|
|
(file, rank) deltas with an explicit bounds check, rather than as raw index
|
|
arithmetic. A knight on a1 having more than two moves is the classic symptom
|
|
of getting this wrong, and there is a test for exactly that.
|
|
|
|
**Castling rights are revoked on capture, not just on movement.** A rook
|
|
captured on its home square ends that right just as surely as a rook that
|
|
moved. Both ends of every move are checked against the four corner squares.
|
|
Missing this allows illegal castling many moves later, and it is one of the
|
|
things perft position 5 exists to catch.
|
|
|
|
**Search is iterative deepening alpha-beta.** Searching depth 1, then 2,
|
|
then 3 sounds wasteful but is not: the previous iteration's best move is
|
|
searched first at the next depth, and good move ordering is what makes
|
|
alpha-beta prune. There is also always a usable move in hand when time runs
|
|
out. Ordering is by previous-best, then MVV-LVA captures, then killer moves.
|
|
A test asserts depth 4 visits under 100,000 nodes against perft(4)'s 197,281
|
|
positions — i.e. that pruning is actually happening.
|
|
|
|
**Quiescence search runs past the depth limit on captures only.** Stopping
|
|
mid-exchange produces nonsense: a position where the queen was just captured
|
|
looks lost even when the recapture is obvious. A test verifies the engine
|
|
does not take a defended pawn with its queen.
|
|
|
|
**Mate scores include the distance to mate**, so a mate in 2 outranks a mate
|
|
in 4 and the engine actually finishes the game rather than shuffling.
|
|
|
|
## Tests
|
|
|
|
```sh
|
|
go test ./... # includes full perft
|
|
go test -short ./... # skips the deepest perft levels
|
|
go test -bench=. ./...
|
|
```
|
|
|
|
Engine tests assert on *outcomes* rather than specific moves where a
|
|
position admits several correct answers — a mate-in-one test checks that the
|
|
chosen move actually delivers mate, not that it matches a hardcoded string.
|