futility pruning - razoring

[Don]

I have a question about the value of futility and/or razoring in your programs. There seems to be some confusion with these terms - so what I am talking about is the situation where you essentially drop into quies a ply or two earlier than normal if your "stand pat score" is below alpha by some margin.

I am specifically interested in how much speed one can expect and how much weaker it will make your program at the same depth.

I ask because I'm retesting my own implementation of this and the speedup seems unrealistically high - and I see no noticeable weakening of the program - so there must be a bug somewhere. But it occurs to me I have never considered how much others get from this. I'm well over 2X faster and in older programs it seems (form memory) that I should only be getting 30 or 40 percent speedup with a small weakening of strength at the same depth.

[Gerd Isenberg]

I have a question about the value of futility and/or razoring in your programs. There seems to be some confusion with these terms - so what I am talking about is the situation where you essentially drop into quies a ply or two earlier than normal if your "stand pat score" is below alpha by some margin.

I am specifically interested in how much speed one can expect and how much weaker it will make your program at the same depth.

Also interesting would be the total gain in ELO

I ask because I'm retesting my own implementation of this and the speedup seems unrealistically high - and I see no noticeable weakening of the program - so there must be a bug somewhere. But it occurs to me I have never considered how much others get from this. I'm well over 2X faster and in older programs it seems (form memory) that I should only be getting 30 or 40 percent speedup with a small weakening of strength at the same depth.

If you refer to the idea which is mentioned in cpw as Hyatt's Razoring, iirr Bob rejected it. The code from Strelka 2.0 has no if (new_value < beta) condition at depth one. I am about to test it in my old 32-bit program as well.

[bob]

I have a question about the value of futility and/or razoring in your programs. There seems to be some confusion with these terms - so what I am talking about is the situation where you essentially drop into quies a ply or two earlier than normal if your "stand pat score" is below alpha by some margin.

I am specifically interested in how much speed one can expect and how much weaker it will make your program at the same depth.

I ask because I'm retesting my own implementation of this and the speedup seems unrealistically high - and I see no noticeable weakening of the program - so there must be a bug somewhere. But it occurs to me I have never considered how much others get from this. I'm well over 2X faster and in older programs it seems (form memory) that I should only be getting 30 or 40 percent speedup with a small weakening of strength at the same depth.

I am not doing those any longer. I have resorted to simply doing pure forward-pruning out near the tips, and it has worked even better. If a move is within N plies of the q-search (I think I am using 4 but will look) and it meets the criteria for pruning (which has to do with how far below alpha the cheap static evaluation is, among other things) I just skip the move and keep going.

They are worth a lot in terms of speed, but there is a loss in accuracy. I know that I posted results about futility and/or razoring performance improvements measured on my cluster. I think it was in the 10-30 Elo range adding both...

[Don]

I have a question about the value of futility and/or razoring in your programs. There seems to be some confusion with these terms - so what I am talking about is the situation where you essentially drop into quies a ply or two earlier than normal if your "stand pat score" is below alpha by some margin.

I am specifically interested in how much speed one can expect and how much weaker it will make your program at the same depth.

Also interesting would be the total gain in ELO

I ask because I'm retesting my own implementation of this and the speedup seems unrealistically high - and I see no noticeable weakening of the program - so there must be a bug somewhere. But it occurs to me I have never considered how much others get from this. I'm well over 2X faster and in older programs it seems (form memory) that I should only be getting 30 or 40 percent speedup with a small weakening of strength at the same depth.

If you refer to the idea which is mentioned in cpw as Hyatt's Razoring, iirr Bob rejected it. The code from Strelka 2.0 has no if (new_value < beta) condition at depth one. I am about to test it in my old 32-bit program as well.

The strength in ELO is enormous of course if you are getting a 3X speedup with no ELO weakening. My test harness automatically estimates this if you are playing fixed depth games (I use a different doubling estimate depending on what depth I am testing.)

At the momement, based on only 500 games but enough to be in the right general ballpark I am showing 250 ELO improvement!

Part of the explanation is that perhaps the test is idea for this. It's 7 ply, fixed depth, no LMR and no null move pruning. I'm just trying to isolate what is important and what isn't and how things interact. I suspect that with LMR and null move this will go down signficantly - but I don't remember that being the case back in the brute force days of computer chess.

[bob]

I have a question about the value of futility and/or razoring in your programs. There seems to be some confusion with these terms - so what I am talking about is the situation where you essentially drop into quies a ply or two earlier than normal if your "stand pat score" is below alpha by some margin.

I am specifically interested in how much speed one can expect and how much weaker it will make your program at the same depth.

Also interesting would be the total gain in ELO

I ask because I'm retesting my own implementation of this and the speedup seems unrealistically high - and I see no noticeable weakening of the program - so there must be a bug somewhere. But it occurs to me I have never considered how much others get from this. I'm well over 2X faster and in older programs it seems (form memory) that I should only be getting 30 or 40 percent speedup with a small weakening of strength at the same depth.

If you refer to the idea which is mentioned in cpw as Hyatt's Razoring, iirr Bob rejected it. The code from Strelka 2.0 has no if (new_value < beta) condition at depth one. I am about to test it in my old 32-bit program as well.

The strength in ELO is enormous of course if you are getting a 3X speedup with no ELO weakening. My test harness automatically estimates this if you are playing fixed depth games (I use a different doubling estimate depending on what depth I am testing.)

At the momement, based on only 500 games but enough to be in the right general ballpark I am showing 250 ELO improvement!

Part of the explanation is that perhaps the test is idea for this. It's 7 ply, fixed depth, no LMR and no null move pruning. I'm just trying to isolate what is important and what isn't and how things interact. I suspect that with LMR and null move this will go down signficantly - but I don't remember that being the case back in the brute force days of computer chess.

The flaw in this is that you are not getting a true 3x speedup. Your nps should not change much. You will get a ply or two deeper. But with additional errors thrown in, which means that in many positions you need to get two plies deeper to get the same result. It is a win, but it is not a big win. Particularly if you are already using the traditional null-move search. I believe I found between 10 and 30 elo total as I added all of the three types of pruning Heinz mentioned (AEL where the A is null-move) which included futility, extended futility, and razoring. That was somewhere in the 10-30 range when adding all three, assuming null-move and LMR are already in. I don't do any of the futility/razoring specifically, rather I just forward prune at the last few plies using something like the old futility-margin idea (but different and larger as I get farther from the tips).

[BubbaTough]

Are you razoring based on material, or a call to Eval? Because if it is via material, you may be getting some of the benefit usually associated with Lazy Eval, which can be a pretty big speedup.

-Sam

[Don]

Are you razoring based on material, or a call to Eval? Because if it is via material, you may be getting some of the benefit usually associated with Lazy Eval, which can be a pretty big speedup.
-Sam

My program always calls eval - at the moment I do not use Lazy evaluation. I'm still trying to figure out why this does not work in my program as it seems like every good program uses it. I don't think my evaluation is particularly fast so it should help but it doesn't.

If I did not test thoroughly, I probably would have accepted this as a definite program improvement long ago because it almost always plays the same move and it's definitely faster with lazy evaluation. The deciding factor for me is whether it plays stronger or not in real time control games.

I don't know if I buy your argument that I'm getting some of the benefit of lazy evaluation with futility pruning. Can you elaborate? I suppose that lazy evaluation could be thought of as a kind of futility ... so perhaps if you have this you benefit less from futility?

[Gerd Isenberg]

Are you razoring based on material, or a call to Eval? Because if it is via material, you may be getting some of the benefit usually associated with Lazy Eval, which can be a pretty big speedup.
-Sam

My program always calls eval - at the moment I do not use Lazy evaluation. I'm still trying to figure out why this does not work in my program as it seems like every good program uses it. I don't think my evaluation is particularly fast so it should help but it doesn't.

If I did not test thoroughly, I probably would have accepted this as a definite program improvement long ago because it almost always plays the same move and it's definitely faster with lazy evaluation. The deciding factor for me is whether it plays stronger or not in real time control games.

I don't know if I buy your argument that I'm getting some of the benefit of lazy evaluation with futility pruning. Can you elaborate? I suppose that lazy evaluation could be thought of as a kind of futility ... so perhaps if you have this you benefit less from futility?

Yes, lazy stand pat fail high nodes need the additional make/umake which one may safe for almost the same futility condition to skip this move. Lazy eval fail low nodes are probably more seldom to pay off.

[bob]

Are you razoring based on material, or a call to Eval? Because if it is via material, you may be getting some of the benefit usually associated with Lazy Eval, which can be a pretty big speedup.

-Sam

I am not "razoring" whatsoever any longer. I now just outright prune based on a "quick eval" and a pruning margin that gets larger as I get farther from the tips...

Razoring is a quick jump to q-search. I do a quick-jump to UnmakeMove() if I decide to prune it.

[BubbaTough]

Are you razoring based on material, or a call to Eval? Because if it is via material, you may be getting some of the benefit usually associated with Lazy Eval, which can be a pretty big speedup.

-Sam

I am not "razoring" whatsoever any longer. I now just outright prune based on a "quick eval" and a pruning margin that gets larger as I get farther from the tips...

Razoring is a quick jump to q-search. I do a quick-jump to UnmakeMove() if I decide to prune it.

Ahh...that is what I do to. I guess I misunderstood what razoring is.

-Sam