An implementation of tic-tac-toe in C, featuring an AI powered by the negamax algorithm, TD learning algorithm, and the Monte Carlo tree search (MCTS) algorithm.

If you want to play with negamax AI: Build the game:

$ make

and run:

$ ./ttt

If you want to play with TD learning AI: Train the state value table first, you could modify

• EPSILON_START EPSILON_END in train.c : $\epsilon$ in Epsilon-Greedy Algorithm and it would decay exponentially.
• NUM_ITERATION in train.c: nums of game iteration
• LEARNING_RATE, GAMMA in temporal_difference.h: $\alpha$, $\gamma$ in TD learning.

compile

$ make train

and run:

$./train

Build the game playing with TD agent, it would load the pretrained model from train:

$ make td

and run:

$ ./td

If you want to play with MCTS AI:
There are several hyperparameters you can modify:

• EXPLORATION_FACTOR in agents/mcts.h : The exploration parameter.
• ITERATIONS in agents/mcts.h : Number of simulations in MCTS.

Build the game:

$ make mcts

and run:

$ ./mcts

These program operate entirely in the terminal environment. Below is its appearance as it awaits your next move:

 1 |  ×
 2 |     ○
 3 |
---+----------
      A  B  C
>

To execute a move, enter [column][row]. For example:

> a3

Press Ctrl-C to exit.

The winner is determined by the first player who successfully places GOAL of their marks in a row, whether it is vertically, horizontally, or diagonally, regardless of the board size.

Using the following 4x4 board games, whose GOAL is 3, as examples:

 1 |  ×  ×
 2 |     ○  ×
 3 |     ○
 4 |     ○
---+------------
      A  B  C  D
>

The player "○" wins the game since he placed his marks in a row vertically (B2-B3-B4).

 1 |  ×  ×  ○
 2 |  ×  ○  
 3 |  ○  
 4 |     
---+------------
      A  B  C  D
>

The player "○" wins the game since he placed his marks in a row diagonally (A3-B2-C1).

 1 |  o  x  
 2 |  o  x  
 3 |  o     x
 4 |  o  x
---+------------
      A  B  C  D
>

The player "○" wins the game if ALLOW_EXCEED is 1; otherwise, the game will continue because the number of "○"s in a row exceeds GOAL.

• Mastering Tic-Tac-Toe with Minimax Algorithm in Python
• tic-tac-toe: tic-tac-toe game for terminal I/O.