Python Agent in Ludii
Izaias Saturnino de Lima Neto, Marco Antônio Athayde De Aguiar Vieira, Anderson Rocha Tavares · 2024
Read Python Agent in Ludii by Izaias Saturnino de Lima Neto, Marco Antônio Athayde De Aguiar Vieira, Anderson Rocha Tavares (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-14372.txt.
Introduction
Ludii is a system that can play and describe a large library of board games, but writing game playing programs for it means writing Java. Izaias Saturnino de Lima Neto and two co-authors built Python interfaces so researchers can code Ludii agents in Python instead, opening the door to Python's machine learning libraries. They implemented the bridge twice, once with a library called jpy and once with Py4J, and set out to learn which one runs faster.
They benchmarked both bridges with two classic game playing methods, minimax and Monte Carlo tree search, across several games that differ in depth and branching. Models fitted to the timings suggest jpy is the faster bridge, though a native Java agent still beats both. Tutorials and code repositories accompany the work so others can reproduce the tests.
Catalog record
| CREATOR | Izaias Saturnino de Lima Neto, Marco Antônio Athayde De Aguiar Vieira, Anderson Rocha Tavares |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-14372
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Python Agent in Ludii Izaias Saturnino de Lima Neto, Marco Antônio Athayde De Aguiar Vieira, Anderson Rocha Tavares Abstract Ludii is a Java general game system with a considerable number of board games, with an API for developing new agents and a game description language to create new games. To improve versatility and ease development, we provide Python interfaces for agent programming. This allows the use of Python modules to implement general game playing agents. As a means of enabling Python for creating Ludii agents, the interfaces are implemented using different Java libraries: jpy and Py4J. The main goal of this work is to determine which version is faster. To do so, we conducted a performance analysis of two different GGP algorithms, Minimax adapted to GGP and MCTS. The analysis was performed across several combinatorial games with varying depth, branching factor, and ply time. For reproducibility, we provide tutorials and repositories. Our analysis includes predictive models using regression, which suggest that jpy is faster than Py4J, however slower than a native Java Ludii agent, as expected. 1 Introduction Ludii is a comprehensive game platform built to play, evaluate, and create various types of games ( Piette et al. 2020 ). It is implemented in Java, offering an application programming interface (API) for agent development 1 1 1 Ludii API documentation: https://ludiitutorials.readthedocs.io/en/latest/basic_ai_api.html and a game description language for game creation 2 2 2 Ludii language reference: https://www.ludii.games/downloads/LudiiLanguageReference.pdf . Interoperability between languages is beneficial in Ludii. For example, Python has numerous libraries for data analysis and machine learning. However, the overhead of the Python-Java communication can be considerable. Thus, the main goal of this work is to evaluate two different Python-Java communication methods: jpy 3 3 3 Jpy Git repository: https://github.com/jpy-consortium/jpy and Py4J 4 4 4 Py4J Documentation: https://www.py4j.org/contents.html . The Python-Java bridges were evaluated by assessing the execution performance of a general game playing (GGP) implementation of the Minimax algorithm with alpha-beta pruning ( Knuth and Moore 1975 ), along with Upper Confidence Bound for Trees (UCT) ( Kocsis and Szepesvari 2006 ), a widely used variant of Monte Carlo Tree Search (MCTS). The selected games for this evaluation are combinatorial, defined as deterministic, two-player, zero-sum games with complete information. Different performance metrics were employed for each algorithm: the number of expanded states for Minimax and the number of playouts for UCT. The evaluation was conducted across 30 games with varying depth, ply time, and branching factor. The data collected from this analysis was used to develop predictive models. Consequently, the jpy agent was found to be faster than the Py4J agent but slower than the native Java agent, as anticipated. Tutorials and repositories for the jpy 5 5 5 Jpy agents implementations: https://github.com/izaias-saturnino/jpy-ludii-example and Py4J 6 6 6 Py4J agents implementations: https://github.com/izaias-saturnino/Py4j-ludii-example agents implementations are publicly available. The report is structured as follows: Section 2 explains the concepts and tools used as basis for this report, briefly discusses how they function and how the Ludii agents are created. Section 3 explains how the libraries are evaluated, presents the evaluation results, and discusses them. Section 4 shows the regression analysis, which provides insights into the behavior of the algorithms given a game’s characteristics and can be used to predict the performance on new games. Finally, Section 5 gives a brief overview, along with the findings and their significance. 2 Background General game playing artificial intelligence refers to a program capable of playing a wide variety of games. As explained by Genesereth et al. 2005 and further emphasized by Vieira et al. 2023 , these algorithms cannot be tailored for specific games, since they receive a game description in some representation at runtime and must use this description to play the game effectively. Several algorithms for general game playing AI exist, implementing different approaches to the problem. This report uses common and simple algorithms for the purposes of performance evaluation, which are further discussed in Sections 2.1 and 2.2 . 2.1 Monte Carlo Tree Search As the name suggests, Monte Carlo Tree Search (MCTS) is a tree search algorithm. There are several variants of this algorithm ( Browne et al. 2012 ). MCTS is an iterative algorithm with four steps in each iteration: selection, expansion, simulation, and backpropagation. The selection step chooses the leaf node on the partially-built game tree with the highest evaluation, where this evaluation is usually a function of the number of node visits and the reward associated with it. The next step is expansion, where a child of the selected leaf node is added to the tree. In the simulation step, a random game is played from the added node and backpropagation uses the result obtained on the simulation to update the number of visits and reward associated with each node traversed in the tree. The intuition is that the selection process directs the search towards more promising tree regions, building an unbalanced tree tending towards stronger moves. Since the algorithm uses statistics, it may return a suboptimal move with finite time. Even so, it tends to choose better moves given more time. This report uses the Upper Confidence bounds for Trees (UCT) variant of MCTS ( Kocsis and Szepesvari 2006 ), which is simple to implement and understand. During selection, UCT favors nodes with the highest average reward plus its upper confidence bound, related to how frequently the node was visited. Given infinite time, this variant is guaranteed to infer the path that maximizes the reward. 2.2 Minimax Minimax is another tree search algorithm. It differs significantly from UCT, since it calculates the value of the current state without the use of probability, requiring the construction of the entire subtree from the current state in a depth-first fashion. This allows the discovery of all terminal node values and the propagation of this information upwards. Since the tree grows exponentially, finding the true state value is unfeasible in most cases. A variation of this algorithm is the alpha–beta pruning, which reduces the number of evaluated states without losing optimality ( Knuth and Moore 1975 ). The Minimax algorithm variation used is an anytime variation with alpha-beta pruning and no heuristic. When the time limit is reached, the algorithm assumes that every non-evaluated state is a draw for the purpose of selecting a move. 2.3 Ludii Ludii is a general game system designed to play, evaluate, and create a wide range of games ( Piette et al. 2020 ). Ludii provides a game description language for creating games and an API for developing agents. A game description language serves as a formalism for specifying the rules, objects, and behavior of a game in a structured format. By using the game description language, a game can be expressed in a concise and formal manner, enabling its realization and evaluation within the Ludii system. This language abstracts away the complexities of a programming language, allowing a focus on the conceptual aspects of game design. Ludii’s API for developing agents provides a set of functions and protocols that enable the creation of intelligent agents capable of playing the games within Ludii. This API acts as a bridge between the game engine and third-party code, supporting agents with custom strategies and algorithms. 2.4