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 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
key words Rating Algorithm, Multi-player Games, Imperfect Information Games, Daihinmin iv
1 1 1.1.............................. 1 1.2................................... 2 1.3................................. 2 2 4 3 6 4 8 4.1...................... 8 4.2................. 9 5 2 11 5.1................................... 11 5.2................................... 12 6 16 6.1................................... 16 6.2................................... 17 7 19 20 21 v
3.1........................ 7 4.1................... 10 5.1 1500............................ 14 5.2 1500.................................... 14 5.3 0.9 0.1 1500................................. 14 5.4 1700............................ 15 5.5 1700.................................... 15 5.6 0.9 0.1 1700................................. 15 6.1............................ 18 vi
1 1.1 [5][7] [1]. 2 1
1.2 1.2 Glicko 2 [2] RD ±2RD 95% 1850 50 95% 1750 1950 [6] 2 1.3 2 3 2
1.3 4 5 6 7 3
2 0 2 14 2 15 16 1 1 8 3 1 [3] 1 1 2 2 1 3 0 4 1 5 2 4
( ) 8 8 3 3 3 3 5
3 [1] 2 2. R a R b A B A B e ab e ab = 1 1 + 10 (R a R b )/400) (3.1) 600 600 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 1500 1 0 e ab =0.76 A A 1703.84 A A 1687.84 6
1 Expected Winning Rate 0.75 0.5 0.25 0-600-500-400-300-200-100 0 100 200 300 400 500 600 Rate Difference 3.1 7
4 2 4.1 3 8
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 = 1 1 + 10 ((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 1500 0.1 f ab (0.1) = 0.26 A 1695.84 ( ) 1687.4 4.2 2 9
4.2 Expected Winning Rate 1 0.75 0.5 0.25 p=0.8 p=0.5 p=0.2 0-600-500-400-300-200-100 0 100 200 300 400 500 600 Rate Difference 4.1 R i j P,j i = (R i + K(s ij e ij )) P 1 (4.2) P 1 1500 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 ((1500 + 16(1 0.64)) + (1500 + 16(1 0.47)) 4 + (1500 + 16(1 0.33)) + (1500 + 16(1 0.30))) = 1509.04 10
5 2 2 5.1 3.1 3 none: 2 P a = 0.5 gauss: 0.5 0.25 binary: 0.9 0.1 2 2 0 1500 400 1700 1 1000 1000 1 3 11
5.2 ( 0 0.05) 5.2 1500 5.1 1500 1498 1501 5.2 5.3 1700 5.4 1701 1607 1501 5.5 5.6 12
5.2 13
5.2 1 0.9 BaseWR=binary BaseWR=gauss BaseWR=none 0.8 0.7 Cumulative Frequency 0.6 0.5 0.4 0.3 0.2 0.1 5.1 0 1450 1500 1550 1600 1650 1700 1750 1800 Rate 1500 5.2 Cumulative Frequency 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 Elo Proposed w Error 0 1450 1500 1550 1600 1650 1700 1750 1800 Rate 1500 5.3 Cumulative Frequency 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 Elo Proposed w Error 0 1450 1500 1550 1600 1650 1700 1750 1800 Rate 0.9 0.1 1500 14
5.2 1 0.9 BaseWR=binary BaseWR=gauss BaseWR=none 0.8 0.7 Cumulative Frequency 0.6 0.5 0.4 0.3 0.2 0.1 5.4 0 1450 1500 1550 1600 1650 1700 1750 1800 Rate 1700 5.5 Cumulative Frequency 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 Elo Proposed w Error 0 1450 1500 1550 1600 1650 1700 1750 1800 Rate 1700 5.6 Cumulative Frequency 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 Elo Proposed w Error 0 1450 1500 1550 1600 1650 1700 1750 1800 Rate 0.9 0.1 1700 15
6 (UECda) 6.1 9 5 Java UECda 30 1 1 2000 2000 9 fugo 06 TaiTai 2006 UECda 2007 UECda yupi2 08 2008 UECda fumiya Party 2009 UECda 2012 UECda 16
6.2 paoon 2012 UECda Nakanaka UECda Montecarlo [8] sample UECda Java (2 ) [9] 1 2 1 5 1 3 4 2 5 2 3 2 3 5 1 10000 6.2 6.1 UECda fumiya(2009) yupi2(2008) 2012 Party Nakanaka Party Nakanaka Nakanaka [4] [8] TaiTai(2007) 100 17
6.2 Rate 1900 1850 1800 1750 1700 1650 1600 1550 1500 1450 1400 1350 1300 1250 1200 1150 1100 1050 1000 sample fugo_06 Montecarlo Party TaiTai fumiya yupi2_08 Nakanaka paoon 6.1 18
7 2 0 400 19
20
[1] Arpad E. Elo: The Rating of Chessplayers Past&Present. Ishi Press International, 2008. [2] Mark E. Glickman: Example of the Glicko-2system. http://www.glicko.net/glicko/glicko2.pdf, 2014. [3] 5 UEC 20101114. http://uecda.nishinolab.jp/2010/man/index.html. [4] UECda2012, http://uecda.nishino-lab.jp/2012/result.html, 2014. [5] World Chess Federation, http://www.fide.com/, 2014. [6] :., GI, [ ], Vol. 2008-GI- 59,pp. 17-22, 2008. [7] 24, http://shogidojo.com/, 2014. [8], :., GI, [ ] Vol. 2013-GI- 29, pp. 1 6, 2013. [9] :., Vol. 49, No. 6, pp. 686 693, 2008 21