Tricolor: Computational Analysis and AI Exploration of an Early Hexagonal Board Game

Details

Supervisors

Piette, Eric ; Rougetet, Lisa

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] en sciences informatiques, à finalité spécialisée

Abstract

enTricolor is a combinatorial board game invented in 1930 by the Belgian mathematician Maurice Kraitchik. Notable for its early use of a hexagonal tiling, its stack-based piece mechanics, and its capture rules influenced by tile colors, the game constitutes an original object of study at the intersection of the history of mathematics, artificial intelligence, and computational game analysis. Despite its historical interest, Tricolor has not previously been the subject of a systematic computational study. This thesis provides a first computational analysis of Tricolor. The rules of the game are formalized from historical sources and adapted into a precise model suitable for automated simulation and AI-based experimentation. An efficient game engine is implemented in C++, using compact representations of states and actions in order to support fast move generation, efficient state copying, and large-scale simulations. Using this framework, the thesis studies several quantitative properties of the game. Sim- ulations between Random Agents are used to estimate average game duration, branching factor, game tree complexity, state space complexity, player balance, and several dynamic gameplay metrics such as decisiveness, stability, and drama. The results show that Tricolor has a large search space, relatively long games, and unstable tactical dynamics, making it a non-trivial game from an artificial intelligence perspective. The thesis then identifies several strategic principles specific to Tricolor, including material control, positional power, stack concentration, and forced tactical sequences. These observations are used to design a heuristic evaluation function. Two classical game-playing agents are implemented and compared: an Alpha-Beta agent guided by this heuristic and a Monte Carlo Tree Search agent based on random simulations. Experimental results show that both agents strongly outperform random play, but that the Alpha-Beta agent clearly dominates the basic MCTS agent under the tested conditions. This difference is explained by the high branching factor, long game duration, and delayed tactical consequences created by stacking and forced moves. Beyond agent performance, this work provides a computational tool for the future study of Tricolor. The developed framework can support artificial intelligence researchers, historians of games, mathematicians, and cultural heritage specialists in exploring the strategic properties of the game, testing historical interpretations, generating represen- tative games, and comparing different styles of play. More broadly, this thesis illustrates how computational methods and artificial intelligence can contribute not only to playing historical games, but also to understanding, preserving, and studying them as mathematical and cultural objects.