Neural network chess computer abandons brute force for selective, ‘human’ approach
Mon 14 Sep 2015
A chess computer has taught itself the game and advanced to ‘international master’-level in only three days by adopting a more ‘human’ approach. Mathew Lai, an MsC student at Imperial College London, devised a neural-network-based chess computer dubbed Giraffe [PDF] – the first of its kind to abandon the ‘brute force’ approach to competing with human opponents in favour of a branch-based approach whereby the AI stops to evaluate which of the calculated move branches that it has already made are most likely to lead to victory.
Most chess computers iterate through millions of moves in order to select their next position, and it was this traditional ‘depth-based’ approach that led to the first ground-breaking robot>human chess victory in 1997, when IBM’s Big Blue beat reigning world champion Garry Kasparov.
Lai sought instead to create a more evolutional end-to-end AI, building and improving on previous efforts which sought to leverage neural networks, but which paid performance penalties, and faced logical issues about which of the potential millions of ‘move branches’ to explore efficiently.
In the mid-1990s Sebastian Thrun at the University of Bonn in Germany developed the ‘NeuroChess’ entity [zipped postscript], which sought to improve on the basis of recursive evaluation functions (as opposed to move-crunching, which simply pits CPU cycles against human ingenuity). Thrun noted in his paper on the project: ‘Currently, NeuroChess does a poor job, because it spends most of its time computing board evaluations. Computing a large neural network function takes two orders of magnitude longer than evaluating an optimized linear evaluation function (like that of GNU-Chess).’
The network architecture behind Mathew Lai’s ‘Giraffe’ chess AI.
The lag between depth-based ‘move-crunching’ and neural-based branch evaluation has not completely closed, and Giraffe cannot perform yet at either the same level or with the same latency as traditional depth-based chess engines. Instead Lai envisions Giraffe as a seminal project on a new, or newly-revived, technological path for chess AI:
’With all our enhancements, Giraffe is able to play at the level of an FIDE International Master on a modern mainstream PC. While that is still a long way away from the top engines today that play at super-Grandmaster levels, it is able to defeat many lower-tier engines, most of which search an order of magnitude faster. One of the original goals of the project is to create a chess engine that is less reliant on brute-force than its contemporaries, and that goal has certainly been achieved.’
Quiescent search as resolution for the ‘horizon effect’
‘Example of nodes searched by depth-limited search vs probability-limited search’ – ‘Giraffe: Using Deep Reinforcement Learning to Play Chess’ by Mathew Lai, September 2015
The ‘search tree’ for chess – the potential network of paths one can explore when evaluating a series of pending moves and countermoves – is estimated at 10 to the power of 123, one hundred orders of magnitude above the capabilities of modern computers to calculate efficiently.
In seeking to approach the problem with a neural network rather than a fusillade of move-calculations, one comes up against the problem of the ‘horizon effect’, in which a branch calculation may be terminated at a ‘favourable’ move. This is logical in terms of machine learning, but may not take into account a correlative effect, such as opening oneself up to opponent captures by capturing one of the opponent’s own valuable pieces. Continuing the ‘cut-off’ point a step further is only going to lead the algorithm to the next horizon-based quandary.
Lai addresses this by letting his search algorithms branch into a new type of move evaluation at a certain point, called ‘quiescent search’, which limits its scope to certain types of move and evaluates only those. Much as with the human game, the efficiency of the technique improves according to the number of pieces taken, which limit the possible outcomes and captures.
