sourcelib/TTTML.xtl

1⍝ TTTML: a machine that learns tic-tac-toe by playing itself (a 2⍝ standard library, built into xetal), ported from the TTTML workspace 3⍝ of sw-apl's library 1. Import it with an alias of your choice: 4⍝ "t:" u_se< "TTTML". docs/literate/tttml.org explains it. 5⍝ 6⍝ A board is 9 numbers, the squares row by row: 1 for X, -1 for O, 0 7⍝ for an empty square. X moves first, so the board says whose turn it 8⍝ is: X's when it sums to 0. What the machine learns is a model: two 9⍝ rows, the codes of the positions met and their values. Only the 10⍝ functions that roll dice end in !. 11 12⍝ The board drawn: X, O and a dot for an empty square. 13ˡs̲how ← { s → 3 6 r̲eshape (1 + (s + 2) '× t̲able 0 1) s̲elect " O.X" } 14 15⍝ The 8 lines (3 rows, 3 columns, 2 diagonals) as rows of 0s and 1s: 16⍝ one inner product sums a board along every line. 17ˡ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 18 19⍝ 1 X has won (a line sums to 3), -1 O has (-3), 2 a draw (a full 20⍝ board), 0 the game goes on. 21ˡo̲utcome ← { s → 22 l ← ˡlines '+ '× i̲nner s 23 3 m̲ember? l ? 1◆ -3 m̲ember? l ? -1◆ 0 m̲ember? s ? 0◆ 2 24} 25 26⍝ The 8 symmetries of the square as rearrangements of the squares. A 27⍝ board read as a base-3 number names it; the least of its 8 names is 28⍝ the position's code, the same for a board turned or reflected. 29ˡ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 30ˡc̲ode ← { s → 'm̲in r̲/ 3 d̲ecode o̲\ 1 + ˡsymmetries s̲elect s } 31 32⍝ The model knows nothing yet: no positions. 33ˡempty ← 2 0 r̲eshape 0.5 34 35⍝ m v_alues c: what the positions with codes c, each just after a 36⍝ move, are worth to the player who made it: towards 1 a win, towards 37⍝ 0 a loss, 0.5 a draw. A code not met yet is found one past the end, 38⍝ where a 0.5 is added, so it is worth 0.5 too. 39ˡv̲alues ← { m c → ((1 s̲elect m) i̲ndexOf c) s̲elect (2 s̲elect m) c̲at 0.5 } 40ˡv̲alue ← { m s → m ˡv̲alues f̲loat ˡc̲ode s } 41 42⍝ s a_fter a: the board once the player to move takes square a. 43ˡa̲fter ← { s a → s + (1 − 2 × '+ r̲/ s) × (r̲ange 9) = a } 44 45⍝ m c_hoose s: the square whose board is worth most to the mover. 46ˡc̲hoose ← { m s → 47 p ← w̲here s = 0 48 v ← m ˡv̲alues '{ a → f̲loat ˡc̲ode s ˡa̲fter a } e̲ach p 49 (v i̲ndexOf 'm̲ax r̲/ v) s̲elect p 50} 51 52⍝ A game against itself, as its boards from the empty one on: the 53⍝ best move, but one time in ten a random one, so that it keeps trying 54⍝ moves it now thinks are bad. 55p̲ick! ← { m s → 56 p ← w̲here s = 0 57 (r̲oll! 10) = 1 ? (r̲oll! t̲ally p) s̲elect p◆ m ˡc̲hoose s 58} 59p̲lay! ← { m g → 60 s ← (t̲ally g) s̲elect g 61 g ← g c̲at 1 9 r̲eshape s ˡa̲fter m p̲ick! s 62 0 = ˡo̲utcome (t̲ally g) s̲elect g ? m p̲lay! g◆ g 63} 64ˡg̲ame! ← { m → m p̲lay! 1 9 r̲eshape 0 } 65 66⍝ Learning from game g, from the last move back to the first: each 67⍝ board's value moves a fifth of the way to a target. For the last two 68⍝ moves the target is the result as its mover sees it (1 won, 0 lost, 69⍝ 0.5 drawn); before that, the mover's next board, two moves on, taken 70⍝ at 0.9 so that a sooner win is worth more. 71r̲esult ← { g j → 72 w ← ˡo̲utcome (t̲ally g) s̲elect g 73 x ← '+ r̲/ (j + 1) s̲elect g 74 (0.5 × f̲loat w = 2) + f̲loat w = (2 × x) − 1 75} 76t̲arget ← { g m j → 77 j ≥ (t̲ally g) − 2 ? g r̲esult j◆ 0.9 × m ˡv̲alue (j + 3) s̲elect g 78} 79b̲ack ← { g m j → 80 k ← (1 s̲elect m) i̲ndexOf f̲loat ˡc̲ode (j + 1) s̲elect g 81 d ← 0.2 × ((g t̲arget m)_ j) − m ˡv̲alue (j + 1) s̲elect g 82 m ← m + (0.0 c̲at d) '× t̲able f̲loat (r̲ange t̲ally 1 s̲elect m) = k 83 j = 1 ? m◆ (g b̲ack m)_ j − 1 84} 85⍝ Boards not met before join the model at 0.5 first. 86m̲eet ← { m g → 87 c ← u̲nique '{ j → f̲loat ˡc̲ode j s̲elect g } e̲ach 1 d̲rop r̲ange t̲ally g 88 n ← (w̲here 0 = c m̲ember? 1 s̲elect m) s̲elect c 89 k ← (t̲ally 1 s̲elect m) + t̲ally n 90 (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 91} 92ˡl̲earn ← { m g → (g b̲ack m m̲eet g)_ (t̲ally g) − 1 } 93 94⍝ n t_rain! m: model m after learning from n games against itself. 95⍝ It plays in rounds of 250 games, and after each prints how many games 96⍝ are still to go and how many positions it knows, so a long training 97⍝ shows its progress. A round repeats one game with p_ower, which does 98⍝ not nest calls: the recursion is one level per round, not per game 99⍝ (a browser's stack holds a few hundred levels, not thousands). 100r̲ound! ← { m → m ˡl̲earn ˡg̲ame! m } 101l̲oop! ← { n m → 102 k ← 250 m̲in n 103 m ← k 'r̲ound! p̲ower m 104 shown ← p̲rint! (n − k) c̲at t̲ally 1 s̲elect m 105 n = k ? m◆ (n − k) l̲oop! m 106} 107ˡt̲rain! ← { n m → 108 shown ← p̲rint! "games to go, positions known:" 109 n l̲oop! m 110} 111 112⍝ Against a random player: the machine plays side (1 as X, -1 as O) 113⍝ with its best move, the other side at random. A game's result for 114⍝ the machine: 1 won, -1 lost, 2 drawn. 115t̲urn! ← { m side s → 116 p ← w̲here s = 0 117 (1 − 2 × '+ r̲/ s) = side ? m ˡc̲hoose s◆ (r̲oll! t̲ally p) s̲elect p 118} 119v̲ersus! ← { m side s → 120 s ← s ˡa̲fter ((m t̲urn! side)_ s) 121 w ← ˡo̲utcome s 122 w = 0 ? ((m v̲ersus! side)_ s)◆ w 123} 124c̲ount! ← { m side n → 125 w ← '{ i → ((m v̲ersus! side)_ 9 r̲eshape 0) } e̲ach r̲ange n 126 '+ r̲/ w '= t̲able side c̲at (0 − side) c̲at 2 127} 128⍝ n t_rial! m: n games as X, then n as O; a row each of games won, 129⍝ lost and drawn. 130ˡt̲rial! ← { n m → 2 3 r̲eshape ((m c̲ount! 1)_ n) c̲at (m c̲ount! -1)_ n } 131 132⍝ The game the model plays against itself, its best move on both 133⍝ sides, as its boards from the empty one on. 134g̲reedy ← { m g → 135 s ← (t̲ally g) s̲elect g 136 g ← g c̲at 1 9 r̲eshape s ˡa̲fter m ˡc̲hoose s 137 0 = ˡo̲utcome (t̲ally g) s̲elect g ? m g̲reedy g◆ g 138} 139ˡb̲est ← { m → m g̲reedy 1 9 r̲eshape 0 } 140 141⍝ The boards of a game (a board per row) drawn left to right. 142ˡb̲oards ← { g → 143 k ← t̲ally g 144 rows ← (3 × (r̲ange 3) − 1) '+ t̲able 9 × (r̲ange k) − 1 145 at ← (1 + 9 × k) m̲in rows '+ t̲able 1 2 3 99 146 squares ← at s̲elect (r̲avel g) c̲at 3 147 (3 c̲at 8 × k) r̲eshape (1 + (squares + 2) '× t̲able 0 1) s̲elect " O.X " 148} 149 150⍝ n s_elfTrial m: n games against itself, its best move on both sides 151⍝ but the first move at random (from the empty board its best move is 152⍝ always the same, so every game would be one game): games X won, O 153⍝ won, drawn. Played well from any opening, every game is a draw. 154o̲pening! ← { @ → 2 9 r̲eshape (9 r̲eshape 0) c̲at 1 × (r̲ange 9) = r̲oll! 9 } 155f̲inal ← { g → ˡo̲utcome (t̲ally g) s̲elect g } 156ˡs̲elfTrial! ← { n m → 157 w ← '{ i → f̲inal m g̲reedy o̲pening! @ } e̲ach r̲ange n 158 '+ r̲/ w '= t̲able 1 -1 2 159}