Notakto X-only tic-tac-toe, misère

Both players draw X's. Pick any board, mark any empty cell. A board with three in a row is dead. Whoever kills the last board loses. The computer plays perfectly: every board gets a value in an 18-element monoid, and a position is a second-player win exactly when the product of the values lands in P = {a, b², bc, c²}. With hints on, each cell shows whether the move wins (W) or loses (L).

the monoid Q

checked

the 2013 note, re-checked

The dictionary

The 46 boards without a line, up to rotation and reflection, with their values. Dead boards are 1. Boards in play are outlined.

Why a monoid

In normal play (last move wins) a sum of games is solved by Sprague–Grundy: each board is worth a nim-heap and the heaps add by XOR. In misère play that breaks: one empty board is worth a heap of 1 in normal play, and misère nim says a single heap of 1 is a loss for the player to move — but the empty board is a win (take the centre). Plambeck's misère quotients replace the nim-heaps by elements of a finite commutative monoid that is specific to the game. For 3×3 Notakto it has 18 elements.

How it was checked

The 18 elements come from the seven relations by Knuth–Bendix completion (the relations are already confluent). The dictionary is the one printed in the note. The proof that it decides every sum is finite: whether a sum is P depends only on the product and, for each kind of board present, the product of the rest, so a breadth-first walk over those states (285,480 of them) checks all sums of all sizes at once. Plain game search on every sum of up to six boards agrees. Change any one of the 46 live entries to any other element and the proof fails; the only other dictionaries that work rename d.