Author |
Topic: Capturing Moves (Read 12060 times) |
|
Janzert
Forum Guru
Arimaa player #247
Gender: 
Posts: 1016
|
 |
Re: Capturing Moves
« Reply #15 on: Aug 14th, 2005, 9:11pm » |
 Quote  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:
Posts: 45
|
|
Re: Capturing Moves
« Reply #16 on: Aug 14th, 2005, 10:32pm » |
Quote 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
Gender:
Posts: 437
|
|
Re: Capturing Moves
« Reply #17 on: Aug 14th, 2005, 11:07pm » |
Quote Modify
|
That is what I wanted  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:
Posts: 45
|
|
Re: Capturing Moves
« Reply #18 on: Aug 15th, 2005, 1:00pm » |
Quote 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
Gender:
Posts: 437
|
|
Re: Capturing Moves
« Reply #19 on: Aug 15th, 2005, 1:04pm » |
Quote Modify
|
sorry about the lazyness comment - just quoted you there
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:
Posts: 682
|
|
Re: Capturing Moves
« Reply #20 on: Aug 15th, 2005, 1:41pm » |
Quote 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:
Posts: 45
|
|
Re: Capturing Moves
« Reply #21 on: Aug 15th, 2005, 2:27pm » |
Quote 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". 
|
| « Last Edit: Aug 16th, 2005, 11:48am by haizhi » |
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Capturing Moves
« Reply #22 on: May 6th, 2009, 1:56pm » |
Quote 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:
Posts: 98
|
|
Re: Capturing Moves
« Reply #23 on: May 8th, 2009, 11:26am » |
Quote 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: 768
|
|
Re: Capturing Moves
« Reply #24 on: May 8th, 2009, 12:58pm » |
Quote 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:
Posts: 682
|
|
Re: Capturing Moves
« Reply #25 on: May 8th, 2009, 1:04pm » |
Quote 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
Gender:
Posts: 5928
|
|
Re: Capturing Moves
« Reply #26 on: May 27th, 2009, 6:30pm » |
Quote 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: 768
|
|
Re: Capturing Moves
« Reply #27 on: May 27th, 2009, 10:48pm » |
Quote 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: 768
|
|
Re: Capturing Moves
« Reply #28 on: May 28th, 2009, 12:20pm » |
Quote 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
Gender:
Posts: 5928
|
|
Re: Capturing Moves
« Reply #29 on: May 28th, 2009, 2:43pm » |
Quote 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 |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print