Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Bot_bomb
        
(Message started by: fotland on Jan 5^th, 2004, 2:33pm)

Title: Bot_bomb
Post by fotland on Jan 5^th, 2004, 2:33pm

Bot_bomb does a full width search, with iterative deepening by steps, starting at step 3 and increasing one step per iteration. At 3 minutes per move it typically gets through 9 to 11 steps, or between 2 and 3 ply.

Pruning during the full width portion of the search is only due to null move cutoffs.

The evaluation statically recognizes the number of unopposed steps remining for each pawn to get to the goal (up to 8), and the number of unopposed steps to trap each piece (up to 6), and the number of steps required to prevent trapping of a piece (up to 4).

When there is a goal threat, a goal search looks up to an additional 8 steps, with move generation pruned to just moves relevant to that goal.

When there is a trappable piece, a quiescence search tries just the trapping moves until the end of the current ply (1 to 4 steps).

The evaluation function includes terms for pinned pieces (where a strong piece is defending a trap to prevent trapping of its own weaker piece), and pieces that are stuck on the trap with one defender.

It has terms for elephant and camel mobility, and keeping the camel away from the enemy elephant. When the camel in near the elephant, the camel wants to stay back, and does not want to be ahead of the elephant.

Pawn evaluation encourages pawns to stay in a connected line and advancing edge pawns and keeping center pawns back.

The biggest weakness I want to fix is to cause a coordinated attack on an enemy trap when it is safe to do so.

There are also many bugs in the goal and trap evaluations, since they are complex.

-David

Title: Re: Bot_bomb
Post by 99of9 on Jan 5^th, 2004, 3:49pm

Wow, very impressive!

Title: Re: Bot_bomb
Post by fotland on Jan 5^th, 2004, 8:58pm

Thanks. I put way too much time into it :) Probably about 500 hours total. The evaluation function, move generator and move maker is 3800 lines of C++, and
the search is 1500 lines.

Title: Re: Bot_bomb
Post by 99of9 on Nov 5^th, 2004, 3:30am

Welcome back bomb! Is it much different to last year? I guess we'll find out soon.

Title: Re: Bot_bomb
Post by Fritzlein on Nov 5^th, 2004, 9:03am

Wow, it's generous of you to share how Bomb works. Do you mind if I ask a few questions? I understand if you don't want to reveal trade secrets, but I'm curious if you are in a talkative mood.

1) Is it correct that Bomb uses no AI techniques? It doesn't learn and hasn't ever learned?

2) Is it correct that the camel-related parameters are specific to the camel and not the second-strongest piece? I.e. if both sides lose a camel and a horse, Bomb will not feel the same way about the remaining horses as it felt about the camels?

3) Is it correct that the value of the pieces doesn't change depending on what pieces are left? For example, if the opponent has lost both dogs and both horses, Bomb will still prefer a horse to a dog, and maybe even prefer a horse to a dog plus a rabbit? Or another example, if all the horses and dogs are gone on both sides, Bomb will still prefer a camel to two cats, and maybe even prefer a camel to two cats and two rabbits?

Title: Re: Bot_bomb
Post by fotland on Nov 8^th, 2004, 10:21am

bomb does not learn, and has never learned. I had planned to have it learn, but it's not clear what are interesting features.

All features are specific to the actual piece and not relative to the strongest piece left. I know this is not theoretically correct, but it is simpler, and I have never seen a game between strong players without both elephants (except for sacrifices to force immediate goal).

All values are indepent of the number of pieces left, except rabbits. When fewer rabbits are left, the value of each rabbit goes up.

The bomb now is only slightly different than last years. I worked on it a few weeks after the competition. I'd like to improve it more by late december, but I doubt I'll have time to do much.

Title: Re: Bot_bomb
Post by Fritzlein on Nov 9^th, 2004, 9:32am

Yes, my experience leads me to guess that fixing the pieces at constant values is not too big a deal. I notice it as a weakness only when one camel is gone but not both, or when both camels and a pair of horses are gone, or when both camels remain but about four smaller pieces on each side are gone. None of these happens often enough to be a big worry.

More significantly, as a "feature request", I'd like to see Bomb resist the framing of its pieces more vigorously than it does at present. I find that I can beat it consistently by framing one piece, and then collecting rabbits until I have a large material advantage. At that point I can convert without any particular brilliance.

If I couldn't easily frame pieces, I would have a hard time winning consistently. I guess next I would try to lure it into elephant traps, but that seems a less reliable strategy.

I will play experimentally in some games just to see what happens, i.e. to see if there is some other way I can figure out to beat Bomb, but it would be cool to be _forced_ into such creativity by the failure of more formulaic means.

Title: Re: Bot_bomb
Post by 99of9 on Nov 9^th, 2004, 4:57pm

David,

Remember you asked how could my bot be searching more nodes than yours but yet not going as deep at full width. I said that because I don't use null move my full width is wider than yours. But that's probably not the whole explanation. Most likely my move ordering is also much worse than yours, so I just have to examine more than you. That's something I've been preparing to improve.

Toby