TicTacToe.xtl

1⍝# Tic-tac-toe's rules, a library: tic-tac-toe.xtl (scripted), play.xtl
2⍝# (at the terminal) and the web page all use these. The board is a
3⍝# vector of 9 squares, numbered row by row: 0 empty, 1 X, -1 O. X moves
4⍝# first.
5
6ᵇ⁼u̲se< "Board"
7
8⍝ :: Num a => Unit -> a
9⍝# The eight lines (three rows, three columns, two diagonals) as an 8 by
10⍝# 3 table of square numbers.
11ˡl̲ines ← { @ → 8 3 r̲eshape 1 2 3 4 5 6 7 8 9 1 4 7 2 5 8 3 6 9 1 5 9 3 5 7 }
12⍝ :: Num a => a -> a
13⍝# Every line's sum at once: the table used as indices into the board
14⍝# (an 8 by 3 matrix of squares), summed along each row. 3 is a line of
15⍝# X, -3 a line of O.
16ˡs̲ums ← { b → '+ r̲/₂ (ˡl̲ines @) s̲elect b }
17⍝ :: (Num a, Num b, Truthy b) => a -> b
18⍝# 1 when X has a line, -1 when O has, else 0.
19ˡw̲inner ← { b →
20  s ← ˡs̲ums b
21  (3 m̲ember? s) − -3 m̲ember? s
22}
23⍝ :: (Num a, Num b, Truthy b) => a -> b
24⍝# Whose turn: X (1) when the board has as many X as O, else O (-1).
25ˡt̲urn ← { b → 1 − 2 × 0 ≠ '+ r̲/ b }
26⍝ :: (Any a, Num b) => a -> b
27⍝# A new board: nine empty squares.
28ˡn̲ew ← { x → 9 r̲eshape 0 }
29⍝ :: Num a => a -> Int
30⍝# The empty squares, by number: the legal moves.
31ˡl̲egal ← { b → w̲here b = 0 }
32⍝ :: (Num a, Num b) => a -> b
33⍝# 0 playing, 1 X won, 2 O won, 3 a draw: the first of the three that
34⍝# holds.
35ˡs̲tatus ← { b →
36  w ← ˡw̲inner b
37  f̲irst (((w = 1) c̲at (w = -1) c̲at 0 = t̲ally ˡl̲egal b) r̲eplicate 1 2 3) c̲at 0
38}
39⍝ :: (Num a, Truthy a) => a -> Int -> a
40⍝# The player to move takes square k.
41ˡm̲ove ← { b k → b + (ˡt̲urn b) × k = r̲ange 9 }
42
43⍝ :: Num a => a -> Int
44⍝# Every square's code at once: O 1, X 2, an empty square 2 plus its
45⍝# number (so the text shows the number to type).
46ˡc̲odes ← { b → 3 3 r̲eshape (b = -1) + (2 × b = 1) + (b = 0) × 2 + r̲ange 9 }
47⍝ :: Num a => a -> Char
48⍝# The board as text, spaced (lib/Board).
49ˡv̲iew ← { b → ᵇs̲paced (ˡc̲odes b) s̲elect "OX123456789" }
50⍝ :: Num a => a -> Char
51⍝# The board as a picture X_eTaL draws (SVG text); []S_HOW shows it.
52ˡp̲icture ← { b → ⎕G̲RID (ˡc̲odes b) s̲elect "OX123456789" }
53
54⍝## Players
55⍝ :: Truthy a => Unit -> a
56⍝# Which squares lie on which lines: a 9 by 8 table (square against line),
57⍝# from a 9 by 8 by 3 table of every square against every entry.
58ˡo̲n ← { @ → '∨ r̲/₃ (r̲ange 9) '= t̲able ˡl̲ines @ }
59⍝ :: (Num a, Num b, Truthy b) => a -> a -> b
60⍝# For every square, whether a line through it sums to t.
61ˡn̲ear ← { b t → '∨ r̲/₂ (ˡo̲n @) × 9 8 r̲eshape t = ˡs̲ums b }
62⍝ :: (Num a, Truthy a) => a -> Int
63⍝# A quick player that rates every empty square at once: four features
64⍝# per square (it completes a line of the mover's, it blocks one of the
65⍝# other's, the center, a corner), a 4 by 9 matrix, weighted 1000, 100,
66⍝# 10 and 5 by one inner product. A line through a square with sum 2 (or
67⍝# -2) has two marks and one empty square, which must be that one.
68ˡa̲i ← { b →
69  p ← ˡt̲urn b
70  f ← (b ˡn̲ear 2 × p) c̲at (b ˡn̲ear -2 × p) c̲at (5 = r̲ange 9) c̲at (r̲ange 9) m̲ember? 1 3 7 9
71  r ← (b = 0) × 1 + 1000 100 10 5 '+ '× i̲nner 4 9 r̲eshape f
72  f̲irst w̲here r = 'm̲ax r̲/ r
73}
74
75⍝ :: (Num a, Truthy a, Num b, Truthy b) => a -> b
76⍝# A perfect player: minimax, written as negamax. A board's value with
77⍝# best play (1 X wins, -1 O wins, 0 a draw) is the winner if there is
78⍝# one, 0 when the board is full, else the mover's best: the mover times
79⍝# the largest of the mover times every move's value (every legal move
80⍝# tried, by recursion).
81ˡv̲alue ← { b →
82  w ← ˡw̲inner b
83  w ≠ 0 ? w
84  e ← ˡl̲egal b
85  0 = t̲ally e ? 0
86  p ← ˡt̲urn b
87  p × 'm̲ax r̲/ p × '{ ˡv̲alue b ˡm̲ove ⍵ } e̲ach e
88}
89⍝ :: (Num a, Truthy a) => a -> Int
90⍝# Its move: the first legal square with the best value for the mover.
91ˡb̲est ← { b →
92  e ← ˡl̲egal b
93  v ← (ˡt̲urn b) × '{ ˡv̲alue b ˡm̲ove ⍵ } e̲ach e
94  f̲irst (v = 'm̲ax r̲/ v) r̲eplicate e
95}