Browsing by Subject "Monte Carlo Tree Search"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Computer Go and Monte Carlo Tree Search: Opening Book and Parallel Solutions
    (2016-05) Steinmetz, Erik
    This work examines two aspects of Monte Carlo Tree Search (MCTS), a recent invention in the field of artificial intelligence. We propose a method to guide a Monte Carlo Tree Search in the initial moves of the game of Go. Our method matches the current state of a Go board against clusters of board configurations that are derived from a large number of games played by experts. The main advantage of this method is that it does not require an exact match of the current board, and hence is effective for a longer sequence of moves compared to traditional opening books. We apply this method to two different open-source Go-playing programs. Our experiments show that this method, through its filtering or biasing the choice of a next move to a small subset of possible moves, improves play effectively in the initial moves of a game. We also conduct a study of the effectiveness of various kinds of parallelization of MCTS, and add our own parallel MCTS variant. This variant introduces the notion of using multiple algorithms in the root version of parallelization. The study is conducted across two different domains: Go and Hex. Our study uses a consistent measure of performance gains in terms of winning rates against a fixed opponent and uses enough trials to provide statistically significant results.
  • Thumbnail Image
    Item
    Stochastic Tree Search for Highly Coordinated Planning
    (2016-08) Kartal, Bilal
    Coordination plays a key role in efficiently solving multi-agent problems such as exploration of unknown environments, search and rescue, and surveillance. Planning in a highly coordinated fashion causes traditional search algorithms to perform poorly as it creates combinatorial search spaces that renders exploration versus exploitation dilemma challenging as well. Recently, there has been great improvement in stochastic planning in large search spaces with sampling based algorithms. One particular algorithm is Monte Carlo Tree Search (MCTS) which is an anytime stochastic planning algorithm. MCTS employs the well-established multi-armed bandit theory to solve optimization problems by asymmetrically sampling actions where it foresees the existence of an optimal solution. In this thesis, we propose new algorithms and heuristics in order to address several challenges arising due to highly coordinated planning in physical and abstract domains. Our algorithms improve scalability for search in large domains, provides data-driven evaluation functions to guide the search algorithm better, and enables finite search algorithms to produce infinite length solutions. In the first part of this thesis, we study two multi-robot planning problems that require high degree of coordination, patrolling and task allocation. The main challenge for these domains is the large search space. For patrolling, we propose a novel search technique, the Monte Carlo Tree Search with Useful Cycles, which can generate optimal cyclic patrol policies with theoretical convergence guarantees. For task allocation, we develop a parallelized MCTS based planner where branch and bound paradigm is integrated to the search algorithm for admissible pruning. In the second part of this thesis, we study two coordinated abstract planning problems within the field of procedural content generation, goal-driven computer narrative generation and Sokoban puzzle level creation. In these problems, virtual agents coordinate their actions to procedurally create stories and puzzles which have numerous application areas ranging from video games to education. We formulate both story generation and Sokoban puzzle generation as optimization problems and propose data-driven heuristic evaluation metrics for efficient coordinated solutions using MCTS.