librarylib/TTTML.xtl
TTTML: a machine that learns tic-tac-toe by playing itself (a standard library, built into xetal), ported from the TTTML workspace of sw-apl's library 1. Import it with an alias of your choice: "t:" u_se< "TTTML". docs/literate/tttml.org explains it; the demos demos/tttml.xtl, demos/tttml-train.xtl and demos/tttml-play.xtl use it.
A board is 9 numbers, the squares row by row: 1 for X, -1 for O, 0 for an empty square. X moves first, so the board says whose turn it is: X's when it sums to 0. What the machine learns is a model: two rows, the codes of the positions met and their values. Only the functions that roll dice end in !.
Boards
ˡs̲how : Int -> Char
t:s_how s: board s drawn as 3 rows of text: X, O and a dot for an empty square.
"t:" u̲se< "TTTML"
ᵗs̲how 1 -1 0 0 1 0 0 0 -1 X O . . X . . . O
ˡs̲how ← { s → 3 6 r̲eshape (1 + (s + 2) '× t̲able 0 1) s̲elect " O.X" }
ˡlines : Int
The 8 lines (3 rows, 3 columns, 2 diagonals) as rows of 0s and 1s: one inner product sums a board along every line.
ˡlines ← 8 9 r̲eshape 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
ˡo̲utcome : Num a => Int -> a
t:o_utcome s: the state of board s: 1 X has won (a line sums to 3), -1 O has (-3), 2 a draw (a full board), 0 the game goes on.
"t:" u̲se< "TTTML"
ᵗo̲utcome 1 1 1 -1 -1 0 0 0 0 1
ᵗo̲utcome 1 -1 1 1 -1 -1 -1 1 1 2
ᵗo̲utcome 0 0 0 0 0 0 0 0 0 0
ˡo̲utcome ← { s → l ← ˡlines '+ '× i̲nner s 3 m̲ember? l ? 1◆ -3 m̲ember? l ? -1◆ 0 m̲ember? s ? 0◆ 2 }
Positions and the model
ˡsymmetries : Int
The 8 symmetries of the square, each a row rearranging the 9 squares (turns and reflections).
ˡsymmetries ← 8 9 r̲eshape 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
ˡc̲ode : Num a => a -> a
t:c_ode s: the code of board s. A board read as a base-3 number names it; the least of its 8 names (one per symmetry) is the code, the same for a board turned or reflected.
"t:" u̲se< "TTTML"
ᵗc̲ode 1 0 0 0 0 0 0 0 0 9842
ᵗc̲ode 0 0 1 0 0 0 0 0 0 9842
ˡc̲ode ← { s → 'm̲in r̲/ 3 d̲ecode o̲\ 1 + ˡsymmetries s̲elect s }
ˡempty : Float
The model that knows nothing yet: two rows (codes, values) of no positions. Training starts from it.
"t:" u̲se< "TTTML"
t̲ally 1 s̲elect ᵗempty 0
ˡempty ← 2 0 r̲eshape 0.5
ˡv̲alues : Float -> Float -> Float
m t:v_alues c: what the positions with codes c, each just after a move, are worth in model m to the player who made it: towards 1 a win, towards 0 a loss, 0.5 a draw. A code not met yet is worth 0.5.
ˡv̲alues ← { m c → ((1 s̲elect m) i̲ndexOf c) s̲elect (2 s̲elect m) c̲at 0.5 }
ˡv̲alue : Num a => Float -> a -> Float
m t:v_alue s: what board s is worth in model m to the player who just moved (t:v_alues of its code).
"t:" u̲se< "TTTML"
ᵗempty ᵗv̲alue 1 0 0 0 0 0 0 0 0 0.5
ˡv̲alue ← { m s → m ˡv̲alues f̲loat ˡc̲ode s }
ˡa̲fter : (Num a, Truthy a) => a -> Int -> a
s t:a_fter a: the board once the player to move (X when s sums to 0, else O) takes square a, 1 to 9.
"t:" u̲se< "TTTML"
(0 0 0 0 1 0 0 0 0) ᵗa̲fter 1 -1 0 0 0 1 0 0 0 0
ˡa̲fter ← { s a → s + (1 − 2 × '+ r̲/ s) × (r̲ange 9) = a }
Playing
ˡc̲hoose : (Num a, Truthy a) => Float -> a -> Int
m t:c_hoose s: the best move in model m for the player to move on board s: the empty square (1 to 9) whose board is worth most.
ˡc̲hoose ← { m s → p ← w̲here s = 0 v ← m ˡv̲alues '{ a → f̲loat ˡc̲ode s ˡa̲fter a } e̲ach p (v i̲ndexOf 'm̲ax r̲/ v) s̲elect p }
ʰp̲ick! : (Num a, Truthy a) => Float -> a -> Int
m h:p_ick! s: the move on board s, the best in model m but one time in ten a random empty square, so that it keeps trying moves it now thinks are bad.
ʰp̲ick! ← { m s → p ← w̲here s = 0 (r̲oll! 10) = 1 ? (r̲oll! t̲ally p) s̲elect p◆ m ˡc̲hoose s }
ʰp̲lay! : Float -> Int -> Int
m h:p_lay! g: game g (its boards so far, a board per row) played on to the end by model m against itself, moves from h:p_ick!.
ʰp̲lay! ← { m g → s ← (t̲ally g) s̲elect g played ← g c̲at 1 9 r̲eshape s ˡa̲fter m ʰp̲ick! s 0 = ˡo̲utcome (t̲ally played) s̲elect played ? m ʰp̲lay! played◆ played }
ˡg̲ame! : Float -> Int
t:g_ame! m: a game model m plays against itself, as its boards from the empty one on (a board per row); one move in ten is random.
ˡg̲ame! ← { m → m ʰp̲lay! 1 9 r̲eshape 0 }
Learning
ʰr̲esult : Int -> Int -> Float
g h:r_esult j: the result of game g as the mover of its board j + 1 sees it: 1 won, 0 lost, 0.5 drawn.
ʰr̲esult ← { g j → w ← ˡo̲utcome (t̲ally g) s̲elect g x ← '+ r̲/ (j + 1) s̲elect g (0.5 × f̲loat w = 2) + f̲loat w = (2 × x) − 1 }
ʰt̲arget : Int -> Float -> Int -> Float
g h:t_arget m j: the value board j + 1 of game g moves towards: the result for the last two moves, else 0.9 times model m's value of the mover's next board.
ʰt̲arget ← { g m j → j ≥ (t̲ally g) − 2 ? g ʰr̲esult j◆ 0.9 × m ˡv̲alue (j + 3) s̲elect g }
ʰb̲ack : Int -> Float -> Int -> Float
g h:b_ack m j: model m after moving the values of boards j + 1 down to 2 of game g a fifth of the way to their targets.
ʰb̲ack ← { g m j → k ← (1 s̲elect m) i̲ndexOf f̲loat ˡc̲ode (j + 1) s̲elect g d ← 0.2 × ((g ʰt̲arget m) j) − m ˡv̲alue (j + 1) s̲elect g learned ← m + (0.0 c̲at d) '× t̲able f̲loat (r̲ange t̲ally 1 s̲elect m) = k j = 1 ? learned◆ (g ʰb̲ack learned) j − 1 }
ʰm̲eet : Num a => Float -> a -> Float
m h:m_eet g: model m with the boards of game g not met before added, each at 0.5.
ʰm̲eet ← { m g → c ← u̲nique '{ j → f̲loat ˡc̲ode j s̲elect g } e̲ach 1 d̲rop r̲ange t̲ally g n ← (w̲here 0 = c m̲ember? 1 s̲elect m) s̲elect c k ← (t̲ally 1 s̲elect m) + t̲ally n (2 c̲at k) r̲eshape ((1 s̲elect m) c̲at n) c̲at (2 s̲elect m) c̲at 0.5 + 0.0 × n }
ˡl̲earn : Float -> Int -> Float
m t:l_earn g: model m after learning from game g (a board per row, as t:g_ame! gives), from the last move back to the first: each board's value moves a fifth of the way to a target. For the last two moves the target is the result as its mover sees it (1 won, 0 lost, 0.5 drawn); before that, the mover's next board, two moves on, taken at 0.9 so that a sooner win is worth more.
ˡl̲earn ← { m g → (g ʰb̲ack m ʰm̲eet g) (t̲ally g) − 1 }
Training
ʰr̲ound! : Float -> Float
h:r_ound! m: model m after one game against itself and learning from it.
ʰr̲ound! ← { m → m ˡl̲earn ˡg̲ame! m }
ʰl̲oop! : Int -> Float -> Float
n h:l_oop! m: model m after n more games, in rounds of 250, printing the games still to go and the positions known after each round.
ʰl̲oop! ← { n m → k ← 250 m̲in n trained ← k 'ʰr̲ound! p̲ower m _ ← p̲rint! (n − k) c̲at t̲ally 1 s̲elect trained n = k ? trained◆ (n − k) ʰl̲oop! trained }
ˡt̲rain! : Int -> Float -> Float
n t:t_rain! m: model m after learning from n games against itself. After each round of 250 games it prints how many games are still to go and how many positions it knows, so a long training shows its progress. Start from t:empty.
ˡt̲rain! ← { n m → _ ← p̲rint! "games to go, positions known:" n ʰl̲oop! m }
Measuring
ʰt̲urn! : (Num a, Truthy a) => Float -> a -> a -> Int
m h:t_urn! side s: the move on board s, model m playing side (1 as X, -1 as O) against a random player: its best move when side is to move, else a random empty square.
ʰt̲urn! ← { m side s → p ← w̲here s = 0 (1 − 2 × '+ r̲/ s) = side ? m ˡc̲hoose s◆ (r̲oll! t̲ally p) s̲elect p }
ʰv̲ersus! : Num a => Float -> Int -> Int -> a
m h:v_ersus! side s: the outcome of the game from board s, model m playing side against a random player: 1 X won, -1 O won, 2 drawn.
ʰv̲ersus! ← { m side s → played ← s ˡa̲fter ((m ʰt̲urn! side) s) w ← ˡo̲utcome played w = 0 ? ((m ʰv̲ersus! side) played)◆ w }
ʰc̲ount! : Float -> Int -> Int -> Int
m h:c_ount! side n: n games as side against a random player; how many the machine won, lost and drew.
ʰc̲ount! ← { m side n → w ← '{ ▁ → ((m ʰv̲ersus! side) 9 r̲eshape 0) } e̲ach r̲ange n '+ r̲/ w '= t̲able side c̲at (0 − side) c̲at 2 }
ˡt̲rial! : Int -> Float -> Int
n t:t_rial! m: n games of model m against a random player as X, then n as O; a row each of games won, lost and drawn.
ˡt̲rial! ← { n m → 2 3 r̲eshape ((m ʰc̲ount! 1) n) c̲at (m ʰc̲ount! -1) n }
Its own games
ʰg̲reedy : Float -> Int -> Int
m h:g_reedy g: game g (a board per row) played on to the end by model m against itself, its best move on both sides.
ʰg̲reedy ← { m g → s ← (t̲ally g) s̲elect g played ← g c̲at 1 9 r̲eshape s ˡa̲fter m ˡc̲hoose s 0 = ˡo̲utcome (t̲ally played) s̲elect played ? m ʰg̲reedy played◆ played }
ˡb̲est : Float -> Int
t:b_est m: the game model m plays against itself, its best move on both sides, as its boards from the empty one on (a board per row).
ˡb̲est ← { m → m ʰg̲reedy 1 9 r̲eshape 0 }
ˡb̲oards : Int -> Char
t:b_oards g: the boards of game g (a board per row) drawn side by side, left to right, as 3 rows of text.
ˡb̲oards ← { g → k ← t̲ally g rows ← (3 × (r̲ange 3) − 1) '+ t̲able 9 × (r̲ange k) − 1 at ← (1 + 9 × k) m̲in rows '+ t̲able 1 2 3 99 squares ← at s̲elect (r̲avel g) c̲at 3 (3 c̲at 8 × k) r̲eshape (1 + (squares + 2) '× t̲able 0 1) s̲elect " O.X " }
ʰo̲pening! : Unit -> Int
h:o_pening! @: a random first move: the empty board and the board after X takes a random square, a board per row.
ʰo̲pening! ← { @ → 2 9 r̲eshape (9 r̲eshape 0) c̲at 1 × (r̲ange 9) = r̲oll! 9 }
ʰf̲inal : Num a => Int -> a
h:f_inal g: the outcome of game g's last board.
ʰf̲inal ← { g → ˡo̲utcome (t̲ally g) s̲elect g }
ˡs̲elfTrial! : Int -> Float -> Int
n t:s_elfTrial! m: n games of model m against itself, its best move on both sides but the first move at random (from the empty board its best move is always the same, so every game would be one game); games X won, O won, drawn. Played well from any opening, every game is a draw.
ˡs̲elfTrial! ← { n m → w ← '{ ▁ → ʰf̲inal m ʰg̲reedy ʰo̲pening! @ } e̲ach r̲ange n '+ r̲/ w '= t̲able 1 -1 2 }