Author: Heiner Marxen
Date: 12:36:42 02/17/00
Go up one level in this thread
On February 14, 2000 at 09:36:07, guy haworth wrote: >Lars Rasmussen mentioned this problem to me the other day. He has obviously >been thinking about this for some time but does not have an algorithm. > >Therefore, you have not missed the obvious. > >A similar problem is to devise an algorithm that spots (and eliminates from >consideration) 'time wasting' White moves in an endgame study that allow Black >to return to a previous position. > >It may be possible to do this 'within limits' but a general algorithm >guaranteeing to remove all time-wasting moves seems to imply an open-ended >amount of computing. > >Guy For my problem solver (Chest) I have also been thinking about "permanent check", since it is a great method for the defending side, but is not recognized by the normal tree search. A transposition table can help to increase the effective depth of the tree. I plan to implement a special algorithm, with the following restrictions: - the checking side moves around just one piece (hunting the king) - the other side is always forced to evade the check with a king move (no blocking/capture possible) - no irreversible moves occur Now the total amount of positions to consider is characterized by the sqares of the two moving pieces and the side to move: 2*64*64 = 8192. Now we can handle this like an endgame table: - the role of the terminal mate position is assigned to those positions, where the other side can escape the permanent check (no more check possible) - we backsolve to find the distance to an escape - those positions which are left over (no distance to escape == there is no escape), which in normal endgame table builds are draws, are now the positions, which we hunt for: proven permanent check. Of course, such an analysis is not cheap, and I have no idea how often it is successful. But when the normal search tree is large enough, one additional such analysis could be cheap enough to not slow down the overall search too much. Also, there is much room for efficiency tricks. We have to play with it and find out. Regarding a general solution: no, I have no idea how to do it. If anybody has other ideas how to tackle this problem, I would definitely like to hear about them. Heiner Marxen heiner@drb.insel.de http://www.drb.insel.de/~heiner/
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.