Author |
Topic: Are any bots working with just a subset of pieces? (Read 1505 times) |
|
speek
Forum Guru
Arimaa player #5441
Gender: 
Posts: 75
|
 |
Are any bots working with just a subset of pieces?
« on: Aug 23rd, 2010, 10:18am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Are any bots working with just a subset of pie
« Reply #1 on: Aug 23rd, 2010, 11:43am » |
Quote Modify
|
I think at least bomb does something similar, when confirming a goal threat. It searches only for pieces near enough to stop the goal.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Are any bots working with just a subset of pie
« Reply #2 on: Aug 23rd, 2010, 11:49am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
tize
Forum Guru
Arimaa player #3121
Gender:
Posts: 118
|
|
Re: Are any bots working with just a subset of pie
« Reply #3 on: Aug 23rd, 2010, 12:12pm » |
Quote Modify
|
on Aug 23rd, 2010, 10:18am, 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.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Are any bots working with just a subset of pie
« Reply #4 on: Aug 23rd, 2010, 12:21pm » |
Quote Modify
|
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];
}
}
|
|
|
|
IP Logged |
|
|
|
speek
Forum Guru
Arimaa player #5441
Gender:
Posts: 75
|
|
Re: Are any bots working with just a subset of pie
« Reply #5 on: Aug 23rd, 2010, 12:43pm » |
Quote Modify
|
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 
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Are any bots working with just a subset of pie
« Reply #6 on: Aug 23rd, 2010, 12:52pm » |
Quote Modify
|
BTW, I'm not sure that you would get very meaningful results from such a search if it went very deep.
|
|
IP Logged |
|
|
|
speek
Forum Guru
Arimaa player #5441
Gender:
Posts: 75
|
|
Re: Are any bots working with just a subset of pie
« Reply #7 on: Aug 23rd, 2010, 12:55pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Are any bots working with just a subset of pie
« Reply #8 on: Aug 23rd, 2010, 7:17pm » |
Quote Modify
|
on Aug 23rd, 2010, 12:55pm, 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.
|
|
IP Logged |
|
|
|
speek
Forum Guru
Arimaa player #5441
Gender:
Posts: 75
|
|
Re: Are any bots working with just a subset of pie
« Reply #9 on: Aug 23rd, 2010, 8:06pm » |
Quote Modify
|
on Aug 23rd, 2010, 7:17pm, 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!
|
|
IP Logged |
|
|
|
Manuel
Forum Guru
Arimaa player #4020
Gender:
Posts: 58
|
|
Re: Are any bots working with just a subset of pie
« Reply #10 on: Aug 25th, 2010, 7:11am » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print