Finding a 73-Move Solution When Every Correct Move Looks Wrong

#python #ai #machinelearning #computerscience

A technical write-up on building an AI solver for Google's Tic-Tac-Go puzzle.

Live Solver · GitHub · Play Tic-Tac-Go

What happens when a simple puzzle game defies standard computer science algorithms? While playing Google’s Tic Tac Go, I came upon a problem: I could not solve one of the posted boards myself but I wanted to know the solution. This small issue took me across a multi-week journey diving into topics from graph search to a custom convolutional neural network.

Tic Tac Go is a sliding box puzzle game where the user controls one O piece and has to get 3 O pieces in a row without getting 3 Xs in a row. The board size and number of Xs can vary, from 3×3 to 8×8, but there is always only 3 Os, including the user. Although the game appears simple, the number of reachable board states grows rapidly with board size, making exhaustive search computationally impractical.

The Tutorial board. Try the game first for full context.

The solver evolved from exhaustive graph search into a hybrid architecture combining heuristic search and learned state evaluation.

Initial BFS Solver

My first idea was very simple and came from my University Computer Science class. We had just started to cover simple algorithms, so I decided to give Breadth First Search (BFS) a shot. The implementation was not very difficult. BFS simply starts at the beginning state of the board, and goes out in all directions trying every possible move. This has the added benefit of having the first solution it finds be the most optimal one, since it takes the least number of moves.

BFS diagram showing board states expanding outward from the initial state

Scaling Problems

After half a day of creating this algorithm along with rejecting illegal states and moves, I had a working prototype. It stored the board states in an array and kept a secondary array of board states it had already seen, so as to not loop infinitely. Testing on smaller boards it worked great, solving them in seconds. However, then I tried larger boards - 7×7 and 8×8. These performed far worse. They took at least 10 minutes to solve, and in the worst cases did not finish at all, while using up to 64 GB of RAM.

I attempted to make the algorithm more efficient by checking for illegal states at more optimal times, but the root issue remained. The search space for large boards was just too big.

Due to the exploding board state issue, I realized the problem was I had no way to know a good board from a hopeless one. Without any ranking of boards, every board had to be explored. This realization revealed the central challenge of the project: how can the long-term value of a board state be estimated? My initial thought was to use a search like A*, where a heuristic gives different paths different weights. However the roundabout nature of many solutions would mean any heuristic would not be able to accurately guide a complex solution.

Exploring Reinforcement Learning

To remedy this complexity issue, I turned towards neural networks - more specifically reinforcement learning (RL). I believed if the neural network could learn these complex solutions it would be able to solve any board. I found the library Stable Baselines 3, which has a host of different RL networks. I ended up choosing the Deep Q-Network (DQN) as it was built for discrete action spaces, where the move output was from a countable number of possible moves - in this case 4: up, down, left, and right.

In short, the DQN model initially tries to move randomly. It puts the move and reward it gets from each move in a storage space called a replay buffer. It then randomly chooses a move from the replay buffer and estimates the expected future reward (Q-value). Based on the accuracy of the guessed reward it updates its weights accordingly to be more accurate, thus learning. My approach also used a Convolutional Neural Network (CNN) policy for the model - when a board is inputted, it is separated into different channels, one for each type of piece, since each piece type has its own properties.

Curriculum Learning

To train the model I used a library called Gymnasium. I implemented a custom environment representing the game's rules, observations, legal actions, and reward structure. However, rewards had to be set manually, and for a game like Tic Tac Go rewarding a move based on most metrics could lead to a trap. For example, if rewards are given based on closeness to Os and the solution is roundabout, the agent could never try to move far from the Os. This issue is called sparse rewards, where only very few states can give the model feedback - in my case: win, lose, no movement, and a small per-step penalty.

I found the solution to be curriculum-based learning: very simple situations are given initially, gradually ramping up the difficulty in what is called graduation steps. This combats sparse rewards because the model can learn in an earlier graduation step and transfer that learning to more complex boards rather than randomly wandering with little feedback.

Refining this curriculum took weeks of testing and revising, with around 20 revisions. The model slowly climbed up the grad steps, but soon a new issue emerged. At complex enough boards the model lacked the ability to infer difficult solutions from its greedy approach. After roughly 36 hours of training, performance plateaued. Checking under the hood, the issue was apparent: for complex boards the Q-values were relatively equal, meaning every move was ranked similarly. This caused looping during training so the model could not learn these more complex boards.

I attempted to fix this by adding a 6th channel to the CNN for positions the agent had visited before - if the agent could infer that revisiting states caused negative reward, it might stop the looping. This improved things slightly, but the issue remained.

Beam Search and Heuristics

To assist the DQN model, I added two things: a handcrafted heuristic and beam search. Beam search keeps only a certain width of board states, pruning the rest based on a ranking system. This limited RAM usage to a manageable level - a beam width of approximately 5,000 states provided a good balance between memory consumption and search quality.

The heuristic calculated the score of each board state based on Manhattan distance of the agent to other Os, the X blockers in the path, and proximity to promising win lines. I thought the DQN could guide the heuristic enough to avoid traps, and the heuristic could improve the overall ranking. However after implementing these, the heuristic alone was outperforming the DQN-heuristic combination. The learned policy failed to distinguish sufficiently between promising and unpromising states. I also tried Proximal Policy Optimization (PPO), but this performed substantially worse than DQN.

The heuristic with beam search was able to solve around 87% of all 7×7 and 8×8 boards - a large improvement. I still faced the issue of boards with roundabout solutions being impossible for an algorithmic heuristic to navigate alone.

Learning From Solver Errors

To gain more insight into what exactly was happening with the failing boards, I built a logging tool that compared the heuristic's move rankings against known optimal solutions step by step. I logged the rank of the optimal move at each step, along with the score gap between it and the heuristic's top choice. The output for a single board looked like this:

step 004  correct=D  rank=2  candidates=3  best=U  gap=1.33
step 005  correct=L  rank=2  candidates=3  best=U  gap=1.33
step 006  correct=D  rank=3  candidates=3  best=R  gap=0.67
step 007  correct=R  rank=2  candidates=2  best=U  gap=0.0
step 008  correct=R  rank=3  candidates=3  best=U  gap=2.0  ← confident wrong
step 009  correct=R  rank=2  candidates=2  best=L  gap=0.67
step 010  correct=U  rank=3  candidates=3  best=L  gap=1.33

The pattern was immediate. The correct move was almost never missing entirely - it appeared in the top three nearly every step. The problem was that it was consistently ranked second or third rather than first, often with a nonzero gap, meaning the heuristic was not just breaking a tie but confidently preferring the wrong move. Step 8 is a clear example: the correct move is ranked third with a gap of 2.0, meaning the heuristic scored two other moves meaningfully higher. Over a 70-move solution, this persistent slight disadvantage compounded until the correct path fell out of the beam entirely.

The specific blind spot: the heuristic rewarded moving the agent toward the nearest O piece. But on hard boards, the correct move is often to clear an X blocker out of the O's push path first - which means moving away from the O entirely. The heuristic had no model of whether the O was actually pushable toward the target.

The agent (dots) must first clear the X blockers before approaching the O piece. The heuristic prefers moving directly toward O; the correct move goes the other way.

Supervised CNN

Seeing the failure of the heuristic model due to complexity, I tried a more direct learning approach: a pure CNN trained on correct moves. The DQN model failed in part due to having to infer patterns from its Q-values rather than the direct move. I built this with PyTorch - 3 convolutional layers to analyze the input board and find patterns, and 2 linear layers to identify a move output. This stripped away the inference of Q-values by training directly on board-state and best-next-move pairs.

The heuristic's ability to solve some boards gave me the data necessary to train the model. I formatted the solved boards into board-state/optimal-move pairs and trained the supervised model on roughly 75,000 of them using a batch size of 64 for 5 epochs, converging to a loss of approximately 0.3 in about 20 minutes on CPU.

Alone it was unable to solve many boards, but combined with the heuristic and beam search it was able to solve 90% of real boards. Tuning the heuristic and adding extra training data brought this to 91%. I noticed that some boards the combined heuristic+CNN could not solve, the heuristic alone could - and vice versa. Rather than relying on a single algorithm, the final solver ran both approaches and used whichever succeeded. This brought the number up to 93% of boards solved. 99.4% of the time the optimal move was in the top 3 choices, and 97.1% of the time it was in the top two - significantly reducing the compounding divergence problem.

Results

After exploring BFS, reinforcement learning, heuristic search, and supervised learning, the final hybrid solver achieved a 93% solve rate on real Tic Tac Go boards while averaging roughly 36 seconds per puzzle.

Metric	Value
Training pairs	~75,000
Training boards	~5,000
Beam width	5,000
DQN training time	~36 hours
CNN training time	~20 minutes
Batch size	64
Epochs	5
Peak memory	~2.5 GB
Average solve time	36 s
Evaluation boards	334
Solve rate	93%

Lessons Learned

The biggest lesson from this project was that solving complex search problems rarely involves finding a single perfect algorithm. Instead, progress came from understanding why each approach failed and combining the strengths of multiple methods. Every failed experiment revealed another property of the problem that guided the next iteration.

Remaining boards generally require intentionally moving away from promising positions before making progress - something the current heuristic and CNN still struggle to recognize. Future work could explore Monte Carlo Tree Search, larger supervised datasets, or imitation learning from human solutions to better capture these long-term planning behaviors.

Although this project focused on a puzzle game, many real-world planning problems face similar challenges: large search spaces, sparse rewards, and long-term dependencies. The techniques explored here, combining heuristic search with learned state evaluation, are broadly applicable to search and planning problems beyond games.