Training Neural Networks to Play Ultimate Tic-Tac-Toe Using Evolutionary Algorithms: An Exploration of Task-Agnostic EA and MLP Integration

This project was released by stefanciutac on GitHub on June 13, 2026 (link: https://github.com/stefanciutac/evoNN_UTTT). Its core is combining task-agnostic Evolutionary Algorithms (EA) with Multi-Layer Perceptrons (MLP) to train AI to master Ultimate Tic-Tac-Toe, a complex strategy game. The project demonstrates the unique application of evolutionary computation in the field of reinforcement learning, providing new ideas for game AI development.

Ultimate Tic-Tac-Toe is an advanced version of the classic Tic-Tac-Toe, featuring a 3×3 large grid nested with small boards. Players need to occupy three cells on the large board to win. Each move restricts the opponent's next move to a specific small board, creating complex chain reactions that make exhaustive search infeasible, requiring deep strategic understanding.

1. Task-Agnostic EA: Simulates natural selection. It initializes a population, evaluates fitness through battles, selects excellent individuals for crossover and mutation, and iteratively improves performance. The framework can be migrated to various decision-making tasks. 2. MLP Selection: Takes the board state as input and outputs scores/probabilities for legal moves. Its structure is simple and stable, and the evolution process can autonomously discover useful connections without being constrained by spatial priors.

The core of training is fitness evaluation, which collects win-loss data (combining indicators like win rate and draw rate) through neural networks battling each other. Excellent-performing individuals produce offspring via crossover (combining parent weights) and mutation (random perturbation of weights). The population search strategy avoids local optima and explores innovative strategies.

Highlights: Task-agnostic design enhances versatility; self-play eliminates the need for human game records. Challenges: Efficient encoding of board states, computational cost of large numbers of games, maintaining population diversity (to avoid premature convergence), and designing fitness functions that distinguish between "strong draws" and "weak draws".

Insights: EA is an effective alternative to RL (suitable for scenarios where gradients are hard to compute), and task-agnostic design enhances versatility. Expansion: Can be applied to other board/real-time strategy games and robot control, providing researchers with an introductory case for neuroevolution and game developers with a solution for challenging AI opponents.

The project proves that pure evolutionary methods can achieve good results in complex strategy games, demonstrating the revival trend of neuroevolution. With the popularization of computing resources and algorithm improvements, more neuroevolution applications are expected. This project is a valuable resource worth in-depth study for AI, game, or evolutionary computing enthusiasts.