Moved bits and Zobrist hashing

[leanchess]

Since castling rights in my mailbox implementation are derived from the king's and rook's Moved bit values, the hash key is calculated as follows:

Code: Select all

uint64_t GetKey(Color color, Type type, bool isMoved, Square square) const {
	switch (type) {
	case Type_None:
		return 0;
	case Type_King:
		return isMoved
			&& square == GetKingSquare(color)
				? GetMovedKingKey(color)
				: GetBaseKey(color, type, square);
	case Type_Rook:
		return isMoved
			? GetBaseKey(color, type, square)
				^ GetBaseKey(color, Type_King, GetKingSquare(color))
				^ GetMovedKingKey(color)
			: GetBaseKey(color, type, square);
	default:
		return GetBaseKey(color, type, square);
	}
}

• GetKingSquare() returns e1 for White and e8 for Black (in orthodox).
• GetMovedKingKey() returns one of two extra keys for moved king in e1 for White and in e8 for Black (in orthodox).

Does this make any sense?

Should the keys array be duplicated for moved pieces, i.e. would a branchless GetKey() be worth a 16KB keys array?

[leanchess]

It seems that key entropy can be further reduced thanks to piece indices:

Code: Select all

uint64_t GetKey(Color color, Type type, uint8_t index, bool isMoved, Square square) const {
	switch (type) {
	case Type_None:
		return 0;
	case Type_King:
		return isMoved
			&& square == GetKingSquare(color)
				? GetMovedKingKey(color)
				: GetBaseKey(color, type, square);
	case Type_Rook:
		return isMoved
			&& square == GetRookSquare(color, index)
				? GetBaseKey(color, type, square)
					^ GetBaseKey(color, Type_King, GetKingSquare(color))
					^ GetMovedKingKey(color)
				: GetBaseKey(color, type, square);
	default:
		return GetBaseKey(color, type, square);
	}
}

• GetRookSquare() returns the starting square for the respective rook (a1 for (White,0), h1 for (White,1), a8 for (Black, 0), h8 for (Black, 1) (in orthodox), an illegal square for a higher index).

[Sven]

Since castling rights in my mailbox implementation are derived from the king's and rook's Moved bit values, the hash key is calculated as follows:
...
Does this make any sense?

Should the keys array be duplicated for moved pieces, i.e. would a branchless GetKey() be worth a 16KB keys array?

I can't answer your question directly but since you have mentioned the term "moved bits" I would like to know how you maintain these to get castling rights managed correctly. What do you do, for instance, when unmaking a rook move that started on h1?

[Henk]

Giving pieces an identity is troublesome. My first implementations worked that way.
So better not make them objects.

[dangi12012]

It seems that key entropy can be further reduced thanks to piece indices:

Code: Select all

uint64_t GetKey(Color color, Type type, uint8_t index, bool isMoved, Square square) const {
	switch (type) {
	case Type_None:
		return 0;
	case Type_King:
		return isMoved
			&& square == GetKingSquare(color)
				? GetMovedKingKey(color)
				: GetBaseKey(color, type, square);
	case Type_Rook:
		return isMoved
			&& square == GetRookSquare(color, index)
				? GetBaseKey(color, type, square)
					^ GetBaseKey(color, Type_King, GetKingSquare(color))
					^ GetMovedKingKey(color)
				: GetBaseKey(color, type, square);
	default:
		return GetBaseKey(color, type, square);
	}
}

• GetRookSquare() returns the starting square for the respective rook (a1 for (White,0), h1 for (White,1), a8 for (Black, 0), h8 for (Black, 1) (in orthodox), an illegal square for a higher index).

Your solution seems very verbose. If you were to define all 13 pieces as simple integers it would make this "switch if if complex" code a lot impler.
So just make a well defined enum with: BPawn, BKnight, BBishop, BRook, BQueen, BKing, WPawn, WKnight, WBishop, WRook, WQueen, WKing, Empty
Then you can use these together with the square as a direct lookup into an array. So all switch / if stuff goes away.
Then your whole method above becomes this:

Code: Select all

Hash ^= Zobrist[sq * 13 + piece]

which is probably 35x faster.

If you also add WSpecial and BSpecial, as well as WKing_Wmove then you have also encoded all enpassant and castling possibilities in your hash. (special on left right = rook side that can castle) if special is on the middle ranks then its an enpassant pawn. WKing_Wmove is the same as the wking but its white to move.
With this encoding you can encode the whole FEN information (except movecount) into 4 bits per square.
Which is faster yet again:

Code: Select all

Hash ^= Zobrist[(sq << 4) | piece]

[mar]

I suggest to switch to castling rights stored separately per position - could fit in a byte or byte per side - and then simply a table lookup is your zobrist key
so instead of moved bits you simply lose (some or all) castling rights when your king moves or your rook moves or gets captured

[hgm]

Keeping track of which pieces have moved in the hash key can easily be done by making the unmoved pieces a different type from the unmoved ones, and 'promote' them to the moved type whenever they move. In orthodox Chess you only have to do that for K and R.

Problem is that this doesn't give you a unique key: when the King has moved, you can still have 4 different keys for the same position, depending on whether the Rooks have moved or not. (In Seirawan Chess these positions could of course indeed be different, if you still have ungated pieces.) So it is more efficient to keep 4 bit flags in a separate variable for indicating which castling rights still exist. You can then associate a 'spoiler mask' with each square for indicating which rights get spoiled by a move to or from that square, for updating that variable. The variable can be used as an index in a table of 16 Zobrist keys, which you can XOR with the incrementally updated board key before every probe.

[leanchess]

Thanks everyone for your (mostly) helpful replies. Unfortunately, nobody noticed the biggest fallacy that lies with the original approach, i.e. two unique keys instead of four. I believe deriving the key for the moved king from the rooks (instead of the other way around) should solve that.

Keeping track of which pieces have moved in the hash key can easily be done by making the unmoved pieces a different type from the unmoved ones, and 'promote' them to the moved type whenever they move. In orthodox Chess you only have to do that for K and R.

I am afraid special piece types (as also suggested by Daniel) are not an option, my implementation already has two distinct Pawn types (and not for the reason you may be thinking of), and all the other bits are taken.

You can then associate a 'spoiler mask' with each square for indicating which rights get spoiled by a move to or from that square, for updating that variable. The variable can be used as an index in a table of 16 Zobrist keys, which you can XOR with the incrementally updated board key before every probe.

Would that offer an actual benefit over the double-sized LUT as suggested originally?

[hgm]

After some more thought: these type of issues (another thread just mentioned cornered bishops in FRC) only occur in the opening. So basically you don't want to spend any overhead on them. Even clearing castling rights with a spoiler on every move during the entire game once castling rights have ceased to exist is wasteful. An efficient solution is to reserve one bit of the hash key that is only set for the start squares of the piecec of which the virginity matters. When updating the hash key you can calculate the key modification first. If this doesn't involve any of the critical squares, the dedicated bit will not be set. You test this, and then skip all the code that worries about updating castling rights, or cornered bishops etc. Only when the bit was set in the key modification you can do the usual update of castling-right flags, modify the hash key accordingly when they disappear, and test whether bishop trapping is altered. Perhaps you should use separate bits for black and white to avoid problems with RxR spoiling 2 castlings. The code that handles the cases could clear the bit in the Zobrist key of the from-square of rhe piece that moved, to avoid unnecessari triggering of the code once the condition to be tested is irrevocably gone.

[leanchess]

With this encoding you can encode the whole FEN information (except movecount) into 4 bits per square.
Which is faster yet again:

Code: Select all

Hash ^= Zobrist[(sq << 4) | piece]

How about this?

Code: Select all

Zobrist[(piece << 6) | sq]

I am asking because I am hiding the keys for the e.p. file in the pawns' illegal ranks, and I want them to nicely overflow from WPawn's Rank 8 to BPawn's Rank 1 (an illegal e.p. file can be anything between 0x8 and 0xF). That should also allow my branchless make to remove one LUT access by placing an extra pawn in rank 8 outside the board (0x88, remember?) during a double push.