Pistike Chess Engine
This engine is the zig implementation of Bitboard chess engine in C.
Architecture
Basics
Every chess engine consists of 3 major parts:
- Move generator (which is tightly coupled with Board representation): Move generators just generate all the possible moves for a given state.
- Evaluation: Evaluation tells our engine if a given state is good or bad for us. Is it worth taking that piece? Should I move my pawn instead? etc.
- Search: A chess engine just dumbly creates every move and evaluates the position after every move. Searching is about ruling out moves and ordering them to find the best move.
Move generator
BitBoard
This engine uses a bitboard representation. A chess board got 8x8 squares, so a u6
number can represent the whole board.
You have to separate the pieces (pawn, knight, bishop, rook, queen, king) and colors, which
gives means 12 u6 numbers.
It is also convenient to store the occupied squares for each side, that takes 2xu6.
see BitBoard and GameState in Board.zig
Attacks
Based on the rules for each piece You just generate all possibilities for a given square. For leaper pieces (pawn, knight and king) it is not that hard, but the sliding pieces (bishop, rook, and queen) have a lot of possibilities. To calculate bishop and rook attacks the state of the art method is using Magic Bitboards.
This engine uses the Plain method, which is the simplest one.
The Attacks.zig file contains everything for attacks. Note, that we have to initialize
bishop and rook attacks with initSliderAttacks() before using them with getBishopAttacks(),
getRookAttacks() and genQueenAttacks().
The findMagicNumber() function finds magic numbers. You should only run that once and
just paste it in Your code, it makes no sense to regenerate the same numbers every time.
Generating moves
We created the attacks, now it is time to apply them. The generateMoves() function in
Board.zig does exactly that. For every piece generates all the possible moves given
the current Board state.
Unlike the previous step this is for a given GameState, not some general rule.
The isSquareAttacked() helps to determine if a castling move is possible or not. We
will also use this function to discard invalid moves in next step.
Making moves
After generating all possible moves it is time to make those moves. We are still in
Board.zig, but we use the makeMove() function for that.
This function takes a move, updates GameState's bitboards and occupancies,
sets the new side etc. The final result is a new GameState.
This function finally checks if that is a valid move (eg. the king is not in check)
with isSquareAttacked() and returns true or false accordingly.
Preserving and restoring game states
When the chess engine makes a move the board state changes. We have to use backup() and
restore() functions to reset the states after a given move.
This is called the Copy-Make method.
Evaluation
In chess for years the only option for evaluation was a bunch of handcrafted rules. This
engine can use a very simple table-based evaluation in eval.zig. That is the default
for development as its simplicity makes it predictable which makes debugging easier.
However You can replace eval.evaluate() in search.zig with nnue.evaluate(). Download
the nnue file from here put
it next to the engine binary and it will use Stockfish's NNUE from that point.
NOTE: It can only read SFNNv1 files, so do not try to use later networks, they will not work.
Search
Searching is the method of collecting all the possible moves and picking the best move.
Negamax
The base searching algorithm used here is Negamax.
The basic search is enhanced with the following techniques:
These fancy names may seem intimidating, but implementing them is not that hard.
Interesting links
Bruce Moreland Transposition Table Scoring
NNUE
NNUE readers
TODO
Before first release
- finnish BBC series
- use incremental nnue evaluation
- NULL move pruning: see comment below the video, this is not a perfect solution
Soon
Later
- train our own network and use that
- Gigantua - fast movegen