How should I represent the input to a neural network for the games of tic-tac-toe, checkers or chess?

Question

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 its 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 state 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 indicates 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 indicates 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?

Answer 1

When you are working with neural networks, as long as the data is there, the neural network is usually able to learn how to process it into a useful result.

However, you usually also want to keep the number of weights to a minimum. When 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 number of weights while still giving the most possible variables to the neural network.

Answer 2

The basis of reinforcement learning methods is to give each (game) state (or action) a value that somehow represents 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 chessboard 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 use 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.: a pawn is 19, the 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.

Answer 3

Representation of states is very important to prepare the data for the neural networks. You can try a 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 the output(y) becomes 1 at any layer, then on backpropagating 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 the 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 the regularization technique, whose purpose is to suppress the weights by adding a penalizing term in error.

• To handle variance problems, you can augment some data, for proper training. Because, in tic-tac-toe, you have a 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.