How to teach neural network a policy for a board game using reinforcement learning?

Question

I need to use reinforcement learning to teach a neural net a policy for a board game. I chose Q-learining as the specific alghoritm.

I'd like a neural net to have the following structure:

1. layer - rows * cols + 1 neurons - input - values of consecutive fields on the board (0 for empty, 1 or 2 representing a player), action (natural number) in that state
2. layer - (??) neurons - hidden
3. layer - 1 neuron - output - value of action in given state (float)

My first idea was to begin with creating a map of states, actions and values, and then try to teach neural network. If the teaching process would not succeed I could increase the number of neurons and start over.

However, I quickly ran into performance problems. Firstly, I needed to switch from simple in-memory Python dict to a database (not enough RAM). Now the database seems to be a bottleneck (simply speaking there are so many possible states that the retrieval of actions' values is taking a noticeable amount of time). Calculations would take weeks.

I guess it would be possible to teach neural network on the fly, without the layer of a map in the middle. But how would I choose a right number of neurons on the hidden layer? How could I figure out that I'm loosing periously saved (learned) data?

Answer 1

You need to use some function approximation scheme. In addition, experience replay would be useful for two reasons: (1) you want to keep past memories (2) you need to decorrelate the way to teach your network.

Have a look at Deepmind's DQN on ATARI games. What you are describing is basically what they have solved. The paper is in their website: http://deepmind.com/dqn.html

Mnih V, Kavukcuoglu K, Silver D, Rusu AA, Veness J, Bellemare MG, et al. Human-level control through deep reinforcement learning. Nature. 2015 Feb 25;518(7540):529–33.

With respect to the network architecture, it will definitely require some experimentation. For an alternative, you can also have a look at HyperNEAT. They evolve the network topology:

Hausknecht M, Khandelwal P, Miikkulainen R, Stone P. HyperNEAT-GGP: A HyperNEAT-based Atari general game player. In: Proceedings of the 14th annual conference on Genetic and evolutionary computation p. 217–24. Available from: http://dl.acm.org/citation.cfm?id=2330195

For more strategic games. Maybe you can have a look at "Giraffe: Using Deep Reinforcement Learning to Play Chess" http://arxiv.org/abs/1509.01549

Answer 2

In order to train an agent to play a board game, the first important task is to create a Reinforcement Learning environment.

4 essential aspects of an environment is:

• Observation space: What is the input/state, as well as its shape and range?
• Action space: What is the possible action, as well as its shape and range?
• Reward function: What is the reward for a particular pair of state + action? Will it be immediate or sparse reward? The reward function will affect the difficulty of the environment a lot.
• When will an episode/a game end?

I highly suggest using the same API as OpenAI Gym because of its popularity and high-quality. Then you can try to apply direct these algorithms before trying on your own. They are state-of-the-art algorithms and the quality is guaranteed.

About the neural network architecture, you can exploit the nature of the game for better result.

For example, in Go, the position is symmetric and the actions are simple and position-independent, which is very suitable to use convolutional neural network (AlphaGo Zero).

On the other hand, in Chess, because the actions are asymmetric and position-dependent, Google had to redesign the architecture to train an agent to play chess.