avoidrep-pruning

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Tony

Re: avoidrep-pruning

Post by Tony » Wed May 16, 2007 1:23 pm

Gerd Isenberg wrote:
Tony wrote: You have to check if the returning move is legal off course. ie also for checks etc.
Tony

Code: Select all

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.

Tony

User avatar
hgm
Posts: 23772
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: avoidrep-pruning

Post by hgm » Wed May 16, 2007 4:57 pm

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...

Gerd Isenberg
Posts: 2128
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: avoidrep-pruning

Post by Gerd Isenberg » Wed May 16, 2007 6:04 pm

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?

Tony

Re: avoidrep-pruning

Post by Tony » Wed May 16, 2007 6:05 pm

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")

This is the stuff headaches are made off.

Tony

pijl

Re: avoidrep-pruning

Post by pijl » Wed May 16, 2007 8:20 pm

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.

Gerd Isenberg
Posts: 2128
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: avoidrep-pruning

Post by Gerd Isenberg » Wed May 16, 2007 9:29 pm

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.

See you!

Cheers,
Gerd

pijl

Re: avoidrep-pruning

Post by pijl » Wed May 16, 2007 10:26 pm

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.

bob
Posts: 20635
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: avoidrep-pruning

Post by bob » Thu May 17, 2007 12:28 am

pijl wrote:
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...

User avatar
hgm
Posts: 23772
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: avoidrep-pruning

Post by hgm » Thu May 17, 2007 9:21 am

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.

Gerd Isenberg
Posts: 2128
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: avoidrep-pruning

Post by Gerd Isenberg » Thu May 17, 2007 10:40 am

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.

Post Reply