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)
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.
It appeared in Serria's Quest for Glory III: Trial by Fire which was set in a mythical Africa-like kingdom that included an Egyptian-type city, a savahhana and jungle. Awari was one of the minigames that needed to be completed in order to progress through the game. They don't make them like that anymore; awari or QfG3
I'm tired of bombing the universe
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)
Strangely enough, this is quite interesting.
How about information on Japanese games?
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"
Some people once said that Awari was more complex (= offered more possibilities) than Chess...
You're thinking of Go.
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.
so, what games do you prefer to play? If you play a game that with 'perfect play' should end in a draw, if you win or lose you know whose fault it is.
:):)
Or maybe that's why you don't like games where you can't blame luck/lousy cards/...
-- the cake is a lie
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.
Skiers and Riders -- http://www.snowjournal.com
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."
When the android stalemated an opponent at a board game in Star Trek. The best his computer brain could do to beat the alien, was to play ultimately to a draw, and hence the opponent would never win. I guess Star Trek predicted the future of AI pretty well ;-P
Saskboy's blog is good. 9 out of 10 dentists agree.
I've heard the same thing. The next time you get what you consider to be an unsolveable game, fire up this bad boy and check it out:
freecell-solver
Do you have Linux and a DotPal? Click here now!
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 estimate that I have heard thrown around is 10^120.
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
http://www.cs.ualberta.ca/~awari/
Wow, that Awari game looks quite cool. Does anyone know where I can get one, possibly hand made (doesn't need to be 3500 years old though). It seems way cooler than just a basic chess board (though its cool to have a nice one of those too).
The stones look like those that you can buy, just polished rocks. But the cool fold-up game board is nice. Carved from wood, it would be damn nice to have in the living room. You could even bring it down to the local coffee shop instead of a deck of cards ;-)
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
Next, Gerard Jendras posts links to solutions of the Universal Field Theory, the I.R.S. Tax Code, and How To Pick Up Girls!
Seriously, how long until Go or Go-Moku is cracked? And how many people will damage themselves if chess is ever solved?
It is not true. Proof by counter-example.
And you thought Doom 3 required a lot of resources? Baby ain't got NOTHING on Mancala!
We should pit Joshua against Deep Blue and see who comes out on top.
Let me guess... you currently answer phones for a living?
Breakfast served all day!
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
IANAL, but imagine a beowulf cluster of in Soviet Russia all your belong are base to us welcoming the new SCO overlords.
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.
Player 1 and player 2 both pick up hefty boulders at the beginning of a round.
Player 1 drops his boulder.
Player 2, in turn, drops his boulder.
Both players pick up the boulders again, unless one of them has managed to reach the ground. Rounds continue until the game is over.
If either player's boulder reaches the ground at the end of a round, the game is over, and that player wins. If both players reach the ground at the end of the round, the game is declared a draw.
It's rare that you're presented with a knob whose only two positions are Make History and Flee Your Glorious Destiny.
and does not depend on who the oppenent is.
If both players play a perfect game, awari results in a draw. If the opponent makes a mistake, the perfect game will result in *at least* a draw but may result in a win.
The computer has a *huge* database of *every* possible valid configuration of pieces. Whenever the other player makes a move, it simply prunes all moves that are impossible to make and only considers the best of the valid sequences. There is no guessing as the computer knows *everthing*.
I'm sure the algorithm is not that simple, but I believe that's the gist of it.
Try a search on google for backtracking algorithms and red-black trees.
PS. my apologies if this is not what you were getting at.
Based on upvotes, Ageism is the only "-ism" Slashdotters care about and think isn't SJW
So you can assign win/draw/lose to every move that leads to one of these positions, and so on.
By induction, every position is won, drawn or lost for each player, if they play perfectly. Geddit?
Of course if one player plays perfectly, and the other doesn't then the perfect player can often snatch victory or a draw from the jaws of defeat, cos the imperfect player often makes an inferior move. And, usually both are imperfect.
-WolfWithoutAClause
"Gravity is only a theory, not a fact!"I'm currently taking a grad-level AI course from a major advocate (Dr. J. Weng) of what he calls the Developmental approach. He does not attempt to simulate a human brain, but instead tries to base his programming off of the development process of the human being. For instance, one of his claims is that true intelligence will require a body to interact with the world, as we have one. (This looks like a good introduction to the idea, along with some demos of it in action.)
Interesting stuff. While the jury is still most definately out, he has made some very real progress in some areas many other approaches are finding very difficult. For instance, he has a robot that can navigate the Engineering building with only two or three walkthroughs of the place. Sounds mundane, except that no other technique can come close in such a real-world environment.
I think you'd enjoy reading his stuff. It is being done by a few people; time will tell whether more will pick it up.
Yes, if you're good, you can drop the stones so fast that the opponent doesn't notice if you drop an extra here or there, just to get to a spot that you own. Yes, a good game goes beyond its rules a little, but that's part of the fun.
Here's an unsolvable instance
It's basically normally sorted, but with aces, twos and eights on the first two rows. Nines and sixes are at the bottom and you can't climb up high enough to get to the aces.
So what. The optimal outcome of two perfectly matched chess players is draw. For checkers, Go, gipf and just about any game where it is only possible to make one move at a time. I fail to see the elegant insight of this.
More complex games that are non linear and have multiple simultaneous gaming moves will not end in draw even with two perfectly matched opponent groups because of the effect of moves that only partially account for one another. Bridge comes close to such a game.
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.
There are hundreds, maybe thousands of variations on Mancala-type games (bowls and stones which are placed in them). These games are played all over the world.
I just returned from Kenya and Tanzania where I bought a Mancala borard for a local gamed called Bau (also spelled Bao). It is a lot more complicated than Awati and some say it is the most complex form of Mancala.
- Sam
The secret to enjoying Slashdot is to realize that it should not be taken too seriously.
Agreed. It's not important at all. It's probably just some pr flack who was looking for an interesting angle and didn't actually check with the researchers who did the work.
As for what "the AI community" are doing, might I suggest that they *are* trying a whole bunch of different approaches. None seems to offer the holy grail yet.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
Would you buy a phone that was smarter than you...? :-)
RMN
~~~
At the time they wrote the help file that was true. Eventially somebody found that at least one game is not solveable (other posts tell you which). Now the help file is out of date - unless they have updated it since your version. I haven't read the help file in 6 years, back then it was not known yet that one game was unsolveable.
The current game looks like it has 8 or 10 holes. Just rework the game to have 20 holes or so. When somebody solves that, add yet more holes.
You can never get enough holes.
Table-ized A.I.
I'm up to game 4386. ~2 years so far. I'm hoping to break 5000 by the end of the year.
:)
At that rate you should hit game number 11982 around Feburary 2004. Good luck
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
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.
You know, there are these language devices one may use to comment a situation. You are supposed to learn it in High School. As you failed to notice, I learned to use them in at least two different languages.
So, next time someone says to you "Your understanding is as deep as a rain pool", don't ask him about the average rainfall in the area. Ask him for help...
(As for Europe, I prefer the "Let the Russians win this one for us while we put up little show here in Holland and France" method. It is much safer, although the colateral effects may last half a century or so. Saddam is another matter entirely. Who said I want to ouster him? George, Dick and their vassal Tony, they are the ones at it).
Yes. If you're playing against an optimal player, the best you can hope for is to draw. If you draw, then you've played optimally.
There may be some states from which it is impossible to draw. That depends on the game. But if you were playing optimally, you would never enter that game state.
My other first post is car post.
First of all, it wasn't Deep Blue that beat Kasparov, it was Deeper Blue, its sucessor.
Secondly, the only reason that Deeper Blue was able to beat Kasparov was because it was specifically programmed to play against him. They fed it his entire professional chess playing history so it could figure out his style and how to beat it. If you entered Deeper Blue as a contestant in the world championship proceedings, it wouldn't win.
Awari is not like chess, and if you know what Awari is, you're probably going to know what chess is..
"A language that doesn't affect the way you think about programming, is not worth knowing" - Alan Perlis
A real AI does not want code that plays.
A real AI wants to play. Might even create its own game to play.
Seems like the smarter the animal the more it plays.
"Want to play another game?"
I'm not sure I agree with that. In my experience changing the size of the board in Go makes the game very different. Eg if you play on 9x9 board instead of "real" 19x19 then there are programs which can play fairly well. However the big point of Go is lost, that of strategy. In 9x9 games it almost always comes down to pure tactical playing. And this is where computers beat humans.
After playing a few months of Go I'd say that it's very complex.
Did Deeper Blue really get a fair win? Wasn't there some sort of controversy at the time concerning whether it was fair play for the IBM guys to change its programming during the match?