Computer Beats Humans At Arimaa

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.

Comments

First post for games!!!

[Anonymous Coward]

Better than smartphones!!

what is Arimaa?

[Gravis Zero]

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:what is Arimaa?

[Anonymous Coward]

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

Re:what is Arimaa?

[kcwhitta]

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:what is Arimaa?

[niftymitch]

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 would romp over the novice chess
players (max experience 13 years, average perhaps 7).

Now that there are champion machines the game may well move into the
class of games only played by machines. Or, Programmers and hardware mfg
consortiums could compete little different than the America's Cup.

The game might prove the ideal context to form a man+machine or team+machine contest
where the men shape strategy and the machine carries the game to conclusion
with nudges from the man-power.

Now should I bother to learn the game at all?

Re:what is Arimaa?

[linearZ]

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

Re:what is Arimaa?

[Anonymous Coward]

Now should I bother to learn the game at all?

Nope, but Firaxis could work on making a better AI for Civ:BE.

Re:what is Arimaa?

[foreverdisillusioned]

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

Arimaa isn't a bad game, but despite the claims of its creator I'm not convinced it's simpler than chess. Chess has a few idiosyncratic and tournament-specific rules (three move repetition, castling, double pawn move and the rare en passant capture, having to "checkmate" the king instead of simply capturing him, etc.), but if you ignore those for a moment... chess has straightforward capture, a static setup, and a single method of winning the game. The only thing you have to actually memorize are the 6 different piece movements, the unique rule about knight movement, the unique rule about pawn movement, and the promotion of pawns bit. That's pretty much it. All of the other rules in chess are there for historical reasons or to improve the pace of gameplay among experts--they don't drastically affect the flavor, tactics or depth of the game. If armiaa became a worldwide pastime played by millions, they would surely develop their own array of minor rule tweaks.

So, compare chess's fundamentals (ignoring the ) these are arimaa's fundamentals:

1. Moving one piece one square (plus pushing/pulling--see below) counts as one move. You make four moves per turn. Not bad. It's only slightly more complicated than "move one piece per turn", yet being able to split up a single turn among multiple pieces or pool it all into a single piece is a great way to add depth. (It's not unlike action points in Fallout.) And other than rabbits the pieces all move the same way--obviously, this is simpler than chess.

2. Piece interaction and capture is, um, involved. First, you have a nested hierarchy of pieces that must be memorized (yes, it's "easy" because it's easy to remember that an elephant is bigger than a horse but I don't think that makes it simpler than chess's "any piece can capture any other piece".) Second, there are four different ways to influence an enemy piece: you can pin, pull, push or blockade (blockades only exist in chess in the special case of pawns.) This influence can be used to maneuver an enemy piece over a special trap square, which is which kills the piece... unless there's a friendly piece nearby to save it.

There's a sort of intuitive, real world justification for what is going on ("you see, the horse is grabbing onto the cat's tail, and these four squares here with stickers on them are actually deep holes..."), but I'm not sure how you can call the actual game mechanics simple as compared to chess.

3. The victory condition is getting a rabbit to the other side of the board or killing all of the opponent's rabbits. Like pawns, they can't move backwards. Let's just consider for a moment a game of chess wherein the goal of "kill the king" (again, we're ignoring all of this checkmate nonsense that grew over the centuries) was changed to "kill all of the opponent's pawns". That this would make the game deeper, I don't doubt... but simpler?

Re:what is Arimaa?

[itzly]

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:what is Arimaa?

[GTRacer]

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!

Re:what is Arimaa?

[foreverdisillusioned]

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

Re:what is Arimaa?

[santiago]

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. Deep Blue could only manage 11 GFLOPS. 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:what is Arimaa?

[foreverdisillusioned]

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 see how floating point operations are relevant to discrete problems like chess position analysis.

Re:what is Arimaa?

[foreverdisillusioned]

Ah I see you already noted the FLOP thing. My reading comprehension sucks today

What in the fuck?

[Anonymous Coward]

Is this news?

Re:What in the fuck?

[Drakster]

It's news as the game was designed to be difficult for an AI to play and win.

Re:What in the fuck?

[dwye]

So the game designers screwed up, and it is humanity's fault that we're too stupid?

Re: Old Google Maps beats new

[Anonymous Coward]

The google of today you mean, yes.

"computer beats humans"

[turkeydance]

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.

Re:"computer beats humans"

[Anonymous Coward]

RTFS

Re:"computer beats humans"

[umghhh]

there is at least one board full information game where you still can.

Re:"computer beats humans"

[Anonymous Coward]

there is at least one board full information game where you still can.

If you are referring to GO then it depends on how good you are. There are some good GO AI's these days that have a decent ranking. At the least they could easily wipe the floor with a beginner and be a challenge to casual players, perhaps better.

Arimaa info

[Craigory]

You can play the android version of the bot here: https://play.google.com/store/... It comes with a good tutorial on how to play. Relevant xkcd comic: https://xkcd.com/1002/

Re:Arimaa info

[linearZ]

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

Re:Arimaa info

[Anonymous Coward]

... android version ...

I bought this a few months ago when I first saw Arimaa, now it's free. Arrgh; the cost of being early.

Oh yeah?

[Anonymous Coward]

Get back to me when computers beat us at drinking or anal sex. Then I'd start worrying.

Re: Oh yeah?

[Anonymous Coward]

When a computer is beating you at anal sex, I sure hope you'd be the first to notice.

discussion way too premature

[epine]

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!

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:Old Google Maps beats new

[bistromath007]

nobody likes beta

Re:Old Google Maps beats new

[Anonymous Coward]

Nah, see yah gotta put it like, "Where is your Beta now, motherfucka?!"

clickbait

[Anonymous Coward]

Wow, lets run off to find out what Arimaa is and why this is an achievement, wait. Fuck that.
I don't come to slashdot to be clickbaited off to other sites just to work out wtf the subject of the story really is.
As Gravis Zero said, reference would be nice. No one likes being FORCED to research things, if I'm interested I will force MYSELF.

Go, last bastion of humanity

[Anonymous Coward]

This leaves Go as the last deterministic game where humans retain a lead over computers at the top levels of play I believe?

I can't imagine a deterministic game of complete information more difficult for AI than Go.

4x strategy when?

[Iamthecheese]

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

Re:4x strategy when?

[ledow]

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 multiply by the average length of a game expressed in these "actions" (where several actions may constitute one in-game turn). We're probably talking thousands again.

The game trees thus get huge very quickly. The more possibilities, the larger the trees. If you have 50 options on the first go, and 50 on the second that's 2500 possibilities to be investigated before you even get two "actions" in. Yes, the tree narrows as units become unable to move to certain places, upgrades can't be selected again, etc. but not by enough to matter mathematically.

Now consider that each path has to be evaluated somehow. You have to get a number that says how "good" that move is relative to all the alternatives. That's a lot of calculation and guesswork and heuristics and analysing the entire state of play, and "looking ahead" at what could be next go. Now multiply that out to how much a human is considering, probably 50+ actions or more ahead even if each action isn't that drastic on its own, you will have formulated a gameplan after the first few times of playing.

Now consider that just ONE company is working on the AI for one purpose - to make it entertaining. They can't spend decades and lots of PhD time on it.

Is it really that surprising that a good AI player is hard to find?

AI - on level terms - sucks. If the AI player can only make as many moves as you can per turn / per second then pretty much it won't be able to do much against a human. In FPS - maybe, but that's just because the "game" is really a matter of finding a dot on the screen that's part of you and shooting first. How it does that, if you gave it human-level reaction times, would make it lose every time. It can't formulate, strategise, etc. in such an open world and the programmers thus fall back on programmed heuristics ("try and get behind the player", "follow the sound", "run when you're low on health", etc.).

Even chess, something with only about 8-20 paths available to a player at each point, highly logical, repeatable, and laid-down, gets into trees so deep that it takes a supercomputer and DECADES of research to beat humans who are good at it. Go is an even simpler game in terms of rules, and yet a 19x19 board can baffle the best of AI you might be able to run because it's got such huge game trees (not even anywhere near 19x19 possibilities each go, much smaller, but the game goes on for so long!).

You aren't going to see a decent AI computer player until, quite literally, we have AI. Literally intelligence capable of learning on its own. And you're not going to see that in a commercial game any time soon because we don't even have that anywhere in the world yet.

All the AI you've ever played against in commercial games that aren't the subject of intense established research (e.g. Tetris, chess, Go, etc.) is going to be programmed heuristics. If this, then do that. That's it. If it doesn't cheat or vastly outnumber you, you will win every time - once you have the hang of which if...then rules it's using.

This is the cost of intelligence - you are able to formulate an idea about how the COMPUTER is working just by playing against it, gain insight from testing those ideas, and thus formulate a strategy to beat that opponent. Generally, you can only be beaten - over time - by ever-changing strategies (e.g. boss levels that change how they operate, change what their weaknesses / rules are) or by being vastly handicapped.

If you want that, wait 100 years, or play against other humans.

Re:4x strategy when?

[abies]

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 is certainly non trivial. But these are longer term decisions (few turns probably), so I don't think that decision tree explodes that much - if you keep micromanagement and high level goals separate.
With chess, separating overarching goals from low level movements is a lot harder, as every move influences a lot more aspects of play and a lot of choices are effectively forced on both sides when you go down certain path. When you want to improve your city by building farms with no enemy units in close range, it really doesn't matter which of grasslands you go to first. I'm quite sure that most players play these things on 'auto' anyway.

I'm not trying to say that AI in cmputer games is easy. I'm just saying that trivially multiplying all possible choice of inputs by length of game and comparing that number to chess is not really fair.

Re:4x strategy when?

[ledow]

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 most at risk from attack because "it doesn't matter which tile". You know that because you infer it from other information, the computer doesn't. Either it has to specifically check EVERY time (game tree), or pick a random / northernmost grassland to upgrade first (programmed heuristic).

Although the exact tree is prunable, the above is the way to get yourself into the same order of magnitude. And computers can, and do, and will struggle with trees of that magnitude for even simple actions unless they are following heuristics.

But, the biggest part you've skipped over - knowing that you need a farm to do X to do Y to do Z in N moves time is the real struggle, the real key. Optimising a tree for the low-hanging fruit (pardon the pseudo-pun) is trivial and can be done automatically and save you a handful of necessary steps.

But what if the system is attacked halfway through the process? Do we abandon? Start again? Fight on valiantly until we get where we want no matter the cost? How do we decide we need a farm? That's where the VAST majority of the game tree decisions are made and that's where the decision matters and THAT'S the difficult question to answer such that a computer can't do it in real-time given the possibilities and the impact of those. Or you'll see it build farms while you quietly strip away its land, units, etc. and it won't "notice".

Think of pathfinding, because that's what you're doing (just through a "directed graph"). There is no difference, to the computer, between A* pathfinding through a terrain and working out the best way through a game tree.

Some routes are muddy and slow you down, some routes lead to loops where you come back to where you are, some routes take more "steps" but get you there quicker, some routes are only a single step but take forever to walk through, some steps are more risky, some steps are safer.

Evaluating those for a computer means enumerating them, and their children, and their grandchildren - and virtually all of them until there's a point that you know it's definitely worse than some other route. How deep you go down the tree increases the complexity, but also increases the chance you have a strategy that works in the long-run. Not traversing to a certain depth means you're only thinking in the short-term.

And every time you enumerate some risk, factor or cost, you are required to formulate it into a single calculation ("edge cost" in graph theory terms). That means giving it a weighting (heuristics!) or determining a weighting dynamically, performing calculations, maybe looking at the surrounding areas (this path is quicker but is nearer the enemy etc.).

I studied graph theory for several years at uni. This stuff sounds really basic, boring, easy and predictable. We all know how mini-max algorithms work on simple games like draughts/checkers. But as soon as you try to scale to anything even vaguely complex you see factors, costs and weighting that are required and which greatly affect the performance of the search (and, hence, the AI).

If there are only 10-20 options like explore and they each take, say, 10 turns to complete, then the computer is only making a decision every 10 turns in effect. Which means it can't react. Sure, you could program an interrupt on certain events. But then it might ignore your attack for 5 turns so being "dumb" and giving you an advantage. Or if you interrupt it every turn with SOMETHING, it's basically back to having to evaluate every single move.

Re:4x strategy when?

[Anonymous Coward]

Yeah, I'm like 99% sure when he said "cheating" he meant 'gets arbitrarily more resources than me' and not "How it does that, if you gave it human-level reaction times, would make it lose every time.".

If I am playing starcraft and the AI has a better APM than me or more precise micro (I can imagine fighting perfect blink stalker micro being just horrendous) that is fine, it is using advantages it has in a fair game. If when it mines minerals it just get 20% more (and 30% on normal, 40% on hard) that is crap, and what is usually meant when someone says 'the AI cheats'.

Re:4x strategy when?

[leaen]

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 bot transfers all his resources to borg or makes everything for borg to win. This improves winning chances of each invidiual bot. So we could focus on games 1x1.
Also there is unbeatable starcraft AI since 2010 http://kotaku.com/5667280/you-...
You could also try C-evo where AI doesn't cheat but its bit old.
Also main human advantage is in combat. Without that it turns into building race that is easier to optimize.
As you mentioned Civ 5 main problem is that AI is terrible. It shouldn't be too hard add mods so you will rarely wins. Just take highly formulaic strategies from forums and have Etiopian AI doing regilious/cultural ICS, babylonian science victory, greek diplomatic... you can't block them all.

Re:4x strategy when?

[vux984]

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:4x strategy when?

[Fazed]

I wanted to mod you up but computer says not today.

Re:4x strategy when?

[leaen]

> 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/trustworthness to enforce contracts. Denying that to AI is human cheating as humans learn how to beat specific AI > ; and that the AIs are each playing to win themselves. In multiplayer game best strategy is to cooperate. Its much better when two players do alliane on turn 1 and coordinate attacks destroying everybody else and then have 50% chance on endgame than go to war at start and be weakened. Similar diplomatic AI would make temporary allliance of all neighbours of nation to dogpile him. So if there is politics its evolves to borg-like strategy. At first turn N/2+1 civs would make alliance to eliminate others. Only way for rest would be to make secondary alliance. And in any case human should follow orders of his robotic overlord or be punished as traitor.

There's one game a computer cant win - Strategema

[SirDrinksAlot]

Arimaa is computer childs play, however no computer could ever beat Sirna Kolrami at Strategema. At best all one could expect is a draw.

interesting

[Tom]

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.

Re:There's one game a computer cant win - Stratege

[Vermonter]

And a computer can never beat me in Tic Tac Toe, only reach a draw.

In the end did Wu just brute force it?

[Zontar_Thing_From_Ve]

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 order for a computer to beat humans. I have no idea - did Wu just simply brute force his way to victory? Is arimaa so little played by humans that the best players are far weaker at it than humans are at chess and thus it just wasn't all that hard to eventually write a program that could defeat the best human players? Did Wu actually advance the art any with his winning program?

Re:There's one game a computer cant win - Stratege

[Anonymous Coward]

And a computer can never beat me in Tic Tac Toe, only reach a draw.

The only solution is Thermo Nuclear War.

Re:FWIW Deep blue beating kasparov was a HOAX

[Shortguy881]

That's even more impressive. How did they fit so many grandmasters into that box?

Not surprising

[StikyPad]

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.

Yavoch!

[Anonymous Coward]

I wonder how a computer would do at Yavoch -- www.Yavoch.com

Elements of Chess, Poker and Dice all in one 3D game.

My kids and I enjoy it more than Chess.