Why does the fitness of my neural network to play tic-tac-toe keep oscillating?

Question

I wrote a simple feed-forward neural network that plays tic-tac-toe:

• 9 neurons in input layers: 1 - my sign, -1 - opponent's sign, 0 - empty;
• 9 neurons in hidden layer: value calculated using ReLU;
• 9 neurons in output layer: value calculated using softmax;

I am using an evolutionary approach: 100 individuals play against each other (all-play-all). The top 10 best are selected to mutate and reproduce into the next generation. The fitness score calculated: +1 for the correct move (it's possible to place your sign on already occupied tile), +9 for victory, -9 for a defeat.

What I notice is that the network's fitness keeps climbing up and falling down again. It seems that my current approach only evolves certain patterns on placing signs on the board and once random mutation interrupts the current pattern new one emerges. My network goes in circles without ever evolving actual strategy. I suspect the solution for this would be to pit network against tic-tac-toe AI, but is there any way to evolve the actual strategy just by making it to playing against itself?

Answer 1

What I notice is that the network's fitness keeps climbing up and falling down again. It seems that my current approach only evolves certain patterns on placing signs on the board and once random mutation interrupts current pattern new one emerges. My network goes in circles without ever evolving actual strategy. I suspect solution for this would be to pit network against tic-tac-toe AI, but is there any way to evolve actual strategy just by making it to playing against itself?

The likely cause of this phenomenon is that your fitness function involves evaluating the fitness of an agent by letting it play lots of other agents (the entire population), many of which are likely very poor agents.

Because Tic-Tac-Toe is such a simple game, we know that optimal play from both sides leads to a draw. Suppose we have a population of the following three strategies:

• $\pi_1$: an optimal player
• $\pi_2$: a sub-optimal player
• $\pi_3$: a different sub-optimal player

There can easily be situations where the optimal player $\pi_1$ gets a draw against both of the sub-optimal players (if they're not extremely bad), because right from the get-go an optimal player will play "safe" enough such that it can still guarantee a draw against an optimal opponent, which may not be the fastest way to win against a sub-optimal player.

In the same situation, the sub-optimal player $\pi_2$ for example may be able to consistently win against a slightly worse sub-optimal player $\pi_3$. In this example situation, your fitness function ranks the agents $f(\pi_2) > f(\pi_1) > f(\pi_3)$, which is wrong.

---

As you already suggested yourself, the most straightforward way to address this problem would be to simply evaluate the fitness of strategies by having them play against an optimal minimax-agent, rather than a population of many strategies (including poor ones).

If you really want to use only evolving, no tree search, you'll have to find a way to fix the fitness function such that the problem described above can no longer occur. One way you could try to do that (not 100% sure it would work, but imagine that it might) would be to set up some larger tournament bracket where agents progress through the brackets if they're able to beat others which they were paired up with. Getting further in the tournament would then increase the fitness of an agent. Very bad sub-optimal players should not be able to progress far in the tournament if they get beaten by other (sub-)optimal agents, but sub-optimal agents which manage to advance still shouldn't be able to get more than a draw against an optimal agent. Some things to keep in mind with this idea:

• You'll likely want to repeat the entire tournament many times with different, randomized initial pairings in the bracket, and compute fitness based on average (or maybe median or max) ranking across all repetitions of the tournament. This would be to filter out members of the population getting particularly lucky or unlucky with the opponents they encounter in the brackets.
• You'll have to think about which actions the agents select in such a tournament. Do they deterministically play the action given by the $\arg\max$ of the softmax outputs (in which case you could also just use the linear outputs rather than softmax outputs, since the softmax function does not change ranking of outputs). Or do they nondeterministically sample actions according to the softmax distribution? Sampling actions according to the softmax distribution seems attractive because it leads to more variance in game state situations encountered, and it is important to be robust and be capable of handling many different game states. On the other hand, it does introduce noise and may make an optimal agent accidentally lose. I suppose I would lead towards deterministic play with the $\arg\max$ over the softmax outputs. In a large tournament, there will still be sufficient variety due to encountering many different opponents.
• You'll have to put thought into handling the situation where two agents may infinitely keep drawing against each other. Which agent advances? If this happens, I think I would gradually shift from deterministcally playing $\arg\max$ actions to playing according to the softmax distribution. This guarantees that someone eventually loses. Averaging results over multiple different games like this, plus averaging over multiple different repetitions of the complete tournament, should yield accurate results.
• You'll want to think about how to handle illegal actions. You describe including punishments for illegal actions in the fitness function. This introduces extra noise / variance in the fitness function which is already difficult enough to get right to begin with, so I wouldn't do this. I'd recommend having a manual post-processing step in which you manually set probabilities of illegal actions being played to $0$, and normalizing to make sure the probabilities over the remaining actions add up to $1$ again. This is also what's done (on a much larger scale) by DeepMind in their state-of-the-art Go/Chess/Shogi agents for example. If you really don't want to do this, if you really want evolved strategies to automatically learn not to ever have high outputs for illegal actions, I would recommend immediately making them lose the game if they do suggest an illegal action. That way you still have a "clean" fitness function based only on wins/draws/losses.

Answer 2

The characteristics of the game are these.

• Moves are in two dimensions
• Only three possible first moves because of symmetry (corner, edge, middle)
• Never more than seven possible moves after that
• No random game play element (such as a roll of dice)
• No secrets (such as a hand of cards)
• No way to lose with perfect play
• Only one two-part rule: (1) Must make your mark (2) in an unmarked cell
• Only one winning condition: Three in a row of your mark

The goal strategy is to get two marks such that a third will require two blocks in one opponent move. A three layer network will be able to learn that strategy. Because the game complexity is low, a mutation is always going to have a radical effect on game play. This means that the changes due to the mutation must be gradual and must stop when the strategy is found. This implies that stateful learning is best.

The problem is not related to human versus self play.

Since there is exactly one mark to make per turn, soft max doesn't make much sense for the output layer. You want binary outputs — threshold activation functions in the last layer. Use two pair of binary output cells, one pair for each dimension.