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: Communication-optimal algorithms for contracting distributed tensors

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

Microsoft unveils Xbox in China as it faces probe

8 hours ago

Microsoft on Wednesday unveiled its Xbox game console in China, the first to enter the market after an official ban 14 years ago, even as it faces a Chinese government probe over business practices.

Teens love vacation selfies; adults, not so much

9 hours ago

(AP)—Jacquie Whitt's trip to the Galapagos with a group of teenagers was memorable not just for the scenery and wildlife, but also for the way the kids preserved their memories. It was, said Whitt, a "selfie ...

Tiny UAVs and hummingbirds are put to test

9 hours ago

Hummingbirds in nature exhibit expert engineering skills, the only birds capable of sustained hovering. A team from the US, British Columbia, and the Netherlands have completed tests to learn more about the ...

US spy agency patents car seat for kids

12 hours ago

Electronic eavesdropping is the National Security Agency's forte, but it seems it also has a special interest in children's car seats, Foreign Policy magazine reported Wednesday.

User comments : 0