25,161
edits
Changes
Created page with "'''Home * Search * Graph History Interaction''' '''Graph History Interaction''' (GHI) is a general term related to the path-dependency i..."
'''[[Main Page|Home]] * [[Search]] * Graph History Interaction'''
'''Graph History Interaction''' (GHI) is a general term related to the [[Path-Dependency|path-dependency]] in search algorithms. GHI occurs when the same [[Chess Position|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'''). ''[http://portal.acm.org/citation.cfm?id=320516 The graph-history interaction: on ignoring position history]''. Computer Science Department, [[Carnegie Mellon University]], Proceedings of the 1985 ACM annual conference, [http://wiki.cs.pdx.edu/wurzburg2009/nfp/campbell-ghi.pdf pdf]
* [[Dennis Breuker]], [[Jaap van den Herik]], [[Jos Uiterwijk]], [[Victor Allis]] ('''1998'''). ''[http://link.springer.com/chapter/10.1007/3-540-48957-6_3 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]], [http://e-collection.library.ethz.ch/eserv/eth:25905/eth-25905-02.pdf pdf], <ref>[http://www.open-chess.org/viewtopic.php?f=5&t=2093#p17469 Re: Aquarium IDEA, repetitions, and minimax over cycles] by [[Ronald de Man|syzygy]], [[Computer Chess Forums|OpenChess Forum]], September 22, 2012</ref> 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, [http://webdocs.cs.ualberta.ca/~mmueller/ps/aaai-ghi.pdf 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, [http://webdocs.cs.ualberta.ca/~mmueller/ps/kishimoto-mueller-infsci-ghi.pdf pdf] » [[Proof-Number Search]]
* [[Kuang-che Wu]], [[Shun-Chin Hsu]], [[Tsan-sheng Hsu]] ('''2005'''). ''[http://link.springer.com/chapter/10.1007/11922155_13 The Graph-History Interaction Problem in Chinese Chess]''. [[Advances in Computer Games 11]]
* [[Daniel Andersson]] ('''2009'''). ''Perfect-Information Games with Cycles''. Ph.D. thesis, [https://en.wikipedia.org/wiki/Aarhus_University Aarhus University], advisor [[Mathematician#Miltersen|Peter Bro Miltersen]], [http://www.cs.au.dk/~koda/thesis.pdf pdf]
=Forum Posts=
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=182927 "Don't trust draw score" <=Is it true?] by [[Teerapong Tovirat]], [[CCC]], August 08, 2001 » [[Repetitions]]
* [https://www.stmintz.com/ccc/index.php?id=221335 Algorithm question for Heiner] by [[Tim Foden]] from [[CCC]], April 03, 2002
==2010 ...==
* [http://www.open-chess.org/viewtopic.php?f=5&t=1015 "No progress" and Graph History Interaction] by [[Mark Watkins|BB+]], [[Computer CHess Forums|OpenChess Forum]], January 23, 2011 » [[Fortress]]
* [http://www.talkchess.com/forum/viewtopic.php?t=40388 Repetitions/50 moves and TT] by [[Sergei Markoff]], [[CCC]], September 13, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=45250 Graph History Interaction Problem] by [[Cary Cherng]], [[CCC]], September 21, 2012
* [http://www.open-chess.org/viewtopic.php?f=5&t=2093 Aquarium IDEA, repetitions, and minimax over cycles] by kevinfat, [[Computer Chess Forums|OpenChess Forum]], September 17, 2012 » [[Aquarium]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2942 Another GHI example in SF (maybe)] by [[Mark Watkins|BB+]], [[Computer Chess Forums|OpenChess Forum]], December 30, 2015 » [[Stockfish]]
=External Links=
* [http://webdocs.cs.ualberta.ca/~mmueller/ghi.html The Graph History Interaction (GHI) Problem] by [[Martin Müller]]
=References=
<references />
'''[[Search|Up one Level]]'''
'''Graph History Interaction''' (GHI) is a general term related to the [[Path-Dependency|path-dependency]] in search algorithms. GHI occurs when the same [[Chess Position|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'''). ''[http://portal.acm.org/citation.cfm?id=320516 The graph-history interaction: on ignoring position history]''. Computer Science Department, [[Carnegie Mellon University]], Proceedings of the 1985 ACM annual conference, [http://wiki.cs.pdx.edu/wurzburg2009/nfp/campbell-ghi.pdf pdf]
* [[Dennis Breuker]], [[Jaap van den Herik]], [[Jos Uiterwijk]], [[Victor Allis]] ('''1998'''). ''[http://link.springer.com/chapter/10.1007/3-540-48957-6_3 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]], [http://e-collection.library.ethz.ch/eserv/eth:25905/eth-25905-02.pdf pdf], <ref>[http://www.open-chess.org/viewtopic.php?f=5&t=2093#p17469 Re: Aquarium IDEA, repetitions, and minimax over cycles] by [[Ronald de Man|syzygy]], [[Computer Chess Forums|OpenChess Forum]], September 22, 2012</ref> 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, [http://webdocs.cs.ualberta.ca/~mmueller/ps/aaai-ghi.pdf 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, [http://webdocs.cs.ualberta.ca/~mmueller/ps/kishimoto-mueller-infsci-ghi.pdf pdf] » [[Proof-Number Search]]
* [[Kuang-che Wu]], [[Shun-Chin Hsu]], [[Tsan-sheng Hsu]] ('''2005'''). ''[http://link.springer.com/chapter/10.1007/11922155_13 The Graph-History Interaction Problem in Chinese Chess]''. [[Advances in Computer Games 11]]
* [[Daniel Andersson]] ('''2009'''). ''Perfect-Information Games with Cycles''. Ph.D. thesis, [https://en.wikipedia.org/wiki/Aarhus_University Aarhus University], advisor [[Mathematician#Miltersen|Peter Bro Miltersen]], [http://www.cs.au.dk/~koda/thesis.pdf pdf]
=Forum Posts=
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=182927 "Don't trust draw score" <=Is it true?] by [[Teerapong Tovirat]], [[CCC]], August 08, 2001 » [[Repetitions]]
* [https://www.stmintz.com/ccc/index.php?id=221335 Algorithm question for Heiner] by [[Tim Foden]] from [[CCC]], April 03, 2002
==2010 ...==
* [http://www.open-chess.org/viewtopic.php?f=5&t=1015 "No progress" and Graph History Interaction] by [[Mark Watkins|BB+]], [[Computer CHess Forums|OpenChess Forum]], January 23, 2011 » [[Fortress]]
* [http://www.talkchess.com/forum/viewtopic.php?t=40388 Repetitions/50 moves and TT] by [[Sergei Markoff]], [[CCC]], September 13, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=45250 Graph History Interaction Problem] by [[Cary Cherng]], [[CCC]], September 21, 2012
* [http://www.open-chess.org/viewtopic.php?f=5&t=2093 Aquarium IDEA, repetitions, and minimax over cycles] by kevinfat, [[Computer Chess Forums|OpenChess Forum]], September 17, 2012 » [[Aquarium]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2942 Another GHI example in SF (maybe)] by [[Mark Watkins|BB+]], [[Computer Chess Forums|OpenChess Forum]], December 30, 2015 » [[Stockfish]]
=External Links=
* [http://webdocs.cs.ualberta.ca/~mmueller/ghi.html The Graph History Interaction (GHI) Problem] by [[Martin Müller]]
=References=
<references />
'''[[Search|Up one Level]]'''
