11 July 2012
An AI that can watch two-minute videos of some simple board games being played, learn the rules, and then play against human opponents has been developed by Lukasz Kaiser, a researcher at Paris Diderot University.
MORE AI: DARPA system to blend AI, machine learning to understand mountain of text
In the broad strokes, Kaiser’s AI is a set of subroutines that work in concert — a visual analysis system provides data to a game learning algorithm, and both are linked to an open-source game engine called Toss.
While the program is still unable to accuse you of cheating and leave the game in a huff, the level of sophistication displayed by Kaiser’s invention is nonetheless highly impressive. Even more impressive is the fact that Kaiser’s first tests of the AI — on tic-tac-toe, Connect Four, Go-Moku, Pawns and Breakthrough — were conducted on a laptop with a single-core processor and 4GB of RAM.
Kaiser says his use of planar graphs to represent the current state of a game is part of what allows the software to perform these impressive feats on relatively limited hardware.
“My background is in logic and in finite model theory, so I’m mostly a theoretical computer scientist, but I was looking for applications of the finite model theoretic methods, so I looked toward AI,” he says. “It turned out that, indeed, it is possible to apply some of the theoretic methods to get better results in learning and to illustrate it by game-playing programs.”
“In this simplified model, I can apply the logic methods and see how they fare on different games. So it’s simplified, but not trivialized,” he says.
While Kaiser says there’s no barrier “in principle” to the system learning how to play something more advanced, like chess, the increased complexity of the rule set makes it far more difficult.
“I’m also trying to move toward games where there is dynamic movement, not only changes of the board,” he says, giving Pong as an example.
You can’t yet square off against Kaiser’s game-learning algorithm, but if you want to challenge the open-source game playing engine it uses, you can do so here.