Skip to main content
SpringerLink
Log in
Book cover

Workshop on Computer Games

CGW 2014: Computer Games pp 45–63Cite as

Monte-Carlo Tree Search and Minimax Hybrids with Heuristic Evaluation Functions

  • Conference paper

Part of the book series: Communications in Computer and Information Science ((CCIS,volume 504))

Abstract

Monte-Carlo Tree Search (MCTS) has been found to play suboptimally in some tactical domains due to its highly selective search, focusing only on the most promising moves. In order to combine the strategic strength of MCTS and the tactical strength of minimax, MCTS-minimax hybrids have been introduced, embedding shallow minimax searches into the MCTS framework. Their results have been promising even without making use of domain knowledge such as heuristic evaluation functions. This paper continues this line of research for the case where evaluation functions are available. Three different approaches are considered, employing minimax with an evaluation function in the rollout phase of MCTS, as a replacement for the rollout phase, and as a node prior to bias move selection. The latter two approaches are newly proposed. The MCTS-minimax hybrids are tested and compared to their counterparts using evaluation functions without minimax in the domains of Othello, Breakthrough, and Catch the Lion. Results showed that introducing minimax search is effective for heuristic node priors in Othello and Catch the Lion. The MCTS-minimax hybrids are also found to work well in combination with each other. For their basic implementation in this investigative study, the effective branching factor of a domain is identified as a limiting factor of the hybrid’s performance.

This is a preview of subscription content, log in via an institution.

Chapter
USD   29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD   39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD   54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Learn about institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Auer, P., Cesa-Bianchi, N., Fischer, P.: Finite-Time Analysis of the Multiarmed Bandit Problem. Machine Learning 47(2-3), 235–256 (2002)

    Article  MATH  Google Scholar 

  2. Baier, H., Winands, M.H.M.: Monte-Carlo Tree Search and Minimax Hybrids. In: 2013 IEEE Conference on Computational Intelligence and Games, CIG 2013, pp. 129–136 (2013)

    Google Scholar 

  3. Bouzy, B.: Associating Domain-Dependent Knowledge and Monte Carlo Approaches within a Go Program. Information Sciences 175(4), 247–257 (2005)

    Article  Google Scholar 

  4. Browne, C., Powley, E.J., 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 Transactions on Computational Intelligence and AI in Games 4(1), 1–43 (2012)

    Article  Google Scholar 

  5. Chaslot, G.M.J.B., Winands, M.H.M., van den Herik, H.J., Uiterwijk, J.W.H.M., Bouzy, B.: Progressive Strategies for Monte-Carlo Tree Search. New Mathematics and Natural Computation 4(3), 343–357 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  6. Clune, J.E.: Heuristic Evaluation Functions for General Game Playing. Ph.D. thesis, University of California, Los Angeles, USA (2008)

    Google Scholar 

  7. Coulom, R.: Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. In: van den Herik, H.J., Ciancarini, P., Donkers, H.H.L.M(J.) (eds.) CG 2006. LNCS, vol. 4630, pp. 72–83. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  8. Finnsson, H., Björnsson, Y.: Game-Tree Properties and MCTS Performance. In: IJCAI 2011 Workshop on General Intelligence in Game Playing Agents (GIGA 2011), pp. 23–30 (2011)

    Google Scholar 

  9. Gelly, S., Silver, D.: Combining Online and Offline Knowledge in UCT. In: Ghahramani, Z. (ed.) 24th International Conference on Machine Learning, ICML 2007. ACM International Conference Proceeding Series, vol. 227, pp. 273–280 (2007)

    Google Scholar 

  10. Gelly, S., Wang, Y., Munos, R., Teytaud, O.: Modification of UCT with Patterns in Monte-Carlo Go. Tech. rep., HAL - CCSd - CNRS, France (2006)

    Google Scholar 

  11. van den Herik, H.J., Xu, X., Ma, Z., Winands, M.H.M. (eds.): CG 2008. LNCS, vol. 5131. Springer, Heidelberg (2008)

    MATH  Google Scholar 

  12. Knuth, D.E., Moore, R.W.: An Analysis of Alpha-Beta Pruning. Artificial Intelligence 6(4), 293–326 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  13. Kocsis, L., Szepesvári, C.: Bandit Based Monte-Carlo Planning. In: Fürnkranz, J., Scheffer, T., Spiliopoulou, M. (eds.) ECML 2006. LNCS (LNAI), vol. 4212, pp. 282–293. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  14. Lanctot, M., Winands, M.H.M., Pepels, T., Sturtevant, N.R.: Monte Carlo Tree Search with Heuristic Evaluations using Implicit Minimax Backups. In: 2014 IEEE Conference on Computational Intelligence and Games, CIG 2014, pp. 341–348 (2014)

    Google Scholar 

  15. Lorentz, R.J.: Amazons Discover Monte-Carlo. In: van den Herik (ed.) [11], pp. 13–24

    Google Scholar 

  16. Lorentz, R., Horey, T.: Programming breakthrough. In: van den Herik, H.J., Iida, H., Plaat, A. (eds.) CG 2013. LNCS, vol. 8427, pp. 49–59. Springer, Heidelberg (2014)

    Google Scholar 

  17. Lorentz, R.J.: Experiments with Monte-Carlo Tree Search in the Game of Havannah. ICGA Journal 34(3), 140–149 (2011)

    MathSciNet  Google Scholar 

  18. Nijssen, J(P.) A.M., Winands, M.H.M.: Playout Search for Monte-Carlo Tree Search in Multi-player Games. In: van den Herik, H.J., Plaat, A. (eds.) ACG 2011. LNCS, vol. 7168, pp. 72–83. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  19. Ramanujan, R., Sabharwal, A., Selman, B.: On Adversarial Search Spaces and Sampling-Based Planning. In: Brafman, R.I., Geffner, H., Hoffmann, J., Kautz, H.A. (eds.) 20th International Conference on Automated Planning and Scheduling, ICAPS 2010, pp. 242–245. AAAI (2010)

    Google Scholar 

  20. Ramanujan, R., Sabharwal, A., Selman, B.: Understanding Sampling Style Adversarial Search Methods. In: Grünwald, P., Spirtes, P. (eds.) 26th Conference on Uncertainty in Artificial Intelligence, UAI 2010, pp. 474–483 (2010)

    Google Scholar 

  21. Ramanujan, R., Sabharwal, A., Selman, B.: On the Behavior of UCT in Synthetic Search Spaces. In: ICAPS 2011 Workshop on Monte-Carlo Tree Search: Theory and Applications (2011)

    Google Scholar 

  22. Ramanujan, R., Selman, B.: Trade-Offs in Sampling-Based Adversarial Planning. In: Bacchus, F., Domshlak, C., Edelkamp, S., Helmert, M. (eds.) 21st International Conference on Automated Planning and Scheduling, ICAPS 2011. AAAI (2011)

    Google Scholar 

  23. Sato, Y., Takahashi, D., Grimbergen, R.: A Shogi Program Based on Monte-Carlo Tree Search. ICGA Journal 33(2), 80–92 (2010)

    Google Scholar 

  24. Silver, D., Tesauro, G.: Monte-Carlo Simulation Balancing. In: Danyluk, A.P., Bottou, L., Littman, M.L. (eds.) 26th Annual International Conference on Machine Learning, ICML 2009. ACM International Conference Proceeding Series, vol. 382, pp. 945–952. ACM (2009)

    Google Scholar 

  25. Sturtevant, N.R.: An Analysis of UCT in Multi-Player Games. ICGA Journal 31(4), 195–208 (2008)

    Google Scholar 

  26. Winands, M.H.M., Björnsson, Y., Saito, J.-T.: Monte Carlo Tree Search in Lines of Action. IEEE Transactions on Computational Intelligence and AI in Games 2(4), 239–250 (2010)

    Article  Google Scholar 

  27. Winands, M.H.M., Björnsson, Y.: Alpha-Beta-based Play-outs in Monte-Carlo Tree Search. In: Cho, S.-B., Lucas, S.M., Hingston, P. (eds.) 2011 IEEE Conference on Computational Intelligence and Games, CIG 2011, pp. 110–117. IEEE (2011)

    Google Scholar 

  28. Winands, M.H.M., Björnsson, Y., Saito, J.T.: Monte-Carlo Tree Search Solver. In: van den Herik, et al. (eds.) [11], pp. 25–36

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Games and AI Group, Department of Knowledge Engineering Faculty of Humanities and Sciences, Maastricht University, Maastricht, The Netherlands

    Hendrik Baier & Mark H. M. Winands

Authors
  1. Hendrik Baier
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mark H. M. Winands
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Université Paris-Dauphine, Paris, France

    Tristan Cazenave

  2. Games and AI Group, Department of Knowledge Engineering, Faculty of Humanities and Sciences, Maastricht University, Maastricht, The Netherlands

    Mark H. M. Winands

  3. School of Computer Science, Reykjavik University, Iceland

    Yngvi Björnsson

Rights and permissions

Reprints and permissions

Copyright information

© 2014 Springer International Publishing Switzerland

About this paper

Cite this paper

Baier, H., Winands, M.H.M. (2014). Monte-Carlo Tree Search and Minimax Hybrids with Heuristic Evaluation Functions. In: Cazenave, T., Winands, M.H.M., Björnsson, Y. (eds) Computer Games. CGW 2014. Communications in Computer and Information Science, vol 504. Springer, Cham. https://doi.org/10.1007/978-3-319-14923-3_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-14923-3_4

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-14922-6

  • Online ISBN: 978-3-319-14923-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation