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 !.

source

Boards

ˡs̲how : Int -> Char

function · line 22

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

value · line 26

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
Used in: ˡo̲utcome

ˡo̲utcome : Num a => Int -> a

function · line 37

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

value · line 46

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
Used in: ˡc̲ode

ˡc̲ode : Num a => a -> a

function · line 55

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

value · line 62

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
Used in: m, m

ˡv̲alues : Float -> Float -> Float

function · line 69

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

function · line 75

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

function · line 82

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

function · line 88

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

function (private) · line 97

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
}
Used in: ʰp̲lay!

ʰp̲lay! : Float -> Int -> Int

function (private) · line 103

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

function · line 110

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 }
Used in: ʰr̲ound!

Learning

ʰr̲esult : Int -> Int -> Float

function (private) · line 116

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
}
Used in: ʰt̲arget

ʰt̲arget : Int -> Float -> Int -> Float

function (private) · line 124

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
}
Used in: ʰb̲ack

ʰb̲ack : Int -> Float -> Int -> Float

function (private) · line 129

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

function (private) · line 137

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
}
Used in: ˡl̲earn

ˡl̲earn : Float -> Int -> Float

function · line 149

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 }
Used in: ʰr̲ound!

Training

ʰr̲ound! : Float -> Float

function (private) · line 160

h:r_ound! m: model m after one game against itself and learning from it.

ʰr̲ound! ← { m → m ˡl̲earn ˡg̲ame! m }
Used in: ʰl̲oop!

ʰl̲oop! : Int -> Float -> Float

function (private) · line 163

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

function · line 173

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
}
Used in: m, m

Measuring

ʰt̲urn! : (Num a, Truthy a) => Float -> a -> a -> Int

function (private) · line 183

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
}
Used in: ʰv̲ersus!

ʰv̲ersus! : Num a => Float -> Int -> Int -> a

function (private) · line 189

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

function (private) · line 196

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
}
Used in: ˡt̲rial!

ˡt̲rial! : Int -> Float -> Int

function · line 202

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

function (private) · line 208

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

function · line 215

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

function · line 219

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

function (private) · line 229

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

function (private) · line 231

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

function · line 237

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
}