Graph History Interaction Problem

[ccherng]

I am trying to understand how the paper by Kishimoto and Mueller solves the GHI problem. http://http://webdocs.cs.ualberta.ca/~mmueller/ghi.html

I tried reading their paper and I couldn't understand it. Could someone explain how it works in the following example.

Imagine in the graph there is a cycle in which represents that if either side leaves the cycle they are playing an inferior move. But how would the solution of Kishimoto and Mueller know to assign each position in the cycle an evaluation score of 0. It could only know that if the positions exiting the cycle were evaluated with inferior scores which mean that staying in the cycle is the best for both sides.

But suppose an evaluator gave a good score to a position P extended from the cycle, which has true objective evaluation that is poor. Then the cycle would not be scored 0 because there is a good move to exit the cycle. But what if later on extending the graph leads to backpropgating minimax that gives P an inferior score. Then the cycle should be scored 0. How would the solution of Kishimoto and Mueller know when to switch scores on the cycle? As backprogating minimax doesn't seem to be enough to switch the evaluation of a cycle.

It seems to me that there is a big difference in implementation between an in-memory depth first alpha beta search in chess which doesn't directly deal with representing the graph and never stores a full representation of the graph. VS a disk based graph database that truly stores the search graph and deals directly with cycles and multiple paths joining at a node. Since a disk based database allows extending the search at arbitrary points of the graph it seems to me that this would cause impossible problems for cycles already evaluated. Can someone explain to me how the paper by Kishimoto and Mueller solves the example I described above in a disk based graph database context.

[hgm]

This is a very nasty problem, and especially iterative deepening seems to completely wreck any attempt to solve it. If the loop is long (and loops in Chess are at least 4 ply) it is all to easy to enter the loop at two points through different paths. And then deepening both pathst would forever produce sufficient-depth hits on each other, hiding forever the fact that you are dealing with a loop.

[Rein Halbersma]

I agree it's extremely nasty. The mutual-masking problem with iterative deepening is hardest of all. In chapter 4 of Kishimoto's PhD thesis, some approaches are discussed. IIRC, one interesting thing he does is looking if the stored TT depths along a variation are monotically decreasing compared to the nominal depth that is passed as a parameter to the search() function. So if a successor has a higher depth stored than the current position, then you potentially have intertwined repetition loops. I never quite understood how his solution worked, however. I emailed him once and asked for his source code, but it was not available so who knows how it is supposed to work.

[Daniel Shawul]

I do not have time to read the paper but are you saying that no TT cutoffs are made when the search depth is more than what is needed?? The way you described it looks like impossible to do if the previous positions on the path are not stored in the TT. But if we make the decision before we do the cutoff , we may improve the on the problem with some sacrifice.
Aside from ID, what about GHI problems introduced by many other search tricks?

[ccherng]

This is a very nasty problem, and especially iterative deepening seems to completely wreck any attempt to solve it. If the loop is long (and loops in Chess are at least 4 ply) it is all to easy to enter the loop at two points through different paths. And then deepening both pathst would forever produce sufficient-depth hits on each other, hiding forever the fact that you are dealing with a loop.

So how would this work for the solution of checkers
http://webdocs.cs.ualberta.ca/~mmueller ... eckers.pdf

The solution to checkers is similiar to the question I posed. There is no depth first iterative deepening in the typical sense. It is a disk based search graph. The solution to checkers must have dealt with this cycle problem somehow? I would really love it if someone wrote up a detailed complete explanation for those of us not even experts at alpha beta pruning.

[Rein Halbersma]

So how would this work for the solution of checkers
http://webdocs.cs.ualberta.ca/~mmueller ... eckers.pdf

The solution to checkers is similiar to the question I posed. There is no depth first iterative deepening in the typical sense. It is a disk based search graph. The solution to checkers must have dealt with this cycle problem somehow? I would really love it if someone wrote up a detailed complete explanation for those of us not even experts at alpha beta pruning.

The solving algorithm is really well described in the book One Jump Ahead by Chinook project leader Jonathan Schaeffer. Basically they did an alpha-beta search and converted every score above/low a heuristic threshold to PROBABLE_WIN/LOS. Then they applied two proof-number searches to this tree, to check for a win or a loss (if neither was proven, the position was a draw). Finally, they iterated over the threshold until only really won/lost positions were left.

How exactly they applied the GHI solution to the alpha-beta part of this algorithm is not entirely clear to me (the proof-number part is described in Kishimoto's thesis, but only with pseudo-code).

[syzygy]

Then they applied two proof-number searches to this tree, to check for a win or a loss (if neither was proven, the position was a draw).

I suppose it is more accurate to say: if both were disproven.

How exactly they applied the GHI solution to the alpha-beta part of this algorithm is not entirely clear to me (the proof-number part is described in Kishimoto's thesis, but only with pseudo-code).

I don't know either, but one possibility is to include the move counter in the hashkey. Draws by repetition might not be so important in checkers with more than 10 pieces left on the board? (edit: This is clearly not what is done. I should have read the paper first.)

[ccherng]

So how would this work for the solution of checkers
http://webdocs.cs.ualberta.ca/~mmueller ... eckers.pdf

The solution to checkers is similiar to the question I posed. There is no depth first iterative deepening in the typical sense. It is a disk based search graph. The solution to checkers must have dealt with this cycle problem somehow? I would really love it if someone wrote up a detailed complete explanation for those of us not even experts at alpha beta pruning.

The solving algorithm is really well described in the book One Jump Ahead by Chinook project leader Jonathan Schaeffer. Basically they did an alpha-beta search and converted every score above/low a heuristic threshold to PROBABLE_WIN/LOS. Then they applied two proof-number searches to this tree, to check for a win or a loss (if neither was proven, the position was a draw). Finally, they iterated over the threshold until only really won/lost positions were left.

How exactly they applied the GHI solution to the alpha-beta part of this algorithm is not entirely clear to me (the proof-number part is described in Kishimoto's thesis, but only with pseudo-code).

Do you mean to imply that their solution explicitly used the fact that they were searching a vast space such that evaluating positions coarsely as WIN, LOSS, DRAW, UNKNOWN was good enough to show the initial positions were a draw?

Are you suggesting that their technique won't work for just some small search graph that is nowhere near exhaustive and uses real number evaluations at the "leaves" of the graph.

[Rein Halbersma]

Do you mean to imply that their solution explicitly used the fact that they were searching a vast space such that evaluating positions coarsely as WIN, LOSS, DRAW, UNKNOWN was good enough to show the initial positions were a draw?

Are you suggesting that their technique won't work for just some small search graph that is nowhere near exhaustive and uses real number evaluations at the "leaves" of the graph.

I wasn't suggesting anything. I simply tried to explain how their proof uses a threshold value to translate a alpha-beta search tree with heuristic scores to a binary search tree to which they could apply proof-number search. The Kishimoto thesis addresses how to apply the GHI solution to the latter tree, and also makes some comments on the alpha-beta tree. But the papers and the pseudo-code still leave some details unexplained. AFAIK, there isn't any dependency on the tree size, indeed the whole point is that the GHI solution also works for trees that don't fit into memory.