Awari Solved

Gerard Jendras sent in a submission about applying computing power to an ancient game. The game of Awari has been solved: with perfect play, the game always results in a draw. There is a Java applet to test your skills against.

Comments

Important Step?

[rockmuelle]

From the article:

"The research is an important step forward in a research area within Artificial Intelligence, to solve games with increasing complexity"

I don't quite understand why a big lookup table is an important step for AI. Humans don't play games by checking every possible move and picking the best one and never will.

The AI community really needs to stop looking for tricks that allow computers to solve problems in ways that humans never could and instead spend their time trying to understand how intelligence actually works.

Hint: scrap predicate logic (and in doing so the Turing machine) as the model for intelligence. Instead, define a model from which predicate logic can emerge (Reginald Cahill has more or less done this, but I'm not sure if he realizes it yet: Process Physics.).

-Chris

depends on what you call perfect

[Eric Seppanen]

There are lots of games where you can create a "perfect" player that can do as well as possible against other "perfect" players.

The thing that's interesting is making a program that plays as well as possible against imperfect players, as demonstrated by the RoShamBo Programming Competition.

Kind of Bummed - Just Brute Force

[zetetikos]

I'm kind of bummed that this solution is by enumerating every position, rather than some kind of huristic or mathmatical solution. I don't find brute force methods to be very elegant or interesting, although they do present their own chalenges from a resource management perspective. I'll be much more interested if they can analyse the information they have and come up with a computational approach that plays perfectly. It's likely that such a thing could then be generalized to solve many other types of problems.

Zetetikos

Re:The optimal state of any linear game is a draw

[timster]

This is untrue. The optimal outcome of a chess or go game is unknown. It's possible that the player who moves first can always win, and it's possible that the player who moves second can always win. You've forgotten that in a turn-based game the two players are inherently different mathematically since one moves first.

Come on, he didn't say it was easy

[Pac]

But brute force it is indeed...Think of it as the Allied forces carpet bombing Iraq in Gulf I or the US trying to kill that Laden guy by droping a bomb in his head or the (other) Allied forces wasting tons of blood in Normandy . No one of these operations was easy, everyone of them had its novel approaches to logistical, spatial, scientific and communication problems. But not one of them shares the elegance of the Greeks sneaking a wood horse into Troy or the Panzer division ignoring the Maginot line they were supposed to attack and conquering France in a month.

Re:all 889,063,398,406 positions

[Ed Avis]

The game of awari (owari) was an end-of-first-term programming project at my university. Because there are at most six moves possible at any point, and usually fewer than that, the game works well with a minimax tree-searching strategy. On a Celeron 400, allowing about 30 seconds for each move, I got a lookahead depth of 9 moves, increased to 18 moves after adding alpha-beta pruning. I don't know how this compares to the best human players but it was certainly enough to beat me into the ground :-).

I did wonder about cranking up the lookahead depth to try and solve the game - after all, most games the program played it won within 25 moves or so - but each extra level of lookahead roughly triples the run time. After seeing the hardware used by these two chaps it seems that the problem was a bit bigger than I thought. I had considered using a Postgres database to store the lookup of the best move at each stage - lucky I didn't, it would have been completely slaughtered :-).

The owari-playing program is at http://membled.com/work/owari/owari.c if anyone is interested - that directory also contains a Perl front-end which caches the computed best moves. I used that to automatically build up a database of 'openings' computed to a slightly higher lookahead level. I was planning to package up the program and release it, perhaps moving the minimax code into a library. But now the game of owari has been solved, I guess there isn't much point any more :-P.

BTW you can easily un-solve it just by playing with fourteen bowls and twenty-eight stones - it would take them several times longer to find the solution to that.

I wonder if all possible (symmetric) owari games are draws when played with the best strategy?