Upper bound on proof tree size

[zullil]

A better estimate of the maximum number of nodes in a proof-tree (a DAG by any other name would smell as sweet) appears to be:

MAX_Nodes = 2 * sqrt( Number_of_possible_descendants ) / sqrt( b - 1 )

As a topologist, it's hard to call an object a "tree" if it contains cycles, even undirected ones.

For the upper bound I gave originally, I assumed:

1) All replies to the key are equally good. Not true for many positions, but certainly true for some.

2) Identical positions on the board that arise from different move sequences are counted as distinct nodes (and so too then for all children of such nodes).

Obviously it's (2) that caused the confusion.

I suppose that, in addition to the parameter b, one could add another parameter that bounds the fraction of distinct positions amongst the b^2 that arises from two consecutive moves by the side-to-be-mated. Roughly .5 I suppose ...

Not my type of fun, in any case. Good luck.

[Zenmastur]

As a topologist, it's hard to call an object a "tree" if it contains cycles, even undirected ones.

Well, I'm not a topologist, I'm a person and I intend to remain one for the rest of my life.

Second, I can hardly be blamed if people choose to name objects with words that don't describe what they are. Worse, things are often called one thing and are named something else. Worse yet some objects are named with descriptive words that describe something other than the object they are naming and then are called by some other term which may also be counter descriptive.

Third, while one can always use very precise technical language when discussing any subject it tends to limit the audience and can end up being more confused when not all members of the audience are equally adept in the subject matter.

Besides, more often than not, people hide behind the terminology they use. While I could write a dissertation on this topic, I'll just point out that the operative word in that sentence is "hide" and leave it at that.

For the upper bound I gave originally, I assumed:

1) All replies to the key are equally good. Not true for many positions, but certainly true for some.

2) Identical positions on the board that arise from different move sequences are counted as distinct nodes (and so too then for all children of such nodes).

Obviously it's (2) that caused the confusion.

I think the confusion is more likely the result of one person using the common usage of words and the other assuming some technical meaning to the same words.

I suppose that, in addition to the parameter b, one could add another parameter that bounds the fraction of distinct positions amongst the b^2 that arises from two consecutive moves by the side-to-be-mated. Roughly .5 I suppose ...

Not my type of fun, in any case. Good luck.

You seem to be implying that I have arbitrarily and capriciously altered the equation. That's not how I arrived at the first formula I gave in my last post. That equation is the result of trying to reconcile the iterative formula you gave and the idea that the total number of descendant node at depth "n" from the position in question have a relationship to each other. That relationship is sqrt(4/(b-1)). Since we can remove the 4 in the square root and replace it by a 2 outside the square root we get 2/sqrt(1/(b-1).

If you look back to the original post you'll see that I remarked that I thought the number should be 2*b^(n/2). This was an intuitive "guess" I made after having looked at the number of nodes in each ply of a few short proof-trees (Proof-DAGs if you prefer). The reason I guessed that this could be the formula was that I noticed that at each ply in a proof-tree (DAG), starting at the root the number of nodes increased. Somewhere around half the depth of the mate the number of nodes at each ply began to decrease. So it can be thought of as two right triangles that abut each other to create a third triangle. Thus the 2 in the equation. Since, the number of nodes in each successive ply didn't continue to increase past some middle point b^n didn't seem to work as an estimate of the number of nodes in the tree (DAG). But, since the decline began at approximately half the number of plies to the mate, b^(n/2) seemed to fit pretty well as a node estimator. This formed my first estimate.

The number b^(n/2) in this formula is wrong since it isn't a summations of all the nodes up to the current ply as it should be. This makes it an inaccurate node estimator. At this point I decided to work on something else for a while, which I did. When I came back to the problem I decided to create a spreadsheet so I could graph various quantities etc. This is when I saw that the number of nodes could be an iterative equation as you posted. I also noticed that the iterative formula and the equation above were on many occasions quite disparate in their predictions. Since I knew from looking at proof-trees (DAGs) that the number of nodes at each ply didn't continue to increase all the way until mate was given AND the iterative formula predicted more nodes than were possible in chess, it was easy for me to discard the iterative formula as inconsistent with previous observations and what was possible in a PROOF-DAG.

When I read Schaeffer and Lake's paper I read in to it more than was there. i.e. my mind jumped to what seemed to be obvious conclusions that weren't in their paper. The most important conclusion I drew from their paper was that the total possible number of unique positions that can be obtained with the given material could be used as an upper bound on the number of nodes in a proof-tree (DAG). i.e its a better nodes estimator

Then it occurred to me that even when this didn't produce a good bound part of the idea could still be used. i.e. when there is still lots of material on the board this bound is useless. But, if we are dealing with a mate in "n" moves the summation of all nodes reachable in 2*n-1 plies could be substituted instead of all "possible" descendant positions. When I started comparing the number of nodes that the iterative formula you gave predicts vice the summation of all nodes that can be reached in 2*n-1 plies I noticed that their ratio became constant if "n" was greater than some small number like 3 or 4. When I changed the branching factor the ratio changed with it. So I made a graph of this ratio that corresponded to each possible branching factor from 2 to 120 inclusive. I then tried to find a formula that would match the given curve. The third formula that I tried was sqrt((b-1)/4). I'm not sure why I tried this particular formula, but when I did all of the cells that I could see in the column in the spread sheet that contained the difference between the two quantities became small compared to the number being estimated. (the RSS value became a minimum) If the number being estimated was 10^15 then the error band was at least 14 orders of magnitude below this number.

After all the equations were reduced, rearranged and had superfluous terms removed I was left with what I posted. So, it may look like I Willy-Nilly added terms to the equation, but that's not what happened. I simply tightened the estimate so that it matched that of the iterative equation that you gave.

So if you take the equation that I gave and use the summation of all nodes up to ply 2*n-1 (for a mate in n) as the number of "possible" descendant nodes and compare the output to your iterative formula, both will give essentially the same answers. i.e. with very tight error bars. So this formula can be used instead of the iterative one.

On the other hand if you use my formula and insert the number of "possible" descendants from a position it will give a tighter bound than the previous formula that also used this type of node estimation. Therefore this is a more useful formula as it can do both types of estimation and the second type (using "possible" descendants) the bound is much tighter.

Regards,

Zen

[zullil]

I think the confusion is more likely the result of one person using the common usage of words and the other assuming some technical meaning to the same words.

Yeah, you shouldn't do that. As the rest of us know, a tree is a woody perennial plant, typically having a single stem or trunk growing to a considerable height and bearing lateral branches at some distance from the ground.

[Zenmastur]

Yeah, you shouldn't do that. As the rest of us know, a tree is a woody perennial plant, typically having a single stem or trunk growing to a considerable height and bearing lateral branches at some distance from the ground.

Unless we are talking about banana trees, in which case they resemble VERY large pieces of grass but are actually classified as flowering plants.


The Papaya tree is also not a tree but it does bear fruit.

Or bamboo which actually is a member of the grass family although in many places they are referred to as trees.

Bamboo grass is neither bamboo nor a grass.

Or tomatoes which are commonly referred to as vegetables but are actually a fruit.

And, of course, strawberries are commonly thought of as a fruit, but is neither fruit nor vegetable.

So what is one to do

Regards,

Zen