Is my code inefficent for storing a transposition table entry?

[algerbrex]

I'm currently in the process of adding a very simple transposition table into Blunder, no extra frills, one bucket per entry.

It seemed to be working well from some light testing, so I started some more extensive testing in self-play using a 2+0.8s time control format. However, I'm encountering a pretty odd and frustrating issue.

Basically, sometimes Blunder is taking (much) longer than the time allotted for a 1-ply search (in the time control format I'm using, usually ~50-80ms), which means it doesn't have a best move to return.

Of course, it struck me as very odd that Blunder couldn't even finish a 1-ply search in less than ~50ms, so I did some investigating, and I discovered that the culprit causing this issue was the function used to add an entry into the transposition table. What's happening is that every so often, the performance of this function will "spike" and take anywhere from ~100ms to almost a full second, massively inflating the search time.

Here is the code for the function:

Code: Select all

func (tt *TranspositionTable) AddEntry(hash uint64, depth, ply, score int, flag uint8, best engine.Move) {
	entry := &tt.table[hash%tt.size]
	if entry.Hash == hash && entry.Depth > uint8(depth) {
		return
	}

	if score >= CheckmateThreshold {
		score += ply
	} else if score <= -CheckmateThreshold {
		score -= ply
	}

	entry.Hash = hash
	entry.Depth = uint8(depth)
	entry.Score = int16(score)
	entry.Flag = flag
	entry.Best = best
}

For those who don't know, I'm writing my engine in Golang, and I suspect that something weird might be happening that's Golang specific, since I've been analyzing this relatively short function for any major hidden general ineffiencies, and I simply can't find any. I've also taken a peek at the code from other engines like the CPW-engine, and it doesn't look like I'm doing anything weird.

But just in case I've missed something important, I've decided to get a second pair of eyes and a second opinion.

My current idea to fix this issue is to simply force Blunder to take as much time as needed to at least finish a 1-ply search, and then work around that. But I'd really rather not have to do this, as this seems hacky and something I really shouldn't have to do. So for now I'll be working on some other features until I can figure this problem out.

[amanjpro]

I'm currently in the process of adding a very simple transposition table into Blunder, no extra frills, one bucket per entry.

It seemed to be working well from some light testing, so I started some more extensive testing in self-play using a 2+0.8s time control format. However, I'm encountering a pretty odd and frustrating issue.

Basically, sometimes Blunder is taking (much) longer than the time allotted for a 1-ply search (in the time control format I'm using, usually ~50-80ms), which means it doesn't have a best move to return.

Of course, it struck me as very odd that Blunder couldn't even finish a 1-ply search in less than ~50ms, so I did some investigating, and I discovered that the culprit causing this issue was the function used to add an entry into the transposition table. What's happening is that every so often, the performance of this function will "spike" and take anywhere from ~100ms to almost a full second, massively inflating the search time.

Here is the code for the function:

Code: Select all

func (tt *TranspositionTable) AddEntry(hash uint64, depth, ply, score int, flag uint8, best engine.Move) {
	entry := &tt.table[hash%tt.size]
	if entry.Hash == hash && entry.Depth > uint8(depth) {
		return
	}

	if score >= CheckmateThreshold {
		score += ply
	} else if score <= -CheckmateThreshold {
		score -= ply
	}

	entry.Hash = hash
	entry.Depth = uint8(depth)
	entry.Score = int16(score)
	entry.Flag = flag
	entry.Best = best
}

For those who don't know, I'm writing my engine in Golang, and I suspect that something weird might be happening that's Golang specific, since I've been analyzing this relatively short function for any major hidden general ineffiencies, and I simply can't find any. I've also taken a peek at the code from other engines like the CPW-engine, and it doesn't look like I'm doing anything weird.

But just in case I've missed something important, I've decided to get a second pair of eyes and a second opinion.

My current idea to fix this issue is to simply force Blunder to take as much time as needed to at least finish a 1-ply search, and then work around that. But I'd really rather not have to do this, as this seems hacky and something I really shouldn't have to do. So for now I'll be working on some other features until I can figure this problem out.

- Why do you use int for score and depth? score can be int16 and depth can be int8, it makes your engine considerably faster! basically instead of copying 128 bits per call, you will copy 24 bits
- You can look at my engine (Zahak), or CounterGo whenever you are unsure, BTW. They are both open source and on GitHub
- How is your read function? do you have a lock or anything?
- How big is your TT? from the first glance, I don't see anything too off from this function

[amanjpro]

BTW, tried to find your TT in your repo, couldn't find it, can you point me to it please?

[algerbrex]

Hi Amanj, thanks for the reply,

- Why do you use int for score and depth? score can be int16 and depth can be int8, it makes your engine considerably faster! basically instead of copying 128 bits per call, you will copy 24 bits

Laziness. When I originally wrote the search code I was focused on just getting it to work, and wasn't being very disciplined. I need to go back and clean up that code and now seems like a pretty good time.

- You can look at my engine (Zahak), or CounterGo whenever you are unsure, BTW. They are both open source and on GitHub

Thanks, I'll make a note of that. I've noticed Zurichess as well.

- How is your read function? do you have a lock or anything?

Nope, currently just using one thread:

Code: Select all

func (tt *TranspositionTable) GetEntry(hash uint64, depth, ply, alpha, beta int, best *engine.Move) int16 {
	entry := &tt.table[hash%tt.size]
	if entry.Hash == hash {
		*best = entry.Best
		if entry.Depth >= uint8(depth) {
			score := Invalid

			if entry.Flag == ExactFlag {
				score = entry.Score
			} else if entry.Flag == AlphaFlag && entry.Score <= int16(alpha) {
				score = entry.Score
			} else if entry.Flag == BetaFlag && entry.Score >= int16(beta) {
				score = entry.Score
			} else {
				return Invalid
			}

			if score >= CheckmateThreshold {
				score -= int16(ply)
			} else if score <= -CheckmateThreshold {
				score += int16(ply)
			}

			return score
		}
	}
	return Invalid
}

- How big is your TT? from the first glance, I don't see anything too off from this function

~512 Mb currently. I'm planning to play around with the default size though, and of course eventually allow the user/GUI to adjust the size.

BTW, tried to find your TT in your repo, couldn't find it, can you point me to it please?

Right, this is a newer development feature I'm working on, so I haven't actually made an official release yet or committed any new code to the codebase. Here's a GitHub file with my transposition table implementation:

[amanjpro]

Oh, didn't know about Zurichess! They even incorporate some assembly too! neat...

As for your snippet, it all seems rather standard... how do you call AddEntry?

[algerbrex]

Oh, didn't know about Zurichess! They even incorporate some assembly too! neat...

Yeah, I didn't either until a couple of weeks ago, but a very cool Golang chess engine.

As for your snippet, it all seems rather standard... how do you call AddEntry?

Like so (also included is my main negamax function for context):

Code: Select all

// The primary negamax function, which only returns a score and no best move.
func (search *Search) negamax(depth, ply, alpha, beta int) int {
	if search.Timer.TimeIsUp() {
		return 0
	}

	search.nodesSearched++
	inCheck := search.Board.KingIsAttacked(search.Board.ColorToMove)

	if inCheck {
		depth++
	}

	if search.isDraw() {
		return search.contempt()
	}

	if depth == 0 {
		return search.quiescence(alpha, beta)
	}

	ttBestMove := NullMove
	if score := search.TTable.GetEntry(search.Board.Hash, depth, ply, alpha, beta, &ttBestMove); score != Invalid {
		return int(score)
	}

	moves := engine.GenPseduoLegalMoves(&search.Board)
	scores := search.scoreMoves(&moves, depth, ttBestMove)

	noMoves := true
	ttFlag := AlphaFlag
	bestMove := NullMove

	for index := range moves {
		orderMoves(index, &moves, &scores)
		move := moves[index]

		search.Board.DoMove(move, true)
		if search.Board.KingIsAttacked(search.Board.ColorToMove ^ 1) {
			search.Board.UndoMove(move)
			continue
		}

		score := -search.negamax(depth-1, ply+1, -beta, -alpha)
		search.Board.UndoMove(move)
		noMoves = false

		if score >= beta {
			search.storeKiller(depth, move)
			 search.TTable.AddEntry(search.Board.Hash, depth, ply, beta, BetaFlag, move)
			return beta
		}

		if score > alpha {
			alpha = score
			ttFlag = ExactFlag
			bestMove = move
		}
	}

	if noMoves {
		if inCheck {
			alpha = NegInf + ply
		} else {
			alpha = search.contempt()
		}
	}
	search.TTable.AddEntry(search.Board.Hash, depth, ply, alpha, ttFlag, bestMove)
	return alpha
}

[amanjpro]

I see you use `search.Board.Hash`, are you sure you keep Hash updated properly? Check if you assign every board the same Hash, so all your positions are treated the same (== you effectively run MiniMax, not alpha-beta)

[algerbrex]

I see you use `search.Board.Hash`, are you sure you keep Hash updated properly? Check if you assign every board the same Hash, so all your positions are treated the same (== you effectively run MiniMax, not alpha-beta)

Thanks. I'm quite sure I'm incrementally updating the board Zobrist hash correctly, from some testing I've done. But I suppose I'll double-check, as hashing bugs can be quite sneaky.