Published on: 2024-03-17
Description: Building a Tic-Tac-Toe AI with Monte Carlo Tree Search in Rust
Written by: Fadi Atieh
#rust
In the world of artificial intelligence and game development, creating an efficient and intelligent agent is both a challenge and a rewarding endeavor. Our project aimed to build a Tic-Tac-Toe game agent using the Monte Carlo Tree Search (MCTS) algorithm, implemented in Rust. This blog post narrates the journey of crafting this project, highlighting key insights and learnings along the way.
This project involved creating a Tic-Tac-Toe game agent that employs the MCTS algorithm for decision-making. The primary goals were to deepen our understanding of Rust and gain practical experience with the MCTS algorithm. The game allows users to play against the AI through a simple command-line interface (CLI), with the AI using the MCTS to decide its moves.
The journey began with setting up the project structure and implementing a rudimentary skeleton for the CLI. This initial phase was crucial in defining the basic components of the game, such as the board and game state, and setting up a user-friendly interface for interaction.
A significant milestone was the implementation of the get_played function, which enabled the game to simulate moves without altering the actual game state. This functionality was pivotal for testing potential moves without committing to them, a feature central to the MCTS algorithm.
/// Returns a copy of the game state after the move (row_index, col_index) has been played
pub fn get_played(&self, row_index: usize, col_index: usize) -> Result<Self, GamePlayError> {
let mut cloned_game = (*self).clone();
cloned_game.play(row_index, col_index)?;
Ok(cloned_game)
}
The heart of the project was the implementation of the MCTS algorithm. This involved several key steps:
Node Representation: We defined a tree node structure that represents game states, including the number of visits and wins.
Node Selection: Using the Upper Confidence Bound (UCB) policy, we navigated through the tree to select the most promising nodes.
Node Expansion: For each selected node, we expanded the tree by adding possible child nodes representing future game states.
Simulation: Random simulations were executed from new nodes to estimate the potential outcomes of moves starting from that node.
Backpropagation: Results from simulations were used to update the statistics of nodes, improving decision-making in subsequent iterations.
fn uct(parent_visits: f64, child_wins: f64, child_visits: f64) -> f64 {
let win_rate = child_wins / child_visits;
win_rate + (2.0 as f64).sqrt() * (parent_visits.ln() / child_visits).sqrt()
}
Throughout the development process, we iteratively refined and optimized the MCTS implementation. This involved reshuffling method orders for clarity, removing unused variables, and ensuring efficient memory management. The introduction of randomness via the rand crate was a key enhancement, allowing for more diverse simulations.
As the project neared completion, we focused on polishing the CLI and ensuring comprehensive documentation. The README file was finalized to provide clear instructions and insights into the project’s workings and the MCTS algorithm’s intricacies.
This project is an implementation of a tic-tac-toe game agent that uses Monte Carlo Tree Search (MCTS) for decision-making...
Developing a Tic-Tac-Toe AI using MCTS in Rust was a transformative learning experience. It challenged us to apply theoretical concepts in a practical setting, leading to a deeper understanding of both Rust and AI algorithms. The iterative nature of the project highlighted the importance of robust testing and documentation, ensuring a reliable and user-friendly final product. Through this journey, we not only created a competent game agent but also laid a strong foundation for future explorations in AI and Rust development.
For those interested in delving deeper, the GitHub repository contains the complete code and documentation to start your journey with MCTS in Rust.