bob wrote:
First run completed and showed "0 elo improvement" but one takes that with the +/-4 error bar to be not so conclusive. Running another 30K games to refine the accuracy somewhat...
If it sticks at 0 gain, I am done. If it shows some promise, I might try to optimize a bit. But I have tried so many things with null-move in the past, this was almost certainly one of them, and there's generally a reason something is not in my code like that, in that it simply didn't work for me. I am going to look at this a bit further to see if there are any other potential things to try, again..
Probably for you, the cost of calling the eval offsets the benefit. For us (and all the top engines) the eval must be called for various other prunings anyway, so the benefit is free.
In LearningLemming making null move conditional on eval was a net loss for me. I was using some info from the null move search, such as mate threat detection and such, that could have been useful even if null move pruning was not triggered. So its pretty understandable that it was not a net gain for LearningLemming.
What about for deciding whether to try null move or not? I don't see how Crafty could avoid calling the eval in the main search.
No eval test is done in Crafty as a condition for null move. Arasan does not do this either. The efficacy of this is questionable.
--Jon
For us there is no question. We have tried many permutations of the general idea from always doing the null move test regardless of the evaluation to restricting it to certain node types, etc.
What has always worked best is to do null move pruning test only when the current evaluation is already >= beta. A lot of details in each program that could change this formula of course - but for us it's not a close enough call to even be ambiguous.
What does Arasan do? Do you always do the null move test?
I decided to give this a cluster test since that is one option I do not recall having tried in real games. Initially, with a few positional tests, it actually looks like a reasonable idea (I just added && eval >= beta to the end of the rest of the null-move qualifiers such as not being in check, the hash table didn't say null is futile, etc..., so that the eval call is not done on every node, just the ones that pass the earlier filters). Reduced the size of the tree, and slowed the nps. But with a net gain on just a few test positions. Am now running a cluster test to see if it is a real gain in terms of Elo...
More in a couple of hours...
I tried this in EXchess a few weeks ago and it was a small net win. One thing I realized is that it should not slow down the program very much because I would need to do an eval anyway if the null move drops straight into qsearch. So if the eval >= beta, and I do the null move, I keep the score and just use it (with the sign flipped) when qsearch is called rather than repeat the eval.
- Dan
First run completed and showed "0 elo improvement" but one takes that with the +/-4 error bar to be not so conclusive. Running another 30K games to refine the accuracy somewhat...
If it sticks at 0 gain, I am done. If it shows some promise, I might try to optimize a bit. But I have tried so many things with null-move in the past, this was almost certainly one of them, and there's generally a reason something is not in my code like that, in that it simply didn't work for me. I am going to look at this a bit further to see if there are any other potential things to try, again..
Probably for you, the cost of calling the eval offsets the benefit. For us (and all the top engines) the eval must be called for various other prunings anyway, so the benefit is free.
I remain unconvinced. The tree is about tactics. The eval is prettty tactics-stupid in the engines I have looked at. So basing pruning decisions that affect tactics on an evaluation that knows nothing about them seems a bit off-the-edge. Logic says there must be better ways to influence pruning decisions...
Don't you have to do eval on the last four mainsearch plies in order to do futility pruning?
IIRC Crafty does futility based on material score only.
--Jon
What about for deciding whether to try null move or not? I don't see how Crafty could avoid calling the eval in the main search.
I always do null-move. I've tried all the alternatives and the only exception is that I use the hash table trick where entries with a draft that is too shallow can't be used to terminate the search, but they might have draft sufficient to tell me that a null-move search is hopeless.
Why would you want to waste time on null move if you are (let's say) a piece behind beta?
You can still have some unstoppable threat that the opponent can't fix even with two moves in a row... It is not really what I "want to do" but what has actually tested to be stronger in my program.
I do a null-move search unless any one of the following conditions is false:
1. previous ply did not try a null move;
2. hash table hit did not prove that a null-move would likely fail low and be worthless.
3. This is a null-window search (ie not the first move along a PV path, although once the PV-node window collapses to zero, null is done).
4. side on move is not in check
5. moving side has at least one piece left on the board.
Don't you have to do eval on the last four mainsearch plies in order to do futility pruning?
IIRC Crafty does futility based on material score only.
--Jon
What about for deciding whether to try null move or not? I don't see how Crafty could avoid calling the eval in the main search.
I always do null-move. I've tried all the alternatives and the only exception is that I use the hash table trick where entries with a draft that is too shallow can't be used to terminate the search, but they might have draft sufficient to tell me that a null-move search is hopeless.
Why would you want to waste time on null move if you are (let's say) a piece behind beta?
You can still have some unstoppable threat that the opponent can't fix even with two moves in a row... It is not really what I "want to do" but what has actually tested to be stronger in my program.
I do a null-move search unless any one of the following conditions is false:
1. previous ply did not try a null move;
2. hash table hit did not prove that a null-move would likely fail low and be worthless.
3. This is a null-window search (ie not the first move along a PV path, although once the PV-node window collapses to zero, null is done).
4. side on move is not in check
5. moving side has at least one piece left on the board.
Have you actually tested "don't try null move if behind in material"? I would expect that to be better than what you are doing now.
Don't you have to do eval on the last four mainsearch plies in order to do futility pruning?
IIRC Crafty does futility based on material score only.
--Jon
What about for deciding whether to try null move or not? I don't see how Crafty could avoid calling the eval in the main search.
I always do null-move. I've tried all the alternatives and the only exception is that I use the hash table trick where entries with a draft that is too shallow can't be used to terminate the search, but they might have draft sufficient to tell me that a null-move search is hopeless.
Why would you want to waste time on null move if you are (let's say) a piece behind beta?
You can still have some unstoppable threat that the opponent can't fix even with two moves in a row... It is not really what I "want to do" but what has actually tested to be stronger in my program.
I do a null-move search unless any one of the following conditions is false:
1. previous ply did not try a null move;
2. hash table hit did not prove that a null-move would likely fail low and be worthless.
3. This is a null-window search (ie not the first move along a PV path, although once the PV-node window collapses to zero, null is done).
4. side on move is not in check
5. moving side has at least one piece left on the board.
Have you actually tested "don't try null move if behind in material"? I would expect that to be better than what you are doing now.
Did you read my testing post? I actually tested "if eval < beta don't do a null move". I also tried a "fast eval". And a material only. Made absolutely no difference. I'll dig up the results and post when a server at the office gets rebooted so I can get in...
What about for deciding whether to try null move or not? I don't see how Crafty could avoid calling the eval in the main search.
No eval test is done in Crafty as a condition for null move. Arasan does not do this either. The efficacy of this is questionable.
--Jon
For us there is no question. We have tried many permutations of the general idea from always doing the null move test regardless of the evaluation to restricting it to certain node types, etc.
What has always worked best is to do null move pruning test only when the current evaluation is already >= beta. A lot of details in each program that could change this formula of course - but for us it's not a close enough call to even be ambiguous.
What does Arasan do? Do you always do the null move test?
I decided to give this a cluster test since that is one option I do not recall having tried in real games. Initially, with a few positional tests, it actually looks like a reasonable idea (I just added && eval >= beta to the end of the rest of the null-move qualifiers such as not being in check, the hash table didn't say null is futile, etc..., so that the eval call is not done on every node, just the ones that pass the earlier filters). Reduced the size of the tree, and slowed the nps. But with a net gain on just a few test positions. Am now running a cluster test to see if it is a real gain in terms of Elo...
More in a couple of hours...
I tried this in EXchess a few weeks ago and it was a small net win. One thing I realized is that it should not slow down the program very much because I would need to do an eval anyway if the null move drops straight into qsearch. So if the eval >= beta, and I do the null move, I keep the score and just use it (with the sign flipped) when qsearch is called rather than repeat the eval.
- Dan
First run completed and showed "0 elo improvement" but one takes that with the +/-4 error bar to be not so conclusive. Running another 30K games to refine the accuracy somewhat...
If it sticks at 0 gain, I am done. If it shows some promise, I might try to optimize a bit. But I have tried so many things with null-move in the past, this was almost certainly one of them, and there's generally a reason something is not in my code like that, in that it simply didn't work for me. I am going to look at this a bit further to see if there are any other potential things to try, again..
I think that 0 elo shows some promise because it is possible that with some changes in the condition it is more than 0 elo.
The problem is that calling evaluation is expensive for you and there are many cases when eval>=beta so you do not save nodes in the search but you lose speed so you may try to
replace eval>=beta by
(lazy_eval>=beta||eval>=beta) because checking this condition is faster
for all the cases that lazy_eval>=beta.
bob wrote:[ Have you actually tested "don't try null move if behind in material"? I would expect that to be better than what you are doing now.
Did you read my testing post? I actually tested "if eval < beta don't do a null move". I also tried a "fast eval". And a material only. Made absolutely no difference. I'll dig up the results and post when a server at the office gets rebooted so I can get in...[/quote]
I didn't realize you had tested material only. That should avoid eval calls and so the benefit should be free. Do you use precise material values for this test or just 1-3-3-5-9? In this case the crude numbers should be best, because if you use precise values the side slightly behind in material (say bishop for knight for example) may actually be ahead in true eval. Using the crude numbers means that in general you would do null move unless a side is down a full pawn, which usually means his true eval is negative. If you didn't try this, I recommend doing so. I can hardly see how this could fail to help at least slightly.
Don't you have to do eval on the last four mainsearch plies in order to do futility pruning?
IIRC Crafty does futility based on material score only.
--Jon
What about for deciding whether to try null move or not? I don't see how Crafty could avoid calling the eval in the main search.
I always do null-move. I've tried all the alternatives and the only exception is that I use the hash table trick where entries with a draft that is too shallow can't be used to terminate the search, but they might have draft sufficient to tell me that a null-move search is hopeless.
Why would you want to waste time on null move if you are (let's say) a piece behind beta?
You can still have some unstoppable threat that the opponent can't fix even with two moves in a row... It is not really what I "want to do" but what has actually tested to be stronger in my program.
I do a null-move search unless any one of the following conditions is false:
1. previous ply did not try a null move;
2. hash table hit did not prove that a null-move would likely fail low and be worthless.
3. This is a null-window search (ie not the first move along a PV path, although once the PV-node window collapses to zero, null is done).
4. side on move is not in check
5. moving side has at least one piece left on the board.
Have you actually tested "don't try null move if behind in material"? I would expect that to be better than what you are doing now.
I am not sure if I understand you correctly.
Do you suggest simply not doing null move for the side that has less material when beta is not important?
I think that if some condition like this that is not dependent on beta works for Crafty then replacing only material by lazy evaluation even works better.
In other words lazy_eval<= minus 1 pawn(or minus something different)
should work better than only material<= minus 1 pawn
Last edited by Uri Blass on Sat Apr 14, 2012 7:26 pm, edited 2 times in total.
Don't you have to do eval on the last four mainsearch plies in order to do futility pruning?
IIRC Crafty does futility based on material score only.
--Jon
What about for deciding whether to try null move or not? I don't see how Crafty could avoid calling the eval in the main search.
I always do null-move. I've tried all the alternatives and the only exception is that I use the hash table trick where entries with a draft that is too shallow can't be used to terminate the search, but they might have draft sufficient to tell me that a null-move search is hopeless.
Why would you want to waste time on null move if you are (let's say) a piece behind beta?
You can still have some unstoppable threat that the opponent can't fix even with two moves in a row... It is not really what I "want to do" but what has actually tested to be stronger in my program.
I do a null-move search unless any one of the following conditions is false:
1. previous ply did not try a null move;
2. hash table hit did not prove that a null-move would likely fail low and be worthless.
3. This is a null-window search (ie not the first move along a PV path, although once the PV-node window collapses to zero, null is done).
4. side on move is not in check
5. moving side has at least one piece left on the board.
Have you actually tested "don't try null move if behind in material"? I would expect that to be better than what you are doing now.
I am not sure if I understand you correctly.
Do you suggest simply not doing null move for the side that has less material when beta is not important?
I think that if some condition like this that is not dependent on beta works for Crafty then replacing only material by lazy evaluation even works better.
No, I still meant to compare to beta. I agree that lazy eval should work better if it is nearly free, but my main point is that whether you use material only or lazy eval, you should do null move unless the score is below beta by some serious margin, maybe half a pawn. In other words, you want to do null move unless you are maybe 90% confident that the true current score is below beta.
lkaufman wrote: I can hardly see how this could fail to help at least slightly.
There are more things in heaven and earth, Horatio, than are dreamt of in your philosophy.
Many, many people have found it to be true for their programs. I suspect your intuition is guided by the idea that null search is just like normal search except skipping a move. Its not, all sorts of things are different, such as subtracting out several ply, and (depending on implementation) some funky repetition triggers. Leaving out your condition DOES result in more pruning, at a price of course. Whether thats good or bad (and worth the time spent calculating) is a matter easier settled by testing than Gedankenexperiment, and the answer happens to be different for different programs.
That is not even taking into account that some people use null search results for other purposes, such as threat detection, which you lose if you there are some situations you don't trigger it in.
-Sam
Last edited by BubbaTough on Sat Apr 14, 2012 7:37 pm, edited 1 time in total.
