Vol.55 No (Nov. 2014) Hex 1,a) 1,b) 1,c) 1,d) , Hex 2 Hex Hex Hex Hex Hex Hex Hex Development of Computer Hex Strategy

Size: px

Start display at page:

Download "Vol.55 No (Nov. 2014) Hex 1,a) 1,b) 1,c) 1,d) , Hex 2 Hex Hex Hex Hex Hex Hex Hex Development of Computer Hex Strategy"

れれすみい
4 years ago
Views:

1 Hex 1,a) 1,b) 1,c) 1,d) , Hex 2 Hex Hex Hex Hex Hex Hex Hex Development of Computer Hex Strategy Using Network Characteristics Kei Takada 1,a) Masaya Honjo 1,b) Hiroyuki Iizuka 1,c) Masahito Yamamoto 1,d) Received: February 21, 2014, Accepted: September 12, 2014 Abstract: The game of Hex is the board game with simple rules and is classified as a two-player, zero-sum, logical perfect information game. The game proceeds by players putting their pieces in turn on empty cells of the board. A player wins if player connects the two opposing sides of the board of their own color their pieces. The study of computer Hex is popular enough that there is an international tournament of computer Hex. The electrical circuit model is a well-known method to evaluate boards in conventional studies. The present study investigates an evaluation method using network characteristics obtained from the board, in order to capture board states from different perspectives. To clarify the relation between the network characteristics and Hex strategies, game records by human experts were used. As a result, we found that the averages of shortest path lengths and betweenness centrality show a relationship in the winner s records. Therefore, we propose a novel evaluation function using these two network characteristics and evaluate its effectiveness. Our results shows that it is possible to develop a strong computer hex program using these network characteristics. Keywords: Hex, game, network, betweenness centrality, evaluation function 1 Graduate Schoool of Information Science and Technology Hokkaido University, Sapporo, Hokkaido , Japan a) takada@complex.ist.hokudai.ac.jp b) honjyo@complex.ist.hokudai.ac.jp c) iizuka@complex.ist.hokudai.ac.jp d) masahito@complex.ist.hokudai.ac.jp 1. Hex 1942 Piet Hein 1948 John Nash 2 [1] 2 c 2014 Information Processing Society of Japan 2421

n m n m 1 2 n n Hex 11 11 Hex [2] [3] Hex 2 1 2 Hex 9 9 [4] 2013 9 9 [5] 1 Hex Hex Hex Hexy 2000 [6], [7] Hex Minimax 2 2013 1 Hex UCT UCB applied to tree MoHex [8] 2 EZO [9] Hex [10] Hexy Six [11]

2 n m n m 1 2 n n Hex Hex [2] [3] Hex Hex 9 9 [4] [5] 1 Hex Hex Hex Hexy 2000 [6], [7] Hex Minimax Hex UCT UCB applied to tree MoHex [8] 2 EZO [9] Hex [10] Hexy Six [11] Wolve [12] UCT Hex Hex 2. Hex 2.1 N M G(V,E) V = {v 0,v 1,..., v N } E = {e 0,e 1,..., e M } Hex Fig Hex gameboard. Fig Example of Hex position on a 5 5 board. Fig. 2 2 Gameboard showing a winning configuration for White. 4 3 Fig. 4 Position network of Fig. 3. c 2014 Information Processing Society of Japan 2422

3 v s,v t v s v t v i v j d(v i,v j ) v i L i L i = 1 (N 1) N d(v i,v j ), (1) j=1 d(v i,v i )=0 L (2) L = 1 N N L i (2) i= v i b i v i (3) b i = 2 (N 1)(N 2) N k=1 j=1 N g(i, k, j), (3) g(i, k, j) v i v k v j 1 0 i = k j = k i = j d(i, k, j) =0 B (4) x y V x, y x, y x, y V x, A, y x, y A AND Deduction Rule x, A, u u, B, y u A B = φ x, A B,y 5 (a) OR Deduction Rule x, A k,u k u k,b k,y k u k x, D, y 5(b) (x A k = φ) (y B k = φ) (forallk =1, 2,..., n) A k B k = φ (for all k =1, 2,..., n) C k = A k u k B k n D = k=1 C k H-search H-search AND Deduction Rule OR Deduction Rule [13] 2.3 Hex 2 G b B (V,E) G b W (V,E) V B = 1 N N b i (4) i= [6] x y Fig. 5 5 Method of detecting virtual connections. c 2014 Information Processing Society of Japan 2423

4 6 4 Fig. 6 Position network of Fig. 4 after adding virtual connections. Fig. 7 7 d Ration d of the shortest path lengths for turns. E 4 G b B (V,E) Gb W (V,E) G b B 6 3 (1) i v i V E (2) C i C(v i )=0 i C(v i )=1 C(v i )= 1 (3) 2 v s,v t V (C(v s )= 1,C(v t )=1)) (4) 2 (v i,v j ) e(v i,v j ) (5) v i (C(v i )= 1) v i e(v i,v j ) (6) G b (V,E) H-search E (7) v s,v t v i (C(v i )=1) v i e(v i,v j ) 3. Hex Hex Hex (v s,v t ) d(v s,v t ) B L 3.1 Hex Richard Rognlie s Gamerz.NET server [1] % (v s,v t ) G b B (V,E) (v s,v t ) d B (v s,v t ) G b W (V,E) (v s,v t ) d W (v s,v t ) d B (v s,v t ) d W (v s,v t ) d d = d W (v s,v t ) d B (v s,v t ) (5) d 7 (a) d 7(b) d d>1 d<1 3.3 Hex G b B (V,E) L B G b W (V,E) L W L c 2014 Information Processing Society of Japan 2424

5 Fig. 8 8 L Ration L of the average of shortest path lengths for turns. 10 C L Fig. 10 Correlation between averages of betweenness centrality C and shortest path L. Fig. 9 9 C Ration C of the average of betweenness centrality for turns. L = L W (6) L B G b B (V,E) C B G b W (V,E) C W C Fig Strategy of an expert player. C = C W (7) C B L 8 C (a) 9(a) 8(b) 9(b) 8 9 L>1 C >1 L<1 C < L C = 14,520 L C L C Hex C 1 C C C C 4. 2 c 2014 Information Processing Society of Japan 2425

6 4.1 Ev Ev = C W, (8) C B C B G b B (V,E) C W G b W (V,E) 4.2 Ev Hexy UCT Hex Ev Hex Hexy UCT Hexy Expert UCT Hex UCT 100 5,000 ucb1 2log(n) ucb1 i = w i +0.38, (9) n i w i i n i i n E v E v UCT Hex Hexy Ev Hex 2 Ev Hex UCT Hex 200 Hexy UCT Hex 100 Hexy Hex / Table 1 Win-loss records among computer Hex programs (the number of wins over matches). Ev Hexy UCT Ev ( ) 1/1 (100.0%) 159/200 (79.5%) Hexy ( ) 1/1 (100.0%) 100/100 (100.0%) UCT ( ) 58/200 (29.0%) 4/100 (4.0%) ,900 2 Phenom II X GHz 1 1 Ev Hex UCT 79.5% 71.0% UCT Ev Hexy Ev Hexy UCT 100% 96% Ev Hexy Ev Hexy 4.3 Hex C (v s,v t ) (v s,v t ) (v s,v t ) (v s,v t ) Ev 5. (v s,v t ) (v s,v t ) 5.1 (v s,v t ) G b (V,E) (v s,v t ) G p (V,E ) c 2014 Information Processing Society of Japan 2426

7 12 G p (V,E ) Fig. 12 Processes of creating G p (V,E ) Fig. 14 Values of betweenness centrality for each node. b i = n i N, (10) N (v s,v t ) n i v i (v s,v t ) G p (V,E ) Fig. 13 Examples of the shortest path network G p (V,E ). V ( V ) G b (V,E) (v s,v t ) E ( E) G b (V,E) (v s,v t ) G p B (V,E ) G p W (V,E ) G b (V,E) G p (V,E ) 12 G p (V,E ) (v s,v t ) G p (V,E ) (v s,v t ) (v s,v t ) G p (V,E ) 13 (v s,v t ) (v s,v t ) G p (V,E ) G p (V,E ) G p (V,E ) (v s,v t ) 5.3 G p (V,E ) G p (V,E ) (v s,v t ) v i ( V ) b i 5.4 G p (V,E ) G p (V,E ) (v s,v t ) 14 G p (V,E ) 14 G p (V,E ) (b i =1.0) 1 (b i =1.0) (v s,v t ) G p (V,E ) 5.5 G b (V,E) (v s,v t ) G p (V,E ) Ev Ev Ev = C W C B + γ C W C B, (11) C G b (V,E) C G p (V,E ) B W γ(γ >0) 5.6 Ev UCT c 2014 Information Processing Society of Japan 2427

8 Table 2 Table 3 2 Ev 200 Winning rates of Ev (200 trials for each parameter). γ Ev ( ) Ev ( ) % 71.0% % 73.0% % 76.5% % 74.0% % 70.0% % 74.0% % 64.5% % 61.0% % 52.5% % 73.0% % 56.5% 3 B 200 Winning rates of B (200 trials for each). UCT B ( ) 69.0% B ( ) 57.0% Hex γ Hex UCT Hex UCT Hex Ev γ Ev Hex 2 UCT Hex Ev γ Ev Hex γ =0.0 Ev 2 γ =0.10 γ =0.50 B B B = C W C B (12) (v s,v t ) B 4 Hex / Table 4 Win-loss records among computer Hex programs (the number of wins over matches). Ev Hexy Wolve MoHex Ev ( ) 1/1 1/1 4/10 Hexy ( ) 1/1 0/1 3/10 Wolve ( ) 1/1 1/1 10/10 MoHex ( ) 10/10 10/10 9/ Hex UCT γ 2000 Hexy 2008 Wolve 2009 MoHex Hexy Wolve MoHex Hexy Wolve Minimax MoHex UCT MoHex Hexy Expert MoHex Hex Ev Hex 2 Ev γ γ =0.10 γ = Hexy Hexy Wolve MoHex Wolve MoHex Hexy Wolve MoHex Hexy Wolve MoHex Hexy Wolve Hexy Wolve Hexy Wolve Hexy 2 Wolve 4 1 Wolve c 2014 Information Processing Society of Japan 2428

9 Hexy 5.7 (v s,v t ) Hex (v s,v t ) Hexy Hexy Wole MoHex 4 Wolve MoHex Hexy γ Hexy UCT UCT Hexy UCT UCT Wolve MoHex Hex 6. (v s,v t ) Hex Hex (v s,v t ) Hex swap / 1 swap swap [1] Browne, C.: Hex Strategy Makin the Right Connections, A K Peters Ltd. (2000). [2] Gale, D.: The Game of Hex and the Brouwer Fixrd- Point Theorem, The American Mathematical Monthly, Vol.75, No.10, pp (1979). [3] Even, S. and Tarjan, R.E.: A Combinatorial Problem Which Is Complete in Polynomial Space, Jounal of Assocuation for Computing Maxhinery, Vol.23, No.4, pp (1976). [4] Hex Vol.50, No.2, pp (2009). [5] Pawlewicz, J. and Hayward, R.: Scalable Parallel DFPN Search, Computers and Games CG201 (2013). [6] Anshelevich, V.V.: The game of Hex: An automatic theorem proving approach to game programming, Proc. AAAI-2000, Austin, TX, AAAI Press, Menlo Park, CA/The MIT Press, Cambridge, MA (2000). [7] Anshelevich, V.V.: Hexy Wins Hex Tournament, ICGA Journal, Vol.23, No.3, pp (2000). [8] Arneson, B., Hayward, R. and Henderson, P.: Monte Carlo Tree Search in Hex, IEEE Trans. Computational Intelligence and AI in Games, Vol.2, No.4, pp (2010). [9] Hayward, R., Arneson, B., Huang, S., et al.: Mohex Wins Hex Tournament, ICGA Jounal, Vol.36, No.3, pp (2013). [10] Shannon, C.E.: Computer and Automata, Proc. IRE, Vol.41, No.10, pp (1953). [11] Hayward, R., Arneson, B. and Henderson, P.: Mohex Wins Hex Tournament, ICGA Jounal, Vol.32, No.2, pp (2009). c 2014 Information Processing Society of Japan 2429

10 [12] Henderson, P.: Playing and solving the game of Hex, Doctoral Dissertation, pp (2010). [13] Anshelevich, V.V.: A hierarchical approach to computer Hex, Artificial Inteligence, Vol.134, No.1-2, pp (2002) PD PD c 2014 Information Processing Society of Japan 2430

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