Author |
Topic: Haizhi's unconnected-step pruning (my notes) (Read 4674 times) |
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender: 
Posts: 1413
|
 |
Haizhi's unconnected-step pruning (my notes)
« on: Jan 15th, 2009, 8:01pm » |
 Quote  Modify
|
This is a dump of my notes on Haizhi's step pruning, some of it won't make sense, but feel free to ask.
Standard types of dependencies:
* push
* pull
* step to unfreeze subsequent stepping piece
* vacate square for subsequent stepping piece
* move same piece twice
* support a trap that the second piece to move was supporting
(1) Complex dependencies:
(a)
In the following position
r r - r r r m H
r c E d r M - R
C - R c d - R -
- - - R D R - r
- - - - - - D -
- H - R e - - -
- - - - - R - -
- - - - - - - -
the unpruned version would like to play Rg6n Mf7s Mf6e de6e df6x
but the pruned version is forced to play Mf7s Mf6n de6e df6x Rh7w
it would be nice to acknowledge here that the 3rd step depends on the first
(b)
In the following position
r r r r r r r r
- - - - - R - -
- E M - d R - -
- - - - - R - -
- - - - - - e -
- - - - - - - -
- - - - - - - -
- - - - - - - -
we would like to be able to play Rf6e Mc6e de6e df6x Md6e
The first step is making room for the push, which also depends on the camel coming across. The first two moves could be switched, but they both need to be before the push.
(c)
./runtest.sh H 11
r - c - r - r -
- - - E r C h r
r - - - R - R -
- r - - e - - -
- - R - - - - -
- - - - D - H -
- M - R - C h R
- - - d - - R -
we would like to be able to play Rc4n Ed7w Rc5n Rc6w
The first two steps are necessary for the third. They could be switched, but they both need to be before the rabbit steps on the trap (the dependent step).
(2)
Sometimes the 9th and 10th steps in a search are severely disadvantaged if they have to be connected. e.g. think about a piece that on the 9th steps moves to defend a trap... it is then forced to move again (!) or hope that a piece can shuffle in behind it.
SOLUTION: Perhaps don't apply the pruning during the last 4 ply? DONE
(3)
Similar to (2), the fact that the connected steps have to be done *first* in the final move may mean the search doesn't get to do the most important, disconnected, steps.
e.g.
./runtest.sh 13 11
gives different scores because the full search would prefer to put a final push on the 11th and 12th steps.
SOLUTION: Perhaps don't apply the pruning during the last 4 ply? DONE
|
|
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Haizhi's unconnected-step pruning (my notes)
« Reply #1 on: Jan 15th, 2009, 8:22pm » |
Quote Modify
|
A dependency which I don't see among your cases: First step is a piece on a trap getting off so that the lone piece supporting it can move away on the second step.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Haizhi's unconnected-step pruning (my notes)
« Reply #2 on: Jan 15th, 2009, 8:37pm » |
Quote Modify
|
Good point. That's an added benefit of open notes... free debugging! Perhaps I should write more notes so that I can open them.
|
| « Last Edit: Jan 15th, 2009, 8:39pm by 99of9 » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Haizhi's unconnected-step pruning (my notes)
« Reply #3 on: Jan 15th, 2009, 9:25pm » |
Quote Modify
|
on Jan 15th, 2009, 8:22pm, Fritzlein wrote:| A dependency which I don't see among your cases: First step is a piece on a trap getting off so that the lone piece supporting it can move away on the second step. |
|
I just remembered that I hadn't missed this, it is covered by:
* support a trap that the second piece to move was supporting
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Haizhi's unconnected-step pruning (my notes)
« Reply #4 on: Jan 15th, 2009, 9:52pm » |
Quote Modify
|
Quote:Standard types of dependencies:
* push
* pull
* step to unfreeze subsequent stepping piece
* vacate square for subsequent stepping piece
* move same piece twice
* support a trap that the second piece to move was supporting
|
|
When I tried this in clueless, I used all these except the last one.
It is turned off when there is a goal threat.
Capture moves are generated separately. Seemed too important to risk overlooking any.
The pruning is not applied on the first 4 steps. (ie the first move)
This type of pruning was a huge gain, it added about two steps to the search depth.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Haizhi's unconnected-step pruning (my notes)
« Reply #5 on: Jan 15th, 2009, 10:20pm » |
Quote Modify
|
on Jan 15th, 2009, 9:52pm, jdb wrote:| This type of pruning was a huge gain, it added about two steps to the search depth. |
|
That's astounding. When I put in a version a bit like yours (but with pruning in the first 4 ply, and without any special capture generation), I got an improvement factor of about 1.7. But when I rearranged it to cope with the complex cases I posted, I didn't get anything near as good. In fact I decided that it had all been a bit of a waste of time.
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Haizhi's unconnected-step pruning (my notes)
« Reply #6 on: Jan 16th, 2009, 10:43am » |
Quote Modify
|
The "complex dependencies" here are quite interesting in that they break an assumption made by Haizhi in his thesis that all 3 step combos have a dependency between steps 1 and 2. Instead step 3 has a dependency on both step 1 and 2 without any dependency between them.
It leads me to wonder if it would be possible to come up with a 4 step combo such that the 4th step depends on all of the previous steps without any dependency between the first 3 steps. So far I haven't thought of a way and my guess is that there isn't.
Also I don't think accurately including these 3 step combos would add significantly to the size of the search tree. Although it does make it a fair bit more complex to track.
Currently opfor prunes using the things mentioned above as standard dependencies plus allowing steps where a piece moves away from supporting a trap after the first step was moving a piece off of that trap. It's also conservative instead of exact in some of its checks (e.g. the unfreeze check doesn't check that a piece was actually frozen merely that it was neighboring to an enemy piece with no friendly neighbors previously).
Janzert
|
| « Last Edit: Jan 16th, 2009, 10:44am by Janzert » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Haizhi's unconnected-step pruning (my notes)
« Reply #7 on: Jan 16th, 2009, 4:41pm » |
Quote Modify
|
on Jan 15th, 2009, 9:25pm, 99of9 wrote:I just remembered that I hadn't missed this, it is covered by:
* support a trap that the second piece to move was supporting |
|
Ah, I missed that subtlety. But did you include the case where the piece supporting the trap wants to make a push instead of just a step?
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Haizhi's unconnected-step pruning (my notes)
« Reply #8 on: Jan 16th, 2009, 5:28pm » |
Quote Modify
|
Yes. But anyway, for me the push will be counted later as connected, so it doesn't really matter what the first step was.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Haizhi's unconnected-step pruning (my notes)
« Reply #9 on: Jan 16th, 2009, 8:15pm » |
Quote Modify
|
on Jan 16th, 2009, 5:28pm, 99of9 wrote:| Yes. But anyway, for me the push will be counted later as connected, so it doesn't really matter what the first step was. |
|
Wait, if you don't insist that the first two steps be connected to each other, doesn't that give away almost all of the pruning benefit? If you wait until the move is over before determining that it was connected somewhere inside of it, then you have done a ton of extra move generation. I thought the whole point of haizhi's scheme was to prune enormously at the second step.
|
| « Last Edit: Jan 16th, 2009, 8:17pm by Fritzlein » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Haizhi's unconnected-step pruning (my notes)
« Reply #10 on: Jan 16th, 2009, 8:28pm » |
Quote Modify
|
I wanted to include even the complex dependencies, so I couldn't think of a way do it only in between step 1 and 2.
Move generation is reasonably quick. Beyond that in the search the transposition table will reduce it to the same subset of moves anyway. So the saving I'm looking for is the value of never having to look deeper after those full moves. For example, after each 4 ply, if half of the moves are excluded, the theoretical best cost of the alpha beta tree goes down by a factor of 2^(ply_steps/8), though as you say, it loses some for generating each 4-ply in full.
|
| « Last Edit: Jan 16th, 2009, 8:33pm by 99of9 » |
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Haizhi's unconnected-step pruning (my notes)
« Reply #11 on: Jan 16th, 2009, 9:54pm » |
Quote Modify
|
on Jan 16th, 2009, 8:28pm, 99of9 wrote:I wanted to include even the complex dependencies, so I couldn't think of a way do it only in between step 1 and 2.
Move generation is reasonably quick. Beyond that in the search the transposition table will reduce it to the same subset of moves anyway. So the saving I'm looking for is the value of never having to look deeper after those full moves. For example, after each 4 ply, if half of the moves are excluded, the theoretical best cost of the alpha beta tree goes down by a factor of 2^(ply_steps/8), though as you say, it loses some for generating each 4-ply in full. |
|
I may be misunderstanding things here.
Lets say there is a depth of 8 left to search, at the start of a move. Haizhi's method will prune most of the second step moves away. This results in pruning a bunch of depth 7 subtrees. If we try to capture the complex cases, the pruning happens on the third step (Is this correct?). This results in pruning depth 6 subtrees. This is a huge difference in the size of tree reduction. It looks nice to include the complex cases, but the cost seems fairly high. Maybe if there was some way to prune the majority of the moves on the second step, the numbers would work out better.
|
|
IP Logged |
|
|
|
Oystein
Forum Full Member
Arimaa player #3272
Gender:
Posts: 21
|
|
Re: Haizhi's unconnected-step pruning (my notes)
« Reply #12 on: Jan 17th, 2009, 3:29pm » |
Quote Modify
|
on Jan 16th, 2009, 10:43am, Janzert wrote:| It leads me to wonder if it would be possible to come up with a 4 step combo such that the 4th step depends on all of the previous steps without any dependency between the first 3 steps. |
|
If you want to move E north, R west, C east and D south you in this position:
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - R E C - -
- - - h D h - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
you have to use the last step for the E to avoid frozen pieces.
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Haizhi's unconnected-step pruning (my notes)
« Reply #13 on: Jan 17th, 2009, 3:41pm » |
Quote Modify
|
on Jan 17th, 2009, 3:29pm, Oystein wrote:
you have to use the last step for the E to avoid frozen pieces. |
|
Nicely done.
Janzert
|
|
IP Logged |
|
|
|
Hannoskaj
Forum Guru
Arimaa player #3794
Gender:
Posts: 75
|
|
Re: Haizhi's unconnected-step pruning (my notes)
« Reply #14 on: Feb 26th, 2009, 11:03am » |
Quote Modify
|
I'm not sure that Fritzlein's example really relates to the same definition as examples above: here the last move is not permitted by the first three, it's only necessary to make it in the end in order to also play the first three steps.
If we take for definition of "related": enables the move, we then have the following problem:
- Since we are interested in the fourth step, it must neither be a push nor a pull but a plain move.
- Since we want the first three moves to be unrelated between each other, they cannot be pushes or pulls, either.
- The only things that can prevent a plain move are:
* piece frozen
* unavailable arrival square
* maybe death on a trap if that's the final square (extended meaning)
* maybe loss of a piece it was defending (extended meaning)
For each condition, one step at most is sufficient to cure it, otherwise we would have related first three steps. Hence we cannot obtain an example with only the two first conditions.
Combining condition 2 with 3 serves no purpose: when the piece on the trap leaves, it defends the trap.
We are then left with conditions 1,2 and 4. It's easy to build an example:
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - C e - -
- - - d R R - -
- - - - - - - -
- - - - R- - -
Rabbit e3 to move to e4.
By the way, I have also played at making a position where the only winning move is making four uncorrelated steps.
Here silver goals in two (ha6 mc1 ec7 cg7), but any other move is a loss in two, if I am not mistaken (typically Db2 to defend (or Cb4 if free) and Db6 Ra6).
Silver: r d8 e7 d6 a5; c h7; d b6; h a7 e5; m d1; e b7
Gold: R d5 d7 g6; C b5; D b1 g4; E e6
By the way, is there any agreeable way to post a position ?
Jonas
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print