Monte-Carlo Tree Search for Poly-Y

L. Wevers, Steven te Brinke

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

59 Downloads (Pure)

Abstract

Monte-Carlo tree search (MCTS) is a heuristic search algorithm that has recently been very successful in the games of Go and Hex. In this paper, we describe an MCTS player for the game of Poly-Y, which is a connection game similar to Hex. Our player won the CodeCup 2014 AI programming competition. Our player uses MCTS with the all-moves-as-first heuristic, and detects basic heuristic patterns to defend virtual connections in Poly-Y. In the CodeCup, we can only use 30s single-core computation time per game, whereas in Hex, 5 to 30 minutes of multi-core computation time is common. We improve the performance of our player in the early game with an opening book computed through self play. To assess the performance of our heuristics, we have performed a number of experiments.
Original languageUndefined
Title of host publicationProceedings of the 26th Benelux Conference on Artificial Intelligence, BNAIC 2014
Place of PublicationNijmegen, The Netherlands
PublisherRadboud Universiteit Nijmegen
Pages119-127
Number of pages8
Publication statusPublished - 6 Nov 2014
Event26th Benelux Conference on Artificial Intelligence, BNAIC 2014 - Radboud University Nijmegen, Nijmegen, Netherlands
Duration: 6 Nov 20147 Nov 2014
Conference number: 26

Publication series

NameBNAIC ... : proceedings of the ... Belgium/Netherlands Artificial Intelligence Conference
PublisherRadboud Universiteit Nijmegen
ISSN (Print)1568-7805

Conference

Conference26th Benelux Conference on Artificial Intelligence, BNAIC 2014
Abbreviated titleBNAIC
CountryNetherlands
CityNijmegen
Period6/11/147/11/14

Keywords

  • EWI-25558
  • IR-94138
  • METIS-309810
  • Monte-Carlo Tree Search
  • Artificial Intelligence

Cite this

Wevers, L., & te Brinke, S. (2014). Monte-Carlo Tree Search for Poly-Y. In Proceedings of the 26th Benelux Conference on Artificial Intelligence, BNAIC 2014 (pp. 119-127). (BNAIC ... : proceedings of the ... Belgium/Netherlands Artificial Intelligence Conference). Nijmegen, The Netherlands: Radboud Universiteit Nijmegen.