Transposition tables for newbs

[evandam]

So I have been implementing a TT lookup in my chess program.

The one thing I have is a Zorbrist hash that is updated incrementally for the board and I'm 100% that it is correctly producing the key.

My question I guess is about the different types of nodes and how to use them.

Here is what I'm doing currently.

If a node is the best for a position "PV" I store it, depth and score. I also store "Cut" nodes, depth and score when my score is >= beta.

Now when I start the search of a position I check for a hash entry. If I have a "PV" one and depth >= current search depth I just return that score because there is no need to search, I have already determined the best move to this depth. If I have a "Cut" node and depth >= current search depth and score >= beta I just immediately return beta.

I'm testing this now against my previous version, but the improvement is not what I expected (better just not by as much). Also I'm not storing any "ALL" nodes, because frankly I do not understand what they might be used for.

I hope this is all clear.

[bob]

So I have been implementing a TT lookup in my chess program.

The one thing I have is a Zorbrist hash that is updated incrementally for the board and I'm 100% that it is correctly producing the key.

My question I guess is about the different types of nodes and how to use them.

Here is what I'm doing currently.

If a node is the best for a position "PV" I store it, depth and score. I also store "Cut" nodes, depth and score when my score is >= beta.

Now when I start the search of a position I check for a hash entry. If I have a "PV" one and depth >= current search depth I just return that score because there is no need to search, I have already determined the best move to this depth. If I have a "Cut" node and depth >= current search depth and score >= beta I just immediately return beta.

I'm testing this now against my previous version, but the improvement is not what I expected (better just not by as much). Also I'm not storing any "ALL" nodes, because frankly I do not understand what they might be used for.

I hope this is all clear.

Think about the three possible outcomes of a search at position P.

1. You get a score > alpha and < beta. We call this an EXACT score and store it in the TT as a type EXACT. All TT entries store the draft (the remaining depth from the current position.) Here we store the actual score, the depth, and the best move, along with type=EXACT. If you search somewhere else and you find a match with this position, if TT draft is >= remaining depth, you just return the score instantly, no need to do any additional searching. Sounds like you have this one right.

2. You get a score >= beta. We call this a LOWER entry because the score you have is a lower bound since the actual score could be even higher but you did not search all moves to see. You store the score (fail-soft) or beta (fail-hard) along with the draft, best move, and type=LOWER. If, at some point later in the search, you reach this exact position again, you check to make sure (as always) that draft >= remaining depth. If so, and the score you stored is >= current beta bound, you stop the search and return beta (fail hard) or table score (fail-soft). Sounds like you are doing this right.

3. you search all moves, and when you finish, the best score is still == alpha. you store the type as "UPPER" since you know that the score is <= alpha but you are not sure how much lower, and as always you store the draft. There is no best move to store so set that to zero. If you reach this position again, you first verity that draft >= remaining depth, if so, compare table score to alpha. If it is <= alpha, you can return alpha (fail-hard) or table score (fail-soft) and you don't need to search all the moves again...

The short story is that when you take an action (which could be to back up a score, or fail high, or fail low, if you reach that position again, with the same or less remaining depth, you can again back up the score, or fail high or fail low, without having to do the search again. The 3rd case above is just as important as the 1st and 2nd, to reduce tree size.

[sje]

First, most authors will use the term "draft" here instead of "depth" to avoid confusion. Draft, of course, is the difference between the ply at which an entry is stored and the number of full width plies from where the terminal value was determined.

An intermediate programming step is to not reference the stored score at all, but to simply use the stored move as the first move in the move ordering. When this is working reliably, then further work with scores can be done.

[evandam]

Thanks Robert,

I think I was very close, but you did clear some things up.

Something is still not right because my version without the TT is searching less nodes. I suspect 2 things. I think my null move search may be hashing moves, which I assume is bad since null moves are illegal. Also and maybe a bigger deal is my PVHash. I have a Hash of my best moves from previous deepening iterations and use that in move ordering. I don't think that is happening as well when I get Hash hits. I'm going to look into it this evening and see if I can figure out what is going on. I may try and use the TT for move ordering, but I will have to think about how that is accomplished.

[bob]

Thanks Robert,

I think I was very close, but you did clear some things up.

Something is still not right because my version without the TT is searching less nodes. I suspect 2 things. I think my null move search may be hashing moves, which I assume is bad since null moves are illegal. Also and maybe a bigger deal is my PVHash. I have a Hash of my best moves from previous deepening iterations and use that in move ordering. I don't think that is happening as well when I get Hash hits. I'm going to look into it this evening and see if I can figure out what is going on. I may try and use the TT for move ordering, but I will have to think about how that is accomplished.

I have a variable hash_move[ply]. When I call HashProbe() I first zero hash_move[ply]. If HashProbe() gets a hit, which only means a signature match, I take the best move from the hash entry and store it in hash_move[ply]. If there was no best move (an UPPER entry) I had set the best move field to zero when I stored it, so this works for all cases.

If I can't terminate the search, I take hash_move[ply], verify that it is legal, and then I search that move before I generate any moves at all...

[evandam]

Ok over the weekend I think I got this working much better. At least now the TT version is searching less nodes than the old version. Still not as much as I would have thought, but I think there may still be a few issues.

#1. I cannot figure out why with the lower nodes, the best move is stored. I'm doing it, but what is the case where that would be used. I'm sure I'm missing something.

#2 Not sure I understand the fail-hard (returning alpha-beta with the lower and upper nodes) and fail-soft (returning the table score).

Also I'm not using the table in my QS at all. I'm sure this will make a difference. Since the QS is not to a fixed depth I figure I will only use hash entries from the table that where entered from the QS. I could just add a flag to my hash entry. Does this sound reasonable?

[Evert]

#1. I cannot figure out why with the lower nodes, the best move is stored. I'm doing it, but what is the case where that would be used. I'm sure I'm missing something.

It's used for move ordering.
You can use the TT for two things: to not re-search a position you've searched before, and to remember what move was best in a previous search.

Also I'm not using the table in my QS at all. I'm sure this will make a difference. Since the QS is not to a fixed depth I figure I will only use hash entries from the table that where entered from the QS. I could just add a flag to my hash entry. Does this sound reasonable?

My gut feeling says you should avoid storing QS positions as exact entries in the main TT, but I may be wrong about that.
I've used a dedicated smaller TT for QS in the past, but I think I've disabled it since. It certainly didn't seem to do as much as the TT for the main search did.
The best thing to do would be to try it out and decide whether it works for you or not.

[bob]

Ok over the weekend I think I got this working much better. At least now the TT version is searching less nodes than the old version. Still not as much as I would have thought, but I think there may still be a few issues.

#1. I cannot figure out why with the lower nodes, the best move is stored. I'm doing it, but what is the case where that would be used. I'm sure I'm missing something.

#2 Not sure I understand the fail-hard (returning alpha-beta with the lower and upper nodes) and fail-soft (returning the table score).

Also I'm not using the table in my QS at all. I'm sure this will make a difference. Since the QS is not to a fixed depth I figure I will only use hash entries from the table that where entered from the QS. I could just add a flag to my hash entry. Does this sound reasonable?

Remember, "lower" entry is a fail-high entry. The score is the lower bound on the score while the real score could be higher, still...

[mar]

First, most authors will use the term "draft" here instead of "depth" to avoid confusion. Draft, of course, is the difference between the ply at which an entry is stored and the number of full width plies from where the terminal value was determined.

An intermediate programming step is to not reference the stored score at all, but to simply use the stored move as the first move in the move ordering. When this is working reliably, then further work with scores can be done.

Now I'm a bit confused with the term draft. I always store remaining depth (truncated down as I use fractional depths). I think it's ok. Am I missing something? It has nothing to do with extensions/reductions I suppose?

[bob]

#1. I cannot figure out why with the lower nodes, the best move is stored. I'm doing it, but what is the case where that would be used. I'm sure I'm missing something.

It's used for move ordering.
You can use the TT for two things: to not re-search a position you've searched before, and to remember what move was best in a previous search.

Also I'm not using the table in my QS at all. I'm sure this will make a difference. Since the QS is not to a fixed depth I figure I will only use hash entries from the table that where entered from the QS. I could just add a flag to my hash entry. Does this sound reasonable?

My gut feeling says you should avoid storing QS positions as exact entries in the main TT, but I may be wrong about that.
I've used a dedicated smaller TT for QS in the past, but I think I've disabled it since. It certainly didn't seem to do as much as the TT for the main search did.
The best thing to do would be to try it out and decide whether it works for you or not.

Storing them as exact is OK, because you will also store a draft of zero, so that they will never terminate the regular search, but can be used if you probe in the q-search.