Self-adaptive MCTS for General Video Game Playing

Chiara F. SIRONI; Jialin LIU; Diego PEREZ-LIEBANA; Raluca D. GAINA; Ivan BRAVI; Simon M. LUCAS; Mark H. M. WINANDS

doi:10.1007/978-3-319-77538-8_25

Self-adaptive MCTS for General Video Game Playing

Chiara F. SIRONI^*, Jialin LIU, Diego PEREZ-LIEBANA, Raluca D. GAINA, Ivan BRAVI, Simon M. LUCAS, Mark H. M. WINANDS

^*Corresponding author for this work

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Referred Conference Paper › peer-review

17 Citations (Scopus)

Abstract

Monte-Carlo Tree Search (MCTS) has shown particular success in General Game Playing (GGP) and General Video Game Playing (GVGP) and many enhancements and variants have been developed. Recently, an on-line adaptive parameter tuning mechanism for MCTS agents has been proposed that almost achieves the same performance as off-line tuning in GGP.

In this paper we apply the same approach to GVGP and use the popular General Video Game AI (GVGAI) framework, in which the time allowed to make a decision is only 40 ms. We design three Self-Adaptive MCTS (SA-MCTS) agents that optimize on-line the parameters of a standard non-Self-Adaptive MCTS agent of GVGAI. The three agents select the parameter values using Naïve Monte-Carlo, an Evolutionary Algorithm and an N-Tuple Bandit Evolutionary Algorithm respectively, and are tested on 20 single-player games of GVGAI.

The SA-MCTS agents achieve more robust results on the tested games. With the same time setting, they perform similarly to the baseline standard MCTS agent in the games for which the baseline agent performs well, and significantly improve the win rate in the games for which the baseline agent performs poorly. As validation, we also test the performance of non-Self-Adaptive MCTS instances that use the most sampled parameter settings during the on-line tuning of each of the three SA-MCTS agents for each game. Results show that these parameter settings improve the win rate on the games Wait for Breakfast and Escape by 4 times and 150 times, respectively.

Original language	English
Title of host publication	Applications of Evolutionary Computation : 21st International Conference, EvoApplications 2018, Proceedings
Editors	Kevin SIM, Paul KAUFMANN
Publisher	Springer-Verlag Italia Srl
Pages	358-375
Number of pages	18
ISBN (Print)	9783319775371
DOIs	https://doi.org/10.1007/978-3-319-77538-8_25
Publication status	Published - 2018
Externally published	Yes
Event	21st International Conference on Applications of Evolutionary Computation, EvoApplications 2018 - Parma, Italy Duration: 4 Apr 2018 → 6 Apr 2018

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	10784
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Name	Theoretical Computer Science and General Issues
Publisher	Springer
ISSN (Print)	2512-2010
ISSN (Electronic)	2512-2029

Conference

Conference	21st International Conference on Applications of Evolutionary Computation, EvoApplications 2018
Country/Territory	Italy
City	Parma
Period	4/04/18 → 6/04/18

Bibliographical note

Publisher Copyright:
© Springer International Publishing AG, part of Springer Nature 2018.

Keywords

General video game playing
MCTS
On-line tuning
Robust game playing
Self-adaptive

Access to Document

10.1007/978-3-319-77538-8_25

Cite this

SIRONI, C. F., LIU, J., PEREZ-LIEBANA, D., GAINA, R. D., BRAVI, I., LUCAS, S. M., & WINANDS, M. H. M. (2018). Self-adaptive MCTS for General Video Game Playing. In K. SIM, & P. KAUFMANN (Eds.), Applications of Evolutionary Computation : 21st International Conference, EvoApplications 2018, Proceedings (pp. 358-375). (Lecture Notes in Computer Science; Vol. 10784), (Theoretical Computer Science and General Issues). Springer-Verlag Italia Srl. https://doi.org/10.1007/978-3-319-77538-8_25

SIRONI, Chiara F. ; LIU, Jialin ; PEREZ-LIEBANA, Diego et al. / Self-adaptive MCTS for General Video Game Playing. Applications of Evolutionary Computation : 21st International Conference, EvoApplications 2018, Proceedings. editor / Kevin SIM ; Paul KAUFMANN. Springer-Verlag Italia Srl, 2018. pp. 358-375 (Lecture Notes in Computer Science). (Theoretical Computer Science and General Issues).

@inproceedings{691537a315d040d28d4304315a43ab7a,

title = "Self-adaptive MCTS for General Video Game Playing",

abstract = "Monte-Carlo Tree Search (MCTS) has shown particular success in General Game Playing (GGP) and General Video Game Playing (GVGP) and many enhancements and variants have been developed. Recently, an on-line adaptive parameter tuning mechanism for MCTS agents has been proposed that almost achieves the same performance as off-line tuning in GGP. In this paper we apply the same approach to GVGP and use the popular General Video Game AI (GVGAI) framework, in which the time allowed to make a decision is only 40 ms. We design three Self-Adaptive MCTS (SA-MCTS) agents that optimize on-line the parameters of a standard non-Self-Adaptive MCTS agent of GVGAI. The three agents select the parameter values using Na{\"i}ve Monte-Carlo, an Evolutionary Algorithm and an N-Tuple Bandit Evolutionary Algorithm respectively, and are tested on 20 single-player games of GVGAI. The SA-MCTS agents achieve more robust results on the tested games. With the same time setting, they perform similarly to the baseline standard MCTS agent in the games for which the baseline agent performs well, and significantly improve the win rate in the games for which the baseline agent performs poorly. As validation, we also test the performance of non-Self-Adaptive MCTS instances that use the most sampled parameter settings during the on-line tuning of each of the three SA-MCTS agents for each game. Results show that these parameter settings improve the win rate on the games Wait for Breakfast and Escape by 4 times and 150 times, respectively.",

keywords = "General video game playing, MCTS, On-line tuning, Robust game playing, Self-adaptive",

author = "SIRONI, {Chiara F.} and Jialin LIU and Diego PEREZ-LIEBANA and GAINA, {Raluca D.} and Ivan BRAVI and LUCAS, {Simon M.} and WINANDS, {Mark H. M.}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 21st International Conference on Applications of Evolutionary Computation, EvoApplications 2018 ; Conference date: 04-04-2018 Through 06-04-2018",

year = "2018",

doi = "10.1007/978-3-319-77538-8_25",

language = "English",

isbn = "9783319775371",

series = "Lecture Notes in Computer Science",

publisher = "Springer-Verlag Italia Srl",

pages = "358--375",

editor = "Kevin SIM and Paul KAUFMANN",

booktitle = "Applications of Evolutionary Computation : 21st International Conference, EvoApplications 2018, Proceedings",

address = "Italy",

}

SIRONI, CF, LIU, J, PEREZ-LIEBANA, D, GAINA, RD, BRAVI, I, LUCAS, SM & WINANDS, MHM 2018, Self-adaptive MCTS for General Video Game Playing. in K SIM & P KAUFMANN (eds), Applications of Evolutionary Computation : 21st International Conference, EvoApplications 2018, Proceedings. Lecture Notes in Computer Science, vol. 10784, Theoretical Computer Science and General Issues, Springer-Verlag Italia Srl, pp. 358-375, 21st International Conference on Applications of Evolutionary Computation, EvoApplications 2018, Parma, Italy, 4/04/18. https://doi.org/10.1007/978-3-319-77538-8_25

Self-adaptive MCTS for General Video Game Playing. / SIRONI, Chiara F.; LIU, Jialin; PEREZ-LIEBANA, Diego et al.
Applications of Evolutionary Computation : 21st International Conference, EvoApplications 2018, Proceedings. ed. / Kevin SIM; Paul KAUFMANN. Springer-Verlag Italia Srl, 2018. p. 358-375 (Lecture Notes in Computer Science; Vol. 10784), (Theoretical Computer Science and General Issues).

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Referred Conference Paper › peer-review

TY - GEN

T1 - Self-adaptive MCTS for General Video Game Playing

AU - SIRONI, Chiara F.

AU - LIU, Jialin

AU - PEREZ-LIEBANA, Diego

AU - GAINA, Raluca D.

AU - BRAVI, Ivan

AU - LUCAS, Simon M.

AU - WINANDS, Mark H. M.

N1 - Publisher Copyright: © Springer International Publishing AG, part of Springer Nature 2018.

PY - 2018

Y1 - 2018

N2 - Monte-Carlo Tree Search (MCTS) has shown particular success in General Game Playing (GGP) and General Video Game Playing (GVGP) and many enhancements and variants have been developed. Recently, an on-line adaptive parameter tuning mechanism for MCTS agents has been proposed that almost achieves the same performance as off-line tuning in GGP. In this paper we apply the same approach to GVGP and use the popular General Video Game AI (GVGAI) framework, in which the time allowed to make a decision is only 40 ms. We design three Self-Adaptive MCTS (SA-MCTS) agents that optimize on-line the parameters of a standard non-Self-Adaptive MCTS agent of GVGAI. The three agents select the parameter values using Naïve Monte-Carlo, an Evolutionary Algorithm and an N-Tuple Bandit Evolutionary Algorithm respectively, and are tested on 20 single-player games of GVGAI. The SA-MCTS agents achieve more robust results on the tested games. With the same time setting, they perform similarly to the baseline standard MCTS agent in the games for which the baseline agent performs well, and significantly improve the win rate in the games for which the baseline agent performs poorly. As validation, we also test the performance of non-Self-Adaptive MCTS instances that use the most sampled parameter settings during the on-line tuning of each of the three SA-MCTS agents for each game. Results show that these parameter settings improve the win rate on the games Wait for Breakfast and Escape by 4 times and 150 times, respectively.

AB - Monte-Carlo Tree Search (MCTS) has shown particular success in General Game Playing (GGP) and General Video Game Playing (GVGP) and many enhancements and variants have been developed. Recently, an on-line adaptive parameter tuning mechanism for MCTS agents has been proposed that almost achieves the same performance as off-line tuning in GGP. In this paper we apply the same approach to GVGP and use the popular General Video Game AI (GVGAI) framework, in which the time allowed to make a decision is only 40 ms. We design three Self-Adaptive MCTS (SA-MCTS) agents that optimize on-line the parameters of a standard non-Self-Adaptive MCTS agent of GVGAI. The three agents select the parameter values using Naïve Monte-Carlo, an Evolutionary Algorithm and an N-Tuple Bandit Evolutionary Algorithm respectively, and are tested on 20 single-player games of GVGAI. The SA-MCTS agents achieve more robust results on the tested games. With the same time setting, they perform similarly to the baseline standard MCTS agent in the games for which the baseline agent performs well, and significantly improve the win rate in the games for which the baseline agent performs poorly. As validation, we also test the performance of non-Self-Adaptive MCTS instances that use the most sampled parameter settings during the on-line tuning of each of the three SA-MCTS agents for each game. Results show that these parameter settings improve the win rate on the games Wait for Breakfast and Escape by 4 times and 150 times, respectively.

KW - General video game playing

KW - MCTS

KW - On-line tuning

KW - Robust game playing

KW - Self-adaptive

UR - http://www.scopus.com/inward/record.url?scp=85044096813&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-77538-8_25

DO - 10.1007/978-3-319-77538-8_25

M3 - Conference paper (refereed)

AN - SCOPUS:85044096813

SN - 9783319775371

T3 - Lecture Notes in Computer Science

SP - 358

EP - 375

BT - Applications of Evolutionary Computation : 21st International Conference, EvoApplications 2018, Proceedings

A2 - SIM, Kevin

A2 - KAUFMANN, Paul

PB - Springer-Verlag Italia Srl

T2 - 21st International Conference on Applications of Evolutionary Computation, EvoApplications 2018

Y2 - 4 April 2018 through 6 April 2018

ER -

SIRONI CF, LIU J, PEREZ-LIEBANA D, GAINA RD, BRAVI I, LUCAS SM et al. Self-adaptive MCTS for General Video Game Playing. In SIM K, KAUFMANN P, editors, Applications of Evolutionary Computation : 21st International Conference, EvoApplications 2018, Proceedings. Springer-Verlag Italia Srl. 2018. p. 358-375. (Lecture Notes in Computer Science). (Theoretical Computer Science and General Issues). Epub 2018 Mar 8. doi: 10.1007/978-3-319-77538-8_25

Self-adaptive MCTS for General Video Game Playing

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this