Author |
Topic: Safe pruning (Read 1895 times) |
|
lightvector
Forum Guru
Arimaa player #2543
Gender: 
Posts: 197
|
 |
Safe pruning
« on: Feb 12th, 2008, 4:12pm » |
 Quote  Modify
|
I have been thinking about various ideas for forward pruning, and I was wondering what lines, based on static criteria, could provably be cut from a search.
One of the situations I considered was deliberately stepping one's piece into a trap that currently has no friendly defenders. Can anyone construct a position where this is the best move? I haven't been able to (barring the exceptional cases where it is the only legal move), but there might be a few out there.
Does anyone know of any other possibilities for safe forward pruning? I doubt very much could be safely pruned in total by static criteria, but every little bit helps, before I begin to play with less sound methods.
|
|
 IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Safe pruning
« Reply #1 on: Feb 12th, 2008, 4:52pm » |
Quote Modify
|
It will be good to think through this topic.
One counterexample for you is when a piece suicides to let a rabbit through the square it was on. This is rare because it requires that the piece cannot just move out of the way in the other free direction. If that other direction is blocked by a strong enemy piece, then the rabbit would get frozen on its way though, so the other direction must be blocked by a friendly piece or an enemy rabbit:
for example gold to move
.rrrrr.r
........
..xe.xEM
rm....R.
........
..x..x..
..c.....
.....R..
|
| « Last Edit: Feb 12th, 2008, 4:54pm by 99of9 » |
IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: Safe pruning
« Reply #2 on: Feb 12th, 2008, 5:55pm » |
Quote Modify
|
Great example!
I completely forgot that I had considered cases like this when writing my 4-step goal tree (which I have just finished coding. Yay!). Fortunately, after I finish debugging the goal tree, it will catch such cases directly.
Unfortunately, I suppose if a sacrifice like this can be required for an immediate goal, then it would be conceivable to build a position where a forced goal in three moves would also require such a sacrifice as the first move. Yuck.
|
|
IP Logged |
|
|
|
arimaa_master
Forum Guru
Arimaa player #2010
Gender:
Posts: 358
|
|
Re: Safe pruning
« Reply #3 on: Feb 13th, 2008, 3:03am » |
Quote Modify
|
Another example could be position which requires to sacrifice a piece to gain a stronger one. (This means, that friendly piece is on the way of achieving this and only free direction where to sidestep is trap.)
|
|
IP Logged |
|
|
|
ddyer
Forum Guru
Gender:
Posts: 66
|
|
Re: Safe pruning
« Reply #4 on: Apr 6th, 2008, 3:16pm » |
Quote Modify
|
Based on my years Go programming, I don't think you're
likely to find any significant classes of moves that can be
removed safely. If you do find some, they're not going to
make up a significant enough portion of all moves to justify
the effort to identify them.
On the other hand, throwing away vast classes of moves
without considering them because they're probably useless
is a fine strategy to reduce the size of the space. You just
have to accept that it will be possible to construct situations
where your program will not find the optimal solution.
Examples of this are found in the Zertz and Punct robots
at Boardspace.net. The zertz robot never considers two
unforced moves in a row. The punct robot considers only
a statistical sample of pieces "dropped" onto the board
not in contact with any other pieces, and doesn't consider
board-to-board moves that are not in contact with other
pieces at all.
|
| « Last Edit: Apr 6th, 2008, 3:22pm by ddyer » |
IP Logged |
visit my game site: http://www.boardspace.net/
free online abstract strategy games
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: Safe pruning
« Reply #5 on: Apr 7th, 2008, 12:42pm » |
Quote Modify
|
on Apr 6th, 2008, 3:16pm, ddyer wrote:Based on my years Go programming, I don't think you're
likely to find any significant classes of moves that can be
removed safely. If you do find some, they're not going to
make up a significant enough portion of all moves to justify
the effort to identify them. |
|
And you can always just use measures of moves you think are probably bad in your move ordering function ... put them last. Then you're very likely to get a cutoff because you've looked at better moves first, without actually preventing the bot from searching them in the rare cases where they're worthwhile. So you're not actually pruning them, but 90%+ of the time you will get the same effect, or close enough.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Safe pruning
« Reply #6 on: Apr 7th, 2008, 2:23pm » |
Quote Modify
|
on Apr 6th, 2008, 3:16pm, ddyer wrote:| On the other hand, throwing away vast classes of moves without considering them because they're probably useless is a fine strategy to reduce the size of the space. |
|
Are you saying that unsafe pruning has been effectively applied in Go searchers (i.e. it has raised their playing strength)? Or just Zertz and Punct?
|
| « Last Edit: Apr 7th, 2008, 2:24pm by Fritzlein » |
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Safe pruning
« Reply #7 on: Apr 7th, 2008, 2:34pm » |
Quote Modify
|
My, admittedly very limited, understanding is that pretty much all of the "traditional"1 go programs use large amounts of pruning. If I recall correctly Fotland said that mfgo only considers around a half dozen moves at the root. I guess whether you say these are effective or not is a matter of your viewpoint.
Janzert
1 The heavy pattern matching programs such as many faces, gnugo, etc. as opposed to the more recent UCT/MC based programs.
|
| « Last Edit: Apr 7th, 2008, 2:36pm by Janzert » |
IP Logged |
|
|
|
ddyer
Forum Guru
Gender:
Posts: 66
|
|
Re: Safe pruning
« Reply #8 on: Apr 8th, 2008, 7:35pm » |
Quote Modify
|
on Apr 7th, 2008, 2:34pm, Janzert wrote:| My, admittedly very limited, understanding is that pretty much all of the "traditional"1 go programs use large amounts of pruning. |
|
That is also my understanding.
|
|
IP Logged |
visit my game site: http://www.boardspace.net/
free online abstract strategy games
|
|
|
fotland
Forum Guru
Arimaa player #211
Gender:
Posts: 216
|
|
Re: Safe pruning
« Reply #9 on: Apr 9th, 2008, 1:25am » |
Quote Modify
|
This is correct. Many Faces only looks at 20 to 40 moves at the root, and 5 to 10 during the main search, and 1 to 5 during quiescence search. Other traditional programs are similar.
On 19x19, the strong uct/mc programs also do considerable pruning in the main search, so they search deep and narrow. They will visit all legal moves if given enough time, but in practice they only look at a few moves in most positions.
David
on Apr 7th, 2008, 2:34pm, Janzert wrote:My, admittedly very limited, understanding is that pretty much all of the "traditional"1 go programs use large amounts of pruning. If I recall correctly Fotland said that mfgo only considers around a half dozen moves at the root. I guess whether you say these are effective or not is a matter of your viewpoint.
Janzert
1 The heavy pattern matching programs such as many faces, gnugo, etc. as opposed to the more recent UCT/MC based programs. |
|
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print