Neural networks for Spanish checkers and beyond

[Alvaro]

I know that for three decades we have had to put up with people learning a little bit about neural networks and thinking they could solve every problem, when the reality is that they rarely solved any problems. But please don't run!

It turns out there is this thing call "Deep Learning", which as far as I can tell stands for "neural networks now work", and there are all sorts of things that NNs have become good at since around 2010.

About a year ago I made a very strong Spanish checkers program using a NN as evaluation function, and I used unsupervised learning to train it. These are the steps I followed:
1) I computed 6-piece endgame tablebases, because shallow searches are not going to learn some difficult endgames, and in this particular game it is critically important to know about them in order to determine what "enough advantage to win" means in the midgame.
2) I generated a game database (1000 or so games?) using alpha-beta search with a random evaluation function.
3) I trained a NN using the game database.
4) I generated another game database using alpha-beta search with the NN plus a small random number as the evaluation function.
5) I iterated 3 and 4 (a total of 3 times, I think; I didn't keep good records) using increasingly larger and higher-quality databases, and increasingly complex NNs.

I didn't go overboard with the complexity of the NN. My final version had 121 inputs (a very raw description of the board, with booleans indicating the presence of each type of piece on each possible square, plus whose turn it is), two hidden layers with 32 ReLU units each and a single linear output (tanh might have been better?).

It's hard to test how strong the resulting program was, because high-quality games result in lots of draws, but qualitatively the games kept getting better and better. In the first batch of games the program didn't know that having more pieces than the opponent is a good thing, so it would needlessly give material away. Then it figured out more material is a good thing, but it would move pawns in the back too easily, letting the opponent get to a king without difficulty. By the end, it seemed to have at least as much positional understanding about the game as I did. I then let my friend and Spanish checkers master José Manuel Morán play against it, and his estimation was "it cannot be beaten".

The whole project took about a month. Training a simple NN like the ones I used can be done in a couple of hours in a single CPU thread. Using a GPU you can scale to much larger NNs.


==BEYOND CHECKERS==

Yes, checkers was solved by Chinook a few years ago, although the version of checkers I was dealing with is quite different. But the technique is completely general, and I managed to write a very strong engine without using any insights from human players. Can we do this for other games?

In particular, I am interested in computer go. Starting December 2014 there have been at least three papers about using NNs to predict the next move in go games by strong players (they all use convolutional neural networks):
* http://arxiv.org/abs/1412.3409
* http://arxiv.org/abs/1412.6564
* http://arxiv.org/abs/1511.06410

I have been playing around with similar ideas the last few weeks, with the ultimate goal of making a NN that can be used as an evaluation function for go (where no usable evaluation function exists).


What are other games for which evaluation functions seem difficult to write? Do you think NNs might work for them? I'll be happy to assists others in getting started with this exciting technique, if there is interest.

[Rémi Coulom]

Hi Alvaro. Thanks for your message.

For NN and Go, my impression is that it is easier to learn a policy than to learn an evaluation function. But it is interesting to try original approaches. I am looking forward to your results.

[mmKALLL]

A great read!

I've recently been playing around with the idea of having a NN capable of playing Dominion - because, why not. It's not the traditional thing that someone would try to apply a NN for, but as long as something seems interesting I'm all for trying it out. However, it's very difficult to conceive what kind of inputs such a system would use. From what I can tell, most likely splitting the turn's phases into different networks that would always nominate a single move from the available options would play best, but there are two immediate problems with this approach.

1) How would the evaluation of correct moves be done?
2) How to take into account the opponent's actions?

Unsupervised learning would be nice, but I don't even know if there's a database of games by strong players to compare against. Just having the NNs play against each other seems inefficient. For the second one, generally from intermediate level onwards the strategy involves trying to gain an edge by selecting actions which will hinder the opponent's buildup specifically, or decrease the edge of actions they previously have selected. Of course, an AI will be able to correctly keep track of the contents of an opponent's discard pile and deck, but I don't quite see how to utilize that information.

Just trying to implement the effects of all cards - even in just the base set - seems fairly cumbersome, and there definitely are a bunch of challenges related to the strategy. Any insight?

[cabernet]

Hi Alvaro,

my post is a little bit off-topic but I can't find your's contact anywhere so I write here. My question is about compressing your's checkers database. I suppose you put a lot of time on it and now I handle very similar problem. It would be great if you share your conclusions, what compression technique you finally used and so on. Many thanks!

[Alvaro]

I sent you a PM.