Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Null Move Pruning and races
        
(Message started by: Ciribot on Mar 19^th, 2009, 6:35am)

Title: Null Move Pruning and races
Post by Ciribot on Mar 19^th, 2009, 6:35am

I'm not sure how many bots implement null moves, but an issue I see with the otherwise quite safe null move pruning is that the reduced search depth will typically push a goal win over the horizon. In these cases the null move will actually be an upper bound of the score for that move, which is very bad. Any thoughts on how to implement null move pruning safely? Typically in chess it is not used in pawn endings due to race conditions.

*typo fixed

Title: Re: Null Move Pruning and races
Post by Fritzlein on Mar 19^th, 2009, 8:40am

on 03/19/09 at 06:35:00, Ciribot wrote:

I'm not sure how many bots implement null moves, but an issue I see with the otherwise quite safe null move pruning is that the reduced search depth will typically push a goal win over the horizon. In these cases the null move will actually be an upper bound of the score for that much, which is very bad. Any thoughts on how to implement null move pruning safely? Typically in chess it is not used in pawn endings due to race conditions.

There are quite a few races of different sorts in Arimaa, so if goal races undermine null-move-pruning, then wouldn't capture races also do so, and racing-to-smother-elephant-holding-camel-hostage before-free-camel-wreaks-havoc, etc?

It's somewhat counter-intuitive that null-move pruning would cause a mis-evaluation of a race, because a race is precisely the sort of situation where giving up a move and still winning is proof positive of a superior position. On the other hand, I guess I can see how searching to different depths in different lines means that one line will race to completion and get a correct eval, while another line will not finish the race and get a skewed eval.

Is it a possible solution to declare that certain extensions must happen even in parts of the tree that are being searched to reduced depth for whatever reason? The logic would be, that whatever reason we had for searching a certain line more shallowly is trumped by hanging pieces and imminent goal threat; the latter always mandate deeper search until the position quiets down.

Title: Re: Null Move Pruning and races
Post by Ciribot on Mar 19^th, 2009, 10:11am

I think race might not be the word I was looking for, more like some goal that will inevitably happen. However it can also cause misevaluations of races because it will prefer the null move to a lost race.

If there is some inevitable danger on the horizon, the null move will always cause the AI to think 'this can be avoided', whether it is a win, or a positional disadvantage. Null move pruning really works in chess because inevitable checkmate is usually made much worse with null-move, as well usually follows many checks (in which null-move is never applied).

In my board game, the game is also won by a 'goal' condition (be first to get a piece to the other side, that is), I managed to save a lot of tactical strength by never using a null move to refute a win. That is, if another move has already said 'this is a loss for us', null move pruning isn't used. This isn't perfect, and causes an unstable search to some extent, but greatly improves evaluation of positions where a piece is near the other side.

Title: Re: Null Move Pruning and races
Post by fotland on Mar 31^st, 2009, 8:24am

Bomb uses null move.