Rebel Transposition Table discussion
Robert Hyatt
-->
-->>Following the current discussions, REBEL uses a kind of "back solving":
-->>a) an 32 bit hashkey.
-->>b) the "actual move" is stored in the hashtable too.
-->>
-->>When a transposition is found Rebel checks it as follows:
-->>The destination square + piece type MUST be present in the tree otherwise
-->>it is a collision.
Here, maybe I got completely lost. When you say "destination square" exactly
what are you referring to? IE, where did this "move" come from? Is it the
move made to reach a transposed position? I was interpreting it to be the
"best move" from this position, but that seems wrong...
-->>
-->>Example:
-->>HASH: e2-e4 e7-e5 Ng1-f3 Nb8-c6 Bf1-c4
-->>TREE: e2-e4 e7-e5 Bf1-c4 Nb8-c6 Ng1-f3
Let me explain my interpretation of the above to be sure we are on the
same "wavelength"...
HASH represents a position after 5 moves have been made, this was stored
in the hash table...
TREE represents a position after 5 moves have been made, which results in
a hit with the HASH entry above?
-->>
-->>In case of TREE, a transposition is found for Ng1-f3 at ply 5 with
-->>an actual move of Bf1-c4.
Maybe I'm beginning to understand. In the hash entry, you store the move
made to produce this entry? In that case, it would be Bf1-c4 as you are
describing. And the "interchanged move" is the current move you just made
to reach the position where we got the hash hit? If I understand this (now)
you then loop thru 1/2 the move made list (for the correct side only) to
see if this table piece/to matches, and if not, you toss this position out
as invalid? If I'm correct, I think I finally understand what you are
doing.
-->>
-->>Now both "destination square C4" and "piece type WHITE BISHOP" must be
-->>present in the tree.
-->>
-->>Rebel loops back (2 ply) to search for this conditions.
-->>If WB + C4 is found in the tree the transposition is ok!
-->>If not it is a hashcollision.
-->>In the above case WB + C4 is found at the third ply, meaning the
-->>transposition is ok.
This is where my question (below) came from. I interpreted this to mean
that you look for the transposition two plies back, and if it's not there
you <abort>. Here's the counter-example that I thought about:
HASH: e4 e5 Nf3 Nf6 Bc4 Bc5 Nc3 Nc6 Ng5 Ng4 <hash store at this point>
TREE: e4 e5 Nf3 Nf6 Ng5 Ng4 Bc4 Bc5 Nc3 Nc6 <hash hit at this point>
Note that the hash move Ng4 does not occur two plies back, it occurs 4
plies back. If you only check 2 plies back, you will conclude that this
is a signature collision and throw it out? While the above is a bit deep
unless it's a long game, in an endgame, like fine#70, Crafty hits 20 plies
before I can blink, making it *very* likely... Note how easy it is to add
a couple of more "off the wall" moves to the front of the first PV, then
move 'em to the end of the 2nd, and push this to 6 plies back or 8 plies
back, etc.
-->
-->
-->Bob Hyatt wrote...
-->First question is what about a transposition that occurs
-->12 plies apart(for example) such as those that happen in endings?
-->It would appear (tome) that your test probably avoids a lot of 32bit
-->collisions that you wouldnot detect, but it is also avoiding lots of
-->useful hash hits. Another difficulty: what about "hits" that occur
-->between iterations, such as I ponder for 9 plies, opponent makes a move
-->that was in the old PV, but notthe second move. I'll get a ton of
-->transposition hits, but the transpositionswon't be (necessarily) in
-->the tree.
-->
-->
-->Hi Bob (and others ofcourse)...
-->
-->Like to comment the above.
-->The *MAIN* goal of my writing was to *CHECK* if my backsolving system is
-->correct or not, since I am not completely sure of it. I state that
-->the *actual move* MUST be present in the tree otherwise it is a
-->collision. Reading your comment above you say that my theory is not
-->correct since you state: ", but it is also avoiding lots of useful hash
-->hits."
-->
-->Again:
-->HASH: e2-e4 e7-e5 Ng1-f3 Nb8-c6 Bf1-c4 (Bf8-c5)
-->TREE: e2-e4 e7-e5 Bf1-c4 Nb8-c6 Ng1-f3
-->In case of TREE, a transposition is found for Ng1-f3 at ply 5 with an
-->actual move of Bf1-c4. Now both "destination square C4" and "piece type
-->WHITE BISHOP" must be present in the tree. I state if one of the checks
-->fails we have a bad transposition. Can anyone prove the opposite to me?
-->If possible with an example.
The very first (trivial) case is one you avoid (below) because you don't
carry the hash table from one search to the next (not one iteration to the
next, which I'm sure you do, but one "search" to the next, which means two
searches with different (possibly) root positions.) If you did as I have
always done and *never* clear the hash table of the signature/best move
information, this could easily happen across different searches of course.
It seems to me that there are many ways to transpose besides this, including
allowing captures, just so the path is long enough to accomodate whatever
scenario you want to allow.
However, since you are using 32 bits, this might be what is "saving your
bacon" because you are faster than Crafty, and my testing says that a
"fully-trusted" 32bit hash key will cause many signature collisions, although
this is a far-cry from saying they will cause bad search results. I don't yet
have a clue about what (say) 500 signature collisions would do to a single
multi-million node search as Crafty does in short standard-type games. My
early testing, which was far from exhaustive, reported a significant number
of "errors", but absolutely no changes in PV's or evaluations, when using
32bits. Exactly what this means is unknown, but maybe with all the other
errors built-in to things like evaluations, null-move, etc., this represents
a truly small number of additional errors.
Here's one thing we can do: Pick a few positions, and run them to a
reasonable depth, both middlegame, late-middlegame, and endgames, and let's
compare nodes searched ply by ply. If we are pretty close in the "ratio"
from one ply to the next, then what you are doing isn't hurting. If we are
far apart, it would be revealing. It will take some hairy comparisons,
however, as we probably extend differently, etc. One classic position is
fine #70, which is *all* transpositions, another pretty good one is Win
At Chess #2, which is an ending. If you want to try this, either publicly
or privately, let me know.
-->
-->For clearness sake...
-->If Bf1-c4 is stored in the hashtable it looks like this:
-->
-->struct HASH
-->long hashkey = 0x12345678 // the hashkey leading to Bf1-c4
-->short bestmove = f8c5 // found best move for Bf1-c4
-->char square = c4 // destination square actual move
-->char piece = WB // piece type actual move
-->.. the usual stuff ...
-->
-->So if the hashkeys match for Ng1-f3 and all others checks (bounds, ply
-->etc.) too, Rebel will search for destination square C4 and WB, which must
-->be present in the TREE. True or not true?
First, maybe I read too much into your "two plies back". My first thought
was that's not near enough, because the transposition can occur with moves
further back than that. If your "Rebel loops back 2 ply" was only an example,
most of my comment was off-base.
However, suppose your "hash" came from an old search, such as would happen
when pondering the wrong move, but the move your opponent makes is one of
the moves along the PV for this hash position? You might not pass your
test above if this occurs, because the "move" might not be anywhere in the
current path at all as I understand your reasoning.
Note, I'm not claiming what you do is wrong, just that "to me, it seems
overly restrictive." However, with hashing, anything can happen, so it
might well be that I'm in left field today myself...
-->
-->Remark:
-->Rebel always clears his hashtable, also in the Permanent brain because
-->the use of a preprocessor.
-->
-->- Ed Schroder -
I do this sometimes, but if the preprocessor doesn't change anything, then I
don't touch things. In fact, even if the preprocessor changes some of the
eval weights, I never clear the complete hash entry, I simply run through
the table marking every entry as "worthless" but leaving them there to provide
move ordering information that would be lost otherwise.
Bob (thick in the head today) Hyatt. :)
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Ed Schröder
For clearness sake I have posted this message too as a new subject.
You fully understand my system now.
I already assumed that my introduction of the "actual move" was not
clear enough.
HASH: e4 e5 Nf3 Nf6 Bc4 Bc5 Nc3 Nc6 Ng5 Ng4 <hash store at this point>
TREE: e4 e5 Nf3 Nf6 Ng5 Ng4 Bc4 Bc5 Nc3 Nc6 <hash hit at this point>
^^^
Rebel will find a transposition for Nc6 at ply 10.
The actual move "Ng4" found in the hashtable too will be checked.
Rebel loops back in steps of 2 ply (till ply 1 ofcourse!) and in
your above example Ng4 is found on ply 6 in the tree meaning the
transposition is ok!
To me, it's a cheap and reliable system because a 32 bit hashkey
with NO checks is *NOT* enough. At the time I have tested Rebel
*with* and *without* the backsolving system. Some results:
- 712 positions tested (in about 12 hours)
- 12 different moves
- loss in speed (just) 1.2%
Hashcollisions (transposition errors) detected by the algorithm:
MIDGAME : 0.7%
ENDGAME : 1.3%
I fully agree with you that there are other ways too to recognize
hashcollisions. One of them is ofcourse to make the hashkey bigger.
Still it remains important to have a *GOOD* check because the faster
the hardware the more hashcollisions resulting in unpredictable results.
>Here's one thing we can do: Pick a few positions, and run them to a
>reasonable depth, both middlegame, late-middlegame, and endgames, and
>let's compare nodes searched ply by ply. If we are pretty close in
>the "ratio" from one ply to the next, then what you are doing isn't
>hurting. If we are far apart, it would be revealing. It will take
>some hairy comparisons, however, as we probably extend differently,
>etc. One classic position is fine #70, which is *all* transpositions,
>another pretty good one is Win At Chess #2, which is an ending.
>If you want to try this, either publicly or privately, let me know.
Let's do it publicly.
I assume that "fine #70" is the Kb1! one.
I assume that "wac #2" is the Rxb2! one.
Here are the results of REBEL AEGON which operates with the new idea.
KA1-B1:
PLY NODES TRANSPOSITIONS COLLISIONS
17 48 Kb 22 Kb 0
20 133 Kb 65 Kb 0
23 282 Kb 134 Kb 0
26 337 Kb 154 Kb 0
30 509 Kb 207 Kb 4
RB2xB3:
PLY NODES TRANSPOSITIONS COLLISIONS
7 72 Kb 5 Kb 46
8 192 Kb 16 Kb 89
9 342 Kb 32 Kb 228
10 1651 Kb 143 Kb 1.1 Kb
11 3658 Kb 349 Kb 2.5 Kb
Looking forward for your results (and others).
Best regards,
- Ed Schroder -
Chris Whittington
> Let's do it publicly.
> I assume that "fine #70" is the Kb1! one.
> I assume that "wac #2" is the Rxb2! one.
> Here are the results of REBEL AEGON which operates with the new idea.
>
> KA1-B1:
> PLY NODES TRANSPOSITIONS COLLISIONS
> 17 48 Kb 22 Kb 0
> 20 133 Kb 65 Kb 0
> 23 282 Kb 134 Kb 0
> 26 337 Kb 154 Kb 0
> 30 509 Kb 207 Kb 4
>
> RB2xB3:
> PLY NODES TRANSPOSITIONS COLLISIONS
> 7 72 Kb 5 Kb 46
> 8 192 Kb 16 Kb 89
> 9 342 Kb 32 Kb 228
> 10 1651 Kb 143 Kb 1.1 Kb
> 11 3658 Kb 349 Kb 2.5 Kb
>
> Looking forward for your results (and others).
>
> Best regards,
>
> - Ed Schroder -
>
>
Can you post the positions (rather than their book refs), then, in
the spirit of openness(!), I'll give the CST results as well.
Best regards,
Chris Whittington
Robert Hyatt
Chris Whittington <chr...@cpsoft.demon.co.uk> wrote:
>
>Can you post the positions (rather than their book refs), then, in
>the spirit of openness(!), I'll give the CST results as well.
>
>Best regards,
>
>Chris Whittington
Here's "fine #70" in FEN: Note, if you need 8 squares per rank, you'll
have to edit a little. In my implementation of FEN, "//" is equivalent
to "/8/" and the initial "/" below is equivalent to "8/".
/k/3p/p2P1p/P2P1P///K/ w
Here's Win at Chess #2
/7p/5k/5p/p1p2P/Pr1pPK/1P1R3P// b
Hope that helps... (b=btm, w=wtm of course, no castling nor enpassant
possibilities in either position)
Steven J. Edwards
>In article <8300848...@cpsoft.demon.co.uk>,
>Chris Whittington <chr...@cpsoft.demon.co.uk> wrote:
>>Can you post the positions (rather than their book refs), then, in
>>the spirit of openness(!), I'll give the CST results as well.
>Here's "fine #70" in FEN: Note, if you need 8 squares per rank, you'll
>have to edit a little. In my implementation of FEN, "//" is equivalent
>to "/8/" and the initial "/" below is equivalent to "8/".
>/k/3p/p2P1p/P2P1P///K/ w
>Here's Win at Chess #2
>/7p/5k/5p/p1p2P/Pr1pPK/1P1R3P// b
>Hope that helps... (b=btm, w=wtm of course, no castling nor enpassant
>possibilities in either position)
Fine #70:
8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1
WAC #2:
8/7p/5k2/5p2/p1p2P2/Pr1pPK2/1P1R3P/8 b - - 0 1
Yes, they're a little longer. But the complete enumeration of empty
squares serves as a sort of redundancy check.
-- Steven (s...@mv.mv.com)
Ed Schroder
>"Ed Schröder" <10065...@compuserve.com> wrote:
>
>> Let's do it publicly.
>> I assume that "fine #70" is the Kb1! one.
>> I assume that "wac #2" is the Rxb2! one.
>> Here are the results of REBEL AEGON which operates with the new idea.
>>
>> KA1-B1:
>> PLY NODES TRANSPOSITIONS COLLISIONS
>> 17 48 Kb 22 Kb 0
>> 20 133 Kb 65 Kb 0
>> 23 282 Kb 134 Kb 0
>> 26 337 Kb 154 Kb 0
>> 30 509 Kb 207 Kb 4
>>
>> RB2xB3:
>> PLY NODES TRANSPOSITIONS COLLISIONS
>> 7 72 Kb 5 Kb 46
>> 8 192 Kb 16 Kb 89
>> 9 342 Kb 32 Kb 228
>> 10 1651 Kb 143 Kb 1.1 Kb
>> 11 3658 Kb 349 Kb 2.5 Kb
>>
>> Looking forward for your results (and others).
>>
>> Best regards,
>>
>> - Ed Schroder -
>>
>>
>
>the spirit of openness(!), I'll give the CST results as well.
>
>
>Chris Whittington
Hi Chris,
Here are the positions.
WKa1 a4,d4,d5,f4
BKa8 a5,d6,f5
Move 1.Kb1!
WKf3 WRd2 a3,b2,e3,f4,h2
BKf6 BRb3 a4,c4,d3,f5,h7
Move 1..Rxb2!
Personally I am not interested in the (right) moves, since every
chessprogram will find them.
I am interested in the number of hashcollisions that may occur
since this was my goal of the discussion.
However any comment is welcome ofcourse.
- Ed Schroder -