Welcome, Guest. Please Login or Register.
Aug 23rd, 2019, 2:59pm

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 8690 times)
Janzert
Forum Guru
*****



Arimaa player #247

   


Gender: male
Posts: 1014
Re: Capturing Moves
« Reply #15 on: Aug 14th, 2005, 9:11pm »
Quote Quote Modify Modify

Just for comparison purposes though. What is the average time to do a 5 step+decision tree search compared to the same position with a full 8 step search and no decision tree?
 
I think this is what PMertens is getting at, and I'd also be interested in hearing the answer.
 
Janzert
IP Logged
haizhi
Forum Senior Member
****



Arimaa player #350

   


Gender: male
Posts: 45
Re: Capturing Moves
« Reply #16 on: Aug 14th, 2005, 10:32pm »
Quote Quote Modify Modify

Oh, the decision tree in the evaluation function doesn't make the program visibly slow. A 5-ply search with it is almost as fast as a normal 5-ply search, cost less than 1 sec per move.  
 
Normally my bot take about 5-10 sec to finish a 8-ply search.
 
IP Logged
PMertens
Forum Guru
*****



Arimaa player #692

   
WWW

Gender: male
Posts: 437
Re: Capturing Moves
« Reply #17 on: Aug 14th, 2005, 11:07pm »
Quote Quote Modify Modify

That is what I wanted Wink nice ...
 
So until now its only 3 step because you are lazy ?
Do you think it might make sense to make even more than 4 steps ?
If you dont want to type the code yourself, how about letting the computer generate it (once, in advance) ?
« Last Edit: Aug 14th, 2005, 11:10pm by PMertens » IP Logged
haizhi
Forum Senior Member
****



Arimaa player #350

   


Gender: male
Posts: 45
Re: Capturing Moves
« Reply #18 on: Aug 15th, 2005, 1:00pm »
Quote Quote Modify Modify

search  <=3      <=4  
4  4  8  
5  8  8
6  8  8
7  8  8
8  8  12  
9  12  12
10  12  12  
11  12  12
12  12  16
 
 
Well, before blaming my laziness, let me explain more. See the table above. The difference that the  4 step captrue/goal cases will bring is only when we search 4n step deep. In a 3 minutes time limit, I can not finish a 12-step search, so no matter the depth  of our finished search is 9 or 11, what I get is still a roughly 12-step result. That is why I am not so eager to implement 4 step cases into my bot.
 
There is another reason makes the 12-step an ugly bottleneck: transportation tables doesn't work if the search is less than 3 moves (12 step).
 
Automatic generate a decision tree? Theoritcally it is doable, but is it worth it?
 
I don't think it is a good idea to make it deeper than a complete turn(4 steps). However, Fortland's decision tree is as deep as 6-step or 8-step. I cannot imagine how can he accomplished that.
IP Logged
PMertens
Forum Guru
*****



Arimaa player #692

   
WWW

Gender: male
Posts: 437
Re: Capturing Moves
« Reply #19 on: Aug 15th, 2005, 1:04pm »
Quote Quote Modify Modify

sorry about the lazyness comment - just quoted you there Wink
 
8-step ? that is very interesting.
I will have to experiment with this. Thanks for sharing this information.
 
Why don't you think it is a good idea to make it deeper ?
IP Logged
jdb
Forum Guru
*****



Arimaa player #214

   


Gender: male
Posts: 682
Re: Capturing Moves
« Reply #20 on: Aug 15th, 2005, 1:41pm »
Quote Quote Modify Modify

Quote:
There is another reason makes the 12-step an ugly bottleneck: transportation tables doesn't work if the search is less than 3 moves (12 step).  

 
Maybe we're talking about different things here, but transposition tables will still help if the search is less than 12 steps.  
 
1w Ra1 Rb1 Rc1
1b  ea7
 
One search could be:
2w Ra2 Rc2
 
Another could be:
2w Rc2 Ra2
 
The second one will be a hit in the transposition table.
 
 
Quote:
The difference that the  4 step captrue/goal cases will bring is only when we search 4n step deep.

 
True, it is most useful at a 4n step deep search, but it still can be used at the other levels. In the search, finish out the turn with pass steps. Then run the 4step goal search. If the opponent can goal, then the static eval on the position (before the pass steps) is highly questionable and the position needs to be looked at in more detail.
 
 
Quote:
I don't think it is a good idea to make it deeper than a complete turn(4 steps).

 
I agree. After 4 steps, the opponent has four steps to mess up your plans anyway. What would be the benefit of a five step goal search?  
 
I highly doubt Fotland's goal search detects 8 step wins. I would guess it detects situations that will require *at least* 8 steps to win. This is alot easier to do.
IP Logged
haizhi
Forum Senior Member
****



Arimaa player #350

   


Gender: male
Posts: 45
Re: Capturing Moves
« Reply #21 on: Aug 15th, 2005, 2:27pm »
Quote Quote Modify Modify

Jeff, my bot only generates all the distinct moves, all other moves are pruned before search.  
 
I agree with you, 4-step cases can help even it is not a 4n step search.  I will implement it before the end of this year.
 
I carefully read Fortland's paper word by word, but was still not very clear what he did in his captrue/goal decition tree.
 
PMertens, nothing  you said needs a "sorry".    Shocked
« Last Edit: Aug 16th, 2005, 11:48am by haizhi » IP Logged
aaaa
Forum Guru
*****



Arimaa player #958

   


Posts: 758
Re: Capturing Moves
« Reply #22 on: May 6th, 2009, 1:56pm »
Quote Quote Modify Modify

on Aug 14th, 2005, 11:07pm, PMertens wrote:
If you dont want to type the code yourself, how about letting the computer generate it (once, in advance) ?

on Aug 15th, 2005, 1:00pm, haizhi wrote:
Automatic generate a decision tree? Theoritcally it is doable, but is it worth it?

I've just succeeded in doing exactly this with respect to goal patterns.
IP Logged
BlackKnight
Forum Guru
*****



Arimaa player #695

   


Gender: male
Posts: 98
Re: Capturing Moves
« Reply #23 on: May 8th, 2009, 11:26am »
Quote Quote Modify Modify

on May 6th, 2009, 1:56pm, aaaa wrote:
I've just succeeded in doing exactly this with respect to goal patterns.
That sounds very interesting. Do you mind to share some details? Referring to Haizhi, is it worth it, and could you extend it to goal in 2 or so?
IP Logged
aaaa
Forum Guru
*****



Arimaa player #958

   


Posts: 758
Re: Capturing Moves
« Reply #24 on: May 8th, 2009, 12:58pm »
Quote Quote Modify Modify

on May 8th, 2009, 11:26am, BlackKnight wrote:
That sounds very interesting. Do you mind to share some details?

I used retrograde analysis to incrementally determine all possible combinations of features necessary for goaling and then constructed a covering decision tree.
 
Quote:
Referring to Haizhi, is it worth it,

I would think so, given that my bot now needs practically no time to prevent any preventable goals-in-two by the opponent and it can even find some winning goals-in-three under tournament time controls (e.g. RonWeasley's famous elephant sac).
 
Quote:
and could you extend it to goal in 2 or so?

Most definitely not. I'm already severely pushing it, with the generated code running in the tens of thousands of lines! To get above-mentioned behavior, I just let the search extend on goal threats (once), for a relatively cheap combined increase in search depth of 8 steps for the purpose of finding goals.
 
Suffice it to say that swindling Quad should be a whole lot of harder now.
IP Logged
jdb
Forum Guru
*****



Arimaa player #214

   


Gender: male
Posts: 682
Re: Capturing Moves
« Reply #25 on: May 8th, 2009, 1:04pm »
Quote Quote Modify Modify

on May 8th, 2009, 12:58pm, aaaa wrote:

 To get above-mentioned behavior, I just let the search extend on goal threats (once), for a relatively cheap combined increase in search depth of 8 steps for the purpose of finding goals.
 
Suffice it to say that swindling Quad should be a whole lot of harder now.

 
This is similar to what clueless does. I think it is pretty much an essential component for a bot.
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: Capturing Moves
« Reply #26 on: May 27th, 2009, 6:30pm »
Quote Quote Modify Modify

Congratulations, aaaa.  I'm not a programmer, but achieving perfect static goal detection with an automatically generated decision tree sounds like quite a feat to me.
 
Thanks for using that new feature to verify all the missed goal-in-three opportunities from my Challenge game against Clueless.
 
Out of curiosity, what does your bot now think of the position before move 37g in game 47333?  Can it avoid the forced loss that Bomb fell into, and if so how long does it take to settle on the correct move?
IP Logged

aaaa
Forum Guru
*****



Arimaa player #958

   


Posts: 758
Re: Capturing Moves
« Reply #27 on: May 27th, 2009, 10:48pm »
Quote Quote Modify Modify

For now I can tell that chessandgo's 36s rh3s rh6s rh5s is not goal in three. 37g Ef5e Eg5e rh4s Eh5s for one prevents it long enough.
IP Logged
aaaa
Forum Guru
*****



Arimaa player #958

   


Posts: 758
Re: Capturing Moves
« Reply #28 on: May 28th, 2009, 12:20pm »
Quote Quote Modify Modify

It takes my bot almost 14 minutes to discover that 37g He3w rf3w Hf4s Ef5s loses, but well over two hours to find 37g Ef5e Eg5e Eh5s Eh4s as an alternative. It wasn't able to determine that that's the only non-losing move before I aborted the process. I'm very close to accomplishing the same thing with regard to captures and I need the CPU cycles.
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: Capturing Moves
« Reply #29 on: May 28th, 2009, 2:43pm »
Quote Quote Modify Modify

OK, so we're not quite up to avoiding goal in three in a live game, but getting within hailing distance.  Even playing the non-losing move after two hours is impressive, because I don't think any other bot finds the non-losing move at all!  Thanks for checking this out.
 
I don't want to pull you away from perfecting your static capture detection, but a possibly interesting exercise could be run on my Challenge game with Clueless.  You say you verified that I missed eight goal-in-three opportunities, and there were no more.  Your bot is clearly going to avoid any goal-in-two losses, but how many of those eight goal-in-three situations would it have avoided, given two minutes to think in each situation?  (I'm assuming that Clueless could have avoided each goal-in-three if it had been smarter, but I could be wrong about that, in which case I must have at some point played the starting move of a forced goal-in-four without realizing it.)
« Last Edit: May 28th, 2009, 2:48pm by Fritzlein » 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.