How Robots Will Beat Humans at Billiards

Once a year, at the International Computer Olympiad, teams pit their AI software against others’ in a variety of nerd-appropriate sports: chess, go, backgammon, etc. Since 2005, however, the ICO has also included computer simulations of billiards.

Pool is a hard game for computers to play because it’s not just about sinking balls – it’s also about setting up the table to your opponent’s disadvantage. Throw in opportunities to sink more than one ball at a time and the literally infinite number of shots that can be taken in every turn, and you’ve got a gigantic parameter space for a computer to chew on.

And that’s before you get to the problem of translating the computer simulations of pool to the real world. Right now there are a handful of robots capable of playing the game, most notably Deep Green of Queen’s University, which is an industrial robot.

Warning, the following video has unnecessarily loud, pounding music:

But back to the world of virtual pool: in this realm, advances are being made all the time, in hopes of creating a pool AI so powerful that it can some day be paired with a physics simulator and robot capable of beating the world’s best human players.

The latest development, while modest, allows a pool-playing AI to better optimize its shots for both pocketing extra balls and breaking clusters of them. Researchers at the Université de Sherbrooke, in Quebec, are tuning their AI’s decision-making model to take multiple factors into account when planning its shots, since pool is about strategy as much as skill.

Part of the value of attacking this problem is that it’s so distinct from other models problems in computer science and artificial intelligence, such as Chess. In Chess, all the options available to a player are discrete – there are only so many pieces that can be moved, in a prescribed number of ways, at any given moment.

Pool, on the other hand “features a unique combination of properties that distinguish it from others such games, including continuous action and state spaces, uncertainty in execution, a unique turn-taking structure, and of course an adversarial nature.” That’s a quote from Computational Pool: A new challenge for game theory pragmatics (pdf), which announces the next tournament for virtual pool, to be held in August 2011.

Interestingly, this competition will attempt to simulate what it would be like for these virtual pool players to have their models translated into real-world pool by robots: “The championships will feature separate competitions at different noise levels, allowing for innovation and new ideas, since new strategies may be most effective at the new noise levels.”