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; the demos 5⍝│ demos/tttml.xtl, demos/tttml-train.xtl and demos/tttml-play.xtl use it. 6⍝│ 7⍝│ A board is 9 numbers, the squares row by row: 1 for X, -1 for O, 0 8⍝│ for an empty square. X moves first, so the board says whose turn it 9⍝│ is: X's when it sums to 0. What the machine learns is a model: two 10⍝│ rows, the codes of the positions met and their values. Only the 11⍝│ functions that roll dice end in !. 12 13⍝━━ Boards 14 15⍝│ t:s_how s: board s drawn as 3 rows of text: X, O and a dot for an 16⍝│ empty square. 17⍝│ >> "t:" u_se< "TTTML" 18⍝│ >> t:s_how 1 -1 0 0 1 0 0 0 -1 19⍝│ X O . 20⍝│ . X . 21⍝│ . . O 22ˡs̲how ← { s → 3 6 r̲eshape (1 + (s + 2) '× t̲able 0 1) s̲elect " O.X" } 23 24⍝│ The 8 lines (3 rows, 3 columns, 2 diagonals) as rows of 0s and 1s: 25⍝│ one inner product sums a board along every line. 26ˡ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 27 28⍝│ t:o_utcome s: the state of board s: 1 X has won (a line sums to 3), 29⍝│ -1 O has (-3), 2 a draw (a full board), 0 the game goes on. 30⍝│ >> "t:" u_se< "TTTML" 31⍝│ >> t:o_utcome 1 1 1 -1 -1 0 0 0 0 32⍝│ 1 33⍝│ >> t:o_utcome 1 -1 1 1 -1 -1 -1 1 1 34⍝│ 2 35⍝│ >> t:o_utcome 0 0 0 0 0 0 0 0 0 36⍝│ 0 37ˡo̲utcome ← { s → 38 l ← ˡlines '+ '× i̲nner s 39 3 m̲ember? l ? 1◆ -3 m̲ember? l ? -1◆ 0 m̲ember? s ? 0◆ 2 40} 41 42⍝━━ Positions and the model 43 44⍝│ The 8 symmetries of the square, each a row rearranging the 9 45⍝│ squares (turns and reflections). 46ˡ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 47⍝│ t:c_ode s: the code of board s. A board read as a base-3 number 48⍝│ names it; the least of its 8 names (one per symmetry) is the code, 49⍝│ the same for a board turned or reflected. 50⍝│ >> "t:" u_se< "TTTML" 51⍝│ >> t:c_ode 1 0 0 0 0 0 0 0 0 52⍝│ 9842 53⍝│ >> t:c_ode 0 0 1 0 0 0 0 0 0 54⍝│ 9842 55ˡc̲ode ← { s → 'm̲in r̲/ 3 d̲ecode o̲\ 1 + ˡsymmetries s̲elect s } 56 57⍝│ The model that knows nothing yet: two rows (codes, values) of no 58⍝│ positions. Training starts from it. 59⍝│ >> "t:" u_se< "TTTML" 60⍝│ >> t_ally 1 s_elect t:empty 61⍝│ 0 62ˡempty ← 2 0 r̲eshape 0.5 63 64⍝ A code not met is found one past the end, where a 0.5 is added. 65 66⍝│ m t:v_alues c: what the positions with codes c, each just after a 67⍝│ move, are worth in model m to the player who made it: towards 1 a 68⍝│ win, towards 0 a loss, 0.5 a draw. A code not met yet is worth 0.5. 69ˡv̲alues ← { m c → ((1 s̲elect m) i̲ndexOf c) s̲elect (2 s̲elect m) c̲at 0.5 } 70⍝│ m t:v_alue s: what board s is worth in model m to the player who 71⍝│ just moved (t:v_alues of its code). 72⍝│ >> "t:" u_se< "TTTML" 73⍝│ >> t:empty t:v_alue 1 0 0 0 0 0 0 0 0 74⍝│ 0.5 75ˡv̲alue ← { m s → m ˡv̲alues f̲loat ˡc̲ode s } 76 77⍝│ s t:a_fter a: the board once the player to move (X when s sums to 78⍝│ 0, else O) takes square a, 1 to 9. 79⍝│ >> "t:" u_se< "TTTML" 80⍝│ >> (0 0 0 0 1 0 0 0 0) t:a_fter 1 81⍝│ -1 0 0 0 1 0 0 0 0 82ˡa̲fter ← { s a → s + (1 − 2 × '+ r̲/ s) × (r̲ange 9) = a } 83 84⍝━━ Playing 85 86⍝│ m t:c_hoose s: the best move in model m for the player to move on 87⍝│ board s: the empty square (1 to 9) whose board is worth most. 88ˡc̲hoose ← { m s → 89 p ← w̲here s = 0 90 v ← m ˡv̲alues '{ a → f̲loat ˡc̲ode s ˡa̲fter a } e̲ach p 91 (v i̲ndexOf 'm̲ax r̲/ v) s̲elect p 92} 93 94⍝│ m h:p_ick! s: the move on board s, the best in model m but one 95⍝│ time in ten a random empty square, so that it keeps trying moves it 96⍝│ now thinks are bad. 97ʰp̲ick! ← { m s → 98 p ← w̲here s = 0 99 (r̲oll! 10) = 1 ? (r̲oll! t̲ally p) s̲elect p◆ m ˡc̲hoose s 100} 101⍝│ m h:p_lay! g: game g (its boards so far, a board per row) played on 102⍝│ to the end by model m against itself, moves from h:p_ick!. 103ʰp̲lay! ← { m g → 104 s ← (t̲ally g) s̲elect g 105 played ← g c̲at 1 9 r̲eshape s ˡa̲fter m ʰp̲ick! s 106 0 = ˡo̲utcome (t̲ally played) s̲elect played ? m ʰp̲lay! played◆ played 107} 108⍝│ t:g_ame! m: a game model m plays against itself, as its boards from 109⍝│ the empty one on (a board per row); one move in ten is random. 110ˡg̲ame! ← { m → m ʰp̲lay! 1 9 r̲eshape 0 } 111 112⍝━━ Learning 113 114⍝│ g h:r_esult j: the result of game g as the mover of its board j + 1 115⍝│ sees it: 1 won, 0 lost, 0.5 drawn. 116ʰr̲esult ← { g j → 117 w ← ˡo̲utcome (t̲ally g) s̲elect g 118 x ← '+ r̲/ (j + 1) s̲elect g 119 (0.5 × f̲loat w = 2) + f̲loat w = (2 × x) − 1 120} 121⍝│ g h:t_arget m j: the value board j + 1 of game g moves towards: the 122⍝│ result for the last two moves, else 0.9 times model m's value of 123⍝│ the mover's next board. 124ʰt̲arget ← { g m j → 125 j ≥ (t̲ally g) − 2 ? g ʰr̲esult j◆ 0.9 × m ˡv̲alue (j + 3) s̲elect g 126} 127⍝│ g h:b_ack m j: model m after moving the values of boards j + 1 down 128⍝│ to 2 of game g a fifth of the way to their targets. 129ʰb̲ack ← { g m j → 130 k ← (1 s̲elect m) i̲ndexOf f̲loat ˡc̲ode (j + 1) s̲elect g 131 d ← 0.2 × ((g ʰt̲arget m) j) − m ˡv̲alue (j + 1) s̲elect g 132 learned ← m + (0.0 c̲at d) '× t̲able f̲loat (r̲ange t̲ally 1 s̲elect m) = k 133 j = 1 ? learned◆ (g ʰb̲ack learned) j − 1 134} 135⍝│ m h:m_eet g: model m with the boards of game g not met before 136⍝│ added, each at 0.5. 137ʰm̲eet ← { m g → 138 c ← u̲nique '{ j → f̲loat ˡc̲ode j s̲elect g } e̲ach 1 d̲rop r̲ange t̲ally g 139 n ← (w̲here 0 = c m̲ember? 1 s̲elect m) s̲elect c 140 k ← (t̲ally 1 s̲elect m) + t̲ally n 141 (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 142} 143⍝│ m t:l_earn g: model m after learning from game g (a board per row, 144⍝│ as t:g_ame! gives), from the last move back to the first: each 145⍝│ board's value moves a fifth of the way to a target. For the last two 146⍝│ moves the target is the result as its mover sees it (1 won, 0 lost, 147⍝│ 0.5 drawn); before that, the mover's next board, two moves on, taken 148⍝│ at 0.9 so that a sooner win is worth more. 149ˡl̲earn ← { m g → (g ʰb̲ack m ʰm̲eet g) (t̲ally g) − 1 } 150 151⍝━━ Training 152 153⍝ It plays in rounds of 250 games. A round repeats one game with 154⍝ p_ower, which does not nest calls: the recursion is one level per 155⍝ round, not per game (a browser's stack holds a few hundred levels, 156⍝ not thousands). 157 158⍝│ h:r_ound! m: model m after one game against itself and learning 159⍝│ from it. 160ʰr̲ound! ← { m → m ˡl̲earn ˡg̲ame! m } 161⍝│ n h:l_oop! m: model m after n more games, in rounds of 250, printing 162⍝│ the games still to go and the positions known after each round. 163ʰl̲oop! ← { n m → 164 k ← 250 m̲in n 165 trained ← k 'ʰr̲ound! p̲ower m 166 _ ← p̲rint! (n − k) c̲at t̲ally 1 s̲elect trained 167 n = k ? trained◆ (n − k) ʰl̲oop! trained 168} 169⍝│ n t:t_rain! m: model m after learning from n games against itself. 170⍝│ After each round of 250 games it prints how many games are still to 171⍝│ go and how many positions it knows, so a long training shows its 172⍝│ progress. Start from t:empty. 173ˡt̲rain! ← { n m → 174 _ ← p̲rint! "games to go, positions known:" 175 n ʰl̲oop! m 176} 177 178⍝━━ Measuring 179 180⍝│ m h:t_urn! side s: the move on board s, model m playing side (1 as 181⍝│ X, -1 as O) against a random player: its best move when side is to 182⍝│ move, else a random empty square. 183ʰt̲urn! ← { m side s → 184 p ← w̲here s = 0 185 (1 − 2 × '+ r̲/ s) = side ? m ˡc̲hoose s◆ (r̲oll! t̲ally p) s̲elect p 186} 187⍝│ m h:v_ersus! side s: the outcome of the game from board s, model m 188⍝│ playing side against a random player: 1 X won, -1 O won, 2 drawn. 189ʰv̲ersus! ← { m side s → 190 played ← s ˡa̲fter ((m ʰt̲urn! side) s) 191 w ← ˡo̲utcome played 192 w = 0 ? ((m ʰv̲ersus! side) played)◆ w 193} 194⍝│ m h:c_ount! side n: n games as side against a random player; how 195⍝│ many the machine won, lost and drew. 196ʰc̲ount! ← { m side n → 197 w ← '{ ▁ → ((m ʰv̲ersus! side) 9 r̲eshape 0) } e̲ach r̲ange n 198 '+ r̲/ w '= t̲able side c̲at (0 − side) c̲at 2 199} 200⍝│ n t:t_rial! m: n games of model m against a random player as X, 201⍝│ then n as O; a row each of games won, lost and drawn. 202ˡt̲rial! ← { n m → 2 3 r̲eshape ((m ʰc̲ount! 1) n) c̲at (m ʰc̲ount! -1) n } 203 204⍝━━ Its own games 205 206⍝│ m h:g_reedy g: game g (a board per row) played on to the end by 207⍝│ model m against itself, its best move on both sides. 208ʰg̲reedy ← { m g → 209 s ← (t̲ally g) s̲elect g 210 played ← g c̲at 1 9 r̲eshape s ˡa̲fter m ˡc̲hoose s 211 0 = ˡo̲utcome (t̲ally played) s̲elect played ? m ʰg̲reedy played◆ played 212} 213⍝│ t:b_est m: the game model m plays against itself, its best move on 214⍝│ both sides, as its boards from the empty one on (a board per row). 215ˡb̲est ← { m → m ʰg̲reedy 1 9 r̲eshape 0 } 216 217⍝│ t:b_oards g: the boards of game g (a board per row) drawn side by 218⍝│ side, left to right, as 3 rows of text. 219ˡb̲oards ← { g → 220 k ← t̲ally g 221 rows ← (3 × (r̲ange 3) − 1) '+ t̲able 9 × (r̲ange k) − 1 222 at ← (1 + 9 × k) m̲in rows '+ t̲able 1 2 3 99 223 squares ← at s̲elect (r̲avel g) c̲at 3 224 (3 c̲at 8 × k) r̲eshape (1 + (squares + 2) '× t̲able 0 1) s̲elect " O.X " 225} 226 227⍝│ h:o_pening! @: a random first move: the empty board and the board 228⍝│ after X takes a random square, a board per row. 229ʰo̲pening! ← { @ → 2 9 r̲eshape (9 r̲eshape 0) c̲at 1 × (r̲ange 9) = r̲oll! 9 } 230⍝│ h:f_inal g: the outcome of game g's last board. 231ʰf̲inal ← { g → ˡo̲utcome (t̲ally g) s̲elect g } 232⍝│ n t:s_elfTrial! m: n games of model m against itself, its best move 233⍝│ on both sides but the first move at random (from the empty board its 234⍝│ best move is always the same, so every game would be one game); 235⍝│ games X won, O won, drawn. Played well from any opening, every game 236⍝│ is a draw. 237ˡs̲elfTrial! ← { n m → 238 w ← '{ ▁ → ʰf̲inal m ʰg̲reedy ʰo̲pening! @ } e̲ach r̲ange n 239 '+ r̲/ w '= t̲able 1 -1 2 240}