Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2017 | OriginalPaper | Buchkapitel

1. Game Solvers

verfasst von : Akihiro Kishimoto, Martin Mueller

Erschienen in: Handbook of Digital Games and Entertainment Technologies

Verlag: Springer Singapore

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Games have simple, fixed rules as well as clear results such as win, draw, or loss. However, developing algorithms for solving games has been a difficult challenge in Artificial Intelligence, because of the combinatorial complexity that the algorithms must tackle.
This chapter presents an overview of successful approaches and results accomplished thus far on game solving. Conducting tree search is a standard way to solve games and game positions. Remarkable progress has been made in developing efficient search algorithms over the last few decades. The chapter describes several standard techniques including αβ search, proof-number search, and endgame databases.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Nächstes Kapitel General Game Playing
Literatur
L.V. Allis, A Knowledge-Based Approach of Connect Four: The Game is Over, White to Move Wins. Master’s thesis, Vrije Universiteit Amsterdam, Amsterdam, 1988. Report No. IR-163
L.V. Allis, Searching for Solutions in Games and Artificial Intelligence. PhD thesis, University of Limburg, Maastricht, 1994
L.V. Allis, M.P.H. Huntjes, H.J. van den Herik, Go-moku solved by new search techniques. Comput. Intell. 12(1), 7–23 (1996)CrossRef
V. Anshelevich, A hierarchical approach to computer Hex. Artif. Intell. 134(1–2), 101–120 (2002)CrossRefMATH
B. Arneson, R.B. Hayward, P. Henderson, Solving Hex: beyond humans, in Computers and Games 2010, ed. by H.J. van den Herik, H. Iida, A. Plaat. Lecture Notes in Computer Science (LNCS), vol. 6515 (Springer, Berlin, 2011), pp. 1–10CrossRef
D. Beal, M.C. Smith, Multiple probes of transposition tables. ICCA J. 19(4), 227–233 (1996)
R. Bellman, On the application of dynamic programming to the determination of optimal play in chess and checkers. Proc. Natl. Acad. Sci. U. S. A. 53, 244247 (1965)MathSciNetMATH
D.M. Breuker, Memory Versus Search in Games. PhD thesis, Universiteit Maastricht, Maastricht, 1998
M. Campbell, The graph-history interaction: on ignoring position history, in Proceedings of the 1985 ACM Annual Conference on the Range of Computing: Mid-80’s Perspective, (ACM, New York, 1985). pp. 278–280
M. Campbell, A.J. Hoane Jr., F. Hsu, Deep Blue. Artif. Intell. 134(1–2), 57–83 (2002)CrossRefMATH
T. Cazenave, A generalized threats search algorithm, in Computers and Games 2002, ed. by J. Schaeffer, M. Müller, Y. Björnsson. Lecture Notes in Computer Science (LNCS) (Springer, Heidelberg, 2002), pp. 75–87
A. de Bruin, W. Pijls, A. Plaat, Solution trees as a basis for game tree search. ICCA J. 17(4), 207–219 (1994)
R. Gasser, Solving Nine Men’s Morris, in Games of No Chance, ed. by R.J. Nowakowski. MSRI Publications, vol. 29 (Cambridge University Press, Cambridge, 1996), pp. 101–113
R. Greenblatt, D. Eastlake, S. Croker, The Greenblatt chess program, in Proceedings of the Fall Joint Computer Conference, 1967, pp. 801–810. Reprinted (1988) in Computer Chess Compendium, ed. by D.N.L. Levy (Batsford, London), pp. 56–66
P. Henderson, B. Arneson, R.B. Hayward, Solving 8 × 8 Hex, in Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI’09), ed. by C. Boutilier (AAAI Press, Pasadena, 2009), pp. 505–510
T. Kaneko, Parallel depth first proof number search, in Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, (AAAI’10), ed. by M. Fox, D. Poole (AAAI Press, Menlo Park, 2010), pp. 95–100
Y. Kawano, Using similar positions to search game trees, in Games of No Chance, ed. by R.J. Nowakowski. MSRI Publications, vol. 29 (Cambridge University Press, Cambridge, 1996), pp. 193–202
A. Kishimoto, Dealing with infinite loops, underestimation, and overestimation of depth-first proof-number search, in Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, (AAAI’10), ed. by M. Fox, D. Poole (AAAI Press, 2010)
A. Kishimoto, M. Müller, About the completeness of depth-first proof-number search, in Computers and Games 2008, ed. by H.J. van den Herik, X. Xu, Z. Ma, M.H.M. Winands. Lecture Notes in Computer Science, vol. 5131 (Springer, Heidelberg, 2008), pp. 146–156
A. Kishimoto, M. Müller, Df-pn in Go: an application to the one-eye problem, in Advances in Computer Games 10 (ACG’03): Many Games, Many Challenges, ed. by H.J. van den Herik, H. Iida, E.A. Heinz (Kluwer, Boston, 2003), pp. 125–141
A. Kishimoto, M. Müller, Search versus knowledge for solving life and death problems in Go, in Proceedings of the 20th National Conference on Artificial Intelligence (AAAI’05), ed. by M.M. Veloso, S. Kambhampati (AAAI Press/MIT Press, Menlo Park, 2005), pp. 1374–1379
A. Kishimoto, M. Winands, M. Müller, J.-T. Saito, Game-tree search using proof numbers: the first twenty years. ICGA J. 35(3), 131–156 (2012)CrossRef
R. Lake, J. Schaeffer, P. Lu, Solving large retrograde analysis problems using a network of workstations. Advances in Computer Games 7, 135–162 (1994)
T. Lincke, Exploring the Computational Limits of Large Exhaustive Search Problems. PhD thesis, ETH Zürich, 2002
T. Marsland, A review of game-tree pruning. ICCA J. 9(1), 3–19 (1986)
A. Nagai, A new depth-first-search algorithm for AND/OR trees. Master’s thesis, The University of Tokyo, Tokyo, 1999
A. Nagai, Df-pn Algorithm for Searching AND/OR trees and its Applications. PhD thesis, The University of Tokyo, 2002
J. Nash, Some games and machines for playing them. Technical Report D-1164, Rand Corp., 1952
A.J. Palay, Searching with Probabilities. PhD thesis, Carnagie Mellon University, 1983
J. Pawlewicz, R. Hayward, Scalable parallel depth first proof number search, in Computers and Games (CG 2013), vol. 8427. Lecture Notes in Computer Science (Springer, 2014), pp. 138–150
J. Pawlewicz, L. Lew, Improving depth-first pn-search: 1+ε trick, in Proceedings of the 5th Computers and Games Conference (CG’06), ed. by H.J. van den Herik, P. Ciancarini, H.H.L.M. Donkers. Lecture Notes in Computer Science, vol. 4630 (Springer, Heidelberg, 2007), pp. 160–170
J. Pearl, Heuristics: Intelligent Search Strategies for Computer Problem Solving (Addison-Wesley, Reading, 1984)
J.W. Romein, H. Bal, Solving the game of Awari using parallel retrograde analysis. IEEE Comput. 36(10), 26–33 (2003)CrossRef
A. Saffidine, T. Cazenave, Developments on product propagation. in Computer Games 2013, vol. 8427. Lecture Notes in Computer Science, 2013, pp. 100–109
J. Schaeffer, The history heuristic and alpha-beta search enhancements in practice. IEEE Trans. Pattern Anal. Mach. Intell. 11(1), 1203–1212 (1989)CrossRef
J. Schaeffer, Y. Björnsson, N. Burch, R. Lake, P. Lu, S. Sutphen, Building the checkers 10-piece endgame databases, in Advances in Computer Games 10: Many Games, ed. by H.J. van den Herik, H. Iida, E.A. Heinz. (Kluwer, Boston, 2003), pp. 193–210
J. Schaeffer, N. Burch, Y. Björnsson, A. Kishimoto, M. Müller, R. Lake, P. Lu, S. Sutphen, Checkers is solved. Science 317(5844), 1518–1522 (2007)MathSciNetCrossRefMATH
M. Seo, On effective utilization of dominance relations in tsume-shogi solving algorithms, in Proceedings of the 8th Game Programming Workshop, 1999, pp. 137–144 (in Japanese)
M. Seo, H. Iida, J.W.H.M. Uiterwijk, The PN*-search algorithm: Application to tsume shogi. Artif. Intell. 129(1–2), 253–277 (2001)MathSciNetCrossRefMATH
D.J. Slate, L.R. Atkin, Chapter 4. Chess 4.5 – Northwestern University chess program, in Chess Skill in Man and Machine, ed. by P.W. Frey (Springer, New York, 1977), pp. 82–118
J. Song, M. Müller, An enhanced solver for the game of Amazons, 2014, in Accepted for IEEE Transactions on Computational Intelligence and AI in Games (TCIAIG), 12 pp
D. Stern, R. Herbrich, T. Graepel, Learning to solve game trees, in Proceedings of the 24th International Conference of Machine Learning (ICML), 2007, pp. 839–846
K. Thompson, Retrograde analysis of certain endgames. ICCA J. 9(3), 131–139 (1986)
T. Thomsen, Lambda-search in game trees – with application to Go. ICGA J. 23(4), 203–217 (2000)
Y. Tsuruoka, D. Yokoyama, T. Chikayama, Game-tree search algorithm based on realization probability. ICGA J. 25(3), 132–144 (2002)
E.C.D. van der Werf, H.J. van den Herik, J.W.H.M. Uiterwijk, Solving Go on small boards. ICGA J. 26(2), 92–107 (2003)
M.H.M. Winands, J.W.H.M. Uiterwijk, H.J. van den Herik, An effective two-level proof-number search algorithm. Theor. Comput. Sci 313(3), 511–525 (2004)MathSciNetCrossRefMATH
M.H.M. Winands, Y. Björnsson, J.-T. Saito, Monte-Carlo tree search solver, in Proceedings of the 6th Computers and Games Conference (CG’08), ed. by H.J. van den Herik, X. Xu, Z. Ma, M.H.M. Winands. Lecture Notes in Computer Science, vol. 5131 (Springer, Berlin, 2008), pp. 25–36
T. Wolf, The program GoTools and its computer-generated tsume Go database, in 1st Game Programming Workshop in Japan (Hakone), 1994
K. Yoshizoe, A. Kishimoto, M. Müller, Lambda depth-first proof number search and its application to Go, in Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-07), ed. by M.M. Veloso (2007), Morgan Kaafmann, San Francisco, pp. 2404–2409
Metadaten
Titel
Game Solvers
verfasst von
Akihiro Kishimoto
Martin Mueller
Copyright-Jahr
2017
Verlag
Springer Singapore
Buch
Handbook of Digital Games and Entertainment Technologies

Print ISBN: 978-981-4560-49-8

Electronic ISBN: 978-981-4560-50-4

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-981-4560-50-4_35

Premium Partner

    Bildnachweise