Answers.Body: <blockquote>
    <p>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?</p>
  </blockquote>
  
  <p>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.</p>
  
  <p>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:</p>
  
  <ul>
  <li><span class="math-container">$\pi_1$</span>: an optimal player</li>
  <li><span class="math-container">$\pi_2$</span>: a sub-optimal player</li>
  <li><span class="math-container">$\pi_3$</span>: a different sub-optimal player</li>
  </ul>
  
  <p>There can easily be situations where the optimal player <span class="math-container">$\pi_1$</span> gets a draw against both of the sub-optimal players (if they're not <strong>extremely</strong> 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.</p>
  
  <p>In the same situation, the sub-optimal player <span class="math-container">$\pi_2$</span> for example may be able to consistently win against a slightly worse sub-optimal player <span class="math-container">$\pi_3$</span>. In this example situation, your fitness function ranks the agents <span class="math-container">$f(\pi_2) &gt; f(\pi_1) &gt; f(\pi_3)$</span>, which is wrong.</p>
  
  <hr>
  
  <p>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).</p>
  
  <p>If you really want to use only evolving, no tree search, you'll have to find a way to <strong>fix the fitness function such that the problem described above can no longer occur</strong>. One way you could try to do that (<em>not 100% sure it would work, but imagine that it might</em>) 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:</p>
  
  <ul>
  <li>You'll likely want to <strong>repeat the entire tournament many times with different, randomized initial pairings in the bracket</strong>, 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.</li>
  <li>You'll have to think about which actions the agents select in such a tournament. Do they deterministically play the action given by the <span class="math-container">$\arg\max$</span> 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. <strong>I suppose I would lead towards deterministic play with the <span class="math-container">$\arg\max$</span> over the softmax outputs</strong>. In a large tournament, there will still be sufficient variety due to encountering many different opponents.</li>
  <li>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 <span class="math-container">$\arg\max$</span> 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.</li>
  <li>You'll want to think about how to handle <strong>illegal actions</strong>. 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 <strong>manual post-processing step in which you manually set probabilities of illegal actions being played to <span class="math-container">$0$</span></strong>, and normalizing to make sure the probabilities over the remaining actions add up to <span class="math-container">$1$</span> 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.</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-16T12:01:44.443Z
Answers.LastActivityDate: 2018-12-16T12:01:44.443Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p>The characteristics of the game are these.</p>
  
  <ul>
  <li>Moves are in two dimensions</li>
  <li>Only three possible first moves because of symmetry (corner, edge, middle)</li>
  <li>Never more than seven possible moves after that</li>
  <li>No random game play element (such as a roll of dice)</li>
  <li>No secrets (such as a hand of cards)</li>
  <li>No way to lose with perfect play</li>
  <li>Only one two-part rule: (1) Must make your mark (2) in an unmarked cell</li>
  <li>Only one winning condition: Three in a row of your mark</li>
  </ul>
  
  <p>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.</p>
  
  <p>The problem is not related to human versus self play.</p>
  
  <p>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 &mdash; threshold activation functions in the last layer.  Use two pair of binary output cells, one pair for each dimension.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-16T09:54:40.310Z
Answers.LastActivityDate: 2018-12-16T09:54:40.310Z
Answers.UserDisplayName: Douglas Daseeco
Body: <p>I wrote a simple feed-forward neural network that plays tic-tac-toe:</p>
  <ul>
  <li>9 neurons in input layers: 1 - my sign, -1 - opponent's sign, 0 - empty;</li>
  <li>9 neurons in hidden layer: value calculated using ReLU;</li>
  <li>9 neurons in output layer: value calculated using softmax;</li>
  </ul>
  <p>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.</p>
  <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-24T09:43:23.763Z
Comments.Text: Are you using any form of cross-over between two parents in reproduction?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-24T10:41:35.443Z
Comments.Text: I do, I tried to use mutation only and crossover + mutation, yet results are essentially same. I doubt that this is the problem.
Comments.UserDisplayName: Perpetuum
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-24T11:41:41.900Z
Comments.Text: Yes, I was asking because cross-over in neural networks may work better using a system like NEAT which can track compatibility between architectures as they grow. It is hard to tell where your problem might be, but combining GAs and NNs is quite tough, the search space is complex due to co-dependencies between weights (making cross-over fail unless care is taken). And the space also becomes very large quickly (making random mutations inefficient for searching). I guess your architecture has 180 parameters, weights + biases, to find optimal values for?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-24T12:28:39.727Z
Comments.Text: Yes. I understand why this approach doesn't work, but it's hard for me to it put in technical terms. Basically, there is no emerging correct strategy since network only plays against different variations of itself, playing against AI that knows optimal strategy would teach network to make correct moves, but I want to find a solution without this approach, so I could use network in situations where there is no known optimal strategy.
Comments.UserDisplayName: Perpetuum
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-24T12:38:10.383Z
Comments.Text: The design should work in principle for self-play. It is a matter of details, and what you can change to enable it in a reasonable time. I don't know the answer here. But one thing you could try is see whether the network can learn your desired function. Create a table of all the correct moves, and use normal supervised learning with gradient descent. Can the network get a high accuracy when told the answer? If it can, then you have ruled out the network architecture as a problem. If it cannot, then I would probably try a deeper network - keep adding layers until it works.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-24T12:39:03.557Z
Comments.Text: Of course in a non-trivial game, you won't be able to create this supervised learning data, but you may start to get a feel for correct NN architecture.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-24T13:02:16.873Z
Comments.Text: One thing: How are you matching up genomes to play each other and get a fitness rating in each generation? Is it all-play-all (so an evaluation round is 4950 games), a single random pairing (evaluation round is 50 games), or something in-between or different? Please [edit] that into the question.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-08-24T14:32:32.283Z
Comments.Text: From where I stand you it seems that you miss some new blood in your strategy. Have look here : https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_parent_selection.htm if you always select top elements to reproduce,you will converge too quickly which seems to be the case. Hope this helps
Comments.UserDisplayName: MaxouMask
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-10-25T18:27:32.363Z
Comments.Text: http://eng.uber.com/wp-content/uploads/2017/12/improving-es-arxiv.pdf
  To explore more when stuck in local optimum
Comments.UserDisplayName: sagar_acharya
Tags: <training><evolutionary-algorithms><feedforward-neural-networks><fitness-functions><fitness-design>
Title: Why does the fitness of my neural network to play tic-tac-toe keep oscillating?
UserDisplayName: Perpetuum
ThreadText: # Why does the fitness of my neural network to play tic-tac-toe keep oscillating?
  
  (Asked by: username_0 on 2018-08-24)
  
  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?
  
  **Tags:** training, evolutionary-algorithms, feedforward-neural-networks, fitness-functions, fitness-design
  > **Comments:**
  > **username_1**: Are you using any form of cross-over between two parents in reproduction?  
  > **username_0**: I do, I tried to use mutation only and crossover + mutation, yet results are essentially same. I doubt that this is the problem.  
  > **username_1**: Yes, I was asking because cross-over in neural networks may work better using a system like NEAT which can track compatibility between architectures as they grow. It is hard to tell where your problem might be, but combining GAs and NNs is quite tough, the search space is complex due to co-dependencies between weights (making cross-over fail unless care is taken). And the space also becomes very large quickly (making random mutations inefficient for searching). I guess your architecture has 180 parameters, weights + biases, to find optimal values for?  
  > **username_0**: Yes. I understand why this approach doesn't work, but it's hard for me to it put in technical terms. Basically, there is no emerging correct strategy since network only plays against different variations of itself, playing against AI that knows optimal strategy would teach network to make correct moves, but I want to find a solution without this approach, so I could use network in situations where there is no known optimal strategy.  
  > **username_1**: The design should work in principle for self-play. It is a matter of details, and what you can change to enable it in a reasonable time. I don't know the answer here. But one thing you could try is see whether the network can learn your desired function. Create a table of all the correct moves, and use normal supervised learning with gradient descent. Can the network get a high accuracy when told the answer? If it can, then you have ruled out the network architecture as a problem. If it cannot, then I would probably try a deeper network - keep adding layers until it works.  
  > **username_1**: Of course in a non-trivial game, you won't be able to create this supervised learning data, but you may start to get a feel for correct NN architecture.  
  > **username_1**: One thing: How are you matching up genomes to play each other and get a fitness rating in each generation? Is it all-play-all (so an evaluation round is 4950 games), a single random pairing (evaluation round is 50 games), or something in-between or different? Please [edit] that into the question.  
  > **username_2**: From where I stand you it seems that you miss some new blood in your strategy. Have look here : https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_parent_selection.htm if you always select top elements to reproduce,you will converge too quickly which seems to be the case. Hope this helps  
  > **username_3**: http://eng.uber.com/wp-content/uploads/2017/12/improving-es-arxiv.pdf To explore more when stuck in local optimum  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_4 on 2018-12-16. Score: 2
  
  > 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 by username_5 on 2018-12-16. Score: 1
  
  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.
  
  
  ---
  
  