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: New frontier in error-correcting codes

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

New frontier in error-correcting codes

18 hours ago

Error-correcting codes are one of the glories of the information age: They're what guarantee the flawless transmission of digital information over the airwaves or through copper wire, even in the presence ...

Five ways the superintelligence revolution might happen

Sep 26, 2014

Biological brains are unlikely to be the final stage of intelligence. Machines already have superhuman strength, speed and stamina – and one day they will have superhuman intelligence. This is of course ...

User comments : 0