Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> Haizhi's unconnected-step pruning (my notes)
        
(Message started by: 99of9 on Jan 15th, 2009, 8:01pm)
Title: Haizhi's unconnected-step pruning (my notes)
Post by 99of9 on Jan 15th, 2009, 8:01pm
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
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by Fritzlein on Jan 15th, 2009, 8:22pm
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.
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by 99of9 on Jan 15th, 2009, 8:37pm
Good point.  That's an added benefit of open notes... free debugging!  Perhaps I should write more notes so that I can open them.
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by 99of9 on Jan 15th, 2009, 9:25pm

on 01/15/09 at 20:22:20, 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
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by jdb on Jan 15th, 2009, 9:52pm

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.
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by 99of9 on Jan 15th, 2009, 10:20pm

on 01/15/09 at 21:52:38, 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.
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by Janzert on Jan 16th, 2009, 10:43am
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
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by Fritzlein on Jan 16th, 2009, 4:41pm

on 01/15/09 at 21:25:04, 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?
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by 99of9 on Jan 16th, 2009, 5:28pm
Yes.  But anyway, for me the push will be counted later as connected, so it doesn't really matter what the first step was.
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by Fritzlein on Jan 16th, 2009, 8:15pm

on 01/16/09 at 17:28:51, 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.
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by 99of9 on Jan 16th, 2009, 8:28pm
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.
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by jdb on Jan 16th, 2009, 9:54pm

on 01/16/09 at 20:28:43, 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.
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by Oystein on Jan 17th, 2009, 3:29pm

on 01/16/09 at 10:43:16, 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.
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by Janzert on Jan 17th, 2009, 3:41pm

on 01/17/09 at 15:29:30, Oystein wrote:
you have to use the last step for the E to avoid frozen pieces.


Nicely done.

Janzert
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by Hannoskaj on Feb 26th, 2009, 11:03am
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
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by aaaa on Feb 26th, 2009, 2:48pm

on 02/26/09 at 11:03:49, Hannoskaj wrote:
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

Bot-assisted analysis bears out that you have succeeded in your goal. Minor corrections are that ha7s md1w eb7e ch7w is actually a goal in three (since rd6w Ee6w Rd5w Cb5s delays the goal for one more move) and that there is one other move that is not a loss in two, eb7e ec7n Rd7w ch7w, but this still loses in three.


Quote:
By the way, is there any agreeable way to post a position ?

See http://arimaa.com/arimaa/learn/notation.html, under "Notation for Recording Arimaa Positions".
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by Janzert on Feb 27th, 2009, 4:32am
Hannoskaj

It seems your first position has a related first and second step.

For your first position to move Re3n:
 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . x . . x . . |
5| . . . . . . . . |
4| . . . . C e . . |
3| . . x d R R . . |
2| . . . . . . . . |
1| . . . . R . . . |
+-----------------+
  a b c d e f g h
Re1n Re2e Ce4w Re3n

But maybe I'm misunderstanding it as I did the goal example initially.

Janzert
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by Hannoskaj on Feb 27th, 2009, 5:46am

on 02/27/09 at 04:32:42, Janzert wrote:
It seems your first position has a related first and second step.

For your first position to move Re3n:
 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . x . . x . . |
5| . . . . . . . . |
4| . . . . C e . . |
3| . . x d R R . . |
2| . . . . . . . . |
1| . . . . R . . . |
+-----------------+
  a b c d e f g h
Re1n Re2e Ce4w Re3n


I had thought about keeping the cat from protecting the f3 rabbit, but had forgot about the e1 rabbit. Here is a corrected version with Re1n Rf3e Ce4(wn) Re3n as only solution:

 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . x . . x . . |
5| . . . . . . . . |
4| . . . . C e . . |
3| . . x d R R . . |
2| . . . . . c . . |
1| . . . . R . . . |
+-----------------+
  a b c d e f g h

Jonas
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by Hannoskaj on Feb 27th, 2009, 5:55am

on 02/26/09 at 14:48:19, aaaa wrote:
Bot-assisted analysis bears out that you have succeeded in your goal. Minor corrections are that ha7s md1w eb7e ch7w is actually a goal in three (since rd6w Ee6w Rd5w Cb5s delays the goal for one more move) and that there is one other move that is not a loss in two, eb7e ec7n Rd7w ch7w, but this still loses in three.

See http://arimaa.com/arimaa/learn/notation.html, under "Notation for Recording Arimaa Positions".


Thank you for the correction. I must have seen the defence by Gold with loss in three but did not pay attention since I also knew it went through (just forgot to update length). It would certainly be more aesthetic if there was a way to get rid of it, though.

On the other hand, I had completely missed that the cat b5 could be freed and defend for a turn. In fact I thought I had built everything to make that impossible... Anyway, moving db6 to dc5 in the initial position seems to kill that flaw.

Finally, thank you for the link. I do not call that "agreeable", but with a text file as skeleton, it's at least usable.

Jonas
Title: Re: Haizhi's unconnected-step pruning (my notes)
Post by Hannoskaj on Jun 1st, 2009, 1:33am
I just had an idea to define unconnected steps, that would avoid making a complete list of tests such as the one at the beginning of the topic :

Four steps are unconnected if all (24) permutations are still legal and yield the same final position.

This does not cover the case:
* support a trap that the second piece to move was supporting
if there is no piece on the trap to die during the move.

Jonas


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