July 11, 2012

Computer Program Learns Games by Watching People

Robert Gelber

Łukasz Kaiser, a computer scientist from Paris Diderot University, has created a method that trains systems to learn board games. After being fed two-minute video clips of humans playing classics like Pawns, Connect 4, Gomoku and Breakthrough, a computer was able to understand the rules and outcomes of each game. Yesterday, Wired published an article about the project and described the software behind it.

Machine learning of this caliber can bring to mind scary scenarios of computers run amok. In fact, the concept was used in the 1983 science-fiction film War Games, where a military computer confused reality with board games. In this case, the program used a much safer test machine, a single-core laptop with 4GB of memory.

In his paper, Kaiser pointed out a number of key differences between previous experiments and his own. He mentioned that applications from other game-learning studies based on visual recognition required significant background knowledge and only worked with specific games. In this case, the algorithm would need only a few demonstrations and minimal background knowledge.

To achieve more functionality with less data, the project decided to forego using a popular inductive learning program (ILP) called Progol. Kaiser found that while Progol is a successful ILP application, it was not well suited for understanding games in this context.

“To be able to learn games such as Connect4 or Gomoku from short demonstration videos and with minimal background knowledge, we go back and investigate the basic assumptions of inductive logic programming,” he said.

The new algorithm used relational structures that could recognize common game elements like rows and columns as well as play styles. It then used a general game-playing program to build different types of tactics. The paper concluded that the model could be easily ported for other problem solving applications.

“This combination allowed it to generate very short and intuitive formulas in the experiments we performed, and there is strong theoretical evidence that it will generalize to other problems,” Kaiser explained.

Eventually, he expects the new algorithm to assist in the creation of intelligent robots that can employ structured learning. While the concept may induce fears of robotic rebellions, the application seems far from dangerous. At this point, the program could probably be tripped up with something as simple as a game of Monopoly.

Full story at WiredConnect 4, Gomoku, Pawns and Breakthrough

Share This