Half a licence is nearly all of it

A product against a sum priced what a restricted universe gives a solver. If two positions are equal in a company, a solver working inside that company may replace one by the other — and on Cram sums that licence is worth 4 to 25 times on two components and 24 to 161 on three. It closed on a weaker licence nobody had priced:

The rung above is the partial licence. Three of the seven companies are closed under addition and not under options, and a solver in one of them may rewrite components and not subpositions — a strictly weaker shortcut nobody has priced. Whether half a licence is worth half the saving or almost none is a measurement of the same shape as this one.

Neither. It is worth nearly the whole saving.

What the two licences permit #

A company closed under addition licenses replacing a component of a sum by an equal game. That is what makes the sum decomposable: a solver may evaluate each board on its own and combine the answers, instead of searching the product of their state spaces.

A company closed under options as well licenses replacing a subposition — a position arising inside a component’s own search. In practice that means the solver may key its table on the game rather than on the board and the occupancy: a position arising in one component is answered from work done in another, and a position is answered from its own mirror image.

The measurement is a count of distinct states each solver has to tell apart, which is machine-independent and is the quantity a licence actually reduces.

Rewriting components is nearly the whole of it #

On a 3 × 4 board plus a 3 × 5, a solver with no licence has to distinguish 1,679,700 states. Allowed to rewrite components, it distinguishes 3,604 — a saving of 466 times. Allowed to rewrite subpositions as well, it distinguishes 884, which is 4.1 times better again.

Across the seven sums the first half averages 135 times and the second 5. So half a licence is not worth half the saving and it is not worth almost none: it is worth nearly all of it, and the answer to the rung below’s question is that the two halves are not comparable quantities at all.

The reason is structural rather than accidental. The component licence removes a product: without it the state is a tuple of occupancies and the space is the product of the components’ spaces, so its saving grows like the product itself and rises with every board added. The subposition licence removes duplication: it folds together states the solver would otherwise visit twice, and how much duplication there is does not grow with the board in the same way.

The evidence for that reading is in the range. The first half’s value runs from 9 to 466 across the seven sums; the second half’s runs from 4.1 to 8.3, on the same sums, whose products differ by a factor of five thousand. A saving that does not grow with the problem is a saving of a different kind.

And the one place the second half is worth most is the sum whose two components are the same board, where every shape found in one is found in the other. That is the clearest possible statement of what the subposition licence does: it shares work between components rather than reducing any component’s own search.

And the same licence again, on the pieces #

There is a third step and it is the same licence used once more. A Cram position whose free squares fall into disconnected pieces is a sum, so the substitution applies to it too: each piece may be replaced by an equal game, and a solver may key its table on the piece rather than on the position.

That takes 884 shapes to 14 region shapes on the largest sum — a further 63 times — and the striking thing is the column rather than the ratio. Across all seven sums the region count is 4, 9, 10, 11, 10, 10, 14. It is nearly constant while the product runs from 324 to 1.7 million.

That is what a catalogue is. Once the licence is applied to the pieces, the number of things a solver must know stops depending on the position in front of it and starts depending on the game — which is why the board falls apart prices decomposition as the operation that makes an evaluator possible at all, and why when the catalogue starts paying is a question about the game rather than about the board.

Why a product and a duplication are different kinds of saving #

The two halves are worth different amounts for a reason worth setting out, because it says which half a solver should care about as its problems grow.

Searching a sum with no licence at all means the state is the whole board — every component’s occupancy at once — so the number of states is the product of the components’ counts. Two boards of a thousand positions each give a million states, three give a thousand million. That is the cost the component licence removes, and its saving is therefore the product divided by the sum: with $n$ components of $m$ states each, $m^n / (nm)$, which grows without bound in both $n$ and $m$.

The subposition licence removes something else. Given the decomposition, each component is searched alone and its states are its own positions; what the licence adds is that two of those states, in different components or in the same one, may turn out to be the same game and be answered once. How many such coincidences there are is a property of the game’s shapes — how often a Cram position of nine free squares looks like another — and there is no reason for it to grow with the number of components at all.

So the first half is a structural saving, and it is the one a bigger problem needs more of; the second is a statistical one, and it is roughly constant. The seven sums confirm that shape rather than establishing it: the first half’s value climbs monotonically with the product and the second’s does not move.

That also explains the one outlier in the tables. The 3 × 4 plus 3 × 4 sum has by far the largest second-half saving, at 8.3 times against everything else’s 4 to 5, and it is the sum whose two components are the same board — so every shape reached in one is reached in the other and the coincidence rate is as high as it can be.

Which companies actually have which licence #

The whole distinction rests on there being companies with one closure and not the other, and there are.

Equal in this company sets out what a company is: a set of games a solver promises to stay inside, with equality measured only against members of it. Of the seven finite companies this site has found, three are closed under addition and not under options — so a solver working in one of them genuinely has the partial licence and no more, and the measurement above is about a real situation rather than a hypothetical one.

The ones closed under both are exactly the nimber groups, which is the rung below’s finding and is what makes the full licence rare. So the ordinary case for a solver in a restricted universe is the partial licence — and the measurement here says that is the case worth having.

What a solver should do with this #

The measurement has a practical reading and it is worth stating, because the two halves of the licence cost different amounts to obtain.

Take the component licence always. It is the difference between a product and a sum, it is what every restricted universe with any closure at all provides, and it is cheap to use: decompose, evaluate, combine. Nothing here suggests a situation where it is not worth having.

Take the subposition licence when it is free. For Cram it is nearly free — the table is keyed on a canonical shape instead of on an occupancy, which costs a normalisation per lookup and buys four to eight times. For a game where deciding whether two subpositions are equal in the company is itself a search, the arithmetic would go the other way, and equal in every company is where the cost of deciding equality properly is set out.

And decompose the pieces. The third step is the largest on the largest sums and it is the one that makes the state count stop growing. A solver that decomposes components and not their pieces is leaving the biggest factor on the table — which is the same conclusion the board falls apart reaches from the other direction, by pricing the flood fill that finds the pieces.

What this does not say #

The two halves are measured in one order. Rewriting components then rewriting subpositions is the sequence a solver would use, and the numbers are the marginal value of each step in that order. Taken the other way round — a solver that keyed a table on shapes but did not decompose — the split would be different, and that solver is not one anybody would build.

Cram, and small boards. Every sum here is two Cram boards of at most twenty squares, and the state counts are exact. Whether the first half’s advantage keeps growing at four components or twenty is the same measurement one size up, and the product’s growth suggests it does.

Distinct states, not time. A licence that halves the states does not halve the running time, since the bookkeeping differs — a shape-keyed table costs more per lookup than an occupancy-keyed one, because the key has to be computed. What the counts measure is the size of the problem a solver faces, which is the quantity a theorem about companies can speak to.

The subposition licence is modelled by a shape-keyed table. That is a faithful reading of a subposition may be replaced by an equal game for Cram, where two positions with the same free-square shape are the same game. In a company where equality is coarser than identity of shape the licence would be worth more, and this measurement is a floor for it.

The counts include the terminal positions. A state with no move left is still a state a solver visits and tells apart from the others, so the counts are of everything the table holds rather than of the internal nodes only. That inflates all four columns by the same kind of amount and does not touch the ratios.

And the region step is not a third licence. It is the second one applied twice, and it is separated in the tables because it is where the counts stop growing. A solver holding the full licence may take it; a solver holding only the partial one may not, since the pieces of a position are subpositions.

Why the cheap half is worth the most #

The result inverts what a reader would expect and it is worth deriving, because the inversion is forced rather than measured.

The component licence collapses a product. With $k$ components each having $s$ times fewer classes than positions, the state space goes from a product of $k$ position-sets to a product of $k$ class-sets — a saving of $s^k$, exponential in the number of pieces.

The subposition licence collapses inside a component. It shrinks each factor once, by a fixed amount, and does nothing about how many factors there are.

So the first is exponential in $k$ and the second is not, and on a board with several pieces the first has to dominate. That is arithmetic rather than a finding, and the measurement’s job is to say by how much on a real board — a million and a half states to three thousand six hundred, then to eight hundred and eighty-four.

The awkward part is which of the two is harder to obtain. The component licence needs closure under addition, which many companies have. The subposition licence needs closure under forming options, which almost nothing has — it picks out the nimber groups exactly among the finite closed companies.

So the expensive property buys the small saving and the cheap one buys the large. A reader looking for a restricted universe to work in should therefore stop at addition-closure, which is available for far more companies, and treat option-closure as a bonus rather than as the goal — which is the reverse of the order the theory presents them in.

The chain, read as one thing #

Standing back from the four columns, the whole table is one substitution applied at four scales, and it is worth reading it that way.

At the coarsest scale the position is the board, and there is nothing to substitute: the solver must hold every configuration of everything at once. At the next the position is a component, and equal components may be interchanged — so the board becomes a list of independent problems. At the next the position is a subposition, and equal subpositions may be interchanged — so the list of problems becomes a shared body of knowledge. At the finest the position is a region, and the shared body of knowledge becomes a catalogue that does not grow.

Each step is the same theorem — equal games are interchangeable in a sum — applied to a smaller object. The reason it keeps paying is that a smaller object recurs more often, and the reason it eventually stops is that the smallest objects are the ones a catalogue can hold outright.

That is the whole argument for restricted universes as a practical tool rather than a theoretical one, and the numbers say where the tool’s value is: 1,679,700 to 14 across four steps, with the first step carrying two orders of magnitude and the last carrying most of the rest.

The convention, named #

Normal play throughout: a player who cannot place loses. Cram is the impartial game in which both players place dominoes either way up, so every position is a win or a loss outright.

A company is a set of games a solver stays inside; two games are equal in a company when they are interchangeable in every sum with a member of it. A company is closed under addition when the sum of two members is a member, and closed under options when every option of a member is one.

A licence is what closure permits: closure under addition licenses replacing a component of a sum, closure under options licenses replacing a subposition as well.

The counts are of distinct states each solver must tell apart — tuples of occupancies with no licence, occupancies per board with the component licence, free-square shapes up to the eight symmetries of the square with the subposition licence, and connected region shapes when the licence is applied to the pieces.

The eight symmetries are the reflections and rotations of the square. Cram is symmetric under all of them because both players place the same pieces, which is what makes a shape-keyed table legitimate; the same table would be wrong for Domineering, where the two players see different games.

Where the ladder goes next #

The universes anchor has five rungs: restricted equality made computable, which restrictions license rewriting a sum, which license rewriting a subposition, what the second licence is worth when it exists, and now what the first is worth on its own.

The rung above is the number of components. Every measurement here is two boards, and the first half’s saving is the ratio of a product to a sum — so it should grow roughly like the state space of each board added, while the second half’s should not move. Three and four components would say whether that is right, and it would turn a comparison of two numbers into a comparison of two growth rates, which is the form the answer wants to be in.

Two neighbours are worth the trip. Equal in this company is where the whole apparatus is set out and where the seven companies are found, and it is what makes the partial licence a real object rather than a hypothetical one. And a position reached eleven ways is one position is the other saving a solver makes, and reading the two together separates them cleanly: memoisation collapses repeated positions, and the licence collapses different positions that are the same game.