How do neural networks play chess?

Question

I have been spending a few days trying to wrap my head around how and why neural networks are used to play chess.

Although I know very little about how the game of chess works, I can understand the following idea. Theoretically, we could make a "tree" that included every possible outcome of a chess game. Through knowledge provided by chess experts, we could identify how "favorable" certain parts of this tree are compared to other parts of the tree. We could also use this tree to "rank" optimal chess moves based on how the chess board appears in the current turn (e.g. which pieces you and your opponent have left and where these pieces are situated).

The problem is, this tree would be so enormous that it would be impossible to create, store and "search" (e.g. with the MinMax algorithm):

I understand that perhaps this tree can be created using data to limit the size of the tree based on scenarios that are more likely to appear compared to all possible scenarios. For example, if a player wanted they could spend the whole game aimlessly shifting their "Rook" back and forth - theoretically, this outcome could occur but no player (in their sane mind) would ever do this. Thus, the tree could be constructed using actual data from millions of chess games. This for example could tell us : Based on historical data and given the current setup of the chess board, 21% of games were won when the immediate next move involved moving the Queen to "F5" vs only 3% of games were won when the immediate next move involved moving the Knight to "F5". I suppose at each move, the data based tree could be queried to rank the optimality of each next move by checking the proportion of "terminal nodes" that resulted in wins for each possible move given the current chess board.

However, I still see 2 problems with this approach:

• It is possible that we might run into a scenario(s) that never occurred within the historical data, rendering the tree useless in this scenario

• This tree still might be too large to efficiently store and query.

This is probably why neural networks are being used to play chess - I tried to do some readings about this topic, but I can't seem to fully understand it. In this case, what exactly would the neural network use as a loss function? I don't see how the loss function in this case is continuous, and thus how could gradient descent be used on such a loss function?

Could someone please recommend some sources (e.g. YouTube Videos, Blogs, etc.) that show how a neural network can be used to play chess.

Answer 1

Minimax and related algorithms are used to play chess. That is how chess programs have worked for many years (with some additions such as standard opening playbooks). They do not need to process the whole game tree. There are a few different techniques used to reduce the effective search space. One of the most the most impactful is to truncate search after a certain depth if it has not resolved the game, and to score the position reached using some form of heuristic function that takes the board state as input and outputs a number. The impact from this has two parts:

• The search space is reduced by a large factor.

• The strength of the resulting automated player is limited by how effective the heuristic is at reflecting the strength of the game position. A perfect heuristic could allow a very limited search (just one ply look ahead, or up to some point within the game) to play perfectly. However, it is a practical impossibility for many games - if a game is "unsolved" that means by extension that there is no known perfect heuristic.

There are other ways to reduce search space or search it more efficiently, but this search depth plus heuristic pattern is very common in turn-based games. This is how IBM's Deep Blue worked for example, and it did not use neural networks. The heuristic function in Deep Blue was constructed by experts extending already well-studied basics of chess playing, such as assigning simple points value to each side's remaining pieces (e.g. a rook is worth more than a bishop).

What exactly would the Neural Network use as a Loss Function?

There are two main ways that a neural network can be applied in a game like chess:

1. To predict the chances of winning from a given position

(or equivalently score a heuristic for the position)

In reinforcement learning terms, this would be the value function for that state (game position).

This can be used alongside tree searches, the main difference being that instead of an expert designing the heuristic, the neural network will have learned one from observing games. Those games could be a database of games played by humans, or generated by a learning agent playing against itself.

The loss function that drives learning here would typically be a cross-entropy loss comparing the eventual win/loss with the predicted probability. This is noisy of course, because the same position may lead to win, draw or loss depending on relative strengths of the players. However, as the agent player becomes stronger, the prediction will start to match it, and more closely approximate the probabilities from optimal play.

2. To predict the best move from a given position

This is also called a policy function.

This is a multi-class prediction problem, that would use the normal multiclass log loss function. Similar to learning the value function, it can be learned from observation assuming all action choices that lead to a win are the best choices. Again this is noisy, but should converge on an approximation of optimal play provided the input is from master-level play database, or is from a working self-play system.

I don't see how the Loss Function in this case is continuous, and thus how could Gradient Descent be used on such a Loss Function?

Once you move away from trying to have the neural networks process a game tree directly, the problem becomes clearer. You need to run the game tree processing using suitable tree search algorithm (minimax, negamax, MCTS etc), and have neural networks for the value and/or policy function estimations at each node, which they can learn from any relevant data.

If you want to create self-learning agents, as opposed to training them from a pre-existing database of games, then you will need to study systems that can generate suitable data from experiencing game play directly. This adds another outer layer of logic alongside the tree search algorithm that helps decide what data to collect and how to score it so it can be used as training data for the neural networks.

There is quite a lot you could study about these kinds of learning systems. I recommend for the basics that you look into reinforcement learning (RL), and the go-to book for many people there is Sutton & Barto's Reinforcement Learning: An Introduction, which lays out the theory and terminology used in RL and a variety of basic learning algorithms. It would be a diversion from building a game-playing program to study it all, and it does not delve into all elements of game-playing agents in great detail, but it is IMO a very good grounding into the learning parts of any such agent.

In addition, one state-of-the-art self-play learning algorithm is Deep Mind's Alpha Zero. It might be a bit of a steep learning curve to dive straight into how it works, but the algorithm is at its core surprisingly simple and elegant. It may be possible, given some basic knoweldge of terms from RL (so you know what a policy is), to get straight into it based on some tutorials like this one that learns Othello.

Answer 2

This is a good question. your understanding in general is correct. Indeed, data can be used to construct a proper evaluation of a move/board position and recommended moves based on its history (at least alphago does).

Regarding your first point, it is possible that scenarios that never occurred in historical data could occur, but that's not a problem if your valuation procedure is strong. Typically this is modeled by some continuous function that takes your input board and gives some scalar value. Doing so implicitly assumes you learn the patterns among data pretty well so that ideally you can extrapolate sufficiently in new scenarios. If you had used a lookup table for every board state, you would be screwed in both of the respects you mentioned above.

Regarding your second point, problems related to storing the tree itself and efficiently querying has other solutions that essentially involve a clever pruning method (minimax, and its variants) and/or an efficient cache, like zobrist hashing (see chessprogramming wiki for more techniques).

Now to the core of the question, how do you evaluate and setup a loss function? There are several ways to do this though: roughly you can think about this as falling into the following buckets

• (i) a reinforcement learning approach, which Alphago uses (https://www.chess.com/article/view/whats-inside-alphazeros-brain) . This is interesting because RL is quite a different paradigm of learning than supervised learning. I'd recommend reading through some of sutton/barto (http://www.incompleteideas.net/book/the-book-2nd.html) to see how questions of policy learning and move recommendations can be derived in general; this is quite a readable book. Then read about alphazero and alphago https://www.science.org/doi/10.1126/science.aar6404.

• (ii) supervised learning. When I initially tried this out, I trained a neural net to output a value at least as good as the moves outputted by a grandmaster (see Should I use neural networks or genetic algorithms to solve Gomoku? for more details). Another way can be based on whether the player won or lost at the end, assuming that in general their moves were better when they won than when they lost (a little strong of an assumption to me personally). See https://www.cs.tau.ac.il/~wolf/papers/deepchess.pdf - They randomly sample moves from a game white won and lost, and learns to choose between the moves with a neural network.

To be explicit, once you setup the appropriate loss or policy optimization problem, you can perform gradient descent as usual. what you are optimizing would of course differ based on if you choose the RL route or the supervised learning route.

Since this is in the first part of your question, I will additionally say that NNs help in chess because of this complex problem of how to valuate a position based on some unique progression and state of the game, and the combinatorial explosion (which is somewhat rectified by a move recommender in alphago, and/or intuitively to me, better evaluating positions may allow for more robust move selection given less plies). Without a NN, some more static evaluator or less complex function approximator may be too simplistic for robustly learning `good moves' in chess.

It is interesting to see that some methods do not require you to actually encode which moves are legal and which are not.