Evolving network in game
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) &gt; f(\pi_1) &gt; 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.