Extended Null-Move Reductions

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
bob
Posts: 20478
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Extended Null-Move Reductions

Post by bob » Fri Aug 20, 2010 5:48 pm

Milos wrote:
bob wrote:I stopped with the 2~3 a couple of years ago. But the basic idea of the paper is that rather than failing high if the null-move search returns a value >= beta, you just reduce the depth and do the normal search (reduction = 4 in this paper). That's a significant departure from null-move search and is somewhat akin to the verification search idea that I also consider to be bad... But when you said "stockfish, et. al. use this" that imples they use the basic idea presented in the paper, which nobody does that I am aware of (unless you count the somewhat similar verification search idea).
Ok my bad expression. I meant the idea of more aggressive null move reduction, not reducing depth and continuing search on fail-high which might be the main idea of the paper, but is certainly not the idea that brought them elo.

The thing with all null-move verification schemes is that zugzwangs are simply too rare in elo terms and good balance between verification search depth and reliable zugzwangs detection simply doesn't exist.
If you increase the tree just little (too high verification search depth reduction) you won't catch any zugzwangs, and will just search additionally for nothing. If you don't reduce verification search depth much, you will detect most of zugzwangs but you will pay much higher penalty elowise in bigger tree searching. Optimum doesn't exists. Or, more precisely optimum exists and is achieved for no verification search :).
Certainly matches my results to date...

Some have great difficulty with the simple concept "you have to accept the bad with the good." If you try to eliminate the bad, you almost always eliminate part (or all) of the good as well...

Cardoso
Posts: 292
Joined: Thu Mar 16, 2006 6:39 pm

Many thanks for the testing (NT)

Post by Cardoso » Fri Aug 20, 2010 6:39 pm

NT.

bob
Posts: 20478
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Many thanks for the testing (NT)

Post by bob » Fri Aug 20, 2010 6:48 pm

Cardoso wrote:NT.
Currently running the test as it is done in the paper (return evaluate() if depth<= 0). Still behind standard version, but I have several different R values to test. More later

Michiel Koorn

Re: Extended Null-Move Reductions

Post by Michiel Koorn » Fri Aug 20, 2010 7:08 pm

bob wrote: Once again someone uses test positions to decide whether an idea is good or bad, followed by self-play bet3ween two versions, one with the idea, one without. The right way to test is with a group of opponents that don't change. Given the test results, it is impossible to say whether this is good, bad or ugly.
Novice question, but what is the issue with self play as a test?

bob
Posts: 20478
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Extended Null-Move Reductions

Post by bob » Fri Aug 20, 2010 7:14 pm

Michiel Koorn wrote:
bob wrote: Once again someone uses test positions to decide whether an idea is good or bad, followed by self-play bet3ween two versions, one with the idea, one without. The right way to test is with a group of opponents that don't change. Given the test results, it is impossible to say whether this is good, bad or ugly.
Novice question, but what is the issue with self play as a test?
If you take a program A, and make one change to the program to produce A', when you test A vs A' the change usually produces an exaggerated result that can be misleading. A has no code to "counteract" the change to A' so all you see is the effect of that change tested in a vacuum. Against a gauntlet, it is not uncommon to see a change help against one opponent, but hurt against others resulting in an overall worse result. I used to have some interesting numbers from when we started cluster testing, comparing A vs A' head-to-head and A vs A' where each plays against a common group of opponents. The results disagreed about as often as they agreed, convincing me it was a poor way of evaluating changes.

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Extended Null-Move Reductions

Post by mcostalba » Fri Aug 20, 2010 7:15 pm

Milos wrote: The thing with all null-move verification schemes is that zugzwangs are simply too rare in elo terms and good balance between verification search depth and reliable zugzwangs detection simply doesn't exist.
This is another myth to be debunked.

I don't know who is the fellow that come up with the idea that null verification search is needed for zugzwangs....and I also don't know how was it possible that a lot of people followed that statement blindly as dumb sheeps follow the shepherd.

Hint: null verification has nothing to do with zugzwangs, especially at very high depths.

You don't believe ? Ok, pick up all the positions where null search at big depth failed high and following verification failed low, print on your screen and try to find the zugzwang in them..you will be surprised you will find none (or very few).

bob
Posts: 20478
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Extended Null-Move Reductions

Post by bob » Fri Aug 20, 2010 7:21 pm

mcostalba wrote:
Milos wrote: The thing with all null-move verification schemes is that zugzwangs are simply too rare in elo terms and good balance between verification search depth and reliable zugzwangs detection simply doesn't exist.
This is another myth to be debunked.

I don't know who is the fellow that come up with the idea that null verification search is needed for zugzwangs....and I also don't know how was it possible that a lot of people followed that statement blindly as dumb sheeps follow the shepherd.
Simple to answer. The guys that wrote the paper on verification search several years ago... It is a partial solution go zugzwang. But that is a rare issue when looking at a complete game. Most often is just says one side is not _that_ far ahead and that doing something is actually significantly better than doing nothing. I think its a waste of time, based on testing, in any case.

Hint: null verification has nothing to do with zugzwangs, especially at very high depths.

You don't believe ? Ok, pick up all the positions where null search at big depth failed high and following verification failed low, print on your screen and try to find the zugzwang in them..you will be surprised you will find none (or very few).

jwes
Posts: 778
Joined: Sat Jul 01, 2006 5:11 am

Re: Extended Null-Move Reductions

Post by jwes » Fri Aug 20, 2010 7:56 pm

Milos wrote:
bob wrote:I stopped with the 2~3 a couple of years ago. But the basic idea of the paper is that rather than failing high if the null-move search returns a value >= beta, you just reduce the depth and do the normal search (reduction = 4 in this paper). That's a significant departure from null-move search and is somewhat akin to the verification search idea that I also consider to be bad... But when you said "stockfish, et. al. use this" that imples they use the basic idea presented in the paper, which nobody does that I am aware of (unless you count the somewhat similar verification search idea).
Ok my bad expression. I meant the idea of more aggressive null move reduction, not reducing depth and continuing search on fail-high which might be the main idea of the paper, but is certainly not the idea that brought them elo.

The thing with all null-move verification schemes is that zugzwangs are simply too rare in elo terms and good balance between verification search depth and reliable zugzwangs detection simply doesn't exist.
If you increase the tree just little (too high verification search depth reduction) you won't catch any zugzwangs, and will just search additionally for nothing. If you don't reduce verification search depth much, you will detect most of zugzwangs but you will pay much higher penalty elowise in bigger tree searching. Optimum doesn't exists. Or, more precisely optimum exists and is achieved for no verification search :).
A few points:
1. Zugzwangs occur frequently in K+P endings, occasionally in K+N+P endings and very rarely anywhere else.
2. Most zugzwangs are apparent after a very few ply (except maybe for K+P).
3. It would make sense to me to do verified null-move only in K+P endings (and possibly in K+N+P with a very large reduction).

bob
Posts: 20478
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Many thanks for the testing (NT) another result.

Post by bob » Sat Aug 21, 2010 1:21 am

one more bit of info. Using this approach, and allowing null-move search with pawn-only endings is worth about -100 Elo, so this is not much of a verification good news test.

bob
Posts: 20478
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Many thanks for the testing (NT) another result.

Post by bob » Sat Aug 21, 2010 2:04 am

bob wrote:one more bit of info. Using this approach, and allowing null-move search with pawn-only endings is worth about -100 Elo, so this is not much of a verification good news test.
Just realized I reported that wrong. Using R=4 and doing null-move in KP endings is a -11 Elo deal in Crafty. Going to R=5 drops it to -100, again doing this in KP endings (my normal null-move only triggers if the side on move has a single piece or more...)

Post Reply