世界コンピュータ将棋選手権参加報告 及び, GPS 将棋のアルゴリズム JST ERATO 湊プロジェクト研究員竹内聖悟 1
概観 世界コンピュータ将棋選手権の紹介 今年は GPS 将棋が優勝 上位 5 プログラムがプロ棋士と対局予定 コンピュータ将棋のアルゴリズム GPS 将棋と そのアルゴリズムを紹介 約 800 台のマシンで疎結合並列探索 2
あらためて自己紹介 竹内聖悟 JST ERATO 湊プロジェクト研究員 ( 札幌 ) GPS 将棋の開発メンバー GPS = Game Programming Seminar 東大総合文化研究科の教員と学生が中心となって開催しているゼミ @ 駒場 コンピュータ将棋 囲碁やチェスの研究 性能評価 探索制御など ERATO : Simpath アルゴリズムの並列化, 3
将棋 インドのチャトランガが起源? ヨーロッパ : チェス アジア : 各国の将棋 中国 韓国 タイ モンゴルなど 他の将棋類との大きな違い 取った駒を再利用 終盤でも駒数が同じ : 分岐数も減らない 駒の動きが弱い 4
コンピュータ将棋選手権の記事 読売新聞 朝日新聞 週刊将棋 掲載予定? 将棋世界 情報処理学会誌 出典: 朝日新 聞 5
IBM Deep Blue チェスのスパコン カスパロフに勝利してから 15 年 1997/5/12 ( 米国時間 5/11) 誕生日じゃない 1 秒間に 1 億局面探索 6 Tech Crunch か
コンピュータ将棋への注目 2010 年 10 月情報処理学会の学会創立 50 周年記念事業にてあからが清水市代女流王将と対局 勝利 2012 年 1 月電王戦にて ボンクラーズが元名人の米長邦雄日本将棋連盟会長と対局 勝利 出典 : 情報処理学会 7 出典 : 産経ニュース
プロ棋士との対局 将棋プログラムが強くなり プロレベルに近づいている ( 諸説あり ) プロ棋士との対局イベント 電王戦 プロ棋士とプログラム 5 対 5 の対局が予定 電王戦出場プログラムは 今年の世界コンピュータ将棋選手権の上位 5 プログラム 8
世界コンピュータ将棋選手権 CSA 主催 (Computer Shogi Association) コンピュータ将棋の強さを競う大会 ハードウェア : 制限なし 会場持込の場合 騒音と電源の制限あり ソフトウェア : 公認の将棋ライブラリ ライブラリ例 : Bonanza, GPS 将棋, ライブラリは予選通過が 2 つまでと制限 一から作らないでも参加できる 強くするアイデアとその実装は必要 9
参加資格 自作のプログラム 1 つ 機種は問わない ( 原則として持ち込み ) 複数のプログラムには参加できない 思考部について 自力で十分な工夫を施したものであること その他細かい点はルール参照 CSA プロトコルでの LAN 対戦への対応など 10
対局時間 25 分切れ負け, 秒単位で消費 1 手あたり 1 秒は消費 比較的短い参考 : プロの対局 : 各 3 時間など, 1 分単位で消費 2 時間 59 分使ってもかならず1 分は考えられる タイトル戦には各 8 時間で2 日制のものも アマチュア : 1 手 1 分や 20 分 +1 手 30 秒など 11
今大会の上位 5 プログラム GPS 将棋 Puella α ( 旧名ボンクラーズ ) ツツカナ Ponanza 習甦 http://www.computershogi.org/wcsc22/team.html 12
スケジュール 12 月 WCSC 参加募集 1 月末 WCSC 参加締切 2 月オープン戦 3 月アピール文書など締切 4 月オープン戦 4 月末 - 5 月マシン送付など 5 月 2 日前日テスト 5 月 3 日 - 5 日選手権 13 WCSC = World Computer Shogi
選手権に必要なもの 参加申し込み参加費 1 万円将棋プログラムマシンアピール文書当日参加できるスケジュール 14
将棋プログラムを作ろう CSA 公認ライブラリの Bonanza を使おう 強いし GPS 将棋よりも読みやすいと評判! bonanza~/src/client/ 以下にソース 評価関数には bonanza~/winbin/fv.bin が必要 Bonanza を改造する 探索を 評価関数を 15
次は? そういえば名前がない Bonanza が元なので Honanza と名付ける カタカナなら ホナンザ Honanza はちゃんと動くのか? 変なことがないか手元で確認したい GUI を使って指し手の確認 Windows かつ Bonanza 付属の CSA 将棋 16
GUI 将棋所 : Windows USI への対応が必要 読み筋や評価値のグラフがあって見やすい Linux やMac ならwine やmono で頑張る? 自動対戦もしてくれる Universal Shogi Interface Bonanza : U2B http://www.geocities.jp/shogi_dep ot/ 将棋所 17 http://www.geocities.jp/shogid
実力を試したい floodgate 自動対局場所 floodgate に接続 30 分に一度 他のプレイヤと対戦 15 分切れ負け組み合わせはレーティングなどを元に決定 対局結果に応じてレーティングがつく 寝ている間に試せる 騒音 熱 電気代に注意 http://wdoor.c.utokyo.ac.jp/shogi/floodgate.html 18
floodgate 決勝プログラムも参加 本番マシンでの参加も 予選通過の目安にも? gps_normal (2150) が一次通過の目安とか 様々なプログラムが参加 手元では出にくいバグ, 弱点の発見に 19
情報収集 発信 情報処理学会ゲーム情報学研究会 (sig-gi) ゲームプログラミングワークショップ (GPW) 研究会 CSA 例会 CG, ACG Blog など 何となく はてなダイアリーが多い? 20
ゲームプログラミングワーク ショップ (GPW) 毎年 11 月に箱根で開催 2012 年 11 月 9 日 ( 金 ) から 11 日 ( 日 ) 研究発表がメイン 夜はナイトイベント, コンピュータ将棋や囲碁の大会 情報交換 交流 http://sig-gi.c.u-tokyo.ac.jp/gpw/2012/ 21
選手権参加申込 12 月頃に募集 参加締切は 1 月いっぱい 何が必要? 将棋プログラム マシン 参加費 1 万円 アピール文書 選手権当日の予定 22
申し込んだ その後は? 2 月 4 月 オープン戦 が開催 接続テストを兼ねている参加数は少ない. GPS 将棋はできるだけ参加 floodgate は拡張プロトコル 本番で拡張のまま参加してうまくいかない こともありえるので ここで経験するのが吉 お弁当やパーティーの予約, 追加入場者ホテルや航空券の予約 (GW!) マシンの送付 23
本番直前 一次予選前日に 会場にて接続テスト 本番環境でのテスト 他の参加者との交流も 遅刻しないように適当な睡眠を マシンを送付しているので 予選前はすることがない場合も 24
当日 参加受付本番 ログイン, 確認に返事, 対戦相手に挨拶将棋を眺めながら雑談や情報交換終局したら挨拶以下, くり返し 対局が始まれば 離れても OK むしろ 触ってはいけない プロ棋士やアマの強い人がコメントくれるかもしれない 25
参加後 予選を通過したなら 点呼に答えることマシンの送付挨拶 片付け 帰宅選手権参加記関連 blog や情報を追う本番マシンでfloodgate に参加などなど 26
スケジュール 12 月 WCSC 参加募集 1 月末 WCSC 参加締切 2 月オープン戦 3 月アピール文書など締切 4 月オープン戦 4 月末 - 5 月マシン送付など 5 月 2 日前日テスト 5 月 3 日 - 5 日選手権 27 WCSC = World Computer Shogi
参加ハードウェア 次の中で選手権に参加したことのあるハードウェアは? 1. ファミコン 2. PS3 3. FPGA 4. imac 788 台 28
参加ハードウェア 次の中で選手権に参加したことのあるハードウェアは? 全部! 1. ファミコン ( 第 1 回 ) 招待プログラム 2. PS3( 第 18 回 ) 3. FPGA( 第 18, 19 回 ) ボンクラーズ開発者 4. imac 788 台 ( 第 22 回 )GPS 将棋 29
今大会について 日時 : 5 月 3 日から 5 月 5 日 (GW!) 場所 : 電気通信大学 全 42 プログラムが参加 奇数だったため 1 プログラムが招待参加 ここ 10 年ぐらいは 40~50 プログラム 今大会から決勝シードなし 上位者を電王戦へ推薦 30
第 22 回大会の主催 共催など 主催 共催 コンピュータ将棋協会 (CSA) 電気通信大学エンターテイメントと認知科学研究ステーション 早稲田大学ゲームの科学研究所 特別協力 協賛 後援 公益社団法人日本将棋連盟 富士通株式会社 株式会社ドワンゴ 総務省 文部科学省 経済産業省 一般社団法人情報処理学会 一般社団法人情報サービス産業協会 電気通信大学 早稲田大学メディアネットワークセンター 31
予選と決勝 参加プログラム数試合数 一次予選 26 7 8 二次予選 24 ( シード 16) 9 8 選出 決勝 8 7 ( 総当り ) (5) 予選では完全スイス式と変形スイス式で組み合わせ基本的に同じ成績のもの同士を当てる 順位の決定は 勝ち数, ソルコフ, SB, MD, DB を見る強い相手と戦った方が有利 32
GPS 将棋 将棋プログラム GPS のメンバーが主体となって開発 GPS = Game Programming Seminar 東京大学大学院総合文化研究科の教員, 学生が開催 GPS 将棋, OSL は CSA 公認ライブラリ OSL = Open Shogi Library 選手権 : GPS 将棋としては10 回参加成績 : 2009 年優勝 10 年 3 位 12 年優勝 33
GPS 将棋の特色 コンピュータチェスやコンピュータ将棋の最新の研究を取り入れている 実現確率を用いた探索 評価関数の機械学習 ( 並列 )df-pn による詰将棋探索 疎結合並列探索 オープンソース, フリーウェア クラスタ : 約 800 台約 3200 コア 34
計算機群 情報基盤センター教育用計算機を利用 東京大学駒場キャンパス情報教育棟 平日と土曜日は学生が利用 土曜日は一部演習室は閉鎖されている 日曜祝日しか利用できない! 利用申請が必要 申請者は離れられない http://gps.tanaka.ecc.utokyo.ac.jp/gpsshogi 35
GPS 将棋の参加記 5/2: 接続テスト, 駒場と会場 5/3: 一次予選, 駒場にて作業 5/4: 二次予選, 駒場と会場 5/5: 決勝, 駒場と会場 終了後に現地へ集合 / 表彰式など 36
5/2 : 前日 夕方から会場へリモートのため 回線の接続テスト ネットワーク越しに対局できるかテストなど 問題なく終了 37
5/3 : 一次予選 シードなので参加しないで良い情報教育棟にて作業 東大駒場キャンパス GW に入ったので imac 全台を借りられた 1 人で全台起動すると 1 時間半かかる 管理者がいないといけない ログの読み方や作業の共有 おかしな点を発見するため 定跡のチェック 変な指手がないかのチェック 38
5/4 : 二次予選 朝は駒場 マシン起動の手伝いなど 起動の仕組みがうまくいったので不要だった 会場とskype で接続中継を眺めるなど 午後から現地へ 予選通過後の作業 ルートでの分割数を増やす定跡の一部変更時間制御 / 切れ負けの反省 39
5/5 : 決勝 駒場 中継を眺める 個人の感想 : 今年は安心して見ていられた 最終戦を除く 全局終了後 マシンを落として現地へ 閉会式と表彰式に間に合った 懇親会 40
選手権の模様の紹介 コンピュータ将棋選手権ネット中継 http://computer-shogi-live.cocolognifty.com/ 情報交換しながら和気あいあい 本人同士が将棋を指すわけではない でも胃が痛くなったりする 少しくだけたワークショップなどと雰囲気が似ているかも 発表はないが 41
個人的なポイントなど 一次予選 Selene の全勝, 新規参加組が多く予選通過 二次予選 決勝シードがないため より厳しい戦い クラスタ参加が6 組? 去年の決勝 8プログラム + ツツカナの争い 決勝 この 9 プログラムは 10 位以下のプログラムに負けていない Bonanza が予選落ち GPS 将棋がラスト前で優勝を決めたかと思いきや上位 5 位の争い 新人賞と独創賞 42
報道 一般紙 読売新聞, 朝日新聞 将棋専門誌 週刊将棋 5/16 号, 将棋世界 7 月号? その他 情報処理学会学会誌 例年は 8 月号にミニ小特集 Yahoo ニュースや /. 43
決勝 8 プログラム + 1 の紹介 GPS 将棋 Puella α ( 旧名ボンクラーズ ) ツツカナ Ponanza 習甦 激指 YSS Blunder Bonanza http://www.computershogi.org/wcsc22/team.html 44
以上 選手権の紹介と参加報告でした 45
コンピュータ将棋 入力 : 局面 (+ 時間, これまでの棋譜 ) 出力 : 指し手 入力 出力 46
ゲーム木 ゲームを木として表す x o 局面 : ノード 手 : 枝 x o x x x o x 展開すれば解ける! ( 必勝法 ) x o x o x x o x o x o x o x x o x x o x x o x o x x o x o x x 47
ゲーム木サイズ ゲーム チェッカー オセロ チェス 中国象棋 将棋 囲碁(19路) ゲーム木サイズ 10^30 10^60 10^120 10^150 10^220 10^360 解析済 人間より上 人間のトップレベル 人間のトップレベル? トップにはまだ アマチュアレベル 阿伽羅 あから = 10^224 現実的には解けない 48
強いプログラムを作るには 評価関数 ( 形勢判断 ) 探索 ( 先読み ) どちらかが完全 解析できる 現実的でない 49
1 手読み 1 手進めてから選ぶ 1 手で終わるゲームなら解析 : 局面 : 手 実際のゲーム : 1 手では終わらない 1 手先の勝ち負けを知りたい 形勢判断 勝分負??? 50
1 手読み + 形勢判断 1 手進め 形勢が良い手を選ぶ 形勢判断が完璧なら解析 実際のゲーム : 不正確 +100 0-90 深い探索 正確な形勢判断が必要 51
評価関数 局面の良し悪しを数値化 評価項目 / 特徴とその重みからなる 例 ) 5*( 駒得 ) + 10*( 危険度 ) +... 重みは機械学習で自動調整特徴は人間が考える 局面 評価関数 評価値 +300 52
評価関数ひとむかし 特徴を考える 人間が考える, 将棋の知識が必要 駒の点数, 王の危険度 重みをつける 人間が考える, 将棋の知識が必要 歩が 100 点として 香車は 200?400? パラメータ数に限界 せいぜい数百数千?
評価関数, 現在 特徴をたくさん考える 人間が考える 駒の点数, 王の危険度 重みをつける 機械学習による自動処理 棋譜の指し手を選ぶように重みを調整 パラメータ数は数百万, 数千万, 億?
GPS 将棋の評価関数 序盤, 中盤, 中盤 2, 終盤の 4 種類 8,952,491 項目 ( 重み 0 も含める ) 2009 年は約 300 万 : およそ 3 倍に 局面の進行度に基づき内分を取る 人間の知識で項目を選択 重みは棋譜から調整 調整後強くなったか対戦で確認, 採否 55
Min-Max 探索 Max Player は最大値 Min Player は最小値を選ぶ Best Move 3 Root Max-Player 3 2 Min-Player 3 5 2 4 3 2 5 1 1 2 1 4 5 3 6 2 4 5 1 1 9 2 3 4 1 4 数字は 評価値 点数が高いほど Max-Player が有利 56
探索 評価関数 + αβ 探索 互いに最善を尽くす前提 深さ打ち切り探索 葉ノードで 評価関数による評価値を得る 一般に, 深く探索するほど強い 速度を上げる工夫 局面 探索 指し手, 評価値 (7776FU, +300) 57
αβ 探索 Min-Max を効率的に行い 同じ結果を得る 不要な探索を行わない : 枝刈 探索窓, alpha-beta window の導入 興味のある評価値の範囲 (alpha, beta) として表記 返り値 V で更新 Max : If (V > alpha) alpha = V Min : if (V < beta) beta = V 58
枝刈 枝刈条件 Max : V >= beta Min : V <= alpha 例 : ルートの Max ノードは 5 以上 Max Min 矢印のノードに左の子ノードから 3 が返った 値は 3 以下になる ( Min ノード ) ルートには 3 以下しか返らない 選ばれない それ以上探索するのは無駄 枝刈 5 3 (5, ) (5, ) Cut! 59
αβ 探索 (-,5) ) 3 2 (-, ) 3) 3 Best Move 3 5 5 (-, (3, ) ) (-, (3, ) (-, ) 3) (-, (3, 6) ) 3) Cut 3 Root (3, ) (3, ) (3, ) 1 2 2 2 Cut (3, ) Cut Max-Player Min-Player 5 3 6 2 9 5 1 2 数字は 評価値 点数が高いほど Max-Player が有利 60
αβ 探索の結果 3 Root 3 3 5 2 2 3 2 5 1 2 5 3 6 2 9 5 1 2 枝刈されたノード 枝刈されたノード 61
αβ探索と効率 探索の順序 良い手を先に探索すると枝刈の効率が良い ハッシュ表 千日手や合流 76歩 34歩 66歩 66歩 34歩 76歩 62
探索順序の重要性 Max で小さい値 Min で大きな値を先に探索 Root 3 Best Move 2 3 Max-Player Min-Player 4 2 4 3 1 4 1 2 1 4 2 3 4 1 4 1 3 2 4 1 5 4 6 2 5 3 αβ 探索で枝刈が起こらない! 63
効率的な探索 Null-window search (NWS) V より大きいかを調べるなら (v, v+1) で探索 探索窓の幅が Null, 枝刈がすぐ起こるので高速 Principal Variation Search (PVS) 一番左端は (-, ) で探索 : 評価値 v 残りに PV の結果を上回る手がないか調べる v = Null-window search (v, v+1) 上回る (v > v) なら (v, ) で再探索 (v ) 64
PVS 左端の探索結果は 5. 5 より大きくなるか調べたい (5,6) で NWS 5 Root 5 (5,6 ) (5,6 ) 3 (5,6 ) 3 2 (5,6 ) 3 (5,6 ) (5,6 ) (5,6 ) 1 (5,6 ) 5 3 6 2 9 5 1 4 1 2 2 2 2 3 4 1 4 65
探索の効率化に重要な情報 探索順序 枝刈が起こらないことも 探索窓の広さ 狭いほど枝刈は起こりやすい ハッシュ表 探索結果の保持 : 同一局面の探索を行わない 手の並び替え : 浅い探索結果を元に 66
探索の工夫 枝刈 探索延長探索順序探索窓ハードウェア 専用ハードウェア ( 例 : Deep Blue) CPUのオーバークロック マルチコア クラスタ / 疎結合 67
並列化の難しさ 処理は並列に行える? 処理に順序依存性があると難しい オーバヘッド 探索 : ( 逐次なら ) 枝刈されるノードの探索 同期 : 他のプロセッサの結果を待つ 通信 : 仕事の分割, 仕事を通信, 通信遅延 68
αβ 探索の結果 色のついた分を探索するのが 探索オーバヘッド 3 Root 3 3 5 2 2 3 2 5 1 2 5 3 6 2 9 5 1 2 枝刈されたノード 枝刈されたノード 69
メモリ共有環境 例 : 最近のパソコン Nコアプロセッサ間の通信は十分速い 通信オーバヘッドはあまりない PV Split PVS の並列化 左端を1 人で展開 残りのノードを並列にnull window search ハッシュ表を共有 ロックレスハッシュ 70
PVSplit 2 並列 Processor1,2 (P1,P2) Max Min P1 P1 P2 P 1 P 2 P 1 P 2 P1 P2 1 2 2 3 3 4 4 5 5 71
GPS 将棋の疎結合並列探索 2010 年の第 20 回大会からクラスタ参加 順位 : 3 位 -> 6 位 -> 1 位! コア数 : 666, 800, 3200 情報教育棟の imac, Amazon EC2 (2011) ネットワークで緩く接続されたマシン群 通信速度はそんなに速くない 情報のやり取りがあまり出来ない 協調的に動かすのが難しい 72
単純なアイデア 木を展開していき 台数分ノードができたら全ノードに 1 台ずつ割り振る 無駄な探索がかなり多い 台数効果が出ない 将棋の平均合法手数は80 1 手深く探索するには80 台 2 手深く探索するには6,400 台必要! 73
メモリ非共有環境 情報のやり取りが通信となり 遅い 探索結果やハッシュ表 ハッシュ表については local, global, ハッシュ値に応じて割り振る, hybrid などが考えられる 探索結果を使うには 他の人の仕事が終わるのを待つ必要がある 74
従来手法 YBWC, APHID, TDSAB YBWC は PVSplit に近い手法 合議 将棋では実際に成功した例があまりない チェスでもRybka がクラスタ探索をしているが 詳細は不明 他ではクラスタ探索を聞かない http://cluster.rybkachess.com/ 75
合議 お手軽な ( 疎結合 ) 並列探索 複数台で1 台のマシンよりも強くなる 4, 8 台で55% 前後逓減は速い 準備 : 異なるプログラムの用意 : 台数分 評価関数に乱数を入れるなど 手順 : それぞれ同じ局面を探索 多数決で指手を選択 76
8台合議例 左から手a,b,c と並ぶ 指手 票 a P1, P2, P4, P8 b P3, P5 c P6, P7 P3 P4 手a が選ばれる Root P1 P2 P5 P6 P7 P8 77
GPS 将棋 探索窓を共有しない 同期オーバヘッドと効率のトレードオフ ハッシュ表は各自で持つ 割当て時に前回担当分に割当てられる ここでは 通信オーバヘッドはない 並び替えは探索など 探索オーバヘッドはあるが 並び替えがうまくいけば 少なく抑えられる 78
GPS 将棋のアプローチ ( 概要 ) ルートで手生成上位 N 手にマシンを割当 順位に応じて台数を変化残りの手は1 台で通常探索 それぞれ, 手を進めた局面で手生成 各手の台数が1 台なら1 台で通常探索上位 M 手にマシンを割当, 残りは1 台で探索以下 繰り返し 残りの手 が最善となったら探索時間延長 79
8 並列 N=M=1 Root Max Min A P6 P 7 P8 P1 P2 P3 P 4 P 5 P8 と比較し, A の子ノードは 5 手深く探索 80
11 並列 N=2, M=1 Root Max Min A P 5 P 1 0 P 1 1 P1 P2 P3 P 4 P6 P7 P8 P 9 P11 と比較し, A の子ノードは 3 手深く探索 81
82
83
台数分割 良い手には多く割当 良くない手にはあまり割当てたくない 良い手 がわかれば探索する必要はない 順位付けが必要 1 秒での探索や実現確率の上位の手を利用 (2010,2011) 84
上位を選ぶ (2012) 前回その局面を探索した 前回の探索結果の上位 N 手 (new) 探索していないが 5 秒以上ある 1 秒で探索した結果の上位 N 手実現確率の上位 N 手 85
探索時間延長 残りの手 が一番良い 探索時間延長 他の手よりも浅い 1 台で複数の手を担当 信用出来ない 残りの手 以外での 1 位はそのまま探索 他は 残りの手 の最善の探索に再割当 残りの手 を読んでいた 1 台は 新しい残りの手を探索 ( これは問題 ) 86
問題点 残りの手 を読んでいた1 台は 新しい残りの手を探索 新しい 残りの手 は1 台で探索 やはり怪しい浅い探索の結果が選ばれる可能性がある本番でも起きていた様子 どうすべきだったか 残りの手 で良い手 残りの手 以外での1 位の手 だけを探索すれば良い 87
評価値 : d > a > b > c 探索時間延長 ( 延長前 ) Root 手 a 手 b 手 d = best 手 c P1 P2 P3 P 4 P 5 P6 P7 P8 P 9 P 1 0 P 11 手 a, 手 b に比べて 3 手浅い手 d が最善単純な比較では判断できない 探索時間延長 88
探索時間延長 ( 再割当後 ) 上位 N(=2) 手の最善 (a) : そのまま探索を続行 手 a Root 手 d 残りの手 (c,d) の担当は新しい残りの手 (b,c) を探索手 c 手 b P5 P 1 0 P11 P1 P2 P3 P 4 P6 P7 P8 P 9 上位 N(=2) 手の残り (b) : プロセッサ (6-10) を集め 最善手 d を探索 89
GPS 将棋のアプローチ ( 再掲 ) ルートで手生成上位 N 手にマシンを割当 順位に応じて台数を変化残りの手は1 台で通常探索 それぞれ, 手を進めた局面で手生成 各手の台数が1 台なら1 台で通常探索上位 M 手にマシンを割当, 残りは1 台で探索以下 繰り返し 残りの手 が最善となったら探索時間延長 90
選手権での構成 マスタ 1 台 情報の統合など スレーブ 792 台 探索 詰将棋専用スレーブ 4 台 詰将棋専用 91
今年のクラスタ差分 Perl, ruby から C++ へ書き換え 速度向上 タスク分割方法 性能向上 探索時間延長 探索結果の信頼性を向上 92
マシンスペック imac Core 2 Duo imac Core i 5 Amazon EC2 その他コア数 2010 307 0 0 7 666 2011 208 0 40 15 832 2012 0 788 0 9 3224 CPU #core #cpu memory imac Core 2 Duo imac Core i 5 Amazon EC2 2.0GHz Intel Core 2 Duo 2.5GHz Intel Core i 5 2.93GHz? Intel Xeon 93 2 1 2GB 4 1 4GB 4 2 23GB
対戦実験 今年も行なっていない 参考記録: 金子, 田中 最善手の予測に基づくゲーム木 探索の分散並列実行 GPW2010 逐次よりも強い 8コアでメモリ共有探索4コアと同等 勝,負,引分 メモリ共有型 1コア クラスタ8コア 71 28-94 2コア 4コア 57 29-43 50 -
計算機群 ( 再掲 ) 情報基盤センター教育用計算機を利用 東京大学駒場キャンパス情報教育棟 平日と土曜日は学生が利用 土曜日は一部演習室は閉鎖されている 日曜祝日しか利用できない! 利用申請が必要 申請者は離れられない http://gps.tanaka.ecc.utokyo.ac.jp/gpsshogi 95
他の部分の去年との違い 評価関数 古いバージョンに勝ち越すものを採用 探索 チェスプログラムStockfish を将棋へ移植 gpsfish 今回探索のスレーブとして利用 チェスと将棋の違いに起因する問題が多々 稲庭対策がない / クラスタはあり 詰将棋がない / クラスタはあり 96 (元)駒得少年の冒険 http://www.sgtpepper.net/kaneko/di
関連 URL GPS 将棋 http://gps.tanaka.ecc.utokyo.ac.jp/gpsshogi http://twitter.com/gpsshogi Floodgate ( コンピュータ将棋対局道場 ) http://wdoor.c.u-tokyo.ac.jp/shogi 第 22 回コンピュータ将棋選手権 http://www.computer-shogi.org/wcsc22/ 97
まとめ WCSC において, GPS 将棋が優勝 約 800 台での疎結合並列探索 注目の集まる電王戦への出場 コンピュータ将棋のアルゴリズムを紹介 GPS 将棋の疎結合並列探索を簡単に紹介 選手権参加をお待ちしています 98