Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Are any bots working with just a subset of pieces?
        
(Message started by: speek on Aug 23^rd, 2010, 10:18am)

Title: Are any bots working with just a subset of pieces?
Post by speek on Aug 23^rd, 2010, 10:18am

I was thinking about my bot and realized that I could basically "turn off" pieces when building a search tree, and thus reduce the number of moves considered. So, as an extreme example, to test if a certain rabbit might be able to score in the next few moves with the help of the nearby elephant, I could turn off all my other pieces, and all opponent pieces that weren't in the vicinity and blast through a fairly deep tree to find a solution. Kind of like playing out just one small corner in a Go game, I guess, but rather than being necessarily geographic, I can filter by piece or by location.

Do any current bots do this or something similar? I am unsure if it's really worthwhile, as you have to be able to detect times when it might be useful to do this.

Title: Re: Are any bots working with just a subset of pie
Post by rbarreira on Aug 23^rd, 2010, 11:43am

I think at least bomb does something similar, when confirming a goal threat. It searches only for pieces near enough to stop the goal.

Title: Re: Are any bots working with just a subset of pie
Post by Fritzlein on Aug 23^rd, 2010, 11:49am

I'm pretty sure that when Loc detects a goal threat, only pieces near enough to affect the situation are allowed to move. Also Bomb orders its moves to examine moves near a threatening rabbit before it examines moves further away, thus providing better pruning. I don't know about any other bots, though.

Title: Re: Are any bots working with just a subset of pie
Post by tize on Aug 23^rd, 2010, 12:12pm

on 08/23/10 at 10:18:17, speek wrote:

I am unsure if it's really worthwhile, as you have to be able to detect times when it might be useful to do this.

I think it really can be worth it, but as with all forward pruning it potentially opens for tactical holes in the search.

In a quick test I got marwin to finish a 10 steps search 83% faster when pieces standing on A1,B1, G1, H1, A8, B8, G8 & H8 wasn't allowed to move. The position was an opening position. So yes it can be worth it if as you say it can be detected when to use it.

ps. Marwin isn't using this kind of pruning.

Title: Re: Are any bots working with just a subset of pie
Post by jdb on Aug 23^rd, 2010, 12:21pm

Haizhi came up with a form of pruning. He observed that most moves involved at least 2 connected steps. So on the second step of a turn, almost all moves can be pruned. If there are goal threats or capture threats, one needs to be careful.

Here is the code snippet from clueless.

Code:

// Determine second step relationship pruning
// Loss by immobilization is still handled correctly

// 1) Piece moved on first step
// 2) A piece touching the destination of the previous moved piece
// 3) The elephant
long from_bb = FULL_BB;
if (use_haizi_relationship_pruning) {
if (gs.isSecondStep() && !is_goal_threat) {
long prev_step = abms[ply - 1].getCurrentMove();
long to_bb = GameState.getToBB((int) prev_step);
from_bb = to_bb | touching_bb(to_bb) | gs.piece_bb[10] | gs.piece_bb[11];
}
}

Title: Re: Are any bots working with just a subset of pie
Post by speek on Aug 23^rd, 2010, 12:43pm

When I think about a move, rather than looking at all possible moves (duh), I tend to see points in the position where it'd be nice to have my elephant, or a rabbit. Or, I see that if opponent's piece X could be just moved out of the way, I could do lots of stuff.

So, if a program looked at a position and decided that pieces X,Y, and Z had interesting possibilities, then just focus on them. It's not exactly the same, but it feels similar.

And then, it also feels like I rely on my subconscious to alert me to dangerous stuff that needs attention, beyond the above. Perhaps, in the program, there is still a wider search going on to detect tactical holes in the above. The problem I have is merging the two different approaches, because both will generate the same moves, but I'd rather not duplicate the effort when they do. But, merging also devours resources...

In case it's not clear, I'm not doing a strict alpha-beta search. I do generate a move tree, but my code looks for paths through the tree to examine deeper and basically just applies killer moves to the rest to even out the evaluations as I go deeper in the tree. I'm looking for some good ways to find the best paths to search :-)

Title: Re: Are any bots working with just a subset of pie
Post by rbarreira on Aug 23^rd, 2010, 12:52pm

BTW, I'm not sure that you would get very meaningful results from such a search if it went very deep.

Title: Re: Are any bots working with just a subset of pie
Post by speek on Aug 23^rd, 2010, 12:55pm

That's true, but my idea is to use it as a way to detect moves of interest that deserve further study. "Deep" in this case means maybe 6-ply.

Title: Re: Are any bots working with just a subset of pie
Post by jdb on Aug 23^rd, 2010, 7:17pm

on 08/23/10 at 12:55:40, speek wrote:

That's true, but my idea is to use it as a way to detect moves of interest that deserve further study. "Deep" in this case means maybe 6-ply.

Usually, interesting steps involve traps. So maybe steps that effect traps and squares touching traps should be looked at first.

Title: Re: Are any bots working with just a subset of pie
Post by speek on Aug 23^rd, 2010, 8:06pm

on 08/23/10 at 19:17:58, jdb wrote:

Usually, interesting steps involve traps. So maybe steps that effect traps and squares touching traps should be looked at first.

Wow, so obvious, yet that didn't occur to me in just that way. Thanks, I think I can use that to good effect!

Title: Re: Are any bots working with just a subset of pie
Post by Manuel on Aug 25^th, 2010, 7:11am

I think this is a very good idea! Especially when taken a little bit to the extreme, I think it could be very effective in quickly finding some potential threads, and as you combine it with a real search afterwards, it does not matter if you have a few tactical holes.
To make the quick search even faster, you could also apply the haizhi scheme during the quick search...

Myself I am working on a similar (but much more complicated, so I will probably never finish...) idea, so I would find it rather interesting to see how your ideas work out!

I think you should just experiment with different amounts of pieces turned off and compare to a full search, such that you can see how effective different schemes are, and how much things you are missing compared to the full search.

Good luck!