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...
I've heard that there's a solution for every dealt hand. I was wondering if anyone has tried anything similar to find out if this is actually true?
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
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 Nokia cell phones include a variation of that game called Bantumi. The rules are slightly different, but the principle is the same. The computer's (phone's) gameplay is far from "perfect" though.
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.
I have a perfect solution for Go:
Knock-knock.
Who's there?
Go.
Go where?
Go fish.
Would seem to be the next step in solving the game. It may be that something could be derived by examining the game-state set itself.
I suppose if the rule was easy someone would have found it without the brute force solving though.
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
Bud Selig has too much influence.
Hey, Here in Maldives we call this game Oh'Walhu (Something about holes), anyway, we have a slight twist to this game. Before playing it, the players need to drink at least four glasses of coconut toddy, or else he or she would forfit the game. Anyway, due to this reason, the game still remains unsolvable here.
Amaa Fui
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
That might take 54 or even 55 hours.
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."
I can hear the computerish monotone right now:
"Would you like to play a nice game of Global Thermonuclear Warfare?"
Draw.
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.
How about:
Knock-knock.
Who's there?
Go.
Go where?
GFAD.
"If he thinks he can hide and run from the United States and our allies, he's sorely mistaken." Bush on bin Laden
So, does anyone know *about* how many possible games of chess there are? I'm guessing it's quite a few more than Awari, else it would have been solved by now.
Personally, I'm curious to see whether you can always force a draw or if the first player to move always wins.
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
And in other news, still no cure for cancer.
"Tell me doctor, with all of your defenses, are there any provisions for an attack by killer bees?"
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 ;-)
We have a similar game in south india (Called "Pallankuzhi" in my native tongue) that is more complicated. Typically you use smooth sea-shells for the pieces. Each side has 7 holes instead of 6 and you start of with 12 shells in each hole except the center one on either side which only have one large shell. Here is some mention of it on the web:b stract sFinal.html
http://www.unifr.ch/psycho/pgp/boardgames/a
I did it. With a scientific method and a few hours of play, I was able to solve the game of chess. Indeed, it seems I lose even when I play my best.
IP Therefore I am.
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
The game of Awari has been solved: with perfect play, the game always results in a draw.
Personally, I wouldn't trust a game in which playing a perfect game was rewarded with losing. That just means an element of uncertainty was inserted somewhere along the line, and then it's no longer a game of skill, but of chance.
Everything that was once directly lived has receded into a representation. -debord
There's a draw if a position is repeated three times (not necessarily consecutively).
There's no rule about consecutive checks. In fact some fun chess problems involve dozens of consecutive checks.
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?
the last level of Quake3 with Xaero on nightmare level!
I wonder what "perfect play" is: playing the move with the highest chance to win? the highest chance not to loose? something else?
And you thought Doom 3 required a lot of resources? Baby ain't got NOTHING on Mancala!
Actually as any religous reader of Scientific American knows, pawn to king's rook 4 is a win for white. (See http://www.ericberlin.com/reader.html if you don't know what I'm talking about)
In Soviet America the banks rob you!
There is a Java applet to test your skills against.
Err.... what's the point anymore? Now that the game has been solved, the only factor is human error, and there is no room for human ingenuity.
I swear, as soon as they solve chess, there's going to be a lot of smart people comitting suicide.
no thanks
We should pit Joshua against Deep Blue and see who comes out on top.
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.
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.
As kids, we often played that game (without
computer). We called it "Serata".
It is also known under the name "Mankala"
programmed in Tcl/Tk. See
http://www.elf.org/tclplugin/mankala.html
A javascript implementation can be found at
http://imagiware.com/mancala
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
It's hella easy to torque up with that opening though. It's a very weak position to start from,
tactically speaking, and unless you really know what you're doing (e.g., you are deeper blue),
it's not advised.
... the only winning move is not to play.
--Pat / zippy@cs.brandeis.edu
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.
Part of the Programming I course for first years at Imperial College is writing an Owari game. There was a competition to see who could write the 'best' AI for the game, touted as a battle to the death between two hand crafted stone moving virtual constructs... As it turned out, it was apparently a somewhat boring affair. Most of the rounds ended up drawn, so nobody could win ;)
.. the only winning move is not to play
- MbM
Comment removed based on user account deletion
"But you always win?!"
"Not always, *sometimes* I draw"
Comment removed based on user account deletion
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.
The estimate that I have heard thrown around is 10^120 [possible chess positions].
For comparison, there are about 10^80 to 10^85 atoms in the universe. (A googol is 10^100.) So we'll never be able to solve chess until somebody discovers some sort of magnificent reduction.
Will I retire or break 10K?
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.
.... argh, never mind, stupid joke.
What time is it/will be over there? Check with my iPhone app!
I'm not very good...but man what an addictive game!
SIGFAULT
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
~~~
GO has quite a few times more positions than chass silly.
A Good Troll is better than a Bad Human.
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 wonder what that implies.
Does it mean that a player with sub-optimal tactics is bound to lose? This statement sounds intuitive, but it's not so obvious.
Basically, I'm wondering if for any state the game is in, optmial play from that point on will yield a draw... or if the draw only applies if both players have been playing 'optmially' from the beginning.
I'm always weary of 'brute force proofs'.
We should pit Joshua against Electric Blue and see who comes out on top.
Copyrights, Patents, Trademarks: temporary loans from the Public Domain, not real property ("intellectual" or otherwise)
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).
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?"
White is lower-case and black is upper-case.
White is about to promote the f-pawn. If White promotes to a queen, Black will be stale-mated. If White promotes to a rook, Black can move to g7 or h6, and White will eventually checkmate Black with K+R versus King.
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?
But, right now, why not trying with a real one?
Their rules are neither the used in international championships nor the played in any place in the world (as far as I know). So, it makes no sense for me to solve such a game.
VBiR