A Practical Solution to Handling Randomness and Imperfect Information in Monte Carlo Tree Search

• Autorzy: Świechowski Maciej , Tajmajer Tomasz

Identyfikatory

DOI

10.15439/2021F3

• Konferencja: Federated Conference on Computer Science and Information Systems (16 ; 02-05.09.2021 ; online)
• Języki publikacji: EN

Abstrakty

EN

This paper provides practical guidelines for developing strong AI agents based on the Monte Carlo Tree Search algorithm in a game with imperfect information and/or randomness. These guidelines are backed up by series of experiments carried out in the very popular game - Hearthstone. Despite the focus on Hearthstone, the paper is written with reusability and universal applications in mind. For MCTS algorithm, we introduced a few novel ideas such as complete elimination of the so-called nature moves, separation of decision and simulation states as well as a multi-layered transposition table. These have helped to create a strong Hearthstone agent.

Słowa kluczowe

EN

computer game; Monte Carlo methods; software agents; search tree

PL

gra komputerowa; Metody Monte Carlo; oprogramowanie; wyszukiwanie

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2021
• Tom: Vol. 25
• Strony: 101--110
• Opis fizyczny: Bibliogr. 32 poz., rys., tab., wykr.

Twórcy

autor

Świechowski Maciej

• QED Software, Warsaw, Poland

autor

Tajmajer Tomasz

• Institute of Informatics University of Warsaw, Poland
• QED Software, Warsaw, Poland

Bibliografia

• 1. L. Kurke, “Ancient Greek Board Games and How to Play Them,” Classical Philology, vol. 94, no. 3, pp. 247–267, 1999.
• 2. J. McCarthy, “Chess as the Drosophila of AI,” in Computers, chess, and cognition. Springer, 1990, pp. 227–237.
• 3. A. L. Samuel, “Some Studies in Machine Learning Using the Game of Checkers,” IBM Journal of research and development, vol. 3, no. 3, pp. 210–229, 1959.
• 4. C. E. Shannon, “XXII. Programming a Computer for Playing Chess,” The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, vol. 41, no. 314, pp. 256–275, 1950.
• 5. M. Buro and T. Furtak, “RTS Games as Test-Bed for Real-Time AI Research,” in Proceedings of the 7th Joint Conference on Information Science (JCIS 2003), 2003, pp. 481–484.
• 6. M. R. Genesereth, N. Love, and B. Pell, “General Game Playing: Overview of the AAAI Competition,” AI Magazine, vol. 26, no. 2, pp. 62–72, 2005.
• 7. M. Świechowski and J. Mańdziuk, “Self-Adaptation of Playing Strategies in General Game Playing,” IEEE Transactions on Computational Intelligence and AI in Games, vol. 6, no. 4, pp. 367–381, Dec 2014.
• 8. M. Świechowski, H. Park, J. Mańdziuk, and K.-J. Kim, “Recent Advances in General Game Playing,” The Scientific World Journal, vol. 2015, 2015.
• 9. J. Levine, C. B. Congdon, M. Ebner, G. Kendall, S. M. Lucas, R. Miikkulainen, T. Schaul, and T. Thompson, “General Video Game Playing,” Dagstuhl Follow-Ups, vol. 6, 2013.
• 10. S. Sharma, Z. Kobti, and S. Goodwin, “Knowledge Generation for Improving Simulations in UCT for General Game Playing,” in Australasian Joint Conference on Artificial Intelligence. Springer, 2008, pp. 49–55.
• 11. S. Haufe, D. Michulke, S. Schiffel, and M. Thielscher, “Knowledge-Based General Game Playing,” KI-Künstliche Intelligenz, vol. 25, no. 1, pp. 25–33, 2011.
• 12. I. Szita, G. Chaslot, and P. Spronck, “Monte-Carlo Tree Search in Settlers of Catan,” in Advances in Computer Games. Springer, 2009, pp. 21–32.
• 13. 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 Transactions on Computational Intelligence and AI in Games, vol. 4, no. 4, pp. 241–257, 2012.
• 14. G. Van den Broeck, K. Driessens, and J. Ramon, “Monte-Carlo Tree Search in Poker Using Expected Reward Distributions,” in Asian Conference on Machine Learning. Springer, 2009, pp. 367–381.
• 15. D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot et al., “Mastering the Game of Go with Deep Neural Networks and Tree Search,” Nature, vol. 529, no. 7587, pp. 484–489, 2016.
• 16. B. Arneson, R. B. Hayward, and P. Henderson, “Monte Carlo Tree Search in Hex,” IEEE Transactions on Computational Intelligence and AI in Games, vol. 2, no. 4, pp. 251–258, 2010.
• 17. D. Robles, P. Rohlfshagen, and S. M. Lucas, “Learning Non-Random Moves for Playing Othello: Improving Monte Carlo Tree Search,” in 2011 IEEE Conference on Computational Intelligence and Games (CIG’11). IEEE, 2011, pp. 305–312.
• 18. F. Teytaud and O. Teytaud, “Creating an Upper-Confidence-Tree Program for Havannah,” in Advances in Computer Games. Springer, 2009, pp. 65–74.
• 19. M. Swiechowski, T. Tajmajer, and A. Janusz, “Improving Hearthstone AI by Combining MCTS and Supervised Learning Algorithms,” in 2018 IEEE Conference on Computational Intelligence and Games, CIG 2018, Maastricht, The Netherlands, August 14-17, 2018, 2018, pp. 445–452. [Online]. Available: https://doi.org/10.1109/CIG.2018.8490368
• 20. A. Janusz, T. Tajmajer, and M. Świechowski, “Helping AI to Play Hearthstone: AAIA’17 Data Mining Challenge,” in 2017 Federated Conference on Computer Science and Information Systems (FedCSIS). IEEE, 2017, pp. 121–125.
• 21. A. K. Hoover, J. Togelius, S. Lee, and F. de Mesentier Silva, “The Many AI Challenges of Hearthstone,” KI-Künstliche Intelligenz, vol. 34, no. 1, pp. 33–43, 2020.
• 22. M. Świechowski, K. Godlewski, B. Sawicki, and J. Mańdziuk, “Monte Carlo Tree Search: A Review of Recent Modifications and Applications,” 2021, submitted to Springer-Nature AI Reviews Journal. [Online]. Available: https://arxiv.org/abs/2103.04931
• 23. L. Kocsis and C. Szepesvári, “Bandit Based Monte-Carlo Planning,” in Proceedings of the 17th European conference on Machine Learning, ser. ECML’06. Berlin, Heidelberg: Springer-Verlag, 2006, pp. 282–293.
• 24. S. Gelly and Y. Wang, “Exploration Exploitation in Go: UCT for Monte-Carlo Go,” in NIPS: Neural Information Processing Systems Conference On-line trading of Exploration and Exploitation Workshop, Canada, Dec. 2006. [Online]. Available: https://hal.archives-ouvertes.fr/hal-00115330
• 25. J. R. Long, N. R. Sturtevant, M. Buro, and T. Furtak, “Understanding the Success of Perfect Information Monte Carlo Sampling in Game Tree Search.” in AAAI, 2010.
• 26. P. I. Cowling, E. J. Powley, and D. Whitehouse, “Information Set Monte Carlo Tree Search,” IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, no. 2, pp. 120–143, 2012.
• 27. I. Frank and D. Basin, “Search in games with incomplete information: A case study using bridge card play,” Artificial Intelligence, vol. 100, no. 1-2, pp. 87–123, 1998.
• 28. M. J. Ponsen, G. Gerritsen, and G. Chaslot, “Integrating Opponent Models with Monte-Carlo Tree Search in Poker.” in Interactive Decision Theory and Game Theory, 2010.
• 29. A. Kishimoto and J. Schaeffer, “Transposition Table Driven Work Scheduling in Distributed Game-Tree Search,” in Proceedings of the 15th Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence, ser. AI ’02. London, UK, UK: Springer-Verlag, 2002, pp. 56–68.
• 30. J. Schaeffer, “The history heuristic and alpha-beta search enhancements in practice,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, no. 11, pp. 1203–1212, 1989.
• 31. A. Janusz, T. Tajmajer, M. Świechowski, Ł. Grad, J. Puczniewski, and D. Ślęzak, “Toward an Intelligent HS Deck Advisor: Lessons Learned from AAIA’18 Data Mining Competition,” in 2018 Federated Conference on Computer Science and Information Systems (FedCSIS). IEEE, 2018, pp. 189–192.
• 32. D. Taralla, “Learning Artificial Intelligence in Large-scale Video Games: A First Case Study with Hearthstone: Heroes of Warcraft,” Ph.D. dissertation, Université de Liège, Liège, Belgique, 2015.

Uwagi

1. Track 1: Artificial Intelligence in Applications

2. Session: 15th International Symposium Advances in Artificial Intelligence and Applications