PVS and aspiration

[PK]

Hi,

When using PVS together with the aspiration window it is soetimes possible to fail low on the first ply of aspirated search in the root node. When it happens, what is the correct course of action:

1) finish the aspirated search, hoping that something that does not fail?
2) interrupt the aspirated search immediately and go for a full-window search?

[bob]

Hi,

When using PVS together with the aspiration window it is soetimes possible to fail low on the first ply of aspirated search in the root node. When it happens, what is the correct course of action:

1) finish the aspirated search, hoping that something that does not fail?
2) interrupt the aspirated search immediately and go for a full-window search?

You have two possibilities as you mentioned.

(1) search the entire root move list before lowering the aspiration window and starting over. This works well for positions where the best (previous) move fails low but there are other ways to avoid the loss.

(2) reset the aspiration window immediately. This makes you re-search the first move, before you search any other moves. If you are going to change your mind, this is less efficient. But it has advantages as well. At least you know how significant your expected loss is going to be, which gives you an idea of how much time you should spend to solve the problem...

I use (2) in Crafty, having tried (1) in the past. What I saw often enough to be a problem was the case where your opponent makes a deep move, that does not lose material, but shallow searches thinks it does and claims to (say) win a pawn. Once you get as deep as your opponent, that pawn+ score will fail low. If you search all moves, each and every one will fail low, and then you get to start over with a lowered alpha value after spending all that time. If you immediately re-aspire on the fail low, you find the true score faster and search the rest of the moves with a better set of bounds to dismiss them quicker.

Each approach has positions that favor them...

[jwes]

Hi,

When using PVS together with the aspiration window it is soetimes possible to fail low on the first ply of aspirated search in the root node. When it happens, what is the correct course of action:

1) finish the aspirated search, hoping that something that does not fail?
2) interrupt the aspirated search immediately and go for a full-window search?

You have two possibilities as you mentioned.

(1) search the entire root move list before lowering the aspiration window and starting over. This works well for positions where the best (previous) move fails low but there are other ways to avoid the loss.

(2) reset the aspiration window immediately. This makes you re-search the first move, before you search any other moves. If you are going to change your mind, this is less efficient. But it has advantages as well. At least you know how significant your expected loss is going to be, which gives you an idea of how much time you should spend to solve the problem...

I use (2) in Crafty, having tried (1) in the past. What I saw often enough to be a problem was the case where your opponent makes a deep move, that does not lose material, but shallow searches thinks it does and claims to (say) win a pawn. Once you get as deep as your opponent, that pawn+ score will fail low. If you search all moves, each and every one will fail low, and then you get to start over with a lowered alpha value after spending all that time. If you immediately re-aspire on the fail low, you find the true score faster and search the rest of the moves with a better set of bounds to dismiss them quicker.

Each approach has positions that favor them...

An intermediate approach might work better. Since crafty does fail low in three steps, it may make sense to research the same move on the first step, but search the other moves first on the second or third step. I parsed some log files to estimate how well this would work. This table shows for each of the three steps how many times it stayed with the same move, changed to a different move, or failed to resolve the fail low in the time available (10 min + 5 sec). It appears it would be better to resolve the first step fail low and search other moves after the second or third fail low step.

Code: Select all

fl    same  diff timeout
  1   603   436   108
  3    53    87    29
  M    16    21     5

p.s. Bob, if you would like, you could put some logs on your ftp site so I could have a larger sample size, or I could send you my ugly awk script.

[bob]

Hi,

When using PVS together with the aspiration window it is soetimes possible to fail low on the first ply of aspirated search in the root node. When it happens, what is the correct course of action:

1) finish the aspirated search, hoping that something that does not fail?
2) interrupt the aspirated search immediately and go for a full-window search?

You have two possibilities as you mentioned.

(1) search the entire root move list before lowering the aspiration window and starting over. This works well for positions where the best (previous) move fails low but there are other ways to avoid the loss.

(2) reset the aspiration window immediately. This makes you re-search the first move, before you search any other moves. If you are going to change your mind, this is less efficient. But it has advantages as well. At least you know how significant your expected loss is going to be, which gives you an idea of how much time you should spend to solve the problem...

I use (2) in Crafty, having tried (1) in the past. What I saw often enough to be a problem was the case where your opponent makes a deep move, that does not lose material, but shallow searches thinks it does and claims to (say) win a pawn. Once you get as deep as your opponent, that pawn+ score will fail low. If you search all moves, each and every one will fail low, and then you get to start over with a lowered alpha value after spending all that time. If you immediately re-aspire on the fail low, you find the true score faster and search the rest of the moves with a better set of bounds to dismiss them quicker.

Each approach has positions that favor them...

An intermediate approach might work better. Since crafty does fail low in three steps, it may make sense to research the same move on the first step, but search the other moves first on the second or third step. I parsed some log files to estimate how well this would work. This table shows for each of the three steps how many times it stayed with the same move, changed to a different move, or failed to resolve the fail low in the time available (10 min + 5 sec). It appears it would be better to resolve the first step fail low and search other moves after the second or third fail low step.

Code: Select all

fl    same  diff timeout
  1   603   436   108
  3    53    87    29
  M    16    21     5

p.s. Bob, if you would like, you could put some logs on your ftp site so I could have a larger sample size, or I could send you my ugly awk script.

I just cleaned them out. Give me a day or two for ICC games to accumulate and I will stick 300 of them on the ftp box...