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

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?

[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?

[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?

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

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/

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

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.