7
$\begingroup$

I've been reading a lot about TD-Gammon recently as I'm exploring options for AI in a video-game I'm making. The video game is a turn-based positional sort of game, i.e. a "units", or game piece's, position will greatly impact it's usefulness in that board state.

To work my way towards this, I thought it prudent to implement a Neural Network for a few different games first.

The idea I like is encoding the board state for the Neural Network with a single output neuron which gives that board states relative strength compared to other board states. As I understand, this is how TD-Gammon worked.

However, when I look at other people's code and examples/tutorials, there seems to be a lot of variance in the way they represent the board-state. Even for something as simple as tic-tac-toe.

So; specifically for tic-tac-toe, which is a better, or what is the correct representation for the board state? I have seen:

  1. 9 input neurons, one for each square. A 0 indicating a free-space, -1 the opponent and 1 yourself.
  2. 9 input neurons, but using different values such as 0 for the opponent, 0.5 for free and 1 for yourself?
  3. Could you use larger values? LIke 0, 1 and 2?
  4. 27 input neurons. The first 3 being square 1, the next 3 being square 2 etc. Every neuron is 1 or 0. The first of the set of three indicates whether this square is free or not; the second indicating whether the square is occupied by your opponent or not. In the end, only one in every 3 neurons will have a 1, the other two will have a 0.
  5. 18 input neurons. The first being 1 for the X player, the second being 1 for the O player and both being 0 for a blank

Then; when branching into games where the specific pieces abilities come into play, like in chess, how would you represent this?

Would it be as simple as using higher input values for more valuable pieces? I.e. -20 for an opponents Queen and +20 for your own queen? Or would you need something more complex where you define 10+ values for each square, one for each unit-type and player combination?

$\endgroup$
3
$\begingroup$

When you are working with neural networks, as long as the data is there, the network is usually able to learn how to process it into a useful result, you usually also want to keep the amount of weights to a minimum. When you you use extra weights, it will take longer to train the network because you need to tune even more values for an optimal network. So, for tic-tac-toe, any of your solutions involving 9 inputs should work just fine. Also, it helps if you keep the inputs between 0 and 1 if you are using log sigmoid, and -1 and 1 if you are using hyperbolic tangent for your activation function. You can probably easily figure out what to use for other activation functions. You can take your data and transform it into another dataset with values within a specific range through a process called range normalization. For chess, you can simply encode every piece in several different ways, and it will probably not make that much of a difference. The general rule of thumb is you want to minimize the amount of weights while still giving the most possible variables to the network.

$\endgroup$
  • $\begingroup$ Does not creating a fully connected layer help alleviate the issue with the amount of weights that you're describing? Like the network structure in arxiv.org/pdf/1509.01549.pdf (page 21) $\endgroup$ – NeomerArcana Nov 24 '17 at 2:19
  • $\begingroup$ @NeomerArcana that may work, but you are still not getting the most efficient encoding. It would be better to just have 9 inputs, rather than have 18 in a non fully connected layer. $\endgroup$ – Aiden Grossman Nov 24 '17 at 2:53
  • $\begingroup$ and the decision to use -1, 0, 1 vs 0, 0.5, 1 is determined by the activation function in use? $\endgroup$ – NeomerArcana Nov 24 '17 at 3:13
  • $\begingroup$ @NeomerArcana yes. $\endgroup$ – Aiden Grossman Nov 24 '17 at 3:13
  • $\begingroup$ Does it matter if it's -1 is opponent, 0 free and 1 your own? As in, could -1 be free, 0 your own and 1 as your opponent work? I'm guessing it would so long as it's always consistent? $\endgroup$ – NeomerArcana Nov 24 '17 at 3:15
2
$\begingroup$

Representation of states is very important to prepare the data for neural network. You can try different way and pick which fit best in your case.

  • You can use 18 neurons as input where each state is represented by the 2 bits. But avoid 0 and 1 if you are using sigmoid activation function, which can cause saturation at the output, which means if output(y) become 1 at any layer, then on back propagating error, we have y (1-y) dE/dy in weight update part, which become zero with the saturation, which means it will stay in the same state ever.

This problem can be solved by following method:

Solution 1. You can initialize the input with some margin from 0 and 1. For example input can be [0.1, 0.9] instead for [0, 1].

Solution 2. Another you can initialize weights very small in the range of [-0.01, 0.01].

Solution 3. You can use regularization technique, whose purpose is to supress the weights by adding a penalizing term in error.

  • To handle variance problem, you can augment some data, for proper training. Because, in tic-tac-toe, you have small data set. To augment data, you can add some margin of range -0.1 to +0.1 in inputs with the same outputs.

I hope this may be helpful.

$\endgroup$
1
$\begingroup$

The basis of reinforcement learning methods is to give each (game) state (or action) a value that somehow represent how good that state (or action) is. To store these values we could use something as simple as a table/hashmap, however complex games like chess or go has so many states they cannot fit into the memory. As a remedy we think of the hashmap as a function and try to approximate it with a neural network(NN). Luckily NNs are universal approximators, which means they can learn any function, including an arbitrary mapping from a chess board to a number.

Now the question is how to represent a game board and feed it to the neural network. In the case of tic-tac-toe all 5 methods you listed can be considered correct.

Theoretically it does not matter what (w, b, v) numbers are assigned to (white, black or vacant tiles), if we teach the NN that f(w, w, v, ...) = 1 enough times, it will learn this association whether it is (w, b, v) = (0, -1, 1) or (w, b, v) = (0, 0.5, 1).

Now your first three examples uses this method, however a small flaw here is that it assigns numbers to nominal things, that is numbers can be ordered, yet we cannot really say that black > white > vacant. Your last two examples try to fix this by using one-hot-vectors.

So for a game like chess, if we used numbers simply to represent the figures the NN might mistakenly mix up two figure types (eg.: pawn is 19, queen is 20 and it thinks that a queen is trying to attack your king whereas it is just a pawn) and make a bad decision. However it will learn that the decision was bad and will assign the correct value to the state and the decision in the long run.

One last note: choosing the correct state representation for a problem is a crucial part of reinforcement learning (similar to picking the right features for a classification problem) and sometimes one might be too afraid to pick a very high dimensional state space. But remember, that chess is not a simple game so a large state space may not be unreasonable. Also for reference, Atari games were trained with an input dimension of 84*84*4.

$\endgroup$

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.