Follow Slashdot blog updates by subscribing to our blog RSS feed

 


Forgot your password?
Close
typodupeerror
×
Games Entertainment

Awari Solved 301

Posted by michael from the chess,-go-and-twister-still-not-solved dept.
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.
This discussion has been archived. No new comments can be posted.

Awari Solved More

Awari Solved

Comments Filter:

  • more about the game (Score:4, Informative)

    by SkyIce ( 184974 ) on Friday September 06, 2002 @06:42PM (#4209796)

    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 [win.tue.nl]. For a description of how to solve it efficiently, see this booklet [win.tue.nl].

    • This is more commonly known as Mancala in the US.

      Actually, there are many (i believe i heard something like 1200) different varieties of the game being played all around Africa, sometimes different games with the same name, sometimes different names for one game. As it says in the article, this particular variant is also known as wari, owari, awale, etc. etc.

      Some of the variants feature bigger boards, and some even include the possibility of endless moves. Many of those are more complex or have bigger search spaces than the game from the article.

      So it seems there is still hope for mancala fanatics...
  • 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

  • Fun (Score:2)

    by dazdaz ( 77833 )
    Strangely enough, this is quite interesting.

    How about information on Japanese games?

  • Amazing. (Score:5, Funny)

    by unicron ( 20286 ) <{ten.tencht} {ta} {norcinu}> on Friday September 06, 2002 @06:49PM (#4209827) Homepage
    It seems the only way to win is not to play.

  • all 889,063,398,406 positions (Score:5, Funny)

    by Alien54 ( 180860 ) on Friday September 06, 2002 @06:49PM (#4209829) Journal
    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. ;-)

    • And you thought Doom 3 required a lot of resources? Baby ain't got NOTHING on Mancala!
    • 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?

  • Uhhh. (Score:5, Funny)

    by unicron ( 20286 ) <{ten.tencht} {ta} {norcinu}> on Friday September 06, 2002 @06:52PM (#4209850) Homepage
    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.
    • 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/... :):)
      • With the exception of Tic-Tac-Toe and possibly this Awari game, I can't think of a single game without some factor of luck/chance in it.
        • With the exception of Tic-Tac-Toe and possibly this Awari game, I can't think of a single game without some factor of luck/chance in it

          Checkers, Chess, Go, Reversi (=Othello(tm)), most Chess variants . . .
        • How about:
          Checkers (Chinese and domestic)
          Chess
          othello
          go

          None of these have any chance. They don't even have hidden information known to one player and not the other.

          • Re:double Uhhh. (Score:2, Insightful)

            by Derg ( 557233 )
            Maybe I'm missing something, but there is a Huge element of chance in all the games listed. Its that unless your playing against a computer, and even in that instance, there is a Chance of Human error. Someone may move a piece they didnt intend to. A program may have been written with a susceptibility in it that makes it less than perfect. There is no such thing as a game without chance, there is always the chance of a human error, since humans, despite what some may feel, are far FAR from perfet.

            Just my two cents...

            • A human can screw up playing tic-tac-toe too, it's just not that likely. When most people refer to a "game of chance" they mean something where randomness is supposed to be a fundamental part of the game, such as games that use shuffled decks of cards or dice.

            • That's a really strange usage of the word "chance" within the context of games. In tic-tac-toe, there is a chance your opponent will make a mistake, and then you could win. Of course, your opponent would have to be pretty stupid.
            • The reason I say that there is no chance is that for any move you make, you can look at the moves available to your opponent, and and for each of these, you can look at the moves available to you and so on. In a game like backgammon, monopoly, etc, there are dice or spinners or some element of randomness that keeps you from being able to make this kind of analysis.

              You might think that an opponent could fool this strategy by making a few moves that the computer didn't expect. This is possible if the computer is not playing a "perfect" game. 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. Therefore, it would expect you to make those moves and take whatever steps were available to it to keep you from being able to make those moves in the first place.
              • 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.
        • Global Thermonuclear War?
      • "...if you win or lose you know whose fault it is."

        No you don't.
    • So what do you think of global thermal nuclear war then?

  • 3500 year old technology (Score:3, Interesting)

    by cr@ckwhore ( 165454 ) on Friday September 06, 2002 @07:02PM (#4209910) Homepage
    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.

    • I'm not as impressed. Tic tac toe was probably invented even earlier, and it easily meets your definition of "mathematical perfection".

      • Re:3500 year old technology (Score:5, Funny)

        by micahjd ( 54824 ) <micahjd@users.sourceforge.net> on Friday September 06, 2002 @10:19PM (#4210707) Homepage
        /* 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);;;;;}}}

    • Sheesh, the didn't solve the game 3500 years ago. What's so mathematically astounding about it? A game has three possible outcomes: draw, first player to move always win, second player to move always win. None of the outcomes are more "pure" than any of the others./p:

      • Thats exactly what makes it amazing!! The game, operating on theory only (because they couldn't have solved the game 3500 years ago), turns out to be perfectly balanced, with no advantage to any single player.
        • I would find it quite unlikely that people 3500 years ago would have been able to work out game theory. Although people have displayed amazing ingenuity (see the pyramids of Egypt: built completely with manual labor, and we still aren't completely sure how they did it), an advancement such as game theory even before things as simple as decimals and fractions were even formalized would be pretty much impossible. More likely, people went by what felt fair and "right".
    • they had stone henge to use for development.
      • Yeah, they had to overrock it from 33 megaliths to 50 just to work out all the possibilities.
        • (* Yeah, they had to overrock [stonehenge] from 33 megaliths to 50 just to work out all the possibilities. *)

          He he.

          But technology progress stopped for thousands of years when the King declared that upgrading every 2 years was a royal pain in the back and forbid future upgrades.

          And that bronze sh*t was all just a fad.
    • 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.
    • You read too much into the word "perfect". Perfect just means that if both players played perfectly, then it would lead to a draw. With that long a time, all obviously lopsided games would have been deemed uninteresting. Someday, we should be able to prove that some games are perfect.
    • They also built the pyramids, calculated the radius of the Earth, and so on.

      The human brain hasn't changed that much in 3500 years; we were a pretty smart bunch back then. And of course, we didn't have computers so we actually used it now and then.

      RMN
      ~~~

  • 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.

  • 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
  • If perfect play didn't end in a draw, would this mean that the first player (or second) could do something to ensure a win?

  • Important Step? (Score:5, Insightful)

    by rockmuelle ( 575982 ) on Friday September 06, 2002 @07:10PM (#4209972)

    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 [flinders.edu.au].).

    -Chris

    • 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 ...

      Well... I understand the feeling ("just a huge brute force thing, nothing intelligent"), but consider your statement for a while. You are saying that researchers should NOT research methods humans do not use, but should try to simulate humans. While it is useful to try to understand the best information processor in existence that we know of (human brain), shouldn't it be even more interesting to find new ways of solving problems, methods this ultimate processing machine can not do? That is, to study these methods humans brains do NOT use? Otherwise, the best we could do would be just cloning existing system.

    • I'm currently taking a grad-level AI course from a major advocate (Dr. J. Weng) [msu.edu] 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 [msu.edu], 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.

    • Re:Important Step? (Score:2, Insightful)

      by jareds ( 100340 )

      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.

      Yeah, and the automobile industry ought to stop using tricks like "wheels" that allow cars to move in ways that humans never could, and switch to building giant two-legged robots.

    • Well, if you talk to human chess players that are very good, their skill lies in being able to look ahead and see as many possible moves as they can, as deeply as they can. There are standard game openings that they memorize, as well as standard game finishings. That's not much different than a big database, it's just that the middle portion is generated on the fly. That's pretty cool of us.

      So, excercises in deep search ARE sort of like Artificial Intelligence, in a way. It just seems kind of pointless when the whole game is solved - that's something no human would ever be able to do.

      • Good chess players think in terms of "blocks" on the board. They don't see individual moves and peices, they see larger conceptual board positions and sets of interrelated peices that confer advtanges to one side or the other, and they see "patterns" that are difficult to define in explicit terms. It was in one of Hofstadter's books this was brought up in examining how humans play chess.

    • Re:Important Step? (Score:3, Informative)

      by wfmcwalter ( 124904 )
      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.

    • If you take any strategic game, a human player will consider all of the possible moves that they can think of, whether or not these include all possible moves as defined by the rules of said game.

      How does this differ from human intelligence? Surely the fact that the machine can utilise a full range of options makes the machine more intelligent?

    • Re:Important Step? (Score:3, Interesting)

      by bwt ( 68845 )
      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.
    • I don't quite understand why a big lookup table is an important step for AI.

      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.

  • depends on what you call perfect (Score:5, Insightful)

    by Eric Seppanen ( 79060 ) on Friday September 06, 2002 @07:12PM (#4209979)
    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 [ualberta.ca].

    • 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.

    • 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..

    • That looks like a paper-scissors-stone competition.. I thought roshambo was where you kick each other in the nuts as hard as you can until someone falls over?

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

    • Re:Game board/peices? (Score:4, Funny)

      by cosmol ( 143886 ) on Friday September 06, 2002 @07:30PM (#4210098)
      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.
    • I have one of them... actually it's the spitting image to the one you see. It's even cooler when it is closed because there are a lot of designs woodworked into the outside. Anyway, I don't know where to get them. My ex-girlfriend got it for me when she went to Ghana.

  • Kind of Bummed - Just Brute Force (Score:5, Insightful)

    by zetetikos ( 150524 ) on Friday September 06, 2002 @07:20PM (#4210024) Homepage
    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?
    • You seem to think that it would be more likely to crack Go than chess. Chess, which develops from a fixed position, is much easier to solve (at least via brute force) than Go, which allows any starting position. Also, the chess board is 10x10, the Go board is 19x19. While both are incredibly hard games computationally, Go, to a programmer or theorist, is even harder than chess.

  • I can see it now... (Score:3, Funny)

    by littleRedFriend ( 456491 ) on Friday September 06, 2002 @07:50PM (#4210195)
    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

  • 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.
  • 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.
  • 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.
  • For prople who enjoy mancala-type games, and want to play something with more complexity which has not been solved yet, game inventer Christian Freeling has an excellent game called the glass bead game [mindsports.net].

    - Sam

  • 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.

  • They claim the game has over 800 billion distinct game positions - yet they computed a database to fully solve the game that took only 778GB of space. Doesn't this seem odd? You'd have to describe each position with an 8-bit number to fit them all, and that leaves no room for any other data (such as how they relate). What magic did they pull here?
    • "You'd have to describe each position with an 8-bit number to fit them all, and that leaves no room for any other data (such as how they relate)."

      The 8-bit identity could be implicity defined by the data's position in the database.

      For example, assume 0 = inevitable win for player 1, 1 = inevitable loss for player 1, 2 = inevitable tie, and 3 = unknown (i.e. 2 bits of data per position). Now assume that we only need 2 bits to store the game state. If we have a database of (2, 1, 3, 0). In only 8 bits of data, we've encoded that position 0 has result 2, position 1 has result 1, position 2 has result 3, and position 3 has result 0.

Slashdot Top Deals

He has not acquired a fortune; the fortune has acquired him. -- Bion

Close