The Nest
Explore
0
Chess engine in zig 
# Pistike Chess Engine

This engine is the zig implementation of
[Bitboard chess engine in C](https://www.youtube.com/playlist?list=PLmN0neTso3Jxh8ZIylk74JpwfiWNI76Cs).

## 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 2x`u6`.

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](https://www.chessprogramming.org/Magic_Bitboards).

This engine uses the [Plain](https://www.chessprogramming.org/Magic_Bitboards#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](https://www.chessprogramming.org/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](https://tests.stockfishchess.org/api/nn/nn-62ef826d1a6d.nnue) 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](https://www.chessprogramming.org/Negamax).

The basic search is enhanced with the following techniques:
 - [Alpha-beta pruning](https://www.chessprogramming.org/Alpha-Beta)
 - [Checkmate and Stalemate detection](https://youtu.be/lAAdjCkWd9s)
 - [Quiescence Search](https://www.chessprogramming.org/Quiescence_Search)
 - [Move Scoring](https://www.chessprogramming.org/Move_Ordering)
    - [MVV-MLA](https://www.chessprogramming.org/MVV-LVA)
    - [Killer Move](https://www.chessprogramming.org/Killer_Move)
    - [History Heuristics](https://www.chessprogramming.org/History_Heuristic)
    - [Iterative Deepening](https://www.chessprogramming.org/Iterative_Deepening)
    - [PV-Move](https://www.chessprogramming.org/PV-Move)
    - [PVS - Principle Variation Search](https://web.archive.org/web/20071030220825/http://www.brucemo.com/compchess/programming/pvs.htm)
    - [Late Move Reduction - LMR](https://www.chessprogramming.org/Late_Move_Reductions)
    - [NULL move pruning](https://web.archive.org/web/20071031095933/http://www.brucemo.com/compchess/programming/nullmove.htm)
    - Aspiration window

These fancy names may seem intimidating, but implementing them is not that hard.

## Interesting links

[Bruce Moreland](https://web.archive.org/web/20070922181832/http://www.brucemo.com/compchess/programming/index.htm)
[Transposition Table Scoring](https://raw.githubusercontent.com/maksimKorzh/chess_programming/master/src/bbc/tt_search_mating_scores/TT_mate_scoring.txt)

### NNUE
- [Using NNUE for Shogi translations](https://github.com/asdfjkl/nnue/)
- [Stockfish NNUE layout](https://github.com/glinscott/nnue-pytorch/blob/master/docs/nnue.md)
- [Neural Networks for Chess](https://github.com/asdfjkl/neural_network_chess)

### NNUE readers
- [https://github.com/dshawul/nnue-probe](https://github.com/dshawul/nnue-probe)
- [https://github.com/jdart1/nnue/](https://github.com/jdart1/nnue/)

## TODO

### Before first release
- finnish BBC series
- use incremental nnue evaluation
- NULL move pruning: see comment below the [video](https://www.youtube.com/watch?v=n6xAzopULxU&list=PLmN0neTso3Jxh8ZIylk74JpwfiWNI76Cs&index=63), this is not a perfect solution

### Soon
- Check [SEE - Static Exchange Evaluation](https://web.archive.org/web/20070606043300/http://www.brucemo.com/compchess/programming/quiescent.htm)

### Later
- train our own network and use that
- [Gigantua - fast movegen](https://www.codeproject.com/Articles/5313417/Worlds-fastest-Bitboard-Chess-Movegenerator)