[1] Google AlphaGo [2] AI [3], [4] [5], [6] 1 [7] [8], [9] IEEE-CIG 2015 AI [10] GPW AI 2 AI GCCS AI Expectimax [11] A

Size: px

Start display at page:

Download "[1] Google AlphaGo [2] AI [3], [4] [5], [6] 1 [7] [8], [9] IEEE-CIG 2015 AI [10] GPW AI 2 AI GCCS AI Expectimax [11] A"

かずしみやまる
5 years ago
Views:

1 1,a) 1,b) 1,c) , AI AI Expectimax Expectimax AI Expectimax A Method of Game Tree Search in Digital Curling Including Uncertainty Shu Katoh 1,a) Hiroyuki Iizuka 1,b) Masahito Yamamoto 1,c) Received: February 20, 2016, Accepted: September 6, 2016 Abstract: Computer AI game players have beaten human expert players in two players zero-sum perfect information games such as Go and Japanese Chess and the focus is moving to multiple players, imperfect information games and even with uncertainty such as Mah-jong and Werewolf. Digital curling is one of the games with uncertainty. It has been developed as a testbed of the games with uncertainty to compete computer AI programs and to analyze the curling strategies of human players. This paper proposes an expectimax game tree search method for the digital curling where candidate moves are represented as the combination of the throwing-target position and rotational direction of stones and the discretized board states are nodes of the tree. The method can take into account uncertainty using stochastic transition in the game tree. To evaluate our proposed method, we compare the winning rates of the methods with and without the stochasticity while changing the searching depth. Our results show that our proposed method with the stochasticity is better than without the stochasticity and can only show the effective look ahead. From those results, it is shown that our proposed method could handle uncertainty and perform effective tree search on digital curling. Keywords: digital curling, stochastic game, game tree, expectimax 1 Graduate Schoool of Information Science and Technology Hokkaido University, Sapporo, Hokkaido , Japan a) shu.kato@complex.ist.hokudai.ac.jp b) iizuka@complex.ist.hokudai.ac.jp c) masahito@complex.ist.hokudai.ac.jp 1. AI 1997 IBM c 2016 Information Processing Society of Japan 2354

2 [1] Google AlphaGo [2] AI [3], [4] [5], [6] 1 [7] [8], [9] IEEE-CIG 2015 AI [10] GPW AI 2 AI GCCS AI Expectimax [11] AI Fig. 1 Example of scoring (yellow 2 points, red 0 point). c 2016 Information Processing Society of Japan 2355

3 2 Fig. 2 Curling Rink v R s t s t+1 (1) s t+1 = f(v,r,s t ) (1) v R R R R L 2 s t R v q 1 1 (v,r)=g(q,r) (2) (q,r)=g 1 (v,r) (3) v m v r v m v r (1) 0 σ x σ y r x r y r (2) p h v h (v h,r)=g 1 (p h,r) (4) (3) p h r v h (v h,r)=g 1 ((p h + r),r) (5) (4) v h v h v r v r = v h v h (6) v m R m v r v m s t+1 (7) s t+1 = f((v m + v r ),R,s t ) (7) v m g(v m,r m ) q m g((v m + v r ),R m ) q m q m q m r v m r r x r y σ x σ y UEC σ x σ y 0.145m 3 c 2016 Information Processing Society of Japan 2356

4 Expectimax Fig. 4 Game tree of Expectimax. 3 Fig. 3 Snapshot of digital curling. x y x y 3. Expectimax q R Expectimax Minimax Minimax q m 1 m 1 m m M M (m) 4 Minimax 5 Q = Q p + Q f Q U q Fig.

4 4 Expectimax Fig. 4 Game tree of Expectimax. 3 Fig. 3 Snapshot of digital curling. x y x y 3. Expectimax q R Expectimax Minimax Minimax q m 1 m 1 m m M M (m) 4 Minimax 5 Q = Q p + Q f Q U q Fig. 5 Left: Discretized target positions for delivering stones. Q p is mainly for draw shots and Q f is for take-out shots. Right: Discretized possible result positions, U q, by candidate moves because of noise. (1) M (2) M (m) (3) (4) 3.1 M M q Q R (8) Q Q p Q f 2 5 Q p (9) Q f 1 (10) (11) Q p Q f Q p x y r s Q f 0.5r s (9) p hx p hy x y (9) (10) (11) Z c 2016 Information Processing Society of Japan 2357

5 M = {m m =(q,r), q Q(R), Q(R) =Q p (R)+Q f (R), R {R R,R L }} (8) Q p (R R )=Q p (R L ) = {q q =(x, y), x = p hx + r s s, y = p hy + r s t, 13 s +13, 17 t +41, s, t Z} (9) Q f (R R )={q q =(x, y), x = r s s, y =6.039, 0 s 71, s Z} (10) Q f (R L )={q q =(x, y), x = r s s, y =6.039, 0 s 71, s Z} (11) Q p (R R ) = Q p (R L ) = 1593 (12) Q f (R R ) = Q f (R L ) = 72 (13) 6 Fig. 6 m m U m m Top: Possible results by candidates moves. Middle: Sharing the possible results among different candidates moves. Bottom: Our sharing method for digital curling. 3.2 M (m) AI CueCard m M (m) m 1 m 2 M (m 1 ) M (m 2 ) 6 m 1 m 2 M (m 1 ) M (m 2 ) m m 1 m m m M (m) m M m U m (14) M (m) U m (15) m M (m) 6 7 m 1 m 2 m Fig. 7 A resulting move is shared between candidate move m 1 and m 2 (game tree). U m (R) ={m m =(q,r), q U q (R)} (14) M (m =(q,r)) = {m m =(q,r), q q 3r s q U q (R)} (15) (14) (15) U q M Q 5 Q m M (m) Q 3r s (15) m M (m q q 3r s 4 σ x = r s σ y = r s m h =(q h,r) m h c 2016 Information Processing Society of Japan 2358

6 m h =(q h,r) q h q h 3r s 99.7% Q f m f y v r y M (m f ) x 1 y M (m) M (m) 3.3 m M m M (m) p(m, m ) m M m M (m) p(m, m ) m =(q,r) m r =(q r,r) 10 m =(q,r) M (m) q q r M (m) m M Match Equity Table [12] or 3 e(s) (16) e(s) =W (s)+μ u(s, i)n(s, i) (16) i W (s) s 8 s W (s) s 8 s s μ i u(s, i)n(s, i) μ u(s, i) s i b(s, i) +1 1 N(s, i) b(s, i) (17) N(s, i) =J(s, i) T (s, i) D(s, i) (17) J(s, i) b(s, i) T (s, i) b(s, i) D(s, i) b(s, i) b(s, i) J(s, i) J(s, i) (18) J(s, i) =w 1 k(s, i)+w 2 h(s, i) (18) w 1 w 2 k(s, i) b(s, i) h(s, i) b(s, i) (19) (22) 1 k(s, i) = (19) 1+n s (s, i) h(s, i) =h x (s, i) h y (s, i) (20) h x (s, i) = 1 x p hx ( x p hx <α) α (21) 0 (otherwise) (y p hy + β) 2 β 2 (p hy β y<p hy ) h y (s, i) = 1 (y p hy) 2 (22) γ 2 (p hy y<p hy + γ) 0 (otherwise) c 2016 Information Processing Society of Japan 2359

8 b(s, i) J(s, i) b(s, i) D(s, i) T (s, i) Fig.

and the other pictures are value when b(s, i) is already put and putting another stone on each coordinates (D(s, i): figure in the upper

(19) n s (s, i) b(s, i) (20) h x (s, i) h y (s, i) b(s, i) x y h(s, i) (21) (22) x y b(s, i) x y p hx p hy x y α β γ h(s, i) b(s, i) 2 h(s,

2 b(s, i) T (s, i) T (s, i) (23) T (s, i) =min(o(s, i, R)) + c (23) o(s, i, R) R b(s, i) c T (s, i) 0 b b b b b b b r s /6 24 b t b 1 0 24

7 8 b(s, i) J(s, i) b(s, i) D(s, i) T (s, i) Fig. 8 Heat map of value of J(s, i), T (s, i) andd(s, i), figure in the upper left is value of J(s, i) when puting b(s, i) on each coordinates, and the other pictures are value when b(s, i) is already put and putting another stone on each coordinates (D(s, i): figure in the upper right, T (s, i): figure below left and right). (19) n s (s, i) b(s, i) (20) h x (s, i) h y (s, i) b(s, i) x y h(s, i) (21) (22) x y b(s, i) x y p hx p hy x y α β γ h(s, i) b(s, i) 2 h(s, i) b(s, i) T (s, i) T (s, i) (23) T (s, i) =min(o(s, i, R)) + c (23) o(s, i, R) R b(s, i) c T (s, i) 0 b b b b b b b r s /6 24 b t b bit bit b t R R R L 2 b b b b 24 bit bit O f b b O b b t 24 b(s, i) b(s, i) o(s, i, R) =w 3 o (o f (s, i, R)) + w 4 o (o b (s, i, R)) (24) 1 o (o f (s, i, R)) = o (25) (o f (s, i, R)) o (o b (s, i, R)) = o (26) (o b (s, i, R)) + 1 w 3 w 4 o f (s, i) b(s, i) s b(s, i) o b (s, i) b(s, i) s b(s, i) O f O b bit AND o bit bit 1 b(s, i) T (s, i) b(s, i) D(s, i) 2 D(s, i) (27) (29) D(s, i) =min(d i,j) (27) c 2016 Information Processing Society of Japan 2360

8 Table 1 1 Winning percentage table (second player). 9 D(s, i) Fig. 9 Difficulty of double takeout D(s, i). D i,j d2 i,j = D i,j 2 (d i,j <D i,j ) 1 (otherwise) (28) D i,j = a + b cos θ i,j (29) j i (29) a b θ i,j y b(s, i) b(s, j) (28) d i,j b(s, i) b(s, j) 9 D i,j b(s, i) b(s, j) or (1) GPW 1 (2) 0 100% 0% 0 (1) 1 1 (3) (2) 1 (2) (4) (2) % 97% 99% 100% +2 88% 91% 96% 100% +1 77% 80% 87% 100% ±0 62% 61% 73% 73% 1 45% 39% 47% 0% 2 29% 22% 24% 0% 3 16% 10% 8% 0% AI UEC AI GCCS GCCS 1 UEC GPW AI Q p 10 2 y Q p ,458 2,082 c 2016 Information Processing Society of Japan 2361

9 2 100 Table 2 Winning rate of victory of jiritsu-kun in 100 games % (±5.2%) 10.9% (±3.1%) % (±3.7%) 7.9% (±2.7%) Table 3 3 Score distributions when jiritsu-kun is the first player. 10 Fig. 10 Resulting moves made from filled circle coordinates is substituted by resulting moves made from circle coordinates. { μ = 0.1 (if the first player s turn) 0.2 (otherwise) (30) w 1 =1.0 (31) w 2 =1.0 (32) α = r h1 + r s (33) β = r h2 (34) γ = r h1 + r s (35) w 3 =1.0 (36) w 4 =2.0 (37) a =0.915 (38) b = r h1 (39) c =0.3 (40) r h1 = r h2 =1.22 r s = , Intel Xeon GHz % 0% 0% 0% 2 3% 4% 1% 0% 1 11% 15% 6% 2% 0 4% 6% 0% 1% 1 47% 50% 47% 46% 2 24% 18% 28% 30% 3 9% 5% 14% 15% Table 4 Score distributions when jiritsu-kun is the second player % 13% 5% 5% 2 21% 27% 16% 16% 1 52% 44% 37% 38% 0 5% 0% 3% 8% 1 11% 8% 25% 22% 2 3% 2% 8% 7% 3 1% 0% 2% 3% GCCS % 0% c 2016 Information Processing Society of Japan 2362

10 % Welch t % Z 1 GCCS Fig Example of move without considering uncertainty at depth AI AI 12 Fig. 12 Comparison of move bitween depth 1 and depth 2 (uncertainty is considered). [1] Campbell, M., Hoane, J.A., Hsu, F., et al.: Deep blue, Artificial Intelligence, Vol.134, No.1-2, pp (2002). [2] Silver, D., Huang, A., Maddison, J.C., et al.: Mastering the game of Go with deep neural networks and tree search, Nature, Vol.529, pp (2016). [3] Vol.55, No.11, pp (2014). [4] Vol.20, pp.1 3 (2014). [5] Smith, M.: Pickpocket: A computer billiards shark, Artificial Intelligence, Vol.171, pp (2007). [6] Altman, A., Archibald, C. and Shoham, Y.: Analysis of awinning computational billiards player, Artificial Intelligence, Vol.171, pp (2009). [7] Coleman, G.: Introduction to Curling Strategy (2014). [8] Vol.GI31, No.2, pp.1 5 (2014). [9] curling/wiki.cgi c 2016 Information Processing Society of Japan 2363

[10] 14 FIT2015 No.14, pp.313 314 (2015). [11] Michie, D.

http://www.bkgm.com/articles/gol/demo/ equity.

11 [10] 14 FIT2015 No.14, pp (2015). [11] Michie, D.: Advances in programming and nonnumerical computation, pp (1966). [12] Backgammon Galore: Match Equity Table, available from equity.htm (accessed ) PD PD c 2016 Information Processing Society of Japan 2364

2 ( ) i

2 ( ) i 25 Study on Rating System in Multi-player Games with Imperfect Information 1165069 2014 2 28 2 ( ) i ii Abstract Study on Rating System in Multi-player Games with Imperfect Information Shigehiko MORITA