Handling of repetition (draw) in transposition table
Bjarke Dahl Ebert
Hello,
It is a well-known problem that a position occuring two places in the
game tree doesn't have the same position history at the two places,
and that therefore move repetition cannot (in any obvious way) be
taken into consideration in the transposition table.
But I was wondering if the following idea has been tried by anyone:
In evaluating a position, always take into consideration the moves
that led to that position (i.e. not just the "real" moves, but also
the "thought" moves in the tree search). If this evaluates to a draw
(by repetition), store it as a draw. When the same position is
obtained by another sequence of moves, how bad will it to assume that
the position is drawn?
Maybe it can be proven that this search algorithm will still produce
the minimax value at the root?
If so, it will be faster since "repetition subtrees" is pruned.
If not, is there a simple counterproof?
Regards,
Bjarke Ebert
--
---------------------------------------+------------------------------
Bjarke Dahl Ebert | If it works, it's obsolete
<URL: http://www.daimi.aau.dk/~bde/> |
---------------------------------------+------------------------------
Robert Hyatt
Bjarke Dahl Ebert (b...@daimi.aau.dk) wrote:
: Hello,
: It is a well-known problem that a position occuring two places in the
: game tree doesn't have the same position history at the two places,
: and that therefore move repetition cannot (in any obvious way) be
: taken into consideration in the transposition table.
: But I was wondering if the following idea has been tried by anyone:
: In evaluating a position, always take into consideration the moves
: that led to that position (i.e. not just the "real" moves, but also
: the "thought" moves in the tree search). If this evaluates to a draw
: (by repetition), store it as a draw. When the same position is
: obtained by another sequence of moves, how bad will it to assume that
: the position is drawn?
: Maybe it can be proven that this search algorithm will still produce
: the minimax value at the root?
: If so, it will be faster since "repetition subtrees" is pruned.
: If not, is there a simple counterproof?
: Regards,
: Bjarke Ebert
I do this exactly as you state it, if I find a draw score, I store a
draw score. It is wrong on occasion.
I also do exactly the same thing with mates, which works perfectly. If
I find a mate (score=MATE-ply) then I simply store score+ply (which adjusts
the mate score to be mate in N from this position) and it works with zero
problems...
draws are a problem, because of the path information that is not carried
in the transposition table...
chrisw
--
http://www.demon.co.uk/oxford-soft
Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in article
<5nhjbp$j...@juniper.cis.uab.edu>...
This is an inherently solvable problem, in fact I'm working on it right now
after looking at a strange autoplayer game against Fritz3.
My program gave Fritz's unmoved king a check. Fritz moved its king. My
program then retreated the checking piece to its original square.
Fritz's main line then gave Ke8 (eg move king back to the original square)
and a score of +0.00.
In other words it assessed this position as a 2-move repetition draw, but
forgot that the position was not the same because the king no longer had
castling rights.
My guess is that this is probably a general chess program bug.
Chris Whittington
>
>
Marcel van Kervinck
chrisw (chr...@cpsoft.demon.co.uk) wrote:
: This is an inherently solvable problem, in fact I'm working on it right now
: after looking at a strange autoplayer game against Fritz3.
It can simply be solved by not always storing the draw score
in the transposition table. Only two types of draw-by-repetition
scores can safely be stored in the table:
-1- those based on positions that actually occured two time
in the game.
-2- those based on a line where the repetition occurs after (or at)
the position you just searched and want to put into the table.
Others may cause problems if stored without full path information.
Detecting the latter case might cause some headaches and that's
probably the reason nobody really cares.
Marcel
-- _ _
_| |_|_|
|_ |_ Marcel van Kervinck
|_| mar...@stack.nl
Robert Hyatt
chrisw (chr...@cpsoft.demon.co.uk) wrote:
: --
: http://www.demon.co.uk/oxford-soft
: This is an inherently solvable problem, in fact I'm working on it right now
: after looking at a strange autoplayer game against Fritz3.
: My program gave Fritz's unmoved king a check. Fritz moved its king. My
: program then retreated the checking piece to its original square.
: Fritz's main line then gave Ke8 (eg move king back to the original square)
: and a score of +0.00.
: In other words it assessed this position as a 2-move repetition draw, but
: forgot that the position was not the same because the king no longer had
: castling rights.
: My guess is that this is probably a general chess program bug.
: Chris Whittington
That part is simply a bug in Fritz. In Crafty, I hash in a term to
take care of enpassant possibilities as well as castling status. But
there is another part that is unsolvable, because the hash table can
say "this is a win" when it is not, because it doesn't have the path
information from the position where the value was stored to the position
where the value was produced. And there can be repetition draws that
end in a 3rd repetition anywhere between the hash hit and the end of the
path the hash represents, and it won't be considered. Incorrect, of
course...
: >
: >
brucemo
Marcel van Kervinck wrote:
>
> chrisw (chr...@cpsoft.demon.co.uk) wrote:
>
> : This is an inherently solvable problem, in fact I'm working on it right now
> : after looking at a strange autoplayer game against Fritz3.
>
> in the transposition table. Only two types of draw-by-repetition
> scores can safely be stored in the table:
>
> -1- those based on positions that actually occured two time
> in the game.
>
> -2- those based on a line where the repetition occurs after (or at)
> the position you just searched and want to put into the table.
It's not just the draw score, it's any score.
The general problem here involves cases where you get a different score if you
probe the table than if you do a search.
One way this can come up is if you store a draw score, based upon a 2x rep, and
later come back to this node via a path with no reps in it, and use this score.
This is the way you discuss.
Another way is as follows. You have a position where you have a choice between
making a move that causes a 2x rep, which you score as 0, or making another move
which you regard as +0.10. You would choose to make the +0.10 move here, so
that's the score that goes into the hash table. Consider the case where there is
another way to get to this node, and in this case neither of these candidates
causes a repetition, and the first one should evaluate as +0.35 and the second one
should still evaluate as +0.10. The score for this node should be +0.35, but you
will get a +0.10 from the table. All this without ever storing the draw score in
the table.
I think this problem is solvable. All you have to do is never cut off based upon
a hash table score. This is obviously a very bad solution. Therefore, we choose
instead to live with the evils of hashing -- hashing produces a non-deterministic
search, because in order to be fully useful, it cannot include path information.
This is one of the reasons I say that hashing takes a day to implement, a week to
debug, a month to really debug, a year to really really debug, etc.
bruce
Robert Hyatt
Dan Thies (rt...@nospam.accessone.com) wrote:
: On 10 Jun 1997 23:54:36 +0200, mar...@stack.nl (Marcel van Kervinck)
: wrote:
: >It can simply be solved by not always storing the draw score
: >in the transposition table. Only two types of draw-by-repetition
: >scores can safely be stored in the table:
: >
: >-1- those based on positions that actually occured two time
: >in the game.
: >
: >-2- those based on a line where the repetition occurs after (or at)
: >the position you just searched and want to put into the table.
: >
: >Others may cause problems if stored without full path information.
: >
: >Detecting the latter case might cause some headaches and that's
: >probably the reason nobody really cares.
: I'd say the bigger problem is using an exact value, in a search which
: is based on approximations. You might not avoid the draw if your best
: line is scored as -.001 pawns, even though there's still a lot of
: play. On the other hand, you might avoid the draw if you have a line
: that scores +.001 pawns, even if the position is dead. Or worse,
: you'd see your program, a knight up, give the knight back to reach a
: +.001 position instead of playing to win - just because it thinks
: there *might* be a repetition possible in 10 plies and it can push
: that off by tossing a piece.
Don't forget the inverse case. IE imagine the following two paths:
..................X.........Y........Z
............Y.........X
in the first path, we search thru X to reac position Z, which we score.
When we get back to position X, we store the result.
later we search the second path and when we get to X, we hit the hash
table and retrieve the score for the search that ended up at position
Z. Notice it is *wrong*... because in the second search we have already
encountered a position that occurred *after* the table entry store position
X. So that if we were to do a real search from X in this second path, we'd
get a draw score as soon as we hit Y. But we never see Y, and use the score
as though we really could reach Z from here, which is wrong.
The bottom line: It has nothing to do with draw scores. It has everything
to do with the fact that the transposition table is storing scores that are
dependant on path information, but without any path information in the
table. We simply accept the errors...
: Deciding what do do about a draw in the tree is probably harder than
: figuring out how to find it. If you end up losing a lot of search
: depth to be able to detect the draw, which happens very rarely in
: chess, you're probably better off missing it. When I used to look for
: repetitions, I saw a lot more "phantom" draws than real draws. It's
: quite rare that a draw by repetition can be forced with "best play" by
: both sides.
: Dan
This isn't rare at all. If you take Crafty, and disable the repetition
detection and run it on ICC, you'll be *amazed* at how manygames end in
a draw...
Marcel van Kervinck
Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
: : >
: : >-2- those based on a line where the repetition occurs after (or at)
: : >the position you just searched and want to put into the table.
: : >
: : >Others may cause problems if stored without full path information.
: : >
: : >Detecting the latter case might cause some headaches and that's
: : >probably the reason nobody really cares.
: ..................X.........Y........Z
: ............Y.........X
: in the first path, we search thru X to reac position Z, which we score.
: When we get back to position X, we store the result.
: later we search the second path and when we get to X, we hit the hash
: table and retrieve the score for the search that ended up at position
: Z. Notice it is *wrong*... because in the second search we have already
: encountered a position that occurred *after* the table entry store position
: X. So that if we were to do a real search from X in this second path, we'd
: get a draw score as soon as we hit Y. But we never see Y, and use the score
: as though we really could reach Z from here, which is wrong.
*Storing* a draw for the X in the 2nd line in the table would be wrong,
because it will be based on a line where the repetition occurs to a
position -before- X. Expanding your second line you'ld get this:
............Y.........X [tt: .........Y........Z]
What I'm saying is that, if the line after X gets fully searched
and a draw score backs up to X, it's okay to accept that value
in the minimax, but not to store in in the table.
Only until the draw score backs up upto Y it's safe to store
this value in the table entry for Y (and all positions before the
1st Y).
Robert Hyatt
Marcel van Kervinck (mar...@stack.nl) wrote:
: Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
: : : >
: : : >-2- those based on a line where the repetition occurs after (or at)
: : : >the position you just searched and want to put into the table.
: : : >
: : : >Others may cause problems if stored without full path information.
: : : >
: : : >Detecting the latter case might cause some headaches and that's
: : : >probably the reason nobody really cares.
: : ..................X.........Y........Z
: : ............Y.........X
: : in the first path, we search thru X to reac position Z, which we score.
: : When we get back to position X, we store the result.
: : later we search the second path and when we get to X, we hit the hash
: : table and retrieve the score for the search that ended up at position
: : Z. Notice it is *wrong*... because in the second search we have already
: : encountered a position that occurred *after* the table entry store position
: : X. So that if we were to do a real search from X in this second path, we'd
: : get a draw score as soon as we hit Y. But we never see Y, and use the score
: : as though we really could reach Z from here, which is wrong.
: *Storing* a draw for the X in the 2nd line in the table would be wrong,
: because it will be based on a line where the repetition occurs to a
: position -before- X. Expanding your second line you'ld get this:
: ............Y.........X [tt: .........Y........Z]
yes... note I'm not talking about storing the second line, rather I
am searching the second line and the hash hit creates the line you have
above. And the eval is *wrong* because at point "Y" (the second "Y")
this turns into a draw, but we don't catch it, and still use the score
from position Z as though it was correct. Which it isn't...
: What I'm saying is that, if the line after X gets fully searched
: and a draw score backs up to X, it's okay to accept that value
: in the minimax, but not to store in in the table.
: Only until the draw score backs up upto Y it's safe to store
: this value in the table entry for Y (and all positions before the
: 1st Y).
I think I didn't explain well enough. In the above case, *no* draw scores
are ever getting into the hash table at all...
: Marcel
chrisw
--
http://www.demon.co.uk/oxford-soft
chrisw <chr...@cpsoft.demon.co.uk> wrote in article
<01bc75e4$b124bf20$c308...@cpsoft.demon.co.uk>...
> This is an inherently solvable problem, in fact I'm working on it right
now
> after looking at a strange autoplayer game against Fritz3.
>
> My program gave Fritz's unmoved king a check. Fritz moved its king. My
> program then retreated the checking piece to its original square.
>
> Fritz's main line then gave Ke8 (eg move king back to the original
square)
> and a score of +0.00.
>
> In other words it assessed this position as a 2-move repetition draw, but
> forgot that the position was not the same because the king no longer had
> castling rights.
>
> My guess is that this is probably a general chess program bug.
Er, most (all) of you missed my point. Probably my fault for not explaining
better.
This was not a hash table bug, but a ply 0 evaluation bug.
The draw was misread at EVALUATION time by failing to account for king
castle status.
Of course it gets worse if the situation happens in the tree and then the
hash gets hold of the wrong score as well.
Chris Whittington
>
> Chris Whittington
>
> >
> >
>
Robert Hyatt
chrisw (chr...@cpsoft.demon.co.uk) wrote:
: --
: http://www.demon.co.uk/oxford-soft
: Chris Whittington
I thought this looked like a repetition list problem... where the repetition
position entries did not include castling status, and would give false matches
like this. I believe I fell into this way early in Crafty's development, in
fact...
Ronald de Man
hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
>chrisw (chr...@cpsoft.demon.co.uk) wrote:
>: My program gave Fritz's unmoved king a check. Fritz moved its king. My
>: program then retreated the checking piece to its original square.
>: Fritz's main line then gave Ke8 (eg move king back to the original square)
>: and a score of +0.00.
>: In other words it assessed this position as a 2-move repetition draw, but
>: forgot that the position was not the same because the king no longer had
>: castling rights.
>: My guess is that this is probably a general chess program bug.
>: Chris Whittington
>That part is simply a bug in Fritz. In Crafty, I hash in a term to
>take care of enpassant possibilities as well as castling status. But
It is not necessarily a bug. Maybe Fritz thought it was ahead and so
expected his opponent to go for the draw by repetition by checking again.
In any case, I don't think this is a general chess program bug, as it is
so easy to take care of castling status in the hashkey.
>there is another part that is unsolvable, because the hash table can
>say "this is a win" when it is not, because it doesn't have the path
>information from the position where the value was stored to the position
>where the value was produced. And there can be repetition draws that
>end in a 3rd repetition anywhere between the hash hit and the end of the
>path the hash represents, and it won't be considered. Incorrect, of
>course...
Yes, the hash table can really cause strange things to happpen. I remember
an endgame position where my program gave PV's that included repetition
of moves, and gave evaluations of about +1.5. It took me a couple of days
before I realized that this was not a simple bug in my code, but just an
inevitable effect of hash table use. The search transposed after e.g. 12
ply into a position that had been searched at e.g. 6 ply and terminated
the search at that point. The PV moves printed out came from the
hashtable from the 12th ply on and so contained a repetition that had
never been actually searched.
Ronald de Man
Robert Hyatt
Ronald de Man (de...@wsdw10.win.tue.nl) wrote:
: hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
: >chrisw (chr...@cpsoft.demon.co.uk) wrote:
: >: My program gave Fritz's unmoved king a check. Fritz moved its king. My
: >: program then retreated the checking piece to its original square.
: >: Fritz's main line then gave Ke8 (eg move king back to the original square)
: >: and a score of +0.00.
: >: In other words it assessed this position as a 2-move repetition draw, but
: >: forgot that the position was not the same because the king no longer had
: >: castling rights.
: >: My guess is that this is probably a general chess program bug.
: >: Chris Whittington
: >That part is simply a bug in Fritz. In Crafty, I hash in a term to
: >take care of enpassant possibilities as well as castling status. But
: It is not necessarily a bug. Maybe Fritz thought it was ahead and so
: expected his opponent to go for the draw by repetition by checking again.
: In any case, I don't think this is a general chess program bug, as it is
: so easy to take care of castling status in the hashkey.
But the position Chris posted was *not* a repetition... that was the whole
point of his post and my comment. It "claimed" that the position before
the king moved from its original square and the position after it moved back
were identical. Obviously they aren't...
: >there is another part that is unsolvable, because the hash table can
: >say "this is a win" when it is not, because it doesn't have the path
: >information from the position where the value was stored to the position
: >where the value was produced. And there can be repetition draws that
: >end in a 3rd repetition anywhere between the hash hit and the end of the
: >path the hash represents, and it won't be considered. Incorrect, of
: >course...
: Yes, the hash table can really cause strange things to happpen. I remember
: an endgame position where my program gave PV's that included repetition
: of moves, and gave evaluations of about +1.5. It took me a couple of days
: before I realized that this was not a simple bug in my code, but just an
: inevitable effect of hash table use. The search transposed after e.g. 12
: ply into a position that had been searched at e.g. 6 ply and terminated
: the search at that point. The PV moves printed out came from the
: hashtable from the 12th ply on and so contained a repetition that had
: never been actually searched.
Yep. Just another path dependency that's broken, but acceptable, at least
for me. :)
: Ronald de Man
Ronald de Man
mar...@stack.nl (Marcel van Kervinck) writes:
>Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
>: ..................X.........Y........Z
>: ............Y.........X
>: in the first path, we search thru X to reac position Z, which we score.
>: When we get back to position X, we store the result.
>: later we search the second path and when we get to X, we hit the hash
>: table and retrieve the score for the search that ended up at position
>: Z. Notice it is *wrong*... because in the second search we have already
>: encountered a position that occurred *after* the table entry store position
>: X. So that if we were to do a real search from X in this second path, we'd
>: get a draw score as soon as we hit Y. But we never see Y, and use the score
>: as though we really could reach Z from here, which is wrong.
>*Storing* a draw for the X in the 2nd line in the table would be wrong,
>because it will be based on a line where the repetition occurs to a
>position -before- X. Expanding your second line you'ld get this:
The point Bob is making is that in fact storing the score for X in the
1st line is wrong. Wrong in the sense that in the second line this score
is used for X, where in fact the variation on which this score depends
is impossible, because it would mean a repetition of position Y. I observed
this once in my program: the score was +1.5 or so, and the PV contained
a repetition of moves.
So this has nothing to do with storing draws: no draw is recognized by
the search. And of course, it doesn't need to be a draw, there can be
another variation from position X in the second line.
Of course curing this problem by disabling hash cutoffs is a very bad idea.
>............Y.........X [tt: .........Y........Z]
>What I'm saying is that, if the line after X gets fully searched
>and a draw score backs up to X, it's okay to accept that value
>in the minimax, but not to store in in the table.
But it won't be searched in Bob's scenario.
>Only until the draw score backs up upto Y it's safe to store
>this value in the table entry for Y (and all positions before the
>1st Y).
And yes, you are probably right about when to score draws. But fortunately
I've never seen this give any problems in an actual game. And it's by
far not the only problem.
Ronald de Man