Slashdot Mirror
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.
← Back to Stories (view on slashdot.org)
Some people once said that Awari was more complex (= offered more possibilities) than Chess...
I guess this proves them wrong...
You aren't gonna ask for a game of globalthermonuclear war next are you, Joshua?
Chess has a finite number of squares and a finite number of pieces, thus the total number of possible boards in chess is also finite.
With sufficient storage and proper linking of data, the decision for the next move could be reduced to simply following the chain that leads the highest probability of success.
Considering that either side can use the same data, it is possible with perfect play chess would also lead to a draw every time.
"The unicode stuff in the latest version is working fabulously well. My russian mafia friends are ecstatic."
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
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.
314-15-9265
Maybe I'm missing something, but there is a Huge element of chance in all the games listed. Its that unless your playing against a computer, and even in that instance, there is a Chance of Human error. Someone may move a piece they didnt intend to. A program may have been written with a susceptibility in it that makes it less than perfect. There is no such thing as a game without chance, there is always the chance of a human error, since humans, despite what some may feel, are far FAR from perfet.
Just my two cents...
I'm a little tea pot.
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
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.
I have seen the future, and it is inconvenient.
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.
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 :-).
:-).
:-P.
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
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?
-- Ed Avis ed@membled.com