Solving TicTacToe using Monte Carlo Tree Search or Minimax optimized with alpha beta pruning

Work in Progress

Overview

This project is an implementation of the classic Tic Tac Toe game, showcasing the power of AI through the Monte Carlo Tree Search (MCTS) and Minimax algorithm with Alpha-Beta pruning. This project demonstrates efficient decision-making and strategic gameplay, offering a formidable AI opponent.

The project is built for Android using Jetpack Compose, ensuring a modern, declarative UI framework for a smooth and interactive gaming experience.

Branches

• The Minimax implementation can be found in the minimax branch.

• The MCTS implementation can be found in the mcts branch.

Algorithms

Minimax with Alpha-Beta Pruning

The AI evaluates all possible moves to determine the best outcome, pruning unnecessary branches to improve efficiency.

• Minimax: Explores all possible game states to choose the optimal move.

• Alpha-Beta Pruning: Reduces the number of nodes evaluated in the Minimax tree, enhancing performance.

Images

Screenshots

Video