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.

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

## Table of Contents

Home * Search * Graph History InteractionGraph 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

## Selected Publications

1985).The graph-history interaction: on ignoring position history. Computer Science Department, Carnegie Mellon University, Proceedings of the 1985 ACM annual conference, pdf1999).A Solution to the GHI Problem for Best-First Search. CG 1998, pp. 25-49.2002).Exploring the Computational Limits of Large Exhaustive Search Problems. Ph.D thesis, ETH Zurich, pdf,^{[1]}Chapter 4.3 Cycles2004).A General Solution to the Graph History Interaction Problem. American Association for Artificial Intelligence (AAAI) National Conference, pp. 644-649, pdf2005).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 Search2009).Perfect-Information Games with Cycles. Ph.D. thesis, Aarhus University, advisor Peter Bro Miltersen, pdf2010).Theory of Computer Games: Concluding Remarks, slides as pdf## Forum posts

## External Links

## References

## What links here?

Up one Level