Here is an easy one to try, and it should improve any chess engine that uses a null move search (NMS). For some time I have been playing with the problem of NMS zugzwang in the endgame. Pawn endgames are not a problem since NMS is not performed. For minor end games, it is a problem. An interesting try is to avoid a null search by including a zugswang test line:
if minors=2 and beta=0 then zugzwang=1
beta=0 helps to avoid the problems of repetition of position. minors is ideally one minor per side, but 2 minors versus no minors should not be a problem because of overwhelming odds. There should be no noticeable increase in node counts, but rather a decrease. Do not expect big overall elo results since minor two-piece endgames are rare. Schooner has shown some success, especially in hopelessly drawn opposite colored bishop endings.
Instead of using an opening book for testing, try an endgame suite test. Here is a small test suite of two-piece end games to get started with.
1r6/4kpp1/1p5p/p2pPP1P/P4P2/4K3/8/2R5 w - - 0 1
5kn1/5pp1/2p4p/pp5P/P2PPPP1/8/3NK3/8 w - - 0 1
7R/p4p1p/1p1r2p1/6k1/8/7P/PP3PP1/6K1 b - - 0 1
8/p6p/1p3kp1/5p2/PP6/2b4P/5PPB/5K2 w - - 0 1
1n2k3/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/4K1N1 w - - 0 1
4kb2/pppppppp/8/8/8/8/PPPPPPPP/4KB2 w - - 0 1
2b1k3/pppppppp/8/8/8/8/PPPPPPPP/4KB2 w - - 0 1
4k1n1/pppppppp/8/8/8/8/PPPPPPPP/4KB2 w - - 0 1
Null Move Beta=0
Moderators: hgm, Rebel, chrisw
-
- Posts: 4840
- Joined: Sun Aug 10, 2008 3:15 pm
- Location: Philippines
Re: Null Move Beta=0
In your NMS, do you use verification?D Sceviour wrote:Here is an easy one to try, and it should improve any chess engine that uses a null move search (NMS). For some time I have been playing with the problem of NMS zugzwang in the endgame. Pawn endgames are not a problem since NMS is not performed. For minor end games, it is a problem. An interesting try is to avoid a null search by including a zugswang test line:
if minors=2 and beta=0 then zugzwang=1
beta=0 helps to avoid the problems of repetition of position. minors is ideally one minor per side, but 2 minors versus no minors should not be a problem because of overwhelming odds. There should be no noticeable increase in node counts, but rather a decrease. Do not expect big overall elo results since minor two-piece endgames are rare. Schooner has shown some success, especially in hopelessly drawn opposite colored bishop endings.
Instead of using an opening book for testing, try an endgame suite test. Here is a small test suite of two-piece end games to get started with.
1r6/4kpp1/1p5p/p2pPP1P/P4P2/4K3/8/2R5 w - - 0 1
5kn1/5pp1/2p4p/pp5P/P2PPPP1/8/3NK3/8 w - - 0 1
7R/p4p1p/1p1r2p1/6k1/8/7P/PP3PP1/6K1 b - - 0 1
8/p6p/1p3kp1/5p2/PP6/2b4P/5PPB/5K2 w - - 0 1
1n2k3/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/4K1N1 w - - 0 1
4kb2/pppppppp/8/8/8/8/PPPPPPPP/4KB2 w - - 0 1
2b1k3/pppppppp/8/8/8/8/PPPPPPPP/4KB2 w - - 0 1
4k1n1/pppppppp/8/8/8/8/PPPPPPPP/4KB2 w - - 0 1
-
- Posts: 570
- Joined: Mon Jul 20, 2015 5:06 pm
Re: Null Move Beta=0
Hello Ferdy,
No. I assume you are referring to the verification search that Stockfish does at deep depths. That might make a difference.
No. I assume you are referring to the verification search that Stockfish does at deep depths. That might make a difference.
-
- Posts: 4840
- Joined: Sun Aug 10, 2008 3:15 pm
- Location: Philippines
Re: Null Move Beta=0
Something like below, if I pass (and you make a move), I would win if I do not pass I would not win.D Sceviour wrote:Hello Ferdy,
No. I assume you are referring to the verification search that Stockfish does at deep depths. That might make a difference.
Code: Select all
if eval() >= beta and not sideKingUnderAttack:
doNull()
ns = nms()
undoNull()
if ns >= beta:
vs = vnms()
# if vs is not lower than ns then we are not in zugzwang
# 8/8/8/3pK3/2kP4/8/8/8
# Trébuchet (extreme mutual zugzwang), whoever moves loses
# https://en.wikipedia.org/wiki/Zugzwang#Tr.C3.A9buchet
if vs >= ns:
return ns
-
- Posts: 570
- Joined: Mon Jul 20, 2015 5:06 pm
Re: Null Move Beta=0
The exampleFerdy wrote:Something like below, if I pass (and you make a move), I would win if I do not pass I would not win.D Sceviour wrote:Hello Ferdy,
No. I assume you are referring to the verification search that Stockfish does at deep depths. That might make a difference.Code: Select all
if eval() >= beta and not sideKingUnderAttack: doNull() ns = nms() undoNull() if ns >= beta: vs = vnms() # if vs is not lower than ns then we are not in zugzwang # 8/8/8/3pK3/2kP4/8/8/8 # Trébuchet (extreme mutual zugzwang), whoever moves loses # https://en.wikipedia.org/wiki/Zugzwang#Tr.C3.A9buchet if vs >= ns: return ns
8/8/8/3pK3/2kP4/8/8/8 w
would never be searched in NMS because NMS normally requests non-pawn material to prevent zugzwang.
However, vs = vnms() looks like a normal search that is always done after a null move hit, so it allows NMS to be done in pawn endgames (and thus all types of positions). This looks interesting.
Anyway, the use of beta=0 was intended something like this:
Code: Select all
if eval() >= beta and not sideKingUnderAttack and not zugzwang
-
- Posts: 4840
- Joined: Sun Aug 10, 2008 3:15 pm
- Location: Philippines
Re: Null Move Beta=0
True, but perhaps the verification I should can probably be applied in minor ending as in your case. I have been exploring applying null move pruning in pawn endings.D Sceviour wrote:The exampleFerdy wrote:Something like below, if I pass (and you make a move), I would win if I do not pass I would not win.D Sceviour wrote:Hello Ferdy,
No. I assume you are referring to the verification search that Stockfish does at deep depths. That might make a difference.Code: Select all
if eval() >= beta and not sideKingUnderAttack: doNull() ns = nms() undoNull() if ns >= beta: vs = vnms() # if vs is not lower than ns then we are not in zugzwang # 8/8/8/3pK3/2kP4/8/8/8 # Trébuchet (extreme mutual zugzwang), whoever moves loses # https://en.wikipedia.org/wiki/Zugzwang#Tr.C3.A9buchet if vs >= ns: return ns
8/8/8/3pK3/2kP4/8/8/8 w
would never be searched in NMS because NMS normally requests non-pawn material to prevent zugzwang.
However, vs = vnms() looks like a normal search that is always done after a null move hit, so it allows NMS to be done in pawn endgames (and thus all types of positions). This looks interesting.
Anyway, the use of beta=0 was intended something like this:
Code: Select all
if eval() >= beta and not sideKingUnderAttack and not zugzwang
-
- Posts: 1357
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
Re: Null Move Beta=0
What are the solutions for those positions?
-
- Posts: 570
- Joined: Mon Jul 20, 2015 5:06 pm
Re: Null Move Beta=0
These positions are not supposed to have a solution. They are used as a game suite test positions. It is difficult to show any strength advantage from games started from the normal root position. One use of the test suite is to play two identical engines against each other; except one of the engines will have the beta=0 modification. The modified engine should have a large plus score against the other engine.JVMerlino wrote:What are the solutions for those positions?
Not much time was spent putting together these positions. Best are positions that will quickly lock up in a zugzwang formation. The engine without beta=0 is expected to make a NMS error at some point in the game.
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: Null Move Beta=0
I do not understand the "beta == 0" condition.
I have a "zugzwang threat" pre-condition for null-moves. If either side has
1. a bare king,
2. only pawns,
3. a single knight
then the position is flagged as a "zugzwang threat" and the null-move is skipped. Possibly this should only apply to the side to move (who cares if the attacking side makes a null move?). The logic here is that a null-move represents any "quiet move that does not fundamentally alter the position". If such a move does not exist, then obviously the null-move should not be tried.
I have a "zugzwang threat" pre-condition for null-moves. If either side has
1. a bare king,
2. only pawns,
3. a single knight
then the position is flagged as a "zugzwang threat" and the null-move is skipped. Possibly this should only apply to the side to move (who cares if the attacking side makes a null move?). The logic here is that a null-move represents any "quiet move that does not fundamentally alter the position". If such a move does not exist, then obviously the null-move should not be tried.
-
- Posts: 570
- Joined: Mon Jul 20, 2015 5:06 pm
Re: Null Move Beta=0
I am not sure if I understand beta == 0 either. It showed measurable improvement in tests. At some point in a locked position, the sides are going to repeat a position and the score should be returned as null. There is danger of zugzwang if the position can repeat, and any other move loses. The explanation is empirical, and there is definitely room for better theoretical analysis. First, convince yourself this is doing something, and then try for a deeper explanation!Evert wrote:I do not understand the "beta == 0" condition.
I have a "zugzwang threat" pre-condition for null-moves. If either side has
1. a bare king,
2. only pawns,
3. a single knight
then the position is flagged as a "zugzwang threat" and the null-move is skipped. Possibly this should only apply to the side to move (who cares if the attacking side makes a null move?). The logic here is that a null-move represents any "quiet move that does not fundamentally alter the position". If such a move does not exist, then obviously the null-move should not be tried.
The single knight condition was not tested, but the principle might still be correct. A null score should be returned on repetition of position. Using beta=0 for more than two minors slowed the search.