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

more about the game

[SkyIce]

This is more commonly known as Mancala in the US.

An adaptation (simplified) of the game was used as a problem in last year's International Olympiad in Informatics: see the description of the problem here. For a description of how to solve it efficiently, see this booklet.

Re:Freecell Solitaire...

[extra the woos]

Nope, it's not true... If you have windows freecell, go into it and put in select game. Type in "-1" or "-2" and see for yourself :)

Amazing.

[unicron]

It seems the only way to win is not to play.

all 889,063,398,406 positions

[Alien54]

Well, another weekend project shot all to heck ...

Dr. John W. Romein and Prof. dr. ir. Henri E. Bal solved the game by developing a program that computes the best move and eventual outcome for all 889,063,398,406 positions that can possibly occur in a game. The results are stored in a database that is 778 gigabyte large. The database was computed on a large computer cluster with 144 processors. A new and fast, parallel algorithm managed to compute the database in only 51 hours. Each processor accounted for part of the postitions, but the processors closely co-operated to determine the best moves. One complication was that the available main memory, 72 gigabyte, was by far not large enough to hold the entire database. Another problem was the heavy communication between the processors; a total of 1.0 petabit (= 10^{15} bits) was sent over the interconnection network.

Next thing I know, someone is going to try programming the database in perl. ;-)

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?

Re:Chess

[lightspawn]

Some people once said that Awari was more complex (= offered more possibilities) than Chess...

You're thinking of Go.

Uhhh.

[unicron]

Perfect play always results in a draw? In America, we call that game tic-tac-toe, and we didn't need any computers to figure it out, either. Hell, my first day of kindergarten I was told the game was futile by other children.

3500 year old technology

[cr@ckwhore]

The game is estimated to be 3500+ years old. I'm really astounded by the fact that a perfect game is a draw! 3500 years ago, they created a piece of mathematical perfection... with rocks.

Re:3500 year old technology

[Verteiron]

Yeah, they had to overrock it from 33 megaliths to 50 just to work out all the possibilities.

Re:3500 year old technology

[micahjd]

/* Obfuscated tic-tac-toe in C
* Copyright 2002 Micah Dowty <micahjd@users.sourceforge.net>
*
* Enter your moves using this key:
* 0|1|2
* -+-+-
* 3|4|5
* -+-+-
* 6|7|8
*/

#include <stdio.h>
#define E " | | \n"
#define F "-+-+-\n"
#define L(x)b[x/3*12+x%3*2]
#define P(x)e=x<0?e:x;
#define R(a,b,c,p)if(L(x)==a&&L(y)==b&&L(z)==c)p=z;
&nbsp ;
int x,y,z, e,i,v,o,h,
X=88,S=32, O=48,r[]={
0,1,2,3,4, 5,6,7,8,0,
3,6,1,4,7, 2,5,8,0,4,
8,2,4,6};char b[]=E F E F E;void a(int
x,int y,int z){if(L(z)==S)e=z;R(O,O,S,
v)R(X,X,S,o)R(X,S,S,h)}void l(){for(i=
0;i<24;){x=r[i++];y=r[i++];z=r[i++];a(
x,y,z);a(y ,x,z);a(z,
y,x);a(x,z ,y);a(y,z,
x);a(z,x,y );if(L(r[x
])!=S&&L(r [x])==L(r[
y])&&L(r[y])==L(r[z]))exit(printf("%s"
"You Lose\n",b));}}int main(){puts(b);
for(;;){i=getc(stdin)-O;if(i>(e=v=o=h=
-1)&&i<9&&L(i)==S){L(i)=X;l();i f (e<0)
exit(1-1&& printf("%"
"sCat's G" "ame\n",b)
);P(h)P(o) P(v)L(e)=O
;l();puts( b);;;;;}}}

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

Re:Important Step?

[wfmcwalter]

I don't quite understand why a big lookup table is an important step for AI.

I think you're quite correct here. Brute force isn't a reasonable solution to most interesting realworld problems, and it's hard to see how this approach is instructive for future AI research.

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

Ah, now I think you're overstating things a bit. It sounds like your objection is predicated (sic) upon the assumption that the sole purpose of AI research is to reproduce biological, and finally human, intelligence, and that the way biological brains do it is the only way it can be done. I think that's not necessarily the case.

In the first matter, there's plenty of higher-order problems that we might want solved, and there's no reason to suppose that a human thought process is the best way to go about things. The sole purpose of AI research isn't to pass a Turing test. A truly artificial intelligence, that solves hard problems in exotic ways would still be a very interesting and useful thing to possess, even if one couldn't talk sports with it.

In the second matter, it's still a contentious matter whether human-like intelligence could ever be built with hardware and software components like the ones we have today. In the event that it is, it's quite possible that the artificial solution would take a radically different path than the biological - a path worthy of exploration, interesting even if it ends in a blind alley.

...and instead spend their time trying to understand how intelligence actually works.

That's not unlike saying that birds fly by flapping feathery wings, and thus so should passenger aircraft - they're solving different problems, and with different means.

Study of the biological solution is instructive - mere apeing of it isn't.

Re:Important Step?

[bwt]

I don't quite understand why a big lookup table is an important step for AI.

What AI wants is code that plays, observes the results, and converges to perfect play. One such algorithm has been produced and perfect play has been determined. Now the question is can an algorithm that converges *faster* be found. Learning speed can now be objectively measured, which opens a whole new scientific basis for studying AI.

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.

Re:depends on what you call perfect

[MisterBlister]

RoShamBo is fundamentally different because there is the chance element of "what is the other guy going to choose". And that chance element is reset every time you throw..The past doesn't matter. You can't force someone into a 'positon' because each 'move' is completely independent of any others.

In this instance, no matter what move you make the computer knows what every possible board combination from now to the end of the game can look like.. You can't throw him for a loop with imperfect play because he will have already 'predicted' (by way of a simple scoring algorithm) the possibility that one of your moves could result in weakining his position and he would have avoided making the move that allows you to make that move.

Your observation makes a bit more sense in chess, since chess isn't really "solved" yet (far more possible move combinations than in this game). But once a game is "solved" in this manner, you'll never beat the computer, ever, no matter how clever you are unless the game is flawed (one player has an inherent advantage) or the computer has a programmer error.

Another way to look at it is Tic-Tac-Toe. Tic-tac-toe is simple enough that it can be 'solved' in the human mind by any reasonably intelligent person. If you play against such a person, you'll never win no matter how 'tricky' your moves..

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:Game board/peices?

[cosmol]

Yeah, I know where to find them. Go to your local grocery store and ask to be directed to the dairy section. There you will find eggs in what are called "cartons." Some cartons may contain only six, some contain 18, you want the one that has 12 eggs in it. On your way to the register, stop by the toy aisle and pick up a few packs of marbles.

Wow......

[Ride-My-Rocket]

And you thought Doom 3 required a lot of resources? Baby ain't got NOTHING on Mancala!

Speaking of computer AI......

[Ride-My-Rocket]

We should pit Joshua against Deep Blue and see who comes out on top.

Re:Freecell Solitaire...

[PCM2]

I'm up to game 4386. ~2 years so far. I'm hoping to break 5000 by the end of the year.

Let me guess... you currently answer phones for a living? :-)

I can see it now...

[littleRedFriend]

Microsoft Awari.

Minimal system requirements:

distributed computer cluster with 144 Athlons XP+2600
72 Gb of RAM
778 gigabyte free disk space
1.0 petabit Ethernet card

Re:Chess

[Anonymous Coward]

Maybe now they'll release the alternate ending to "War Games", where Matthew Brodderick tells the computer to play Awari against itself. 51 hours later, it decides not to nuke the world.

Most annoying game ever

[soramimicake]

If it is playing a perfect game, then it would be able to follow your moves all the way to the end of the game and see that you could win.

I can see it now: a computer game that keeps popping up "warning: you already won, continue playing to endgame? Yes/No" after each move until you make a mistake, it which case it pops up "warning: You made a mistake. Duh. I win. Game Over ", since the computer will not make a mistake.

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:a perfect game

[Old Wolf]

Not so; in some games the second player wins, here's an example:

you have a pile of 21 matches. players alternate turns. on your turn you may take either 1, 2, or 3 matches. whoever takes the last match LOSES.