pycgt

Combinatorial game theory in pure Python — exact canonical forms, thermography, and game values.

>>> from pycgt import parse, render, temperature, mean
>>> from pycgt.rulesets import domineering

>>> render(domineering.rectangle(2, 4))
'Miny(2)'
>>> temperature(domineering.rectangle(2, 3))
Fraction(5, 4)
>>> render(parse("{1|-1}") + parse("{1|-1}"))
'0'

pip install pycgt. Python 3.11+, no dependencies.

The one idea everything rests on

Short games are exact objects built from the empty game up. Two values are equal, or one is greater, or they are confused with each other — there is no tolerance to set, no rounding, and no floating point anywhere. Temperatures are Fractions found by bisection on an exact dyadic grid.

The operation that makes this usable is canonical form. Two games of the same value reduce to identical canonical forms, so structural equality becomes value equality and comparison becomes a dictionary lookup. Every Game returned by this library is canonical, which is why == means what you want.

Why it exists

CGSuite is the established tool in this field and is far more complete than this. But it is a Java desktop application: not pip install-able, awkward to drive from a script, and unavailable in a notebook or in CI. Getting it to answer one batch of questions headlessly took a from-source Maven build and a JDK version pin.

pycgt is for when you want game values inside ordinary Python. It has no dependencies, so it also runs unchanged under Pyodide in a browser.

What's here

Games are only partially ordered, so <= and >= are defined but < and > deliberately are not — not (G <= H) does not imply G > H. Use compare() for the four-way answer, which includes confused.

>>> from pycgt import compare, STAR, ZERO
>>> compare(STAR, ZERO)
<Relation.CONFUSED: '||'>

A worked example

examples/berlekamp_1988.py reproduces Berlekamp's Blockbusting and Domineering (1988) — his Table III sequences, their period-5/saltus-1 structure, and the overheating bound from Appendix B.1 — and checks the results against the paper.

$ python examples/berlekamp_1988.py
  period 5, saltus 1: holds
  x_1 is the only non-number: 1*
  ok    G_2 = tiny-2
  ok    G_3 = +-1 + 2*tiny-2

Correctness

The interesting values in this field are easy to get subtly wrong, so nothing here is trusted because it looks right. The test suite validates against external sources:

• CGSuite — canonical forms, temperatures and means of Domineering 2×n boards, generated by driving CGSuite 2.2 headlessly.
• Berlekamp (1988), Blockbusting and Domineering, Appendix B.1 — his exact values for the 2-wide Domineering rectangles, G₂ = tiny-2 and G₃ = ±1 + 2·tiny-2.
• Wolfe, via Guy's Problem 4 in Games of No Chance — the 4×5 board is 1.
• Uiterwijk, arXiv:1305.3257 — the value of the 11×2 board.
• Closed forms — Nim sums follow exclusive-or; Hackenbush strings give the expected dyadic rationals; Cram values are nimbers.

Plus internal laws that catch real bugs: G + (−G) = 0, transposing a Domineering board negates its value, ish(G) is always infinitesimal, and canonical form is idempotent.

Provenance

Implemented clean-room from the mathematics — Winning Ways, Siegel's Combinatorial Game Theory, and Berlekamp (1988). CGSuite is GPL; its source was consulted only for the API needed to run it as a test oracle, and none of its implementation was used or ported. This library is MIT.

Limitations

Honest about scope:

• Short games only. No loopy games, stoppers, or on/off.
• No misère theory and no misère quotients.
• Slower than CGSuite, which is a JVM program with far more optimisation. Expect exact Domineering values up to about 2×16 comfortably.
• The number-temperature convention (a number with denominator 2**k has temperature −1/2**k) is checked against CGSuite for 0 and 1/2 only.

Licence

MIT.