Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Psuedo-random sparse search
        
(Message started by: rednaxela on Aug 23^rd, 2010, 8:58pm)

Title: Psuedo-random sparse search
Post by rednaxela on Aug 23^rd, 2010, 8:58pm

Well, while working on a new bot, I started wondering that if one wanted to try forward pruning, what would be best to prune. I'm wondering if anyone has any comments on the following strategy for such:

First, evaluate 'obvious' and 'interesting' moves of course. Use techniques such as a capture decision tree I've seen mentioned in order to do so. Be careful with this as to avoid pitfalls.
Then, start evaluating remaining moves in a pseudo-random manner, with bias towards evaluating moves that are similar to moves already evaluated to be strong. (A simple way of choosing 'similar' is with proximity in the step tree)
Repeat until all moves evaluated or there is a time crunch.

Maybe I'm wrong, but I'm thinking this approach could be a good way of to search deeper by evaluating fewer moves and branching less. The idea is that the weighted-but-random search priority would also mean it would 1) tend to do more useful searches first, 2) still explore the search space a reasonable amount, and 3) mitigate disadvantages of a less complete search by not predictably ignoring the same things.

Any thoughts?

(Also, all that said, I'm probably not trying this approach in my current bot-in-progress (at least for now). After all, my current planned approach is more about making the most of low depth. Just wondering if anyone has thoughts on this idea.)

Title: Re: Psuedo-random sparse search
Post by Fritzlein on Aug 24^th, 2010, 1:21am

My intuition is that the Arimaa Challenge is less likely to fall to improving the evaluation of full-width alpha-beta searchers, and more likely to fall to some aggressive pruning scheme we haven't thought of yet. However, I have no idea what such pruning would look like, and everything that has been tried so far has worked poorly. So maybe evaluation and not search is the key after all.

Title: Re: Psuedo-random sparse search
Post by Hippo on Aug 24^th, 2010, 5:32am

I would still consider MCTS like methods but with modified exploration ... I would like a heuristic able to generate move candidates in as good order as possible and explore just limited number of them at a time. After the branch becomes visited treshold number of times another portion of moves would be added. This would limit width of MCTS tree in less perspective branches and I hope speeded the perspective branches.

Of course bad candidate order heuristic would made the method poor. And especially goaling, goal preventing, capturing, capture preventing moves should be included in the explored part as fast as possible. But as there is (in Kozelek's work) shellow alpha-beta evaluator, at least best looking candidate moves could be find quickly in transposition tables.

Title: Re: Psuedo-random sparse search
Post by rednaxela on Aug 24^th, 2010, 6:40am

Yeah, issues with bad heuristics for candidate order would be problematic... which is part of why I was thinking "the result of evaluation of similar moves" would perhaps be a powerful heuristic to involve, as far as impact per amount of cpu use. Of course that would certainly be a lower priority heuristic than goaling/goal-prevention/capture related ones yeah.

Title: Re: Psuedo-random sparse search
Post by speek on Aug 24^th, 2010, 1:20pm

I currently just use my evaluation function to determine good search candidates. It does not work all that well, though it's a very simple eval function - a better one might work better.

But, it does seem like candidate recognition has to be different from position evaluation.

I am trying to visualize my bot as a bunch of spiders that roam the search tree independently looking for good things and avoiding bad things. Some sort of randomization in their roaming is probably good. I'm also thinking that multiple different candidate recognizers might also be helpful.

The similar move thing sounds interesting, but also sounds difficult to really make it work well. A lot of moves that will look similar will often prove to have very different effects on the game.

Title: Re: Psuedo-random sparse search
Post by rbarreira on Aug 25^th, 2010, 5:37am

on 08/24/10 at 01:21:15, Fritzlein wrote:

However, I have no idea what such pruning would look like, and everything that has been tried so far has worked poorly.

I thought Haizhi's pruning scheme had been adopted by a few bots. How much it helps I'm not sure.