Author |
Topic: Null Move Pruning and races (Read 1418 times) |
|
Ciribot
Forum Junior Member
Arimaa player #1955
Gender: 
Posts: 7
|
 |
Null Move Pruning and races
« on: Mar 19th, 2009, 6:35am » |
 Quote  Modify
|
I'm not sure how many bots implement null moves, but an issue I see with the otherwise quite safe null move pruning is that the reduced search depth will typically push a goal win over the horizon. In these cases the null move will actually be an upper bound of the score for that move, which is very bad. Any thoughts on how to implement null move pruning safely? Typically in chess it is not used in pawn endings due to race conditions.
*typo fixed
|
| « Last Edit: Mar 19th, 2009, 10:13am by Ciribot » |
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Null Move Pruning and races
« Reply #1 on: Mar 19th, 2009, 8:40am » |
Quote Modify
|
on Mar 19th, 2009, 6:35am, Ciribot wrote:| I'm not sure how many bots implement null moves, but an issue I see with the otherwise quite safe null move pruning is that the reduced search depth will typically push a goal win over the horizon. In these cases the null move will actually be an upper bound of the score for that much, which is very bad. Any thoughts on how to implement null move pruning safely? Typically in chess it is not used in pawn endings due to race conditions. |
|
There are quite a few races of different sorts in Arimaa, so if goal races undermine null-move-pruning, then wouldn't capture races also do so, and racing-to-smother-elephant-holding-camel-hostage before-free-camel-wreaks-havoc, etc?
It's somewhat counter-intuitive that null-move pruning would cause a mis-evaluation of a race, because a race is precisely the sort of situation where giving up a move and still winning is proof positive of a superior position. On the other hand, I guess I can see how searching to different depths in different lines means that one line will race to completion and get a correct eval, while another line will not finish the race and get a skewed eval.
Is it a possible solution to declare that certain extensions must happen even in parts of the tree that are being searched to reduced depth for whatever reason? The logic would be, that whatever reason we had for searching a certain line more shallowly is trumped by hanging pieces and imminent goal threat; the latter always mandate deeper search until the position quiets down.
|
|
IP Logged |
|
|
|
Ciribot
Forum Junior Member
Arimaa player #1955
Gender:
Posts: 7
|
|
Re: Null Move Pruning and races
« Reply #2 on: Mar 19th, 2009, 10:11am » |
Quote Modify
|
I think race might not be the word I was looking for, more like some goal that will inevitably happen. However it can also cause misevaluations of races because it will prefer the null move to a lost race.
If there is some inevitable danger on the horizon, the null move will always cause the AI to think 'this can be avoided', whether it is a win, or a positional disadvantage. Null move pruning really works in chess because inevitable checkmate is usually made much worse with null-move, as well usually follows many checks (in which null-move is never applied).
In my board game, the game is also won by a 'goal' condition (be first to get a piece to the other side, that is), I managed to save a lot of tactical strength by never using a null move to refute a win. That is, if another move has already said 'this is a loss for us', null move pruning isn't used. This isn't perfect, and causes an unstable search to some extent, but greatly improves evaluation of positions where a piece is near the other side.
|
| « Last Edit: Mar 19th, 2009, 10:20am by Ciribot » |
IP Logged |
|
|
|
fotland
Forum Guru
Arimaa player #211
Gender:
Posts: 216
|
|
Re: Null Move Pruning and races
« Reply #3 on: Mar 31st, 2009, 8:24am » |
Quote Modify
|
Bomb uses null move.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print