Please create an account to participate in the Slashdot moderation system

 



Forgot your password?
typodupeerror
AI Programming Software Games

Computer Beats Humans At Arimaa 58

An anonymous reader writes A computer engine has beaten humans at Arimaa, an abstract strategy game, in the official human–computer challenge of the year. Sharp, as the bot is called, had to beat each of three strong human players in a best 2-out-3 contest and managed to sweep the first two rounds, thereby already guaranteeing victory. Its developer David Wu will receive a $12,000 prize, contingent on him submitting a paper describing the program to the International Computer Games Association.
This discussion has been archived. No new comments can be posted.

Computer Beats Humans At Arimaa

Comments Filter:
  • by Anonymous Coward

    Better than smartphones!!

  • what is Arimaa? (Score:5, Informative)

    by Gravis Zero ( 934156 ) on Sunday April 19, 2015 @07:56PM (#49507183)

    Arimaa is a two-player strategy board game that was designed to be playable with a standard chess set and difficult for computers while still being easy to learn and fun to play for humans. Every year since 2004, the Arimaa community has held three tournaments: a World Championship (humans only), a Computer Championship (computers only), and the Arimaa Challenge (human vs. computer).

    seriously, slashdice, some reference would be nice sometimes.

    • Re: (Score:2, Informative)

      by Anonymous Coward

      The wiki link seemed to sum it up nicely...

    • It was the first link in the submission. :)

      There you see it
      Sitting there across the way
      It don’t got a lot to say
      But there’s something about it
      And you don’t know why
      But you’re dying to try
      You wanna click the link

      You’ve got to click the link
      Why don’t you click the link
      You gotta click the link
      Go on and click the link

      • by GTRacer ( 234395 )
        Little Mermaid, right? I'm supposed to sing that to the tune of "Kiss De Girl"?

        Because I totally read that in Sebastian's voice!
    • Arimaa is a two-player strategy board game that was designed to be playable with a standard chess set and difficult for computers while still being easy to learn and fun to play for humans. Every year since 2004, the Arimaa community has held three tournaments: a World Championship (humans only), a Computer Championship (computers only), and the Arimaa Challenge (human vs. computer).

      seriously, slashdice, some reference would be nice sometimes.

      Given the youth of the game I suspect there is much less analysis and history in
      support of the game. The difficulty that computers faces is the same one that players face and
      while depth search for a computer is difficult it is more difficult for the human player.

      The game was invented in about 2002... and chess has a history that spans 1500 years
      and Go 2500 to 4000 years.

      While difficult to test I suspect that if we restricted chess players to the same age
      and tenure profile of Arimaa players a machine woul

      • While difficult to test I suspect that if we restricted chess players to the same age and tenure profile of Arimaa players a machine would romp over the novice chess players (max experience 13 years, average perhaps 7).

        You're a decade too late. Even a modestly budgeted machine will (if not intentionally underpowered) romp over master chess players.

        I get what you're saying and I'm sure an arimaa grandmaster, if one existed, could beat that particular program. However, you're ignoring the other side of the coin. There have been orders of magnitude more effort expended on writing chess-playing software vs. arimaa-playing software.

        Now should I bother to learn the game at all?

        Go is much simpler and deeper (although computers are getting pretty good there, too.)

        • by itzly ( 3699663 )

          You're a decade too late. Even a modestly budgeted machine will (if not intentionally underpowered) romp over master chess players.

          A decent smartphone will romp over grandmaster chess players.

          • A decent smartphone will romp over grandmaster chess players.

            Is this actually true? I'm aware of the recent grandmaster-in-the-bathroom-with-an-iPhone scandal but I had assumed the phone was tied to a desktop at home doing the analysis. My reasoning was thus: ARM processors aren't as powerful (hz for hz) as x86, the existing ARM-optimized chess codebase is presumably much smaller, and most importantly the processing power of smart phones is limited by both heat dissipation and battery life.

            I would be surprised if a high-end smartphone in the world could out-comp

            • by santiago ( 42242 )

              I would be surprised if a high-end smartphone in the world could out-compute a reasonably spec'ed desktop from the early 2000s (which was point at which computers began to rather consistently beat grandmasters.) The lack of CPU fan is the biggest limiting factor of all.

              An iPhone 6 can do 77 GFLOPS. [anandtech.com] Deep Blue could only manage 11 GFLOPS. [wikipedia.org] Now, Deep Blue had specialized VLSI chips that are hard to measure, and chess computations are going to be mostly integer, not floating-point, but the point stands that a modern phone has plenty of computing power for crushing puny meatbags at chess.

              • That is quite interesting, but I think my point may stand. Remember, standard chess matches last for hours. How long can the phone maintain maximum power before having to throttle to keep itself from burning up? And even if heat isn't an issue and we assume it's plugged in, can it pull enough juice through a USB charger to maintain that power? (My Nexus 7 loses power faster than it charges while I'm playing a graphics intensive game.)

                Also, I'm not sure why Deep Blue was rated in terms of FLOPs. I don't
    • by linearZ ( 710002 )

      I guess it wasn't *that* difficult for computers. Were the human opponent 4 years old?

  • by turkeydance ( 1266624 ) on Sunday April 19, 2015 @09:07PM (#49507497)
    how about computerS beat humanS? or one computer beat one human? or this computer beat that human? hey, i could beat you given enough chances.
  • Arimaa info (Score:3, Informative)

    by Craigory ( 553911 ) <cfalls@REDHATcs.unc.edu minus distro> on Sunday April 19, 2015 @09:10PM (#49507525)
    You can play the android version of the bot here: https://play.google.com/store/... [google.com] It comes with a good tutorial on how to play. Relevant xkcd comic: https://xkcd.com/1002/ [xkcd.com]
    • by linearZ ( 710002 )

      Robot wins Beer Pong? Kids these days need robots to tell them when to drink? Ingrate whipper snappers.

  • by epine ( 68316 ) on Sunday April 19, 2015 @09:32PM (#49507643)

    This is the most substantive bit I was able to find, a forum post by David Jian Wu from eariler today:

    Thanks for the questions! [arimaa.com]

    I can't even find a discussion of the winning games by someone who knows the game and its strategic evolution.

    Interesting, but at present there's nothing much to discuss here.

  • How soon can I hope to see powerful AI in 4x games? When will the Civilization AI be able to beat me without cheating?
    • by ledow ( 319597 )

      Work out the number of options that can possibly be performed each second. Literally, how many icons you could click, things you could build, things building that you could cancel, things built you could destroy, things you could move, etc.etc.etc. With 4K games there's probably hundreds of options at each point. If you get to non-tile-based games, it's almost an infinity unless you break it down to tile-based areas. How finely you do that determines how finely the computer can deploy units, etc.

      Now mul

      • by abies ( 607076 )

        I don't think it is THAT complicated. You don't really have hundreds of options each time - you have probably 10-20 options or so like 'explore', 'invest in infrastructure', 'build up military', 'attack players', etc. For each of these goals, you might need to do number of small actions - but I don't think this part is hard for computers. Given goal of 'churn out best miliary units in 5 turns', computer should be always able to come up with optimal set of moves.
        Now, moving between these higher level goals i

        • by ledow ( 319597 )

          You've just done what the programmers do. Introduce higher-level heuristics into the rules by pushing everything into blocks of actions.

          No different to "find enemy", "target enemy", "shoot enemy". The problem is not breaking down a problem given the goal (in your example, every path taken to get from "I want to build a farm" to "I have built a farm here" is equal-cost to the computer) - a simple optimisation removes them from the tree, yes.

          But then you either get them, say, building on tiles that are the

      • by leaen ( 987954 )
        That is not main problem. Main problems are that players won't pay extra for better AI so managers decide to save on AI. Players only say that they want challenging AI yet expect to beat it every time.
        Its easy to make strategy where AI reigns supreme. It would be focused on micromanagement ideally with complex resource system.
        For 4X there is simple AI strategy that would incredibly piss players: Borg diplomacy. At first turn all AI players do distributed roll of dice to select borg player. Every other b
        • by vux984 ( 928602 )

          For 4X there is simple AI strategy that would incredibly piss players: Borg diplomacy. At first turn all AI players do distributed roll of dice to select borg player. Every other bot transfers all his resources to borg or makes everything for borg to win.

          One of the constraints for any interesting solution is that the AIs not prioritize beating the human player over the other AIs; and that the AIs are each playing to win themselves.

          • by leaen ( 987954 )
            > One of the constraints for any interesting solution is that the AIs not prioritize beating the human player over the other AIs Thats arbitrary constraint that is hard to enforce. If computer learns about other players he finds that attacking human while weak increases his winning chances. And there is no need to discriminate AI vs human, just give human 1/N of times game while rest of time write him message surrender or you will be assimilated. The only problem is learning player identity/trustworth
  • Arimaa is computer childs play, however no computer could ever beat Sirna Kolrami at Strategema. At best all one could expect is a draw.

  • by Tom ( 822 ) on Monday April 20, 2015 @08:14AM (#49509515) Homepage Journal

    Actually much more interesting than I thought at first glance.

    The game is designed intentionally with computational complexity in mind. It failed. The rules (WP has them, or a dozen other sites) are mostly designed to increase the search space. For example, instead of the fixed setup in chess, you get basically the same pieces, but you can put them into your 2 rows in any way you want. I'm too lazy to calculate the initial starting positions, but thanks to the Internet, someone else did it and came up with ~10^15. That makes an opening library practically impossible.

    However, I'm a hobby game designer, so I look at rules with slightly different eyes. The complexity of the game is largely artificial. Brilliant minds will, like in a badly designed crypto-cipher, find tons of places where the complexity can, for the practical purpose of actually playing and winning a game, be reduced dramatically. Remember that in theory chess has 20 valid opening moves for white. The vast majority of them you will never seen in any real game.

    I'm also bothered by the fact that complexity is reached by the addition of rules, instead of the subtraction. Go is a perfect example for how you can reach complexity with very simple rulesets. When building games, especially board games, you generally strive to keep the ruleset as simple as possible and check every rule for whether or not it adds anything worthwhile to the gameplay or not. For a simple, conventional style 2-player board game, the ruleset is overly complex IMHO. Maybe that's why I never heard about this game before - it doesn't actually appeal to many human players, except those interested in not being beaten by a computer.

  • Many years ago, it was assumed that in order for a computer to beat humans at chess that major advances would have to happen in artificial intelligence. In the end IBM just simply brute forced an approach by basically allowing the computer the equivalent of an open book test against a poor human who could only go by memory. Maybe some improvements got made in searching in order to beat humans, but I think that's about it. I know that arimaa was developed in the hope that it would spur new AI advances in
  • I wrote a program about 6 months ago that can beat a human at literally any game that I make up and don't explain.

"Life is a garment we continuously alter, but which never seems to fit." -- David McCord

Working...