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

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. ;-)

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.

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);;;;;}}}