Combinatorial Game Theory
who wins, and by how much
Generator

What it costs to decide the winner

What it costs to decide the winner
What it costs to decide the winner. Three families of game, each at several sizes, with the number of distinct positions an exhaustive solver must evaluate beside the work its closed form does. The bars are logarithmic. Hardness is not about the size of the board or the length of the rules — Domineering has the shortest rule here — it is about whether anybody has found the shortcut.

Three families of game, each at several sizes, with the number of distinct positions an exhaustive solver must evaluate beside the work its closed form does. The bars are logarithmic. Hardness is not about the size of the board or the length of the rules — Domineering has the shortest rule here — it is about whether anybody has found the shortcut.

1 essay calls cost-curve. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

Where it is called

Changing this generator changes every one of these figures.

What it costs to decide the winner. Three families of game, each at several sizes, with the number of distinct positions an exhaustive solver must evaluate beside the work its closed form does. The bars are logarithmic. Hardness is not about the size of the board or the length of the rules — Domineering has the shortest rule here — it is about whether anybody has found the shortcut. What it costs

The game with the shortest rule is the hard one

Deciding a generalised board game is PSPACE-complete, which is a statement about families and encodings rather than about size. Nim in the same subject is settled by one pass over the input at any size, and green Hackenbush by one pass over the edges — while Domineering, whose rules take a single line, has no shortcut anybody has found.

The whole library · The position index · The figures that play back