Author |
Topic: Null Move (Read 1547 times) |
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
So the Null Move works like this (or can be used like this): the bot examines an opponent's move (ie 4-step turn) that results in a big material advantage for the bot (eg the bot can take a the opponent's elephant), and then the bot pretends to pass its move (the null move) so the opponent has two full moves (8 steps), and if the opponent still can't win the material back or score a goal (etc) then it can be assumed that the opponent wouldn't choose to do that move in the first place, and that move can be pruned.
Bomb uses Null Move, but what are other thoughts? ... does it really add value for arimaa (even though it works in chess), due to the amount of time it takes to search two opponent full moves?
If the bot really can take the opponent's elephant, wouldn't qsearch and static material/goal evaluations be enough to prune the move?
|
|
 IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender: 
Posts: 605
|
 |
Re: Null Move
« Reply #1 on: May 27th, 2011, 6:31am » |
 Quote  Modify
|
on May 25th, 2011, 8:33pm, Swynndla wrote:
Bomb uses Null Move, but what are other thoughts? ... does it really add value for arimaa (even though it works in chess), due to the amount of time it takes to search two opponent full moves? |
|
I've been meaning to make a test of my bot with null-move enabled vs null-move disabled, but I haven't had a chance yet. I think I started a test on that once which was strangely unable to prove it made the bot stronger, but that was a while ago and I didn't let the test finish for some reason.
Intuitively it makes sense that it would help... there are so many bad moves in any Arimaa position (such as simply throwing pieces into an empty trap), and null-move should prune them in a very efficient way. The way I do it in my bot, if a position was going to be searched to a depth of 3 plies (12 steps), a successful null-move replaces this search with a single 1 ply search. A 1-ply search takes negligible time compared to a 3-ply search.
on May 25th, 2011, 8:33pm, Swynndla wrote:
If the bot really can take the opponent's elephant, wouldn't qsearch and static material/goal evaluations be enough to prune the move? |
|
Qsearch / static trap evaluation is typically applied only at depth = 0, so it's not used in the same situations as null-move is. A typical pre-condition for applying null-move is something like "depth >=2".
Static goal detection only applies in a very narrow subset of legal positions, typically in the endgame. Null-move can be applied anywhere starting immediately from the opening.
|
| « Last Edit: May 27th, 2011, 7:26am by rbarreira » |
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: Null Move
« Reply #2 on: May 27th, 2011, 7:42am » |
Quote Modify
|
Thanks for that rbarreira, and thanks for explaining how you implement it in your bot. I'm a newbie at this sort of thing, and I appreciate any help & thoughts. 
on May 27th, 2011, 6:31am, rbarreira wrote:| The way I do it in my bot, if a position was going to be searched to a depth of 3 plies (12 steps), a successful null-move replaces this search with a single 1 ply search. A 1-ply search takes negligible time compared to a 3-ply search. |
|
You'll see by my questions that I haven't got my head around null-move like I thought I had. I've read that a 1 ply search (or two less than depth) is reducing rather than pruning, and it doesn't miss as many tactics that way (although for the limited depth of arimaa I'm not sure how many tactics it would see over pruning). I think I understand that bit, but the specifics confuse me. If your bot's opponent does a weak move that lets your bot trap (ie take) the opponents elephant (and this might take up to a 4-step move), then your bot would give the opponent two moves to see if the opponent had anything sneaky it could do, and if after those two moves your bot still had an advantage out of it, then it would only search one ply from root ... but you've already searched two opponent plies right? (and the first opponent ply is a legitimate ply) ... so that doesn't make sense, unless you mean one more ply after the opponent's ply, which would be the bot's move, and that would be 3 plies - but your tree is only searching to three plies anyway?? I hope you can see where I'm confused. Or are you meaning that it works like this: the opponent moves the opponent's elephant into an undefended trap (and loses the elephant straight away) and now it's the bot's turn, but instead does the null-move giving the opponent another turn to see if it's got something sneaky, and if not then searches one ply from root (ie the bot's turn) instead of three plies. There - have I just answered my own question? Edit: hmmm that doesn't quite work, as the move can't be pruned because the opponent has already made the move.
Quote:| Qsearch / static trap evaluation is typically applied only at depth = 0, so it's not used in the same situations as null-move is. A typical pre-condition for applying null-move is something like "depth >=2". |
|
Ahhh that part makes sense! Do you perform a null move on every move from the root of the tree, or only the ones where there's a capture?
|
| « Last Edit: May 27th, 2011, 7:46am by Swynndla » |
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Null Move
« Reply #3 on: May 27th, 2011, 8:27am » |
Quote Modify
|
on May 27th, 2011, 7:42am, Swynndla wrote:
You'll see by my questions that I haven't got my head around null-move like I thought I had. I've read that a 1 ply search (or two less than depth) is reducing rather than pruning, and it doesn't miss as many tactics that way (although for the limited depth of arimaa I'm not sure how many tactics it would see over pruning).
|
|
Very true, null-move searches can be confusing to understand (I think when I first implemented it I didn't fully understand it either).
There is both reducing and pruning involved in what is usually called "null-move pruning". A reduced depth search is done in order to decide whether or not to prune, i.e. whether to do the so called cut-off ("return beta"). In my bot the depth is reduced by 2, i.e. a 2-ply search becomes a 0-ply search (which is a Qsearch), a 3-ply search becomes a 1-ply search etc.
This pruning is, however, temporary and not permanent. The decision of whether to prune or not depends both on the position being searched AND the depth that the position is being searched to. This means that even if a move at the root results in a position that gets pruned, in the next iteration (when the depth is larger) the null-move cut-off might not happen since the null-move search also has increased its depth.
To sum up it's very accurate to call null-move pruning a search reduction technique. We're effectively searching certain moves to a higher depth than others. I hope that wasn't too confusing, otherwise I can try to clarify.
on May 27th, 2011, 7:42am, Swynndla wrote:
If your bot's opponent does a weak move that lets your bot trap (ie take) the opponents elephant (and this might take up to a 4-step move), then your bot would give the opponent two moves to see if the opponent had anything sneaky it could do, and if after those two moves your bot still had an advantage out of it, then it would only search one ply from root ... but you've already searched two opponent plies right? (and the first opponent ply is a legitimate ply) ... so that doesn't make sense, unless you mean one more ply after the opponent's ply, which would be the bot's move, and that would be 3 plies - but your tree is only searching to three plies anyway?? I hope you can see where I'm confused. Or are you meaning that it works like this: the opponent moves the opponent's elephant into an undefended trap (and loses the elephant straight away) and now it's the bot's turn, but instead does the null-move giving the opponent another turn to see if it's got something sneaky, and if not then searches one ply from root (ie the bot's turn) instead of three plies. There - have I just answered my own question? Edit: hmmm that doesn't quite work, as the move can't be pruned because the opponent has already made the move.
Ahhh that part makes sense! Do you perform a null move on every move from the root of the tree, or only the ones where there's a capture?
|
|
I think the easiest example to understand is indeed the one where a piece is thrown into an empty trap. This is one of the cases where, when the search skips to the other player's turn after the sacrifice, a null-move search will typically be successful. For example: (each line is a new ply)
- depth = 4; player A sacrifices an elephant without doing anything else
- depth = 3; player B tries a null-move search to see if it has a great position. the depth of the null-move search is 3-2 = 1
- depth = 1; player A tries all moves, but without the elephant it can't find any great one, so it returns a low score.
This low score is negated as normal in player B's depth 3 search, which results in a high score (>= beta) for player B, which results in an immediate cut-off and, after another negation resulting in a low score at depth 4 for player A. This is theoretically how the elephant-sacrificing move gets assigned a low score without much search.
PS: BTW for me, a null-move search can happen for either player as long as depth >= 2, so it applies equally for opponent moves and the bot's moves. That's why the example simply says players A/B without specifying which is the opponent.
|
| « Last Edit: May 27th, 2011, 8:29am by rbarreira » |
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: Null Move
« Reply #4 on: May 27th, 2011, 9:24am » |
Quote Modify
|
Wow thank you rbarreira for taking the time to explain it in a way I can understand. It was good of you to break down that example into steps, and I can now see how it's implemented.
It seems that it must reduce the search tree (and it should be pretty safe as long as the static evaluation is decent). I wonder if any of the top bots don't use null-move.
|
|
IP Logged |
|
|
|
Druzil
Forum Junior Member
Arimaa player #6252
Gender:
Posts: 6
|
|
Re: Null Move
« Reply #5 on: May 27th, 2011, 7:32pm » |
Quote Modify
|
greate example rbarreira. I've been meaning to implement null moves, but hadn't quite got my head around them yet. Cheers
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print