An algorithm would like to watch you play, then beat you at Connect Four

Łukasz Kaiser, a researcher at LIAFA laboratory at the University of Paris, has created an algorithm that watches games being played, learns the rules and then plays the games competitively.

Łukasz Kaiser, a researcher at LIAFA laboratory at the University of Paris, has created an algorithm that watches games being played, learns the rules, and then plays against human opponents.

With little more information than the size and position of the game board and what a human hand looks like, Kaiser's algorithm learns by watching videos of individual moves in Connect Four, Tic-Tac-Toe, Gomoku, Breakthrough, and Pawn Whopping.

Based on the information observed, the algorithm learns the rules of the game.

The videos run about two minutes long and show winning conditions, legal moves, illegal moves, unfinished plays, and tied plays. In each video, Kaiser's algorithm observes the relational structures between rows, columns, and pieces on the game board. Based on the information observed, the algorithm learns the rules of the game.

In a research paper called "Learning Games from Videos Guided by Descriptive Complexity," Kaiser details his desire to obviate the kind of pre-programmed background knowledge that allowed previous computer programs to play games. In contrast with previous methods, his algorithm "requires only a few demonstrations and minimal background knowledge, and, having learned the rules, automatically derives position evaluation functions and can play the learned games competitively."

Kaiser deployed the algorithm in Toss, a program designed to "create, modify and play games," where it selects among several logic sets to put the knowledge it gathered into action. Because Toss can also accept game rules entered manually, he was able to compare the algorithm's results against rules entered manually. According to Kaiser, the algorithm's "playing strength" was "exactly the same as for manually written definitions."

Though Kaiser believes that there is "strong theoretical evidence that it will generalize to other problems" beyond board games, future applications will require more complex formulas and further experimentation. Though the paper is silent on specific applications, it's easy to imagine, for example, a more sophisticated video game AI methodology. Programmed to learn from watching a single player's movement and behavior patterns, this kind of persistent, player-centric reaction could further blur the line between real and AI opponents, just as the algorithm does with Tic-Tac-Toe.

For a detailed discussion about the complexities of designing AI for video games, check out Polygon's recent feature on Civilization 5: Gods & Kings, featuring Ed Beach, who played an integral part in crafting the strategy game's AI.