On 7 Dec 2017 DeepMind's AlphaZero (AZ) v Stockfish (SF8) chess match hit headlines round the world. No-expense-spared deep AI v a strong traditional open-source chess engine and AZ won convincingly. SF8 was not optimised and had a fixed time imposed on it, however AZ played some astonishing chess and is almost certainly the most powerful chess-playing entity ever created. I know a bit about chess, and a bit about ANNs. Chess using artificial neural networks is not new and has an interesting history (Giraffe). Maybe playing around with chess would be a good way to resharpen my ANN teeth.
Big thanks to: Chessboard js (the board), Chess.js (move validation, event detection), Chess Programming Wiki (a vast gold-mine of info and discussion, sadly soon to close).
Random-move games were the initial fodder for AlphaZero's network training. They result in approx 80% draw, 10% win for white, and 10% win for black. AZ apparently trained in 4 hours— but that was using hugely expensive custom hardware and has been calculated as the equivalent of 170 years on a normal high-end PC. AZ is not, and may never be, accessible to the public.
A function which takes a static board position and returns a value representing white / black advantage. This can consider:
The game-tree is a set of nodes with evaluation values. To create this you recursively search the tree of possible moves (including replies from the opponent) to the required depth (ply). fn board-evaluation is called for each node and the maximum value of evaluation is marked as best move.
Chess typically has 30-40 possible moves at any one time. So about 35ply moves are added with each ply. This is disconcertingly exponential: 1.4 million at 4 ply, and 1.8 trillion at 6 ply. There are around 1044 possible games of chess!
So, at lower ply poor evaluations are pruned - assuming that they are unlikely to transform into better evaluations later on.
The balance between deeper ply and excessive pruning is critical. Max ply is the horizon beyond which the software is ignorant. But excessive pruning might mean missing very strong moves that happen to be preceded by weak ones.
ANNs have been used for board evaluation. In one interesting study convolutional networks trained on grids containing individual piece types. The trained ANN, unfortunately, was assessed by how well it predicted test-game outcomes (which are susceptible to playing errors) rather than by embedding the ANN in a chess-engine and playing a series against a traditional engine.
These two programs have demonstrated that ANN self-reinforced learning works spectacularly well, but it remains a daunting task and Joe Public isn't able to play against programs like AZ which only run on one-off specialised hardware.
For us mere mortals with desktop PCs, the best option looks like some sort of hybrid approach: maybe using embedded ANNs, trained on specific game-features, to augment the traditional approach.