Aquarium IDEA, repetitions, and minimax over cycles

[kevinfat]

Does anyone have an idea how Aquarium's interactive deep analysis (IDEA) works when encountering cycles in the graph of positions? Consider a position where the best play for both sides is to follow a line that is quite lengthy but eventually comes back to the original position. When IDEA adds the information for the last moves of that line how does it detect that it has completed a cycle. And even if it detects the long cycle how would it know to evaluate the positions in the cycle as 0.0, meaning a draw? Not all cycles should be automatically evaluated at 0.0 since some cycles will have positions where making a move that leaves the cycle is best. And it is not obvious to me how, if it is possible at all, to make minimax work here since minimax is meant for directed acyclic graphs.

Is anyone aware of how minimax on graphs with cycles is handled so that perpetuals and repetitions in the graph are correctly evaluated?

[syzygy]

Thomas Lincke's PhD thesis Exploring the Computational Limits of Large Exhaustive Search Problems has a section on it (section 4.3).

[kevinfat]

Thomas Lincke's PhD thesis Exploring the Computational Limits of Large Exhaustive Search Problems has a section on it (section 4.3).

That thesis is an amazing find though I'm saddened to see that the thesis was written in 2002 which is before the paper by Kishimoto and Muller (2004) http://webdocs.cs.ualberta.ca/~mmueller/ghi.html. I would have really liked it if the thesis had some commentary on that paper by Kishimoto and Muller because I am finding it impossible to understand their paper.

[BB+]

Not really a direct answer to your question, but:
I recently wrote/adapted some code for Losing Chess, and was eager to put transpositions in (as Nilatac does not have them, at least for unsolved positions). But in the end, I decided that it was easiest to only do transpositions when the move-counter was zero (so that GHI was not a problem). I also declared draws to be Black wins (since I am trying to prove the game is won for White), which also avoids many difficulties. But I found that even with these simplifications, keeping track of transpositions slowed down my code quite noticeably. In a middlegame position, I could hit 10 million nodes (the pn-search cutoff) in about 5-6 seconds, while endgame positions, where there would typically be more transpositions, would typically time-out at my imposed 10 second limit, searching maybe 6-7 million nodes. The difference (I think, though I should check) is that the updating part of the minimax would take much longer when there were more transpositions around. I seem to recall a similar comment from "buffos" (an Aquarium/IDeA developer, I think) on Rybka Forum in response to a question about why a tree update was taking so long (he queried/guessed along the lines of whether there were many transpositions).

[syzygy]

Thomas Lincke's PhD thesis Exploring the Computational Limits of Large Exhaustive Search Problems has a section on it (section 4.3).

That thesis is an amazing find though I'm saddened to see that the thesis was written in 2002 which is before the paper by Kishimoto and Muller (2004) http://webdocs.cs.ualberta.ca/~mmueller/ghi.html. I would have really liked it if the thesis had some commentary on that paper by Kishimoto and Muller because I am finding it impossible to understand their paper.

As far as I understand these papers, they do NOT have a general solution to the GHI problem. Instead, they have a way of dealing with the problem for positions that are being proved or disproved as a win. This basically reduces the applicability of this solution to chess to mate solvers.

It might be possible to apply the same technique to solve it for heuristic evaluations, but it seems that would basically come down to removing transpositions altogether.

What they do is keep track of two hash keys. One (normal) path independent hash key and one path dependent hash key. If a position has been proved or disproved and this position is later encountered through a transposition (i.e. same path independent hash key, but different path dependent hash key), then the proof tree that proved this position is replayed ("simulated") to determine whether it also proves this position given the new history. I'm not sure how this proof tree is remembered, but I suppose the idea is to retrieve it from the hash table. If the proof works, then the position is proved (or disproved, i.e. proved not to be winning). If the proof does not work (because of a draw by repetition due to the new path history or in case of a disproof due to a draw by repetition in the proof tree for the earlier position that does not work for the transposed path), the position will have to be searched further. As far as I understand, in all cases proved/disproved positions that are identical but for their history must be stored separately (and their proof trees should be remembered).

In case alpha/beta is used with a heuristic evaluation function, the papers seem to accept (and acknowledge) that the GHI problem still affects these values. This is not considered to be a problem, since the goal underlying these papers is to solve checkers, for which GHI-unaffected heuristic values would be nice to have but are not essential, and for which GHI-unaffected proved / disproved value are essential. The solution is "general" only in the sense that it is not tied to the search algorithm.

Applying the solution to obtain GHI-unaffected heuristic values, one would need to store all transposed positions separately in the hash table, i.e. remove all transpositions. Without transpositions the GHI problem does indeed not occur, but this we already knew. What the papers add is the idea of replaying proof trees. For heuristic values this basically means to use hash moves of transpositions, which I guess gives some benefit but will never come close to the efficiency achieved by simply ignoring the GHI problem.

[BB+]

As far as I understand these papers, they do NOT have a general solution to the GHI problem. Instead, they have a way of dealing with the problem for positions that are being proved or disproved as a win. This basically reduces the applicability of this solution to chess to mate solvers.

This is my understanding too, that their work most directly applies to proof trees with definite results. However, in analogue to parts of the checkers solution [and MTD(f) for that matter], one can (try to) weasel out of this by turning all questions into yes/no decisions by iterating over a cutoff vis-a-vis a heuristic evaluation. Whether or not this is practical or useful is a different inquiry (and my guess would be that overall it is not).

[kevinfat]

Thomas Lincke's PhD thesis Exploring the Computational Limits of Large Exhaustive Search Problems has a section on it (section 4.3).

That thesis is an amazing find though I'm saddened to see that the thesis was written in 2002 which is before the paper by Kishimoto and Muller (2004) http://webdocs.cs.ualberta.ca/~mmueller/ghi.html. I would have really liked it if the thesis had some commentary on that paper by Kishimoto and Muller because I am finding it impossible to understand their paper.

As far as I understand these papers, they do NOT have a general solution to the GHI problem. Instead, they have a way of dealing with the problem for positions that are being proved or disproved as a win. This basically reduces the applicability of this solution to chess to mate solvers.

It might be possible to apply the same technique to solve it for heuristic evaluations, but it seems that would basically come down to removing transpositions altogether.

What they do is keep track of two hash keys. One (normal) path independent hash key and one path dependent hash key. If a position has been proved or disproved and this position is later encountered through a transposition (i.e. same path independent hash key, but different path dependent hash key), then the proof tree that proved this position is replayed ("simulated") to determine whether it also proves this position given the new history. I'm not sure how this proof tree is remembered, but I suppose the idea is to retrieve it from the hash table. If the proof works, then the position is proved (or disproved, i.e. proved not to be winning). If the proof does not work (because of a draw by repetition due to the new path history or in case of a disproof due to a draw by repetition in the proof tree for the earlier position that does not work for the transposed path), the position will have to be searched further. As far as I understand, in all cases proved/disproved positions that are identical but for their history must be stored separately (and their proof trees should be remembered).

In case alpha/beta is used with a heuristic evaluation function, the papers seem to accept (and acknowledge) that the GHI problem still affects these values. This is not considered to be a problem, since the goal underlying these papers is to solve checkers, for which GHI-unaffected heuristic values would be nice to have but are not essential, and for which GHI-unaffected proved / disproved value are essential. The solution is "general" only in the sense that it is not tied to the search algorithm.

Applying the solution to obtain GHI-unaffected heuristic values, one would need to store all transposed positions separately in the hash table, i.e. remove all transpositions. Without transpositions the GHI problem does indeed not occur, but this we already knew. What the papers add is the idea of replaying proof trees. For heuristic values this basically means to use hash moves of transpositions, which I guess gives some benefit but will never come close to the efficiency achieved by simply ignoring the GHI problem.

Even though Kishimoto and Muller (2004) http://webdocs.cs.ualberta.ca/~mmueller/ghi.html as you say is aimed at a different problem space I would be interested in trying to understand it. It would be really nice if someone wrote up a detailed explanation of their paper. There isn't a single diagram or figure in their paper!

[syzygy]

As far as I understand these papers, they do NOT have a general solution to the GHI problem. Instead, they have a way of dealing with the problem for positions that are being proved or disproved as a win. This basically reduces the applicability of this solution to chess to mate solvers.

This is my understanding too, that their work most directly applies to proof trees with definite results. However, in analogue to parts of the checkers solution [and MTD(f) for that matter], one can (try to) weasel out of this by turning all questions into yes/no decisions by iterating over a cutoff vis-a-vis a heuristic evaluation. Whether or not this is practical or useful is a different inquiry (and my guess would be that overall it is not).

To verify that an exact value is exactly correct, one would need to do two zero window searches based on the hash moves stored for the transposed node and its children, or a single full window search. In alpha/beta you will usually not need an exact value (and usually no exact value will be stored), so it would be sufficient to do a single zero window search to verify that a stored bound is correct. In any case the solution presented seems to come down to storing all transpositions of a node separately (or rather, all positions that are identical except for their history since the last zeroing move), but reusing hash moves stored for transposed nodes. I would be surprised if this pays off in chess for game play.

I don't know much about IDEA, but I imagine it builds an (on-disk?) tree (graph) of positions where the leaf nodes store the values of normal alpha/beta searches, which values are backed up to the interior nodes using minimax, with the user or some algorithm deciding which leaf nodes to expand further. In that case it seems possible to use the ideas of the paper: store transposed positions separately, and check whether the subtree (well... graph) of an already stored transposition is unaffected by draws by repetition (and possibly the 50-move rule) both for that stored transposition and for the position being added, and if so, duplicate that subtree. Ignore the problem for the leaf nodes. For endgames this probably leads to an explosion of the tree size. I suppose if positions are affected by the GHI problem it doesn't hurt too much to duplicate the subtree anyway, as long as the draw by repetition (and possibly the 50-move rule) are correctly taken into account when expanding the position being added with the subtree.

If detecting draws by repetitions is not necessary, an easier solution is allowing transpositions but hashing in the move counter. This will avoid cycles. Of course without such repetition detection the tree might expand arbitrarily deep while just repeating positions, so one would have to make the cost of expanding positions with high move counter high (in the function deciding on which node to expand next).

I haven't studied Lincke's idea well enough to be able to say much about his proposal.

[syzygy]

Even though Kishimoto and Muller (2004) http://webdocs.cs.ualberta.ca/~mmueller/ghi.html as you say is aimed at a different problem space I would be interested in trying to understand it. It would be really nice if someone wrote up a detailed explanation of their paper. There isn't a single diagram or figure in their paper!

I suggest trying to read what I wrote, since I've made an attempt to explain it. Of course based on my understanding, which may well be flawed. However, what I try to explain at least seems to make sense so might be helpful.