A Monte Carlo Algorithm for Time-Constrained General Game Playing

Victor Scherer Putrich; Anderson Rocha Tavares; Felipe Meneguzzi

doi:10.1007/978-3-031-45368-7_7

A Monte Carlo Algorithm for Time-Constrained General Game Playing

Victor Scherer Putrich^*, Anderson Rocha Tavares, Felipe Meneguzzi

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Published conference contribution

Abstract

General Game Playing (GGP) is a challenging domain for AI agents, as it requires them to play diverse games without prior knowledge. In this paper, we develop a strategy to improve move suggestions in time-constrained GGP settings. This strategy consists of a hybrid version of UCT that combines Sequential Halving and, favoring information acquisition in the root node, rather than overspend time on the most rewarding actions. Empirical evaluation using a GGP competition scheme from the Ludii framework shows that our strategy improves the average payoff over the entire competition set of games. Moreover, our agent makes better use of extended time budgets, when available.

Original language	English
Title of host publication	Intelligent Systems
Subtitle of host publication	12th Brazilian Conference, BRACIS 2023, Belo Horizonte, Brazil, September 25–29, 2023, Proceedings, Part I
Editors	Murilo C. Naldi, Reinaldo A. Bianchi
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	97-111
Number of pages	15
ISBN (Print)	9783031453670
DOIs	https://doi.org/10.1007/978-3-031-45368-7_7
Publication status	Published - 12 Oct 2023
Event	12th Brazilian Conference on Intelligent Systems, BRACIS 2023 - Belo Horizonte, Brazil Duration: 25 Sept 2023 → 29 Sept 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14195 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th Brazilian Conference on Intelligent Systems, BRACIS 2023
Country/Territory	Brazil
City	Belo Horizonte
Period	25/09/23 → 29/09/23

Keywords

General Game Playing
Monte Carlo
Regret

Access to Document

10.1007/978-3-031-45368-7_7Licence: Unspecified

Cite this

Putrich, V. S., Tavares, A. R., & Meneguzzi, F. (2023). A Monte Carlo Algorithm for Time-Constrained General Game Playing. In M. C. Naldi, & R. A. Bianchi (Eds.), Intelligent Systems : 12th Brazilian Conference, BRACIS 2023, Belo Horizonte, Brazil, September 25–29, 2023, Proceedings, Part I (pp. 97-111). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14195 LNAI). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-45368-7_7

A Monte Carlo Algorithm for Time-Constrained General Game Playing. / Putrich, Victor Scherer; Tavares, Anderson Rocha; Meneguzzi, Felipe.
Intelligent Systems : 12th Brazilian Conference, BRACIS 2023, Belo Horizonte, Brazil, September 25–29, 2023, Proceedings, Part I. ed. / Murilo C. Naldi; Reinaldo A. Bianchi. Springer Science and Business Media Deutschland GmbH, 2023. p. 97-111 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14195 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Published conference contribution

Putrich, VS, Tavares, AR & Meneguzzi, F 2023, A Monte Carlo Algorithm for Time-Constrained General Game Playing. in MC Naldi & RA Bianchi (eds), Intelligent Systems : 12th Brazilian Conference, BRACIS 2023, Belo Horizonte, Brazil, September 25–29, 2023, Proceedings, Part I. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14195 LNAI, Springer Science and Business Media Deutschland GmbH, pp. 97-111, 12th Brazilian Conference on Intelligent Systems, BRACIS 2023, Belo Horizonte, Brazil, 25/09/23. https://doi.org/10.1007/978-3-031-45368-7_7

Putrich VS, Tavares AR, Meneguzzi F. A Monte Carlo Algorithm for Time-Constrained General Game Playing. In Naldi MC, Bianchi RA, editors, Intelligent Systems : 12th Brazilian Conference, BRACIS 2023, Belo Horizonte, Brazil, September 25–29, 2023, Proceedings, Part I. Springer Science and Business Media Deutschland GmbH. 2023. p. 97-111. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-45368-7_7

Putrich, Victor Scherer ; Tavares, Anderson Rocha ; Meneguzzi, Felipe. / A Monte Carlo Algorithm for Time-Constrained General Game Playing. Intelligent Systems : 12th Brazilian Conference, BRACIS 2023, Belo Horizonte, Brazil, September 25–29, 2023, Proceedings, Part I. editor / Murilo C. Naldi ; Reinaldo A. Bianchi. Springer Science and Business Media Deutschland GmbH, 2023. pp. 97-111 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d74b737471e34e72b1d96255f84b6d2d,

title = "A Monte Carlo Algorithm for Time-Constrained General Game Playing",

abstract = "General Game Playing (GGP) is a challenging domain for AI agents, as it requires them to play diverse games without prior knowledge. In this paper, we develop a strategy to improve move suggestions in time-constrained GGP settings. This strategy consists of a hybrid version of UCT that combines Sequential Halving and, favoring information acquisition in the root node, rather than overspend time on the most rewarding actions. Empirical evaluation using a GGP competition scheme from the Ludii framework shows that our strategy improves the average payoff over the entire competition set of games. Moreover, our agent makes better use of extended time budgets, when available.",

keywords = "General Game Playing, Monte Carlo, Regret",

author = "Putrich, {Victor Scherer} and Tavares, {Anderson Rocha} and Felipe Meneguzzi",

year = "2023",

month = oct,

day = "12",

doi = "10.1007/978-3-031-45368-7_7",

language = "English",

isbn = "9783031453670",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "97--111",

editor = "Naldi, {Murilo C.} and Bianchi, {Reinaldo A.}",

booktitle = "Intelligent Systems",

address = "Germany",

note = "12th Brazilian Conference on Intelligent Systems, BRACIS 2023 ; Conference date: 25-09-2023 Through 29-09-2023",

}

TY - GEN

T1 - A Monte Carlo Algorithm for Time-Constrained General Game Playing

AU - Putrich, Victor Scherer

AU - Tavares, Anderson Rocha

AU - Meneguzzi, Felipe

PY - 2023/10/12

Y1 - 2023/10/12

N2 - General Game Playing (GGP) is a challenging domain for AI agents, as it requires them to play diverse games without prior knowledge. In this paper, we develop a strategy to improve move suggestions in time-constrained GGP settings. This strategy consists of a hybrid version of UCT that combines Sequential Halving and, favoring information acquisition in the root node, rather than overspend time on the most rewarding actions. Empirical evaluation using a GGP competition scheme from the Ludii framework shows that our strategy improves the average payoff over the entire competition set of games. Moreover, our agent makes better use of extended time budgets, when available.

AB - General Game Playing (GGP) is a challenging domain for AI agents, as it requires them to play diverse games without prior knowledge. In this paper, we develop a strategy to improve move suggestions in time-constrained GGP settings. This strategy consists of a hybrid version of UCT that combines Sequential Halving and, favoring information acquisition in the root node, rather than overspend time on the most rewarding actions. Empirical evaluation using a GGP competition scheme from the Ludii framework shows that our strategy improves the average payoff over the entire competition set of games. Moreover, our agent makes better use of extended time budgets, when available.

KW - General Game Playing

KW - Monte Carlo

KW - Regret

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

U2 - 10.1007/978-3-031-45368-7_7

DO - 10.1007/978-3-031-45368-7_7

M3 - Published conference contribution

AN - SCOPUS:85175829371

SN - 9783031453670

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 97

EP - 111

BT - Intelligent Systems

A2 - Naldi, Murilo C.

A2 - Bianchi, Reinaldo A.

PB - Springer Science and Business Media Deutschland GmbH

T2 - 12th Brazilian Conference on Intelligent Systems, BRACIS 2023

Y2 - 25 September 2023 through 29 September 2023

ER -