Optimisation of MCTS player for The Lord of the Rings: The Card Game

• Autorzy: Godlewski Konrad , Sawicki Bartosz

Identyfikatory

DOI

10.24425/bpasts.2021.136752

• Języki publikacji: EN

Abstrakty

EN

The article presents research on the use of Monte-Carlo Tree Search (MCTS) methods to create an artificial player for the popular card game “The Lord of the Rings”. The game is characterized by complicated rules, multi-stage round construction, and a high level of randomness. The described study found that the best probability of a win is received for a strategy combining expert knowledge-based agents with MCTS agents at different decision stages. It is also beneficial to replace random playouts with playouts using expert knowledge. The results of the final experiments indicate that the relative effectiveness of the developed solution grows as the difficulty of the game increases.

Słowa kluczowe

EN

computational intelligence; LoTR; Lord of the Rings; Monte Carlo Tree Search

PL

inteligencja obliczeniowa; Monte Carlo Tree Search; Władca Pierścieni

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2021
• Tom: Vol. 69, nr 3
• Strony: art. no. e136752
• Opis fizyczny: Bibliogr. 23 poz., rys., tab.

Twórcy

autor

Godlewski Konrad

• Warsaw University of Technology, ul. Koszykowa 75, 00-662 Warsaw, Poland

autor

Sawicki Bartosz

• Warsaw University of Technology, ul. Koszykowa 75, 00-662 Warsaw, Poland

Bibliografia

• [1] C. Browne, “A survey of monte carlo tree search methods”, IEEE Trans. Comput. Intell. AI Games 4., 1–43 (2012).
• [2] R. Bjarnason, A. Fern, and P. Tadepalli, “Lower bounding Klondike solitaire with Monte-Carlo planning”, Nineteenth International Conference on Automated Planning and Scheduling, 2009.
• [3] M. Świechowski, T. Tajmajer, and A. Janusz, “Improving hearthstone ai by combining mcts and supervised learning algo rithms”, 2018 IEEE Conference on Computational Intelligence and Games (CIG), 2018.
• [4] J. Mańdziuk, “MCTS/UCT in Solving Real-Life Problems”, Advances in Data Analysis with Computational Intelligence Methods, 277‒292, Springer, Cham, 2018.
• [5] S. Kajita, T. Kinjo, and T. Nishi, “Autonomous molecular design by Monte-Carlo tree search and rapid evaluations using molecular dynamics simulations”, Commun. Phys. 3(1), 1‒11 (2020).
• [6] S. Haeri and L. Trajković, “Virtual network embedding via Monte Carlo tree search”, IEEE Trans. Cybern. 48(2), 510‒521 (2017).
• [7] G. Best, O.M. Cliff, T. Patten, R.R. Mettu, and R. Fitch, “Decentralised Monte Carlo tree search for active perception”, Algorithmic Foundations of Robotics XII, 864‒879, Springer, Cham, 2020.
• [8] D.A. Dhar, P. Morawiecki, and S. Wójtowicz. “Finding differentia paths in arx ciphers through nested monte-carlo search”, AEU Int. J. Electron. Commun 64(2), 147‒150 (2018).
• [9] K. Guzek and P. Napieralski, “Measurement of noise in the Monte Carlo point sampling method”, Bull. Pol. Acad. Sci. Tech. Sci. 59(1), 15‒19 (2011).
• [10] D. Tefelski, T. Piotrowski, A. Polański, J. Skubalski and V. Blideanu, “Monte-Carlo aided design of neutron shielding concretes”, Bull. Pol. Acad. Sci. Tech. Sci. 61(1), 161‒171 (2013).
• [11] C.D. Ward and P.I. Cowling, “Monte Carlo search applied to card selection in Magic: The Gathering”, IEEE Symposium on Computational Intelligence and Games, 2009.
• [12] P.I. Cowling, C.D. Ward, and E.J. Powley, “Ensemble determinization in monte carlo tree search for the imperfect information card game magic: The gathering”, IEEE Trans. Comput. Intell. AI Games 4(4), 241‒257 (2012).
• [13] S. Turkay, S. Adinolf, and D. Tirthali, “Collectible Card Games as Learning Tools”, Procedia – Soc. Behav. Sci. 46, 3701‒3705 (2012), doi: 10.1016/j.sbspro.2012.06.130.
• [14] K. Bochennek, B. Wittekindt, S.-Y. Zimmermann, and T. Klingebiel, “More than mere games: a review of card and board games for medical education”, Med. Teach. 29(9), 941‒948 (2007), doi: 10.1080/01421590701749813.
• [15] J.S.B. Choe and J. Kim, “Enhancing Monte Carlo Tree Search for Playing Hearthstone”, 2019 IEEE Conference on Games (CoG), London, United Kingdom, 2019, pp. 1‒7.
• [16] K. Godlewski and B. Sawicki, “MCTS Based Agents for Multistage Single-Player Card Game”, 21st International Conference on Computational Problems of Electrical Engineering (CPEE), 2020.
• [17] “Magic: The Gathering”, [online] https://magic.wizards.com/en
• [18] E.J. Powley, P.I. Cowling, and D. Whitehouse. “Information capture and reuse strategies in Monte Carlo Tree Search, with applications to games of hidden information”, Artif. Intell. 217, 92‒116 (2014).
• [19] Fantasy Flight Publishing, “Hall of Beorn”, technical documentation, 2020 [Online] Available: http://hallofbeorn.com/LotR/Scenarios/Passage-Through-Mirkwood
• [20] S. Zhang and M. Buro, “Improving hearthstone AI by learning high-level rollout policies and bucketing chance node events”, 2017 IEEE Conference on Computational Intelligence and Games (CIG), New York, USA, 2017, pp. 309‒316.
• [21] G.M.J-B. Chaslot, M.H.M. Winands, and H.J. van Den Herik, “Parallel monte-carlo tree search”, International Conference on Computers and Games, Springer, Berlin, Heidelberg, 2008.
• [22] A. Fern and P. Lewis, “Ensemble monte-carlo planning: An empirical study”, Twenty-First International Conference on Automated Planning and Scheduling, ICAPS 2011, Germany, 2011.
• [23] A. Santos, P. A. Santos, and F.S. Melo, “Monte Carlo tree search experiments in hearthstone,” 2017 IEEE Conference on Computational Intelligence and Games (CIG), New York, USA, 2017, pp. 272‒279.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).