Null Move Beta=0

[D Sceviour]

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]

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]

Hello Ferdy,

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

[Ferdy]

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]

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]

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

[JVMerlino]

What are the solutions for those positions?

[D Sceviour]

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.

[Evert]

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]

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.