Author |
Topic: Capturing Moves (Read 12345 times) |
|
jdb
Forum Guru
Arimaa player #214
Gender: 
Posts: 682
|
 |
Capturing Moves
« on: Aug 6th, 2005, 1:17pm » |
 Quote  Modify
|
I am working on generating all possible capture moves from a given position. I am looking for static tests that can rule out the possibilitiy of a capture on a given trap. Here are the three I use now:
1) Enemy elephant touching trap
2) Three or more enemy pieces touching trap
3) 1 non dominated enemy piece AND any other enemy piece touching trap. A dominated piece is a piece that is touching a stronger enemy piece.
In a normal position these tests eliminate around 30-40% of the traps.
Any ideas for some more simple tests?
|
|
 IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Capturing Moves
« Reply #1 on: Aug 7th, 2005, 7:24pm » |
Quote Modify
|
4) Two enemy pieces touching the trap that are both dominated by the same friendly piece AND neither are dominated by any others.
5) One enemy piece touching the trap that has no dominating friendly pieces within 3 steps of it.
6) No friendly pieces within 1 step of the trap AND no dominated friendly pieces 2 steps from the trap.
7) No friendly pieces within 2 steps of the trap  .
Do you want more like these, or are these too strange?
|
| « Last Edit: Aug 7th, 2005, 7:25pm by 99of9 » |
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Capturing Moves
« Reply #2 on: Aug 8th, 2005, 8:25am » |
Quote Modify
|
These are exactly what I was looking for. The actual generation of the capture moves is hundreds of times more expensive than these simple tests. So they don't have to be true very often to be effective.
4 and 5 are great, but I dont quite follow number 6 and 7. Could you please explain these a little more?
I don't see how they handle this case:
1w Ec5
2b rf5
8 ) No enemy piece within two steps of the trap.
|
| « Last Edit: Aug 8th, 2005, 8:25am by jdb » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Capturing Moves
« Reply #3 on: Aug 8th, 2005, 6:25pm » |
Quote Modify
|
Arrgghh, sorry, I mixed up friendly and enemy teams in 6 and 7. So my rule 7 should read the same as your rule 8.
9) No friendly piece within 4 steps of the trap. (So even if they're hanging a rabbit, we can't get to it.)
[EDIT actually this turns out to be a less-discerning version of #5]
[EDIT rule 7 also turns out to be a less-discerning version of #6]
|
| « Last Edit: Aug 8th, 2005, 6:30pm by 99of9 » |
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Capturing Moves
« Reply #4 on: Aug 12th, 2005, 11:56am » |
Quote Modify
|
Why don't you just build a trap-local search decision tree?
It's simpler than I though. I make one that solve all up tp 3-step cases( about 30-40 totally), it only takes about 200 lines of code, and make a 5-ply search almost as good as an 8-ply search. The number of 4-step cases is less than 60, so it is also doable.
Goal-local search has much more cases and is harder to build.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Capturing Moves
« Reply #5 on: Aug 12th, 2005, 2:29pm » |
Quote Modify
|
Haizhi,
What is a "trap-local search decision tree"?
What is "goal-local search"?
Thanks
|
| « Last Edit: Aug 13th, 2005, 8:22am by jdb » |
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Capturing Moves
« Reply #6 on: Aug 13th, 2005, 11:10pm » |
Quote Modify
|
Sorry for my clumsy english. Is there any chance you speak Chinese, Jeff?  Here is something from my paper:
For every position at level 4n+m (0≤m<4), we calculate the possibility that any enemy piece can be trapped in the next 4-m steps, and subtract the material value of the most valuable piece that can be trapped from the evaluation score. Therefore, search step 4n+m (0≤m<4) will give us a roughly a 4n+4 step result.
A piece at c4, c5, f4, f5, d3, e3, d6 or f6 can be captured into two different traps. For these squares, the threats from both sides need to be calculated.
During the process of trapping an enemy’s piece, sacrificing a friendly piece may be unavoidable. In this case, the evaluation depends on the comparison of the values of the lost piece and the gained piece.
For every position at level 4n+m (0≤m<4), we check the possibility that any Rabbit of the player to move can achieve the goal in the next 4-m steps, and if so score the situation as infinite (win) or minus infinite (lost). It can discover an unavoidable win or loss situation up to 4 steps earlier, saving further search and greatly improving the performance of the endgame play.
The difficulty in finding out the situation of trapping or reaching the goal in 4 steps is obvious. There are many different paths. Pulling, pushing, blocking, freezing and supporting: all these rules make the situation very hard to handle.
The easiest way to solve the problem is to generate all the legal moves of the next turn. This method is simple to implement, but not practical due to the time-consuming cost of move generation. To make the program fast, we have to use decision trees to handle all the trapping and goal situations case by case.
|
|
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Capturing Moves
« Reply #7 on: Aug 13th, 2005, 11:15pm » |
Quote Modify
|
In Fotland's evaluation function, there is also a trap/goal evaluating decision tree (in fact we got this idea from him). But he doesn’t evaluate trap/goal by completing unfinished steps left in the current move as we did. Instead, he statically evaluates how many steps it will take to trap each piece on the board (1 to 6 steps) or have each Rabbit reach the goal (1 to 8 steps), assuming no intervening moves by the opponent.
I think my way is simpler and easy to understand.
|
|
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Capturing Moves
« Reply #8 on: Aug 13th, 2005, 11:20pm » |
Quote Modify
|
So far our decision tree can handle all the cases that take up to 3 steps to trap or goal, but the 4 steps cases are not accomplished yet.
Step Trap case Goal case
≤1 1 1
≤2 3 4
≤3 10 29
≤4 >40 >100
Table 3.2: Number of trap evaluation and goal evaluation cases.
Table 3.3 shows the result of trap and goal evaluation. It can make a 5-step search roughly equivalent to an 8-step search, which is a great improvement. It also helps to give Iterative Deepening a better move ordering. Implementing the cases for all 4 steps will make it better, but considering the difficulty involved, it is not critical.
Search Roughly equivalent search
Without ≤4 With ≤4
5-7 step 8 step 8 step
8 step 11 step 12 step
9-11 step 12 step 12 step
12 step 15 step 16 Step
Table 3.3: Result of trap evaluation and goal evaluation.
Sorry, I cannot make it more readable.
|
|
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Capturing Moves
« Reply #9 on: Aug 13th, 2005, 11:23pm » |
Quote Modify
|
Step Trap case Goal case
----------------------------------------------
>=1 1 1
>=2 3 4
>=3 10 29
>=4 >40 >100
Table 3.2: Number of trap evaluation and goal evaluation cases.
Search Roughly equivalent search
Without <=4 With<=4
------------------------------------------------------------
5-7 step 8 step 8 step
8 step 11 step 12 step
9-11 step 12 step 12 step
12 step 15 step 16 Step
Table 3.3: Result of trap evaluation and goal evaluation.
Better?
|
|
IP Logged |
|
|
|
PMertens
Forum Guru
Arimaa player #692
Gender:
Posts: 437
|
|
Re: Capturing Moves
« Reply #10 on: Aug 14th, 2005, 12:08am » |
Quote Modify
|
nice
how much time does this safe you ?
|
|
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Capturing Moves
« Reply #11 on: Aug 14th, 2005, 2:19am » |
Quote Modify
|
on Aug 14th, 2005, 12:08am, PMertens wrote:| how much time does this safe you ? |
|
I beg your pardon?
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Capturing Moves
« Reply #12 on: Aug 14th, 2005, 8:48am » |
Quote Modify
|
Thanks for your detailed and informative reply.
Quote:| Sorry for my clumsy english. Is there any chance you speak Chinese, Jeff? |
|
Your english is fine. I was just unfamiliar with the terms you used. Sorry, I don't speak Chinese.
If I understand correctly,
A decision tree answers a question with a boolean result.
A local search generates the actual moves satisfying a specific objective.
I think a decision tree is a good way to go for the goal search. The number of cases to consider is formidable. Clueless has about 900 lines of code to detect goals and there are still cases it will miss.
For the capture search, actually generating the moves can be helpful. During the search, clueless generates these moves first. It makes a huge difference in move ordering. A decision tree is most useful at the leaves. Capture move generation can be used anywhere in the search tree.
Your approach of considering each enemy piece individually is interesting. Clueless analyzes each trap square individually.
Quote:Implementing the cases for all 4 steps will make it better, but considering the difficulty involved, it is not critical.
|
|
I disagree with this. Having full four step goal detection is very important. It prunes the search tree very efficiently in endgame situations.
|
|
IP Logged |
|
|
|
PMertens
Forum Guru
Arimaa player #692
Gender:
Posts: 437
|
|
Re: Capturing Moves
« Reply #13 on: Aug 14th, 2005, 10:36am » |
Quote Modify
|
on Aug 14th, 2005, 2:19am, haizhi wrote:
I would be interested how much faster is your solution compared to a full move generation ?
|
|
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Capturing Moves
« Reply #14 on: Aug 14th, 2005, 4:06pm » |
Quote Modify
|
Oh, I shouldn't use the word "local search" and "decision tree" together, it was confusing. In fact it is only a decision tree, almost nothing with "search".
Jeff, I think we were talking diffrent stuff. By finding all the capture moves, You were trying to do some forward pruning, and I am trying to better the evaluation. I didn't test the capture/goal moves in the move generation, so no any pruning there. But in evaluation, I try to adjust their final scores based on what these nodes will go with the unseached steps in the same turn.
If we only consider material and goal in the evaluation, with all 3-step cases implemented, we can make a 5-ply search working as an 8-ply search. A normaly 5-ply search find I can capture a dog and think it is a good move, but with the "capture decition tree" a 5-ply search will find that doing so we will lost a horse in the next turn. Normally we need a 8-ply seach to find that.
Imlementing all the 4-step cases can make a 4-ply search working as an 8-ply search, of course it is better, but I still don't think it's very critical. (I confess that got this conclusion is partially because I am too lazy.)
See, Pmertens, my approach doesn't make a bot any faster, but make it much stronger with same search depth for sure.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print