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.
First post for games!!! (Score:1)
Better than smartphones!!
Re: (Score:2)
what is Arimaa? (Score:5, Informative)
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)
The wiki link seemed to sum it up nicely...
Re: (Score:1)
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
Re: (Score:2)
Because I totally read that in Sebastian's voice!
Re: (Score:3)
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
Re: (Score:3)
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.)
Re: (Score:2)
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.
Re: (Score:2)
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
Re: (Score:2)
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.
Re: (Score:2)
Also, I'm not sure why Deep Blue was rated in terms of FLOPs. I don't
Re: (Score:2)
Re: (Score:2)
I guess it wasn't *that* difficult for computers. Were the human opponent 4 years old?
Re: (Score:1)
Re: (Score:2)
So the game designers screwed up, and it is humanity's fault that we're too stupid?
"computer beats humans" (Score:3)
Re: (Score:1)
Arimaa info (Score:3, Informative)
Re: (Score:2)
Robot wins Beer Pong? Kids these days need robots to tell them when to drink? Ingrate whipper snappers.
discussion way too premature (Score:4, Interesting)
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.
Re: (Score:2)
4x strategy when? (Score:1)
Re: (Score:3)
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
Re: (Score:2)
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
Re: (Score:2)
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
Re: (Score:1)
I wanted to mod you up but computer says not today.
Re: (Score:1)
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
Re: (Score:2)
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.
Re: (Score:1)
There's one game a computer cant win - Strategema (Score:2)
Arimaa is computer childs play, however no computer could ever beat Sirna Kolrami at Strategema. At best all one could expect is a draw.
Re: (Score:2)
interesting (Score:3)
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.
In the end did Wu just brute force it? (Score:2)
Not surprising (Score:2)
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.