TicTic: Perfect Play

When a new game sees the light of day, it's only a matter of time till computers start to dominate it. Even the best players in the world can't compare to the Chess bots and alike. Since TicTic is quite small, we can take this even further: how about a program that plays perfectly? That already knows in advance whether or not it's going to win?

Running this experiment can help us answer some key questions:

1. Are the two roles (Cross vs Circle) truly balanced?
2. Which starting moves are the best?

Mining a board ain't easy

To solve a board, we need to prove that a player can force a win or at least a tie. We do this by showing that for whichever move the opponent does, we have a response that leads to a win (tie). Even though there's just 13 places to play on (12 pairs + the center), it's a lot of options to navigate! With numerous optimisations, it still took on average 69.4 seconds to solve a board, times varying from just 10 milliseconds to half an hour! Huge thanks go to my good friend Adam for investing about 32 days of processing time to create our 40,000 board dataset.

The first move first

How we discussed in the previous article, TicTic has a tad of imperfect information – the first move. With most of the board covered in darkness, even our perfect AI can't always make the best decision. It turns out the opening is way more influential than I thought. If Cross gets very lucky (or if they could see the whole board), Circle wins just 3.8% of the time! On the other hand, if the first player gets very unlucky, they win on only 0.6% boards! Choosing a random move goes slightly in favour of Circle: the X/tie/O win rate is 19.4/51.1/29.6%. There is surely a better way to play, but which moves to prioritize?

View of the spectrum

Taking all the symmetries into account, there are 20 different move types on the perimeter (can you find them all?). With the way boards are generated (see previous article), just 18 move types can appear on a real board. Some are brilliant, some are to avoid.

To compare them, simply looking at the win rate isn't enough as the tie plays an important role. A better approach would be to calculate a single number: the average "points" the starting move results in, where a win for X is 1, a tie = 0.5 and a loss is 0. Below are the two best openings in the game (they immediately threat by making a three in-a-row), as well as the two worst:

They all excel in their category. The greatest move (0.85), for example, wins 75% of the time and ties in 20.5% cases, leaving very little chance for Circle. After the top two follow some fine moves, though they're already way more fair:The ones lower than 0.5 are actually already in O's favour, but still comparably on the better side. Then there are three "average" 0.42 moves and here are the definitely bad: 

Strategize for profit

Now that we know which first moves to prefer, the AI can choose the best one overall. While this doesn't take into account all the information available, it is a huge advancement over the random strategy: from 0.45 points to 0.6! In theory, the ceiling is 0.75, though I doubt choosing perfectly is possible with this much unknown. Using the current method, X secures a win on 34.8% of the boards and loses just 14.3% games, the rest being draws.

Wrap up

All this talk is mostly theoretical as humans aren't perfect players. But it wouldn't surprise me if playing the "right" opening yielded more wins in human games too! The stats also confirm the game is decently balanced, even on this unthinkable level. For now.

Thanks for making it here, I hope you enjoyed! If you have any thoughts or feedback, please let me know down in the comments :), or reach me out on Discord (tonylium). Have a wonderful new year.