1
$\begingroup$

I've recently become interested in machine learning, specifically neural networks, and after creating ones to solve basic problems such as XOR and Sin and Cos graphs, however i am now looking into reinforcement learning and specifically q learning with neural networks, to try this out and see if i could implement this, i used a q learning neural network for tic tac toe. However I am unsure as to why my program does not learn correctly. One idea I have is that i have implemented the input neurons incorrectly.I am using visual basic console application so just let me know if you need me to post any code

My view on how to implement this:

Use 18 input neurons and have the first 9 being the state before placing a move, and the next 9 being the state after placing a move.

another question I have in terms of when you teach the neural network, would you feed it the old state and then the state after both you and the opponent have made a move?al networks, so they can play against each other and teach themselves

Second Problem

This next potential problem i have is how I use my threshold and exploration values to choose whether to pick a random action or one the neural network chooses. I increase my threshold linearly from 0 to 1 throughout the iterations. while exploration is a random value between 0 and 1. is this correct? or is there a better way of doing it?

Any feedback would be greatly appreciated, and if anyone has any problems with my question such as it being unclear, not making sense or anything else please let me know so i can fix it

thank you for all who take the time out to try and help.

$\endgroup$
  • $\begingroup$ Thank you very much for the feedback! I will update the question now to be more focused on specific points. $\endgroup$ – Peter Jamieson Jan 12 '18 at 13:39
  • $\begingroup$ I've answered the first question, but don't understand the second one. As my answer is already long enough IMO, I recommend you move the "Second Problem" part to a new question. However, it is also quite hard to understand. I have no idea what you mean by "threshold" value - so it may be a good idea to explain more about your understanding of threshold and exploration value? $\endgroup$ – Neil Slater Jan 12 '18 at 14:58
0
$\begingroup$

One idea I have is that i have implemented the input neurons incorrectly.

There is no single correct way to implement the solution to this problem. There are less efficient and more efficient ways for specific problems.

Use 18 input neurons and have the first 9 being the state before placing a move, and the next 9 being the state after placing a move.

This should work. The first set of 9 neurons will receive a representation of the current game state. The second set of 9 neurons will receive a representation of the intended action.

For predicting Q values from a state, action pair, this is a reasonable approach. Staying with the same architecture of 18 inputs, you could also have the second set of neurons be one-hot encoded to where the agent will to place the 'X' or 'O'.

In the game Tic Tac Toe however, you can look for more compact representations if you like. You have already noticed that because the game is simple and deterministic, that you can represent the agent's action as simply "desired next state". And in fact, the current state does not actually matter to a player, other than to enforce the rules of what are valid next states.

You won't be implementing the rules of the game into the agent - they are part of the environment. Therefore, you can do away with the initial state altogether in your estimate, and work with the end state of each move - this is called the afterstate in the RL literature, and you will find it used a fair bit in deterministic games, or even in non-deterministic games where the randomness happens before the action choice (e.g. in Backgammon). An afterstate representation is more efficient because it encodes the fact that you don't care what route a player took to get to certain board position, you just care about the value of that position as the game continues.

Having said all that, if your goal is to learn basic RL, then you don't need to be looking for the most efficient solution, just one that works. Don't expect your NN-based learner with state-action logic to be the most efficient learner however.

Another question I have in terms of when you teach the neural network, would you feed it the old state and then the state after both you and the opponent have made a move?

Not as inputs to the network at the same time, no. In your (state, action [=next_state]) representation, your action representation should be the board state for the current player's move and before the other player takes any action. The resulting next state however, will be after the other player takes their action.

If you want to train two separate bots against each other, then each would see the current state, then it would choose an action, then it would either get the reward for winning, or the opponent would take a turn. If the opponent won, then the first bot should receive the (negative) reward. If the opponent's move was not final, then the first bot should see the state after the opponent's move and get to choose its next action.

Again, this is inefficient. For a win/draw/lose game like Tic Tac Toe, you don't need two separate agents, each with their own learning algorithm, in order to train through self-play. You can instead alter Q-Learning slightly to work with the minimax algorithm. In brief this means alternating between the agent selecting actions that maximise the expected reward (for player 1) or minimise it (for player 2).

However, like before, your 2 networks set up should be able to work, and is quite interesting dynamic - you could try different learning parameters, different NNs etc, and see which learns to win quickly (but don't forget starting player has an advantage for early random play, so you'd want to switch which learning algorithm was used for which player to get a fair assessment).

The difference again is in terms of efficiency - a single network inside a modified RL with minimax will typically learn faster that two separate networks.


I have implemented a simple tabular (i.e. no neural networks) Q-Learning based agent for Tic Tac Toe in Python. It uses afterstate representation and modified Q learning with minimax, and learns purely online through repeated self-play.

$\endgroup$
  • $\begingroup$ Thank you a lot this is very helpful! MI i have found another problem which is whether i should be increasing the threshold linearly from 0 to 1 throughout the iterations, because the error appears random, but becomes more accurate at the very end which is because the threshold is so high that it stops picking random actions, however this leaves the game states being saved to just be replays of the same game for some reason, and that it really hasn't learnt, but just learnt the one game set. $\endgroup$ – Peter Jamieson Jan 12 '18 at 17:50
  • $\begingroup$ Do you have any solutions or suggestions as to how to implement the threshold and if you can think of any other mistakes i may have made? $\endgroup$ – Peter Jamieson Jan 12 '18 at 17:50
  • $\begingroup$ @PeterJamieson: This answer is already quite long. Please read my comment on the question. I suggest you ask a new question about "thresholds" and also give some kind of additional explanation about what you mean because that's not something that has a standard meaning in RL (although it may relate to something standard in RL, just you are using an unusual term for it) $\endgroup$ – Neil Slater Jan 12 '18 at 18:24
  • $\begingroup$ Thank you again for the advice, I am still new to this! And yes i think the threshold is a neural network - q learning specific thing so most people probably wont know what i mean by it $\endgroup$ – Peter Jamieson Jan 12 '18 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.