1. Why the tile sliding puzzle is hard to train an AI on

One of the tasks I took on early was the tile sliding puzzle (TSP from here on). As soon as it started, the AI kept repeating the same spot and could not solve the puzzle. If it had got somewhere first I might understand, but it could not even start; it just kept going back and forth on the same spot. I think the reason is the reward. Every AI, LLM or not, works toward a task reward and tries to collect as much reward as possible. But solving a TSP requires knowing a few rules spread over several steps. Suppose the board holds the numbers 1 to 15 plus one empty cell, and the goal is to place 1. You have to build a band (loop) that contains 1, and this band must include 1's target cell, 1's current position and one empty cell in between. Rotating that minimal group of six cells, which contains the empty cell, the target and the number 1, brings 1 to its own place. The problem is that the empty cell sits right behind 1, and 1 only gets a reward for moving forward into the empty cell. After it moves, the empty cell moves up, and once again moving 1 into the empty cell is the biggest reward. So an endless back-and-forth between the empty cell and 1 begins. If you tell the AI not to solve the answer right away, but first to build the loop and keep turning it until 1 reaches the final target zone, rewarding it on arrival and also rewarding it for completing the first loop, the AI stops making endlessly repeating moves. Cases like this come up a lot when you actually train AIs. Reinforcement learning used to be very common, but with reinforcement learning such loops occur countless times. Training is also very slow, and once it reaches the point where a loop appears, all the earlier training turns into loss. Now I no longer use reinforcement learning; I download models from Hugging Face and fine-tune them. Reinforcement learning used to cause trouble as a triple combo of cost, time and training loss. I think people training AIs can use LLMs in many fields by understanding why the infinite-loop problem happens and by changing the training method.

Looking at the records

This is the log of training DQN for 500,000 moves (about 1,000 games). The reward went up, but not a single game was completed within the 500-move limit.

I ran the trained model again on 50 boards shuffled by 80 moves. Without a safeguard, the same board appeared four times after a median of 8 moves, and on 15 boards it just moved back and forth between two cells from the very start.