Is Komodo trying to become like Stockfish? To Larry kaufman

[Laskos]

Most probably this has been thought and tested and perhaps is even already used, but I cannot restrain myself of asking you if would not be a good idea to have a combination of deep and wide search according situation. Wide search in the first, say, 5 ply, then deep search with some lines, then wide search with those lines mos important, and so and so, in a way not to choose in general one approach or the other, but related to circumstances.

Fern

When the search becomes deeper, the first plies are searched more thoroughly too, on long searches it becomes almost full width at shallow depths. The tree grows both in depth and in width.

That's not necessarily true. For example, assume you do LMR at the root. In that case the first ply gets NARROWER as you go deeper, because as the depth increases so does the LMR reduction amount. Each iteration trims more off of the later moves. That's the only way to keep the EBF at 2.0 and lower. Any extra effort near the root blows up way out in the tree.

Near the tips what you describe actually happens, because forward pruning is only done with N plies of the tips of the branches. Each additional ply of search pushes that pruning out one ply farther, which I suppose might be considered searching more carefully near the root...

All in all, when I plotted the tree of Stockfish 2-3 years ago to depth 25, the first 6-7 plies were searched almost full width. To depth 10, only first 2-3 plies. Show me a top engine not solving almost all tactical puzzles of depth 5-6 in 10 seconds on modern PC.

[Laskos]

I do not have an idea from where you got the idea I am asking for weak engines....
No...
I was just musing a bit about search techniques and that is all.
And I had as reference no my paltry 2100 or so elo player level but the best of them..
In fact, when I play with the idea to have some chances, I do it againts one of my dedicated units, which goes from 1300 to 2200 Elo.

Fern

Sorry, I thought you were saying something of the order "too much depth" in some other threads, and maybe you thoght the authors don't pay enough attention to the width.

[syzygy]

I was just wondering if your current development of Komodo is based on trying to become like stockfish? I noticed with Komodo 9.0 there was a faster time to depth to some extent, and then with 9.1 there is an even bigger faster time to depth. So now the depths of Komodo are very comparable to stockfish. I'm wondering if this is a good idea.

I don't see any reason to try to (...)

I think you can very, very, very, very, very safely leave these choices and decisions to Larry and Mark and stop worrying.

[bob]

Most probably this has been thought and tested and perhaps is even already used, but I cannot restrain myself of asking you if would not be a good idea to have a combination of deep and wide search according situation. Wide search in the first, say, 5 ply, then deep search with some lines, then wide search with those lines mos important, and so and so, in a way not to choose in general one approach or the other, but related to circumstances.

Fern

When the search becomes deeper, the first plies are searched more thoroughly too, on long searches it becomes almost full width at shallow depths. The tree grows both in depth and in width.

That's not necessarily true. For example, assume you do LMR at the root. In that case the first ply gets NARROWER as you go deeper, because as the depth increases so does the LMR reduction amount. Each iteration trims more off of the later moves. That's the only way to keep the EBF at 2.0 and lower. Any extra effort near the root blows up way out in the tree.

Near the tips what you describe actually happens, because forward pruning is only done with N plies of the tips of the branches. Each additional ply of search pushes that pruning out one ply farther, which I suppose might be considered searching more carefully near the root...

All in all, when I plotted the tree of Stockfish 2-3 years ago to depth 25, the first 6-7 plies were searched almost full width. To depth 10, only first 2-3 plies. Show me a top engine not solving almost all tactical puzzles of depth 5-6 in 10 seconds on modern PC.

I'm just describing how it actually works, nothing more or less. The whole idea of (dynamic LMR and adaptive null-move) is to be more aggressive near the root, less aggressive near the tips where you have less chance to recover from an error. Forward pruning is exactly the opposite, you do it near the tips where you have all the earlier plies to change something should you introduce an error.

If someone did something like "I am not going to do this except within N plies of the tips" then that would do exactly as you are describing, because every new ply of depth causes one more ply near the root to lose that selectivity stuff. Some used to do this as they approached the endgame, by slowly starting to turn off null move (I am doing this in Crafty now, for example). So in endgames with few pieces, what you describe is exactly what happens.

If you look at stockfish (and others) however, for the LMR reduction value R, as the "depth" increases (the distance from the tips of the tree) the R value also increases. Widening at the root has a PROFOUND affect on the EBF. Because of all the subtrees that are grown below those ply=1 moves.

How can you tell whether the first N plies are searched "full width" or not? In fact, what does that actually mean? In the normal sense, full width means ALL moves are searched at that ply, and we certainly do that for the root. And in fact all but the last few plies. They are not searched as deeply, but I don't think anyone is throwing moves out at the root and never searching them.

As far as solving tactical positions in depth 5-6 you might try win at chess. It is an easy test set with lots of shallow problems. I'll bet most won't get them all, in fact. I just tried Crafty and it got a whopping 145 right out of 300 at sd=5. Using a second per position, however, running on my macbook with 1 thread gets 282 out of 300...

[Laskos]

I'll bet most won't get them all, in fact. I just tried Crafty and it got a whopping 145 right out of 300 at sd=5. Using a second per position, however, running on my macbook with 1 thread gets 282 out of 300...

Yes, I wrote at fixed time of 10 seconds on modern PC, then almost all ply 5-6 problems are solved, no matter how much they are reduced initially.

[bob]

I'll bet most won't get them all, in fact. I just tried Crafty and it got a whopping 145 right out of 300 at sd=5. Using a second per position, however, running on my macbook with 1 thread gets 282 out of 300...

Yes, I wrote at fixed time of 10 seconds on modern PC, then almost all ply 5-6 problems are solved, no matter how much they are reduced initially.

I am not sure what that is supposed to prove. I suppose you could create a set of solved-in-5 positions, solved-in-6 positions and so forth and run them over and over with increasing depth to see where you have to get to depth-wise to solve them all. In many tactical positions the best move doesn't look like the worst move although this does happen (wac 141 for example the solution is Qxf4, and that is typically ordered last). I just tried it on Crafty, it is a mate in 6 and it finds the move at depth=11. I had crafty dump the move list after each iteration, and after depth=10, Qxf4 is still dead last. Takes well under 0.1 seconds on my macbook using one core. In the sd=5 search of WAC, Crafty found several mates in 3, but none any deeper.

So I guess the issue is about the "widening" once again. How do you think the search is being "widened" as the depth grows? If you scatter plot the entire tree, it looks like an inverted V using the usual orientation of "deeper = down". But the angle of the cone sides doesn't seem to shift, the two sides just grow farther apart as the tree goes deeper, and from that perspective the tree is both wider and deeper. But it is "widening" at a constant ratio as a function of the search depth, and it is widening near the tips because there are more of them as depth increases. One root move is not being favored over any other in a way that changes as the depth increases, other than the later moves end up getting reduced more and more with increased depth.

[Darkmoon]

I've noted that Komodo remains on top by my own tests. But what has surprised me is Stockfish bouncing back rather fast with Stockfish 290615 breathing down your neck.

My question is a simple one -how sure are you of your recent changes and are they something that you are determined to stick with in the long run?

I don't know anything about programming.But, are these changes something you can build on successful without loss of momentum.

[Laskos]

I'll bet most won't get them all, in fact. I just tried Crafty and it got a whopping 145 right out of 300 at sd=5. Using a second per position, however, running on my macbook with 1 thread gets 282 out of 300...

Yes, I wrote at fixed time of 10 seconds on modern PC, then almost all ply 5-6 problems are solved, no matter how much they are reduced initially.

I am not sure what that is supposed to prove. I suppose you could create a set of solved-in-5 positions, solved-in-6 positions and so forth and run them over and over with increasing depth to see where you have to get to depth-wise to solve them all. In many tactical positions the best move doesn't look like the worst move although this does happen (wac 141 for example the solution is Qxf4, and that is typically ordered last). I just tried it on Crafty, it is a mate in 6 and it finds the move at depth=11. I had crafty dump the move list after each iteration, and after depth=10, Qxf4 is still dead last. Takes well under 0.1 seconds on my macbook using one core. In the sd=5 search of WAC, Crafty found several mates in 3, but none any deeper.

So I guess the issue is about the "widening" once again. How do you think the search is being "widened" as the depth grows? If you scatter plot the entire tree, it looks like an inverted V using the usual orientation of "deeper = down". But the angle of the cone sides doesn't seem to shift, the two sides just grow farther apart as the tree goes deeper, and from that perspective the tree is both wider and deeper. But it is "widening" at a constant ratio as a function of the search depth, and it is widening near the tips because there are more of them as depth increases. One root move is not being favored over any other in a way that changes as the depth increases, other than the later moves end up getting reduced more and more with increased depth.

Yes, the issue is about the widening once again, this time of the shape of the tree on a single core for smaller and larger number of iterations, and I found I saved the post I posted several years ago here. The model tree is using heavy reductions a la Stockfish and has a constant EBF of 2.0. Depth in the following is used interchangeably with the number of iterations. From the plot it can be seen that iteration (or depth) 10 gives almost full width search to ply 1-2 with EBF(depth, ply) of maybe 10-20, while iteration (or depth) 35 gives 6-7 almost full width plies near the root, with EBF(depth, ply) of 10-20. That all while EBF(depth) is constant 2.0.

Here is what I posted as a reply to Rein several years ago:

Just to abstract from the name-calling and confusion.

Bob's definition of EBF (depth) = nodes(depth) / nodes(depth-1). For a perfectly regular tree, nodes(depth) = width^depth and EBF(depth) = width, independent of depth. So far so good. Marco's observation was that in irregular trees the extra nodes at the next depth iteration are not all leaf nodes. The pyramid analogue really explains this nicely: adding a layer to the sides, some stones to the bottom etc. In such irregular trees, a single EBF doesn't contain all the information about the shape of the tree.

Generalizing slightly, you can define an EBF at each ply level of the tree as EBF(depth, ply) = nodes(depth, ply) / nodes(depth-1, ply). The claim is that for fixed ply, EBF(depth, ply) is increasing in depth, simply because LMR and NMR are reducing more heavily at lower remaining depth. This is what people mean with "widening the tree". A better term would perhaps be that high in the tree, the tree is "thicker" or "denser". Similarly, for fixed depth, EBF(depth, ply) is decreasing in ply. So lower in the tree (near the leafs), the tree is quite "thin".

So at ply=1, (the root moves) the EBF is probably around 30+, whereas at ply=depth (the leaf nodes) the EBF might be 1. The overall EBF of a tree can still remain fairly constant around 2.

I guess these observations are fairly trivial and could have been made a lot earlier if people were to take the courtesy of interpreting each other words a bit more constructively...

Thanks.

Rein

I have just constructed a model tree shape of engines using reductions a la Stockfish. The math is a bit complicated and is not very illuminating. The shape of the tree as a function of (depth, ply) is given by
(depth)^(log(2)) * log(ply+1)/4,
with the normalization factor chosen as to have the EBF(depth) at a constant=2. The tree shapes are plotted here for depths 10, 20, 35.


From ply 20 to 21 the number of nodes for widening are ~2.5 millions, for deepening ~2.1 million, so 54% for widening.
From ply 31 to 30 the number of nodes for widening are ~3.0 billion, for deepening ~2.1 billion, so 59% for widening. Larger depth you go, proportionally more nodes are going to widening.

[bob]

Here's a thought to see if we are talking apples-to-apples. Suppose I create an array of 64 bit counters in Crafty, and for every move searched at a specific ply I increment a counter? And then print these numbers. And do this iteration by iteration to see how things change.

Obviously there is zero widening at ply-1. As there are only N moves available. But if you think about an alpha/beta tree, at ply=2 the first node at that ply is a full-width node. And all others are one-move nodes since they are all cut nodes.

I don't see why that will change at depth=3. Same rule applies. Ply=1 is always a PV node, first ply=2 node is a PV node, the remainder are all Cut nodes. I'd expect the plies to remain quite static. Back in a bit with some real data. I'll probably limit the plies where I count to maybe 10 to avoid a painful amount of data to show here...

[bob]

OK, have some data.

But first, to make sure we are talking the same "widening" definition...

An alpha/beta minimax tree has three cases for nodes near the root. (1) a full-width node (AKA an ALL node in Knuth/Moore terminology) where every move is searched. The only thing that constrains this is how many legal moves there are (and I assume the term widening doesn't refer to the number of legal moves somehow increasing the number of legal moves. (2) a CUT node typically only searches one move, assuming good move ordering. It might search more than one if the best move is not searched first. But again, I only assume you don't mean that we somehow "break" move ordering to search in a worse order? (3) some of those CUT nodes don't just search one node, as explained. How many depends on the quality of the move ordering and how unexpected the best move might be. You can't search more than the number of legal moves at a ply, nor can you search less than 1 move ever.

For my test, I set up a 10 element array (but only use entries 1-9). Each time I make a move, whether in search or quiesce, if ply is < 10, I increment counter[ply]. I print these between each iteration. Here is a search from the opening position. Each row of data comes after a single iteration, starting at iteration 1 (which is why most of the higher counters are zero).

Code: Select all

  20(1)    0(2)    0(3)     0(4)      0(5)      0(6)       0(7)       0(8)        0(9)
  22(1)   42(2)    0(3)     0(4)      0(5)      0(6)       0(7)       0(8)        0(9)
  22(1)   60(2)   86(3)     2(4)      0(5)      0(6)       0(7)       0(8)        0(9)
  22(1)  190(2)  388(3)   207(4)     20(5)     10(6)       0(7)       0(8)        0(9)
  21(1)   40(2)   73(3)   201(4)    117(5)      6(6)       0(7)       0(8)        0(9)
  21(1)   77(2)  526(3)   613(4)    892(5)    299(6)      24(7)      10(8)        0(9)
  21(1)   45(2)  177(3)   300(4)    470(5)    396(6)     378(7)      27(8)        8(9)
  22(1)  154(2)  636(3)  1948(4)   5280(5)   5440(6)    5092(7)    3743(8)      759(9)
  22(1)   75(2)  618(3)  1584(4)   3087(5)   6139(6)    5794(7)    8818(8)     5034(9)
  23(1)   80(2)  565(3)  1608(4)   3680(5)   5057(6)   10633(7)   11619(8)    10221(9)
  21(1)   47(2)  469(3)   918(4)   2248(5)   2442(6)    2859(7)    7431(8)     3965(9)
  20(1)   34(2)  414(3)   929(4)   4166(5)   5462(6)    7843(7)   13946(8)    16441(9)
  22(1)   72(2)  557(3)  1994(4)   9379(5)  15597(6)   25749(7)   41773(8)    49304(9)
  21(1)   73(2)  543(3)  1880(4)  11951(5)  19130(6)   38837(7)   50376(8)    74764(9)
  21(1)   53(2)  459(3)  1023(4)   7494(5)  15914(6)   34420(7)   58374(8)    85166(9)
  21(1)   93(2)  700(3)  2224(4)  16419(5)  44146(6)  133565(7)  212495(8)   304994(9)
  20(1)   28(2)  453(3)   882(4)   8926(5)  17666(6)   73493(7)  128750(8)   202283(9)
  20(1)   27(2)  418(3)   775(4)   6717(5)  17215(6)   55580(7)  139609(8)   181104(9)
  22(1)   75(2)  577(3)  1678(4)  13042(5)  34590(6)  167060(7)  349814(8)   726978(9)
  20(1)   40(2)  499(3)   972(4)  11451(5)  23846(6)  185655(7)  239267(8)   735104(9)
  21(1)   69(2)  494(3)  1684(4)  10952(5)  39406(6)  156158(7)  506800(8)   971224(9)
  20(1)   36(2)  467(3)   901(4)  10785(5)  22348(6)  191083(7)  317677(8)  1177444(9)
  21(1)   49(2)  439(3)   977(4)   9363(5)  25734(6)  151756(7)  436878(8)  1176560(9)
  20(1)   34(2)  450(3)   723(4)  10231(5)  18663(6)  196544(7)  299081(8)  1326857(9)
  20(1)   34(2)  474(3)   855(4)  11402(5)  22648(6)  254562(7)  406337(8)  1934743(9)
  20(1)   34(2)  471(3)   842(4)  11487(5)  23204(6)  281363(7)  481762(8)  2455019(9)

what I see happening is that as the iterations progress, the early counters stabilize. You might notice some 20's and 21's and even a 22, which is caused by a fail high at the root (there are obviously 20 legal first moves for white).

If you pick a ply like 5, and watch it, it starts off at zero, then as the search begins to hit 5 plies, the counters start to climb. And each iteration after that for a few iterations the counters continue to climb as those nodes near the tips definitely widen as the search goes deeper. At ply=5 with depth=5, Crafty does pretty aggressive futility and LMP type pruning. At depth=6, ply=5, the pruning tapers off a bit and that level widens. At depth=7, ply=5 more of the same. Until the search goes deep enough that ply=5 is beyond any sort of forward pruning. But that takes 10-15 plies to happen since LMR can reduce the depth between the root and that ply=5 move significantly. But eventually that goes away.

So what I see is that as the search goes deeper, the early plies become pretty stable (there are always move ordering issues, history counter changes, hash table hits and such) as to how many moves are searched. The REAL effort gets added on to the end of each branch as you go one ply deeper.

So somehow we don't seem to be talking about the same thing. There is no widening that can happen within the first 5 plies on a 20 ply search. The above seems to have stabilized in the first 9 plies by the time we get to depth=20. Which leads me to the conclusion that "widening" is not quite the right word here. It is pretty easy to go deeper at a given depth, with more extensions or less reductions, but I don't see how to influence the width of the tree except at that narrow band right before the frontier where the full-width search transitions to the quiescence search. (I think Crafty does this forward pruning only at the last 6 plies unless I changed it and have forgotten). So there is that "band" that widens as the frontier passes it by, ply by ply, until it stabilizes...

Thoughts???