Research Repository

Multiobjective Monte Carlo Tree Search for Real-Time Games

Perez, D and Mostaghim, S and Samothrakis, S and Lucas, SM (2015) 'Multiobjective Monte Carlo Tree Search for Real-Time Games.' IEEE Transactions on Computational Intelligence and AI in Games, 7 (4). 347 - 360. ISSN 1943-068X

[img]
Preview
Text
MOMCTS_TCIAIG2014.pdf - Accepted Version

Download (1MB) | Preview

Abstract

© 2015 IEEE. Multiobjective optimization has been traditionally a matter of study in domains like engineering or finance, with little impact on games research. However, action-decision based on multiobjective evaluation may be beneficial in order to obtain a high quality level of play. This paper presents a multiobjective Monte Carlo tree search algorithm for planning and control in real-time game domains, those where the time budget to decide the next move to make is close to 40 ms. A comparison is made between the proposed algorithm, a single-objective version of Monte Carlo tree search and a rolling horizon implementation of nondominated sorting evolutionary algorithm II (NSGA-II). Two different benchmarks are employed, deep sea treasure (DST) and the multiobjective physical traveling salesman problem (MO-PTSP). Using the same heuristics on each game, the analysis is focused on how well the algorithms explore the search space. Results show that the algorithm proposed outperforms NSGA-II. Additionally, it is also shown that the algorithm is able to converge to different optimal solutions or the optimal Pareto front (if achieved during search).

Item Type: Article
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: 04 Dec 2014 13:48
Last Modified: 23 Jan 2019 02:15
URI: http://repository.essex.ac.uk/id/eprint/11985

Actions (login required)

View Item View Item