Computer turns into boardgame master of all it surveys

Jul 10, 2012 by Nancy Owano report
A position winning for white and one not winning. Image from "Learning Games from Videos Guided by Descriptive Complexity" by Łukasz Kaiser

(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 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 ’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.

Explore further: Engineer leads effort to develop computer systems that can see better than humans

More information: liafa.jussieu.fr/~kaiser/pub/l… ptive_complexity.pdf

Related Stories

Computer learns language by playing games

Jul 12, 2011

Computers are great at treating words as data: Word-processing programs let you rearrange and format text however you like, and search engines can quickly find a word anywhere on the Web. But what would it ...

The family that plays together stays together?

Apr 21, 2011

(PhysOrg.com) -- “Get off the computer and go play outside.” So go the words heard in homes around the country as parents and children clash over the social benefits of video games.

Video games shown to improve vision

Mar 15, 2007

According to a new study from the University of Rochester, playing action video games sharpens vision. In tests of visual acuity that assess the ability to see objects accurately in a cluttered space, game players scored ...

Recommended for you

Enabling a new future for cloud computing

15 hours ago

The National Science Foundation (NSF) today announced two $10 million projects to create cloud computing testbeds—to be called "Chameleon" and "CloudLab"—that will enable the academic research community ...

Hacking Gmail with 92 percent success

Aug 21, 2014

(Phys.org) —A team of researchers, including an assistant professor at the University of California, Riverside Bourns College of Engineering, have identified a weakness believed to exist in Android, Windows ...

User comments : 0