Slight enhancement to PVS

[Pradu]

Here's a small analysis of zero window searches and perhaps a slight enhancment to PVS as well. Here's a slightly unconventional node type classification I use for imperfectly ordered trees:

Code: Select all

OPEN Nodes
----------
The root node is an OPEN node.
All children of OPEN nodes are an OPEN nodes.
An OPEN node changes to an ALL node when alpha is raised.

ALL Nodes
---------
All children of ALL nodes are CUT nodes.
An ALL node changes an OPEN node when the scout search fails high.
(will define "scout search" later)

CUT Nodes
---------
The first child of a CUT node is an ALL node.
A CUT node changes to an ALL node when the first move fails low.

Notes:
======
Parallelism isn't good on OPEN nodes because there is too much search overhead for the current window.  It is very likely that the window will be smaller at a later time and that parallel search should wait until the window is smaller.
Parallelism isn't good on CUT nodes because there is too much search overhead because one of the moves will cutoff the search.
Parallelism is possible only on ALL nodes.

Basically from the definitions, on OPEN nodes we know that a move will at a later time will likely increase alpha. On CUT nodes we know that the first move will likely cause a cutoff. On ALL nodes it is likely that all the moves will fail low. So basically just like in PVS we can do a "scout search" that tests only for the fail high or fail low and does a research of the move as an OPEN node if it doesn't:

Code: Select all

a=alpha=lowerbound
b=beta=upperbound

On OPEN nodes search normally.
On nodes with a == b+1 search normally.

ALL Nodes:
Because ALL nodes are expected to fail low, all you need to do is prove the fail low so you can do a scout search on all moves assuming the current window is (a,a+1).  If it fails high the node type changes to OPEN and you do a research.

CUT Nodes:
You always enter a CUT node in a zero window because it always succeeds an ALL node and scout search is done for all moves in an ALL node.  And from the above conditions for zero windows, you always do a normal search on CUT nodes.

Note this is identical to PVS in every manner except in how the research is handled. For the research, if the PV doesn't increase alpha, the node remains an OPEN node. PVS assumes that it becomes an ALL node which I think is a slight inefficiency because our scout search asserts that one of the lines will increase alpha except in the case of search instability...

Code: Select all

#define OPEN_NODE 0
#define CUT_NODE  1
#define ALL_NODE  2

int childNodeType(const int previous_type)
{
   switch(previous_type)
   {
   case ALL_NODE: return CUT_NODE;
   case CUT_NODE: return ALL_NODE;
   default: return OPEN_NODE;
   }
}

int alphabeta(int depth, int alpha, int beta, int p_nodeType)
{
   int score = -MATE;
   int nodeType = childNodeType(p_nodeType);
   //Depth=0, Game decidable recognizers, Hashtables,
   //Mate-distance pruning for beta only, Nullmove, stuff...
   for( /* every move m */ )
   {
      int tempscore;
      int lowerbound = max(alpha,score);

      <makemove m>

      //a CUT_NODE always has a zero window
      if(lowerbound+1==beta || nodeType==OPEN_NODE)
         tempscore = -alphabeta(depth-1, -beta, -lowerbound, nodeType);
      else /* Node is a non-zero window ALL node */
      {
         tempscore =  -alphabeta(depth-1, -(lowerbound+1), -lowerbound, nodeType);
         if(tempscore > lowerbound && tempscore < beta)
         {
            nodeType = OPEN_NODE;
            tempscore =  -alphabeta(depth-1, -beta, -(tempscore-1), nodeType);
         }
      }

      <unmakemove m>

      if(nodeType == CUT_NODE && tempscore<beta)
         nodeType = ALL_NODE;

      if(tempscore>score)
      {
         score = tempscore;
         if(score >= beta)
            return score;
         if(score > alpha)
         {
            if(nodeType == OPEN_NODE)
               nodeType = ALL_NODE;
         }
      }
   }
   return score;
}

Quick Benchmarks on a P4 2.8 Ghz with 64MB hash:

[diag]rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w[/diag]

Code: Select all

Times are not accurate, look at node counts.
<depth> <score> <centiseconds> <nodes> <PV>

PVS
1 25 0 1 Nc3
1 59 0 9 d4
1 63 0 11 e4
1 63 0 22 e4
2 0 0 43 e4 e5
2 0 0 89 e4 e5
3 34 0 409 e4 Nf6 Nc3
3 56 0 639 d4 Nf6 e3
3 56 1 661 d4 Nf6 e3
4 -36 1 1132 d4 e6 Qd3 Qh4
4 0 1 1573 Nc3 Nc6 Nf3 Nf6
4 8 1 2040 e4 Nf6 e5 Nd5
4 8 1 2926 e4 Nf6 e5 Nd5
5 30 4 6205 e4 d5 Qf3 e6 a4
5 31 4 7883 Nc3 Nc6 e3 Nf6 Bd3
5 56 6 11704 e3 Nf6 Qf3 e5 Nc3
5 56 7 12630 e3 Nf6 Qf3 e5 Nc3
6 -6 10 20287 e3 Nc6 d4 d5 Qh5 Qd6
6 -1 18 33467 Nc3 e6 e4 Nc6 Qh5 g5
6 -1 28 52737 Nc3 e6 e4 Nc6 Qh5 g5
7 27 53 97857 Nc3 Nc6 d4 e5 dxe5 d6 Nf3
7 29 65 125602 Nf3 d5 d4 h6 Qd3 Qd6 Ne5
7 29 75 147888 Nf3 d5 d4 h6 Qd3 Qd6 Ne5
8 -6 107 207087 Nf3 d5 d4 h6 Nc3 Qd6 Ne5 g5
8 0 231 438253 d4 d5 Nc3 Nc6 h3 h6 g4 g5
8 1 293 559851 e3 Nc6 Bb5 Nf6 Qf3 e5 Nc3 d5
8 1 448 797145 e3 Nc6 Bb5 Nf6 Qf3 e5 Nc3 d5
9 11 900 1714216 e3 d5 Nf3 Nc6 Nd4 Nxd4 exd4 Qd6 Qh5
9 22 1125 2187834 Nf3 d5 d4 Nc6 Qd3 Qd6 h3 h6 Nc3
9 22 1290 2535906 Nf3 d5 d4 Nc6 Qd3 Qd6 h3 h6 Nc3
10 3 1640 3233235 Nf3 d5 d4 Nf6 Qd3 Qd6 Nc3 h6 Qb5+ c6 Qc5
10 4 1996 3958070 Nc3 Nc6 d4 d5 Bf4 f6 Nf3 g5 Bg3 h5
10 4 3867 7847359 Nc3 Nc6 d4 d5 Bf4 f6 Nf3 g5 Bg3 h5
11 19 6982 13935286 Nc3 Nc6 d4 d5 Bf4 Nf6 e3 a6 Be5 Nxe5 dxe5
11 19 7834 15791726 Nc3 Nc6 d4 d5 Bf4 Nf6 e3 a6 Be5 Nxe5 dxe5

NTS (Node-Type Search is a good name?)
1 25 0 1 Nc3
1 59 0 9 d4
1 63 0 11 e4
1 63 0 22 e4
2 0 0 45 e4 e5
2 0 0 91 e4 e5
3 34 1 416 e4 Nf6 Nc3
3 56 1 646 d4 Nf6 e3
3 56 1 668 d4 Nf6 e3
4 -36 1 1139 d4 e6 Qd3 Qh4
4 0 1 1580 Nc3 Nc6 Nf3 Nf6
4 8 1 2047 e4 Nf6 e5 Nd5
4 8 3 2933 e4 Nf6 e5 Nd5
5 30 4 6224 e4 d5 Qf3 e6 a4
5 31 4 7902 Nc3 Nc6 e3 Nf6 Bd3
5 56 7 11710 e3 Nf6 Qf3 e5 Nc3
5 56 7 12636 e3 Nf6 Qf3 e5 Nc3
6 -6 10 20292 e3 Nc6 d4 d5 Qh5 Qd6
6 -1 17 33338 Nc3 e6 e4 Nc6 Qh5 g5
6 -1 28 52613 Nc3 e6 e4 Nc6 Qh5 g5
7 27 51 97498 Nc3 Nc6 d4 e5 dxe5 d6 Nf3
7 29 64 125345 Nf3 d5 d4 h6 Qd3 Qd6 Ne5
7 29 75 147637 Nf3 d5 d4 h6 Qd3 Qd6 Ne5
8 -6 104 206687 Nf3 d5 d4 h6 Nc3 Qd6 Ne5 g5
8 0 217 438000 d4 d5 Nc3 Nc6 h3 h6 g4 g5
8 1 275 560066 e3 Nc6 Bb5 Nf6 Qf3 e5 Nc3 d5
8 1 392 797900 e3 Nc6 Bb5 Nf6 Qf3 e5 Nc3 d5
9 11 851 1721569 e3 d5 Nf3 Nc6 Nd4 Nxd4 exd4 Qd6 Qh5
9 22 1079 2197230 Nf3 d5 d4 Nc6 Qd3 Qd6 h3 h6 Nc3
9 22 1245 2544411 Nf3 d5 d4 Nc6 Qd3 Qd6 h3 h6 Nc3
10 3 1596 3239388 Nf3 d5 d4 Nf6 Qd3 Qd6 Nc3 h6 Qb5+ c6 Qc5
10 4 1957 3963162 Nc3 Nc6 d4 d5 Bf4 f6 Nf3 g5 Bg3 h5
10 4 3882 7858987 Nc3 Nc6 d4 d5 Bf4 f6 Nf3 g5 Bg3 h5
11 19 6950 13694847 Nc3 Nc6 d4 d5 Bf4 Nf6 e3 a6 Be5 Nxe5 dxe5
11 19 7800 15529047 Nc3 Nc6 d4 d5 Bf4 Nf6 e3 a6 Be5 Nxe5 dxe5

Alphabeta
1 25 0 1 Nc3
1 59 0 8 d4
1 63 0 9 e4
1 63 0 20 e4
2 0 0 41 e4 e5
2 0 0 87 e4 e5
3 34 0 309 e4 Nf6 Nc3
3 56 0 481 d4 Nf6 e3
3 56 0 503 d4 Nf6 e3
4 -36 1 876 d4 e6 Qd3 Qh4
4 8 1 1219 e4 Nf6 e5 Nd5
4 8 1 2259 e4 Nf6 e5 Nd5
5 30 3 5361 e4 d5 Qf3 e6 a4
5 31 4 6722 Nc3 Nc6 e3 Nf6 Bd3
5 56 7 12815 e3 Nf6 Qf3 e5 Nc3
5 56 7 12944 e3 Nf6 Qf3 e5 Nc3
6 -6 11 19360 e3 Nc6 d4 d5 Qh5 Qd6
6 -3 12 23287 Nc3 Nc6 Nf3 Nf6 h3 a5
6 -3 25 49879 Nc3 Nc6 Nf3 Nf6 h3 a5
7 27 46 89520 Nc3 Nc6 d4 e5 dxe5 d6 Nf3
7 29 61 120532 Nf3 d5 d4 h6 Qd3 Qd6 Ne5
7 29 70 144625 Nf3 d5 d4 h6 Qd3 Qd6 Ne5
8 -6 107 216627 Nf3 d5 d4 h6 Nc3 Qd6 Ne5 g5
8 0 181 369494 Nc3 Nc6 d4 d5 h3 h6 g4 g5
8 1 218 447072 e3 Nc6 Bb5 Nf6 Qf3 e5 Nc3 d5
8 1 473 946817 e3 Nc6 Bb5 Nf6 Qf3 e5 Nc3 d5
9 11 957 1864034 e3 d5 Nf3 Nc6 Nd4 Nxd4 exd4 Qd6 Qh5
9 24 1176 2278041 Nf3 d5 d4 Nf6 Qd3 Nc6 h3 Ne4 Bd2
9 24 1329 2614454 Nf3 d5 d4 Nf6 Qd3 Nc6 h3 Ne4 Bd2
10 4 1767 3476484 Nf3 d5 d4 Nf6 Qd3 Nc6 Nc3 Bg4 Ne5 Qd6
10 4 4796 9601553 Nf3 d5 d4 Nf6 Qd3 Nc6 Nc3 Bg4 Ne5
11 14 7217 14346966 Nf3 d5 d4 Nc6 Qd3 Qd6 a3 h6 h3 g5 g4
11 17 10100 20090312 Nc3 Nc6 d4 d5 h3 h6 a3 a6 Nf3 g5 Ne5
11 19 14156 28000545 d4 d5 Qd3 Nc6 Bd2 g6 Nf3 Nf6 Nh4 Ne4
11 19 15378 30591797 d4 d5 Qd3 Nc6 Bd2 g6 Nf3 Nf6 Nh4 Ne4

[diag]4k3/5p2/6pp/B7/P1P5/6PP/5PK1/8 w[/diag]

Code: Select all

NTS
setboard 4k3/5p2/6pp/B7/P1P5/6PP/5PK1/8 w
analyze
1 648 0 1 c5
1 664 0 3 Bc3
1 682 0 5 Bd2
1 682 0 19 Bd2
2 646 0 30 Bd2 g5
2 652 0 52 Bc3 f5
2 652 0 83 Bc3 f5
3 672 0 149 Bc3 f5 Bd2
3 679 0 265 c5 g5 Bc3
3 680 1 322 Bd2 g5 g4
3 680 1 583 Bd2 g5 g4
4 674 1 683 Bd2 g5 g4 f6
4 674 1 1324 Bd2 g5 g4 f6
5 686 1 1893 Bd2 g5 g4 f6 a5
5 686 3 6646 Bd2 g5 g4 f6 a5
6 677 3 7850 Bd2 g5 g4 Kd7 Be3 f6
6 677 4 18529 Bd2 g5 g4 Kd7 Be3 f6
7 704 7 26092 Bd2 g5 a5 Kd7 a6 Kc6 g4
7 704 15 72221 Bd2 g5 a5 Kd7 a6 Kc6 g4
8 698 18 87499 Bd2 g5 a5 Kd7 a6 Kc6 g4 f6
8 698 40 191884 Bd2 g5 a5 Kd7 a6 Kc6 g4 f6
9 701 54 265455 Bd2 g5 g4 Ke7 f4 f6 Kg3 Ke6 f5+ Kd6
9 701 117 617088 Bd2 g5 g4 Ke7 f4 f6 Kg3 Ke6 f5+ Kd6
10 711 178 942646 Bd2 h5 a5 Kd7 a6 Kc6 a7 Kb7 Be3 f6 g4
10 711 315 1699560 Bd2 h5 a5 Kd7 a6 Kc6 a7 Kb7 Be3 f6 g4
11 720 393 2130461 Bd2 h5 a5 Kd7 a6 Kc7 Be3 Kb8 Kf3 f6 Ke4
11 720 845 4647235 Bd2 h5 a5 Kd7 a6 Kc7 Be3 Kb8 Kf3 f6
12 731 1035 5609027 Bd2 h5 a5 Kd7 a6 Kc7 Be3 g5 a7 Kb7 g4 hxg4 hxg4
12 731 2801 15028430 Bd2 h5 a5 Kd7 a6 Kc7 Be3 g5 a7 Kb7 g4 hxg4 hxg4
13 739 3329 17175614 Bd2 h5 a5 Kd7 a6 Kc6 c5 f6 Bc3 f5
13 762 5332 26380133 g4 Kd7 Bd2 h5 gxh5 gxh5 Kg3 Kc6 Be3 f5 Kh4 Kb7 Kxh5
13 762 7395 37286379 g4 Kd7 Bd2 h5 gxh5 gxh5 Kg3 Kc6 Be3 f5 Kh4 Kb7
14 765 8992 45377299 g4 Kd7 Bb6 Kc6 Be3 h5 gxh5 gxh5 Kg3 Kb7 Kh4 Ka6 Bd2 f5
14 771 12326 62298321 Bb4 Kd7 Kf3 h5 a5 Kc6 Kf4 h4 g4 f5 Be7 fxg4 Kxg4 g5
14 774 13889 70426328 Bc3 Kd7 Kf3 Kc6 Kf4 h5 Bb4 Kd7 Ke5 h4 gxh4 Kd8 c5 Ke8
14 841 16159 82147663 Bd2 Kd7 Bxh6 Kc6 a5 Kb7 Bg7 Ka6 Bc3 Kb7 g4 f5 f4
14 841 19289 98335409 Bd2 Kd7 Bxh6 Kc6 a5 Kb7 Bg7 Ka6 Bc3 Kb7 g4 f5

PVS
1 648 0 1 c5
1 664 0 3 Bc3
1 682 0 5 Bd2
1 682 0 19 Bd2
2 646 0 29 Bd2 g5
2 652 0 51 Bc3 f5
2 652 0 82 Bc3 f5
3 672 0 146 Bc3 f5 Bd2
3 679 0 262 c5 g5 Bc3
3 680 0 319 Bd2 g5 g4
3 680 0 580 Bd2 g5 g4
4 674 1 677 Bd2 g5 g4 f6
4 674 1 1318 Bd2 g5 g4 f6
5 686 1 1887 Bd2 g5 g4 f6 a5
5 686 3 6640 Bd2 g5 g4 f6 a5
6 664 3 9426 Bd2 g5 f4 f6 f5 h5
6 676 6 17371 Bc3 Kf8 Bb4+ Kg7 a5 f5 Bd2
6 676 7 24735 Bc3 Kf8 Bb4+ Kg7 a5 f5 Bd2
7 684 15 62181 Bc3 Kd7 a5 Kc6 Bd4 f5 Bf6
7 704 18 75106 Bd2 g5 a5 Kd7 a6 Kc6 g4
7 704 23 101857 Bd2 g5 a5 Kd7 a6 Kc6 g4
8 698 28 120654 Bd2 g5 a5 Kd7 a6 Kc6 g4 f6
8 698 50 227055 Bd2 g5 a5 Kd7 a6 Kc6 g4 f6
9 701 65 304471 Bd2 g5 g4 Ke7 f4 f6 Kg3 Ke6 f5+ Kd6
9 701 139 704543 Bd2 g5 g4 Ke7 f4 f6 Kg3 Ke6 f5+ Kd6
10 711 190 986012 Bd2 h5 a5 Kd7 a6 Kc6 a7 Kb7 Be3 f6 g4
10 711 361 1861536 Bd2 h5 a5 Kd7 a6 Kc6 a7 Kb7 Be3 f6 g4
11 720 475 2376830 Bd2 h5 a5 Kd7 a6 Kc7 Be3 Kb8 Kf3 f6 Ke4
11 720 1056 5404921 Bd2 h5 a5 Kd7 a6 Kc7 Be3 Kb8 Kf3 f6
12 731 1232 6378347 Bd2 h5 a5 Kd7 a6 Kc7 Be3 g5 a7 Kb7 g4 hxg4 hxg4
12 731 3362 17181666 Bd2 h5 a5 Kd7 a6 Kc7 Be3 g5 a7 Kb7 g4 hxg4 hxg4
13 739 3900 20039434 Bd2 h5 a5 Kd7 a6 Kc6 c5 f6 Bc3 f5 Bf6 g5 Bxg5 Kxc5 a7 Kd6
13 762 6271 32826482 g4 Kd7 Bd2 h5 gxh5 gxh5 Kg3 Kc6 Be3 f5 Kh4
13 762 8970 47095627 g4 Kd7 Bd2 h5 gxh5 gxh5 Kg3 Kc6 Be3 f5 Kh4
14 766 11923 62486005 g4 Kd7 Kg3 Kc6 Bd2 g5 Bb4 Kd7 a5 f5 gxf5 h5 c5 Kc7 a6 Kc6 f4
14 771 19171 99330237 Bb4 Kd7 Kf3 h5 a5 Kc6 Kf4 h4 g4 f5 Be7 fxg4
14 839 23220 119908004 Bd2 Kd7 Bxh6 Kc6 a5 Kb7 Bg7 Kc6 f4 g5 f5 Kc5 Bf6 Kxc4
14 839 27703 142307559 Bd2 Kd7 Bxh6 Kc6 a5 Kb7 Bg7 Kc6 f4 g5 f5 Kc5 Bf6

Alphabeta
1 648 0 1 c5
1 664 0 2 Bc3
1 682 0 3 Bd2
1 682 0 17 Bd2
2 646 1 27 Bd2 g5
2 652 1 39 Bc3 f5
2 652 1 70 Bc3 f5
3 672 1 146 Bc3 f5 Bd2
3 679 1 195 c5 g5 Bc3
3 680 1 234 Bd2 g5 g4
3 680 1 495 Bd2 g5 g4
4 674 1 589 Bd2 g5 g4 f6
4 674 1 1237 Bd2 g5 g4 f6
5 686 3 1824 Bd2 g5 g4 f6 a5
5 686 3 8387 Bd2 g5 g4 f6 a5
6 664 4 10942 Bd2 g5 f4 f6 f5 h5
6 676 6 17331 Bc3 Kf8 Bb4+ Kg7 a5 f5 Bd2
6 676 7 25839 Bc3 Kf8 Bb4+ Kg7 a5 f5 Bd2
7 684 15 63687 Bc3 Kd7 a5 Kc6 Bd4 f5 Bf6
7 704 17 74460 Bd2 g5 a5 Kd7 a6 Kc6 g4
7 704 21 100826 Bd2 g5 a5 Kd7 a6 Kc6 g4
8 698 26 119744 Bd2 g5 a5 Kd7 a6 Kc6 g4 f6
8 698 45 223105 Bd2 g5 a5 Kd7 a6 Kc6 g4 f6
9 701 60 303715 Bd2 g5 g4 Ke7 f4 f6 f5 Kd6 Kg3
9 702 104 535850 Bb4 Kd7 a5 Kc6 Bf8 h5 Be7 Kd7 Bg5 Ke8 a6 Kd7 Bf4
9 702 137 723154 Bb4 Kd7 a5 Kc6 Bf8 h5 Be7 Kd7 Bg5 Ke8 a6 Kd7 Bf4
10 702 181 940674 Bb4 Kd7 a5 Kc6 Bf8 h5 Be7 Kd7 Bg5 Kc6 Be7
10 711 281 1441322 Bd2 h5 a5 Kd7 a6 Kc6 a7 Kb7 Be3 f6 g4
10 711 393 2024588 Bd2 h5 a5 Kd7 a6 Kc6 a7 Kb7 Be3 f6 g4
11 720 518 2691600 Bd2 h5 a5 Kd7 a6 Kc7 Be3 Kb8 Kf3 f6 Ke4
11 720 1064 5694121 Bd2 h5 a5 Kd7 a6 Kc7 Be3 Kb8 Kf3 f6
12 731 1357 7179708 Bd2 h5 a5 Kd7 a6 Kc7 Be3 g5 a7 Kb7 g4 hxg4 hxg4
12 757 2192 11767144 g4 Kd7 Bd2 g5 Bb4 f6 Bf8 h5 gxh5 Ke6 Kg3 f5 a5
12 757 3112 16508879 g4 Kd7 Bd2 g5 Bb4 f6 Bf8 h5 gxh5 Ke6 Kg3 f5 a5
13 762 4248 22764970 g4 Kd7 Bd2 h5 gxh5 gxh5 Kg3 Kc6 Be3 f5 Kh4 Kb7
13 762 8612 45821565 g4 Kd7 Bd2 h5 gxh5 gxh5 Kg3 Kc6 Be3 f5 Kh4
14 770 13832 71837921 g4 Kd7 Kg3 Kc6 Bd2 g5 Bb4 Kb7 a5 f5 gxf5 h5 f4
14 781 22021 111562629 Bb4 Kd7 Kf3 f5 Kf4 Ke6 h4 Kf6 Bc3+ Ke6 Bg7 Kd6 Bxh6
14 845 26145 132369211 Bd2 Kd7 Bxh6 Kc6 a5 Kb7 c5 f6 Bg7 f5 f4 Ka6
14 845 31943 160266360 Bd2 Kd7 Bxh6 Kc6 a5 Kb7 c5 f6 Bg7 f5 f4 Ka6

[diag]R3r1k1/2qb1pbn/1n1p2p1/2pP3p/1p2P3/7P/1P2NPB1/1QBNR1K1 b[/diag]

Code: Select all

Alphabeta
setboard R3r1k1/2qb1pbn/1n1p2p1/2pP3p/1p2P3/7P/1P2NPB1/1QBNR1K1 b
analyze
1 218 0 1 Nxa8
1 241 0 2 Rxa8
1 241 0 43 Rxa8
2 211 0 82 Rxa8 Bf4
2 211 0 346 Rxa8 Bf4
3 234 0 544 Rxa8 f4 h4
3 234 0 1100 Rxa8 f4 h4
4 212 1 1539 Rxa8 f4 h4 f5
4 212 3 4233 Rxa8 f4 h4 f5
5 224 6 10129 Rxa8 f4 f5 Ne3 fxe4
5 224 7 14694 Rxa8 f4 f5 Ne3 fxe4
6 224 14 27143 Rxa8 f4 f5 Ne3 fxe4 Bxe4
6 224 20 43902 Rxa8 f4 f5 Ne3 fxe4 Bxe4
7 223 60 134889 Rxa8 f4 Qb7 Nf2 f5 b3 fxe4
7 223 64 140009 Rxa8 f4 Qb7 Nf2 f5 b3 fxe4
8 220 184 402680 Rxa8 f4 Qc8 Qd3 f5 Ne3 fxe4 Bxe4
8 220 207 460115 Rxa8 f4 Qc8 Qd3 f5 Ne3 fxe4 Bxe4
9 221 900 2015121 Rxa8 b3 h4 Nb2 Kh8 Qd3 f5 Nc4 Nxc4
9 221 940 2096937 Rxa8 b3 h4 Nb2 Kh8 Qd3 f5 Nc4 Nxc4
10 212 3046 6615608 Rxa8 b3 Qc8 Qd3 h4 Nb2 f5 Nc4 Nxc4 bxc4
10 212 3614 7906203 Rxa8 b3 Qc8 Qd3 h4 Nb2 f5 Nc4 Nxc4 bxc4
11 222 8379 18499881 Rxa8 b3 Qc8 Qd3 h4 Nb2 Qa6 Qxa6 Rxa6 Nc4 Nxc4
11 222 8678 19242666 Rxa8 b3 Qc8 Qd3 h4 Nb2 Qa6 Qxa6 Rxa6 Nc4 Nxc4

PVS
1 218 0 1 Nxa8
1 241 0 3 Rxa8
1 241 0 44 Rxa8
2 211 0 83 Rxa8 Bf4
2 211 1 335 Rxa8 Bf4
3 234 1 585 Rxa8 f4 h4
3 234 1 1141 Rxa8 f4 h4
4 212 1 1577 Rxa8 f4 h4 f5
4 212 3 4277 Rxa8 f4 h4 f5
5 224 6 9365 Rxa8 f4 f5 Ne3 fxe4
5 224 7 13643 Rxa8 f4 f5 Ne3 fxe4
6 224 14 25073 Rxa8 f4 f5 Ne3 fxe4 Bxe4
6 224 20 41789 Rxa8 f4 f5 Ne3 fxe4 Bxe4
7 223 57 127093 Rxa8 f4 Qb7 Nf2 f5 b3 fxe4
7 223 59 132156 Rxa8 f4 Qb7 Nf2 f5 b3 fxe4
8 220 228 498563 Rxa8 f4 Qc8 Qd3 f5 Ne3 fxe4 Bxe4
8 220 257 571305 Rxa8 f4 Qc8 Qd3 f5 Ne3 fxe4 Bxe4
9 221 665 1520852 Rxa8 b3 h4 Nb2 Kh8 Qd3 f5 Nc4 Nxc4
9 221 706 1603847 Rxa8 b3 h4 Nb2 Kh8 Qd3 f5 Nc4 Nxc4
10 212 2125 4645561 Rxa8 b3 Qc8 Qd3 h4 Nb2 f5 Nc4 Nxc4 bxc4
10 212 2500 5530674 Rxa8 b3 Qc8 Qd3 h4 Nb2 f5 Nc4 Nxc4 bxc4
11 222 4687 10372117 Rxa8 b3 Qc8 Qd3 h4 Nb2 Qa6 Qxa6 Rxa6 Nc4 Nxc4
11 222 5001 11128855 Rxa8 b3 Qc8 Qd3 h4 Nb2 Qa6 Qxa6 Rxa6 Nc4 Nxc4

NTS
1 218 0 1 Nxa8
1 241 0 3 Rxa8
1 241 0 44 Rxa8
2 211 0 85 Rxa8 Bf4
2 211 0 337 Rxa8 Bf4
3 234 0 594 Rxa8 f4 h4
3 234 1 1150 Rxa8 f4 h4
4 212 1 1586 Rxa8 f4 h4 f5
4 212 3 4286 Rxa8 f4 h4 f5
5 224 6 9386 Rxa8 f4 f5 Ne3 fxe4
5 224 7 13664 Rxa8 f4 f5 Ne3 fxe4
6 224 14 25094 Rxa8 f4 f5 Ne3 fxe4 Bxe4
6 224 20 41810 Rxa8 f4 f5 Ne3 fxe4 Bxe4
7 223 57 127219 Rxa8 f4 Qb7 Nf2 f5 b3 fxe4
7 223 60 132282 Rxa8 f4 Qb7 Nf2 f5 b3 fxe4
8 220 242 523875 Rxa8 f4 Qc8 Qd3 f5 Ne3 fxe4 Bxe4
8 220 271 594691 Rxa8 f4 Qc8 Qd3 f5 Ne3 fxe4 Bxe4
9 221 732 1652084 Rxa8 b3 h4 Nb2 Kh8 Qd3 f5 Nc4 Nxc4
9 221 773 1734585 Rxa8 b3 h4 Nb2 Kh8 Qd3 f5 Nc4 Nxc4
10 212 2187 4734066 Rxa8 b3 Qc8 Qd3 h4 Nb2 f5 Nc4 Nxc4 bxc4
10 212 2501 5476958 Rxa8 b3 Qc8 Qd3 h4 Nb2 f5 Nc4 Nxc4 bxc4
11 222 4709 10292837 Rxa8 b3 Qc8 Qd3 h4 Nb2 Qa6 Qxa6 Rxa6 Nc4 Nxc4
11 222 5004 11055657 Rxa8 b3 Qc8 Qd3 h4 Nb2 Qa6 Qxa6 Rxa6 Nc4 Nxc4

My implementations:

• NTS search.c source
• AB and PVS search.c source (search type modified by a define)

[Edsel Apostol]

Hi Pradu,

I am interested in your idea. Have you tried it in real games? How does it fair against PVS and the modified PVS that is implemented in Fruit?

Edsel Apostol (Twisted Logic)

[Pradu]

Hi Pradu,

I am interested in your idea. Have you tried it in real games? How does it fair against PVS and the modified PVS that is implemented in Fruit?

Edsel Apostol (Twisted Logic)

I have tried it in 64RR 1 minute, 1 second increment games on a 2.8 Ghz P4 and PVS, AB, and NTS are all rather equal. Perhaps long TC, high speed 64-bit computer tests (Gives Buzz +2-3 ply) are needed for PVS and NTS to be effective. I'm not aware about what Fruit does for its search. Search-wise, I think PVS and NTS are atleast equal. Also with NTS you have the node type so it will be easier to find good split points for a parallel search. Because the node type also gets updated depending on the scout search, perhaps you can use the information about the changes in the node type improve the parallel search as well. Not quit sure on that but just an idea. I think search instability also matters. If your search is relatively unstable (relatively frequent fail low on an open window after a fail high on a scout search) then it might be better to use PVS. If your search is relatively stable then NTS is probably better. Actually, for an unstable search, it might help to modify NTS to change OPEN nodes to ALPHA nodes whenever a score gets back instead of updating only when the score improves alpha. Here's a modified NTS for a relatively unstable search:

Code: Select all

UNSTABLE NTS

#define OPEN_NODE 0
#define CUT_NODE  1
#define ALL_NODE  2

int childNodeType(const int previous_type)
{
   switch(previous_type)
   {
   case ALL_NODE: return CUT_NODE;
   case CUT_NODE: return ALL_NODE;
   default: return OPEN_NODE;
   }
}

int alphabeta(int depth, int alpha, int beta, int p_nodeType)
{
   int score = -MATE;
   int nodeType = childNodeType(p_nodeType);
   //Depth=0, Game decidable recognizers, Hashtables,
   //Mate-distance pruning for beta only, Nullmove, stuff...
   for( /* every move m */ )
   {
      int tempscore;
      int lowerbound = max(alpha,score);

      <makemove m>

      //a CUT_NODE always has a zero window
      if(lowerbound+1==beta || nodeType==OPEN_NODE)
         tempscore = -alphabeta(depth-1, -beta, -lowerbound, nodeType);
      else /* Node is a non-zero window ALL node */
      {
         tempscore =  -alphabeta(depth-1, -(lowerbound+1), -lowerbound, nodeType);
         if(tempscore > lowerbound && tempscore < beta)
         {
            nodeType = OPEN_NODE;
            tempscore =  -alphabeta(depth-1, -beta, -(tempscore-1), nodeType);
         }
      }

      <unmakemove m>

      if(nodeType == OPEN_NODE || (nodeType == CUT_NODE && tempscore<beta))
         nodeType = ALL_NODE;

      if(tempscore>score)
      {
         score = tempscore;
         if(score >= beta)
            return score;
      }
   }
   return score;
}

EDIT: Just did a quick experiment on initial position, unstable NTS works much better for Buzz here than everything else....

Code: Select all

Times are off I had stuff running in the background, look at nodes:
10 4 5506 7439501 Nc3 Nc6 d4 d5 Bf4 f6 Nf3 g5 Bg3 h5 (Unstable NTS)
10 4 5728 7858987 Nc3 Nc6 d4 d5 Bf4 f6 Nf3 g5 Bg3 h5 (Stable NTS)
10 4 5707 7847359 Nc3 Nc6 d4 d5 Bf4 f6 Nf3 g5 Bg3 h5 (PVS)
10 4 7085 9601553 Nf3 d5 d4 Nf6 Qd3 Nc6 Nc3 Bg4 Ne5  (AB)


Code: Select all

Search Test
PRADU-BUZZ, 2007.06.11 - 2007.06.12
 1: Buzz PVS  65.5 / 128   
 2: Buzz NTS  64.0 / 128   (Stable NTS)
 3: Buzz AB   62.5 / 128

1:
-------------------------------------------------------------------------------------------------
Buzz PVS   ==010=11000110011==1=00=====0=1=1=1101==0==1===1101010=11==01001 34.0 / 64   Buzz AB 
-------------------------------------------------------------------------------------------------

2:
-------------------------------------------------------------------------------------------------
Buzz AB    1=0=0=00=0=1001=1=01=1010=10=1=1=10=11==00=011111=1=100===100=0= 32.5 / 64   Buzz NTS
-------------------------------------------------------------------------------------------------

3:
-------------------------------------------------------------------------------------------------
Buzz NTS   =10110=00=1===1=11010101=0=001=1=1100==001110=00100010====1==11= 32.5 / 64   Buzz PVS
-------------------------------------------------------------------------------------------------

192 games: +66 =68 -58

[Onno Garms]

Hi Pradu,

How does it fair against PVS and the modified PVS that is implemented in Fruit?

What modification (in Fruit over normal PVS) have you in your mind?

[Pradu]

The unstable NTS seems to outperform both PVS and stable NTS for Buzz. It's rather suprising to me that search instabiliy isn't negligable for a real chess search. Here are some node type prediction rates for unstable NTS:

Code: Select all

4k3/5p2/6pp/B7/P1P5/6PP/5PK1/8 w
1 682 0 19 [ext=0.00% hh=0.0% cut=0.00% CUTpred=100.00% q/n=0%] Bd2
2 652 0 83 [ext=0.00% hh=1.3% cut=18.99% CUTpred=96.30% ALLpred=87.50% q/n=5%] Bc3 f5
3 680 1 583 [ext=0.88% hh=6.5% cut=11.44% CUTpred=97.33% ALLpred=87.50% q/n=3%]Bd2 g5 g4
4 674 1 1309 [bf=1.00 ext=0.53% hh=15.0% cut=32.78% CUTpred=96.29% ALLpred=96.31% q/n=13%] Bd2 g5 g4 f6
5 686 3 6600 [bf=1.94 ext=1.56% hh=8.9% cut=16.91% CUTpred=98.27% ALLpred=98.76% q/n=5%] Bd2 g5 g4 f6 a5
6 677 6 18264 [bf=2.03 ext=1.88% hh=19.6% cut=35.46% CUTpred=96.49% ALLpred=99.66% q/n=13%] Bd2 g5 g4 Kd7 Be3 f6
7 704 15 71593 [bf=2.48 ext=1.76% hh=14.4% cut=22.15% CUTpred=98.20% ALLpred=99.68% q/n=8%] Bd2 g5 a5 Kd7 a6 Kc6 g4
8 698 42 188821 [bf=2.71 ext=1.83% hh=21.7% cut=37.12% CUTpred=96.72% ALLpred=99.91% q/n=16%] Bd2 g5 a5 Kd7 a6 Kc6 g4 f6
9 701 123 611174 [bf=2.92 ext=1.83% hh=18.7% cut=26.52% CUTpred=98.07% ALLpred=99.91% q/n=10%] Bd2 g5 g4 Ke7 f4 f6 Kg3 Kd6 f5
10 711 329 1669620 [bf=2.67 ext=1.95% hh=27.9% cut=40.42% CUTpred=97.47% ALLpred=99.94% q/n=14%] Bd2 h5 a5 Kd7 a6 Kc6 a7 Kb7 Be3 f6 g4
11 720 887 4608870 [bf=2.69 ext=2.15% hh=25.6% cut=33.72% CUTpred=98.15% ALLpred=99.97% q/n=11%] Bd2 h5 a5 Kd7 a6 Kc7 Be3 Kb8 Kf3 f6
12 731 2760 14193897 [bf=3.11 ext=2.54% hh=29.2% cut=41.64% CUTpred=97.63% ALLpred=99.98% q/n=13%] Bd2 h5 a5 Kd7 a6 Kc7 Be3 g5 a7 Kb7 g4 hxg4 hxg4
13 762 6190 32140909 [bf=2.24 ext=2.70% hh=28.2% cut=39.38% CUTpred=97.88% ALLpred=99.99% q/n=11%] g4 Kd7 Bd2 h5 gxh5 gxh5 Kg3 Kc6 Be3 f5 Kh4
14 781 20478 103054839 [bf=3.31 ext=3.22% hh=24.6% cut=40.62% CUTpred=97.03% ALLpred=99.99% q/n=14%] Bd2 g5 a5 Kd7 Kf3 f5 h4 gxh4 gxh4 Kc6 Kf4

Initial Position
1 63 0 22 [ext=0.00% hh=0.0% cut=0.00% CUTpred=100.00% q/n=0%] e4
2 0 0 91 [ext=0.00% hh=0.0% cut=20.88% CUTpred=96.92% ALLpred=89.47% q/n=0%] e4e5
3 56 0 668 [ext=0.85% hh=7.8% cut=15.96% CUTpred=95.56% ALLpred=83.72% q/n=12%]d4 Nf6 e3
4 8 1 2856 [ext=0.51% hh=9.6% cut=29.03% CUTpred=96.61% ALLpred=96.18% q/n=10%]e4 Nf6 e5 Nd5
5 56 6 12297 [bf=3.94 ext=1.52% hh=15.2% cut=33.30% CUTpred=95.83% ALLpred=98.50% q/n=12%] e3 Nf6 Qf3 e5 Nc3
6 -3 25 47310 [bf=3.97 ext=1.35% hh=16.2% cut=39.82% CUTpred=96.77% ALLpred=99.47% q/n=15%] Nc3 Nf6 Nf3 Nc6 a3 h5
7 29 67 133972 [bf=2.69 ext=1.22% hh=15.2% cut=36.14% CUTpred=97.09% ALLpred=99.70% q/n=15%] Nf3 d5 d4 h6 Qd3 Qd6 Ne5
8 1 376 738983 [bf=5.60 ext=1.65% hh=11.4% cut=33.96% CUTpred=97.60% ALLpred=99.92% q/n=18%] e3 Nc6 Bb5 Nf6 Qf3 e5 Nc3 d5
9 24 1071 2160059 [bf=2.85 ext=1.67% hh=11.7% cut=31.01% CUTpred=97.75% ALLpred=99.93% q/n=18%] Nf3 d5 d4 Nf6 Qd3 Nc6 h3 Ne4 Bd2
10 4 3990 8006983 [bf=3.72 ext=1.71% hh=10.2% cut=30.02% CUTpred=98.13% ALLpred=99.98% q/n=19%] Nc3 Nc6 d4 d5 Bf4 f6 Nf3 g5 Bg3
11 19 8528 16635680 [bf=2.14 ext=1.70% hh=8.8% cut=28.31% CUTpred=98.09% ALLpred=99.99% q/n=21%] Nc3 Nc6 d4 d5 Bf4 Nf6 e3 a6 Be5 Nxe5 dxe5

Node type prediction rates seem to be very high around 97%-98% so they can be used safely for parallel search. Hopefully I'll get some processor time to run long TC tests to see if NTS offers any advantage over PVS or AB for playing strength in real games.

EDIT: My mistake ... the above measurements included nodes which arn't searched like depthLeft=0 nodes or hashtable cutoff nodes. Without taking nodes that we don't search into consideration the prediction rate is actually much lower--around 88-97% for CUT node prediction depending on the position. A CUT node is assumed to be predicted correctly if the first move fails high, otherwise it is assumed that the CUT node is predicted incorrectly even if it fails high for a later move. Nevertheless I think this is still sufficiently good for parallel search and the prediction rate will probably be better if the moveordering/eval is better than what I have in Buzz.

Code: Select all

Initial Position:
1 63 0 22 [ext=0.00% hh=0.0% cut=0.00% q/n=0%] e4
2 0 0 91 [ext=0.00% hh=0.0% cut=20.88% CUTpred=89.47% q/n=0%] e4 e5
3 56 0 668 [ext=0.85% hh=7.8% cut=15.96% CUTpred=75.29% q/n=12%] d4 Nf6 e3
4 8 1 2856 [ext=0.51% hh=9.6% cut=29.03% CUTpred=89.86% q/n=10%] e4 Nf6 e5 Nd5
5 56 6 12297 [bf=3.94 ext=1.52% hh=15.2% cut=33.30% CUTpred=87.86% q/n=12%] e3 Nf6 Qf3 e5 Nc3
6 -3 26 47310 [bf=4.22 ext=1.35% hh=16.2% cut=39.82% CUTpred=91.90% q/n=15%] Nc3 Nf6 Nf3 Nc6 a3 h5
7 29 78 133972 [bf=2.94 ext=1.22% hh=15.2% cut=36.14% CUTpred=91.97% q/n=15%] Nf3 d5 d4 h6 Qd3 Qd6 Ne5
8 1 410 738983 [bf=5.26 ext=1.65% hh=11.4% cut=33.96% CUTpred=92.98% q/n=18%] e3 Nc6 Bb5 Nf6 Qf3 e5 Nc3 d5
9 24 1160 2160059 [bf=2.83 ext=1.67% hh=11.7% cut=31.01% CUTpred=92.54% q/n=18%] Nf3 d5 d4 Nf6 Qd3 Nc6 h3 Ne4 Bd2
10 4 4332 8006983 [bf=3.73 ext=1.71% hh=10.2% cut=30.02% CUTpred=93.47% q/n=19%] Nc3 Nc6 d4 d5 Bf4 f6 Nf3 g5 Bg3
11 19 8889 16635680 [bf=2.05 ext=1.70% hh=8.8% cut=28.31% CUTpred=93.12% q/n=21%] Nc3 Nc6 d4 d5 Bf4 Nf6 e3 a6 Be5 Nxe5 dxe5

setboard 4k3/5p2/6pp/B7/P1P5/6PP/5PK1/8 w
analyze
1 682 0 19 [ext=0.00% hh=0.0% cut=0.00% q/n=0%] Bd2
2 652 0 83 [ext=0.00% hh=1.3% cut=18.99% CUTpred=87.50% q/n=5%] Bc3 f5
3 680 1 583 [ext=0.88% hh=6.5% cut=11.44% CUTpred=76.79% q/n=3%] Bd2 g5 g4
4 674 1 1309 [bf=1.00 ext=0.53% hh=15.0% cut=32.78% CUTpred=88.52% q/n=13%] Bd2g5 g4 f6
5 686 3 6600 [bf=2.00 ext=1.56% hh=8.9% cut=16.91% CUTpred=88.12% q/n=5%] Bd2 g5 g4 f6 a5
6 677 6 18264 [bf=1.97 ext=1.88% hh=19.6% cut=35.46% CUTpred=87.38% q/n=13%] Bd2 g5 g4 Kd7 Be3 f6
7 704 17 71593 [bf=2.73 ext=1.76% hh=14.4% cut=22.15% CUTpred=88.08% q/n=8%] Bd2 g5 a5 Kd7 a6 Kc6 g4
8 698 40 188821 [bf=2.37 ext=1.83% hh=21.7% cut=37.12% CUTpred=87.68% q/n=16%] Bd2 g5 a5 Kd7 a6 Kc6 g4 f6
9 701 120 611174 [bf=2.96 ext=1.83% hh=18.7% cut=26.52% CUTpred=88.05% q/n=10%]Bd2 g5 g4 Ke7 f4 f6 Kg3 Kd6 f5
10 711 323 1669620 [bf=2.69 ext=1.95% hh=27.9% cut=40.42% CUTpred=89.36% q/n=14%] Bd2 h5 a5 Kd7 a6 Kc6 a7 Kb7 Be3 f6 g4
11 720 871 4608870 [bf=2.70 ext=2.15% hh=25.6% cut=33.72% CUTpred=89.39% q/n=11%] Bd2 h5 a5 Kd7 a6 Kc7 Be3 Kb8 Kf3 f6
12 731 2856 14193897 [bf=3.28 ext=2.54% hh=29.2% cut=41.64% CUTpred=89.35% q/n=13%] Bd2 h5 a5 Kd7 a6 Kc7 Be3 g5 a7 Kb7 g4 hxg4 hxg4
13 762 6501 32140909 [bf=2.28 ext=2.70% hh=28.2% cut=39.38% CUTpred=89.35% q/n=11%] g4 Kd7 Bd2 h5 gxh5 gxh5 Kg3 Kc6 Be3 f5 Kh4

EDIT again:
The previous values were with an experiment where nullmove pruning is not done on ALL nodes which seems to slow down search... Here are the values when you do nullmove pruning on ALL nodes as well:

Code: Select all

Initial Position:
1 63 0 22 [ext=0.00% hh=0.0% cut=0.00% q/n=0%] e4
2 0 1 91 [ext=0.00% hh=0.0% cut=20.88% CUTpred=89.47% q/n=0%] e4 e5
3 56 1 668 [bf=1.00 ext=0.85% hh=7.8% cut=15.96% CUTpred=75.29% q/n=12%] d4 Nf6 e3
4 8 3 2933 [bf=2.07 ext=0.49% hh=10.0% cut=29.65% CUTpred=90.30% q/n=10%] e4 Nf6 e5 Nd5
5 56 12 12649 [bf=2.72 ext=1.45% hh=15.3% cut=33.73% CUTpred=89.04% q/n=12%] e3 Nf6 Qf3 e5 Nc3
6 -1 42 48307 [bf=3.37 ext=1.23% hh=16.1% cut=39.83% CUTpred=91.55% q/n=15%] Nc3 e6 e4 Nc6 Qh5 g5
7 29 117 140636 [bf=2.78 ext=1.21% hh=15.0% cut=36.57% CUTpred=91.31% q/n=16%] Nf3 d5 d4 h6 Qd3 Qd6 Ne5
8 1 442 760731 [bf=3.78 ext=1.57% hh=13.1% cut=34.81% CUTpred=92.96% q/n=17%] e3 Nc6 Bb5 Nf6 Qf3 e5 Nc3 d5
9 24 1298 2517688 [bf=2.94 ext=1.68% hh=13.5% cut=32.16% CUTpred=92.68% q/n=18%] Nf3 d5 d4 Nf6 Qd3 Nc6 h3 Ne4 Bd2
10 4 3840 7439501 [bf=2.96 ext=1.61% hh=11.6% cut=30.80% CUTpred=93.69% q/n=19%] Nc3 Nc6 d4 d5 Bf4 f6 Nf3 g5 Bg3 h5

rnr3k1/pp1qppbp/5np1/3p4/2PNP3/1PN2P2/P5PP/R1BQ1RK1 w - - 0 2
1 98 0 54 [ext=0.00% hh=2.4% cut=0.00% q/n=24%] Nxd5
2 98 1 401 [ext=0.00% hh=3.1% cut=21.13% CUTpred=92.31% q/n=52%] Nxd5 Nxd5
3 136 1 2040 [bf=1.00 ext=0.24% hh=11.5% cut=16.21% CUTpred=77.70% q/n=40%] exd5 a5 Ncb5
4 116 6 8570 [bf=3.94 ext=2.27% hh=10.8% cut=24.12% CUTpred=93.85% q/n=33%] exd5 Na6 Ncb5 Nc5
5 66 28 53745 [bf=4.48 ext=0.97% hh=10.8% cut=24.95% CUTpred=90.95% q/n=46%] exd5 Nxd5 Nxd5 e6 Ne7+ Qxe7
6 64 70 150177 [bf=2.50 ext=1.21% hh=9.2% cut=20.87% CUTpred=93.94% q/n=34%] exd5 Nxd5 Nxd5 e6 Ne7+ Qxe7 a3
7 49 134 308783 [bf=1.91 ext=1.32% hh=11.4% cut=20.05% CUTpred=95.25% q/n=38%] exd5 Nxd5 Nxd5 e6 Bg5 exd5 cxd5
8 49 309 721472 [bf=2.31 ext=1.51% hh=10.9% cut=19.80% CUTpred=96.22% q/n=31%] exd5 Nxd5 Nxd5 e6 Bg5 exd5 cxd5 Qxd5
9 35 600 1397413 [bf=1.93 ext=1.87% hh=13.5% cut=23.63% CUTpred=96.24% q/n=33%]exd5 Nxd5 Nxd5 e6 Qd3 exd5 cxd5 Rc5 d6
10 32 1745 3700670 [bf=2.91 ext=1.85% hh=12.3% cut=22.16% CUTpred=96.48% q/n=32%] exd5 Nxd5 Nxd5 e6 Bh6 exd5 Bxg7 Kxg7 cxd5 Qxd5
11 16 4715 9767141 [bf=2.70 ext=2.03% hh=13.1% cut=23.97% CUTpred=96.08% q/n=34%] exd5 Nxd5 Nxd5 e6 Be3 exd5 Rc1 dxc4 Rxc4 Rxc4 bxc4
12 19 10112 21906711 [bf=2.14 ext=1.92% hh=12.4% cut=22.65% CUTpred=96.40% q/n=32%] exd5 Nxd5 Nxd5 e6 Bh6 exd5 Bxg7 Kxg7 cxd5 Qxd5 Qd2 Nc6


Prediction rates are about the same with or without nullmove on ALL nodes.

[Onno Garms]

Hi Pradu,

You have to do node counts on at least hundreds (better thousands) of searches. When I tried to figure out whether to do null move searches on ALL nodes or not, I observed large differences in the node count in some searches, but sometimes it was better with NMP and sometimes without. The same might hold when you compare NTS and PVS.

[Onno Garms]

Hi pradu,

Note this is identical to PVS in every manner except in how the research is handled. For the research, if the PV doesn't increase alpha, the node remains an OPEN node. PVS assumes that it becomes an ALL node which I think is a slight inefficiency because our scout search asserts that one of the lines will increase alpha except in the case of search instability...

If your search is relatively unstable (relatively frequent fail low on an open window after a fail high on a scout search) then it might be better to use PVS. If your search is relatively stable then NTS is probably better. Actually, for an unstable search, it might help to modify NTS to change OPEN nodes to ALPHA nodes whenever a score gets back instead of updating only when the score improves alpha. Here's a modified NTS for a relatively unstable search:

The second statement seems to say that the modification for instable search eliminates the only thing that is different in NTS from PVS. So what difference is remaining beween instable NTS and PVS?

Also note that the on an OPEN node where the first move did not increase alpha you do know that some move will increase alpha (if the search is stable), but you do not know which one. While the first move had a relatively high propability to do so, the propability for each individual of the following moves is much lower. So it might be good to do a scout search on them. Overall, search instability is not the only reason why instable NTS might be better then stable NTS.

[Edsel Apostol]

Hi Onno,

If you can see in the Fruit search, it has a slight modification from the regular PVS in order to make the search more stable.

This is the pseudocode:

Code: Select all

/* this is Fruit PVS */
if(first_move or beta == alpha + 1){
    score = -search(pos, -beta, -alpha, new_depth);
}else{
    score = -search(pos, -alpha-1, -alpha, new_depth);
    if(score > alpha)
        score = -search(pos, -beta -alpha, new_depth);
}


Notice that Fruit do a research every time the score is greater than alpha. In normal PVS, you only do a research if the score is in between alpha and beta.

Edsel Apostol (Twisted Logic)

[Onno Garms]

Notice that Fruit do a research every time the score is greater than alpha. In normal PVS, you only do a research if the score is in between alpha and beta.

I see, thank you.

Have you also compared these two techniques, e.g. my modifying the fruit sources or trying both in your engine? Which one performs better?

[Edsel Apostol]

Hi Onno,

If you can see in the Fruit search, it has a slight modification from the regular PVS in order to make the search more stable.

This is the pseudocode:

Code: Select all

/* this is Fruit PVS */
if(first_move or beta == alpha + 1){
    score = -search(pos, -beta, -alpha, new_depth);
}else{
    score = -search(pos, -alpha-1, -alpha, new_depth);
    if(score > alpha)
        score = -search(pos, -beta -alpha, new_depth);
}


Notice that Fruit do a research every time the score is greater than alpha. In normal PVS, you only do a research if the score is in between alpha and beta.

Edsel Apostol (Twisted Logic)

Notice also that the parameter for the research is "alpha and beta", and not "beta and score + 1".

I think that this is much stable than the regular PVS.

Pradu would you mind trying this in your engine BUZZ so that we could compare its performance over your NTS and the regular PVS.

One more thing, if you test them, don't play them against each other, maybe you could try playing a gauntlet match from a single opponent, and use the same set of positions, maybe Noomen Testsuite 2006 or Nunn positions. If you really want an extensive test then you could add more opponents and play each opponent a gauntlet match against the different versions.

Edsel Apostol (Twisted Logic)

[Edsel Apostol]

I have tried all variations of search before in my program and I found out that this search version is the most stable, I mean the principal variation didn't change much from lower depths to greater depths. For example, when it find a best move in depth 1, it still is the best move in depth 12 and above. Unlike other versions that are very unstable that when you change the time allocated for search, the move it would play will have a high outcome to change.

I have not tested this much though, it was way before since I tried these variations of search. That time my program is still weak, and my programming experience and skills is limited.

There are a lot of variations to PVS. Here is the version by Bruce Moreland: http://www.brucemo.com/compchess/programming/pvs.htm
I think I have tried it before and it isn't as efficient as what Fruit is doing, but that was way before. I will try to experiment with search again one of this days.

[Pradu]

Hi pradu,

The second statement seems to say that the modification for instable search eliminates the only thing that is different in NTS from PVS. So what difference is remaining beween instable NTS and PVS?

Hi Onno, I'm not saying NTS is a new algorithm or anything just an enhancement to PVS. NTS is a more general algorithm dependent on node type so that moves that PVS doesn't do a scout search on NTS will: For example, say you do an enhancement such as no scout searches unless you have a well ordered move like a hash move or a killer or a good capture or whatever. Lets say you are on a non-null window ALL node and you don't have a good move ordered up front and so you don't do a scout search. But for the CUT node after the ALL node you have a good move ordered up front. For this you can do a scout search assuming current window is (beta-1,beta) unlike PVS which will search this move with the open window. Also I think I was wrong about the assesment that the research was faster when assuming stability. I think there are stable and unstable versions of PVS now as well:

From Bruce Moreland's website:

Code: Select all

int AlphaBeta(int depth, int alpha, int beta)
{
    BOOL fFoundPv = FALSE;
    if (depth == 0)
        return Evaluate();
    GenerateLegalMoves();
    while (MovesLeft()) {
        MakeNextMove();
        if (fFoundPv) {
            val = -AlphaBeta(depth - 1, -alpha - 1, -alpha);
            if ((val > alpha) && (val < beta)) // Check for failure.
                val = -AlphaBeta(depth - 1, -beta, -alpha);
        } else
            val = -AlphaBeta(depth - 1, -beta, -alpha);
        UnmakeMove();
        if (val >= beta)
            return beta;
        if (val > alpha) {
            alpha = val;
            fFoundPv = TRUE;
        }
    }
    return alpha;
}

This is a stable PVS because it trys scout search only after a move goes above alpha. For an unstable PVS you would do scout search after the first move has been searched.

Also note that the on an OPEN node where the first move did not increase alpha you do know that some move will increase alpha (if the search is stable), but you do not know which one. While the first move had a relatively high propability to do so, the propability for each individual of the following moves is much lower. So it might be good to do a scout search on them. Overall, search instability is not the only reason why instable NTS might be better then stable NTS.

[Pradu]

Hi Onno,

If you can see in the Fruit search, it has a slight modification from the regular PVS in order to make the search more stable.

This is the pseudocode:

Code: Select all

/* this is Fruit PVS */
if(first_move or beta == alpha + 1){
    score = -search(pos, -beta, -alpha, new_depth);
}else{
    score = -search(pos, -alpha-1, -alpha, new_depth);
    if(score > alpha)
        score = -search(pos, -beta -alpha, new_depth);
}


Notice that Fruit do a research every time the score is greater than alpha. In normal PVS, you only do a research if the score is in between alpha and beta.

Edsel Apostol (Twisted Logic)

I guess the score you get back here is a lower bound to the current position if scout search fails high. Therefore in the above code you can research with an even smaller window although this is maybe a bit more unstable:

Code: Select all

if(score > alpha && score < beta)
score = -search(pos, -beta, -(score-1), new_depth);

If you are going to research with the whole window anyways like Fruit then all you need to do is test if the score>alpha.

[Pradu]

Hi Onno,

If you can see in the Fruit search, it has a slight modification from the regular PVS in order to make the search more stable.

This is the pseudocode:

Code: Select all

/* this is Fruit PVS */
if(first_move or beta == alpha + 1){
    score = -search(pos, -beta, -alpha, new_depth);
}else{
    score = -search(pos, -alpha-1, -alpha, new_depth);
    if(score > alpha)
        score = -search(pos, -beta -alpha, new_depth);
}


Notice that Fruit do a research every time the score is greater than alpha. In normal PVS, you only do a research if the score is in between alpha and beta.

Edsel Apostol (Twisted Logic)

Notice also that the parameter for the research is "alpha and beta", and not "beta and score + 1".

I think that this is much stable than the regular PVS.

Pradu would you mind trying this in your engine BUZZ so that we could compare its performance over your NTS and the regular PVS.

Edsel Apostol (Twisted Logic)

I think it's just a difference in how you do a research. For Buzz, I think I "tested" a long while back and I decided to use updated bounds info from the scout search. I can try to do the test again.

[Pradu]

Final NTS search with no assumptions about what enhancements might be done to the search:

Code: Select all

#define OPEN_NODE 0
#define CUT_NODE  1
#define ALL_NODE  2

int childNodeType(const int previous_type)
{
   switch(previous_type)
   {
   case ALL_NODE: return CUT_NODE;
   case CUT_NODE: return ALL_NODE;
   default: return OPEN_NODE;
   }
}

int alphabeta(int depth, int alpha, int beta, int p_nodeType)
{
   int score = -MATE;
   int nodeType = childNodeType(p_nodeType);
   //Depth=0, Game decidable recognizers, Hashtables,
   //Mate-distance pruning for beta only, Nullmove, stuff...

   //Add split point adding code here if node type is ALL node

   for( /* every move m */ )
   {
      int tempscore;
      int lowerbound = max(alpha,score);

      <makemove m>

      if(lowerbound+1==beta || nodeType==OPEN_NODE || <optional> (haveNoGood ordered move) || <optional> (don't do NTS for this move for some reason))
         tempscore = -alphabeta(depth-1, -beta, -lowerbound, nodeType);
      else if(nodeType==ALL_NODE)
      {
         tempscore =  -alphabeta(depth-1, -(lowerbound+1), -lowerbound, nodeType);
         if(tempscore > lowerbound && tempscore < beta)
         {
            nodeType = OPEN_NODE;
            tempscore =  -alphabeta(depth-1, -beta, -(tempscore-1), nodeType);
         }
      }
      else /*CUT_NODE*/
      {
         tempscore =  -alphabeta(depth-1, -beta, -(beta-1), nodeType);
         if(tempscore > lowerbound && tempscore < beta)
         {
            nodeType = OPEN_NODE;
            tempscore =  -alphabeta(depth-1, -(tempscore+1), -lowerbound, nodeType);
         }
      }

      <unmakemove m>

      if(tempscore>score)
      {
         score = tempscore;
         if(score >= beta)
            return score;
      }
      if(nodeType == OPEN_NODE || (nodeType == CUT_NODE))
            nodeType = ALL_NODE;
      //Add split point adding code here if node type changes to ALL node
   }
   return score;


}

And here's the "Fruit-style"-research NTS counterpart of the above

Code: Select all

#define OPEN_NODE 0
#define CUT_NODE  1
#define ALL_NODE  2

int childNodeType(const int previous_type)
{
   switch(previous_type)
   {
   case ALL_NODE: return CUT_NODE;
   case CUT_NODE: return ALL_NODE;
   default: return OPEN_NODE;
   }
}

int alphabeta(int depth, int alpha, int beta, int p_nodeType)
{
   int score = -MATE;
   int nodeType = childNodeType(p_nodeType);
   //Depth=0, Game decidable recognizers, Hashtables,
   //Mate-distance pruning for beta only, Nullmove, stuff...

   //Add split point adding code here if node type is ALL node

   for( /* every move m */ )
   {
      int tempscore;
      int lowerbound = max(alpha,score);

      <makemove m>

      if(lowerbound+1==beta || nodeType==OPEN_NODE || <optional> (haveNoGood ordered move) || <optional> (don't do NTS for this move for some reason))
         tempscore = -alphabeta(depth-1, -beta, -lowerbound, nodeType);
      else if(nodeType==ALL_NODE)
      {
         tempscore =  -alphabeta(depth-1, -(lowerbound+1), -lowerbound, nodeType);
         if(tempscore > lowerbound)
         {
            nodeType = OPEN_NODE;
            tempscore = -alphabeta(depth-1, -beta, -lowerbound, nodeType);
         }
      }
      else /*CUT_NODE*/
      {
         tempscore =  -alphabeta(depth-1, -beta, -(beta-1), nodeType);
         if(tempscore < beta)
         {
            nodeType = OPEN_NODE;
            tempscore = -alphabeta(depth-1, -beta, -lowerbound, nodeType);
         }
      }

      <unmakemove m>

      if(tempscore>score)
      {
         score = tempscore;
         if(score >= beta)
            return score;
      }
      if(nodeType == OPEN_NODE || (nodeType == CUT_NODE))
            nodeType = ALL_NODE;
      //Add split point adding code here if node type changes to ALL node

   }
   return score;
}

Quick Initial Position Test

Code: Select all

Regular Research:
1 25 0 1 Nc3
1 59 0 9 d4
1 63 0 11 e4
1 63 0 22 e4
2 0 0 45 e4 e5
2 0 0 91 e4 e5
3 34 1 416 e4 Nf6 Nc3
3 56 1 646 d4 Nf6 e3
3 56 1 668 d4 Nf6 e3
4 -36 1 1139 d4 e6 Qd3 Qh4
4 0 1 1580 Nc3 Nc6 Nf3 Nf6
4 8 3 2047 e4 Nf6 e5 Nd5
4 8 3 2933 e4 Nf6 e5 Nd5
5 30 6 6224 e4 d5 Qf3 e6 a4
5 31 7 7902 Nc3 Nc6 e3 Nf6 Bd3
5 56 11 11723 e3 Nf6 Qf3 e5 Nc3
5 56 12 12649 e3 Nf6 Qf3 e5 Nc3
6 -5 18 20026 e3 Nc6 d4 d5 Qh5 Qd6
6 -1 26 29081 Nc3 e6 e4 Nc6 Qh5 g5
6 -1 43 48307 Nc3 e6 e4 Nc6 Qh5 g5
7 27 86 91250 Nc3 Nc6 d4 e5 dxe5 d6 Nf3
7 29 101 118724 Nf3 d5 d4 h6 Qd3 Qd6 Ne5
7 29 111 140636 Nf3 d5 d4 h6 Qd3 Qd6 Ne5
8 -6 145 201105 Nf3 d5 d4 h6 Nc3 Qd6 Ne5 g5
8 0 248 404208 d4 d5 Nc3 Nc6 h3 h6 g4 g5
8 1 307 522574 e3 Nc6 Bb5 Nf6 Qf3 e5 Nc3 d5
8 1 431 760731 e3 Nc6 Bb5 Nf6 Qf3 e5 Nc3 d5
9 12 882 1582747 e3 d5 d4 Qd6 Nc3 a6 Qh5 Nf6 Qg5
9 17 1087 1986824 Nc3 Nc6 d4 d5 h3 h6 Nf3 g5 a4
9 24 1267 2358283 Nf3 d5 d4 Nf6 Qd3 Nc6 h3 Ne4 Bd2
9 24 1336 2517688 Nf3 d5 d4 Nf6 Qd3 Nc6 h3 Ne4 Bd2
10 3 1732 3195276 Nf3 d5 d4 Nf6 Qd3 Qd6 Nc3 h6 Qb5+ c6 Qc5
10 4 2165 4062634 Nc3 Nc6 d4 d5 Bf4 f6 Nf3 g5 Bg3 h5
10 4 3815 7439501 Nc3 Nc6 d4 d5 Bf4 f6 Nf3 g5 Bg3 h5
11 19 6698 13058002 Nc3 Nc6 d4 d5 Bf4 Nf6 e3 a6 Be5 Nxe5
11 19 7582 14958231 Nc3 Nc6 d4 d5 Bf4 Nf6 e3 a6 Be5 Nxe5

"Fruit-Style" Research:
1 25 0 1 Nc3
1 59 0 9 d4
1 63 0 11 e4
1 63 0 22 e4
2 0 0 45 e4 e5
2 0 0 91 e4 e5
3 34 0 416 e4 Nf6 Nc3
3 56 0 646 d4 Nf6 e3
3 56 0 668 d4 Nf6 e3
4 -36 1 1139 d4 e6 Qd3 Qh4
4 0 1 1580 Nc3 Nc6 Nf3 Nf6
4 8 1 2047 e4 Nf6 e5 Nd5
4 8 1 2933 e4 Nf6 e5 Nd5
5 30 4 6224 e4 d5 Qf3 e6 a4
5 31 4 7902 Nc3 Nc6 e3 Nf6 Bd3
5 56 6 11723 e3 Nf6 Qf3 e5 Nc3
5 56 7 12649 e3 Nf6 Qf3 e5 Nc3
6 -6 10 20306 e3 Nc6 d4 d5 Qh5 Qd6
6 -1 17 33487 Nc3 e6 e4 Nc6 Qh5 g5
6 -1 28 52757 Nc3 e6 e4 Nc6 Qh5 g5
7 27 51 97881 Nc3 Nc6 d4 e5 dxe5 d6 Nf3
7 29 65 125626 Nf3 d5 d4 h6 Qd3 Qd6 Ne5
7 29 76 147912 Nf3 d5 d4 h6 Qd3 Qd6 Ne5
8 -6 112 207114 Nf3 d5 d4 h6 Nc3 Qd6 Ne5 g5
8 0 239 438430 d4 d5 Nc3 Nc6 h3 h6 g4 g5
8 1 303 560028 e3 Nc6 Bb5 Nf6 Qf3 e5 Nc3 d5
8 1 439 797322 e3 Nc6 Bb5 Nf6 Qf3 e5 Nc3 d5
9 11 914 1713710 e3 d5 Nf3 Nc6 Nd4 Nxd4 exd4 Qd6 Qh5
9 22 1143 2187356 Nf3 d5 d4 Nc6 Qd3 Qd6 h3 h6 Nc3
9 22 1312 2535334 Nf3 d5 d4 Nc6 Qd3 Qd6 h3 h6 Nc3
10 3 1670 3232661 Nf3 d5 d4 Nf6 Qd3 Qd6 Nc3 h6 Qb5+ c6 Qc5
10 4 2034 3957430 Nc3 Nc6 d4 d5 Bf4 f6 Nf3 g5 Bg3 h5
10 4 4048 7844591 Nc3 Nc6 d4 d5 Bf4 f6 Nf3 g5 Bg3 h5
11 19 7207 13924834 Nc3 Nc6 d4 d5 Bf4 Nf6 e3 a6 Be5 Nxe5 dxe5
11 19 8078 15783362 Nc3 Nc6 d4 d5 Bf4 Nf6 e3 a6 Be5 Nxe5 dxe5

[Edsel Apostol]

This searches needs to be tested throughly. I wish I had time. I will try to implement this on my engine and see if it improves perormance but that would be later. I need first to fix the crashing bug on my brand new engine.

Pradu if you have more results, we are interested to know.

[Pradu]

This searches needs to be tested throughly. I wish I had time. I will try to implement this on my engine and see if it improves perormance but that would be later. I need first to fix the crashing bug on my brand new engine.

Pradu if you have more results, we are interested to know.

I'm quite bad (or lazy?) at testing. I've decide to use it in my engine with hardly any tests... Anyways I think you should try it out for your own engine to see if it works or not instead of taking my word. It is nearly identical to PVS, just bit generaized to take care of oddities like not doing PVS/NTS on certain nodes. So, theoretically, I don't see why it shouldn't work.