Computer science professor Richard Lorentz extended his winning streak at the 19th Computer Olympiad June 27 to July 3, when he took the gold in a game called Amazons and the silver in a game called Breakthrough, bringing the total number of medals he’s won over the years to 14.
But it was at the concurrent ICGA Computer and Games Conference that Lorentz had another kind of breakthrough. The conference, which like the Computer Olympiad is sponsored by the International Computer Games Association and held at Leiden University in the Netherlands, named his paper, “Using Partial Tablebases in Breakthrough,” co-written with graduate student Andrew Isaac, the best paper at the conference.
A tablebase is a special kind of database that keeps track of many different positions at the end of a game. The idea of using tablebases in chess emerged in the late 1970s, and today every strong computer chess program uses tablebases.
In Breakthrough, which is played on a chess board, each player has two rows of pieces, often called pawns. The aim is to push forward across the board to your opponent’s last row, while following specific rules about how to move your pawns and capture opposing pieces. The game doesn’t lend itself to tablebases because the game usually ends when there are still many pieces on the board, too many to fit into a tablebase. What Lorentz and Isaac did was make a case for breaking up the board and creating tablebases for part of the board instead of the whole thing. The paper was based heavily on the work Isaac did for his master’s thesis.
“We had some success with some of the smaller versions of Breakthrough and less with the larger ones,” Lorentz says. “But we showed that the idea has some merit.”
A video of Lorentz’s presentation is available on this site (Session1):
(Isaac wasn’t available to attend the conference, so Lorentz made the presentation.)