29

I want to program a chess engine which learns to make good moves and win against other players. I've already coded a representation of the chess board and a function which outputs all possible moves. So I only need an evaluation function which says how good a given situation of the board is. Therefore, I would like to use an artificial neural network which should then evaluate a given position. The output should be a numerical value. The higher the value is, the better is the position for the white player.

My approach is to build a network of 385 neurons: There are six unique chess pieces and 64 fields on the board. So for every field we take 6 neurons (1 for every piece). If there is a white piece, the input value is 1. If there is a black piece, the value is -1. And if there is no piece of that sort on that field, the value is 0. In addition to that there should be 1 neuron for the player to move. If it is White's turn, the input value is 1 and if it's Black's turn, the value is -1.

I think that configuration of the neural network is quite good. But the main part is missing: How can I implement this neural network into a coding language (e.g. Delphi)? I think the weights for each neuron should be the same in the beginning. Depending on the result of a match, the weights should then be adjusted. But how? I think I should let 2 computer players (both using my engine) play against each other. If White wins, Black gets the feedback that its weights aren't good.

So it would be great if you could help me implementing the neural network into a coding language (best would be Delphi, otherwise pseudo-code). Thanks in advance!

bias
  • 1,467
  • 3
  • 19
  • 39
caw
  • 30,999
  • 61
  • 181
  • 291
  • Thanks for your answers so far. I realized that it is difficult or impossible to play chess by neural networks. But a second part of my question was: How do you code a neural network (for example my configuration)? I've no idea so I look forward to get some proposals. – caw Apr 16 '09 at 22:34
  • There needs to be an updated answer on this as the SOTA has significantly changed since 2009! It certainly is possible to learn to play Chess using a deep NL mixed in with reinforcement learning! – Keir Simmons Mar 02 '17 at 05:02
  • @KeirSimmons You're welcome to post one, or add a bounty. – Bernhard Barker Nov 29 '17 at 08:19
  • I wanna point out that one neuron to indicate the player who has to move isn't a great idea, you'll face some problem beacause the evaluation of the boards won't be even. I suggest you invert all the value of the board if it's black turn so it won't consider black and white but rather the player and the oponent. – Super Toto Jul 03 '20 at 13:19

8 Answers8

14

In case somebody randomly finds this page. Given what we know now, what the OP proposes is almost certainly possible. In fact we managed to do it for a game with much larger state space - Go ( https://deepmind.com/research/case-studies/alphago-the-story-so-far ).

Tsundoku
  • 2,455
  • 1
  • 19
  • 31
siemanko
  • 1,389
  • 1
  • 13
  • 26
12

I don't see why you can't have a neural net for a static evaluator if you also do some classic mini-max lookahead with alpha-beta pruning. Lots of Chess engines use minimax with a braindead static evaluator that just adds up the pieces or something; it doesn't matter so much if you have enough levels of minimax. I don't know how much of an improvement the net would make but there's little to lose. Training it would be tricky though. I'd suggest using an engine that looks ahead many moves (and takes loads of CPU etc) to train the evaluator for an engine that looks ahead fewer moves. That way you end up with an engine that doesn't take as much CPU (hopefully).

Edit: I wrote the above in 2010, and now in 2020 Stockfish NNUE has done it. "The network is optimized and trained on the [classical Stockfish] evaluations of millions of positions at moderate search depth" and then used as a static evaluator, and in their initial tests they got an 80-elo improvement when using this static evaluator instead of their previous one (or, equivalently, the same elo with a little less CPU time). So yes it does work, and you don't even have to train the network at high search depth as I originally suggested: moderate search depth is enough, but the key is to use many millions of positions.

Silas S. Brown
  • 1,469
  • 1
  • 17
  • 18
  • A problem with this approach is, if you use a minimax and alpha-beta pruning heuristic, you already accept that your NN is inferior to your evaluator. Now I agree it is cool to do so just to have a chess playing NN, the practical benefit (except for the experience you'll get) wouln't be much. – Atilla Filiz Jul 11 '16 at 16:50
  • 3
    @AtillaFiliz No. A manual (written by a programmer) evaluator + deep search get used to train the NN in the hope that the NN + shallow search outperform manual evaluator + shallow search. If it works, then the NN is better than the manual evaluator. – maaartinus Oct 02 '16 at 23:48
6

It is possible, but not trivial by any means.

https://erikbern.com/2014/11/29/deep-learning-for-chess/

To train his evaluation function, he utilized a lot of computing power to do so.

To summarize generally, you could go about it as follows. Your evaluation function is a feedforward NN. Let the matrix computations lead to a scalar output valuing how good the move is. The input vector for the network is the board state represented by all the pieces on the board so say white pawn is 1, white knight is 2... and empty space is 0. An example board state input vector is simply a sequence of 0-12's. This evaluation can be trained using grandmaster games (available at a fics database for example) for many games, minimizing loss between what the current parameters say is the highest valuation and what move the grandmasters made (which should have the highest valuation). This of course assumes that the grandmaster moves are correct and optimal.

sma
  • 315
  • 3
  • 6
6

Been there, done that. Since there is no continuity in your problem (the value of a position is not closely related to an other position with only 1 change in the value of one input), there is very little chance a NN would work. And it never did in my experiments.

I would rather see a simulated annealing system with an ad-hoc heuristic (of which there are plenty out there) to evaluate the value of the position...

However, if you are set on using a NN, is is relatively easy to represent. A general NN is simply a graph, with each node being a neuron. Each neuron has a current activation value, and a transition formula to compute the next activation value, based on input values, i.e. activation values of all the nodes that have a link to it.

A more classical NN, that is with an input layer, an output layer, identical neurons for each layer, and no time-dependency, can thus be represented by an array of input nodes, an array of output nodes, and a linked graph of nodes connecting those. Each node possesses a current activation value, and a list of nodes it forwards to. Computing the output value is simply setting the activations of the input neurons to the input values, and iterating through each subsequent layer in turn, computing the activation values from the previous layer using the transition formula. When you have reached the last (output) layer, you have your result.

Robert Harvey
  • 178,213
  • 47
  • 333
  • 501
Varkhan
  • 16,601
  • 5
  • 31
  • 24
  • 5
    But TD-Gammon learnt to play Backgammon using only a neural network, too. So it has to work somehow, hasn't it? – caw Apr 15 '09 at 23:07
  • 1
    Blackgammon is a very different game from Chess... it replaces rule complexity and wide branching of possibilities with randomness. But NN are very good at dealing with statistical prediction, not so at pruning the tree of possible solutions. – Varkhan Apr 15 '09 at 23:30
  • Continuity wouldnt be a problem with enough internal nodes (for a back-prop NN) and training data. The trouble is that the number of nodes and amount of training required would make it infeasible. I agree that a NN is a bad solution to the problem. – geofftnz Apr 16 '09 at 00:47
  • So you would say that it isn't possible to play chess using artificial neural networks, at least using my network configuration? – caw Apr 16 '09 at 19:42
  • Let's say, I would be surprised if you managed to make it play properly. NN are very well suited to numeric filtering tasks, where you need to take decisions based on some data that is numeric, and semi-continuous. They do not perform well on symbolic, discrete data like board configurations. – Varkhan Apr 16 '09 at 20:16
  • OK, thanks! Thus it would probably not work well. But I would like to test it, though. So I would be very happy about some coding tips or examples. – caw Apr 16 '09 at 22:48
  • 3
    downvote because the answer only focuses on feedforward networks. There are dozens of different models today. Convolution Neural Networks for example should work for pattern recognition in chess which can give you solutions for some configurations. After all Recurrent Neural networks are touring complete and therefore can play chess in theory. – Benedikt S. Vogler Feb 28 '17 at 19:37
  • 1
    Alpha Zero and Leela Zero which are based on NNs and outperforms all classical chess engines proves this answer wrong. – user1066278 May 21 '20 at 18:40
4

What you need to train a ANN is either something like backpropagation learning or some form of a genetic algorithm. But chess is such an complex game that it is unlikly that a simple ANN will learn to play it - even more if the learning process is unsupervised.

Further, your question does not say anything about the number of layers. You want to use 385 input neurons to encode the current situation. But how do you want to decide what to do? On neuron per field? Highest excitation wins? But there is often more than one possible move.

Further you will need several hidden layers - the functions that can be represented with an input and an output layer without hidden layer are really limited.

So I do not want to prevent you from trying it, but chances for a successful implemenation and training within say one year or so a practically zero.

I tried to build and train an ANN to play Tic-tac-toe when I was 16 years or so ... and I failed. I would suggest to try such an simple game first.

Svante
  • 50,694
  • 11
  • 78
  • 122
Daniel Brückner
  • 59,031
  • 16
  • 99
  • 143
  • The neural network should only evaluate a position. The other functions compute all possible moves. Then for every move, the resulting position is given to the neural network which gives a numerical value as the evaluation. For example, White would rather take a move leading to 4.5 than -6.2. – caw Apr 15 '09 at 22:46
  • As Varkhan pointed out, that score function will be very wavy and is very hard to represent with an ANN. – Daniel Brückner Apr 15 '09 at 22:55
  • I cannot program Tic-tac-toe, either. I lack the know-how. Therefore I asked here how to implement such a neural network. In my opinion, a neural network is a quite abstract thing. I can imagine how it would work, but I have no idea how to code that. So I hope someone here can help me. – caw Apr 15 '09 at 22:57
4

The main problem I see here is one of training. You say you want your ANN to take the current board position and evaluate how good it is for a player. (I assume you will take every possible move for a player, apply it to the current board state, evaluate via the ANN and then take the one with the highest output - ie: hill climbing)

Your options as I see them are:

  • Develop some heuristic function to evaluate the board state and train the network off that. But that begs the question of why use an ANN at all, when you could just use your heuristic.

  • Use some statistical measure such as "How many games were won by white or black from this board configuration?", which would give you a fitness value between white or black. The difficulty with that is the amount of training data required for the size of your problem space.

With the second option you could always feed it board sequences from grandmaster games and hope there is enough coverage for the ANN to develop a solution.

Due to the complexity of the problem I'd want to throw the largest network (ie: lots of internal nodes) at it as I could without slowing down the training too much.

geofftnz
  • 9,954
  • 2
  • 42
  • 50
  • Thanks. I've already tested that. It would work but you would need an unimaginable amount of training data - as you already wrote. In chess, there are about 2,28x10^46 possible positions, so you would never have enough training data for each position. – caw Apr 16 '09 at 18:51
  • 2
    Yes, although the idea of a neural network is that it should be able to generalise given a limited training set. A lot depends on the complexity of the function you are trying to fit, which in the case of chess will be insane. – geofftnz Apr 16 '09 at 21:12
  • OK, you've convinced me. But how could you code it, though? I would love to test it, although I know now that my engine will never be a pro player. – caw Apr 16 '09 at 22:49
1

Your input algorithm is sound - all positions, all pieces, and both players are accounted for. You may need an input layer for every past state of the gameboard, so that past events are used as input again.

The output layer should (in some form) give the piece to move, and the location to move to.

Write a genetic algorithm using a connectome which contains all neuron weights and synapse strengths, and begin multiple separated gene pools with a large number of connectomes in each.

Make them play one another, keep the best handful, crossover and mutate the best connectomes to repopulate the pool.

0

Came here to say what Silas said. Using a minimax algorithm, you can expect to be able to look ahead N moves. Using Alpha-beta pruning, you can expand that to theoretically 2*N moves, but more realistically 3*N/4 moves. Neural networks are really appropriate here.

Perhaps though a genetic algorithm could be used.

Steve Pierce
  • 322
  • 2
  • 9