Research Repository

Monte Carlo Tree Search: Long-term versus short-term planning

Perez, D and Rohlfshagen, P and Lucas, SM (2012) Monte Carlo Tree Search: Long-term versus short-term planning. In: UNSPECIFIED, ? - ?.

Full text not available from this repository.


In this paper we investigate the use of Monte Carlo Tree Search (MCTS) on the Physical Travelling Salesman Problem (PTSP), a real-time game where the player navigates a ship across a map full of obstacles in order to visit a series of waypoints as quickly as possible. In particular, we assess the algorithm's ability to plan ahead and subsequently solve the two major constituents of the PTSP: the order of waypoints (long-term planning) and driving the ship (short-term planning). We show that MCTS can provide better results when these problems are treated separately: the optimal order of cities is found using Branch & Bound and the ship is navigated to collect the waypoints using MCTS. We also demonstrate that the physics of the PTSP game impose a challenge regarding the optimal order of cities and propose a solution that obtains better results than following the TSP route of minimum Euclidean distance. © 2012 IEEE.

Item Type: Conference or Workshop Item (Paper)
Additional Information: Published proceedings: 2012 IEEE Conference on Computational Intelligence and Games, CIG 2012
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Jim Jamieson
Date Deposited: 19 Oct 2012 22:58
Last Modified: 17 Aug 2017 18:07

Actions (login required)

View Item View Item