A computer that learns the rules of a game by watching you play

A Parisian researcher has created a computer system that can learn the rules of games by watching you play — and then beat you at it.

Łukas Kaiser, a cross-disciplinary researcher at the Paris Diderot University who has a love for logic, games, and computer algorithms, has created software that uses computer vision to learn the rules of five board games: Breakthrough, Connect 4, Gomoku, Tic-tac-toe, and Pawn Whopping [does anyone know what this game is?]. Kaiser records videos of winning games, losing games, and illegal moves — and then feeds them into the system.

From these videos, the software strips out superfluous features, such as human hands, and focuses on the position of the games’ tokens (all five games are grid-based). From these positions (winning positions, losing positions, and illegal positions), the software works out the rules of the game. These rules are expressed as logical formulae, such as ∃x1Q(x1) ∧ ∃x0(C(x1,x0) ∧ x0 = e1). It only takes around 60 seconds for the video to be processed, and then a few more minutes to work out the rules — on an old-school Core 2 Duo laptop.

Both the computer vision/video recognition portion of the software (written in C++) and the rule-learning algorithm (written in OCaml) are integrated into Toss, an open-source games playing program. This means that Kaiser could actually test the algorithmically-generated rules against hand-written rules — and indeed, he found that his system created identical rules (and yes, it’s almost impossible to beat the computer at Tic-tac-toe or Connect 4).

In short, Kaiser’s software learnt the exact rules of a game from scratch, with a minimum of external input. There’s no getting around the fact that all five of these games are very simple, though, with only a couple of very basic rules. Moving forward, Kaiser wants to improve the rule-learning algorithm so that it can pick up complex games like Chess. Maybe Kaiser should team up with MIT, who last year taught an AI to read the Civili ation user manual so that it could develop an optimal winning strategy.

A computer that learns the rules of a game by watching you play