Null Move Beta=0

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
D Sceviour
Posts: 389
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Null Move Beta=0

Post by D Sceviour » Fri Apr 28, 2017 11:38 pm

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

Ferdy
Posts: 3645
Joined: Sun Aug 10, 2008 1:15 pm
Location: Philippines

Re: Null Move Beta=0

Post by Ferdy » Fri Apr 28, 2017 11:44 pm

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
In your NMS, do you use verification?

D Sceviour
Posts: 389
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: Null Move Beta=0

Post by D Sceviour » Fri Apr 28, 2017 11:50 pm

Hello Ferdy,

No. I assume you are referring to the verification search that Stockfish does at deep depths. That might make a difference.

Ferdy
Posts: 3645
Joined: Sun Aug 10, 2008 1:15 pm
Location: Philippines

Re: Null Move Beta=0

Post by Ferdy » Sat Apr 29, 2017 12:41 am

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.
Something like below, if I pass (and you make a move), I would win if I do not pass I would not win.

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

D Sceviour
Posts: 389
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: Null Move Beta=0

Post by D Sceviour » Sat Apr 29, 2017 1:07 am

Ferdy wrote:
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.
Something like below, if I pass (and you make a move), I would win if I do not pass I would not win.

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
The example
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

Ferdy
Posts: 3645
Joined: Sun Aug 10, 2008 1:15 pm
Location: Philippines

Re: Null Move Beta=0

Post by Ferdy » Sat Apr 29, 2017 1:40 am

D Sceviour wrote:
Ferdy wrote:
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.
Something like below, if I pass (and you make a move), I would win if I do not pass I would not win.

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
The example
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.
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.
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

User avatar
JVMerlino
Posts: 979
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: Null Move Beta=0

Post by JVMerlino » Sat Apr 29, 2017 4:42 am

What are the solutions for those positions?

D Sceviour
Posts: 389
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: Null Move Beta=0

Post by D Sceviour » Sat Apr 29, 2017 10:51 am

JVMerlino wrote:What are the solutions for those positions?
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.

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.

User avatar
Evert
Posts: 2909
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Null Move Beta=0

Post by Evert » Sat Apr 29, 2017 12:11 pm

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.

D Sceviour
Posts: 389
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: Null Move Beta=0

Post by D Sceviour » Sat Apr 29, 2017 12:37 pm

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.
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!

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.

Post Reply