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: Algorithm accounts for uncertainty to enable more accurate modeling

More information: liafa.jussieu.fr/~kaiser/pub/learning_games_descriptive_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

Cattle ID system shows its muzzle

Jun 29, 2015

Maybe it sounds like a cow and bull story, but researchers in Egypt are developing a biometric identification system for cattle that could reduce food fraud and allow ranchers to control their stock more efficiently. The ...

Combining personalization and privacy for user data

Jun 29, 2015

Computer scientists and legal experts from Trinity College Dublin and SFI's ADAPT centre are working to marry two of cyberspace's greatest desires, by simultaneously providing enhanced options for user personalisation alongside ...

User comments : 0

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.