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}