Transposition Tables

[bob]

1. using exact mate scores is not a "silly" thing.

2. I don't see how your kludge works when you store at ply=10, and probe at ply=16 and get a hit on the ply=10 result. The way most of us do this produces perfect mate scores no matter where we store and then probe...

Well, if at ply=10 you store a mate-in-2 score, and at ply=16 you reach that same position and probe in, you would find a mate-in-2 score. As the position is a mate in 2.

Of course by the time that score would have propagated to the ply=10 level, it would now be a mate-in-5 score (as the side to be checkmated adds one to the score on each of its intervening plies). The ply=10 mate-in-2 would of course be a mate-in-7 score by the time it reached the root, while the ply=16 hit on it would arrive there as a mate-in-10 score. As from the root it would be a mate in 10.


So _all_ scores get +1 added as you step down the tree? Doesn't that wreck hash probes since the bounds get screwed up?


See it now?

[nczempin]

Also for castling, I use values 0-15 to describe the castling rights for a position, so again, I guess I can do castRandom*castRights, or use an array of 16.... castRandomArray[castRights].

Thanks

Why 16, when there are only 8 states:
whiteShort yes/no
whiteLong yes/no
blackShort yes/no
blackLong yes/no

What am I missing?

that 2 pow 4 equals 16 ?



Remember, you can have short AND long castle rights.

Tony

well, duh

I just have bits, and of course 4 bits = 16 states

[nczempin]

Also for castling, I use values 0-15 to describe the castling rights for a position, so again, I guess I can do castRandom*castRights, or use an array of 16.... castRandomArray[castRights].

Thanks

Why 16, when there are only 8 states:
whiteShort yes/no
whiteLong yes/no
blackShort yes/no
blackLong yes/no

What am I missing?

There are 16 states. nobody can castle = 0000, white can castle short, black can't castle at all = 0001, white can castle long, not short, black can't castle = 0010, white can castle long or short, black can't castle = 0011. Repeat each of those four for each of the other three black possibilities and you get 16.

Please, I feel embarrassed enough already, no need to spell it all out for me.

2 x 4 = 8
2 ^ 4 = 16

I will resign from my job.

Seriously now, it never occurred to me to enum all the states; I just have that 4 bit value; it must have been late.

Yes, I do know that it makes 16, where can I go hide now?

Someone please delete my post and all the answers. Then remove it from the Google cache as well as archive.org. Then brainwash all those who have read it. I will change my name, too.

Jeez.

[nczempin]

Basically... I have a 4 bit number castRights=ABCD..

if a piece is moved from/to a1, then castRights &= 1101 (13)
if a piece is moved from/to h1, then castRights &= 1110 (14)
if a piece is moved from/to e1, then castRights &= 1100 (12)

So by looking at bits C and D, we can determine if castling is allowed long or short for white.

And similarly for black...
if a piece is moved from/to a8, then castRights &= 0111 (7)
if a piece is moved from/to h8, then castRights &= 1011 (11)
if a piece is moved from/to e8, then castRights &= 0011 (3)

So by looking at bits A and B, we can determine if castling is allowed long or short for black.

And if a piece is moved to/from any other square castRights &= 1111 (15)

So ultimatley I have an array
7 15 15 15 3 15 15 11
15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15
13 15 15 15 12 15 15 14

Hope that helps

Yes, you are right about the 4-bit value. This is actually what I do myself. I think that array is a bit of an overkill, though. I am not sure the extra memory will translate into saved time, compared to just updating the respective flag when the rooks or king move for the first time (and somehow remember it; I don't do unmake yet, so I haven't thought about that part yet).

[hgm]

So _all_ scores get +1 added as you step down the tree? Doesn't that wreck hash probes since the bounds get screwed up?

Only scores below CurEval get +1 added. So in a mate branch only the side to be mated adds points, the side that mates adds nothing. So the score gets better for the side that faces a loss (in this case a checkmate) for every move he can delay it.

The hash probes merely pass on what a search would produce. I don't see how that could ever mess things up.

[bob]

So _all_ scores get +1 added as you step down the tree? Doesn't that wreck hash probes since the bounds get screwed up?

Only scores below CurEval get +1 added. So in a mate branch only the side to be mated adds points, the side that mates adds nothing. So the score gets better for the side that faces a loss (in this case a checkmate) for every move he can delay it.

The hash probes merely pass on what a search would produce. I don't see how that could ever mess things up.

There are bounds (mate) stored in the table. >= Mate in 10, or <= mated in 10. We compare those to the current bounds all the time to make sure we always go toward the shortest mate, or go toward the longest getting mated. I don't see how adjusting 1/2 of those but not the other 1/2 doesn't lead to strange artifacts in actual play.

The simplest solution is to just correct all mate scores and bounds to be mate in N from the current ply rather than all the tests to determine whether the score gets incremented or not.

[hgm]

I don't understand what problem you see.

One has to adjust the scores along the tree, as a mate-in-n at ply=10 is a mate-in-(n+1) at ply=8. And as mate-in-n is considered better than mate-in-(n+1), a mate-in-n score will have to be higher. So I cannot pass the score from ply=10 unmodified to ply=8.

I don't see what this has to do with hashing. Hashing is largely transparent. You store what the search would return. So when you probe, you wouldn't see the difference if you obtained the score from a hash hit or by doing the search.

[bob]

I don't understand what problem you see.

One has to adjust the scores along the tree, as a mate-in-n at ply=10 is a mate-in-(n+1) at ply=8. And as mate-in-n is considered better than mate-in-(n+1), a mate-in-n score will have to be higher. So I cannot pass the score from ply=10 unmodified to ply=8.

I don't see what this has to do with hashing. Hashing is largely transparent. You store what the search would return. So when you probe, you wouldn't see the difference if you obtained the score from a hash hit or by doing the search.

Here is what I don't follow. You find a LOWER position in the hash with a mate in 12 bound. You find that at ply=2. How do you use it? Ditto for UPPER and mate in 12. BTW the hash entry was stored at say ply=12. And is getting used at ply=2... That is what I am not following, because the bound needs to change from what it was at ply=12 to what it should be at ply=2 to be used... That is, not only EXACT entries have to be adjusted, but UPPER/LOWER entries as well to properly produce cutoffs when they should and not when they shouldn't.

[Colin]

I've found a different pseudocode to deal with transposition tables.
The code is on page 15 of this pdf...
http://www.cs.ualberta.ca/~tony/OldPape ... review.pdf
The code looks a little dated with the BEGIN/END statements, but after comparing it to the code in the last pdf I mentioned...

1. The code is essentially the same, except in this pdf, where the depth=0, only EVAL is called, and no storing takes place.

2. It explicitly shows the hash move being played first

3. I think the code is the wrong way round in this pdf..

Code: Select all

IF&#40;score<=alpha&#41; THEN flag&#58;=UBOUND;
IF&#40;score>=beta&#41; THEN flag&#58;=LBOUND;

I believe UBOUND and LBOUND need to be swapped ?

Can I get a chess programmers seal of approval on this psuedocode before I use it?
Thanks for any help

[bob]

I've found a different pseudocode to deal with transposition tables.
The code is on page 15 of this pdf...
http://www.cs.ualberta.ca/~tony/OldPape ... review.pdf
The code looks a little dated with the BEGIN/END statements, but after comparing it to the code in the last pdf I mentioned...

1. The code is essentially the same, except in this pdf, where the depth=0, only EVAL is called, and no storing takes place.

2. It explicitly shows the hash move being played first

3. I think the code is the wrong way round in this pdf..

Code: Select all

IF&#40;score<=alpha&#41; THEN flag&#58;=UBOUND;
IF&#40;score>=beta&#41; THEN flag&#58;=LBOUND;

I believe UBOUND and LBOUND need to be swapped ?

Can I get a chess programmers seal of approval on this psuedocode before I use it?
Thanks for any help

There was never complete agreement on the naming. We had lots of discussions about 10-15 years ago and we all pretty well standardized on the convention that "LOWER" means you are storing the current upper bound, but that represents the _lowest_ the value can possibly be, it is probably higher. Ditto for UPPER means you are actually storing a current lower bound, but that represents the _highest_ the value can possibly, and it is probably lower than that.

Back in the 70's-80's-early-90's, we called the things by what we stored, which would reverse the names, but other than that everything works exactly as it does today.