Artificial Intelligence Is Taking Computer Chess Beyond Brute Force
To International Master status
Chess is often seen as the ultimate mental challenge: 32 pieces on an 8-by-8 board, and nearly limitless possible moves. There are chess engines that calculate millions of moves per second, but the traditional approach is to “brute force” the match. Brute forcing is a method in hacking (and apparently computer chess simulation) that means to run every possibility of a problem until the program finds the best solution.
But Matthew Lai wants to make chess-playing computers smarter. For part of his Masters degree at Imperial College London, Lai trained artificial neural networks to play at the level of a FIDE International Master, better than 97.8 percent of rated tournament players. He calls his software Giraffe.
After 72 hours of training, Giraffe figured out the best possible move 46 percent of the time. The move that Giraffe selected was in the top 3 moves 70 percent of the time. Previous attempts at machine learning in chess, like Knightcap, needed programmers to design “pattern recognizers,” separate functions to learn moves like shielding a king with a pawn, or the importance of having both colors of a bishop, says Lai. The machine learning algorithm would watch already-defined moves, and learn how strong they were. Giraffe discovers these patterns automatically, so it can learn moves that even the programmer wouldn’t have considered.
“Giraffe derives its playing strength not from being able to see very far ahead, but from being able to evaluate tricky positions accurately, and understanding complicated positional concepts that are intuitive to humans,” Lai writes in his paper detailing Giraffe.
Lai trained his artificial neural networks, which mimic human learning by continually testing the effectiveness of the surmised solution, on a set of 175 million data points. He took 5 million initial legal board configurations from humans’ and other computers’ games, and then applied a random legal move to each, multiple times for each board. The learning process involved the computer playing itself, and then calculating whether it would win or not based on its next move.
Without any training, Giraffe scores about 6,000 of 15,000 points in a standardized chess engine test. After training for 72 hours, it peaked at 9,700. It learned.
Giraffe is only bested by an engine called Stockfish 5, created and tuned since 2008 (and first built around a 2004 Glaurung chess engine). Lai writes that Giraffe’s ability to stand up to “carefully hand-designed behemoths with hundreds of parameters” is remarkable for how young it is, and that the testing suite might even underestimate his program.
“Since the test suite is famous, it is likely that at least some of the engines have been tuned specifically against the test suite,” Lai writes in his paper. “Since Giraffe discovered all the evaluation features through self-play, it is likely that it knows about patterns that have not yet been studied by humans, and hence not included in the test suite.”
The next step is making Giraffe more efficient. Lai suggests that training smaller networks using Giraffe could increase speed, and using another neural network for time management.