11
$\begingroup$

I'm wondering how to train a neural network for a round based board game like, tic-tac-toe, chess, risk or any other round based game. Getting the next move by inference seems to be pretty straight forward, by feeding the game state as input and using the output as the move for the current player. However training an AI for that purpose doesn't appear to be that straight forward, because:

  1. There might not be a rating if a single move is good or not, so training of single moves doesn't seem to be the right choice
  2. Using all game states (inputs) and moves (outputs) of the whole game to train the neural network, doesn't seem to be the right choice as not all moves within a lost game might be bad

So I'm wondering how to train a neural network for a round based board game? I would like to create a neural network for tic-tac-toe using tensorflow.

$\endgroup$
10
$\begingroup$

Great question! NN is very promising for this type of problem: Giraffe Chess. Lai's accomplishment was considered to be a pretty big deal, but unfortunately came just a few months before AlphaGo took the spotlight. (It all turned out well, in that Lai was subsequently hired by DeepMind, although not so well for the Giraffe engine;)

I've found Lai's approach to be quite helpful, and it is backed by solid results.


You may want to use "sequential" as opposed to "round based" since sequential is the preferred term in Game Theory and Combinatorial Game Theory, and these are the fields that apply mathematical analysis to games.

The games you list are further termed "abstract" to distinguish them from modern strategy boardgames, or games in general, which utilize a strong theme and are generally less compact than abstract games in terms of mechanics and elements. This carries the caveat that abstract games are not restricted to sequential games or boardgames, or even games specifically, as in the case of puzzles like Sudoku.

The formal name for this group of games is generally "partisan, sequential, deterministic, perfect information" with the further categorization of Tic-Tac-Toe as "trivial" (solved and easily solvable) and non-trivial (intractable and unsolved) for games like Chess and Go.

$\endgroup$
7
$\begingroup$

I'm a chess player and my answer will be only on chess.

Training a neutral network with reinforcement learning isn't new, it has been done many times in the literature.

I'll briefly explain the common strategies.

  • The purpose of a network is to learn position evaluation. We all know a queen is stronger than a bishop, but can we make the network know about it without explicitly programming? What about pawn structure? Does the network understand how to evaluate whether a position is winning or not?

  • Now, we know why we need the network, we'll need to design it. The design differs radically between studies. Before deep learning was popular, people were using shallow network. Nowadays, a network with many layers stands out.

  • Once we have the network, you'll need to make a chess engine. Neural network can't magically play chess by itself, it needs to connect to a chess engine. Fortunately, we don't need to write position evaluation code because the network can do that for us.

  • Now, we have to play games. We could start with some high quality chess databases or instead have our AI agent play games with another player (e.g. itself, another AI agent, or a human). This is known as reinforcement learning.

  • While we play games, we update the network parameter. This can be done by stochastic gradient descent (or other similar techniques). We repeat our training as long as we want, usually over millions of iterations.

  • Finally, we have a trained neutral network model for chess!

Look at the following resources for details:

https://chessprogramming.wikispaces.com/Learning

$\endgroup$
  • $\begingroup$ Only smallchess has it here $\endgroup$ – quintumnia May 20 '17 at 21:46
  • $\begingroup$ This is an example of how providing an external link, without summarizing, can be damaging in the future. As the link provided is now dead $\endgroup$ – Greg Hilston May 6 at 15:10
4
$\begingroup$

I think you should get familiar with reinforcement learning. In this field of machine learning the agent interacts whit its environment and after that the agent gets some reward. Now, the agent is the neural network the environment is the game and the agent can get a reward +1 if it wins or -1 if loses. You can use this state, action, reward experienc tuple to train the agent. I can recommend David Silver's lectures on youtube and Sutton's book as well.

$\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.