A reduction that reads a graph

The same position, written once measured what sharing buys. A game form written as a tree repeats every subposition it reaches more than one way; written as a graph, with identical subforms identified, it is smaller — and on day three, much smaller. That page closed on the thing sharing appears to make impossible:

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.

It exists, it is short, and it reaches the same fixed point. And it does not inherit the saving.

The two rewritings #

A node in the shared form carries its own outgoing edges — the Left edges to its Left options, the Right edges to its Right options. That is not an option list in the sense the reductions are usually stated in, because the same node is on the far end of several other nodes’ edges, but it is enough.

The distinction is worth making sharply, because it is the whole of why the rung below thought this was blocked. In a tree, deleting an option means deleting a subtree: the option and everything under it goes, because nothing else reaches it. In a graph, deleting an edge deletes an edge — the node it pointed at may still be reached from three other places and stays where it is. So the operation that reads as remove this option in one representation reads as remove this reference in the other, and only the second is well defined when things are shared.

Domination deletes an edge. At node G, if two Left edges lead to a and b with b at least as good for Left as a, the edge to a goes. That is a comparison between two of G’s own children and it is decided by G’s edges alone.

Bypassing replaces an edge. At node G, if the Left edge to a leads somewhere from which Right has a reply aᴿ with aᴿ ≤ G, then the edge to a is replaced by edges to each of aᴿ’s Left options. That comparison is against G itself, which is a step further out, and it is still decided at G.

So both are rewritings at a node. Neither needs an option list; each needs the node’s edges and the values below them, which the graph has. The forms in the sweep average five and a half nodes before the reduction and three and a half after, in about one and a half rewritings each, and 170 of the 250 get strictly smaller.

That the answer is yes and takes two paragraphs to say is worth noting, because the rung below expected it to be harder. What made it look hard is the assumption that a reduction has to be a rewriting of the node — and it is not.

There is one thing the graph version has to get right that the tree version never faces, and the sweep would fail if it did not. Bypassing adds edges: the edge to a is replaced by edges to aᴿ’s Left options, which are nodes already in the graph. In a tree those options would be copied, and the form would grow — which is what the first rung of this anchor measured. In a graph they are already there and the rewriting adds references rather than material, so the node count can fall even when the form is getting wider. Both numbers are real and they are measuring different things.

The order does not matter #

A rewriting system that reaches different answers depending on which rewriting is applied first is not a reduction. So the sweep runs each form three ways: always the first rewriting available, always the last, and one chosen at random.

All three agree on the value, on all two hundred and fifty forms. All three agree on the number of nodes left, which is the stronger claim and the one that could have failed by itself — a system can be confluent on values and still leave graphs of different sizes, since a rewriting that deletes an edge can orphan a node another order would have kept. And the value all three reach is the canonical form computed the ordinary way.

That is the whole of what confluence has to mean here, and it means the graph rewriting is a reduction and not merely a procedure that happens to terminate.

It is worth saying what would not have followed from confluence on values alone. Two orders reaching the same value would leave open whether the graph is the right object to reduce — one order might leave a graph twice the size of another’s, both correct, and then the reduction would have no canonical output and the shared form would be a representation nothing can normalise. The node-count agreement is what rules that out, and it is checked separately for exactly that reason.

The sweep also bounds itself. It refuses a form that has not reached a fixed point in two hundred rewritings, which is a guard against a rewriting system that cycles — bypassing adds edges, so termination is not obvious from the shape of the rules, and a system that added an edge it later removed and re-added would spin. Nothing here spins, and the average is one and a half rewritings, but the guard is what makes that a measurement rather than an assumption.

What the sharing does not buy #

The reason the rung below thought this was hard turns out to be a real difficulty, in a different place. Sharing makes the form small; the question is whether it makes the reduction small.

It would, if a rewriting were a property of a node. A node reached from six parents would be examined once and every parent would benefit.

It is not. Reversibility compares an option’s reply against the parent, so the same node is reversible under one parent and irreversible under another. Over eleven thousand forms and forty-one thousand parent-option pairs there are twenty-eight distinct option nodes; twenty-two of them — four fifths — answer differently under different parents. The Right option worth 1 is reversible under three hundred and ninety-two parents and not under a thousand and seventy-eight.

So the rewriting belongs to the edge, not to the node. Reducing a shared form means visiting every edge in the context of the node it leaves, which is exactly the number of visits the tree version needed. The graph is smaller to store and the reduction over it is the same size it always was.

That is not a defect of the rewriting; it is a fact about what reversibility is. The test aᴿ ≤ G has G in it, and any test with the parent in it cannot be answered once per node.

The numbers are worth reading carefully, because twenty-eight nodes sounds small beside eleven thousand forms and it is the right count. The forms are built by choosing option sets from fourteen day-two values, so every option of every form is one of those fourteen, on one side or the other — twenty-eight possibilities, and each of them turns up under hundreds of different parents. That is a pool designed to make the sharing extreme, which is what makes the split visible: with twenty-eight nodes and forty-one thousand pairs, any node whose answer were a property of the node would be answering the same question fifteen hundred times.

Twenty-two of them are not. The six that never split are the ones whose answer is no under every parent in the pool — an option with no reply that reaches back anywhere — and those are constant for a reason that is about the option and not about the sharing.

What separates the two operations #

Domination and bypassing come out of this looking less alike than they usually do.

Domination’s comparison is between two children of one node. It never mentions anything above the node, so the answer is a property of the node’s own edge set — and if two parents happened to share both the node and its edges, they would share the answer.

Bypassing’s comparison reaches up. It asks whether a reply from below gets back to at least where the parent already is, and that is a statement about the parent. The reduction that puts options back is where this anchor first found that bypassing behaves unlike domination — it can make a form wider, where domination only ever makes it narrower — and the two facts are the same fact seen twice. An operation that reads the parent can add material from below and an operation that reads only siblings cannot.

Read that way, the rung below’s expectation was right about the shape and wrong about the target. Something does fail to carry over to the graph, and it is not the statement of the reduction; it is the economics.

The economics, stated #

Put the two halves together and the account is this.

Storing a day-three form as a graph rather than a tree saves what the previous rung measured, and the saving is real: identical subpositions appear once. Reducing that form costs one visit per edge, which is what reducing the tree cost, because the reduction is a function of the edge and not of its target.

So sharing is a representation saving and not an algorithmic one, at least for this operation. That distinction is worth having explicitly because the two usually travel together — a smaller representation is normally a cheaper thing to work on — and the reason they part here is stated rather than mysterious.

The same distinction has a practical edge for anything that stores forms. A collection of day-three values held as shared graphs is smaller than the same collection held as trees, and it is smaller in a way that survives: the sharing is across values as well as within them, since every subposition of a day-three form is itself a day-three value. What this page says is that the moment one of those stored forms is reduced there is no discount, and the reduction is the operation anybody storing forms is most likely to want.

There is a mild consolation in the direction of use. A form that has already been reduced is canonical, and a canonical form has no reversible options at all — that is what canonical means — so the expensive test never fires on a stored collection of canonical forms. The cost falls entirely on the forms arriving from somewhere else, which is where it was always going to fall.

There is one thing the graph does buy for the reduction and it is not nothing: the comparisons. Deciding whether b ≥ a is a search, and comparison is a search that this site has priced; in a shared form the same comparison is asked for by many edges and can be answered once. So the visits do not compress and the work inside each visit does. That is a smaller claim than the rung below was hoping for and it is the one the measurement supports.

It is also the shape of saving that a memo would give without any graph at all. Caching comparisons by the pair of values compared is a change to the comparison routine, not to the representation, and it would deliver the same benefit to a tree. So the honest position is that the graph’s contribution to the reduction is a saving the tree could have had anyway, and its contribution to storage is one the tree could not.

That leaves the shared form as a good thing to keep and not a good thing to work in, which is the opposite of the usual advice about compressed representations and is worth stating plainly rather than leaving implied.

What a graph reduction would have to be to pay #

It is worth setting out what the alternative would look like, because naming it is what makes the negative result precise rather than merely disappointing.

A rewriting that paid for the sharing would be one whose applicability is a property of the node — decidable from the node’s own edges and the values below, with no reference to anything above. Domination is such a rewriting. If it were the only one, the reduction of a shared form would cost one visit per node and the graph would save work in exactly the proportion it saves storage.

Bypassing is not, and the obstruction is not a detail of how it is stated. Its whole content is that an option can be answered so well that the option was never worth offering — and worth offering compared to what is the position it is an option of. Removing the parent from the test would be removing the test.

What could still be true is that the parent enters only through a bounded summary of itself. If reversibility depended on the parent only through, say, its stops, then a node would need one answer per stop-pair rather than one per parent, and the sharing would pay in proportion. Nothing here rules that out and nothing here supports it: the twenty-two split nodes are split, and this sweep has not asked what the parents that answer yes have in common. That is a well-defined question and it is the one worth asking next.

What the restatement preserves #

Moving the two reductions from deletions to rewritings is not a change of definition, and the reason it is not is the whole licence for doing it.

A deletion says which option to remove from a list. A rewriting says what to do at a node. On a tree the two coincide, because a node has exactly one parent and its option list is unambiguous. On a shared graph the list does not exist and the rewriting still does — so the restatement is what carries the reductions across, and it carries the canonical form with them because the fixed point is the same object either way.

Where the ladder goes next #

The reversibility anchor has five 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, what a second currency does to the ranking, and now the reduction stated on the shared form.

The rung above is the memoised comparison. This page ends by claiming that the graph saves comparisons rather than visits, which is asserted from the shape of the algorithm and not measured — the sweep counts rewritings and not the comparisons underneath them. Instrumenting the comparison and counting how many are repeats within one form’s reduction would put a number on the only saving the graph turns out to offer, and the number could easily be small: a form of five nodes has few pairs to compare, and the pool here is small forms.

It is also worth reading beside what a value costs to write down, which prices a form in symbols rather than in nodes: the two currencies rank forms differently, and this page adds a third — the number of edges the reduction has to visit — which agrees with neither.

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 the reduction that puts options back is where bypassing was first found to behave unlike domination, which is the same asymmetry this page meets in a different currency.