Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Win by immobilization
        
(Message started by: Nazgand on Jul 4^th, 2011, 11:54pm)

Title: Win by immobilization
Post by Nazgand on Jul 4^th, 2011, 11:54pm

I was wondering if anyone programmed their bot to prefer moves that left the opponent with fewer options. I think this would be a powerful heuristic; I think win by immobilization is most impressive.
Edit: to be clear, I suspect that modifying a bot to have this preference would allow it to win more often.

Title: Re: Win by immobilization
Post by Swynndla on Jul 6^th, 2011, 4:24am

While lots of moves would be generally good, I think you'd have to be careful, as some positions with less number of moves available than the opponent are actually winning positions (think camel hostage, or even horse frame on one trap, and a camel hostage by the other). But yes generally more moves should be an advantage I would think (and Fritz might even provide some statistics when he gets back from holiday if we're lucky).

Edit: but yes, I too would be interested to know if anyone has programmed that into their bot's evaluation.

Title: Re: Win by immobilization
Post by rbarreira on Jul 6^th, 2011, 4:57am

My bot has a mobility evaluation, but the aim of this is not really to win by immobilization (which is extremely rare), but instead to leave the opponent with fewer options and less access to critical squares.

Title: Re: Win by immobilization
Post by Swynndla on Jul 6^th, 2011, 5:00am

Thanks rbarreira ... is that evaluation the total number of moves the opposition has?

Title: Re: Win by immobilization
Post by rbarreira on Jul 6^th, 2011, 5:09am

on 07/06/11 at 05:00:57, Swynndla wrote:

Thanks rbarreira ... is that evaluation the total number of moves the opposition has?

No, that would be way too slow for an evaluation function. It's more like a weighted sum of the number of reachable squares for each piece, attempting not to traverse undefended traps or squares where the piece would be frozen (this is fairly efficient with bitboard tricks). The weight is of course bigger for stronger pieces.

It's not very well tuned or tested though, as is the case with most of my evaluation function which is frankly not very good. I'm not sure it's a good idea to take evaluation advice from my bot :)

Title: Re: Win by immobilization
Post by Fritzlein on Jul 6^th, 2011, 1:57pm

I don't know about specific bots, but my general impression is that bots like to freeze pieces more than humans do, so there must be some evaluation bonus for immobilized enemy pieces.

Title: Re: Win by immobilization
Post by ginrunner on Jul 6^th, 2011, 2:44pm

on 07/06/11 at 13:57:13, Fritzlein wrote:

I don't know about specific bots, but my general impression is that bots like to freeze pieces more than humans do, so there must be some evaluation bonus for immobilized enemy pieces.

yes but is that explicitly coded in or is it a coincidental side effect of their material evaluators. My guess is freezing pieces leads to more opportunities for them to take those pieces and it is not the computer purposely leaving less moves for the other player. Then again I could be completely wrong :-P

Title: Re: Win by immobilization
Post by dree12 on Jul 6^th, 2011, 4:37pm

In chess, Robert Hyatt (the developer of Crafty) used a random evaluation function for it, and found out that on a decent computer it had IM levels of success. The random evaluation is like a mobility score, as moves that increase your mobility and decrease your opponent's recieve better results (the entire concept behind minimax). Since Arimaa bots are far behind chess bots in terms of search, I don't think this mechanism can easily be copied over. What would be interesting is an ArimaaScoreP2-esque bot, except with a random* evaluation rather than score. My guess is that the result will be worse than ArimaaScoreP2 but better than ArimaaScoreP1 (it won't give up rabbits all that easily).
*With goals scoring +Inf, of course.

My bot-development has so far provided no results, but this should be a simple-enough change to ArimaaScoreP2. Does anyone still have the source to that?

Title: Re: Win by immobilization
Post by Fritzlein on Jul 6^th, 2011, 5:45pm

on 07/06/11 at 16:37:09, dree12 wrote:

My bot-development has so far provided no results, but this should be a simple-enough change to ArimaaScoreP2. Does anyone still have the source to that?

Iirc, ArimaaScoreP2 is Don Dailey's sample bot (available here (http://arimaa.com/arimaa/download/)) with a drop-in change to eval. Replacing the Arimaa-score eval with a random eval should be relatively straightforward. I predict, however, that mobility is not as useful to good Arimaa as it is to good chess, for reasons discussed in other threads.

Title: Re: Win by immobilization
Post by dree12 on Jul 6^th, 2011, 7:34pm

Thanks. I'll see what I can do, and hopefully this computer is fast enough to spill some tests. Do you know where I can obtain a copy of bot_random?

Title: Re: Win by immobilization
Post by Janzert on Jul 6^th, 2011, 9:49pm

Although the data is fairly old now, I did look at this a little in the branching factor study (http://arimaa.janzert.com/bf_study/). Here is the most relevant graph:

http://arimaa.janzert.com/bf_study/bysidegoal.png

But while OpFor (as I imagine all the other bots do) has terms in its evaluation for frozen, blockaded and mobility of pieces, etc., it does not directly look at just the total number of moves available to a side. (Except for the case of actual immobilization)

Janzert

Title: Re: Win by immobilization
Post by Nazgand on Jul 6^th, 2011, 11:00pm

Nice graph. Exactly the sort of thing I meant. rbarreira's method sounds like a good heuristic if optimized. In related news, I recently learned that research shows that telling others your goals makes you less likely to achieve them.

Title: Re: Win by immobilization
Post by RonWeasley on Jul 12^th, 2011, 7:15pm

on 07/06/11 at 23:00:35, Nazgand wrote:

In related news, I recently learned that research shows that telling others your goals makes you less likely to achieve them.

I must be doing it wrong then. My goal is to tell others my goals more.

Title: Re: Win by immobilization
Post by Nazgand on Jul 12^th, 2011, 10:37pm

on 07/12/11 at 19:15:17, RonWeasley wrote:

I must be doing it wrong then. My goal is to tell others my goals more.

Yes. It makes a good joke if you add "So my new goal is to not tell anyone any of my goals."

Edit: http://www.ted.com/talks/derek_sivers_keep_your_goals_to_yourself.html