24 19 19115096
i 1 1 2 2 2.1..................................... 2 2.2....................... 3 2.3................................... 3 2.3.1.................. 4 2.4............................... 4 2.4.1............................. 4 2.4.2........................... 4 2.4.3.......................... 5 2.5................................ 9 2.5.1............................... 9 2.5.2............................ 9 2.6................................ 9 3 9 3.1 Bonanza................................... 10 3.2 Puella................................... 10 3.3..................................... 10 3.4 GPS.................................. 10 4 12 4.1................................ 13 4.2 GPS............................ 13 4.2.1 PV.............................. 16 5 17
ii 6 19 7 21 7.1.................................... 21 7.2................................. 21
1. 1 1 2006 2006 Bonanza Method[1] 2.5 GPS 2 GPS 3 4 5 6 7
2. 2 2 2.1 2 9 9 2 1 1 1: 0
2. 3 2.2 10 123 10 226 [2] 100 2.3 2.4.2 13 [3]
2. 4 2.3.1 Bonanza 16 Bonanza [1] [4][5] 2.4 2.4.1 (Breadth First Search BFS ) (Depth First Search DFS ) BFS DFS 1 2 BFS 2.4.2 2
2. 5 2: 2.5 1 1. C H I +1 2. D E F G 1 3. A C D E +1 4. B 3 5. A B +1 A 2.4.3 2.4.3
2. 6 先手 +1 後手 A +1 B -8 先手 C D E F G +1 +3 +4-8 +2 後手 H I J K L M -2 +1 +3-4 -7 +4 1:
2. 7 2 2 A K 1. C +1 A +1 2. J +3 D +3 3. A C D E 4. 2 D A K B 1. A +1 +1 2. F -8 B -8 3. A B 4. 2 B G
2. 8 ベータカット 先手 +1 後手 アルファカット A +1 B -8 先手 C D E F G +1 +3 +4-8 +2 後手 H I J K L M -2 +1 +3-4 -7 +4 2:
3. 9 2.5 2.5.1 100% ( ) ( 1 ) ( ) [6] M M [7] 2.5.2 [8] 2.6 1 3 3 1
3. 10 3.1 Bonanza 16 [9] Bonanza [1] Bonanza Bonanza 3.2 Puella 21 Bonanza Bonanza 2011 24[10] 9 4 7 3200 3300 22 3.3 15 18 20 [11] 3.4 GPS 19 22 [12]
3. 11 2012 22 797 6 1 1 1
4. 12 4 2.3 2.3.1 100 [1] +50 +30 2 [11] GPS [12] 2.5
4. 13 2012 GPS 4.1 1 99 [13] 4.2 GPS 1. bestmove 2. 3. bestmove
4. 14 ミニマックス法で候補手を探索 探索手の評価値が bestmove の評価値より高いか bestmove に探索手と評価値を設定 まだ探索していない候補手をミニマックス法で探索 全ての候補手を探索したか bestmove を返して着手 3:
4. 15 ミニマックス法で候補手を探索 Bestmove の評価値を少し低く見積もる 探索手の評価値が bestmove の評価値より高いか bestmove に探索手と評価値を設定 Bestmove の評価値を少し低く見積もる 全ての候補手を探索したか まだ探索していない候補手をミニマックス法で探索 bestmove を返して着手 4:
4. 16 4. bestmove bestmove bestmove 4.2.1 PV
5. 17 5 3 3: OS Ubuntu CPU Intel(R) Core(TM) i5 CPU 750 2.67GHz 8GB GPS r2749m (osl r4471, gpsshogi r2766) gpsshogi/bin gpsshogi.cc gpsshogi TCP/IP CSA [14] floodgate[15] 4 GPS floodgate 4: wdoor.c.u-tokyo.ac.jp 4081 25 500 200 GPS 100 200 5
5. 18 5: GPS 0 100 2 100
6. 19 6 GPS GPS 200 1 25 GPS 2 2 5 GPS 5:
6. 20 GPS GPS GPS 79 GPS GPS GPS GPS
7. 21 7 7.1 GPS GPS 7.2 1 (Node Per Second NPS) 2 5 8 [16] NPS GPS GPS GPS
7. 22 floodgate[15]
7. 23
24 [1].. 11, 2006, pp. 78 83, 2006. [2]. 2006., GI 2006(70), pp. 1 8, jun 2006. [3].. Vol. 52, No. 8, pp. 5 9, 2007. [4].., Vol. 27, No. 1, pp. 75 82, jan 2012. [5],. td( ) :bonanza. 73, 2011, pp. 5 7, mar 2011. [6]. http://www.logos.t.u-tokyo.ac.jp/ gekisashi/algorithm/abstract.html. [7]. 4. (< > )., Vol. 49, No. 8, pp. 982 986, aug 2008. [8]. http://www.logos.t.utokyo.ac.jp/ gekisashi/algorithm/index.html. [9] Bonanza. http://www.geocities.jp/bonanza shogi/. [10], 24. http://www.shogidojo.com/. [11]. http://www.logos.t.u-tokyo.ac.jp/ gekisashi/index.html. [12] GPS. http://gps.tanaka.ecc.u-tokyo.ac.jp/gpsshogi/. [13].., Vol. 81, No. 1, pp. 235 254, mar 1999.
25 [14] CSA. http://www.computer-shogi.org/protocol/. [15] floodgate. http://wdoor.c.utokyo.ac.jp/shogi/floodgate.html. [16] http://www.logos.t.u-tokyo.ac.jp/ gekisashi/strength.html, 2013.