TTTML: a machine that learns tic-tac-toe
learning by playing itself, in APL, in the memory of a 1975 desktop computer

A board is 9 numbers, the squares row by row: 1 for X, ¯1 for O, 0 for an empty square. X always moves first, so whose turn it is can be read from the board: X's when the marks are even. SHOW draws one:

∇SHOW S;B
⍝ THE BOARD: X, O, AND A DOT FOR AN EMPTY SQUARE.
B←9 2⍴' '
B[;2]←'O.X'[S+2]
3 6⍴,B
∇

SHOW 1 ¯1 0 0 1 0 0 0 ¯1

X O .
. X .
. . O

A line is three squares, and there are eight: three rows, three columns, two diagonals. WL holds them as an 8 by 9 matrix of 0s and 1s, a row per line, so one inner product sums the board along every line at once. X has a line where a sum is 3, O where it is ¯3:

WL←8 9⍴1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0

WL+.×1 1 1 ¯1 ¯1 0 0 0 0

3 ¯2 0 0 0 1 0 0

OUTCOME reads the result from those sums: 1 when X has won, ¯1 when O has, 2 for a full board with no line, a draw, and 0 while the game goes on.

∇R←OUTCOME S;L
⍝ 1 X HAS WON, ¯1 O HAS, 2 A DRAW, 0 THE GAME GOES ON.
⍝ WL IS THE 8 LINES OF THE BOARD: A SUM OF 3 IS X'S LINE.
L←WL+.×S
R←2×~0∊S
→(~3∊L)/NX
R←1
NX:→(~¯3∊L)/0
R←¯1
∇

OUTCOME 1 1 1 ¯1 ¯1 0 0 0 0
OUTCOME 1 ¯1 1 1 ¯1 ¯1 ¯1 1 1
OUTCOME 1 ¯1 0 0 0 0 0 0 0

      OUTCOME 1 1 1 ¯1 ¯1 0 0 0 0
1
      OUTCOME 1 ¯1 1 1 ¯1 ¯1 ¯1 1 1
2
      OUTCOME 1 ¯1 0 0 0 0 0 0 0
0

A board turned a quarter or reflected is the same position to play: a corner opening is a corner opening in any of the four corners. The square has eight symmetries, and SYM lists them as eight rearrangements of the square numbers, so S[SYM] is all eight versions of a board S at once:

SYM←8 9⍴1 2 3 4 5 6 7 8 9 7 4 1 8 5 2 9 6 3 9 8 7 6 5 4 3 2 1 3 6 9 2 5 8 1 4 7 3 2 1 6 5 4 9 8 7 7 8 9 4 5 6 1 2 3 1 4 7 2 5 8 3 6 9 9 6 3 8 5 2 7 4 1

CODES names a position. Read as a base-3 number, 3⊥S+1, a board is a single integer; each of the eight versions has its own, and the least of the eight is the position's code. It takes a matrix, a board per row, and codes them all together:

∇C←CODES T;N
⍝ EACH ROW OF T AS A BASE-3 NUMBER, THE LEAST OF ITS 8
⍝ ROTATIONS AND REFLECTIONS (THE ROWS OF SYM).
N←1↑⍴T
C←⌊/(N,8)⍴3⊥⍉((N×8),9)⍴(T+1)[;,SYM]
∇

An X in the top left corner and an X in the top right are one position, and have one code; an X on an edge is another:

CODES 2 9⍴1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
CODES 1 9⍴0 1 0 0 0 0 0 0 0

      CODES 2 9⍴1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
9842 9842
      CODES 1 9⍴0 1 0 0 0 0 0 0 0
9844

Of the 5,478 positions a game can reach, 765 are different up to symmetry. That is the first saving.

What the machine learns is one number for each position it has met: how good that board, just after a move, has turned out to be for the player who made the move. Towards 1 is a win, towards 0 a loss, and 0.5 a draw – or no idea yet. This is the value of an afterstate, and it is the second saving: one number per board, where a table of every board and every move would need nine, and more memory than the machine had.

The model is two vectors: KEYS, the codes met so far, and VALS, their values. They are what training writes, so they are data, not code: 757 numbers each, too long to print here, in chunks <<var-keys>> and <<var-vals>> of the Org source. How many, and how much of the workspace is in use:

⍴KEYS
1048576-⎕WA

      ⍴KEYS
757
      1048576-⎕WA
17762

About 17 KB of the workspace is in use, the model and the program together: well inside 64 KB, with nothing to swap out to tape.

VALUE looks positions up, a matrix of boards at a time. One it has not seen before is added to the model, worth 0.5, so the table grows only with positions that play reaches:

∇V←VALUE T;C;N
⍝ WHAT EACH ROW OF T IS WORTH TO THE PLAYER WHO MADE IT.
⍝ A POSITION NOT SEEN BEFORE IS ADDED, WORTH 0.5.
C←CODES T
N←(KEYS⍳C)>⍴KEYS
N←N∧(⍳⍴C)=C⍳C
KEYS←KEYS,N/C
VALS←VALS,0.5+0×N/C
V←VALS[KEYS⍳C]
∇

VALUE 3 9⍴1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0

0.30922 0.36138 0.40962

To X's first move, the corner is worth a little less than the edge and the centre is worth most.

CHOOSE builds every board the player to move could make, one per empty square, as a single matrix – the board repeated, plus the mover's mark where P∘.=⍳9 puts it – values them all with one call to VALUE, and takes the best. The mover's mark is 1 or ¯1 as the number of marks already down is even or odd.

∇A←CHOOSE S;P;V;M
⍝ THE SQUARE WHOSE AFTERSTATE IS WORTH MOST TO THE MOVER.
P←(S=0)/⍳9
M←1-2×2|+/S≠0
V←VALUE(((⍴P),9)⍴S)+M×P∘.=⍳9
A←P[V⍳⌈/V]
∇

It opens in the centre, takes a win when there is one, and blocks one:

CHOOSE 9⍴0
CHOOSE 1 ¯1 0 ¯1 1 0 0 0 0
CHOOSE 1 1 0 ¯1 0 0 0 0 0

      CHOOSE 9⍴0
5
      CHOOSE 1 ¯1 0 ¯1 1 0 0 0 0
9
      CHOOSE 1 1 0 ¯1 0 0 0 0 0
3

GAME plays one game against itself, choosing as CHOOSE does but, when a draw of ?1000 falls under EPS, playing a random legal move instead, so that it keeps trying moves it now thinks are bad. It keeps every afterstate, a row of H per move, and learns from them once the game is over:

∇W←GAME EPS;S;H;A;P;M
⍝ ONE GAME AGAINST ITSELF, A RANDOM MOVE WHEN A DRAW OF ?1000
⍝ FALLS UNDER EPS, AND THEN LEARN FROM IT.
S←9⍴0
H←0 9⍴0
M←1
LOOP:P←(S=0)/⍳9
A←CHOOSE S
→(EPS≤(?1000)÷1000)/PUT
A←P[?⍴P]
PUT:S[A]←M
H←H,[1]S
W←OUTCOME S
M←-M
→(W=0)/LOOP
H LEARN W
∇

LEARN goes back through the game from the last move to the first, moving each afterstate's value a fifth of the way towards a target. For the last two moves the target is the result, as the player who made the move sees it: 1 won, 0 lost, 0.5 drawn. For an earlier move it is that player's next afterstate, two rows on, taken at 0.9 so that a sooner win is worth more than a later one. This is temporal-difference learning, as in Sutton and Barto's tic-tac-toe example: a win or a loss at the end reaches back, game by game, to the moves that led to it.

∇H LEARN W;I;J;N;T
⍝ MOVE EACH AFTERSTATE A FIFTH OF THE WAY TO ITS MOVER'S NEXT
⍝ ONE, TAKEN AT 0.9 SO A SOONER WIN IS WORTH MORE, OR TO THE
⍝ RESULT: 1 WON, 0 LOST, 0.5 DRAWN.
I←KEYS⍳CODES H
N←⍴I
J←N
BACK:T←(W=2)×0.5
T←T+W=1-2×0=2|J
→(J≥N-1)/SET
T←0.9×VALS[I[J+2]]
SET:VALS[I[J]]←VALS[I[J]]+0.2×T-VALS[I[J]]
J←J-1
→(J>0)/BACK
∇

TRAIN forgets everything and learns again from N games, saying every thousand how many positions it knows and how many bytes are still free. Its result is how many games X won, O won, and were drawn. The workspace ships already trained, since a 1975 machine would have taken far longer over it than sw-apl does; here it relearns from 3,000 games:

∇R←TRAIN N;K
⍝ FORGET, THEN LEARN FROM N GAMES AGAINST ITSELF. R IS HOW
⍝ MANY X WON, O WON AND WERE DRAWN. EVERY 1000 GAMES IT SAYS
⍝ HOW MANY POSITIONS IT KNOWS, AND THE BYTES STILL FREE.
KEYS←VALS←⍳0
R←0 0 0
K←0
L:R←R+(GAME 0.1)=1 ¯1 2
K←K+1
→(0≠1000|K)/NEXT
'GAMES ';K;'  POSITIONS ';(⍴KEYS);'  FREE ';⎕WA
NEXT:→(K<N)/L
∇

TRAIN 3000

GAMES 1000  POSITIONS 754  FREE 1030674
GAMES 2000  POSITIONS 754  FREE 1030674
GAMES 3000  POSITIONS 754  FREE 1030674
886 323 1791

To see how well it has learned, AGAINST plays one game with the machine as one side, ME, and a player moving at random as the other; TRIAL plays N games as X and N as O, and counts. Each row is won, lost and drawn:

∇W←ME AGAINST S;M;P
⍝ ONE GAME, THE MACHINE AS ME (1 X, ¯1 O), THE OTHER SIDE
⍝ MOVING AT RANDOM. W IS THE OUTCOME.
S←9⍴0
M←1
L:P←(S=0)/⍳9
→(M=ME)/MINE
S[P[?⍴P]]←M
→NEXT
MINE:S[CHOOSE S]←M
NEXT:W←OUTCOME S
M←-M
→(W=0)/L
∇

∇R←TRIAL N;K;ME
⍝ N GAMES AS X, THEN N AS O, AGAINST A RANDOM PLAYER. EACH ROW
⍝ OF R IS HOW MANY THE MACHINE WON, LOST AND DREW.
R←2 3⍴0
K←0
L:ME←1-2×K≥N
R[1+K≥N;]←R[1+K≥N;]+(ME AGAINST 0)=ME,(-ME),2
K←K+1
→(K<2×N)/L
∇

TRIAL 100

99 0 1
94 0 6

It does not lose. PLAY is a game against you. Your moves are read with ASK, which uses quad input and asks again for anything that is not an empty square:

∇PLAY N;S;M;W;A;YOU
⍝ PLAY THE MACHINE: N IS 1 TO MOVE FIRST, AS X, OR 2 TO LET
⍝ IT BEGIN. THE SQUARES ARE 1 TO 9, ROW BY ROW.
YOU←1 ¯1[N]
S←9⍴0
M←1
L:→(M≠YOU)/MINE
SHOW S
S[ASK S]←M
→NEXT
MINE:A←CHOOSE S
'I TAKE ';A
S[A]←M
NEXT:W←OUTCOME S
M←-M
→(W=0)/L
SHOW S
→(W=2)/DRAW
→(W=YOU)/WON
'I WIN.'
→0
WON:'YOU WIN.'
→0
DRAW:'A DRAW.'
∇

∇A←ASK S
⍝ YOUR MOVE, READ WITH QUAD: AN EMPTY SQUARE, 1 TO 9.
L:'YOUR MOVE, 1 TO 9:'
A←,⎕
→((1≠⍴A)∨~∧/A∊⍳9)/BAD
A←A[1]
→(S[A]=0)/0
BAD:'THAT IS NOT AN EMPTY SQUARE.'
→L
∇

Here it moves first, as X, and the answers typed at the ⎕: prompts are 5 (taken, so refused), 3, 4 and 2. It sets up two threats at once and wins:

PLAY 2
5
3
4
2

      PLAY 2
I TAKE 5
 . . .
 . X .
 . . .
YOUR MOVE, 1 TO 9:
⎕:
      5
THAT IS NOT AN EMPTY SQUARE.
YOUR MOVE, 1 TO 9:
⎕:
      3
I TAKE 7
 . . O
 . X .
 X . .
YOUR MOVE, 1 TO 9:
⎕:
      4
I TAKE 8
 . . O
 O X .
 X X .
YOUR MOVE, 1 TO 9:
⎕:
      2
I TAKE 9
 . O O
 O X .
 X X X
I WIN.

∇DESCRIBE
'TTTML -- A MACHINE THAT LEARNS TIC-TAC-TOE BY PLAYING'
'ITSELF, THEN PLAYS YOU WITH WHAT IT LEARNED. IT COMES'
'TRAINED.'
''
'   PLAY 1       PLAY IT, YOU MOVING FIRST, AS X'
'   PLAY 2       PLAY IT, IT MOVING FIRST'
'   TRIAL N      N GAMES EACH SIDE AGAINST A RANDOM PLAYER:'
'                WON, LOST AND DRAWN, AS X THEN AS O'
'   TRAIN N      FORGET, AND LEARN AGAIN FROM N GAMES'
'   SHOW S       A BOARD OF 9 SQUARES, 1 X, ¯1 O, 0 EMPTY'
''
'THE SQUARES ARE NUMBERED 1 TO 9, ROW BY ROW. WHAT IT LEARNS'
'IS A VALUE FOR EACH POSITION IT HAS MET, KEYS AND VALS, A'
'POSITION AND ITS 7 ROTATIONS AND REFLECTIONS COUNTED AS ONE:'
'ABOUT 750 OF THEM, AND 12,000 BYTES.'
∇

DESCRIBE

TTTML -- A MACHINE THAT LEARNS TIC-TAC-TOE BY PLAYING
ITSELF, THEN PLAYS YOU WITH WHAT IT LEARNED. IT COMES
TRAINED.

   PLAY 1       PLAY IT, YOU MOVING FIRST, AS X
   PLAY 2       PLAY IT, IT MOVING FIRST
   TRIAL N      N GAMES EACH SIDE AGAINST A RANDOM PLAYER:
                WON, LOST AND DRAWN, AS X THEN AS O
   TRAIN N      FORGET, AND LEARN AGAIN FROM N GAMES
   SHOW S       A BOARD OF 9 SQUARES, 1 X, ¯1 O, 0 EMPTY

THE SQUARES ARE NUMBERED 1 TO 9, ROW BY ROW. WHAT IT LEARNS
IS A VALUE FOR EACH POSITION IT HAS MET, KEYS AND VALS, A
POSITION AND ITS 7 ROTATIONS AND REFLECTIONS COUNTED AS ONE:
ABOUT 750 OF THEM, AND 12,000 BYTES.

A saved workspace is APL that could have been typed. It opens with lines that say what it is and names itself; then come its variables and its functions, each in the order )SAVE writes them, by name. The ⍝!LINK line is the random link it was saved with, so a run that loads it draws the same random numbers every time, which is why the examples above come out the same.

⍝ sw-apl workspace. Re-executable APL: loading it runs it.
⍝!MODES (B)
⍝!SOURCE sw-apl -- written for this repository. MIT, (c) 2026 Michael A Wright.
⍝!SAVED 21.39.13 09/22/26
⍝!LINK 1547632030
⍝!ORIGIN 1
⍝!DIGITS 5
⍝!WIDTH 64
)WSID TTTML

The assembly, in the file's order; tangling the document writes the workspace:

<<workspace-header>>
<<var-keys>>
<<var-sym>>
<<var-vals>>
<<var-wl>>
<<fn-against>>
<<fn-ask>>
<<fn-choose>>
<<fn-codes>>
<<fn-describe>>
<<fn-game>>
<<fn-learn>>
<<fn-outcome>>
<<fn-play>>
<<fn-show>>
<<fn-train>>
<<fn-trial>>
<<fn-value>>

samples/81-tttml.apl plays two games and trains it again, as a transcript, and docs/learn-tic-tac-toe-strategy.md gives the design and the measurements.