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)
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 :)
replacing it with NEW Folger's Crystals! (lets see if they notice the difference)
It seems the only way to win is not to play.
Finally, math books without any of that base 6 crap in them.
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. ;-)
"It is a greater offense to steal men's labor, than their clothes"
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.
Finally, math books without any of that base 6 crap in them.
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
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
/* Obfuscated tic-tac-toe in C
p ; ,x,z);a(z, ,y);a(y,z,
;l();puts( b);;;;;}}}
* 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;
&nbs
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
y,x);a(x,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
-- 2 + 2 = 5, for very large values of 2