Microsoft PowerPoint - vc2013.s.takeuchi.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - vc2013.s.takeuchi.pptx"

せとかたなせ
9 years ago
Views:

1 コンピュータ将棋の技術と GPS 将棋について JST ERATO 湊離散構造処理系プロジェクト竹内聖悟

2 概要 GPS 将棋の紹介コンピュータ将棋で使われる技術形勢判断と先読み GPS 将棋の技術今後の将棋 AI と研究コンピュータ将棋と可視化

3 近年のコンピュータ将棋 2007 年 : 渡辺明竜王 -Bonanza 渡辺竜王の勝利 2010 年 : あから清水市代女流王将あからの勝利 2012 年 : ボンクラーズ - 米長邦雄永世棋聖ボンクラーズの勝利 2013 年 : プロ棋士 5 人対 5 プログラム三勝一敗一分でコンピュータ側の勝越現役プロ棋士に初勝利

4 GPS 将棋とは

5 GPS 将棋の特色コンピュータチェスやコンピュータ将棋の最新の研究を取り入れている実現確率を用いた探索評価関数の機械学習 ( 並列 )df-pn による詰将棋探索疎結合並列探索オープンソース将棋ライブラリの公開

6 コンピュータ将棋選手権の成績位1 決勝 5 10 二次予選一次予選年順

7 順位 GPS将棋の成績と出来事初優勝 (2009) 決勝二次予選 15 機械学習 (2008) あから参加 (2010) 30 一次予選開発開始(2002) 電王戦: 三浦弘行八段に勝利 (2013) 疎結合並列探索(2009) 初参加 (2003) 年 2014

8 Twitter タイトル戦の形勢判断無料中継のタイトル戦最近はお休み中各局面に対し評価値,読み筋,探索時間詰みや狙いなど指手, 評価値, 最善応手手順, 秒電王戦当日数 [(100) ９九と] ９五香７七歩同角同金８六玉６六角７六銀８五香同銀同桂３二角成同玉７二飛４二金６四歩７五角同飛成同銀同玉８四銀７四玉７三飛

9 ゲーム研究情報科学/人工知能認知科学完全解析強いプログラム強いプレーヤーはどう考えるか教育どう教えたら強くなりやすいか

10 強いプログラムを作るには

11 1手読み :局面 :手 1手進めてから選ぶ 1手で終わるゲームなら解析実際のゲーム: 勝分ゲーム木 1手では終わらない 1手先の勝ち負けを知りたい形勢判断負???

12 1手読み + 形勢判断

13 ゲーム木サイズゲームチェッカーオセロチェス将棋囲碁(19路) サイズコンピュータの強さ解析済み引分チャンピオンを超えたチャンピオンを超えたプロ棋士レベルアマチュアレベル阿伽羅(あから) = 現実的には解けない

14 強くするために正確な形勢判断評価関数の重みを機械学習により調整効率的な探索枝刈, 延長, 短縮実現確率探索詰将棋探索並列探索疎結合並列探索

15 評価関数局面評価関数評価値 +300

16 評価関数, ひとむかし特徴を考える重みをつける人間が考える, 将棋の知識が必要駒の点数, 王の危険度人間が考える, 将棋の知識が必要歩が100点として香車は200?400? パラメータ数に限界せいぜい数百数千?

17 評価関数, 現在特徴をたくさん考える重みをつける人間が考える, 将棋の知識が必要駒の点数, 王の危険度, 3駒間の関係... 機械学習による自動処理棋譜の指し手を選ぶように重みを調整パラメータ数は数百万, 数千万, 億?

18 GPS将棋の評価関数

19 評価関数の学習評価関数のパラメータ調整 Bonanza が成功(2006) 強化学習や進化的アルゴリズムあまり成功していなかった GPW 2006 にて機械学習の発表 2008年ソースコードの公開現在将棋プログラムの大半が利用オンライン学習化など研究も進んでいる

20 学習のイメージ棋譜の指手を真似られるように調整プログラムの指手との一致率を高くする棋譜以外の手を選ばない兄弟局面の比較棋譜の指手探索を行う探索末端局面同士の比較歩兵 7 11 簡単な例金将 3 1 f(x) = 3 1 歩+4 3 金 f(x)

21 評価関数の項目 f (x) = å wi xi どうやって項目を選ぶか xi: 駒の枚数, ３駒の関係人間の知識が必要自動生成の研究: あまり成功していない

22 Evaluation Curve 勝率手法: 評価値に対し勝率をプロット有効な特徴の発見を目的とする X軸: 評価値 Y軸: 勝率評価値強いプログラムのカーブ: 単調性 (評価値と勝率の大小関係が単調増加) 一貫性 (異なる棋譜でも同じカーブになる) 理想役立たず逆転すれば良い

23 E.C. の分離棋譜セット A, B, C 一本一貫 (良いプログラム) 例) 駒の価値だけの評価関数全局面自玉が安全 (勝ちやすい) 自玉が危険 (負けやすい) 分離非一貫 (良くないプログラム)

24 分離したE.C. の問題点ゲーム木勝率 B 勝率評価値 A B の勝率が高いしかし A が選ばれる良くない! 評価値

25 実例 2006年前後のGPS 将棋の評価関数王の危険度: 王周辺にある敵の利きの数機械学習以前のもの多いほど負けやすい利き: 駒が動ける範囲評価関数が上記を正しく評価できているなら勝率に影響はない正しく評価: Evaluation Curve が1本化される

26 改良前分離問題あり有効な特徴

27 改良後一本問題ない対戦実験からも棋力の改善を確認

28 E.C.

29 評価関数線形の評価関数が主流重さは機械学習による自動調整ニューラルネットワークなども一部あり基本的に速度が優先される数百万の重みを調整特徴は人間が知識を使って見つけるサポートする手法が必要

30 探索評価関数 + αβ探索互いに最善を尽くす前提深さ打ち切り探索葉ノードで評価関数による評価値を得る一般に, 深く探索するほど強い速度を上げる工夫局面探索指し手, 評価値 +7776FU, +300

31 αβ探索 Min-Max を効率的に行い同じ結果を得る不要な探索を行わない : 枝刈探索窓, alpha-beta window の導入興味のある評価値の範囲 (alpha, beta) として表記返り値V で更新 Max : If (V > alpha) alpha = V Min : if (V < beta) beta = V

32 枝刈枝刈条件例: Max : V >= beta Min : V <= alpha (5, ) 5 3 (5, ) Cut Max! Min ルートのMax ノードは5以上矢印のノードに左の子ノードから3が返った値は3以下になる ( Min ノード) ルートには3以下しか返らない選ばれないそれ以上探索するのは無駄枝刈

33 αβ探索の挙動 (-, ) (3, ) Best Move 3 Root Max-Player ) (-, 3) 3 (-, (3, ) ) (-, 3) (-, 3) ) (3, 6) (-,5) (-, ) 5 (3, ) Cut 2 Cut Min-Player 2 (3, ) (3, (3, ) ) 1 2 Cut 1 2 数字は評価値点数が高いほどMax-Player が有利

34 αβ探索の結果 3 Root 枝刈されたノード 2 2 枝刈されたノード

35 探索の効率化に重要な情報探索順序探索窓の広さ最善を先に探索できると効率的最悪の場合枝刈が起こらないことも狭いほど枝刈は起こりやすいハッシュ表探索結果の保持 : 同一局面の探索を行わない手の並び替え: 浅い探索結果を元に

36 探索の工夫枝刈探索延長探索順序探索窓ハードウェア専用ハードウェア (例: Deep Blue) CPUのオーバークロックマルチコアクラスタ/疎結合

37 並列化の難しさ並列処理が可能か? 処理に順序依存性があると難しいオーバヘッド探索 : 逐次なら枝刈されるノードの探索同期 : 他のプロセッサの結果を待つ通信 : 仕事の分割, 仕事を通信, 通信遅延

38 メモリ共有環境プロセッサ間の通信は十分速い通信オーバヘッドはあまりない PV Split 左端を1人で展開残りのノードを並列にnull window search ハッシュ表を共有ロックレスハッシュ

39 PVSplit Max 2並列 Processor1,2 (P1,P2) Min P2 P1 P1 P1 P P 1 3 P 2 P1 P

40 GPS将棋の疎結合並列探索 40

41 計算機群

42 クラスタ構成選手権他合計台/コア数備考 / / / 3224 Intel Core 2 Duo 2.0GHz Amazon EC2 40台 imac 2012 imac 入れ替え Intel Core i5 2.5GHz / 3318

43 単純なアイデア

44 従来手法

45 GPS将棋の疎結合並列探索探索窓を共有しないハッシュ表は各自で持つ同期オーバヘッドと効率のトレードオフ割当て時に前回担当分に割当てられるここでは通信オーバヘッドはない並び替えは探索など探索オーバヘッドはあるが並び替えがうまくいけば少なく抑えられる

46 GPS将棋のアプローチ概要ルートで手生成上位N 手にマシンを割当それぞれ, 手を進めた局面で手生成順位に応じて台数を変化残りの手は1台で通常探索前回担当した局面は同じマシンが担当各手の台数が1台なら1台で通常探索上位M手にマシンを割当, 残りは1台で探索以下繰り返し残りの手が最善となったら探索時間延長

47 N=M=1 Max Root 8並列 Min P8 P7 P6 A P5 P1 P2 P3 P4 P8 と比較し, Aの子ノードは5手深く探索

48 N=2, M=1 11並列 Max Root Min A P1 P2 P3 P1 0 P5 P 4 P6 P7 P8 P 9 P11 と比較し, Aの子ノードは3手深く探索 P 11

49 クラスタの思考の可視化

50 nps = nodes per second 2013年5月の例約3億nps を達成 (Deep Blue: 1億nps) 6手深く探索

51 探索のまとめアルファベータ探索と評価関数効率的な探索の工夫枝刈や探索延長など並列探索 SMP 環境での並列化疎結合並列探索

52 順位 GPS将棋の成績と出来事初優勝 (2009) 決勝二次予選 15 機械学習 (2008) あから参加 (2010) 30 一次予選開発開始(2002) 電王戦: 三浦弘行八段に勝利 (2013) 疎結合並列探索(2009) 初参加 (2003) 年 2014

53 今後の展望など人間のトップに勝つことは１つの目標さらに強いプレイヤの作成段々近付いてきたチェスは現在も強くなり続けている強いプレイヤがいないと出来ない研究プレイヤの強さの解析時代の違うプレイヤの比較

54 これからの研究人間らしい指手人間のサポート昔から研究されている人間らしいことの評価の難しさ感想戦支援など思考の可視化言語化の研究など

55 コンピュータ将棋と可視化

世界コンピュータ将棋選手権参加報告、及び、GPS 将棋の技術

世界コンピュータ将棋選手権参加報告、及び、GPS 将棋の技術世界コンピュータ将棋選手権参加報告及び, GPS 将棋のアルゴリズム JST ERATO 湊プロジェクト研究員竹内聖悟 1 概観世界コンピュータ将棋選手権の紹介今年は GPS 将棋が優勝上位 5 プログラムがプロ棋士と対局予定コンピュータ将棋のアルゴリズム GPS 将棋とそのアルゴリズムを紹介約 800 台のマシンで疎結合並列探索 2 あらためて自己紹介竹内聖悟 JST ERATO