Computer turns into boardgame master of all it surveys

(Phys.org) -- Igniting interest in computer logic and gaming, a paper titled “Learning Games from Videos Guided by Descriptive Complexity” shows how computer systems can successfully learn how to play boardgames, just by its watching two-minute videos of humans playing and can then proceed to try to beat them at their own game. Łukasz Kaiser, the author of the paper, studies logic and games at Paris Diderot University in France. His research effort was to introduce a system for learning board game rules from brief videos and demonstrate it on several well-known games—such as Connect4,Gomoku, Pawns, and Breakthrough.

“The presented 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,” according to the paper. “Our main technique is based on descriptive complexity, i.e., the logical means necessary to define a set of interest. We compute formulas defining allowed moves and final positions in a game in different logics and select the most adequate ones.”

He used software that processed video clips to recognize the board, pieces, moves, and outcomes. The system could examine viable moves, draw data from all possible outcomes, and proceed with an optimal calculated move. The video recognition procedure was implemented in C++ and the game learning algorithm in OCaml. Both were integrated with Toss, a game playing program. Toss is an open source project hosted by SourceForge and distributed under the BSD license.

He used relational structures that recognize rows, columns and diagonals of a boardgame, and made use of different logic systems —pure first-order, existential and guarded. Additionally, a General Game Playing program enhanced the system’s learning power to play tactically and know legal moves. (General Game Playing is the design of AI programs that can play more than one game successfully. The system is valued by researchers for use beyond gaming to an intelligence support for search and rescue missions.)

Kaiser said he chose to use games as a primary learning tool because they are models of real-world interaction scenarios, making the results significant in a broader context. “Systems able to learn from visual observations are of central importance in many fields, especially in autonomous robotics and interactive computer vision,” he said.

The tests for Kaiser’s experiment were run on a laptop with 4GB RAM and a2.13GHz Intel L9600 processor. The computer’s performance depends on the complexity of the game. Nonethtless, observers agree that the significance of Kaiser’s efforts is to demonstrate that software can learn the rules of a game with a modest amount of external input.

© 2012 Phys.Org