an overview of distress
DISTRIBUTION-ESTIMATING SEARCH

The conceit of the algorithm is returning a prob­a­bil­ity dis­tri­bu­tion rather than a value. Supposing that we’ve an eval­u­a­tion func­tion that does so, which we will con­sult at the leaves of the search tree, we are left with two pro­ce­dures to determine:

• q1 a procedure that yields a dis­tri­bu­tion given the dis­tri­bu­tions of the suc­ces­sors of a position.
• q2 a procedure that selects a suc­ces­sor of a posi­tion to explore, or alter­na­tively, a pro­ce­dure that allo­cates a given amount of time among the suc­ces­sors of a position.

The prob­a­bil­ity dis­tri­bu­tions may be over centi­pawn or wdl scores,* *By which I mean expected outcome. but we will gen­er­ally assume the latter so that the sup­port is bounded, and the dis­tri­bu­tions may be either con­tin­u­ous or dis­crete — with domain of any car­di­nal­ity, such as dis­tri­bu­tions over { loss, draw, win} or the inter­val from −1 to +1 sub­divided into any number of parts.

* By wdl score I mean expected outcome.

This first pro­ce­dure might be riven in twain:

• q1^a modelling (i ) the belief that a suc­ces­sor is optimal — which is not a dis­tri­bu­tion^† †For example, if two moves are believed to be optimal and are equally believed to be optimal, we would assign them both a value of 1 rather than ½. over the successors — or, alter­na­tively, con­triving (ii ) a dis­tri­bu­tion of the belief that a suc­ces­sor of a posi­tion would be played were the posi­tion the root, or (iii ) both, or (iv) some­thing else entirely, which we will broadly refer to as a policy.
• q1^b producing a dis­tri­bu­tion given not only the dis­tri­bu­tions of the suc­ces­sors of a posi­tion but also a policy.

Note that the policy may also be of use in answering q2.

† For example, if two moves are believed to be opti­mal and are equally believed to be optimal, we would assign them both a value of 1 rather than ½.

In two thousand twenty one, before having con­sid­ered the prob­lem as a whole and decom­posing it as above, I con­sid­ered q1 only and bluntly began down the following path.

The maximum of two random var­i­ables ${\mathrm{X}}_0$ and ${\mathrm{X}}_1$ with prob­a­bil­ity den­sity func­tions ${\mathrm{p}}_0$ and ${\mathrm{p}}_1$ and cumu­la­tive dis­tri­bu­tion func­tions ${\mathrm{q}}_0$ and ${\mathrm{q}}_1$,

$${\mathrm{q}}_{\mathrm{i}}(\mathrm{x})=\mathrm{P}({\mathrm{X}}_{\mathrm{i}}\le \mathrm{x})={\int }_{-}^{\mathrm{x}}{\mathrm{p}}_{\mathrm{i}}(\mathrm{t})\mathrm{d}\mathrm{t}$$

if ${\mathrm{X}}_0$ and ${\mathrm{X}}_1$ are inde­pen­dent, has the cumu­la­tive dis­tri­bu­tion func­tion

$$\mathrm{P}(\text{max}({\mathrm{X}}_0\text{,}{\mathrm{X}}_1)\le \mathrm{x})={\mathrm{q}}_0(\mathrm{x})\times {\mathrm{q}}_1(\mathrm{x})\text{.}$$

I used dis­tri­bu­tions over centi­pawn score, and instead of work­ing with the dis­tri­bu­tions directly, I rep­re­sented them with three sum­mary sta­tis­tics: the peak (the median or mean), the right-hand dispersion (the dif­fer­ence between the peak and the ninety-fifth per­cen­tile if I recall correctly), and the left-hand dis­per­sion (. . . the fifth per­cen­tile). My hope was to find an accept­able approx­i­ma­tion of the effect of $\text{max}(\text{–}\text{,}\text{–})$ on the sum­mary sta­tis­tics. I did not succeed.

Four years later, I returned to the subject and began to con­tem­plate it more com­pletely, writing the following:

Let N be the number of suc­ces­sors, and then con­sider four quantities:

• s −1 to +1 estimated score
• v 0 to ? uncertainty of score estimate ( from “variance” )
• f 0 to 1 probability posi­tion is subs­tan­tially better than expected ( from “fortuitous” )
• c 0 to 1 probability posi­tion is subs­tan­tially worse than expected ( from “catastrophic” )

Informally, the quantities s and v are meant to describe the bulk of the dis­tri­bu­tion and the quan­ti­ties f and c are meant to describe the tails (“the dis­tri­bu­tion” here being the dis­tri­bu­tion of belief about the true score of the position).

When switching perspectives, s negates, v remains the same, and f and c swap.

The variables s, v, f, and c can also be indexed, e.g.

• f (i) c of the i-th successor (the position that follows from making the i-th move)
• c(i) f of the i-th successor

Then also consider:

• b(i) current belief that the i-th move is the best move or is as good as the best move
• p(i) probability of picking the i-th move

The move with the highest p (which is also the move with the highest b) is the one we’d pick if this were the root. Here I’m treating b(i) as in the range 0 to 1 and ini­tial­ized to ½ or 1 / N or ini­tial­ized depending on s(i) and v(i) — but should it be log odds and ini­tial­ized to 0, or something else?

When we write “$\sum \text{· · ·}$ ”, this is shorthand for “$\sum \text{· · ·}$ from $\mathrm{i}=\text{1}$ to $\mathrm{i}=\mathrm{N}$”.

The p(i) obey the property that $\sum \mathrm{p}(\mathrm{i})=\text{1}$ ; in other words, it’s a distribution.

Perhaps the b(i) are also a dis­tri­bu­tion, and perhaps further b(i) and p(i) should be the same. As a the­o­ret­i­cal matter, they are distinct; if all moves are pre­cisely equally good, b(i) should be 1 for all i, but p(i) should be 1 / N. And p(i) should depend on v(i), f (i), and c(i) in addi­tion to s(i), but b(i) may depend only on s(i).

In some sense, the c of a posi­tion is the f of the suc­ces­sor you will pick.

$${\mathrm{c}}_{\text{pick}}=\sum \mathrm{c}(\mathrm{i})\times \mathrm{p}(\mathrm{i})$$

In another sense, the c of a posi­tion is the prob­a­bil­ity that all suc­ces­sors are cata­strophic, since it only takes one of them being okay for the position to not be catastrophic.

$${\mathrm{c}}_{\text{opt}}=\prod \mathrm{c}(\mathrm{i})$$

The relevance of that obser­va­tion depends on our belief that we’d be able to find the right move if this posi­tion became the root, so we blend the two with some factor β:

$$\mathrm{c}={\mathrm{c}}_{\text{opt}}\times \mathrm{\beta }+{\mathrm{c}}_{\text{pick}}\times (1-\mathrm{\beta }).$$

This can be done asym­metrically — we may pick a higher β for our oppo­nent than our­selves if we think they are less likely to make a mistake.

Similarly, ${\mathrm{f}}_{\text{pick}}=\sum \mathrm{f}(\mathrm{i})\times \mathrm{p}(\mathrm{i})$ and the probability that any suc­ces­sor is fortuitous is

$${\mathrm{f}}_{\text{opt}}=1-\prod (1-\mathrm{f}(\mathrm{i})).$$

We blend the two: $\mathrm{f}={\mathrm{f}}_{\text{opt}}\times \mathrm{\beta }+{\mathrm{f}}_{\text{pick}}\times (1-\mathrm{\beta }).$

There is a defect: it oughtn’t make a dif­fer­ence whether a bad move has a high chance of being unex­pect­edly worse or not.

Because of this defect, and a dis­sat­is­fac­tion with the arbi­trar­i­ness and lack of the­o­ret­i­cal simplicity, I aban­doned this line of thinking as well.

This brings us to my ongoing endeavour. I have resolved to use dis­crete dis­tri­bu­tions over the inter­val from −1 to +1 sub­divided into S parts. For q1^a we will use a dis­tri­bu­tion of the belief that the suc­ces­sor of a posi­tion would be played were the posi­tion the root. Then q1^b be­comes rather simple: let $\mathrm{\pi }(\mathrm{i})$ for $\mathrm{i}=1\text{,}\text{. . .}\text{,}\mathrm{N}$ be the policy for the N suc­ces­sors and ${\mathrm{p}}_{\mathrm{i}}(\mathrm{x})$ for $\mathrm{x}=1\text{,}\text{. . .}\text{,}\mathrm{S}$ be the prob­a­bil­ity mass func­tion returned by the search of a successor. The var­i­able x indexes the sub­in­ter­vals,
so x = 1 refers to the inter­val from −1 to −1 + 2/S and x = S refers to the inter­val from +1 − 2/S to +1; more generally, x refers to the inter­val from −1 + 2/S × (x−1) to −1 + 2/S × x. Then the dis­tri­bu­tion $\mathrm{r}(\mathrm{x})$ we will return is

$$\mathrm{r}(\mathrm{x})=\sum _{\mathrm{i}=1}^{\mathrm{N}}\mathrm{\pi }(\mathrm{i})\times {\mathrm{p}}_{\mathrm{i}}(\mathrm{x})\text{.}$$

Now we define q1^a. Consider again two ran­dom var­i­ables ${\mathrm{X}}_0$ and ${\mathrm{X}}_1$ with prob­a­bil­ity den­sity func­tions ${\mathrm{p}}_0$ and ${\mathrm{p}}_1$ and cumu­la­tive dis­tri­bu­tion func­tions ${\mathrm{q}}_0$ and ${\mathrm{q}}_1$. If ${\mathrm{X}}_0$ and ${\mathrm{X}}_1$ are inde­pen­dent, then

$$\mathrm{P}({\mathrm{X}}_0\le {\mathrm{X}}_1)={\sum _{\mathrm{x}}}_1^{\mathrm{S}}({\sum _{\mathrm{y}}}_1^{\mathrm{x}}{\mathrm{p}}_0(\mathrm{y}))\times {\mathrm{p}}_1(\mathrm{x})$$

or more simply

$$\mathrm{P}({\mathrm{X}}_0\le {\mathrm{X}}_1)={\sum _{\mathrm{x}}}_1^{\mathrm{S}}{\mathrm{q}}_0(\mathrm{x})\times {\mathrm{p}}_1(\mathrm{x})\text{.}$$

We can extend this to three ran­dom var­i­ables:

$$\mathrm{P}({\mathrm{X}}_0\le {\mathrm{X}}_2\wedge {\mathrm{X}}_1\le {\mathrm{X}}_2)=\sum _{\mathrm{x}}{\mathrm{q}}_0(\mathrm{x})\times {\mathrm{q}}_1(\mathrm{x})\times {\mathrm{p}}_2(\mathrm{x})\text{.}$$

And more generally,

$$\mathrm{P}(\underset{\mathrm{k}}{\bigwedge }{\mathrm{X}}_{\mathrm{k}}\le {\mathrm{X}}_{\mathrm{i}})=\sum _{\mathrm{x}}(\prod _{\mathrm{k}\ne \mathrm{i}}{\mathrm{q}}_{\mathrm{k}}(\mathrm{x}))\times {\mathrm{p}}_{\mathrm{i}}(\mathrm{x})\text{.}$$

This is our belief that the i-th successor is optimal (at least as good as any other successor).

After normalization, these terms become our policy:

$$\mathrm{s}={\sum }_{\mathrm{i}=1}^{\mathrm{N}}\mathrm{P}(\underset{\mathrm{k}}{\bigwedge }{\mathrm{X}}_{\mathrm{k}}\le {\mathrm{X}}_{\mathrm{i}})$$ $$\mathrm{\pi }(\mathrm{i})=\mathrm{P}(\underset{\mathrm{k}}{\bigwedge }{\mathrm{X}}_{\mathrm{k}}\le {\mathrm{X}}_{\mathrm{i}})/\mathrm{s}\text{.}$$

There may be numer­i­cal dif­fi­cul­ties when N is large because of the product $\prod {\mathrm{q}}_{\mathrm{k}}(\mathrm{x})$, which might vary wildly in mag­ni­tude depend­ing on the value of x, but this com­pletes q1 in concept.

I suspect that q2 admits no sim­i­larly simple answer. Much like how α/β search* *Depth-first minimax search with iterative deepening, α/β pruning, and zero-window pruning. is effec­tively made a best-first search through the heuristic appli­ca­tion of reduc­tions and exten­sions,^† †Whether by reducing/extending some nodes directly according to some criteria or by uniformly applying late move reduction and ordering successors according to some criteria. the most suc­cess­ful pro­ce­dure is likely to be found empir­i­cally, perhaps as a syn­the­sis of var­i­ous methods. Like in α/β search, online learning is apt to be indispensable.

* Depth-first minimax search with iter­a­tive deep­ening, α/β pruning, and zero-window pruning.

† Whether by reducing/extending some nodes directly according to some crite­ria or by uniformly applying late move reduc­tion and ordering suc­ces­sors according to some criteria.

At nodes for which we happen to have saved infor­mation about the suc­ces­sors’ dis­tri­bu­tions, it may be rea­son­able to start by dividing time in pro­por­tion to $\mathrm{\pi }(\mathrm{i})$, or if vis­i­ta­tion counts are also avail­able, by dividing time in proportion to

$$\mathrm{\pi }(\mathrm{i})+\mathrm{c}\sqrt{\frac{\text{log}{\sum }_{\mathrm{k}}\mathrm{v}(\mathrm{k})}{\mathrm{v}(\mathrm{i})}}$$

for some constant c, analogous to ucb1, or perhaps

$$\mathrm{\pi }(\mathrm{i})+\mathrm{c}\mathrm{A}(\mathrm{i})\frac{\sqrt{{\sum }_{\mathrm{k}}\mathrm{v}(\mathrm{k})}}{1+\mathrm{v}(\mathrm{i})}$$

where c is scaled by roughly the square root of the var­i­ance and $\mathrm{A}(\mathrm{i})$ is an adjusting heuristic, analogous to puct. Note the absence of a log­a­rithm in this second formula.

Then search can pro­ceed by iter­a­tive deep­ening, giving a node count to approx­i­mately divy out recur­sively and pro­gres­sively searching with higher counts.

This cannot work as stated. Repeat­edly taking the mix­ture of dis­tri­bu­tions, as in our pre­scrip­tion of $\mathrm{r}(\mathrm{x})$ for q1^b, can only increase the var­i­ance, but we would expect the var­i­ance to gen­er­ally decrease as draught increases. On the other hand, repeat­edly taking the max­i­mum of two bounded ran­dom var­i­ables will reduce var­i­ance. This suggests that the idea of blending r_opt and r_pick was a decent one, as it addresses a fun­da­men­tal problem.

By r_opt we mean the dis­tri­bu­tion whose cumu­la­tive dis­tri­bu­tion func­tion is ${\prod }_{\mathrm{i}}\mathrm{q}(\mathrm{x})$ and by r_pick we mean $\mathrm{r}(\mathrm{x})$ as it was defined above.

It is tricky matter, avoiding degen­eracy under repeated appli­ca­tion into either a flat or a narrow dis­tri­bu­tion, dif­fusing or col­lapsing quickly. What process would push the var­i­ance toward a stable value, but could be over­come given prov­o­ca­tion?

We might con­sider two pos­sible prin­ciples at play:

• A sharp policy (that is, having only a few good options, with a wide gap between those options and the remaining successors) should be cause for wari­ness, because the risk of catas­trophe is higher,* *We have been blithely neglecting the fact that the scores of suc­ces­sors are almost cer­tainly not inde­pen­dent. If the most prom­ising suc­ces­sor turns out to be unex­pect­edly bad, it is some­what likely the other emi­nent suc­ces­sors will be worse than believed hitherto. and the var­i­ance should per­haps remain the same or increase mildly. In such cases we would inter­po­late almost entirely toward r_pick.
• A wide policy (that is, having many similar options) should be cause for con­fi­dence in the eval­u­a­tion,^† †Separately, it is also jus­ti­fi­ca­tion to begin focusing on a sub­set of suc­ces­sors, as it is rel­a­tively safe to do so; a desire to dif­fer­en­ti­ate the suc­ces­sors would pro­vide an impetus to do so. because the con­se­quence of a indi­vi­dual error is less­ened, and so the var­i­ance should per­haps decrease. In such cases we would inter­po­late toward r_opt.

To put it more suc­cinctly, low dis­per­sion in the policy drives inter­po­la­tion toward r_pick and high dis­per­sion drives inter­po­la­tion toward r_opt. This estab­lishes some degree of neg­a­tive feedback.

* We have been blithely neglecting the fact that the scores of suc­ces­sors are almost cer­tainly not inde­pen­dent. If the most prom­ising suc­ces­sor turns out to be unex­pect­edly bad, it is some­what likely the other emi­nent suc­ces­sors will be worse than hitherto believed.

† Separately, it is also jus­ti­fi­ca­tion to begin focusing on a sub­set of suc­ces­sors, as it is rel­a­tively safe to do so; a desire to dif­fer­en­ti­ate the suc­ces­sors would pro­vide an impetus to do so.

At the present time, it remains an open ques­tion how this ought to be car­ried out exactly, or what heuris­tics ought to mod­ify it. This essay was last updated on the fif­teenth day of Feb­ru­ary in the two thou­sand twenty sixth year of the common era.