This machine, made of K’nex and paper, plays a perfect game of tic-tac-toe: it never loses, and it always forces a win (immediate or deferred) if possible. The opponent can be X or O (X goes first), and can make any legal move. The opponent informs the machine of the opponent’s move, and the machine then reports its own move.

Rather than representing the game state as a board position, the machine represents the state as a point in a four-dimensional phase space, one dimension for each of the opponent's four moves. (The machine's own moves needn't be represented since those introduce no extra degrees of freedom, with respect to the fixed strategy that the machine implements. The opponent’s fifth move, if the opponent is X, needn’t be represented, because it fills the board and ends the game.)

The machine has a lookup table that associates each (legal) point in the phase space with the machine's pre-computed optimal move for the corresponding game state. The machine performs analog addition and multiplication to index into the 4D table, and displays the move stored there. (Digital arithmetic in Tinkertoy/K’nex would be orders of magnitude bulkier than the analog implementation.)

Because the phase-space representation uses a 1-1 mapping between the opponent’s moves and the dimension indexes, each dimension index can be specified by a simple user action to input the next move via a token of the appropriate length.

Each phase-space dimension has 10 positions (the 9 board squares, plus no-move-yet). But the center square is unavailable to the opponent except on her initial move when she is X (and on that move, no table entry is required for the no-move-yet state); so the table can be compressed to 9⁴, implemented as a physically two-dimensional 81² array. The other two dimensions use a standard strided memory layout. There are separate arrays for playing X and O, printed on opposite sides of the output sheet.

Each array cell is 2 mm on a side, for a total length of 16 cm (the outermost row and column turn out to be blank). The analog components need to have a tolerance of about ±0.25 mm. A $20 trimmer cuts paper input-tokens to lengths within that tolerance. The output sheet is mounted on four clips that adjust the position within that tolerance. Each sliding pointer is inherently accurate enough in the slider’s lateral position. Setting the pointer’s angle is trickier; it needs to be correct to within about a tenth of a degree in order to keep the lateral error within bounds at the most distant points. The connection to the upper track extension provides angular stability, and rotating the upper white rod deflects the stabilizer to adjust the pointer angle over a range of a few degrees to within the required tolerance.

The machine’s volume (convex hull) is roughly 0.01 m³. The machine consists of 93 K’nex parts, plus a few dozen pieces of paper (and four binder clips). That’s two orders of magnitude more compact than the version that inspired it:

http://www.rci.rutgers.edu/~cfs/472_html/Intro/TinkertoyComputer/TinkerToy.html 

Here's an inventory of K'nex parts for the tic-tac-toe machine.

(Click thumbnails for full photos.)