# 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.

## Contents

# See also

# 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,^{[1]}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

# External Links

# References

- ↑ Re: Aquarium IDEA, repetitions, and minimax over cycles by syzygy, OpenChess Forum, September 22, 2012