Problems with my transposition table implementation?

[algerbrex]

So I've made some progress since the last post and have gotten my engine to the point where it makes moves based solely on material gain. Of course, this isn't great, but I'm going to start to improve its evaluating scheme by adding piece-square tables.

But before I do that, I needed to implement triple repetition draw detection, since my engine will often just shuffle a rook back and forth even when it's in a clearly winning position, since it thinks it's doing well maintaining its material advantage.

To do this, and for general speed-ups, I took a crack at making a transposition table using Zobrist hashing. I tested the function which produces the Zobrist keys pretty well, and I made sure I tested that the initialize hash was being updated correctly when my engine made and unmade a move. But for some reason, I have two big problems:

• I'm getting incorrect perft numbers, which is the biggest problem

• Using even this buggy transposition table shows hardly any speed-ups whatsoever, which is pretty disappointing. I do realize that perft speed doesn't really play a huge factor in a lower ELO created engine, but I do want transposition tables to improve the speed of my minimax implementation

Any advice on where I'm going wrong in my implementation? (The language I'm doing all of this in is golang btw)

Here is where I initialize the 12*64 random numbers:

Code: Select all

const (
	ZobristRandomNumbersSize = 12 * 64
	TranspositionTableSize   = 1000
)

var TranspositionTable [TranspositionTableSize]Entry
var ZobristTable [ZobristRandomNumbersSize]uint64

func init() {
	for index := 0; index < ZobristRandomNumbersSize; index++ {
		ZobristTable[index] = rand.Uint64()
	}
	TranspositionTable = [TranspositionTableSize]Entry{}
}

Here is my code for creating a hash key. The way I use, which is what I thought would work, is by assigning a constant representing the chunk each piece has in the ZobristTable (e.g. WhitePawns get the first chunk of 64 numbers, WhiteKnights get the second chunk). And each chunk is multiplied by 64 to get the starting index of the chunk in the table, and then the current board index is added to that to get the right square. Here is a snippet of the code which I'm explaining:

Code: Select all

const (
	WhitePawnChunkStart = 0
	WhiteKnightChunkStart = 1
)

var hash uint64
for index := 0; index < 64; index++ {
	if board.Pieces[index] != 0 {
		if board.Pieces[index]&Pawn != 0 && board.Pieces[index]&White != 0 {
			hash ^= ZobristTable[WhitePawnChunkStart*64+index]
		} else if board.Pieces[index]&Knight != 0 && board.Pieces[index]&White != 0 {
			hash ^= ZobristTable[WhiteKnightChunkStart*64+index]
                ...
}

I use the same process to find the right number from ZobristTable when updating the initialize Zobrist hash in DoMove and UndoMove.

Here is my code for putting an entry in the TranspositionTable:

Code: Select all

type Entry struct {
	Hash      uint64
	Depth     int
	NodeCount uint64
}

func getHashEntry(board *Board, depth int) Entry {
	entry := TranspositionTable[board.InitZobristHash%TranspositionTableSize]
	if entry.Hash == board.InitZobristHash && entry.Depth >= depth {
		return entry
	}
	return Entry{Depth: NoEntry}
}

func setHashEntry(board *Board, depth int, nodeCount uint64) {
	entry := Entry{Hash: board.InitZobristHash, Depth: depth, NodeCount: nodeCount}
	TranspositionTable[board.InitZobristHash%TranspositionTableSize] = entry
}

And finally, here is how I use them in my Perft function:

Code: Select all

func DividePerft(board *Board, depth, divideAt int) uint64 {
	if depth == 0 {
		return 1
	}

	entry := getHashEntry(board, depth)
	if entry.Depth != NoEntry {
		return entry.NodeCount
	}

	pseduoMoves := computePseduolegalMoves(board)
	var nodes uint64

	for _, move := range pseduoMoves {
		board.DoMove(&move, true)
		if KingIsSafe(board) {
			moveNodes := DividePerft(board, depth-1, divideAt)
			nodes += moveNodes
			if depth == divideAt {
				fmt.Printf("%v: %v\n", move, moveNodes)
			}
		}
		board.UndoMove(&move)
	}
	setHashEntry(board, depth, nodes)
	return nodes
}

Here's an example of the erroneous perft output now my engine gives:

Code: Select all

perft(5) from startpos:
b1-c3: 234656
b1-a3: 198572
g1-h3: 198502
g1-f3: 233491
a2-a3: 181046
a2-a4: 217832
b2-b3: 215255
b2-b4: 216142
c2-c3: 223341
c2-c4: 240080
d2-d3: 328511
d2-d4: 361790
e2-e3: 402988
e2-e4: 405383
f2-f3: 178889
f2-f4: 198469
g2-g3: 217210
g2-g4: 214049
h2-h3: 181044
h2-h4: 218830
Nodes: 4866080

I'd also be happy if anyone could just point me towards how they do things!

[tmokonen]

It appears that you are only hashing the position of the pieces. You also need to include castling rights, en passant file and side to move in your Zobrist key for hashing to work properly.

And just to be clear, you were getting correct perft results before adding hashing?

[algerbrex]

It appears that you are only hashing the position of the pieces. You also need to include castling rights, en passant file and side to move in your Zobrist key for hashing to work properly.

And just to be clear, you were getting correct perft results before adding hashing?

Yup, my perft results were perfect, for like 30-40 different positions. So I know Zobrist hashing was the culprit. I made sure I would ONLY fool with hashing once normal perft was correct.

And thanks, I didn't realize that. I'll work on implementing that right now haha.

[Rein Halbersma]

It appears that you are only hashing the position of the pieces. You also need to include castling rights, en passant file and side to move in your Zobrist key for hashing to work properly.

And just to be clear, you were getting correct perft results before adding hashing?

Yup, my perft results were perfect, for like 30-40 different positions. So I know Zobrist hashing was the culprit. I made sure I would ONLY fool with hashing once normal perft was correct.

And thanks, I didn't realize that. I'll work on implementing that right now haha.

Also, for Perft/divide hashing, you need depth equality (==) during lookups, not >= as in your code.

[algerbrex]

It appears that you are only hashing the position of the pieces. You also need to include castling rights, en passant file and side to move in your Zobrist key for hashing to work properly.

And just to be clear, you were getting correct perft results before adding hashing?

Yup, my perft results were perfect, for like 30-40 different positions. So I know Zobrist hashing was the culprit. I made sure I would ONLY fool with hashing once normal perft was correct.

And thanks, I didn't realize that. I'll work on implementing that right now haha.

Also, for Perft/divide hashing, you need depth equality (==) during lookups, not >= as in your code.

Ahh I didn't realize that, thanks. I remember reading somewhere I needed to use >=

[mvanthoor]

Ahh I didn't realize that, thanks. I remember reading somewhere I needed to use >=

Yes, when using the TT in play, you look for a position stored at a depth equal or greater than the depth you are on while probing. When using the TT for perft, you look for a position stored at exactly the depth you're probing on.

Rustic has a transposition table that can store anything, as long as the data object it's storing adheres to an interface.

It can store PerftData, which is only a Zobrist hash and a node count. It can also store SearchData, which is everything needed during the search. The data objects have a "get" function. The one for the PerftData is this:

Code: Select all

    pub fn get(&self, depth: i8) -> Option<u64> {
        if self.depth == depth {
            Some(self.leaf_nodes)
        } else {
            None
        }
    }

So if the TT has a position for the exact depth stored, it returns the leaf node count.

The get()-function for the SearchData object is much more complex, but it has this:

Code: Select all

pub fn get(&self, depth: i8, ply: i8, alpha: i16, beta: i16) -> (Option<i16>, ShortMove) {
	...
        if self.depth >= depth {
        	...
        }
        ...
}

As you can see, this function looks at positions at equal or higher depths, because if a position is searched to a greater depth, it has more accurate information. Thus, you're now at depth 6, but you previously searched the position to depth 9, and thus that information is more accurate and you can use this at depth 6.

With perft you can't do that because all the node counts must be exactly correct for each position and depth; there is nothing like a "more accurate node count"; it's correct, or it isn't.

[algerbrex]

With perft you can't do that because all the node counts must be exactly correct for each position and depth; there is nothing like a "more accurate node count"; it's correct, or it isn't.

Ah, I see. That makes perfect sense. Thank you.

[mvanthoor]

Ah, I see. That makes perfect sense. Thank you.

Good luck with fixing this.

You're doing the right thing with first getting perft correct, then getting hashing correct, then implementing the TT for perft to actually test if the hashing works with the TT (and the TT itself is working), and only _then_ implementing the TT for game playing. Go very slowly with the TT and make sure it's correct; because if it isn't, you either won't gain any strength at best, or at worst, your engine may make stupid or even illegal moves.

Have you tested the Zobrist hashing by calculating the hash from scratch, at the end of make_move, and comparing it with the incrementally updated hash? They should always be the same. If you don't store the hash/game-state on make_move to copy it back during unmake_move, but you incrementally update it "backwards", you must do this check in unmake_move as well. This test of "calculate from scratch == incrementally kept value" works for PST's, material, and everything else you incrementally update during movement of the pieces.

It is a very handy function to have when running perft. (In my engine it's only compiled into the engine in debug mode, if I need to test a new functionality.)

PS: If you're implementing a TT, search for "buckets". It makes the implementation much more efficiënt because you get 2-4 slots per index. You can also postpone this as a future update.

[algerbrex]

Ah, I see. That makes perfect sense. Thank you.

Good luck with fixing this.

You're doing the right thing with first getting perft correct, then getting hashing correct, then implementing the TT for perft to actually test if the hashing works with the TT (and the TT itself is working), and only _then_ implementing the TT for game playing. Go very slowly with the TT and make sure it's correct; because if it isn't, you either won't gain any strength at best, or at worst, your engine may make stupid or even illegal moves.

Have you tested the Zobrist hashing by calculating the hash from scratch, at the end of make_move, and comparing it with the incrementally updated hash? They should always be the same. If you don't store the hash/game-state on make_move to copy it back during unmake_move, but you incrementally update it "backwards", you must do this check in unmake_move as well. This test of "calculate from scratch == incrementally kept value" works for PST's, material, and everything else you incrementally update during movement of the pieces.

It is a very handy function to have when running perft. (In my engine it's only compiled into the engine in debug mode, if I need to test a new functionality.)

PS: If you're implementing a TT, search for "buckets". It makes the implementation much more efficiënt because you get 2-4 slots per index. You can also postpone this as a future update.

Thanks, currently debugging now

And no, I wasn't calculating the hash from scratch at the end of make move, but I did save the initialize Zobrist hashing before DoMove and UndoMove, and then compared the board Zobrist hash with the saved one at the end of UndoMove, and this has worked pretty well so far (it actually caught the bug I'm currently trying to fix haha). But calculating the hash manually at the end of DoMove seems like a good idea as well.

And thanks for the tip at the end!

[pedrojdm2021]

In transpositions you need to consider:

- Side to move
- Piece placement
- En passant (if any)
- Castling rights (if any)

Each time you make a move in your board you need to update your transposition hash using the same xorbist techique that you use for generating it from scratch

for example when you move a piece:

Code: Select all

board_hash ^= zorbistKeys.Pieces[PieceColour][SquareFrom][SquareTo];

To test it go grab some fen, you can use the "tricky" position, from the "perft" results in chess programming wiki.
grab the initial board hash and print it into the console.

make your move, print the updated hash, it should change.

then grab a fen that corresponds with the move that you have made, and build the tranposition hash from scratch.

compare the hash made from scratch with the hash that you updated in your make_move function. both must be equal. if they are different you are doing something wrong. Once you got it Ok. repeat the process for each type of move: moves,captures, castling, en-passant, do that for both players.

when you get it correct for all tests, your board hashing must be ok. if you get it correct in the hashing BUT you still having issues, probably is something wrong during the implementation itself.

you can check out this article on transpositions to get a more clear idea inside the implementation during the search:
https://web.archive.org/web/20070206185 ... ashing.htm