Search statistics

[henkf]

In another thread Vincent asked Harm Geert for search statistics of his engine. In my recently started engine I'm gathering them, but I don't know exactly what to aim for. Currently my engine consists of an unmodified PVS, move ordering in main search hashmove, captures sorted with MVV/LVA and one killer. In qsearch i only sort captures with MVV/LVA. Evaluation is just material and piece-square tables.

This is what i am getting from the opening position:

Code: Select all

Welcome to Vlad Tepes 6000 00.00.02
Type "help" for help
sd 10
go
+-----------------------------------------------------------------------------+
|Depth   Value     Time        Nodes PV                                       |
+-----------------------------------------------------------------------------+
     1    0.40    0.000           22 1. Nf3
     2    0.00    0.000           85 1. Nf3 Nf6
     3    0.40    0.015          609 1. Nf3 Nf6 2. Nc3
     4    0.00    0.015         2013 1. Nf3 Nf6 2. Nc3 Nc6
     5    0.10    0.031        18778 1. Nf3 Nf6 2. Nc3 Nc6 3. d4
     6    0.00    0.062        66433 1. Nf3 Nf6 2. Nc3 Nc6 3. d4 d5
     7    0.10    0.405       538625 1. Nc3 Nf6 2. e4 Nc6 3. Nf3 d5 4. e5
     8    0.00    1.716      2151545 1. Nc3 Nf6 2. e4 Nc6 3. Nf3 d5 4. e5 d4
     9    0.12   12.761     16330235 1. Nc3 Nf6 2. d4 d5 3. Bg5 Ne4 4. Nf3 Nc6
                                     5. Rc1
    10    0.04   89.092    104777349 1. Nc3 Nf6 2. d4 d5 3. Bg5 Ne4 4. Nf3 Nc6
                                     5. Rc1 Be6
+-----------------------------------------------------------------------------+
|Nodes:     ab         leaf          all          cut           pv            |
|    104777349       79.67%        2.08%       14.83%        0.01%            |
+-----------------------------------------------------------------------------+
|Cut:    first       second        third       fourth        fifth        more|
|       61.93%       11.11%        6.70%        3.68%        2.37%      14.21%|
+-----------------------------------------------------------------------------+
|Nodes:      q         q/ab          all          cut           pv         pat|
|    130645162      124.69%       25.63%       15.70%        0.01%      58.67%|
+-----------------------------------------------------------------------------+
|Cut:    first       second        third       fourth        fifth        more|
|       97.02%        2.34%        0.53%        0.09%        0.02%       0.00%|
+-----------------------------------------------------------------------------+
|Hash:    size         fill          get          hit         miss         cut|
|      2097152      100.00%    104688671        4.31%       95.69%       3.68%|
+-----------------------------------------------------------------------------+
Vlad Tepes 6000 plays b1c3

As you can see move ordering in main search is not so great, so there seems a lot of improvement possible there. In qsearch it's different, when it cuts, mostly it cuts on the first move. Also the percentage of hash hits doesn't look very impressive, but I'm not sure since I have nothing to compare it with.

I would appreciate it if you would share your stats/thoughts with me.

[Aleks Peshkov]

Starting position is bad for tests because it is unnaturally closed and have no tactics. Quiescence is degenerated into recapture sequence.

[MattieShoes]

i've been busy breaking things, but here's what mine spits out for the initial position currently.

For my data, leaf node is the one where depth hits zero, not the actual post-qsearch tip. And it doesn't currently track beta cutoffs, just any move > alpha, and in the case of quiesence search, whether stand-pat increases alpha too.

I also calculate branching factor in a not-normal way... I didn't really like the dividing nodes for ply N by nodes for ply N-1.
BF^depth = leaves
BF = 10^(log(leaves)/depth)

Code: Select all

MP> xboard
sd 10
st 9999
go
ply  score   time      nodes PV
  1     -6      0          2 a4
  1      1      0          4 c4
  1     27      0          5 d4
  1     34      0          6 e4
# EBF: 20.00
  2      5      0         45 e4 e5
# EBF: 7.75
  3     28      0        262 e4 d5 Nc3 dxe4 Nxe4
  3     31      1        745 Nc3 e5 e4
# EBF: 8.28
  4      5      1       1579 Nc3 Nc6 e4 e5
# EBF: 5.98
  5     27      2       5546 Nc3 Nc6 e4 e5 Nf3
  5     30      2       9048 d4 Nf6 Nc3 Nc6 e4
# EBF: 5.33
  6      5      4      17590 d4 Nf6 Nc3 d5 Nf3 Nc6
  6      6      6      27512 e4 Nc6 Nf3 Nf6 e5 Nd5
# EBF: 5.24
  7      5     22     134987 e4 d5 e5 d4 Nf3 Nc6 d3
  7      9     27     171257 d4 Nf6 Nc3 d5 Nf3 Nc6 e3
  7     10     32     202172 Nc3 d5 Nf3 Nf6 d3 d4 Ne4
# EBF: 5.20
  8      5     45     298903 Nc3 d5 d4 Nf6 Nf3 Nc6 e3 e6
  8     13     85     591464 e4 e5 Nf3 d5 exd5 e4 Bb5+ Ke7 Nd4 Qxd5
# EBF: 4.79
  9     18    228    1613531 e4 d5 e5 d4 Nf3 Nc6 Bc4 e6 O-O
# EBF: 4.24
 10     10    530    3841663 e4 e5 Ne2 Nf6 Nbc3 d5 d4 exd4 Nxd5 Nxd5 exd5
# EBF: 4.31
move e2e4
# Summary:
#          nodes        internal          leaves      quiescence
#        6445268         1572251         3057960         1815057
#         100.0%           24.4%           47.4%           28.2%

# Internal:
#            ALL              PV             CUT            MATE
#         173217           33418         1068923            3060
#          11.0%            2.1%           68.0%            0.0%

# Hash:
#         Probes            Hits          Misses
#        6445268         1611232         4834036
#         100.0%           25.0%           75.0%

# Null Move:
#       Attempts         Cutoffs        Failures
#          12504            9139            3365
#         100.0%           73.1%           26.9%

# Internal > alpha slots:
#   first   second    third   fourth    fifth    sixth seventh+
# 1049165    99758    29119     6239     1579      663     2458
#   88.2%     8.4%     2.4%     0.5%     0.1%     0.1%     0.2%

# quiesce > alpha slots:
#     pat    first   second    third   fourth    fifth   sixth+
# 2708351   359705    43059    11864     3194      823      148
#   86.6%    11.5%     1.4%     0.4%     0.1%     0.0%     0.0%

# NPS: 719017
# q-nodes per leaf: 1.59

# Hash table data:
#            Size: 16777216 entries
#          Filled:  3970127 (23.7%)
#         Current:  3970127 (100.0%)
#   ALPHA   nodes:   926348 (23.3%)
#   BETA    nodes:  2852002 (71.8%)
#   EXACT   nodes:   191777 (4.8%)
#   Has best move:  1275781 (32.1%)
#     Depths:
#    0:    2909036 (73.3%)
#    1:     940687 (23.7%)
#    2:      81592 (2.1%)
#    3:      34795 (0.9%)
#    4:       2183 (0.1%)
#    5:       1317 (0.0%)
#    6:        293 (0.0%)
#    7:        180 (0.0%)
#    8:         26 (0.0%)
#    9:         17 (0.0%)
#   10:          1 (0.0%)

[MattieShoes]

Code: Select all

# Internal beta cutoff slots:
#   first   second    third   fourth    fifth    sixth seventh+
#  943429    81538    25721     5536     1217      493     1811
#   89.0%     7.7%     2.4%     0.5%     0.1%     0.0%     0.2%

# quiesce beta cutoff slots:
#     pat    first   second    third   fourth    fifth   sixth+
# 2486842   299570    26242     7199     1906      503       95
#   88.1%    10.6%     0.9%     0.3%     0.1%     0.0%     0.0%

There's the beta cutoff data

[henkf]

Starting position is bad for tests because it is unnaturally closed and have no tactics. Quiescence is degenerated into recapture sequence.

Apart from the fact that your answer is not extremely useful, I also disagree here. If I wanted to measure the effectiveness of volatile positions I probably could have contrived a position where every move would be a capture, but in this case the main search would be just an extension of the qsearch. As you can see from my stats qsearch doesn't have big problems with move ordering. The search tree contains a lot of garbage and also in a search of ten plies from the opening position you will see a lot of garbage. However a normal chess game doesn't walk the path of total garbage. If it would a chessgame would probably not last longer than 20 moves.

I think a lot can be gained with a good move ordering in quiet, even extremely quiet positions. Since my engine's evaluation consist of only material count and piece square tables, it is totally blind for this kind of positions, hence the low cutoff rate on first move. Since the eval is so course in a PVS search almost any node is a cut node, but since here my engine has no move ordering except for killer, it is clueless on what to try first. From Matt's example you can see I can gain almost 30 procent on move ordering, which partly explains his much faster finishing of depth 10.

[henkf]

I wish everybody would count the same way I do . The good news is, we count leave nodes the same way. But I don't add main search nodes and qnodes. I will try to transform your data to my approach as much as possible.

There are a few things I don't quite understand though.

On ply 1 (0) you only visit 6 nodes? Do you do some special pruning on the opening position, or is this a more generalistic pruning scheme?

Your leaf node count is higher than your qsearch count. You don't count qsearch nodes when entering qsearch?

Your cutoff rate on first move seems to be extremely good in main search, how do you do your move ordering? I wouldn't expect such a high cutoff rate with the usual ordering scheme, especially since the opening position is a dead quiet position ( but with a lot of potential )

[MattieShoes]

No pruning at all in the information i provided. In fact, I had futility pruning turned off too, but check extensions were on. Futility and extended futility pruning drop the total node count by about 10%, but move ordering numbers look slightly worse. I'm guessing this is because futility pruning hurts move ordering mostly near the tips where it has little impact but doesn't hurt near the root.

By the end of ply 1, the node count is 21 -- One internal node (the root), and 20 leaf nodes. My engine only spits out the PV when it changes and not at the end of a ply, so in this case, e4 was the 5th move tried... It then tried the other 15 but since it didn't change the PV, nothing was printed out. On ply 2, it tries e4 first, and after the 20 replies and a couple q-search nodes, total nodes is up from 21 to 45.
sd=1 search would show this:

Code: Select all

# Summary:
#          nodes        internal          leaves      quiescence
#             21               1              20               0
#         100.0%            4.8%           95.2%            0.0%

Regarding move ordering, it is indeed tricksy at the initial position. In very tactical positions, it might get over 97% of the beta cutoffs on the first move attempted.

On the other hand, engines are typically using a book at the initial position so tuning your engine to have good move ordering there is not as useful as tuning it to have good move ordering elsewhere.

The way I've got it set up, the first q-search node is the leaf node, and all successive ones are in the q-search nodes column. Basically I think of the leaf node itself as part of the search but finishing off any capture sequences is part of eval for determining score of that leaf. If there are no captures, or eval is high enough to cause a beta cutoff without further examination, I didn't want to count it against q-search.

So the literal number of calls to qsearch function would be leaves+qsearch nodes. In the 1 ply example above, qsearch was called 20 times but there were no possible captures so quiescence nodes says zero. It's kind of a weird way to think of it, but it makes the 3 different types add up to 100% and it feels right to me.

Then to make it more confusing, I count leaves as a qsearch node later

Code: Select all

# q-nodes per leaf: 1.59 

That would be 1.0 in the 1 ply example, but using my own logic it should be zero.

Be very wary of tuning your move ordering with a simple value+pcsq evaluation, at least if you plan on adding eval complexity later. You can get tremendously awesome move ordering simply by MVV/LVA and adding pcsq[to]-pcsq[from]. With that, you're practically doing what your entire eval function does already, so of course it usually gets the right answer! But as soon as you make a more intelligent eval, your move ordering will suck again.

If the only thing you have is really just a killer, I can tell you how to fix it. Order captures before the killer (and the killer should never be a capture). You can refine this further by ordering captures in a most valuable victim / least valuable attacker scheme. Trust me, it'll make a world of difference.

A sort of generic move ordering cheat sheet

1) Hash move (if available)
2) captures, MVV/LVA, and queen promotions
3) Killer (and killers are never captures or queen promotions)
4) castle moves
5) pawn moves
6) all else

There are ten bazillion refinements to that of course...

[jsuberd]

A sort of generic move ordering cheat sheet

1) Hash move (if available)
2) captures, MVV/LVA, and queen promotions
3) Killer (and killers are never captures or queen promotions)
4) castle moves
5) pawn moves
6) all else

There are ten bazillion refinements to that of course...

Hello,

Speaking of (initial) move ordering refinements it comes to my mind :
Having observed some engine matches, one idea which I suppose some programs already use, (though I am not aware of,) is that we may use some statistics in various game phases (or other relevant parts) for the moves of a particular piece type.

That is in which phase a particular piece type is expected to move and with what percentage. Then having that percentage together with the percentage of that type in our pieces we can arrange what type to move first and alike.

For instance king is expected to move very little in the opening while the opposite is true in the endgame. So if we are in the opening we put king moves to the end of list (except possibly the castles) and vice versa in endgame. Has this been tried ? What do you think of it ?

[MattieShoes]

Nothing new under the sun

Since alpha beta relies on cutoffs, what you put at the END of the list is not terribly important. It's what goes at the BEGINNING that's crucial. In my little search earlier, a cutoff move was found in the first three slots 99% of the time in beta nodes. Ordering of the other 20+ moves can't help in that 99%, nor in 100% of the alpha nodes, and nearly all of the PV nodes have already found the best move by the end of the movelist. But if I could get that 7.7% beta cutoffs currently in slot 2 to move to slot 1... THEN I'd have something!

Engines evaluate positions and look backwards, not looking forward and evaluating moves like humans. You have to tell the evaluator the position AFTER that move is bad rather than saying the move is bad. It becomes semantics with searching since evaluating the position after every move is equivalent to evaluating every move, but...

Take 1.e4 d5 2. exd5 Qxd5
This is obviously not optimal for black because white gets a free tempo with Nc3, but there's no easy way to tell an engine about tempo. You tell it positions with more mobility are better and it finds after e4 d5 exd5 Qxd5 Nc3 Qanywhere and white continues to develop... Now it knows black is losing. But the real thing here is you don't want to tell it moving the queen a second time is bad -- Moving the queen a second time is best option at that point, and you want to search those queen moves FIRST! And engines spend obscene amounts of time searching crap moves like that. In my 10 ply search, it must have searched at least one line an additional 6 ply, and probably more due to silly queen checks. I can almost guarantee some of those nodes were e4 d5 exd5 Qxd5 Nc3 Qe5+ Be2 Qg5 ... or some variant of that.

But I think what you're suggesting IS done explicitly in the opening - a penalty for unmoved knights and bishops to nudge the comp to develop, and penalties for moved kings that are not castled, penalties for trapped rooks, etc. Also, king pcsq tables change as one nears endgame, so slowly central kings are better than ones tucked safe in the corner, so it naturally starts shuffling the king towards the center like it should.

[MattieShoes]

I lied before -- null move pruning was on. Whoops!

So I ran some tests on the initial position to depth 8

No ordering
345,867,913 nodes

MVV/LVA only
10,350,093 nodes (removes 97%)

Add a pair of killers
1,143,112 nodes (removes 89% of what's left)

Adding hash move
932,242 nodes (removes 18% of what's left)

adding history heuristic
748,741 nodes (removes 20% of what's left)

other stuff
751,484 nodes (added .3% but it does better in a more typical position)

Of course the difference becomes more significant the deeper one searches, with the possible exception of history heuristic, which may lose efficacy as searches get deeper.


MVV/LVA removes a lot of the wasted time in q-search while the others help with internal nodes, except my "other stuff" which mainly improves ordering of captures.


Where moves>alpha are found -- X axis is logarithmic which is probably more accurate in terms of importance. Clearly MVV/LVA + killers are hugely important, and other improvements have good but diminishing returns, relatively speaking.

And this is the one I didn't expect

Good move ordering is necessary for null move pruning to operate effeciently. The faster you get alpha up, the more positions will fail high on depth+1.