Author: Vincent Diepeveen
Date: 18:14:08 06/06/05
Go up one level in this thread
On June 05, 2005 at 22:19:43, Andrew Shapira wrote: You are correct that this can result in a problem. However that practically happens very little times so i ignore it. Please note that in a way simpler way you could in theory get the next thing. Suppose we have a position P with black to move. Chessprogram having white gets to position P' by means of white playing p1 which gives P ( p1 ) --> P' Because for some reason X unknown to us and uninteresting to us, it took half an hour to play p1. Some moves later we have a move m where the search is far smaller than the search from position P'. So somewhere in the tree we can get a true score which directly gets returned by hashtable. As a result of this we have 3 times repetition then. A simple fix for that seemingly is by checking in the root whether move m' leads to repetition. That removes a lot of the above doom scenario happening. Yet that fix will work poorly as soon as we go start adding 16 processors or so. Especially if there are processors which cannot read in ones other hashtable. The odds of the above scenario happening increases then. Because in order to get a 3 fold repetition, we don't need a 100% repetition yet. All we need is a position in which it is difficult to avoid getting back with that piece in order to get 3 fold repetition. we see it a lot in far endgames. the program just hops from square to square with its king and cannot go back with the king to that optimal square, because it will result in 3 times repetition. So the actual repetition doesn't come at the board, but by means of some huge search depths done elsewhere, or by an innocent 'square hopping' the pieces/king already cannot be put at the ideal square to play on for a win. The result is the pieces/king get placed at inferior squares with a sure draw. So the draw happens as a result from the hashtable. There simply is no alternative other than accepting the draw in such a case. Getting rid of the hashtable is one of the most stupid things to do. It gives *such* a huge speedup in terms of effective branching factor. Hyatt argued some years ago that hashtable speeds up by means of shortening lines. IMHO that's not entirely accurate. More accurate IMHO is that hashtable reduces the effective branching factor by removing lines that we already saw elsewhere. So the speedup in the scenario's you drew below is exponential, meaning that there is no alternative to the hashtable. Now you'll realize even more why i'm using win/draw/loss. An accurate DTM in 100% of the cases is just impossible, so is preventing draws. In both cases i'll just go for the easiest path and take the big profit i get in search depth. If i draw a game sooner than i could have, that's just bad luck. A draw against Goldbar is good anyway :) >(This is about hash tables and the 50 move rule and draw by repetition, and to >some extend endgame databases; it's not about the mechanics of detecting whether >a given position has occurred before on the board.) > >Imagine that a search encounters some position P for the first time, >say at time T0, determines some evaluation E0(P) using a depth 9 search, >and stores E0(P) in the hash table. For simplicity let's say that E0(P) >is computed without using hash tables in any way. Some time later, say >at time T1, P is encountered again, and we want to know its evaluation >E1(P) with regard to a depth 9 search. We look up P in the hash table >and find E0(P). Suppose that E0(P) looks fine for us to use, e.g., we >are about to take E1(P) to be the same as E0(P), except that there is >one difficulty: the halfmove clock at time T1 differs from the halfmove >clock at T0, e.g., at T0 the halfmove clock was 12 and at T1 it is 95. >This means that many of the nodes that went into the determination of >E0(P) have evaluations that are not correct at time T1. For example, >suppose that some position Q occurs at depth 4 in P's search tree, and >Q has a mate in 3; E0(P) will incorporate this information, but E1(P) >should not, because at time T1 if we follow the path to Q and then to >the mate in 3 from Q, the result will be a draw by the 50 move rule, >not mate. Because of this we do not want to use set E1=E0. > >A similar issue comes up with draw by repetition. For example, in the >above situation, imagine that Q has appeared on the board 0 times before >T0, but Q has appeared twice before T1. > >The same thing happens with endgame database lookups. It's somewhat >easier to deal with there, if one has distance-to-conversion >or distance-to-zero information in the database. (See >http://www.aarontay.per.sg/Winboard/fiftymove.htm and >http://www.aarontay.per.sg/Winboard/weaktablebase.html .) > >The essential reason this happens with hash tables and endgame databases is that >results are computed while ignoring part of the game state. > >What is known and done about this in regard to hash tables? > >I wonder - should distance-to-zero information about the principal >variation be stored in hash table entries? This might at least make it >possible to detect when a hash table entry could be incorrect because of >the 50 move rule. What to do when this situation is detected is another >question completely. Also, handling lower and upper bounding hash table >entries might be tricky. It doesn't seem to help with draw by repetition.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.