2 ( ) i

Size: px

Start display at page:

Download "2 ( ) i"

さみごちょう
7 years ago
Views:

1 25 Study on Rating System in Multi-player Games with Imperfect Information

2 2 ( ) i

3 ii

4 Abstract Study on Rating System in Multi-player Games with Imperfect Information Shigehiko MORITA A rating system expresses the power of a player with a numerical value, which is computed from the outcomes of the games. In Elo rating, which is a well-known rating algorithm, the amount of increase or decrease of the rate depends the rate difference between the players. For example, if a player with the lower rate win against the other with the higher rate, then the player increase the rate a lot. In the game like Daihinmin, in which the winning rate also depends on the initial state of the game, the stronger player may be defeated by the bias of the initial state. In such a case, the amount of rate increase or decrease can be too much or too little in the Elo rating. We propose a rating algorithm that takes into account the relative advantage of the initial board, and evaluate the algorithm. We compute the advantage of initial board by simulation, and adjust the rate accordingly. By using a virtual two-person game, we compared the results of rating algorithms, the Elo rating and the proposed one, for the cases with and without rate differences. From the experiment results, we observe some shifts for the Elo rating, and have almost identical results for the proposed one. In addition, we compute the rate of Daihinmin players by the proposed method. We mainly used the players that won the first place or the second place in the previous-year computer Daihinmin tournament held at the University of Electro-Communications. The result shows that the rates of players increase over the years. iii

5 key words Rating Algorithm, Multi-player Games, Imperfect Information Games, Daihinmin iv

6 v

7 vi

8 1 1.1 [5][7] [1]. 2 1

9 Glicko 2 [2] RD ±2RD 95% % [6]

11 [3]

12 ( )

13 3 [1] 2 2. R a R b A B A B e ab e ab = (R a R b )/400) (3.1) A 1600 B 1500 e ab = 0.64 A B 64% A s ab A R a, R a = R a + K(s ab e ab ) (3.2) K K K = 16 A 1700 B e ab =0.76 A A A A

14 1 Expected Winning Rate Rate Difference 3.1 7

16 4.2 A p a P a (0 < p a < 1) e ab p f ab (p) p a e ab f ab p a = 0.5 f ab (0.5) = e ab f ab (p a ) = p a e ab = ((R a R b )/400+log(p a /(1 p a ))) (4.1) p a log p a 1 p a 4.1 p a = 0.8 p a = 0.5 p a = 0.2 A 1700 B f ab (0.1) = 0.26 A ( )

17 4.2 Expected Winning Rate p=0.8 p=0.5 p= Rate Difference 4.1 R i j P,j i = (R i + K(s ij e ij )) P 1 (4.2) P P 1 P 2 P 5 e 12 = 0.64 e 13 = 0.47 e 14 = 0.33 e 15 = 0.30 P 1 1 P 1 R 1 R 1 = 1 (( (1 0.64)) + ( (1 0.47)) 4 + ( (1 0.33)) + ( (1 0.30))) =

18 none: 2 P a = 0.5 gauss: binary:

19 5.2 ( )

20 5.2 13

21 BaseWR=binary BaseWR=gauss BaseWR=none Cumulative Frequency Rate Cumulative Frequency Elo Proposed w Error Rate Cumulative Frequency Elo Proposed w Error Rate

22 BaseWR=binary BaseWR=gauss BaseWR=none Cumulative Frequency Rate Cumulative Frequency Elo Proposed w Error Rate Cumulative Frequency Elo Proposed w Error Rate

23 6 (UECda) Java UECda fugo 06 TaiTai 2006 UECda 2007 UECda yupi UECda fumiya Party 2009 UECda 2012 UECda 16

24 6.2 paoon 2012 UECda Nakanaka UECda Montecarlo [8] sample UECda Java (2 ) [9] UECda fumiya(2009) yupi2(2008) 2012 Party Nakanaka Party Nakanaka Nakanaka [4] [8] TaiTai(2007)

25 6.2 Rate sample fugo_06 Montecarlo Party TaiTai fumiya yupi2_08 Nakanaka paoon

27 20

28 [1] Arpad E. Elo: The Rating of Chessplayers Past&Present. Ishi Press International, [2] Mark E. Glickman: Example of the Glicko-2system [3] 5 UEC [4] UECda2012, [5] World Chess Federation, [6] :., GI, [ ], Vol GI- 59,pp , [7] 24, [8], :., GI, [ ] Vol GI- 29, pp. 1 6, [9] :., Vol. 49, No. 6, pp ,

,,,,., C Java,,.,,.,., ,,.,, i

,,,,., C Java,,.,,.,., ,,.,, i 24 Development of the programming s learning tool for children be derived from maze 1130353 2013 3 1 ,,,,., C Java,,.,,.,., 1 6 1 2.,,.,, i Abstract Development of the programming s learning tool for children