ES.268 Dynamic Programming with Impartial Games, Course Notes 3

, , Playing Games with Algorithms: – most games are hard to play well: – Chess is EXPTIME-complete: – n × n board, arbitrary position – need exponential (cn ) time to find a winning move (if there is one) – also: as hard as all games (problems) that need exponential time – Checkers is EXPTIME-complete: ⇒ Chess & Checkers are the “same” computationally: solving one solves the other (PSPACE-complete if draw after poly. moves) – Shogi (Japanese chess) is EXPTIME-complete – Japanese Go is EXPTIME-complete – U. S. Go might be harder – Othello is PSPACE-complete: – conjecture requires exponential time, but not sure (implied by P �= NP) – can solve some games fast: in “polynomial time” (mostly 1D) Kayles: [Dudeney 1908] (n bowling pins) – move = hit one or two adjacent pins – last player to move wins (normal play) Let’s play! 1 First-player win: SYMMETRY STRATEGY – move to split into two equal halves (1 pin if odd, 2 if even) – whatever opponent does, do same in other half (Kn + Kn = 0 . . . just like Nim) Impartial game, so Sprague-Grundy Theory says Kayles ≡ Nim somehow = {Ki + Kn−i−1 , Ki + Kn−i−2 | i = 0, 1, . . . , n − 2} = mex{nimber(Ki + Kn−i−1 ), nimber(Ki + Kn−i−2 ) | i = 0, 1, . . . , n − 2} – nimber(x + y) = nimber(x) ⊕ nimber(y) ⇒ nimber(Kn ) = mex{nimber(Ki ) ⊕ nimber(Kn−i−1 ), nimber(Ki ) ⊕ nimber(Kn−i−2 ) | i = 0, 1, . . . n − 2} – followers(Kn ) ⇒ nimber(Kn ) RECURRENCE! — write what you want in terms of smaller things How do we compute it? nimber(K0 ) = 0 nimber(K1 ) = = nimber(K2 ) = = (BASE CASE) mex{nimber(K0 ) ⊕ nimber(K0 )} 0 ⊕ 0 = 0 1 mex{nimber(K0 ) ⊕ nimber(K1 ), 0 ⊕ 1 = 1 nimber(K0 ) ⊕ nimber(K0 )} 0 ⊕ 0 = 0 2 so e.g. K2 + ∗2 = 0 ⇒ 2nd player win nimber(K3 ) = = mex{nimber(K0 ) ⊕ nimber(K2 ), 0 ⊕ 2 = 2 nimber(K0 ) ⊕ nimber(K1 ), 0 ⊕ 1 = 1 nimber(K1 ) ⊕ nimber(K1 )} 1 ⊕ 1 = 0 3 2 nimber(K4 ) = = mex{nimber(K0 ) ⊕ nimber(K3 ), 0 ⊕ 3 = 3 nimber(K0 ) ⊕ nimber(K2 ), 0 ⊕ 2 = 2 nimber(K1 ) ⊕ nimber(K2 ), 1 ⊕ 2 = 3 nimber(K1 ) ⊕ nimber(K1 )} 1 ⊕ 1 = 0 1 In general: if we compute nimber(K0 ), nimber(K1 ), nimber(K2 ), . . . in order, then we always use nimbers that we’ve already computed (because smaller) – in Python, can do this with for loop: k = {} for n in range(0, 1000): k[n] = mex ([k[i] ˆ k[n - i - 1] for i in range(n)] + [k[i] ˆ k[n - i - 2] for i in range(n - 1)]) print n, ”-”, k[ ] def mex(nimbers): nimbers = set(nimbers) n=0 while n in nimbers: n=n+1 return n 960 – 4 972 – 4 961 – 1 973 – 1 962 – 2 974 – 2 963 – 8 975 – 8 964 – 1 976 – 1 965 – 4 977 – 4 966 – 7 978 – 7 967 – 2 979 – 2 968 – 1 980 – 1 969 – 8 981 – 8 970 – 2 982 – 2 971 – 7 983 – 7 periodic mod 12! (starting at ‘72) [Guy & Smith 1972] DYNAMIC PROGRAMMING How fast? to compute nimber(Kn ): – – – – – look up ≈ 4n previous nimbers compute ≈ 2n nimsums (XOR) compute one mex on ≈ 2n nimbers call all this O(n) work “order n” need to do this for n = 0, 1, . . . , m � m � � � m � � m(m + 1) ⇒ n =O = O(n2 ) O(n) = O 2 n=0 n=0 POLYNOMIAL TIME — GOOD 3 984 985 986 987 988 989 990 991 992 993 994 995 – – – – – – – – – – – – 4 1 2 8 1 4 7 2 1 8 2 7 Variations: dynamic programming also works for: – Kayles on a cycle (1 move reduces to regular Kayles ⇒ 2nd player win) target vertex or 2 adj. vertices – Kayles on a tree: – Kayles with various ball sizes: hit 1 or 2 or 3 pins (still 1st player win) Cram: impartial Domineering – board = m × n rectangle, possibly with holes – move = place a domino (make 1 × 2 hole) Symmetry strategies: [Gardner 1986] – even × even: reflect in both axes ⇒ 1st player win – even × odd: play 2 center �s then reflect in both axes ⇒ 1st player win – odd × odd: OPEN who wins? Liner Cram = 1 × n cram – easy with dynamic programming – also periodic [Guy & Smith 1956] – 1 × 3 blocks still easy with DP – OPEN : periodic? Horizontal Cram: 1 only ⇒ sum of linear crams! Let’s play! 2 × n Cram: Nimbers OPEN 3 × n Cram: winner OPEN (dynamic programming doesn’t work) 4