AI for Tic-Tac-Toe (Part 2)

The last time, I have talked about non-intelligent bot to play to Tic-Tac-Toe (link). The first bot is named 'Full Random' and chose a cell randomly. The second bot is named 'Partial Random', It work in the same way, except if there are two cells aligned with the same symbol. In this case, it fill the last cell to win or to avoid losing. Nevertheless, there are many possible traps.

The 'Partial Random' can align 3 cells and avoid that the opponent align cells (except the cases where there are traps)
The 'Partial Random' can align 3 cells and avoid that the opponent align cells (except the cases where there are traps)

3rd competitor: 'The Trapper'

Now, I present 'The Trapper'. It is an evolved version of 'Partial Random': it creates 'traps' if this is possible. It tests each move and selects one which allows to have two choices. If the opponent select one then the bot win with the second.

Create a trap
Create a trap

This competitor is not unbeatable. Many time it loses the initiative and the opponent can create traps.

Battle #5: 'The Trapper' vs 'Full Random'
Battle #6: 'Full Random' vs 'The Trapper'
Battle #7: 'The Trapper' vs 'Partial Random'
Battle #8: 'Partial Random' vs 'The Trapper'

4th competitor: 'Guided Trapper'

Last time, I have talked about a unbeatable bot. but I am maybe a liar. In fact, I haven't tested all combinations and I can't found my old code. So, I use my memory. I remember a tip: if the bot is the second player so its first move is to chose the central cell.

This choice allow to create a bot which prefers to tie than to lose.

Battle #9: 'Partial Random' vs 'The Guided Trapper (Version 1)'

You can compare battles #8 and #9. The difference concerns the position of the first move of 'The Guided Trapper'.

An weakness of previous bot is the losing of initiative: many times the bots have no choice, the first play to a position to avoid aligning, the second too and this fact create an trap. The previous bots, can’t predict a solution.

5th competitor: 'The Brute'

The next competitor, have tested all solutions by brute-force. So it knows the bad choices and avoid it.

Initially, it creates a tree with all possible solutions (255168 cases).

  • the first player can win in 131184 cases (51%).
  • the second player can win in 77904 cases (30%).
  • there are 46080 tie cases (19%).

The mechanism is simple: there are two tags for each choice: "lose" or "win".  If the current choice is winning, that means the previous player have selected a bad cell and the previous choice is tagged "lose". Now, if all future choices are losing then the current choice is winning.

If there are a winning case, that means the previous is bad. And if there are only losing cases, so the previous case is a winning choice.
If there are a winning case, that means the previous is bad. And if there are only losing cases, so the previous case is a winning choice.
Battle #10: 'The Brute' vs 'Full Random'
Battle #11: 'Full Random' vs 'The Brute'

This new bot can't lose. It's the best and displaying others battles seem useless.

Battle #12: 'The Brute' vs 'Partial Random'
Battle #13: 'The Brute' vs 'The Trapper'
Battle #14: 'The Brute' vs 'The Brute'

Conclusion

This second article shows three other competitors. One which is able to create primitive traps, the second which is guided in a particular case and the third which is unbeatable.

The Brute can be improved. Currently, it chooses a random cell among winning case and non losing case. The choices can be weighted to use weaknesses of the
opponent according to a method as the Multi-armed bandit