Graph History Interaction

Home * Search * Graph History Interaction

Graph History Interaction (GHI) is a general term related to the path-dependency in search algorithms. GHI occurs when the same game position behaves differently when reached via different paths.

See also

• Path-Dependency
• Transposition
• Transposition Table
• Repetitions
• Fifty-move Rule

Selected Publications

• Murray Campbell (1985). The graph-history interaction: on ignoring position history. Computer Science Department, Carnegie Mellon University, Proceedings of the 1985 ACM annual conference, pdf
• Dennis Breuker, Jaap van den Herik, Jos Uiterwijk, Victor Allis (1998). A Solution to the GHI Problem for Best-First Search. CG 1998
• Thomas Lincke (2002). Exploring the Computational Limits of Large Exhaustive Search Problems. Ph.D thesis, ETH Zurich, pdf, ¹ Chapter 4.3 Cycles
• Akihiro Kishimoto, Martin Müller (2004). A General Solution to the Graph History Interaction Problem. American Association for Artificial Intelligence (AAAI) National Conference, pp. 644-649, pdf
• Akihiro Kishimoto, Martin Müller (2005). A Solution to the GHI Problem for Depth-First Proof-Number Search. 7th Joint Conference on Information Sciences (JCIS2003), pages 489 - 492, pdf » Proof-Number Search
• Kuang-che Wu, Shun-Chin Hsu, Tsan-sheng Hsu (2005). The Graph-History Interaction Problem in Chinese Chess. Advances in Computer Games 11
• Daniel Andersson (2009). Perfect-Information Games with Cycles. Ph.D. thesis, Aarhus University, advisor Peter Bro Miltersen, pdf

Forum Posts

2000 ...

• "Don't trust draw score" <=Is it true? by Teerapong Tovirat, CCC, August 08, 2001 » Repetitions
• Algorithm question for Heiner by Tim Foden from CCC, April 03, 2002

2010 ...

• "No progress" and Graph History Interaction by BB+, OpenChess Forum, January 23, 2011 » Fortress
• Repetitions/50 moves and TT by Sergei Markoff, CCC, September 13, 2011
• Graph History Interaction Problem by Cary Cherng, CCC, September 21, 2012
• Aquarium IDEA, repetitions, and minimax over cycles by kevinfat, OpenChess Forum, September 17, 2012 » Aquarium
• Another GHI example in SF (maybe) by BB+, OpenChess Forum, December 30, 2015 » Stockfish
• Graph History Interaction 2 questions by Jouni Uski, CCC, December 15, 2019 » Fifty-move Rule

2020 ...

• Alpha-beta search for drawing endgames by Emanuel Torres, CCC, June 16, 2021 » Alpha-Beta, Draw Evaluation, Repetitions

External Links

• The Graph History Interaction (GHI) Problem by Martin Müller

References