nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

A Hybrid Approach to Parallelization of Monte Carlo Tree Search in General Game Playing

verfasst von : Maciej Świechowski, Jacek Mańdziuk

Erschienen in: Challenging Problems and Solutions in Intelligent Systems

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we investigate the concept of a parallelization of Monte Carlo Tree Search applied to games. Specifically, we consider General Game Playing framework, which has originated at Stanford University in 2005 and has become one of the most important realizations of the multi-game playing idea. We introduce a novel parallelization method, called Limited Hybrid Root-Tree Parallelization, based on a combination of two existing ones (Root and Tree Parallelization) additionally equipped with a mechanism of limiting actions available during the search process. The proposed approach is evaluated and compared to the non-limited hybrid version counterpart and to the Tree Parallelization method. The advantages over Root Parallelization are derived on a theoretical basis. In the experiments, the proposed method is more effective than Tree Parallelization and also than non-limited hybrid version in certain games.

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

Vorheriges Kapitel Transaction Protocol and Mechanisms for Adaptive Management of Long-Running Tasks

Nächstes Kapitel A Consensus Reaching Support System for Multi-criteria Decision Making Problems

Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Boston (1995)MATH

Arneson, B., Hayward, R.B., Henderson, P.: Monte Carlo tree search in hex. IEEE Trans. Comput. Intell. AI Games 2(4), 251–258 (2010)CrossRef

Björnsson, Y., Finnsson, H.: CadiaPlayer: a simulation-based general game player. IEEE Trans. Comput. Intell. AI Games 1(1), 4–15 (2009)CrossRef

Bratko, I.: Prolog Programming for Artificial Intelligence. International Computer Science Series. Addison Wesley, Boston (2001)MATH

Browne, C.B., Powley, E., Whitehouse, D., Lucas, S.M., Cowling, P.I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., Colton, S.: A survey of Monte Carlo tree search methods. IEEE Trans. Comput. Intell. AI Games 4(1), 1–43 (2012)CrossRef

Cazenave, T., Jouandeau, N.: On the parallelization of UCT. Proc. CGW07, 93–101 (2007)

Cazenave, T., Jouandeau, N.: A parallel Monte-Carlo tree search algorithm. In: Computers and Games, pp. 72–80. Springer, Berlin (2008)

Chaslot, G., Winands, M.H., Szita, I., van den Herik, H.J.: Cross-entropy for Monte-Carlo tree search. ICGA J. 31(3), 145–156 (2008)

Coulom, R.: Efficient selectivity and backup operators in Monte-Carlo tree search. In: Computers and Games, pp. 72–83. Springer, Berlin (2007)

10.

Enzenberger, M., Müller, M.: A lock-free multithreaded Monte-Carlo tree search algorithm. In: Advances in Computer Games, pp. 14–20. Springer, Berlin (2010)

11.

Gelly, S., Silver, D.: Achieving Master Level Play in 9 x 9 Computer Go. In: AAAI, vol. 8, pp. 1537–1540 (2008)

12.

Gelly, S., Kocsis, L., Schoenauer, M., Sebag, M., Silver, D., Szepesvári, C., Teytaud, O.: The grand challenge of computer Go: Monte Carlo tree search and extensions. Commun. ACM 55(3), 106–113 (2012)CrossRef

13.

Genesereth, M.R., Love, N., Pell, B.: General game playing: overview of the AAAI competition. AI Mag. 26(2), 62–72 (2005)

14.

Kocsis, L., Szepesvári, C.: Bandit based Monte-Carlo planning. In: Proceedings of the 17th European Conference on Machine Learning. ECML’06, pp. 282–293. Springer, Berlin (2006)

15.

Love, N., Hinrichs, T., Haley, D., Schkufza, E., Genesereth, M.: General Game Playing: Game Description Language specification. http://games.stanford.edu/readings/gdl_spec.pdf (2008)

16.

Mańdziuk, J., Świechowski, M.: Generic heuristic approach to general game playing. In: Bieliková, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Turán, G. (eds.) SOFSEM. Lecture Notes in Computer Science, vol. 7147, pp. 649–660. Springer, Berlin (2012)

17.

Méhat, J., Cazenave, T.: A parallel general game player. Künstliche Intell. 25(1), 43–47 (2011)CrossRef

18.

Méhat, J., Cazenave, T.: Tree parallelization of ary on a cluster. In: Proceedings of the IJCAI-11 Workshop on General Game Playing (GIGA’11), pp. 39–43 (2011)

19.

Plaat, A., Schaeffer, J., Pijls, W., de Bruin, A.: Best-first fixed-depth minimax algorithms. Artif. Intell. 87(1–2), 255–293 (1996)MathSciNetCrossRef

20.

Świechowski, M.: Adaptive simulation-based meta-heuristic methods in synchronous multiplayer games. Ph.D. thesis, Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland (2015) in review

21.

Świechowski, M., Mańdziuk, J.: Fast interpreter for logical reasoning in general game playing. J. Log. Comput. (2014). doi:10.1093/logcom/exu058

22.

Świechowski, M., Mańdziuk, J.: Self-adaptation of playing strategies in general game playing. IEEE Trans. Comput. Intell. AI Games 6(4), 367–381 (2014)CrossRef

23.

Świechowski, M., Mańdziuk, J.: Specialized vs. multi-game approaches to AI in games. In: Angelov, P., Atanassov, K., Doukovska, L., Hadjiski, M., Jotsov, V., Kacprzyk, J., Kasabov, N., Sotirov, S., Szmidt, E., Zadrożny, S. (eds.) Intelligent Systems’2014. Advances in Intelligent Systems and Computing, vol. 322, pp. 243–254. Springer International Publishing (2015)

24.

Świechowski, M., Mańdziuk, J., Ong, Y.S.: Specialization of a UCT-based general game playing program to single-player games. IEEE Trans. Comput. Intell. AI Games (2015) (accepted for publication)

25.

Świechowski, M., Park, H., Mańdziuk, J., Kim, K.: Recent advances in general game playing. Sci. World J. 2015. http://dx.doi.org/10.1155/2015/986262 (2015)

26.

Syed, O., Syed, A.: Arimaa - a new game designed to be difficult for computers. ICGA 26, 138–139 (2003)

27.

Teytaud, F., Teytaud, O.: Creating an upper-confidence-tree program for Havannah. In: Advances in Computer Games, pp. 65–74. Springer, Berlin (2010)

Titel: A Hybrid Approach to Parallelization of Monte Carlo Tree Search in General Game Playing
verfasst von: Maciej Świechowski
Jacek Mańdziuk
Verlag: Springer International Publishing
Buch: Challenging Problems and Solutions in Intelligent Systems
Print ISBN: 978-3-319-30164-8

Electronic ISBN: 978-3-319-30165-5

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-30165-5_10

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"