Difference between revisions of "Graph History Interaction"
GerdIsenberg (talk | contribs) (Created page with "'''Home * Search * Graph History Interaction''' '''Graph History Interaction''' (GHI) is a general term related to the path-dependency i...") |
GerdIsenberg (talk | contribs) |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 24: | Line 24: | ||
* [https://www.stmintz.com/ccc/index.php?id=221335 Algorithm question for Heiner] by [[Tim Foden]] from [[CCC]], April 03, 2002 | * [https://www.stmintz.com/ccc/index.php?id=221335 Algorithm question for Heiner] by [[Tim Foden]] from [[CCC]], April 03, 2002 | ||
==2010 ...== | ==2010 ...== | ||
| − | * [http://www.open-chess.org/viewtopic.php?f=5&t=1015 "No progress" and Graph History Interaction] by [[Mark Watkins|BB+]], [[Computer | + | * [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=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.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=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]] | * [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]] | ||
| + | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72578 Graph History Interaction 2 questions] by [[Jouni Uski]], [[CCC]], December 15, 2019 » [[Fifty-move Rule]] | ||
| + | ==2020 ...== | ||
| + | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77497 Alpha-beta search for drawing endgames] by Emanuel Torres, [[CCC]], June 16, 2021 » [[Alpha-Beta]], [[Draw Evaluation]], [[Repetitions]] | ||
=External Links= | =External Links= | ||
| Line 35: | Line 38: | ||
=References= | =References= | ||
<references /> | <references /> | ||
| − | |||
'''[[Search|Up one Level]]''' | '''[[Search|Up one Level]]''' | ||
Latest revision as of 20:03, 17 June 2021
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
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
- 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
References
- ↑ Re: Aquarium IDEA, repetitions, and minimax over cycles by syzygy, OpenChess Forum, September 22, 2012
