pos[0] white to move
legal reversible white move[0], from[0]->to[0],
pos[1] black to move
legal reversible black move[1], from[1]->to[1],
pos[2] white to move
legal white move[2], from[2]->to[2], where to[2] == from[0] && from[2] == to[0]
pos[3] black to move
is black move[3] legal to repeat the position?
pos[4] == pos[0] again
I think the only legality check needed for undoing black's move[1] are such cases Uri mentioned.
If black's move[1] was a distant move of a sliding piece, but the way back to from[1] is now interrupted, because the of to[2] is occupied again, thus to[2] (or from[0]) is member of the inbetween set of from[1]->to[1]. That is true for checks as well.
I'm not sure anymore, but I also expected some problems with kingmoves. That's why I check for a legal move.
I am always afraid of what such tricks do to the hash table.
Look at the following position:
[d]1Q1n2k1/p3p2p/7p/6bP/1N6/r4qPb/P1P2P1P/3R2K1 w
The winning line is 1. Rxd8+, Kg7; 2. Rg8+ (A), Kf7; 3. Rf8+ (B), Kg7; 4. Rxf3.
Suppose, however, that in your search black tries 1. ..., Kf8 first, speeding up the demise of his Queen by one move. But the white move ordering is not so clever either, so in reply it first tries 3. Rg8+, (after 2. Rf8+, Kg7), in stead of 3. Rxf3. This brings position B on the board before A, in this line. Pruning the move 4. Rf8+ because it returns to position B (with as a consequence black 'drawing' by 4. ..., Kg7, would leave no viable moves for white, as 4. Qf8+ leads to a mere Queen trade and a presumably lost position. (Well, it doesn't work out quite that way, but you get the idea...)
So pruning the move that (after the black reply) leads back to B makes A seem a very bad position for white. It will be stored as such in the hash table. Eventually B will of course look good because white finds 3. Rxf3, leading to refutation of 1. ..., Kf7. So black will try his alternative, 1. ..., Kg7. But now the winning move is to position A, which is hashed as at most a draw...
What you mention seems to me a path-dependency problem in general and I don't think this approach amplifies path-dependency, since it is related to the shortest of all pathes to repeat a position within four ply. With beta <= 0, it works similar to etc, looking for the cheapest, but not necessarily the best refutation - if the stronger side starts shuffling pieces while unmaking it's previous move and the weaker side is able to unmake it's last move as well.
This approach detects possible refutations by immediate repetition of moves one ply earlier as the zobrist-key compare. To prove legality is enough, and that seems cheap and simple.
Or as the side with alfa already >= 0, why would you try to unmake your last move two plies before, if your opponent is able to repeat the position? The best you can get is zero, but you will not improve alfa. So why not prune it at all, if alfa is already big enough?
hgm wrote:I am always afraid of what such tricks do to the hash table.
Look at the following position:
[d]1Q1n2k1/p3p2p/7p/6bP/1N6/r4qPb/P1P2P1P/3R2K1 w
The winning line is 1. Rxd8+, Kg7; 2. Rg8+ (A), Kf7; 3. Rf8+ (B), Kg7; 4. Rxf3.
Suppose, however, that in your search black tries 1. ..., Kf8 first, speeding up the demise of his Queen by one move. But the white move ordering is not so clever either, so in reply it first tries 3. Rg8+, (after 2. Rf8+, Kg7), in stead of 3. Rxf3. This brings position B on the board before A, in this line. Pruning the move 4. Rf8+ because it returns to position B (with as a consequence black 'drawing' by 4. ..., Kg7, would leave no viable moves for white, as 4. Qf8+ leads to a mere Queen trade and a presumably lost position. (Well, it doesn't work out quite that way, but you get the idea...)
So pruning the move that (after the black reply) leads back to B makes A seem a very bad position for white. It will be stored as such in the hash table. Eventually B will of course look good because white finds 3. Rxf3, leading to refutation of 1. ..., Kf7. So black will try his alternative, 1. ..., Kg7. But now the winning move is to position A, which is hashed as at most a draw...
I don't think so, because the draft would not be sufficient to get a hashtable cutoff ? (unless, you store it as a "depth independant always draw")
Gerd Isenberg wrote:What you mention seems to me a path-dependency problem in general and I don't think this approach amplifies path-dependency, since it is related to the shortest of all pathes to repeat a position within four ply. With beta <= 0, it works similar to etc, looking for the cheapest, but not necessarily the best refutation - if the stronger side starts shuffling pieces while unmaking it's previous move and the weaker side is able to unmake it's last move as well.
I just did a little test in the Baron. This trick saves me 0-2% of nodes in the 10 middlegame positions I usually try this stuff with. It took me to read the note above to realize that this small saving is probably due to the fact that I do repetition checking in ETC. So the only place where this saves nodes is in the nodes close to the leaves where ETC is too expensive to try.
Richard.
pijl wrote:I just did a little test in the Baron. This trick saves me 0-2% of nodes in the 10 middlegame positions I usually try this stuff with. It took me to read the note above to realize that this small saving is probably due to the fact that I do repetition checking in ETC. So the only place where this saves nodes is in the nodes close to the leaves where ETC is too expensive to try.
Richard.
Hi Richard,
well, the pre-repetition hits most often occur near the tips or in qsearch, so i think your saving sounds reasonable despite ETC.
It is not a big deal, but it might help in "no progress" and/or shuffle-positions, where pairwise "null-moves" to push "no progress" behind the horizon, gots faster refuted. But of course there are most likely other possibilities to shuffle around rather than immediate repetition of moves near the tips.
In my tests with some middlegame positions the pre-repetition hits occured in about 0.2-2% of all nodes (including qnodes), while repetition detections with zobrist keys were usually less than 1% now of the number of pre-repetition hits.
Gerd Isenberg wrote:
It is not a big deal, but it might help in "no progress" and/or shuffle-positions, where pairwise "null-moves" to push "no progress" behind the horizon, gots faster refuted. But of course there are most likely other possibilities to shuffle around rather than immediate repetition of moves near the tips.
One trick I use to prune some of the nonsense is related to this one: If the move sequence: move-a null move-b is seen where either:
move-a == - move-b
or
move-a+move-b=move-c where move-c is a legal move in the position before move a
and alpha>0, I prune as well. Also not a big node-saver, but it helps.
Richard.
Gerd Isenberg wrote:
It is not a big deal, but it might help in "no progress" and/or shuffle-positions, where pairwise "null-moves" to push "no progress" behind the horizon, gots faster refuted. But of course there are most likely other possibilities to shuffle around rather than immediate repetition of moves near the tips.
One trick I use to prune some of the nonsense is related to this one: If the move sequence: move-a null move-b is seen where either:
move-a == - move-b
or
move-a+move-b=move-c where move-c is a legal move in the position before move a
and alpha>0, I prune as well. Also not a big node-saver, but it helps.
Richard.
sounds like something used in chess 4.x and deep thought...
Gerd Isenberg wrote:What you mention seems to me a path-dependency problem in general and I don't think this approach amplifies path-dependency, since it is related to the shortest of all pathes to repeat a position within four ply.
I guess you are right if you would otherwise have scored the repetition as a draw when it actually occurred. Then the pruning you propose is theoretically sound, and very much related to futility pruning (where the repetition takes the place of stand pat).
But the scoring of the first repetition as draw leads of contamination of every position reached through 2 reversible moves. That the repetition itself is the shortest possible cycle, doesn't mean that you cannot encounter positions in this cycle in other branches of the tree at the same level for the first time.
The way of repetition detection I so far like best is to only score the third tree occurrence as a draw, but limit the score of any move that returns to the current position in its 'PV' to the draw score. That way you correct the score in hind-sight, in the occurrence closest to the root, sparing the nodes in between first and second occurrence from contamination. But tht would preclude this kind of pruning.
hgm wrote:
I guess you are right if you would otherwise have scored the repetition as a draw when it actually occurred. Then the pruning you propose is theoretically sound, and very much related to futility pruning (where the repetition takes the place of stand pat).
But the scoring of the first repetition as draw leads of contamination of every position reached through 2 reversible moves. That the repetition itself is the shortest possible cycle, doesn't mean that you cannot encounter positions in this cycle in other branches of the tree at the same level for the first time.
The way of repetition detection I so far like best is to only score the third tree occurrence as a draw, but limit the score of any move that returns to the current position in its 'PV' to the draw score. That way you correct the score in hind-sight, in the occurrence closest to the root, sparing the nodes in between first and second occurrence from contamination. But tht would preclude this kind of pruning.
Another alternative is to consider where the first occurrence appeared, inside the search tree or in the game-record. If it appeared inside the current search tree, the second occurrence or first repetition is already a draw score. Otherwise if the first occurrence appeared in the game-record a second repetition is needed for a draw.
What i found amazing is that in most positions the zobrist-key repetition hits were only a small fraction (most of the time far below 1%) of the "bounded" pre-repetition hits within four plies. Of course they are more critical, since they may influence the value of the root.
