Engine improvement ?

[lauriet]

My engine searches about 9 ply in 45 seconds. If I set the move time to 60 seconds,
it exits the 10th ply early, without updating the PV. (due to iterative deepening of course)
If I were to improve my search speed by 10% it could complete the 9 ply search now in
approx' 40 seconds, BUT given its branching factor is 3 or more it would still not complete a 10 ply search.
Of course once in a while (but not very often) it will find a better line on the 10th iteration early and
change to a new PV.

Am I right in concluding that the improvement comes from those occasional times where it does update the PV
early ?
Is this why I have to play 10,000 games to measure the improvement ?

Regards
Laurie.

[matthewlai]

My engine searches about 9 ply in 45 seconds. If I set the move time to 60 seconds,
it exits the 10th ply early, without updating the PV. (due to iterative deepening of course)
If I were to improve my search speed by 10% it could complete the 9 ply search now in
approx' 40 seconds, BUT given its branching factor is 3 or more it would still not complete a 10 ply search.
Of course once in a while (but not very often) it will find a better line on the 10th iteration early and
change to a new PV.

Am I right in concluding that the improvement comes from those occasional times where it does update the PV
early ?
Is this why I have to play 10,000 games to measure the improvement ?

Regards
Laurie.

Time-to-ply will be different for different positions, because different positions have different tree shapes and branching factors.

When you improve search speed or increase search time, some searches will finish more plies, and some won't. The ones that do give you the improvement.

Having to play more games is because stronger players won't always win. A stronger player just has a higher chance of winning, and if you want to verify small improvements (say 53% vs 47% win rate), you need a lot of games to make sure you are not just getting the ratios by luck. This has nothing to do with the search, and applies even to humans.

[AndrewGrant]

In addition to what Matthew said....

So you give the example of searching to depth 9, but not having time to finish depth 10. The time spent searching Depth 10, even though it never finishes, is not always wasted. Say the for your depth 10 search you finish looking at the first 4 moves. Well, if move 0, which was in your PV, happens to drop off at d10 (lost a queen.... something), then you can look at moves 1, 2, 3 to see if you have a better option. Even though you did not completely finish the search, ie proving that 1|2|3 is the best, you still know whether or not they are better than move 0.

[Sven]

My engine searches about 9 ply in 45 seconds. [...] given its branching factor is 3 or more it would still not complete a 10 ply search.

Assuming the speed of your engine is somewhere between 100,000 and 1,000,000 nodes per second it has an effective branching factor betwen 5 and 7. If you want to get a real improvement (not just "10%") then you need to work on move ordering and on search technologies that reduce the tree size. For instance, with an effective branching factor of 4 your engine would already search about 11 plies (with 100,000 nps) or almost 12 plies (with 1,000,000 nps). Of course these numbers can vary a lot for different positions but at least they can serve as a rough estimate. The strongest engines today have an EBF of 2 or even less, which is the reason why they get far beyond 20 plies very quickly.

[lauriet]

Hi Sven,

I've read that you need to be cutting nodes about 90% of the time, to get the best branching factor.
Can you explain this a bit more ?

I guess I need some counters in search to check this...any suggestions about that ?

Thanks
Laurie.

[Sven]

I've read that you need to be cutting nodes about 90% of the time, to get the best branching factor.
Can you explain this a bit more ?

Obviously you get the best possible effective branching factor (EBF - note that "branching factor" is not the same, the latter is dictated by the rules of the game!) if you "guess" the best move correctly at each node and prune everything else. But that is phantasy and does not work. Reality is that you have different types of nodes in your search tree: those where you need to search all moves (children) and those where you can save a lot of effort either through cutoffs or through other technologies that reduce the size of the subtree (reductions, pruning, ...). Reductions and other techniques of course help also for nodes where all children are searched.

If I only concentrate on cutoffs (since you asked about that, and I can't explain all in one post ), it should be obvious that the subtree of a node is smaller on average if you can perform a cutoff after the first move, compared to later. So your goal would be to get a high rate of cutoffs on the first move. That rate will never be 100% due to the inevitable existence of nodes where you need to search all children and never get a cutoff (happens at children of CUT nodes or first children of PV nodes). These are either PV nodes or ALL nodes according to Knuth (see https://chessprogramming.wikispaces.com/Node+Types for an overview). One way of measuring the quality of your move ordering is therefore to look at the rate of cutoffs on the first move. Numbers like "90%" are not given by any theory but have been reported by programmers. With roughly 80-90% you are probably quite good already while 50-70% will certainly show some room for improvements of move ordering. Of course you should be careful enough to take the average from searching different positions instead of only the initial opening position.

I guess I need some counters in search to check this...any suggestions about that ?

In my engine I maintain two pairs of additional counters (64 bit numbers to prevent overflow for long searches), one pair for full-width search and one for quiescence search. Each pair has one counter for all cutoffs and one for cutoffs occurring on the first move of a node. Counters are reset to 0 whenever the engine starts calculating its move, i.e. before starting the first iteration. Resetting for each iteration appeared meaningless to me, it could of course make sense for debugging. To update the "cutoffs on first move" counter you also need a local counter at each node that counts legal moves. The cutoff code now looks like:

Code: Select all

if (score >= beta) {
    ++allCutoffs;
    if (nLegalMoves == 1) ++cutoffsOn1stMove;
    break; // or do whatever you do to actually perform the cutoff
}

When finishing the search I print statistics and these now also include the percentages resulting from these counters. It could be done with only one pair as well, combining full-width and quiescence search, but I was interested in more details.

[Sven]

That rate will never be 100% due to the inevitable existence of nodes where you need to search all children and never get a cutoff

That part of my post was not accurate since the calculated rate compares cutoffs on first move to just all cutoffs, not to total number of nodes. So the correct wording would be: That rate will usually never reach 100% since you will be unable to achieve perfect move ordering.

[lauriet]

Hi Sven,

Since I do a null move before generating/searching would you count a null move cutoff in the stats ?


Regards
Laurie.

[lauriet]

Hi Sven,

Thinking a bit more about it and........ my search is like this:

1. Qsearch if depth=0
2. Get TT and look for immediate exit.
3. Null move and look for an immediate exit
4. 2 Killer moves and look for an immediate exit.
5. Generate other moves...and sort to with PV move, TT move, Captures/promotions,
history of quiet moves, in that order.
6. Search the move list.


So 2,3,4 should count as cuts on the first move shouldn't they ?

Regards
Laurie.

[CheckersGuy]

1. Qsearch if depth=0
2. Get TT and look for immediate exit.
3. Null move and look for an immediate exit
4. 2 Killer moves and look for an immediate exit.
5. Generate other moves...and sort to with PV move, TT move, Captures/promotions,
history of quiet moves, in that order.
6. Search the move list.

How do Killer Moves give you an immediate exit ? Shouldnt u just use them for ordering your MoveList ?