Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Safe pruning
        
(Message started by: lightvector on Feb 12^th, 2008, 4:12pm)

Title: Safe pruning
Post by lightvector on Feb 12^th, 2008, 4:12pm

I have been thinking about various ideas for forward pruning, and I was wondering what lines, based on static criteria, could provably be cut from a search.

One of the situations I considered was deliberately stepping one's piece into a trap that currently has no friendly defenders. Can anyone construct a position where this is the best move? I haven't been able to (barring the exceptional cases where it is the only legal move), but there might be a few out there.

Does anyone know of any other possibilities for safe forward pruning? I doubt very much could be safely pruned in total by static criteria, but every little bit helps, before I begin to play with less sound methods.

Title: Re: Safe pruning
Post by 99of9 on Feb 12^th, 2008, 4:52pm

It will be good to think through this topic.

One counterexample for you is when a piece suicides to let a rabbit through the square it was on. This is rare because it requires that the piece cannot just move out of the way in the other free direction. If that other direction is blocked by a strong enemy piece, then the rabbit would get frozen on its way though, so the other direction must be blocked by a friendly piece or an enemy rabbit:

for example gold to move
.rrrrr.r ........ ..xe.xEM rm....R. ........ ..x..x.. ..c..... .....R..

Title: Re: Safe pruning
Post by lightvector on Feb 12^th, 2008, 5:55pm

Great example!

I completely forgot that I had considered cases like this when writing my 4-step goal tree (which I have just finished coding. Yay!). Fortunately, after I finish debugging the goal tree, it will catch such cases directly.

Unfortunately, I suppose if a sacrifice like this can be required for an immediate goal, then it would be conceivable to build a position where a forced goal in three moves would also require such a sacrifice as the first move. Yuck.

Title: Re: Safe pruning
Post by arimaa_master on Feb 13^th, 2008, 3:03am

Another example could be position which requires to sacrifice a piece to gain a stronger one. (This means, that friendly piece is on the way of achieving this and only free direction where to sidestep is trap.)

Title: Re: Safe pruning
Post by ddyer on Apr 6^th, 2008, 3:16pm

Based on my years Go programming, I don't think you're
likely to find any significant classes of moves that can be
removed safely. If you do find some, they're not going to
make up a significant enough portion of all moves to justify
the effort to identify them.

On the other hand, throwing away vast classes of moves
without considering them because they're probably useless
is a fine strategy to reduce the size of the space. You just
have to accept that it will be possible to construct situations
where your program will not find the optimal solution.

Examples of this are found in the Zertz and Punct robots
at Boardspace.net. The zertz robot never considers two
unforced moves in a row. The punct robot considers only
a statistical sample of pieces "dropped" onto the board
not in contact with any other pieces, and doesn't consider
board-to-board moves that are not in contact with other
pieces at all.

Title: Re: Safe pruning
Post by IdahoEv on Apr 7^th, 2008, 12:42pm

on 04/06/08 at 15:16:34, ddyer wrote:

And you can always just use measures of moves you think are probably bad in your move ordering function ... put them last. Then you're very likely to get a cutoff because you've looked at better moves first, without actually preventing the bot from searching them in the rare cases where they're worthwhile. So you're not actually pruning them, but 90%+ of the time you will get the same effect, or close enough.

Title: Re: Safe pruning
Post by Fritzlein on Apr 7^th, 2008, 2:23pm

on 04/06/08 at 15:16:34, ddyer wrote:

On the other hand, throwing away vast classes of moves without considering them because they're probably useless is a fine strategy to reduce the size of the space.

Are you saying that unsafe pruning has been effectively applied in Go searchers (i.e. it has raised their playing strength)? Or just Zertz and Punct?

Title: Re: Safe pruning
Post by Janzert on Apr 7^th, 2008, 2:34pm

My, admittedly very limited, understanding is that pretty much all of the "traditional"¹ go programs use large amounts of pruning. If I recall correctly Fotland said that mfgo only considers around a half dozen moves at the root. I guess whether you say these are effective or not is a matter of your viewpoint.

Janzert

¹ The heavy pattern matching programs such as many faces, gnugo, etc. as opposed to the more recent UCT/MC based programs.

Title: Re: Safe pruning
Post by ddyer on Apr 8^th, 2008, 7:35pm

on 04/07/08 at 14:34:39, Janzert wrote:

My, admittedly very limited, understanding is that pretty much all of the "traditional"¹ go programs use large amounts of pruning.

That is also my understanding.

Title: Re: Safe pruning
Post by fotland on Apr 9^th, 2008, 1:25am

This is correct. Many Faces only looks at 20 to 40 moves at the root, and 5 to 10 during the main search, and 1 to 5 during quiescence search. Other traditional programs are similar.

On 19x19, the strong uct/mc programs also do considerable pruning in the main search, so they search deep and narrow. They will visit all legal moves if given enough time, but in practice they only look at a few moves in most positions.

David

on 04/07/08 at 14:34:39, Janzert wrote: