Please help with Zobrist key incremental updates

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
maksimKorzh
Posts: 214
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Please help with Zobrist key incremental updates

Post by maksimKorzh » Wed Sep 16, 2020 7:32 pm

Hi guys

Currently I have this code to init hash keys and generate hash key for a position:

Code: Select all

// random piece keys [piece][square]
U64 piece_keys[12][64];

// castling keys [bits]
U64 castle_keys[16];

// enpassant keys [square]
U64 enpassant_keys[64];

// side to move keys
U64 side_keys[2];

// init hash keys (with random U64 numbers)
void init_hash_keys()
{
    // loop over piece codes
    for (int piece = P; piece <= k; piece++)
    {
        // loop over squares
        for (int square = 0; square < 64; square++)
        {
            // init piece keys
            piece_keys[piece][square] = get_random_U64_number();
        }
    }
    
    // init side to move keys
    side_keys[white] = get_random_U64_number();
    side_keys[black] = get_random_U64_number();
    
    // loop over board squares
    for (int square = 0; square < 64; square++)
        // init enpassant keys
        enpassant_keys[square] = get_random_U64_number();
    
    // loop over castling keys
    for (int index = 0; index < 16; index++)
        // init castling keys
        castle_keys[index] = get_random_U64_number();
}

// generate unique position key
U64 generate_hash_key()
{
    // final key
    U64 hash_key = 0ULL;
    
    // piece bitboard copy
    U64 bitboard;
    
    // loop over piece bitboards
    for (int piece = P; piece < k; piece++)
    {
        // init piece bitboard copy
        bitboard = bitboards[piece];
        
        // loop over bitboard pieces
        while (bitboard)
        {
            // get piece square
            int square = get_ls1b_index(bitboard);
            
            // hash pieces
            hash_key ^= piece_keys[piece][square];
            
            // reset LS1B
            pop_bit(bitboard, square);
        }
    }
    
    // hash side to move
    hash_key ^= side_keys[side];

    // if enpassant square available
    if (enpassant != no_sq)
        // hash enpassant square
        hash_key ^= enpassant_keys[enpassant];
    
    // hash castling
    hash_key ^= castle_keys[castle];
    
    // return final key
    return hash_key;
}
Now within my make_move function I'm trying to generate_position_key() at the end of the move to see how it SHOULD look like.
On the other hand I'm trying to incrementally update pieces/enpassant/side/castling rights.
It's too complicated and incrementally updated results do not match with the hash keys generated from scratch every time.
I'm trying to XOR pieces and all the stuff back in force but feel really confused.
Could you please give me a clue of how to divide and conquer this process?
Something line first learn to update key if piece is disappeared, then when it appears on new square and so on.

I don't want to clone how other engines doing it and want to implement it on my own.
Please show me the path.
BBC - didactic UCI chess engine written by Code Monkey King
https://github.com/maksimKorzh/bbc

82 video YouTube series
https://www.youtube.com/watch?v=QUNP-Uj ... wfiWNI76Cs

User avatar
pedrox
Posts: 998
Joined: Fri Mar 10, 2006 5:07 am
Location: Basque Country (Spain)
Contact:

Re: Please help with Zobrist key incremental updates

Post by pedrox » Wed Sep 16, 2020 8:43 pm

1º U64 hash2 = hash; // I create a variable to differentiate the value of the current hash key. I also use a couple of variables to store the current empassant and castling.

2º We have to make an xor each time a piece appears or disappears from a square

If there is a castling we have to consider that besides the king we also have to move the rook.

Ej:
/* move rook on castle */
hash2 ^= hash_piece[color[from]][ROOK][from];
color[to] = color[from];
piece[to] = piece[from];
color[from] = EMPTY;
piece[from] = EMPTY;
hash2 ^= hash_piece[color[to]][ROOK][to];

/* remove the piece from the original square */
hash2 ^= hash_piece[side][piece[(int)m.from]][(int)m.from];

/* if there is a capture we have to remove the captured piece/
hash2 ^= hash_piece[side-1][hist_dat[hply].capture][(int)m.to];

/* erase the pawn if this is an en passant move */
if (side == LIGHT) hash2 ^= hash_piece[DARK][PAWN][m.to + 8];
if (side == DARK) hash2 ^= hash_piece[LIGHT][PAWN][m.to - 8];

In the case of promotion, there is no need to do anything since a piece simply disappears from one square and another one appears on another square.

/* put piece "from original" square on "to square" */
hash2 ^= hash_piece[side][piece[(int)m.to]][(int)m.to];

3º we change side and update the hash key
/* switch side */
hash2 ^= hash_side[side];
side ^= 1;

/* put new side */
hash2 ^= hash_side[side];

4º we update empassant and castling if they have been modified
if (old_ep != -1)
hash2 ^= hash_ep[old_ep];
if (ep != -1)
hash2 ^= hash_ep[ep];
if (old_castle != castle) {
hash2 ^= hash_castle[old_castle];
hash2 ^= hash_castle[castle];
}

5º You can now optionally calculate the hash key from zero and compare with this hash2

Here you have if you want a sample in the TSCP makemove function, in this case the hash key, number of pieces and position of the kings are modified incrementally.

Code: Select all

/* makemove() makes a move. If the move is illegal, it
   undoes whatever it did and returns FALSE. Otherwise, it
   returns TRUE. */
int makemove(move_bytes m)
{
	int from = 0, to = 0, old_castle, old_ep;
	U64 hash2 = hash;

	/* test to see if a castle move is legal and move rook
	 (the king is moved with the usual move code later) */
	if (m.bits & 2) {
		if (in_check(side))
			return FALSE;
		switch (m.to) {
			case 62:
				if (color[F1] != EMPTY || color[G1] != EMPTY ||
						attack(F1, xside) || attack(G1, xside))
					return FALSE;
				from = H1;
				to = F1;
				break;
			case 58:
				if (color[B1] != EMPTY || color[C1] != EMPTY || color[D1] != EMPTY ||
						attack(C1, xside) || attack(D1, xside))
					return FALSE;
				from = A1;
				to = D1;
				break;
			case 6:
				if (color[F8] != EMPTY || color[G8] != EMPTY ||
						attack(F8, xside) || attack(G8, xside))
					return FALSE;
				from = H8;
				to = F8;
				break;
			case 2:
				if (color[B8] != EMPTY || color[C8] != EMPTY || color[D8] != EMPTY ||
						attack(C8, xside) || attack(D8, xside))
					return FALSE;
				from = A8;
				to = D8;
				break;
			default:  /* shouldn't get here */
				from = -1;
				to = -1;
				break;
		}
		/* move rook on castle */	
		hash2 ^= hash_piece[color[from]][ROOK][from];
		color[to] = color[from];
		piece[to] = piece[from];
		color[from] = EMPTY;
		piece[from] = EMPTY;
		hash2 ^= hash_piece[color[to]][ROOK][to];
	}

	/* back up information so we can take the move back later. */
	hist_dat[hply].m.b = m;
	hist_dat[hply].capture = piece[(int)m.to];
	hist_dat[hply].castle = old_castle = castle;
	hist_dat[hply].ep = old_ep = ep;
	hist_dat[hply].fifty = fifty;
	hist_dat[hply].hash = hash;
	
	/* remove the piece */
	hash2 ^= hash_piece[side][piece[(int)m.from]][(int)m.from];
	piece[(int)m.to] = piece[(int)m.from];
	piece[(int)m.from] = EMPTY;
	color[(int)m.to] = color[(int)m.from];
	color[(int)m.from] = EMPTY;
	
	/* update the castle, en passant, and fifty-move-draw variables */
	castle &= castle_mask[(int)m.from] & castle_mask[(int)m.to];
	if (m.bits & 8) {
		if (side == LIGHT)
			ep = m.to + 8;
		else
			ep = m.to - 8;
	}
	else
		ep = -1;	
	if (m.bits & 17)
		fifty = 0;
	else
		++fifty;
		
	/* update positions of the kings, hash and number of pieces in captures */
	if (side == DARK) {
		if (piece[(int)m.to] == KING)
			bk = (int)m.to;
		if (hist_dat[hply].capture != EMPTY)  {
			hash2 ^= hash_piece[LIGHT][hist_dat[hply].capture][(int)m.to];
			switch(hist_dat[hply].capture) {
				case PAWN:
					wp--;
					break;
				case KNIGHT:
					wn--;
					break;
				case BISHOP:
					wb--;
					break;
				case ROOK:
					wr--;
					break;
				case QUEEN:
					wq--;
					break;
			}
		}
	}
	else if (side == LIGHT) {
		if (piece[(int)m.to] == KING)
			wk = (int)m.to;
		if (hist_dat[hply].capture != EMPTY)  {
			hash2 ^= hash_piece[DARK][hist_dat[hply].capture][(int)m.to];
			switch(hist_dat[hply].capture) {
				case PAWN:
					bp--;
					break;
				case KNIGHT:
					bn--;
					break;
				case BISHOP:
					bb--;
					break;
				case ROOK:
					br--;
					break;
				case QUEEN:
					bq--;
					break;
			}
		}
	}
	
	/* erase the pawn if this is an en passant move */
	if (m.bits & 4) {
		if (side == LIGHT) {
			color[m.to + 8] = EMPTY;
			piece[m.to + 8] = EMPTY;
			bp--;
			hash2 ^= hash_piece[DARK][PAWN][m.to + 8];
		}
		else {
			color[m.to - 8] = EMPTY;
			piece[m.to - 8] = EMPTY;
			wp--;
			hash2 ^= hash_piece[LIGHT][PAWN][m.to - 8];
		}
	}

	/* promote */
	if (m.bits & 32) {
		piece[(int)m.to] = m.promote;
		switch (m.promote) {
			case QUEEN:
				if (side == LIGHT) {
					wp--;
					wq++;
				}
				else {
					bp--;
					bq++;
				}
				break;
			case ROOK:
				if (side == LIGHT) {
					wp--;
					wr++;
				}
				else {
					bp--;
					br++;
				}
				break;
			case BISHOP:
				if (side == LIGHT) {
					wp--;
					wb++;
				}
				else {
					bp--;
					bb++;
				}
				break;
			case KNIGHT:
				if (side == LIGHT) {
					wp--;
					wn++;
				}
				else {
					bp--;
					bn++;
				}
				break;
		}
	}
	
	/* put piece */
	hash2 ^= hash_piece[side][piece[(int)m.to]][(int)m.to];

	/* switch sides and test for legality (if we can capture
	   the other guy's king, it's an illegal position and
	   we need to take the move back) */
	hash2 ^= hash_side[side];
	side ^= 1;
	xside ^= 1;
	
	++ply;
	++hply;
	
	if (in_check(xside)) {
		takeback();
		return FALSE;
	}
	
	hash2 ^= hash_side[side];
	if (old_ep != -1)
		hash2 ^= hash_ep[old_ep];
	if (ep != -1)
		hash2 ^= hash_ep[ep];
	if (old_castle != castle) {
		hash2 ^= hash_castle[old_castle];
		hash2 ^= hash_castle[castle];
	}
	
	/* set_hash();
	assert(hash == hash2); */
	
	hash = hash2;
	
	return TRUE;
}

maksimKorzh
Posts: 214
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Please help with Zobrist key incremental updates

Post by maksimKorzh » Wed Sep 16, 2020 9:36 pm

pedrox wrote:
Wed Sep 16, 2020 8:43 pm
1º U64 hash2 = hash; // I create a variable to differentiate the value of the current hash key. I also use a couple of variables to store the current empassant and castling.

2º We have to make an xor each time a piece appears or disappears from a square

If there is a castling we have to consider that besides the king we also have to move the rook.

Ej:
/* move rook on castle */
hash2 ^= hash_piece[color[from]][ROOK][from];
color[to] = color[from];
piece[to] = piece[from];
color[from] = EMPTY;
piece[from] = EMPTY;
hash2 ^= hash_piece[color[to]][ROOK][to];

/* remove the piece from the original square */
hash2 ^= hash_piece[side][piece[(int)m.from]][(int)m.from];

/* if there is a capture we have to remove the captured piece/
hash2 ^= hash_piece[side-1][hist_dat[hply].capture][(int)m.to];

/* erase the pawn if this is an en passant move */
if (side == LIGHT) hash2 ^= hash_piece[DARK][PAWN][m.to + 8];
if (side == DARK) hash2 ^= hash_piece[LIGHT][PAWN][m.to - 8];

In the case of promotion, there is no need to do anything since a piece simply disappears from one square and another one appears on another square.

/* put piece "from original" square on "to square" */
hash2 ^= hash_piece[side][piece[(int)m.to]][(int)m.to];

3º we change side and update the hash key
/* switch side */
hash2 ^= hash_side[side];
side ^= 1;

/* put new side */
hash2 ^= hash_side[side];

4º we update empassant and castling if they have been modified
if (old_ep != -1)
hash2 ^= hash_ep[old_ep];
if (ep != -1)
hash2 ^= hash_ep[ep];
if (old_castle != castle) {
hash2 ^= hash_castle[old_castle];
hash2 ^= hash_castle[castle];
}

5º You can now optionally calculate the hash key from zero and compare with this hash2

Here you have if you want a sample in the TSCP makemove function, in this case the hash key, number of pieces and position of the kings are modified incrementally.

Code: Select all

/* makemove() makes a move. If the move is illegal, it
   undoes whatever it did and returns FALSE. Otherwise, it
   returns TRUE. */
int makemove(move_bytes m)
{
	int from = 0, to = 0, old_castle, old_ep;
	U64 hash2 = hash;

	/* test to see if a castle move is legal and move rook
	 (the king is moved with the usual move code later) */
	if (m.bits & 2) {
		if (in_check(side))
			return FALSE;
		switch (m.to) {
			case 62:
				if (color[F1] != EMPTY || color[G1] != EMPTY ||
						attack(F1, xside) || attack(G1, xside))
					return FALSE;
				from = H1;
				to = F1;
				break;
			case 58:
				if (color[B1] != EMPTY || color[C1] != EMPTY || color[D1] != EMPTY ||
						attack(C1, xside) || attack(D1, xside))
					return FALSE;
				from = A1;
				to = D1;
				break;
			case 6:
				if (color[F8] != EMPTY || color[G8] != EMPTY ||
						attack(F8, xside) || attack(G8, xside))
					return FALSE;
				from = H8;
				to = F8;
				break;
			case 2:
				if (color[B8] != EMPTY || color[C8] != EMPTY || color[D8] != EMPTY ||
						attack(C8, xside) || attack(D8, xside))
					return FALSE;
				from = A8;
				to = D8;
				break;
			default:  /* shouldn't get here */
				from = -1;
				to = -1;
				break;
		}
		/* move rook on castle */	
		hash2 ^= hash_piece[color[from]][ROOK][from];
		color[to] = color[from];
		piece[to] = piece[from];
		color[from] = EMPTY;
		piece[from] = EMPTY;
		hash2 ^= hash_piece[color[to]][ROOK][to];
	}

	/* back up information so we can take the move back later. */
	hist_dat[hply].m.b = m;
	hist_dat[hply].capture = piece[(int)m.to];
	hist_dat[hply].castle = old_castle = castle;
	hist_dat[hply].ep = old_ep = ep;
	hist_dat[hply].fifty = fifty;
	hist_dat[hply].hash = hash;
	
	/* remove the piece */
	hash2 ^= hash_piece[side][piece[(int)m.from]][(int)m.from];
	piece[(int)m.to] = piece[(int)m.from];
	piece[(int)m.from] = EMPTY;
	color[(int)m.to] = color[(int)m.from];
	color[(int)m.from] = EMPTY;
	
	/* update the castle, en passant, and fifty-move-draw variables */
	castle &= castle_mask[(int)m.from] & castle_mask[(int)m.to];
	if (m.bits & 8) {
		if (side == LIGHT)
			ep = m.to + 8;
		else
			ep = m.to - 8;
	}
	else
		ep = -1;	
	if (m.bits & 17)
		fifty = 0;
	else
		++fifty;
		
	/* update positions of the kings, hash and number of pieces in captures */
	if (side == DARK) {
		if (piece[(int)m.to] == KING)
			bk = (int)m.to;
		if (hist_dat[hply].capture != EMPTY)  {
			hash2 ^= hash_piece[LIGHT][hist_dat[hply].capture][(int)m.to];
			switch(hist_dat[hply].capture) {
				case PAWN:
					wp--;
					break;
				case KNIGHT:
					wn--;
					break;
				case BISHOP:
					wb--;
					break;
				case ROOK:
					wr--;
					break;
				case QUEEN:
					wq--;
					break;
			}
		}
	}
	else if (side == LIGHT) {
		if (piece[(int)m.to] == KING)
			wk = (int)m.to;
		if (hist_dat[hply].capture != EMPTY)  {
			hash2 ^= hash_piece[DARK][hist_dat[hply].capture][(int)m.to];
			switch(hist_dat[hply].capture) {
				case PAWN:
					bp--;
					break;
				case KNIGHT:
					bn--;
					break;
				case BISHOP:
					bb--;
					break;
				case ROOK:
					br--;
					break;
				case QUEEN:
					bq--;
					break;
			}
		}
	}
	
	/* erase the pawn if this is an en passant move */
	if (m.bits & 4) {
		if (side == LIGHT) {
			color[m.to + 8] = EMPTY;
			piece[m.to + 8] = EMPTY;
			bp--;
			hash2 ^= hash_piece[DARK][PAWN][m.to + 8];
		}
		else {
			color[m.to - 8] = EMPTY;
			piece[m.to - 8] = EMPTY;
			wp--;
			hash2 ^= hash_piece[LIGHT][PAWN][m.to - 8];
		}
	}

	/* promote */
	if (m.bits & 32) {
		piece[(int)m.to] = m.promote;
		switch (m.promote) {
			case QUEEN:
				if (side == LIGHT) {
					wp--;
					wq++;
				}
				else {
					bp--;
					bq++;
				}
				break;
			case ROOK:
				if (side == LIGHT) {
					wp--;
					wr++;
				}
				else {
					bp--;
					br++;
				}
				break;
			case BISHOP:
				if (side == LIGHT) {
					wp--;
					wb++;
				}
				else {
					bp--;
					bb++;
				}
				break;
			case KNIGHT:
				if (side == LIGHT) {
					wp--;
					wn++;
				}
				else {
					bp--;
					bn++;
				}
				break;
		}
	}
	
	/* put piece */
	hash2 ^= hash_piece[side][piece[(int)m.to]][(int)m.to];

	/* switch sides and test for legality (if we can capture
	   the other guy's king, it's an illegal position and
	   we need to take the move back) */
	hash2 ^= hash_side[side];
	side ^= 1;
	xside ^= 1;
	
	++ply;
	++hply;
	
	if (in_check(xside)) {
		takeback();
		return FALSE;
	}
	
	hash2 ^= hash_side[side];
	if (old_ep != -1)
		hash2 ^= hash_ep[old_ep];
	if (ep != -1)
		hash2 ^= hash_ep[ep];
	if (old_castle != castle) {
		hash2 ^= hash_castle[old_castle];
		hash2 ^= hash_castle[castle];
	}
	
	/* set_hash();
	assert(hash == hash2); */
	
	hash = hash2;
	
	return TRUE;
}

Thank you so much Pedro!
This is exactly what I was looking for.
TSCP example is great.

BTW I was confused when realized that TSCP actually does not have incremental Zobrist keys update but instead rebuilds it from scratch via set_hash() at the end of make move.
BBC - didactic UCI chess engine written by Code Monkey King
https://github.com/maksimKorzh/bbc

82 video YouTube series
https://www.youtube.com/watch?v=QUNP-Uj ... wfiWNI76Cs

Post Reply