alpha-beta infinite depth issues

[bPawn]

Hi,

I develop my own chess engine focusing on endgame analysis mostly just for fun.

The problem is to decide if a position leads to a forced mate, forced stalemate or forced *nothing*.
We ignore the 3-fold repetition and 50-move rule. Also we completely ignore any arbitrary search-depth limits as we are interested in the perfect answer which is feasible given a simple position like 2K1R. Also we do not resort to retrograde analysis.

To make myself clear, by *nothing* I mean a situation where there is no way to reach a mate or a stalemate, e.g. only 2 Kings left, or a blockade of Pawns in the central rows forcing the Kings to move endlessly. In other words no way to have any progress at all, no possible captures in the future. I could also refer to cases where a player uses perpetual checks just to force an endless game to avoid a mate.

I am thinking about having something like a HashTable of already visited positions during my alpha-beta to prevent loops in the search graph and also a HashTable with the scores of the fully evaluated child positions (it makes sense to store the score because we have infinite depth). But how do I react upon visiting an already visited child position which is not yet fully evaluated? How to I figure out that this loop is just an innocent loop but not a *nothing* position? What modifications do I need to implement this infinite depth alpha-beta? Do I simply evaluate loops as zero but do not store their result? but will this affect my perfect score? Do I just skip this branch and if it is the only branch I return 0?

I would like to here your thoughts / pointers,

Best regards,
Kostas

[Aleks Peshkov]

Repetition detection with "perfect" draw score is a must. BTW alpha-beta is depth-first algorithm, so setting infinite depth would lead to practically infinite search time.

[crystalclear]

I came across something relevant the other day, and it seems a problem related to what you are describing is called the ..
graph history interaction problem.
A google on that should throw up lots of relevant information.

From what I read, the problem is not serious for iterative deepening searches.
However I suspect the solutions proposed in technical papers would be beneficial anyway - I have nothing to base that on, its a wild statement.

The technical article I read mentioned potential problems of missing a draw by repetion when one is available in a bad position, or thinking that a position is drawn due to using table entries, when a search at greater depth that ignored a table entry would find the win.

The solution that I read to the graph history interaction problem consisted of two things.
1. Detecting repeated positions.
2. Not storing history information for these positions in some cases.

I found it interest, as in my chess program I have a sort of "locking" of table entries for positions being considered. I unlock them when consideration of the position is over. That means that to detect repetition I can potentially look to see if a record is locked. The locking is done by incrementing a counter away from zero, so I could in theory also access a repetition count.

The article I read seemed to be about determining if a position was a win, draw or loss. For my chess program it is unlikely to often see the end of the game and so maybe the article I read doesn't apply or needs adapting. I think the idea (2) was more or less to not store draw positions, and of the rest to only store values that were "the right side" of the draw value.

I think I looked at this because my chess program was slow solving a well known test of transposition tables, the
Lasker-Reichhelm_Position
8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - -

Normally the transposition tables store information about a position, good or bad.
My naive understanding of what they contributed in this case was that they stored the way forwards, but that for nodes where looping (draw by repetition) appeared possible they would not store the bad scores so that they would be re-examined if a search at greater depth found a way forward towards a win.

I have higher priorites at the moment than interefence in searches between transposition tables and repetition of positions. But if I do try something, I'll report back on whether it improved node count for solving the position I mentioned earlier.