Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 4:36am

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum « Capturing Moves »


   Arimaa Forum
   Arimaa
   Bot Development
(Moderator: supersamu)
   Capturing Moves
« Previous topic | Next topic »
Pages: 1 2 3  4 Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Capturing Moves  (Read 12041 times)
jdb
Forum Guru
*****



Arimaa player #214

   


Gender: male
Posts: 682
Capturing Moves
« on: Aug 6th, 2005, 1:17pm »
Quote Quote Modify 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)

  toby_hudson  


Gender: male
Posts: 1413
Re: Capturing Moves
« Reply #1 on: Aug 7th, 2005, 7:24pm »
Quote Quote Modify 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 Smiley.
 
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: male
Posts: 682
Re: Capturing Moves
« Reply #2 on: Aug 8th, 2005, 8:25am »
Quote Quote Modify 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)

  toby_hudson  


Gender: male
Posts: 1413
Re: Capturing Moves
« Reply #3 on: Aug 8th, 2005, 6:25pm »
Quote Quote Modify 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: male
Posts: 45
Re: Capturing Moves
« Reply #4 on: Aug 12th, 2005, 11:56am »
Quote Quote Modify 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: male
Posts: 682
Re: Capturing Moves
« Reply #5 on: Aug 12th, 2005, 2:29pm »
Quote Quote Modify 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: male
Posts: 45
Re: Capturing Moves
« Reply #6 on: Aug 13th, 2005, 11:10pm »
Quote Quote Modify Modify

Sorry for my clumsy english. Is there any chance you speak Chinese, Jeff?  Roll Eyes  Here is something from my paper:
 
 
For every position at level 4n+m (0&#8804;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&#8804;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&#8804;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: male
Posts: 45
Re: Capturing Moves
« Reply #7 on: Aug 13th, 2005, 11:15pm »
Quote Quote Modify 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: male
Posts: 45
Re: Capturing Moves
« Reply #8 on: Aug 13th, 2005, 11:20pm »
Quote Quote Modify 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
&#8804;1 1 1
&#8804;2 3 4
&#8804;3 10 29
&#8804;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 &#8804;4 With &#8804;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: male
Posts: 45
Re: Capturing Moves
« Reply #9 on: Aug 13th, 2005, 11:23pm »
Quote Quote Modify 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

   
WWW

Gender: male
Posts: 437
Re: Capturing Moves
« Reply #10 on: Aug 14th, 2005, 12:08am »
Quote Quote Modify Modify

nice Smiley  
how much time does this safe you ?
IP Logged
haizhi
Forum Senior Member
****



Arimaa player #350

   


Gender: male
Posts: 45
Re: Capturing Moves
« Reply #11 on: Aug 14th, 2005, 2:19am »
Quote Quote Modify 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: male
Posts: 682
Re: Capturing Moves
« Reply #12 on: Aug 14th, 2005, 8:48am »
Quote Quote Modify 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

   
WWW

Gender: male
Posts: 437
Re: Capturing Moves
« Reply #13 on: Aug 14th, 2005, 10:36am »
Quote Quote Modify Modify

on Aug 14th, 2005, 2:19am, haizhi wrote:

 
I beg your pardon?  

 
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: male
Posts: 45
Re: Capturing Moves
« Reply #14 on: Aug 14th, 2005, 4:06pm »
Quote Quote Modify 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
Pages: 1 2 3  4 Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB © 2000-2003. All Rights Reserved.