# Why does self-playing TicTacToe not become perfect?

I trained a DQN that learns TicTacToe by playing against itself with a reward of -1/0/+1 for a loss/draw/win. Every 500 episodes I test the progress by letting it play some episodes (also 500) against a random player.

As shown in the picture the net learns quickly to get an average reward of 0.8-0.9 against the random player. But after 6000 episodes performance seems to deteriorate. If I play manually against the net after 10000 episodes it plays okay, but by no means perfect.

Assuming that there is no hidden programming bug, is there anything that might explain such a behavior? Is there anything special about self-play in contrast to training a net against a fixed environment ?

Here further details: The net has two layers with 100 and 50 nodes (and a linear output layer with 9 nodes), uses DQN and a replay buffer with 4000 state transitions. The shown epsilon values are only used during self-play, during evaluation against the random player exploration is switched off. Self-play actually works by training two separate nets of identical architecture. For simplicity one net is always player1 and the other always player2 (so they learn slightly different things). Evaluation is then done using the player1 net vs. a random player which generates moves for player2.

Thanx

• have you tried making the network deeper? – k.c. sayz 'k.c sayz' Jun 5 '18 at 21:41
• I haven't done any DQN training before, but note that if your game agent plateaus during self-play it might be the case that each instance of gameplay is very similar to previous instances, thus reducing the amount of "stuff" learnt – k.c. sayz 'k.c sayz' Jun 5 '18 at 21:44
• Sounds to me like over-fitting, ie it gets very good at beating one particular player (itself), but cannot cope easily with different playing styles. – Oliver Mason Jun 6 '18 at 7:47
• When you let the network play against a random player, do you switch off the exploratory moves? The DQN should in theory learn optimal play (it may not be here, and I have a few ideas about what might be going wrong for you), but the learning agent will have some epsilon probability of making a random move whilst in learning mode, so I'd like to know a bit more about how you are assessing it. – Neil Slater Jun 6 '18 at 8:45
• Yes, when I play against the random player exploration is off (eps=0). The shown epsilon values only apply during the phases of self-play. Btw., during self-play I train of course two independent networks which play against each other (and not one). – Axel Jun 6 '18 at 10:05

There are lots of ways that RL agents can fail to learn properly, so you are faced with a little bit of experimentation and maybe bug hunting unfortunately. However, from the description you have given in the question and comments, I can make a few observations and guesses about where to look:

• Your metric of average reward against a random player is sensible. In this case, you could also use a perfect player (that ideally randomised choice of any optimal move), where you would see a maximum averaged return of zero - this would be helpful to know if your agent had learned a fully optimal behaviour, because it would consistently score zero. In general for more complex games a perfect player is not available to test with, but as you are learning here it might help you.

• Your DQNs might be unable to fit the value function. You can test that in this case by getting the value function from an optimal self-play player (all the values will be -1, 0, or 1) and using a supervised learning approach, separately from your agent. You should be able to get a loss very close to zero - if you cannot do that, then something could be wrong with your network architecture.

• Whilst you are training, even though you are using a variation of Q-learning (which learns an optimal policy even whilst exploring other actions), your DQNs are not learning optimal play. That is because you have used two agents. In DQN, the algorithm is not aware that there are other learning agents, and it will treat any other agents as if they were part of the environment. Which means that the agents will spend some effort trying to set the game up for each other to make an exploration mistake. That could lead to non-optimal choices and a little bit of instability. Your decay of epsilon should help with that, although you are caught between a rock and a hard place here. You want to learn off-policy and explore, but are forced to reduce exploration. There are a couple of ways to resolve that, I will explain a bit further down . . .

• 10,000 games may not be enough. In the experiments I have done with TicTacToe agents, it seems between 20,000 and 50,000 games are required for a naive learner. More may be required if you have done something that makes learning inefficient. In addition, I found when adding more sophisticated learning approaches (in my case using eligibility traces) the agents appear to become close to optimal very quickly, but actually have flaws which take a long time to shake out, just as long as running a more naive algorithm. When the flaws got found and fixed, it upset the value function for a while and I saw fluctuations in my metrics similar to yours.

• Q-learning with NNs is inherently unstable. DQN implements some ideas to fix that, but it is not perfect. It is not uncommon to need to adjust the batch size and/or time steps between taking frozen copy of network for the TD target calculation. The initial stability followed by poor performance looks a lot like that instability too.

Regarding your use of two opposing agents, I can see two possible improvements:

1. Alternately train one or other agent in each game, don't train both at once. That will mean each agent is learning to play against the other agent playing its best without exploratory moves.

2. Combine networks into single agent description. As this is a zero-sum game, you can take player A's network for calculating values, and just have player B try to minimise the action value on its turn. That means use min and argmin functions for steps that represent player B's turn wherever player A would use min or argmin, including in the Q-value updates - this is typically easy to add to the inner loop of Q-learning, and should improve learning efficiency (essentially you are hard-coding knowledge that this is a zero-sum game and taking advantage of that symmetry).

Both of these ideas will free you up from caring about the value of epsilon, or decaying it - you can probably just leave it fixed at e.g. 0.1

Finally, as a test of whether your agent can cope with learning optimal play in general, you could have it learn against an already optimal agent. That is obviously not something you can do for more complex games, but might help you debug agent code and hyper-parameters of the network - it divides your problem up into "can it learn this at all" and "can it learn through self-play".

• Thanks Neil, that's a lot of useful ideas! I will try to get a perfect player and test some of the things you suggested. How did you actually handle illegal moves in your TicTacToe implementation? Currently, I return a reward of -1 and the game is lost, but I saw that people also suggest to take the next best move that is legal. Any preferences ?? – Axel Jun 7 '18 at 13:16
• @Axel: There is not much benefit to teaching the agent legality of moves - it doesn't help with optimal play. So take next best. My version worked with afterstate value representation (instead of action-value representations), so the agent was not given the option to select a non-valid move. – Neil Slater Jun 7 '18 at 13:22
• My version here: github.com/neilslater/game_playing_scripts/blob/master/… - note it is also just a tabular implementation, so it uses string state summaries and enumerates all possible states – Neil Slater Jun 7 '18 at 13:23
• If this were a tabular learning scenario, how will the final Q-values look like? – pg2455 Jan 17 '19 at 13:15
• @pg2455: Too complex to answer in a comment in detail, and depends a lot on discount rate. With a discount rate of 1 (i.e. no discounting), then you end up with each state being strictly worth -1, 0 or 1, with the starting state worth 0. You could ask a new question on the site if you want more detail. – Neil Slater Jan 17 '19 at 15:10

As epsilon is throttled down networks 1 and 2 can freely specialize to producing tic-tac-toe's well-known non-losing behaviour against quasi-perfect adversaries without encoding any non-losing or winning behaviour against random (in other words, bad) adversaries. I suggest while training network 1 (1st mover) and reducing epsilon-1 you keep the 2nd mover's epsilon-2 to values distinctly above 0, indeed why not fixed. Vice-versa for training the 2nd mover.