The same position, written once

What a value costs to write down counted the symbols in every canonical form born by day three, found that the canonical form is smallest in options and in nothing else, and closed by naming an object it had not built:

A canonical form written with its repetitions shared — each distinct subposition named once, each reference a pointer — is a strictly smaller object with the same content.

It gave one number for that object and left three questions beside it. This is the census, and the third of the three has an answer that is exact.

Three prices for one object #

A canonical form is a tree. {1 | ∗} has a root, a Left option written 1, a Right option written ∗, and each of those is itself a tree with options of its own. Writing it out means writing every node of that tree, and a node that occurs in two places is written twice.

It need not be. Two occurrences of ∗ inside one form are the same position — not two positions that happen to be worth the same, the same object, reached by two routes — and a position reached eleven ways is one position is the essay about exactly that identification. Naming each distinct subposition once and pointing at it thereafter gives a directed graph with the same content and fewer nodes.

So there are three things to count and they are three different questions:

• the tree cost — every node, every time it is written, which is what a printed expression costs;
• the shared cost within one form — the distinct subpositions of that form, which is what storing that value costs a program;
• the shared cost across a day — the distinct subpositions of any form of the day, which is what storing the whole construction costs.

The first two differ by how repetitive a single value is. The second and third differ by how much the day’s values have in common, and the gap between them is the surprising one.

The saving grows #

Day one is four values written in eight nodes, of which seven are distinct: a saving of an eighth. Day two is twenty-two values in 102 nodes, sixty-six distinct: a saving of a third. Day three is 1,474 values in 24,940 nodes, 10,102 distinct: a saving of three fifths.

The proportion is not settling. It grows by roughly the same factor each day, which is what would happen if the depth of a typical form grew while the pool of things that can sit at the bottom of it grew more slowly — and that is exactly the shape of the construction, since the options of a day-three form are day-two values and there are only twenty-two of them.

Nearly every form on day three repeats something. Fourteen hundred and sixty-seven of the 1,474 do — 99.5 per cent — and the seven that do not are the seven integers, whose canonical forms are chains with a different value at every level. That is the same seven that came out unique on the repetition census, arriving here from the other side: a form with no repeat in it is a form sharing cannot shrink.

The most repetitive form of the day is ∗3, at 6.75 nodes written for every distinct node it contains. The median is 2.40. So a typical day-three value is written out about two and a half times larger than it needs to be, and the worst is nearly seven times.

There is a second way to read the growth and it is the one that says why it should be expected. A day-three canonical form has options born by day two, and each of those has options born by day one, and day one has four values in it. So the bottom two levels of any day-three form are drawn from a pool of twenty-two and then a pool of four, while the number of places in the form where such a value can sit grows with the width and the depth. Repetition is forced by counting long before it is forced by anything about the values: a form with eleven leaves and four things to put in them repeats.

That reading also predicts where the saving is largest, and the prediction holds with a correction worth making because the obvious version of it is wrong. The forms with the highest ratios are the ones whose two option lists are short, shallow and nearly the same — {0, ∗ | 0, ∗, ∗2} and {0, ∗, ∗2 | 0, ∗} at 4.50, {↑, ∗ | 0, ∗, ∗2} and {0, ∗, ∗2 | ↓, ∗} at 4.40 — because writing the list twice writes every option in it twice before anything below is counted.

The tempting way to say that is the nimbers, and the nimbers do not behave that way. ∗3 is the extreme case of the day at 6.75 and it is the only nimber anywhere near the top: ∗2 sits 249th at 3.00, ∗ sits 1,420th at 1.50, and 0 is on the floor at 1.00 with the integers. What the top of the ranking holds is nimber-like forms — options drawn from 0, ∗ and ∗2 on both sides — and the nimbers themselves are spread across the whole of it, because a nimber’s ratio depends on how many options it has and the small ones have almost none.

One node per value #

The third column is where the arithmetic stops being a matter of degree.

Across the whole of day three, the number of distinct subpositions occurring in any canonical form is 1,474 — which is the number of values in the day, exactly.

That is not a coincidence and it is not quite a triviality either. The subpositions of a canonical form born by day three are canonical forms born by day two or earlier, and every value born by day two is born by day three as well, so every subposition is a day-three value. That gives one inequality. The other is that every day-three value occurs as a subposition of some day-three form, and it holds because a value is a subposition of itself.

Both directions are asserted rather than assumed: the census compares the set of subpositions it finds with the set of values it was given, and refuses to draw anything if the two differ.

So the whole day’s canonical forms, written as one shared graph, cost one node per value. Twenty-four thousand nine hundred and forty nodes of writing collapse to 1,474 objects — a saving of 94.1 per cent, against the 59.5 per cent available inside a single form.

The practical reading is that a program storing a day should not store forms at all. It should store the day, once, and let each value be a node in it. That is what a memo table is, and it is why the evaluator on this site is fast enough to enumerate day three: the sharing is not an optimisation applied to the output, it is the shape the computation already has.

What it buys a reader, which is nothing #

It is worth saying plainly that none of this changes what a value is, and the essay would be a worse one if it pretended otherwise.

The shared form and the tree form are the same canonical form. They are equal in every company, they have the same options, they win against the same opponents, and a figure drawn from one is a figure drawn from the other. What changes is the count of objects a machine has to hold, and the count of objects is not a property a reader can observe.

So the honest claim is narrow and it is still worth making: the sentence “the canonical form is the smallest form of its value” is true in options, true in a sense that is checkable, and silent about two other measures that a program actually pays. This page supplies the second of them, the rung below supplied the first, and neither is the one the reduction minimises.

The two costs disagree about which value is dear #

If the tree cost and the shared cost were the same question in different units, ordering the day by one would order it by the other. They are not.

The correlation between the two, over all 1,474 values, is 0.795. Nine hundred and eighty-nine of the 1,474 — two in three — move more than a hundred places between the two rankings.

The widest value of the day by tree cost is { {1 | 0, ∗}, ↑, ↑∗ | {0, ∗ | −1}, ↓, ↓∗} at thirty-seven nodes, and it is also the widest by shared cost at eleven — so the extreme agrees. Below the extreme the two part company at once. A form with six options drawn from a small set of positions is long and cheap; a form with three options drawn from three unrelated positions is short and dear.

That is a distinction with a meaning. The tree cost is what a reader pays: how much has to be printed on the page, how much has to be read. The shared cost is what a program pays: how many distinct things have to be in memory. A value can be tedious to read and cheap to hold, and the two are not close to the same property.

What it does not do to the canonical form #

The obvious hope, once the shared form is in hand, is that it might be the better normal form — smaller, still unique, and reducible in its own right. Two of those three are true and the third is the one that matters.

It is unique, and trivially so: the canonical form of a value is unique, the shared form is a function of the canonical form, so the shared form is unique too. Nothing is gained by asking.

It is smaller, by the numbers above.

And the reduction does not operate on it. Domination compares two options and deletes one; bypassing a reversible option replaces it with the option list of the answer. Both are operations on the option lists at the root, and in a shared graph an option list at the root may contain a pointer to a node that is also pointed at from three levels down. Deleting it from the root does not delete it, and bypassing puts a whole list back whose members may already be present elsewhere in the graph. The reduction can be run on the tree and the result shared afterwards, which is what happens here; running it on the graph directly is a different algorithm and nothing on this site is it.

The seven that share nothing #

The integers are worth a paragraph because they are the exception to nearly everything on this page.

An integer’s canonical form is a chain: 3 is {2 | }, and 2 is {1 | }, and so on down to nought. Every node in it is a different value, so nothing repeats, so sharing saves nothing at all — a ratio of exactly 1.00, which is the minimum the census records and which seven values attain.

They are also the cheapest values of the day by both measures at once, which is the only place the two rankings are forced to agree: a form with no repetition has the same tree cost and shared cost by definition, so an integer sits on the diagonal of the plot above rather than in the fan.

And they are the values a reader is least likely to think of as cheap, because three is a bigger number than a half and its form is deeper. That is the birthday’s usual joke: the small-looking values are the late ones and the plain-looking ones are deep.

What the equality is really saying #

The three counts — 24,940, 10,102 and exactly 1,474 — are three ways of writing the same collection down, and the last of them is the one worth turning over, because it is an equality rather than a measurement.

Naming each distinct subposition once across the whole day costs one node per value of the day. That is not a coincidence about day three and it is not a compression result. It is the statement that the values of a day are closed under taking options: nothing appears inside a canonical form of day three that is not itself a value born by day three or earlier.

Once that is said the number is forced. A shared graph over the day has one node per distinct object appearing anywhere in it, the objects appearing are exactly the day’s own values, and there are 1,474 of them. Nothing about the notation, the reduction or the counting enters.

So the three numbers are measuring three different things and only the first two are about writing. 24,940 is the cost of a tree, 10,102 is the cost of a tree with sharing inside each form, and 1,474 is not a cost at all — it is the size of the object the other two are unrollings of.

That reframes the whole comparison. The gap between 24,940 and 1,474 is not evidence that the notation is wasteful; it is the difference between a graph and its unrolling, which is the same difference routes and positions measures in a search. Braces write a tree because a tree is what a linear notation can write, and the object underneath was always a graph on the day’s own values.

What the census does not say #

Three limits, and the first is about what “cost” is being measured.

A pointer is counted as free. The shared cost here is a count of distinct subpositions and nothing else; a real representation pays for the references as well, and a node with six options costs six pointers whether or not they point at anything new. Counting those would narrow the gap and would not close it, since the pointer count is bounded by the tree size and the whole saving is in the nodes.

The whole-day figure is about a day, not about a corpus. One node per value is exact because the values of a day are closed under taking options. A collection of positions from actual games — the gamut sweep, say — is not closed under anything, and its shared cost would have to be measured rather than derived.

And the growth is three points. An eighth, a third, three fifths is a clear trend and it is three numbers. Whether it approaches a limit below one, and where, is a question about day four, and day four is not a computation this machinery reaches: it would need every antichain of a poset of 1,474 elements.

The convention, named #

Normal play, and every count is over canonical forms. The tree cost counts nodes rather than printed characters, so the braces, bars and commas of the written notation are not in it; that is a different measure and it is the one the size census uses, which is why the totals here and there are not the same number.

Two subpositions are the same when their canonical forms are identical, which on this site is a comparison of one key rather than a search — the identification made explicit in an essay of its own and relied on ever since.

Where the ladder goes next #

The reversibility anchor has four rungs: that bypassing is not a contraction, that the growth it produces does not survive, that the form it produces is smallest in one currency only, and now what a second currency does to the ranking.

The rung above is the reduction on the graph. Domination and bypassing are operations on option lists and the shared form has no option lists in the same sense, so a reduction that worked on it would have to be stated differently — presumably as a rewriting of a graph rather than a deletion from a list. Whether such a thing exists, and whether it reaches the same fixed point, is a piece of work with a definite finish and nothing here is it.

Two neighbours are worth the trip. A position reached eleven ways is one position is where the identification this page rests on is established, and where the saving is measured on a search rather than on a form. And how wide a form can get is the width measurement that the two cost columns here disagree with: the widest form of the day is not the dearest to store, and until this census there was no second opinion to notice that with.