Minibal: Balanced Game-Playing Without Opponent Modeling

Quentin Cohen-Solal; Tristan Cazenave

cs.AIMar 24, 2026

Minibal: Balanced Game-Playing Without Opponent Modeling

Authors: Quentin Cohen-Solal, Tristan Cazenave

Organizations: LAMSADE, Universit´e Paris-Dauphine, PSL, CNRS, Paris, France

Abstract

Recent advances in game AI, such as AlphaZero and Athénan, have achieved superhuman performance across a wide range of board games. While highly powerful, these agents are ill-suited for human-AI interaction, as they consistently overwhelm human players, offering little enjoyment and limited educational value. This paper addresses the problem of balanced play, in which an agent challenges its opponent without either dominating or conceding. We introduce Minibal (Minimize & Balance), a variant of Minimax specifically designed for balanced play. Building on this concept, we propose several modifications of the Unbounded Minimax algorithm explicitly aimed at discovering balanced strategies. Experiments conducted across seven board games demonstrate that one variant consistently achieves the most balanced play, with average outcomes close to perfect balance. These results establish Minibal as a promising foundation for designing AI agents that are both challenging and engaging, suitable for both entertainment and serious games.

Figures & tables

Symbols	Definition
$\mathrm{actions}\left(s\right)$	action set of the state $s$ for the current player
$\mathrm{root_{\text{–}}player}\left(s\right)$	true if the current player of the state $s$ is the player of the root of the current search tree
$\mathrm{\mathrm{balanced_{\text{–}}player}\left(s\right)}$	true if the current player of the state $s$ is the balanced player
$\mathrm{terminal\left(s\right)}$	true if $s$ is an end-game state
$a(s)$	state obtained after playing the action $a$ in the state $s$
$\mathrm{time}\left(\right)$	current time in seconds

Table 1: Index of symbols

Algorithm 1 Definition of the algorithms best_action( $s$ , $A$ ), which computes the a priori best action, and backup_resolution( $s$ ), which updates the resolution of $s$ from its children states (see Table 1 for the definitions of symbols).

Algorithm 2 Unbounded Minimax tree search algorithm with completion (i.e., including the calculation of the resolution values c and r of the states ; see Table 1 for symbol definitions and Algorithm 3 for best_action( $s$ ) and backup_resolution( $s$ ) definitions). Note: $T=(v,c,r,n)$ .

Algorithm 3 Definition of the following algorithms for Unbounded $\mathrm{Minibal_{n}}$ : best_action( $s$ , $A$ ), which computes the a priori best action using completion, and backup_resolution( $s$ ), which updates the resolution of $s$ based on its child states.

Algorithm 4 Definition of best_action( $s$ , $A$ ) for Unbounded $\mathrm{Minibal_{+}}$ , which computes the a priori best action.

Panel of Figure 1 — Figure 1: Average binary gain (left) and average scores (right) as a function of search time (in seconds) for $\mathrm{Minibal_{n}}$ (dotted green curve) , $\mathrm{Minibal_{+}}$ (dashed cyan curve) , and Unbounded Minimax (black line) across the studied games (in percentage).

Unbounded	gain	95% C.R	win	draw	loss	score	95% C.R
Minimax	92.68	0.91	94.77	3.14	2.09	0.59	0.016
$\mathrm{Minibal_{+}}$	-2.96	1.95	21.45	54.14	24.41	-0.024	0.011
$\mathrm{Minibal_{n}}$	-68.95	1.24	1.19	30.05	69.45	-0.21	0.011

Table 2: Average binary gains and win, draw, loss rates in percentage and scores at 20 seconds of search time per move across the seven games.

	evaluation
Chess	summed piece values
Xiangqi	summed piece values
International Draughts	summed piece values
Lines of Action	additive depth heuristic
Havannah	multiplicative depth heuristic
Outer-Open-Gomoku	multiplicative depth heuristic

Table 3: Terminal evaluation functions used for each game (see the Athénan paper for their definitions).

Panel of Figure 2 — Figure 2: Average binary gains as a function of search time (in seconds) for $\mathrm{Minibal_{n}}$ (dotted green curve) , $\mathrm{Minibal_{+}}$ (dashed cyan curve) , and Unbounded Minimax (black line) across the studied games (C.R.: confidence radius).

Panel of Figure 3 — Figure 3: Average scores as a function of search time (in seconds) for $\mathrm{Minibal_{n}}$ (dotted green curve) , $\mathrm{Minibal_{+}}$ (dashed cyan curve) , and Unbounded Minimax (black line) across all studied games.

Figure 4: Average binary gain (left) and average scores (right) as a function of search time (in seconds) for $\mathrm{Minibal_{n}}$ (dotted green curve) , $\mathrm{Minibal_{+}}$ (dashed cyan curve) , and Unbounded Minimax (black line) across the studied games against MCTS (in percentage).

Unbounded	gain	95% C.R	win	draw	loss
$\mathrm{Minibal_{+}}$	2.16	1.89	27.16	47.84	25

Table 4: Average binary gains and win, draw, loss rates in percentage at 1 second of search time per move across the seven games.

Game-Playing Agents

Game-playing agents use search, learning, and reasoning to choose actions in games with strategic, uncertain, or changing environments.

See all 201 papers

RuleSmith: Multi-Agent LLMs for Automated Game Balancing
Feb 5, 2026Ziyao Zeng, Hao Wang, Chen Liu +11Multi-Agent System Optimization
Yale University, New Haven, CT, USA · Texas A&M University, College Station, TX, USA
Can AI Agents Learn Their Way to the Top? Evaluating Heuristic Learning in a Long-Running Game Agent Competition
Oct 8, 2026Kaisen Yang, Qingle Liu, Kejin Wang +24Game-Playing Agents Self-Improving Agents
Department of Computer Science and Technology, Tsinghua University
Nemobot Games: Crafting Strategic AI Gaming Agents for Interactive Learning with Large Language Models
Apr 23, 2026Chee Wei Tan, Yuchen Wang, Shangxin GuoGame-Playing Agents LLM Agents
Nanyang Technological University, Singapore, Nanyang Ave., Singapore · Nautilus Software Technologies Limited, Hong Kong.

Feb 5, 2026J/K move · Enter open · S save

RuleSmith: Multi-Agent LLMs for Automated Game Balancing

Ziyao Zeng, Hao Wang, Chen Liu, Youheng Yao+10

Yale University, New Haven, CT, USA · Texas A&M University, College Station, TX, USA

Multi-Agent System Optimization

Open paper AskPDF arXiv

Game balancing is a longstanding challenge requiring repeated playtesting, expert intuition, and extensive manual tuning. We introduce RuleSmith, a framework that couples multi-agent LLM self-play with surrogate-based optimization over a parameterized rule space. As a proof of concept, we build CivMini, a simplified civilization-style game with two asymmetric factions governed by 12 tunable parameters. LLM agents interpret textual rulebooks and game states to propose actions that are validated by the game engine, yielding noisy estimates of faction win rates. Our primary implementation uses Gaussian-process Bayesian optimization with Expected-Improvement-based adaptive sampling to allocate more evaluation games to promising candidates. RuleSmith consistently finds near-balanced configurations: three independent optimization runs reach near-even empirical win rates in independent 200- and 300-game evaluations, and additional experiments with NTBEA and TPE show that the same self-play interface supports different search components. Cross-model evaluations and small human studies provide preliminary evidence of transfer across player populations. RuleSmith produces interpretable numerical rule adjustments without task-specific policy training. Project and code: https://adonis-galaxy.github.io/RuleSmith-website/

Abstract

Game-Playing Agents

Explore similar work

RuleSmith: Multi-Agent LLMs for Automated Game Balancing

Can AI Agents Learn Their Way to the Top? Evaluating Heuristic Learning in a Long-Running Game Agent Competition

Nemobot Games: Crafting Strategic AI Gaming Agents for Interactive Learning with Large Language Models