The Graph History Interaction (GHI) Problem

The Graph History Interaction (GHI) Problem occurs when the same game position behaves differently when reached via different paths. For example, after following one path a move m may be legal in position p, while after following another path the same move is illegal in p.

Our efficient solution to GHI was instrumental in developing the world's strongest tsume Go solver, and in solving checkers. For applications, see our research on tsume Go and seki.

Publications

J. Schaeffer, N. Burch, Y. Björnsson, A. Kishimoto, M. Müller, R. Lake, P. Lu, and S. Sutphen. Checkers is solved. Science, 317(5844):1518-1522, 2007. Originally published in Science Express on 19 July 2007.

A. Kishimoto. Correct and Efficient Search Algorithms in the Presence of Repetitions. PhD thesis, University of Alberta, 2005.

J. Schaeffer, Y. Björnsson, N. Burch, A. Kishimoto, M. Müller, R. Lake, P. Lu, and S. Sutphen. Solving Checkers. In International Joint Conference on Artificial Intelligence (IJCAI), pages 292-297, 2005.

A. Kishimoto and M. Müller. A solution to the GHI problem for depth-first proof-number search. Information Sciences, 175(4):296-314, 2005.

A. Kishimoto and M. Müller. A general solution to the graph history interaction problem. In Nineteenth National Conference on Artificial Intelligence (AAAI 2004), pages 644-649, San Jose, CA, 2004.

Created: Jan 20, 1998 Last modified: Jun 20, 2009

Martin Müller