You want to build your own Tic-Tac-Toe opponent? Then you need to read further! In the Tic-Tac-AI series, I will present a couple of Artificial Intelligence algorithms implemented as Tic-Tac-Toe opponent. In this first article, I will introduce a method called Forward Sampling which is capable of not losing any game of Tic-Tac-Toe!

*The repository for this article is found on GitHub.*

## Introduction

Tic-Tac-Toe is a very basic game and therefore extremely helpful to display the most elegant Artificial Intelligence algorithms. In this article, I will explain Forward Sampling implemented in a Tic-Tac-Toe player for you.

## Forward Sampling!

Here, we will model the winning probability for our smart player by $p_{win}$. Let $S$ denote the current state of the game (that is, the tiles we have picked and the tiles the opponent has picked). So, what is our probability to win? In order to simulate this, we pick a valid random action $a_1$ (a tile that is not occupied yet) and we evaluate our winning probability given the action we just picked ($p_{win}(a_1)$). Now, our opponent can pick any tile. The opponent also picks a random valid next action and denote this by $a_2$. Now, it is our turn again. So, eventually, we end up calculating $p_{win}(a_1, a_2, …, a_n)$.

At any point in the game, $S$ consists of some consecutive actions, say $S=a_1, …, a_s$. What is the next move we need to make in order to win the game? That is, what valid action $k$ should we take such that $p_{win}(S, k)$ is maximal? Let $T$ be the remainder of the game. That is, the set of actions which were picked to finish the game ($T=b_1, …, b_t$). Notice that there are many possibilities for $T$ given $S$ and $k$. With our Forward Sampling procedure, we pick many different options for $T$ and check for every valid $k$ $p_{win}(S, k, T)$. For example, suppose that we are in the following state (and we are O and our opponent is X):

If we do not pick the bottom-right cell, we will lose! Thus, if $k$ does not equal the bottom-right cell, there are only a few options for $T$ in which we will not lose. Our procedure will therefore pick the bottom-right cell, since this has the highest winning probability.

## Implementation

In this section, I will give the code for the Forward Sampling player:

The tiles (my_tiles, opponent_tiles, free_tiles) are lists of integers where 0 is the left-top cell and 8 is the bottom-right cell. The make_action method, returns an action (any free tile) based on the described sampling procedure. Every time, 100 samples are generated (that is, 100 different options for $T$ are computed) and then the best tile is picked.

## Conclusion

Forward sampling is very effective (and does not require any learning). Can you beat the algorithm? If you have any questions or suggestions, feel free to comment below this post!