Initialization
In the previous sections we discussed and wrote all the parts we need to create the Board data structure. Initialization of a new board consists of these stages:
- Create a new board.
- Parse the FEN string and place the pieces.
- Construct all derived state (piece list, Zobrist key, evaluation data, etc.).
The reason why we don’t initialize the board directly after creating it is because the values in many parts of the board are dependent on the position. The steps for getting a usable board are:
let mut board = Board::new();
board.fen_setup(FEN_START_POSITION);It is possible to change Board::new() to accept a FEN string, but I decided to not do that. If there is an error in the FEN string, you’d end up without a board struct. I want the board creation and setup to be two different functions, where creation always succeeds, and any errors in the setup can be handled directly. The drawback is that the programmer needs to remember that just creating the board isn’t enough.
After setting up the pieces as defined in the FEN string, fen_setup() calls
init(). This will make sure that all board components will always have the
correct starting values. This way, calling init() can’t be forgotten. The flow
works as follows:
FEN string
│
▼
fen_setup()
│
├── bb_pieces (raw piece placement from FEN)
├── Initializes several game_state variables fron FEM
│
▼
init()
│
├── bb_side : Derived board-wide occupancy
├── piece_list : Fast lookup structure for piece types
├── zobrist_key : Game state hashing to identify positions
├── phase_value : Current game phase within middle and endgame
├── eval_base : Evaluation base (material and PSQT)
└── next_move : Used while doing takebacks
The init() function
First let’s recall the Board struct:
pub fn new() -> Self {
Self {
bb_pieces: EverySide::new(EveryPiece::new(Bitboard::empty())),
bb_side: EverySide::new(Bitboard::empty()),
game_state: GameState::new(),
history: History::new(),
piece_list: EverySquare::new(Piece::None),
zobrist_randoms: Arc::new(ZobristRandoms::new()),
}
}- bb_pieces: one bitboard per side per piece type.
- bb_side: These are bitboards for each side, computed from bb_pieces. These are used to quickly calculate board occupancy without having to derive it from bb_pieces each time.
- game_state: state that can’t be determined by just looking at the position.
- history: a list of all the moves played in the game.
- zobrist_randoms: The keys used for Zobrist hashing.
I have split init() into different parts, each handling one specific piece of
information:
- Pieces per side
- Piece List
- Zobrist Key
- Game Phase
- Eval Base
- Setting next_move to an empty move.
This is the code:
pub fn init(&mut self) {
// Gather all the pieces of a side into one bitboard.
let pieces_per_side_bitboards = self.init_pieces_per_side_bitboards();
self.bb_side[Side::White] = pieces_per_side_bitboards.0;
self.bb_side[Side::Black] = pieces_per_side_bitboards.1;
// Initialize incrementally updated values.
self.piece_list = self.init_piece_list();
self.game_state.zobrist_key = self.init_zobrist_key();
self.game_state.phase_value = Evaluation::phase_construct(self, Evaluation::parameters());
self.game_state.next_move = Move::new(0);
// Set base evaluation values: also incrementally updated.
let eval_base_values = Evaluation::eval_base_construct(self, Evaluation::parameters());
self.game_state.eval_base[Side::White] = eval_base_values.0;
self.game_state.eval_base[Side::Black] = eval_base_values.1;
}Initializing pieces per side
This function creates one bitboard per side containing all the piece locations of that side. It is coded as follows:
fn init_pieces_per_side_bitboards(&self) -> (Bitboard, Bitboard) {
let mut bb_white: Bitboard = Bitboard::empty();
let mut bb_black: Bitboard = Bitboard::empty();
// Iterate over the bitboards of every piece type.
for (bb_w, bb_b) in self.bb_pieces[Side::White]
.iter()
.zip(self.bb_pieces[Side::Black].iter())
{
bb_white |= *bb_w;
bb_black |= *bb_b;
}
// Return a bitboard with pieces per side.
(bb_white, bb_black)
}It runs through the bitboards of all piece types per side and collects all the white pieces into one bitboard and the black pieces into another. The result is returned. The reason why we want these bitboards is because they allow us to instantly answer questions such as: “Is there a white piece on d6?” It also gives us some nice ergonomics. For example, we can combine the two bitboards like this:
// Pseudo-code
let bb_occupancy = bb_all_white_pieces | bb_all_black_pieces;The bb_occupancy bitboard will contain all pieces on the board, which means
that !bb_occupancy contains all empty squares. This is very useful information
while generating moves. The board will have a lot of helper functions that
encapsulate these operations. These will be discussed in the Board
Functionality chapter.
Initializing the piece list
The piece list has already been discussed in its own section. I’ll shortly recap what it is for. Sometimes, you need to know of what type a piece on a square is, or if any is there at all. Without the piece list, you’d take your square number and then take a look in every one of the 12 piece type bitboards to see if you can find a piece on that square. This is an expensive operation. To speed this up, we incrementally maintain an array of 64 squares, with each square holding the piece type that is there, if any. Now we can just index the square number into the array to find out if, and what piece type is on that square.
The piece list section can be found here.
This is how the piece list is initialized:
fn init_piece_list(&self) -> EverySquare<Piece> {
let bb_w = self.bb_pieces[Side::White]; // White piece bitboards
let bb_b = self.bb_pieces[Side::Black]; // Black piece bitboards
let mut piece_list: EverySquare<Piece> = EverySquare::new(Piece::None);
// piece_type is enumerated, from 0 to 6, with 6 being "no piece."
// The pieces are: K=0, Q=1, R=2, B=3, N=4, P=5, None=6
for (piece_type, (w, b)) in bb_w.iter().zip(bb_b.iter()).enumerate() {
let mut white_pieces = *w; // White pieces of type "piece_type"
let mut black_pieces = *b; // Black pieces of type "piece_type"
// Put white pieces into the piece list.
while white_pieces > Bitboard::empty() {
let square = bits::next(&mut white_pieces);
piece_list[square] = Piece::from(piece_type);
}
// Put black pieces into the piece list.
while black_pieces > Bitboard::empty() {
let square = bits::next(&mut black_pieces);
piece_list[square] = Piece::from(piece_type);
}
}
piece_list
}The function runs through the bitboards to set up the piece type for each square within the piece list. During game play, both the bitboards and the piece list will be incrementally updated as pieces are moved and captured.
Initializing the game state
The game state contains a lot of fields:
pub struct GameState {
pub active_color: Side,
pub castling: Bitboard,
pub half_move_clock: u8,
pub en_passant: Option<Square>,
pub fullmove_number: u16,
pub zobrist_key: u64,
pub phase_value: i32,
pub eval_base: EverySide<EvalBase>,
pub next_move: Move,
}Most of these fields can be directly populated by fen_setup(), because these
values are contained in the FEN string.
- active_color
- castling
- half_move_clock
- en_passant
- fullmove_number
The remaining fields require calculation after fen_setup() places the pieces
onto the board:
- zobrist_key
- phase_value
- eval_base
This is why the initialization of these fields is done by the board’s init()
function. We’ll take a look at them separately.
Initializing the Zobrist Key
To calculate the starting point of the Zobrist Key, the following
function is called by init():
pub fn init_zobrist_key(&self) -> ZobristKey {
// Keep the key here.
let mut key: u64 = 0;
// These are shorthand variables.
let bb_w = self.bb_pieces[Side::White];
let bb_b = self.bb_pieces[Side::Black];
// Iterate through all piece types, for both white and black.
// "piece_type" is enumerated. It will start at 0 (King), then 1
// (Queen), and so on.
for (piece_type, (w, b)) in bb_w.iter().zip(bb_b.iter()).enumerate() {
// These shorthand variables contain the pieces of the type we are now looking at.
let mut white_pieces = *w;
let mut black_pieces = *b;
// Iterate through all the piece locations of the current piece
// type. Get the square the piece is on, and hash that
// side + piece + square combination into the zobrist key.
while white_pieces > Bitboard::empty() {
let square = bits::next(&mut white_pieces);
key ^= self
.zobrist_randoms
.piece(Side::White, Piece::from(piece_type), square);
}
// Same for black.
while black_pieces > Bitboard::empty() {
let square = bits::next(&mut black_pieces);
key ^= self
.zobrist_randoms
.piece(Side::Black, Piece::from(piece_type), square);
}
}
// Hash the castling, active color, and en-passant state.
key ^= self.zobrist_randoms.castling(self.game_state.castling);
key ^= self.zobrist_randoms.side(self.game_state.active_color);
key ^= self.zobrist_randoms.en_passant(self.game_state.en_passant);
// Done; return the key.
key
}The function seems a bit complicated at first, because of the nested for and while loops, but with the help of the comments it should still be fairly straightforward.
The next two parts tie into the engine’s evaluation. The chapter on Evaluation will discuss what the game phase and evaluation basis (eval_base) exactly are. To make these two parts more understandable, we’ll shortly describe them here.
Initializing the game phase
Rustic uses a Tapered Evaluation. This means that the evaluation parameters for the middlegame are different than those for the endgame. As the game moves from middlegame to endgame, less of the middlegame parameters will be used, while the proportion of the end game parameters will become larger.
To facilitate this, the engine has to calculate where the game is on this spectrum. That is called the game phase. In essence, it is just a percentage calculation:
// pseudo code:
let game_phase = current_phase_value / max_phase_value;The current_phase_value drops as pieces are captured. This means the closer
game_phase is to 1, the earlier we are in the game. The closer it is to 0, the
further we are into the endgame.
However, just as with the Zobrist Key, calculating the current game phase value
is costly, so we do this as soon as a position is set up. Then we incrementally
update the value. init() calls phase_construct() with the current
board position and a list of evaluation parameters to determine what the current
phase value is:
pub fn phase_construct(board: &Board, params: &EvalParams) -> i32 {
let mut phase_w: i32 = 0;
let mut phase_b: i32 = 0;
let bb_w = board.bb_pieces[Side::White];
let bb_b = board.bb_pieces[Side::Black];
for (piece_type, (w, b)) in bb_w.iter().zip(bb_b.iter()).enumerate() {
let mut white_pieces = *w;
let mut black_pieces = *b;
while white_pieces > Bitboard::empty() {
phase_w += params[EvalParamsOffset::PHASE_VALUES + piece_type];
bits::next(&mut white_pieces);
}
while black_pieces > Bitboard::empty() {
phase_b += params[EvalParamsOffset::PHASE_VALUES + piece_type];
bits::next(&mut black_pieces);
}
}
phase_w + phase_b
}It runs through all the white and black pieces per piece type. It adds all the phase values for each piece type, for white and black. At the end it adds both phases together and returns the result. Don’t worry if you don’t immediately understand this part. We will get to discuss it in the Evaluation chapter.
Initializing the evaluation basis
This part also ties into the engine’s evaluation. This function sets up the
initial material count and Piece Square Table value for each side, which is
called the Evaluation Basis (or Eval Base). These will be extensively
discussed in the Evaluation Chapter, but will clarify both briefly here:
- The material value is just a count of the material on the board.
- The PSQT value has two parts: a middlegame part, and an endgame part. These values are created by using Piece Square Tables. These tables describe the positional value of a piece on a certain square. The reason why we have middle game and endgame tables is because positional values shift during the game. In the middlegame, you want the king at the edge or in the corner; in the endgame, you want him in the center. In the middlegame you want knights forward on an outpost, but in the endgame, you’d rather have bishops because the board is more open. The Piece Square Tables reflect this.
This is the same story all over again: because calculating the Eval Base from
scratch is expensive, we do this when the position is set up and then update it
incrementally as the position changes. This is the function called by init():
pub fn eval_base_construct(board: &Board, params: &EvalParams) -> (EvalBase, EvalBase) {
let mut material_mg_white: i32 = 0;
let mut material_eg_white: i32 = 0;
let mut material_mg_black: i32 = 0;
let mut material_eg_black: i32 = 0;
let mut psqt_mg_white: i32 = 0;
let mut psqt_eg_white: i32 = 0;
let mut psqt_mg_black: i32 = 0;
let mut psqt_eg_black: i32 = 0;
for (piece_nr, (w, b)) in board.bb_pieces[Side::White]
.iter()
.zip(board.bb_pieces[Side::Black].iter())
.enumerate()
{
let (psqt_mg_offset, psqt_eg_offset) = Evaluation::eval_params_offset(piece_nr);
let mut white = *w;
while white > Bitboard::empty() {
let square = bits::next(&mut white).idx();
let sq = FLIP[square];
material_mg_white += params[EvalParamsOffset::MATERIAL_MG + piece_nr];
material_eg_white += params[EvalParamsOffset::MATERIAL_EG + piece_nr];
psqt_mg_white += params[psqt_mg_offset + sq];
psqt_eg_white += params[psqt_eg_offset + sq];
}
let mut black = *b;
while black > Bitboard::empty() {
let sq = bits::next(&mut black).idx();
material_mg_black += params[EvalParamsOffset::MATERIAL_MG + piece_nr];
material_eg_black += params[EvalParamsOffset::MATERIAL_EG + piece_nr];
psqt_mg_black += params[psqt_mg_offset + sq];
psqt_eg_black += params[psqt_eg_offset + sq];
}
}
let base_white = EvalBase::new(
material_mg_white,
material_eg_white,
psqt_mg_white,
psqt_eg_white,
);
let base_black = EvalBase::new(
material_mg_black,
material_eg_black,
psqt_mg_black,
psqt_eg_black,
);
(base_white, base_black)
}Again, don’t worry too much if you don’t immediately understand this. We will discuss this in the Evaluation chapter. For now, the only important thing is that you know it exists, so you don’t forget to create this functionality when you get to writing the evaluation.
Next…
Now that board creation and initialization are done, we can finally start looking at the Board Functionality, where we define functions to make the board usable by giving us information about the position, or moving pieces.