Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> General Discussion >> Why do bots play Arimaa badly?
        
(Message started by: Fritzlein on Apr 15^th, 2005, 8:15am)

Title: Why do bots play Arimaa badly?
Post by Fritzlein on Apr 15^th, 2005, 8:15am

on 04/14/05 at 17:45:14, Arimanator wrote:

the attacking capablities of arimaa are manifestly blunted when compared to chess where it is as easy to take a piece as to move in an empty space

Very true. The more I think about it, the more I feel that the difficulty of capture is the main reason computers have difficulty playing Arimaa well.

I am not convinced that the high branching factor is very important. So what if there are 20,000 moves to choose from? Why doesn't that mean humans always overlook the best move because they don't have time to look at them all? Why doesn't a higher branching factor give computers a greater advantage over humans?

Look at chess, for example. If a human plays a computer at chess, the human will often be relieved to trade queens. Why is this? Trading queens reduces the branching factor, so it means computers can look deeper, so it ought to be an advantage to the computer, right? But it isn't. The important thing about trading queens is that attacking capability is reduced. With the queens gone there is less chance for the position to change dramatically in a couple of moves. This increase in stability favors humans.

Omar, I know you intentionally put in a huge number of possibilities per move in order to thwart computers, but I am going to guess that the more important thing you did was the playtesting. We can have abstract theories about what makes a good game, but you never know for sure until you try.

IMHO, what makes Arimaa a great game, besides the simple rules, is that offense is just a tiny bit stronger than defense, but defense is strong enough that there is lots of strategy. In chess, similar pieces can take each other, but in Arimaa similar pieces can't hurt each other. This added bit of defensive power means that, although captures abound in lower level games, ultimately when both sides are playing carefully and well, you have to do something special to capture a piece.

Title: Re: Why do bots play Arimaa badly?
Post by jdb on Apr 15^th, 2005, 2:32pm

Quote:

This increase in stability favors humans.

I agree with this comment. One strategy for beating *all* current arimaa bots is the "do nothing, but do it well" approach. For example, that's what I tried to do againt bomb in the postal tournament.

As far as I know, no one has discovered a strategy in Arimaa that forces the game into a period of instability. If such a strategy is discovered, it will help out the bots a great deal.

Once some pieces have been captured, instability can be forced by advancing rabbits. The opponent can't really ignore the threats. Bots do ok in this situation, because typically the goals are much more immediate in unstable situations.

Another reason the bots play poorly, is that the strategy in Arimaa is constantly evolving. Last year the elephant blockade was discovered. This year the Elephant/Horse attack came along. In both cases, if the bot doesn't know about the particular strategy, it is finished. Personally, I haven't implemented any knowledge of the EH attack, because I'm waiting until the strategy surrounding it becomes more concrete.

If it turns out that instability can be forced, then the branching factor will be in the bots favour, instead of the humans!

Title: Re: Why do bots play Arimaa badly?
Post by RonWeasley on Apr 18^th, 2005, 8:29am

Quote:

You don't expect a frog to beat you at arimaa do you?

There may be two or three in the Forbidden Forest that might give me a good game.

Please, Arimanator, I just can't handle this kind of temptation. I've already accidentally made an off-color remark about a player's wife, and now this.

Title: Re: Why do bots play Arimaa badly?
Post by omar on Apr 27^th, 2005, 2:06pm

on 04/15/05 at 08:15:43, Fritzlein wrote:

I am not convinced that the high branching factor is very important. So what if there are 20,000 moves to choose from? Why doesn't that mean humans always overlook the best move because they don't have time to look at them all? Why doesn't a higher branching factor give computers a greater advantage over humans?

A high branching factor really does limit the performance of a program that uses a tree search approach. A high branching factor has almost no effect on humans, since humans take a top down as opposed to a bottom up approach to constructing a move. What hurts humans is if the proximity of the pieces can change a lot from one turn to the next.

In the example of exchanging queens in chess; the fact that it reduces the branching factor is not as important as removing pieces that can cause large physical changes from one turn to the next. The game got easier for the computer after exchanging the queens, but it got a lot more managable for the human.

My earliest attempts at making a difficult game for computers was just to give each player multiple moves per turn while keeping the movement of the pieces the same as in chess. The multiple moves, did increase the branching factor, but it also ment larger physical changes on the board. After trying out some games like that I realized that I just could not deal with the huge changes that happen from one turn to the next. The break through came when I was trying to teach Aamir to play chess. To make things easier we played with just the king and pawns. That was when I realized that keeping the movement of the pieces small while allowing multiple moves was essential to making the game difficult for computers. The multiple moves per turns still increased the branching factor, but the small one step movements kept the physical change on the board small enough that it was easy for humans to cope with.

The smaller changes also means that it will take more turns to accomplish something like a capture. But that itself is not enough to make the game more difficult for computers. For if the game had a low branching factor and small change per turn, a computer could still find forced lines that lead to a capture or some other advantage. A high branching factor makes it more difficult to find forced lines; thus requiring the computer to play by strategy and not tactics.

So I think it's the combination of a high branching factor and small physical changes from one turn to the next that makes Arimaa difficult for computers.

Of course if a game doesn't have captures or other elements that can be used to determine the value of a position, it could still be very difficult for computers even with a low branching factor. Actually Arimaa also did not have trap squares or capturing at one point. But the game felt a bit dull that way. I added trapping just to make it more interesting for humans.

Title: Re: Why do bots play Arimaa badly?
Post by Fritzlein on Apr 28^th, 2005, 9:36am

Thanks for sharing this description, Omar.

I'm trying to imagine Arimaa without captures. At the least there would have to be fewer pieces on the board to prevent it from getting all blocked up.

It certainly does add an element of interest to have captures, even if captures are a sudden, permanent change in the position, and thus favor computers somewhat. But I think the captures do more than make the game exciting for humans: I think they also add to the strategic depth.

The hardest part of Arimaa strategy to say anything intelligent about is rabbit advancement, because it has pros and cons both. Getting a rabbit closer to the goal is balanced by being in greater danger of capture. If there were no capture, I imagine both sides would flood their rabbits forward from the start. But with capture the tension means that there is an important strategic judgement that is not easy for humans to grasp, much less computers.

For example, Omar, in our postal game I felt sure you were going to advance rabbits on moves 43w and 44w, but instead you pushed a rabbit of mine forward! Clearly we had differing views of the position, because you thought material threats were more important and I thought goal threats were more important. I have no idea who was right, but this decision is a strategic dilemma which wouldn't exist without the capture rules.

Whatever the proportion of theory vs. playtesting vs. chance that went into the design of Arimaa, the result is phenomenal.

Title: Re: Why do bots play Arimaa badly?
Post by omar on May 5^th, 2005, 10:40am

on 04/28/05 at 09:36:30, Fritzlein wrote:

I'm trying to imagine Arimaa without captures. At the least there would have to be fewer pieces on the board to prevent it from getting all blocked up.

You're right about that. The version without traps also did not have the camel and four of the rabbit (actually I should say queen and four pawns, since it was always played with a chess set).

As Pat mentioned there is something in our nature that gets our adrenaline pumping if the potential for capture is there. I definitely noticed that when I was trying out different rules.