Singular Margin based on depth?

[Jose Carlos]

[quote="bobThe Hsu "sticky" stuff was done to address a search instability issue. When I did SE in the 1993/1994 Cray Blitz versions, I originally left that out not knowing whether it was that important or not. It was. The problem is that if you SE a move on iteration N, but when you get to N+1, things have changed a bit and the SE search says "don't extend". Now you are warping the shape of the tree and can see instability in the eval and/or PV moves. I don't remember the specifics since that was almost 20 years ago now, but as I carefully read his explanation and created the sticky TT table, the instability problem was mitigated. There was a "time-out" built in. SE says singular this iteration, but not the next. But the sticky says "treat it as singular". But if the next iteration also says "not singular" it would be removed. I don't remember the precise specifics about that, without getting to the office to dig up Hsu's ICGA paper on the algorithm...

How are these programs varying depth? For example, if the margin gets larger as remaining depth increases, that is probably a stop-gap measure to prevent the tree from exploding, as those moves are less likely to get extended near the root, where the extension affects a very large sub-tree. ."

Yes, margin gets larger with depth, in fact they just use depth or depth * constant as the margin. But I'm still unclear on the rationale. True, near the root the extension affects larger subtrees, but near the leaves the extension occurs vastly more often, so it is not obvious whether the extension costs more near the root or near the leaves in total. Can you explain why you think the total cost of all such extensions would be greater near the root than near the leaves?[/quote]

If you extend one ply at depth 10, you're extending all the subtree by a whole ply, but if you extend 95% of depth 4 searches, you still have 5% depth 4 nodes not extended (and all d5, d6, d7, ...), so the net cost is smaller.

[bob]

[quote="bobThe Hsu "sticky" stuff was done to address a search instability issue. When I did SE in the 1993/1994 Cray Blitz versions, I originally left that out not knowing whether it was that important or not. It was. The problem is that if you SE a move on iteration N, but when you get to N+1, things have changed a bit and the SE search says "don't extend". Now you are warping the shape of the tree and can see instability in the eval and/or PV moves. I don't remember the specifics since that was almost 20 years ago now, but as I carefully read his explanation and created the sticky TT table, the instability problem was mitigated. There was a "time-out" built in. SE says singular this iteration, but not the next. But the sticky says "treat it as singular". But if the next iteration also says "not singular" it would be removed. I don't remember the precise specifics about that, without getting to the office to dig up Hsu's ICGA paper on the algorithm...

How are these programs varying depth? For example, if the margin gets larger as remaining depth increases, that is probably a stop-gap measure to prevent the tree from exploding, as those moves are less likely to get extended near the root, where the extension affects a very large sub-tree. ."

Yes, margin gets larger with depth, in fact they just use depth or depth * constant as the margin. But I'm still unclear on the rationale. True, near the root the extension affects larger subtrees, but near the leaves the extension occurs vastly more often, so it is not obvious whether the extension costs more near the root or near the leaves in total. Can you explain why you think the total cost of all such extensions would be greater near the root than near the leaves?[/quote]

The tree is exponential in behavior. If you extend a root move, that entire sub-tree gets extended. If you wait until you are near the tips, you make the singular test many times, and you will not extend every branch. But if you extended at the root, every one of those "tip positions" is automatically extended.

For example, suppose your root singular margin results in one of every 10 moves getting extended. Those entire sub-trees are now one ply deeper. Suppose you don't extend those positions, but near the tips of each one, you extend one of every 5 moves. With the former, 100% of the sub-tree is extended by one ply. With the latter, only 20% is extended, even though we are extending twice as frequently at the tips than at the root. An 80% smaller tree.

[lkaufman]

The tree is exponential in behavior. If you extend a root move, that entire sub-tree gets extended. If you wait until you are near the tips, you make the singular test many times, and you will not extend every branch. But if you extended at the root, every one of those "tip positions" is automatically extended.

For example, suppose your root singular margin results in one of every 10 moves getting extended. Those entire sub-trees are now one ply deeper. Suppose you don't extend those positions, but near the tips of each one, you extend one of every 5 moves. With the former, 100% of the sub-tree is extended by one ply. With the latter, only 20% is extended, even though we are extending twice as frequently at the tips than at the root. An 80% smaller tree.

I still don't get it. In your example the root extension would cause the total tree size to grow by 10% (never mind the sub-tree), whereas the near-leaf extension would make the total tree size grow by 20%. What am I missing?

[BubbaTough]

I still don't get it. In your example the root extension would cause the total tree size to grow by 10% (never mind the sub-tree), whereas the near-leaf extension would make the total tree size grow by 20%. What am I missing?

It is not completely clear to me that extending a few deep nodes causes a worse explosion than extending a lot of shallow nodes (except in obvious cases where all the shallow nodes are subsumed within the few deep nodes). My intuition is this is very much the type of thing that is sometimes true and is sometimes not, and has to be measured on a case by case basis. I would guess the particular settings of the program in question were not deduced by pure logic, but were one of many many half-hazardly concocted things that were tried, and happened to work best. If people here can come up with convincing explanations post-mortem, that is great, but I wouldn't read to much into it. Try whatever makes sense to you, when you find out it doesn't work, try the opposite, and after you have found something that works great via exhaustive search, you can make up a wonderful philosophy on why your solution makes so much sense.

-Sam

[lkaufman]

We've tried both ways on this, but the results were just one elo apart, not significant. In cases like this, I think you have to go by logic and what "ought" to work, unless you think even a tiny plus like one elo should count for more than your own reasoning.

[BubbaTough]

We've tried both ways on this, but the results were just one elo apart, not significant. In cases like this, I think you have to go by logic and what "ought" to work, unless you think even a tiny plus like one elo should count for more than your own reasoning.

Something like this, where its non-obvious that it scales the same at larger time controls as smaller, I guess I would have to agree...assuming you have tested many dozens of things not just "both ways". If it was really a +-1 elo question, its perhaps not worth adding, but I suspect it is more than that, its just hard to demonstrate at a time control you can generate enough games with.

Personally though, when I include something based on gut feel that it is good, rather than results, the intuition I fall back on is what best mirrors an idealized human tree search, not the type of reasoning going on here, which looks pretty flimsy to me. Humans are darn good at organizing the few nodes they get to look at, and their approach scales darn well as you add nodes. For something that is indistinguishable in the length of games you are testing at, I would rather trust your intuition as a chess player than Bob's as a computer scientist.

-Sam

[Jose Carlos]

The tree is exponential in behavior. If you extend a root move, that entire sub-tree gets extended. If you wait until you are near the tips, you make the singular test many times, and you will not extend every branch. But if you extended at the root, every one of those "tip positions" is automatically extended.

For example, suppose your root singular margin results in one of every 10 moves getting extended. Those entire sub-trees are now one ply deeper. Suppose you don't extend those positions, but near the tips of each one, you extend one of every 5 moves. With the former, 100% of the sub-tree is extended by one ply. With the latter, only 20% is extended, even though we are extending twice as frequently at the tips than at the root. An 80% smaller tree.

I still don't get it. In your example the root extension would cause the total tree size to grow by 10% (never mind the sub-tree), whereas the near-leaf extension would make the total tree size grow by 20%. What am I missing?

Code: Select all

Consider this example:

D2           A
          /  |  \
D1      B    C    D
       /|\  /|\  /|\
D0    E F GH I JK L M


  In this tree, A is searched to depth 2, which leads to 13 nodes searched.
  If you extend A, it will be searched to depth 3:

D3                            A
                     /        |             \
D2          B                 C                          D
        /   |   \          /  |   \                 /    |    \
D1    E     F     G     H     I        J        K        L        M
     /|\   /|\   /|\   /|\   /|\     / | \    / | \    / | \    / | \
D0  N O P Q R S T U V W X Y Z A' B' C' D' E' F' G' H' I' J' K' L' M' N'

  40 nodes.
  Now suppose you take the original tree and extend most leaf nodes, like this:

D2                            A
                     /        |             \
D1          B                 C                          D
        /   |   \          /  |   \                 /    |    \
D0    E+1   F+1   G+1   H+1   I+1      J+1      K+1      L        M
     /|\   /|\   /|\   /|\   /|\     / | \    / | \  
D0  N O P Q R S T U V W X Y Z A' B' C' D' E' F' G' H'

  I've marked the extended nodes with "+1". As you see, you have less nodes (34).

  I hope the tree reads correctly.

[BubbaTough]

Code: Select all

Consider this example:

D2           A
          /  |  \
D1      B    C    D
       /|\  /|\  /|\
D0    E F GH I JK L M


  In this tree, A is searched to depth 2, which leads to 13 nodes searched.
  If you extend A, it will be searched to depth 3:

D3                            A
                     /        |             \
D2          B                 C                          D
        /   |   \          /  |   \                 /    |    \
D1    E     F     G     H     I        J        K        L        M
     /|\   /|\   /|\   /|\   /|\     / | \    / | \    / | \    / | \
D0  N O P Q R S T U V W X Y Z A' B' C' D' E' F' G' H' I' J' K' L' M' N'

  40 nodes.
  Now suppose you take the original tree and extend most leaf nodes, like this:

D2                            A
                     /        |             \
D1          B                 C                          D
        /   |   \          /  |   \                 /    |    \
D0    E+1   F+1   G+1   H+1   I+1      J+1      K+1      L        M
     /|\   /|\   /|\   /|\   /|\     / | \    / | \  
D0  N O P Q R S T U V W X Y Z A' B' C' D' E' F' G' H'

  I've marked the extended nodes with "+1". As you see, you have less nodes (34).

  I hope the tree reads correctly.

Good example for root. I think most everyone is convinced (or can be) that extending root causes >= nodes searched than extending farther down the tree. To me, this is kind of obvious as all the nodes extended near the leaves are of course a subset of the nodes extended at the root. It is not at all clear to me, however, that this kind of subset relationship holds for the original topic (extending a node where the highest ranked node is better than all others by a certain margin).

-Sam

[Jose Carlos]

Hmm, maybe I misuderstood Larry's question. I was only addressing this quote:

True, near the root the extension affects larger subtrees, but near the leaves the extension occurs vastly more often, so it is not obvious whether the extension costs more near the root or near the leaves in total. Can you explain why you think the total cost of all such extensions would be greater near the root than near the leaves?

[lkaufman]

I'll simplify and rephrase the question: Would always extending the first move near the root lead to a bigger tree than always extending the first move near the leaf?