Logo PTI Logo FedCSIS

Proceedings of the 16th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 25

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

,

DOI: http://dx.doi.org/10.15439/2021F3

Citation: Proceedings of the 16th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 25, pages 101–110 ()

Full text

Abstract. 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.

References

  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.