Null move as a function of mobility

[Dann Corbit]

When (for instance) you only have two possible moves it is very likely that null move pruning could get you into trouble. Even if the board is crowded, you have very little choice possible and so trimming down on the search is probably very risky, at least on the bottle neck point (if it opens up later you could start trimming aggressively again when you have many move choices).

If you have {for instance} 60 possible moves it seems to me that aggressive null move pruning is safer because you have so many possibilities, it seems likely to me that some of the possible paths will be beneficial (I suppose you might be in zugzwang with 60 legal moves, but it seems very unlikely).

So it seems to me that you could make adjustments to null move depth as a function of mobility at the null move decision point.

Has anybody tried this?

[metax]

I know about a similar experiment where the information of the 'number of potentially good alternative moves' - which was defined as the number of moves with history value > 0 IIRC - was used to adjust the cut-off value. In pseudo-code because that is easier to read:

Code: Select all

if (do_null)
{
   int cutoffValue = beta - F(number_of_potentially_good_alternatives);
   DoNull();
   value = -Search(...);
   UndoNull();

   if (value >= cutoffValue)
   {
      RecordHash(...);
      return max(value, beta);
   }
}

In other words, if there is a high number of potentially good moves, a cut-off is done even if the value of the null-move search is below beta. I do not remember F() but I think they adjusted it by a margin of 10-30cp.
The idea is that your position might be very good but still not good enough to achieve a normal null-move cutoff for positional reasons (a tempo is missing). If you have enough potentially good moves, the probability for a cut-off is high if you are only below beta by the value of a tempo, so you cut-off the search immediately even if the result of the null-move search was not above beta.

[rvida]

When (for instance) you only have two possible moves it is very likely that null move pruning could get you into trouble. Even if the board is crowded, you have very little choice possible and so trimming down on the search is probably very risky, at least on the bottle neck point (if it opens up later you could start trimming aggressively again when you have many move choices).

Has anybody tried this?

I first saw this idea in Protector. It does null move only if there are at least 6 possible moves.

if (restDepth >= 2 * DEPTH_RESOLUTION && inCheck == FALSE
&& pvNode == FALSE
&& numberOfNonPawnPieces(position, position->activeColor) >= 2
&& getNumberOfPieceMoves(position, position->activeColor, 6) >= 6)

[Dann Corbit]

When (for instance) you only have two possible moves it is very likely that null move pruning could get you into trouble. Even if the board is crowded, you have very little choice possible and so trimming down on the search is probably very risky, at least on the bottle neck point (if it opens up later you could start trimming aggressively again when you have many move choices).

Has anybody tried this?

I first saw this idea in Protector. It does null move only if there are at least 6 possible moves.

if (restDepth >= 2 * DEPTH_RESOLUTION && inCheck == FALSE
&& pvNode == FALSE
&& numberOfNonPawnPieces(position, position->activeColor) >= 2
&& getNumberOfPieceMoves(position, position->activeColor, 6) >= 6)

That is similar in that it uses the concept, but I am referring to actually changing the depth allowed as a function of possible moves available at the time of the null move.

[Uri Blass]

When (for instance) you only have two possible moves it is very likely that null move pruning could get you into trouble. Even if the board is crowded, you have very little choice possible and so trimming down on the search is probably very risky, at least on the bottle neck point (if it opens up later you could start trimming aggressively again when you have many move choices).

If you have {for instance} 60 possible moves it seems to me that aggressive null move pruning is safer because you have so many possibilities, it seems likely to me that some of the possible paths will be beneficial (I suppose you might be in zugzwang with 60 legal moves, but it seems very unlikely).

So it seems to me that you could make adjustments to null move depth as a function of mobility at the null move decision point.

Has anybody tried this?

Movei simply does not use null move pruning when the number of legal moves is small(less than 10 legal moves)

I think that it is not the optimal solution and the optimal solution is to build a zugzwang detection function that is going to tell you if there is a suspect for zugzwang.

I think that it may be interesting to know the frequency of zugzwangs in chess games and build database of zugzwang position based on games.

After doing it you can use the database to test your zugzwang detection function to see how many right zugzwangs it detects and how many wrong zugzwangs it detects.

[rvida]

That is similar in that it uses the concept, but I am referring to actually changing the depth allowed as a function of possible moves available at the time of the null move.

Although being more conservative with null move R will make you less likely to miss some tactics, it will _not_ save you from being blind in zugzwangs. In a real zugzwang position even with only R=2 reduction you will _never_ see the right move. The only cure is not doing null move at all or doing a verification search.

edit: or performing duble-null-move a la Vincent, which is in fact a form of implicit verification search.

Richard

[Dann Corbit]

That is similar in that it uses the concept, but I am referring to actually changing the depth allowed as a function of possible moves available at the time of the null move.

Although being more conservative with null move R will make you less likely to miss some tactics, it will _not_ save you from being blind in zugzwangs. In a real zugzwang position even with only R=2 reduction you will _never_ see the right move. The only cure is not doing null move at all or doing a verification search.

edit: or performing duble-null-move a la Vincent, which is in fact a form of implicit verification search.

Richard

I am not suggesting this as a replacement for a scheme like double null move.

What I am suggesting is that if we have only 2 legal moves, we do not perform null move search even if we do not detect zugzwang, or the reduction should be microscopic.
As the number of legal moves increases, we gradually increase the depth reduction we allow for null move search. When (for instance) 20 moves are possible, then perhaps the depth reduction is 2.5. If there are 40 possible moves, then perhaps the depth reduction is 3. If there are more than 60 possible moves, then perhaps the depth reduction is 4.

We would still do things like check for no pieces and double null move for safety.

[Dann Corbit]

That is similar in that it uses the concept, but I am referring to actually changing the depth allowed as a function of possible moves available at the time of the null move.

Although being more conservative with null move R will make you less likely to miss some tactics, it will _not_ save you from being blind in zugzwangs. In a real zugzwang position even with only R=2 reduction you will _never_ see the right move. The only cure is not doing null move at all or doing a verification search.

edit: or performing duble-null-move a la Vincent, which is in fact a form of implicit verification search.

Richard

I am not suggesting this as a replacement for a scheme like double null move.

What I am suggesting is that if we have only 2 legal moves, we do not perform null move search even if we do not detect zugzwang, or the reduction should be microscopic.
As the number of legal moves increases, we gradually increase the depth reduction we allow for null move search. When (for instance) 20 moves are possible, then perhaps the depth reduction is 2.5. If there are 40 possible moves, then perhaps the depth reduction is 3. If there are more than 60 possible moves, then perhaps the depth reduction is 4.

We would still do things like check for no pieces and double null move for safety.

One possible choice is something along the lines of ln(possible_moves)
[assuming that there are no zugzwangs detected, we have at least one piece, and we are using double null move] which gives:

Code: Select all

moves=1, max_reduction= 0.00
moves=2, max_reduction= 0.69
moves=3, max_reduction= 1.10
moves=4, max_reduction= 1.39
moves=5, max_reduction= 1.61
moves=6, max_reduction= 1.79
moves=7, max_reduction= 1.95
moves=8, max_reduction= 2.08
moves=9, max_reduction= 2.20
moves=10, max_reduction= 2.30
moves=11, max_reduction= 2.40
moves=12, max_reduction= 2.48
moves=13, max_reduction= 2.56
moves=14, max_reduction= 2.64
moves=15, max_reduction= 2.71
moves=16, max_reduction= 2.77
moves=17, max_reduction= 2.83
moves=18, max_reduction= 2.89
moves=19, max_reduction= 2.94
moves=20, max_reduction= 3.00
moves=21, max_reduction= 3.04
moves=22, max_reduction= 3.09
moves=23, max_reduction= 3.14
moves=24, max_reduction= 3.18
moves=25, max_reduction= 3.22
moves=26, max_reduction= 3.26
moves=27, max_reduction= 3.30
moves=28, max_reduction= 3.33
moves=29, max_reduction= 3.37
moves=30, max_reduction= 3.40
moves=31, max_reduction= 3.43
moves=32, max_reduction= 3.47
moves=33, max_reduction= 3.50
moves=34, max_reduction= 3.53
moves=35, max_reduction= 3.56
moves=36, max_reduction= 3.58
moves=37, max_reduction= 3.61
moves=38, max_reduction= 3.64
moves=39, max_reduction= 3.66
moves=40, max_reduction= 3.69
moves=41, max_reduction= 3.71
moves=42, max_reduction= 3.74
moves=43, max_reduction= 3.76
moves=44, max_reduction= 3.78
moves=45, max_reduction= 3.81
moves=46, max_reduction= 3.83
moves=47, max_reduction= 3.85
moves=48, max_reduction= 3.87
moves=49, max_reduction= 3.89
moves=50, max_reduction= 3.91
moves=51, max_reduction= 3.93
moves=52, max_reduction= 3.95
moves=53, max_reduction= 3.97
moves=54, max_reduction= 3.99
moves=55, max_reduction= 4.01
moves=56, max_reduction= 4.03
moves=57, max_reduction= 4.04
moves=58, max_reduction= 4.06
moves=59, max_reduction= 4.08
moves=60, max_reduction= 4.09
moves=61, max_reduction= 4.11
moves=62, max_reduction= 4.13
moves=63, max_reduction= 4.14
moves=64, max_reduction= 4.16
moves=65, max_reduction= 4.17
moves=66, max_reduction= 4.19
moves=67, max_reduction= 4.20
moves=68, max_reduction= 4.22
moves=69, max_reduction= 4.23
moves=70, max_reduction= 4.25
moves=71, max_reduction= 4.26
moves=72, max_reduction= 4.28
moves=73, max_reduction= 4.29
moves=74, max_reduction= 4.30
moves=75, max_reduction= 4.32
moves=76, max_reduction= 4.33
moves=77, max_reduction= 4.34
moves=78, max_reduction= 4.36
moves=79, max_reduction= 4.37
moves=80, max_reduction= 4.38
moves=81, max_reduction= 4.39
moves=82, max_reduction= 4.41
moves=83, max_reduction= 4.42
moves=84, max_reduction= 4.43
moves=85, max_reduction= 4.44
moves=86, max_reduction= 4.45
moves=87, max_reduction= 4.47
moves=88, max_reduction= 4.48
moves=89, max_reduction= 4.49
moves=90, max_reduction= 4.50
moves=91, max_reduction= 4.51
moves=92, max_reduction= 4.52
moves=93, max_reduction= 4.53
moves=94, max_reduction= 4.54
moves=95, max_reduction= 4.55
moves=96, max_reduction= 4.56
moves=97, max_reduction= 4.57
moves=98, max_reduction= 4.58
moves=99, max_reduction= 4.60
moves=100, max_reduction= 4.61
moves=101, max_reduction= 4.62
moves=102, max_reduction= 4.62
moves=103, max_reduction= 4.63
moves=104, max_reduction= 4.64
moves=105, max_reduction= 4.65
moves=106, max_reduction= 4.66
moves=107, max_reduction= 4.67
moves=108, max_reduction= 4.68
moves=109, max_reduction= 4.69
moves=110, max_reduction= 4.70
moves=111, max_reduction= 4.71
moves=112, max_reduction= 4.72
moves=113, max_reduction= 4.73
moves=114, max_reduction= 4.74
moves=115, max_reduction= 4.74
moves=116, max_reduction= 4.75
moves=117, max_reduction= 4.76
moves=118, max_reduction= 4.77
moves=119, max_reduction= 4.78
moves=120, max_reduction= 4.79
moves=121, max_reduction= 4.80
moves=122, max_reduction= 4.80
moves=123, max_reduction= 4.81
moves=124, max_reduction= 4.82
moves=125, max_reduction= 4.83
moves=126, max_reduction= 4.84
moves=127, max_reduction= 4.84
moves=128, max_reduction= 4.85
moves=129, max_reduction= 4.86
moves=130, max_reduction= 4.87
moves=131, max_reduction= 4.88
moves=132, max_reduction= 4.88
moves=133, max_reduction= 4.89
moves=134, max_reduction= 4.90
moves=135, max_reduction= 4.91
moves=136, max_reduction= 4.91
moves=137, max_reduction= 4.92
moves=138, max_reduction= 4.93
moves=139, max_reduction= 4.93
moves=140, max_reduction= 4.94
moves=141, max_reduction= 4.95
moves=142, max_reduction= 4.96
moves=143, max_reduction= 4.96
moves=144, max_reduction= 4.97
moves=145, max_reduction= 4.98
moves=146, max_reduction= 4.98
moves=147, max_reduction= 4.99
moves=148, max_reduction= 5.00
moves=149, max_reduction= 5.00
moves=150, max_reduction= 5.01
moves=151, max_reduction= 5.02
moves=152, max_reduction= 5.02
moves=153, max_reduction= 5.03
moves=154, max_reduction= 5.04
moves=155, max_reduction= 5.04
moves=156, max_reduction= 5.05
moves=157, max_reduction= 5.06
moves=158, max_reduction= 5.06
moves=159, max_reduction= 5.07
moves=160, max_reduction= 5.08
moves=161, max_reduction= 5.08
moves=162, max_reduction= 5.09
moves=163, max_reduction= 5.09
moves=164, max_reduction= 5.10
moves=165, max_reduction= 5.11
moves=166, max_reduction= 5.11
moves=167, max_reduction= 5.12
moves=168, max_reduction= 5.12
moves=169, max_reduction= 5.13
moves=170, max_reduction= 5.14
moves=171, max_reduction= 5.14
moves=172, max_reduction= 5.15
moves=173, max_reduction= 5.15
moves=174, max_reduction= 5.16
moves=175, max_reduction= 5.16
moves=176, max_reduction= 5.17
moves=177, max_reduction= 5.18
moves=178, max_reduction= 5.18
moves=179, max_reduction= 5.19
moves=180, max_reduction= 5.19
moves=181, max_reduction= 5.20
moves=182, max_reduction= 5.20
moves=183, max_reduction= 5.21
moves=184, max_reduction= 5.21
moves=185, max_reduction= 5.22
moves=186, max_reduction= 5.23
moves=187, max_reduction= 5.23
moves=188, max_reduction= 5.24
moves=189, max_reduction= 5.24
moves=190, max_reduction= 5.25
moves=191, max_reduction= 5.25
moves=192, max_reduction= 5.26
moves=193, max_reduction= 5.26
moves=194, max_reduction= 5.27
moves=195, max_reduction= 5.27
moves=196, max_reduction= 5.28
moves=197, max_reduction= 5.28
moves=198, max_reduction= 5.29
moves=199, max_reduction= 5.29
moves=200, max_reduction= 5.30
moves=201, max_reduction= 5.30
moves=202, max_reduction= 5.31
moves=203, max_reduction= 5.31
moves=204, max_reduction= 5.32
moves=205, max_reduction= 5.32
moves=206, max_reduction= 5.33
moves=207, max_reduction= 5.33
moves=208, max_reduction= 5.34
moves=209, max_reduction= 5.34
moves=210, max_reduction= 5.35
moves=211, max_reduction= 5.35
moves=212, max_reduction= 5.36
moves=213, max_reduction= 5.36
moves=214, max_reduction= 5.37
moves=215, max_reduction= 5.37
moves=216, max_reduction= 5.38
moves=217, max_reduction= 5.38
moves=218, max_reduction= 5.38
moves=219, max_reduction= 5.39
moves=220, max_reduction= 5.39
moves=221, max_reduction= 5.40
moves=222, max_reduction= 5.40
moves=223, max_reduction= 5.41
moves=224, max_reduction= 5.41
moves=225, max_reduction= 5.42
moves=226, max_reduction= 5.42
moves=227, max_reduction= 5.42
moves=228, max_reduction= 5.43
moves=229, max_reduction= 5.43
moves=230, max_reduction= 5.44
moves=231, max_reduction= 5.44
moves=232, max_reduction= 5.45
moves=233, max_reduction= 5.45
moves=234, max_reduction= 5.46
moves=235, max_reduction= 5.46
moves=236, max_reduction= 5.46
moves=237, max_reduction= 5.47
moves=238, max_reduction= 5.47
moves=239, max_reduction= 5.48
moves=240, max_reduction= 5.48
moves=241, max_reduction= 5.48
moves=242, max_reduction= 5.49
moves=243, max_reduction= 5.49
moves=244, max_reduction= 5.50
moves=245, max_reduction= 5.50
moves=246, max_reduction= 5.51
moves=247, max_reduction= 5.51
moves=248, max_reduction= 5.51
moves=249, max_reduction= 5.52

[Roman Hartmann]

I think that it is not the optimal solution and the optimal solution is to build a zugzwang detection function that is going to tell you if there is a suspect for zugzwang.

There are already at least two ways to deal with that: You can do a shallow research after a successful null move or you could use the approach proposed by Vincent Diepeveen, that is to allow two null moves in a row.

I tried both approaches and they both work in known zugzwang positions but at least in my tests they seemed to weaken the overall playing strength rather than to increase it.

Roman

[hgm]

For the purpose of tree balancing, it would be good to do something like you propse on _any_ search, not just null-move searches. Except I would use the log table that you printed not to define the reduction, but in stead the relative cost of the ply. So if there is only a single move, the cost would be zero, meaning a full ply extension (sigular extension). With 55 moves I would count it as a full ply, i.e. the table gives quarter plies. When you have only two moves, it would count 0.69 quarter plies ~0.17, equivalent to an extension of 0.83 ply.

That way you would reach more depth in critical situations, where you can easily afford it. Such as on conversion to a Pawn ending.