<4D F736F F F696E74202D2091E F B835E B C >

Size: px

Start display at page:

Download "<4D F736F F F696E74202D2091E F B835E B C >"

あつのたけはな
5 years ago
Views:

1 機械学習とコンピュータゲームプレイヤへの応用工学部電子情報工学科近山隆 1

2 講義の概要機械学習前回コンピュータ将棋プレイヤと機械学習今回コンピュータゲームプレイヤ研究の状況コンピュータゲームプレイヤ激指ゲーム木の探索手法機械学習のゲーム木探索への応用モンテカルロ法と機械学習 2

3 コンピュータゲームプレイヤとはコンピュータの誕生当初から研究されてきた人間の知性の象徴もともとゲームは現実世界の縮図組合せ探索問題の一種多数の選択肢の中から最適なものを選択初期局面から必勝手を選べれば最高だが無理与えられた時間内にできるだけ良い手を選択 3

4 種々のゲームのプレイヤオセロ: 1990年代に人間を凌ぐチェス: 人間のトップを破る IBM Deep Blue vs 世界チャンピオンカスパロフ 1997 将棋: トッププロに迫る 6x6のオセロは完全に解かれている必勝手順が既知平均的プロ棋士程度の力はある囲碁: 初級者レベル近年急激に実力向上新しいアルゴリズムが大きな役割 4

5 コンピュータ将棋プレイヤ激指現時点でトップのプレイヤのひとつ近山研究室の大学院生が開発世界コンピュータ将棋選手権で活躍し商品化も開発者の修了就職後も開発チームは継続研究室の後輩による関連研究 5

6 激指の歴史誕生成長 1999.秋大学院生4人将棋でもやってみようか速い実装をすれば勝てるんじゃないの? 世界コンピュータ将棋選手権 WCSC 挑戦二次予選 9 位決勝進出ならず 2000秋実現確率打切りを提案実装鶴岡 WCSC二度目の出場決勝進出 4位他ソフトと違う特徴的棋風に注目集める商品版毎日コミュニケーションズより発売 6

7 激指の歴史円熟期 WCSC初優勝 WCSC 3位 WCSC 2位 WCSC 全勝で全勝優勝勝又プロ五段との記念角落ち戦にも勝利アマ竜王戦全国大会出場ベスト将棋世界企画トッププロとの角落ち戦渡辺竜王に敗れるも木村一基7段に勝利 7

8 激指の歴史停滞復活 WCSC 5位 WCSC 4位 WCSC 3度目の優勝エクシビションで清水上アマ名人に勝利 WCSC 6位 WCSC 4度目の優勝この間にどの強豪ソフトも確実に強くなってきている 8

9 人間 vs. コンピュータ将棋 2011/07/11 9

10 決定的完全情報零和ゲーム決定的: 偶然性なし backgammon 完全情報: 全情報は開示 contract bridge 互いに最善を尽くした場合の勝負は原理的には決まっている (たとえばゲームで賭けられる?) ゼロサム: 自分の勝ちは相手の負け 10

11 AND-OR 木探索局面指し手 OR 自分の手番: ひとつ勝つ手があればいい相手の手番: ひとつでも負ける手があると困る AND 11

12 最後までは読みきれない 6手先: 1秒ある局面で可能な手は60種ぐらい 7手先: 1分 1手深く読むには約60倍の時間 8手先: 1時間 9手先: 2.5日ゲームの終了まで探索するのは 10手先: 半年 11手先: 30年事実上不可能 12手先: 1800年最後まで読むのはあきらめて読める範囲でなるべく有利になる手を探索勝ち負けの二値有利不利の度合いの多値局面の評価が重要に AND/OR 探索 Mini-Max 探索 12

13 Mini-Max探索先手番後手番先手番選択手 Min 節もっとも後手有利の手を選択 1 もっとも先手有利の手を選択 Max 節 13

14 探索の省略 α枝刈り先手番後手番先手番先手は左の枝をとれるのでこの局面の評価は 2以上 2 後手が左の枝をとれるのでこの局面の評価は-3以下ここがどうだろうとこの手は選ばない 14

15 β枝刈り: α枝刈りと先後逆先手番後手番先手番後手は左の枝をとれるのでこの局面の評価は 2以下先手が左の枝をとればこの局面は 7以上 7 ここがどうだろうとこの手は選ばない 15

16 探索窓 α値とβ値の範囲各局面で考慮すべき評価値の下界上界先手番後手番先手番 [2, ] [2,-3] ここは最低でも評価値 2 最高は不明ここは最高でも評価値 -3 親から2 以下は不要とわかるこれ以上の探索不要

17 αβ枝刈りの効率向上有望な手を先に探索するのが大事早く大きく枝刈りできる理想的探索順なら約倍の深さ読める反復深化 iterative deepening 繰返し段々深く読んでいく浅い読みの結果で深い読みの際の順序を決める浅い読みは何度も行なうので冗長だが深さ優先の探索がメモリコスト上で有利探索コストは深さの指数関数浅い探索は安価 17

18 探索窓を縮小した探索探索窓をあらかじめ縮小して探索探索窓の決め方結果が窓の外だとどちら側かしかわからない結果が窓の内なら探索が効率的悪い着手を早くあきらめられる以前の着手決定の際の結果から推定反復深化の際浅い読みの結果から推定幅0の探索を繰り返す手法も 18

19 水平線効果 Horizon Effect 限られた深さの mini-max 探索の本質的問題読める深さは限られている読める範囲内で最適なものを探す読める範囲のちょっと先の不利に気づかないどうやっても先が不利になりそうな局面で小さな不利の手伸ばし歩の打捨てなどで大きな不利を視界の外に追いやる振舞い 19

20 どこまで深く読むか単純には最大 n 手先まで最後の一手がはんぱだったら? 駒の交換で n 取ったところまで大きく有利? 取られたところまで大きく不利? ほんのちょっと先まで読むと全然違うという局面は少し先まで読みたい 20

21 選択深化 selective deepening 枝によって先読みの深さを変える少し読めば精度が大きく高まるならより深く i.e. 限界効用の高いところに資源投入従来からゲームプレイヤで広く採用連続王手が終わるまで駒の取り合いが一段落するまでアドホックに人手で設定するのでは将棋の知識が必要考え落ちが生じやすい 21

22 実現確率打切り選択深化の一手法方針: 実現しそうな局面は深く読む現局面から始めて各局面の実現確率を推定実現確率は棋譜から得た統計データから推定打切り閾値以上の実現確率の部分木のみ探索 22

23 局面の実現確率の算定手法指し手の実現確率を求める指し手を表す特徴を適宜設定約600局のプロ棋士の棋譜から各特徴を持つ手について指せるときに実際に指した率を計算現在の局面からある局面に至る指し手の確率の積がその局面の実現確率 e.g., 大駒の交換はたいがい取り返す取った局面取り返した局面はほぼ同確率 23

24 実現確率打切り局面の実現確率 p = p1 p2 p3 p1 p2 実現確率 q1 以上実現確率 q2 以上 p3 実装は対数で管理乗算加算 24

25 実現確率打切りはなぜ有効強いプレイヤが実際に指すことが多い手は良い手である可能性が高い良い手は有利な局面をもたらしやすい有利な局面に至る手は詳しく調べる価値あり注強いプレイヤが指しそうな手を選ぶのではない強いプレイヤが指しそうな手は詳しく調べるすなわち資源投入量の制御にあたる 25

26 コンピュータ将棋と機械学習コンピュータ将棋の黎明期: 職人芸激指の実現確率: データからの学習の導入局面のどこに注目どの局面を探索計算機が遅いときにはこれしかなかった職人芸的プログラミングからの解放近年では機械学習の適用が当然にコンピュータが十分速くなった大量のデータが扱えるようになった 26

27 実現確率算定の改良指し手の確率指し手を生成する尤度を学習特徴として盤面パターンなどを追加手の移動先移動元の3x3のパターンなど約4000局のプロ棋士の棋譜(約50万局面)で指された手を正例指されなかった手を負例とし Maximum Entropy 法で学習ひと目でこの手は65%指しそうとわかる 27

28 局面評価関数の機械学習かつてはなかなかうまくいかなかったコンピュータ将棋プレイヤ Bonanzaの登場評価要素: 玉と他の2個の駒の位置関係すべて比較学習を導入して初出場で優勝 (2006) 大きなインパクトを与えた 100万におよぶ次元の重みを調整する学習今日では多くのコンピュータプレイヤが同様の方法を採用 28

29 比較学習局面評価パラメタの学習法 Deep Thought: IBMによるチェス専用機世界チャンピオン Kasparov を破った Deep Blue (1997) の前身評価関数の重みを自動学習 (1988) 強いプレイヤが指したと同じ手を指すように調整指した手/指さなかった手の評価値の相対値が問題指した直後の局面の評価を高くするのではダメ先まで読んだ結果その手を指すように調整 29

30 詰将棋と指将棋の関係詰将棋は読み切る指将棋とは異なる発展指将棋でも詰の判定は重要証明数反証数に基づく選択深化による探索プロ棋士を大きく上回る実力それでも殊に不詰の判定には時間がかかる終盤はもちろん序盤でも頓死の可能性あり激指では全体の30%の時間が詰み探索詰むはずもない局面では時間をかけたくない 30

31 証明数と反証数 proof number/disproof number AND-OR 木全体の真偽を決める問題たとえば詰将棋木をあまり展開せずに真偽を決めたい証明数あと p ノード展開するだけで真とわかるかも反証数あと d ノード展開するだけで偽とわかるかも証明数反証数の小さなノードを優先して展開最小限のコストで結論を得られそうな戦略 31

32 直感の重要性強い将棋指しは先読みで手を探さない? よい手は直感的に思いつく時間をかけて読むのは直感を確かめるだけ実はよくない手だったとわかる場合も直感はどの手をよく読むべきかの資源配分制御に使っている! 詰み判定への資源配分を直感で制御 32

33 詰不詰の予測三輪2004 将棋の局面をいくつかの特徴量で表現多くの局面について詰将棋プログラムで詰不詰を決定詰不詰と特徴量との関係を SVM で学習特徴量２特徴量１ 33

34 ソフトマージンの SVM 線形分離不能の場合線形では誤分類誤分類の程度を数値化誤分類コスト最小となる分離超平面を選択 Support Vector 34

35 局面の特徴129種を人手で選択玉将について: 絶対位置玉間の距離玉周辺の状況: 周辺の各位置は盤端/空/味方/敵玉の可能な動きの数守り駒攻め駒合い駒状態の駒の数手駒の種類と数可能な王手の種類 35

36 学習に用いたデータ終局に近い四万局面を生成プロ棋士の四千局の棋譜を用意終局近くからランダムに進めて各十局面を生成詰将棋プログラムで判定最長３０秒で判定全四万局面中10,159局面が詰み棋譜 2010/07/12 進行局面集判定詰み不詰 36

37 Cross Validation 限られた数のデータを学習と評価に使いまわし３-fold cross validation では: データ全体学習学習評価評価評価学習学習 37

38 実験の結果(4-fold cross valid.) 実際は詰と判定詰不詰 6,414 1,865 計 8,279 不詰と判定 3,745 27,976 31,721 計 10,159 29,841 40,000 この精度の判定が数マイクロ秒で可能詰不詰正解率再現率 F値詰み判定としては信用できない詰みの見逃しは少なくない 38

39 詰判定に時間をかける価値いかにも詰みそう特徴量２詰み判定超平面との距離に注目大きく離れていればなんともいえない判定は信頼できそう距離にしたがって詰み判定にかけるいかにも詰まなさそう時間を調節特徴量１ 39

40 詰判定への資源投入量制御局面と分離超平面との距離で詰判定ルーチンへの時間配分を制御 Sigmoid関数詰み判定にかける時間詰まなそうなら詰みを読むのに時間をかけない 0 詰みそうなら時間をかけて詰みを読む分離超平面との距離 40

41 資源投入量制御の効果この制御を行わない版と千局対戦させたら平均計算時間を 65.6% に削減して勝率 53.4% 3/4 の計算時間だと勝率55.3% 3.26σ 強さを保って 2/3 の計算時間少ない計算時間で有意に強くなった 41

42 特徴量の自動生成三輪2005 局面を表す特徴量は人間が選ぶのが普通問題領域の知識が必要見落としが生じる可能性多数の事例から自動生成できないか単純で自明な特徴の組合せを特徴量に有利不利との関係が強い組合せを自動選択 2010/07/12 42

43 特徴パターンの生成手順選択有用なパターン 2010/07/12 頻出飽和パターンこれだけは人手で特徴パターン単純な特徴要素組合せ頻出するもの抽出棋譜ラベル付け 43

44 パターン選択と評価関数構築頻出するパターンの中から独立して意味を持つ飽和パターンのみ選択有用なパターンを選択 ① ② 条件付相互情報量の大きいものを選択各訓練局面の持つ頻出飽和パターンのうちラベル付けとの相互情報量上位のもののみ考慮すべて考えるとメモリに載りきらない Naive Bayesian classifier で評価関数構築 2010/07/12 44

45 詰将棋問題での実験基本特徴要素駒の位置効きの 41,224 種訓練用 80,000局面オンライン将棋対局サイト組合せは論理積のみ考慮 2%以上の局面で出現するもの 38,173,197 種事前選択を上位100, 200, 500, 1000 種で試行評価関数に用いる評価要素数 ,000 9,768 局面を用いて評価 2010/07/12 45

46 処理に要した時間 2種類のシステムを利用 Xeon 3.06 GHz 2, メモリ 2GB Opteron GHz 2, メモリ 8GB 頻出飽和パターン抽出: Xeon で 38分有用なパターンの抽出: Opteron で5日間実用的な時間でできる範囲内に設定 2010/07/12 46

47 詰将棋問題への適用結果 2010/07/12 47

48 詰将棋のための評価関数自動構築実験のまとめ上位200, 評価要素数 2,000 で最良の結果正解率約74 計算量膨大: さまざまな工夫をして計算量を削減してなんとか実現可能に人手で評価要素を選択 SVM で評価関数を作った場合の 84% にはまだ及ばないゲーム以外の問題への適用も十分考えられる 2010/07/12 48

49 局面評価の見直し卒論テーマ局面の評価値その局面から勝てる確率強い棋士は不利な局面では紛れを求める実力差があるときの駒落ち将棋は最初から不利上手はわかりにくい局面に持ち込もうとする有利な局面からは紛れにくい手を選ぶ紛れを定式化数量化したい 49

50 局面評価と勝率の関係局面評価関数は優勢度の推定値所詮は推定値実際の値は広がりがある敗勝形勢不利なら勝敗ラインの推定が不正確な右側部分の方が高い可能性面積が問題不正確な評価真の優勢度 50

51 局面評価の誤差の推定局面評価値は真の優劣の期待値を表現分散までわかれば勝率を表現できる機械学習で分散を推定局面評価値と深い読みの結果を大量に比較評価要素ごとに誤差を推定分散がわかれば勝率を計算可能 51

52 将棋の強さの尺度段位は現在の強さを表すものではないレーティングチェスなどのゲームで使われる指標対局成績からの相対尺度敗者から勝者に得点を移動合計は一定レーティングが高い相手に勝てば大きくプラスレーティングが低い相手に勝てば小さくプラス勝敗が３１の割合なら２００点差レーティングが１０００点違えば千勝一敗の差コンピュータは時間を3倍使うと約200点強くなる

53 コンピュータ将棋は名人に勝てるコンピュータは2年ごとに倍程度速くなっている 10年では25 32倍 3倍が3回程度レーティングで点ぐらい強くなる計算現状で女流トップやアマチュアトップより少し強いトッププロ棋士との差は600点ぐらいかソフトが現状でもコンピュータが速くなるので 10年後には勝てるという単純な考えは成り立ちそうにない

54 そう単純ではない理由そんなに早くは勝てないかも CPU単体はもうあまり速くできず並列化が必須将棋のような最適化探索は並列処理が難しい現状は並列処理に何台使っても実質数倍程度日本将棋連盟が対局を承知しないかももっと早く勝てるかも画期的な並列処理手法が出てくるかも画期的なアルゴリズムが出てくるかも

55 異なるアプローチモンテカルロ法ランダム試行を何度も繰り返しそれらの平均で真の値を推定する確率的手法例円周率の計算 ① 正方形中に一様にランダムに点をバラ撒く ② 内接円内の割合を計算 ③ 点の数を増やしていけば割合は π/4 に近づくはず 55

56 ゲームへのモンテカルロ法適用モンテカルロ法の最適探索への適用 ① 候補手を指した局面から開始 ② その後は合法手中からランダムに着手していく ③ その結果の勝敗数を記録これを繰り返し勝ちが多かった候補手を選ぶ簡単に並列処理できて高速化可能ランダムプレイに対して勝率が高くても 56

57 Multi-Armed Bandit 問題 One-Armed Bandit 片腕の盗賊スロットマシン何本もレバーがあるスロットマシンそれぞれ当たり確率が違うかもしれない何回か試した後次はどのレバーがいい今まで当たりが多かったもの高確率だが運が悪かっただけのがあるかもランダムに選ぶよいレバーの見当が少しはついてるのに 57

58 Multi-Armed Bandit の最適解レバーを引いてみることによって得られるのは当たりが出ることによって得る直接の利得試してみることによって得る情報将来の利得両者の適切なミックスが最適理論上は試行回数 n のうち最適でないものを選ぶ回数を確率1で O log n)回以内にできる最適な選択方法は複雑で非実用的近似的方法を使うのが有力 58

59 UCB: Upper Confidence Bound 以下のUCB値最大の選択肢を試す UCB１全体の試行回数選択肢 i のUCB値選択肢 i の勝率選択肢 i の試行回数最適手以外を試す回数はO log n)回に漸近理論上最適な手法との違いは定数倍程度他にも近似方式はいくつかある 59

60 UCT: UCB for Tree UCB に基づく選択を探索木のノードごとに適用見込みの高い手試行の少ない手を優先コンピュータ囲碁では大成功単純な UCT 探索ではなく知識との組合せ大規模な並列処理が比較的容易将棋などより局面評価が難しいランダムに近くてもいいから終局まで打ってみた方が確かな結果将棋でも成功する可能性はある 60

61 機械学習の視点でUCTを見るとどの手を多く試すかどこに資源を投入資源投入をそれまで得られた結果で制御自ら作ったデータからの学習による資源投入制御 61

62 メタ計算の重要性メタ計算計算の進め方についての計算コンピュータが速くなっても計算量は有限どの計算をすべきかが重要賢い人は何を考えればよいかわかる人賢いコンピュータは何を計算すればよいかわかっているコンピュータ 62

63 成長するコンピュータコンピュータは学べる機械学習が有利な領域は急速に拡大中入手可能な電子データはますます大量に解析のための処理能力も向上していくコンピュータは経験を積めるコンピュータ自身が熟考して結果を蓄積蓄積した結果経験から知識を抽出して利用人間の場合より経験の共有はずっと容易 63

64 まとめコンピュータゲームプレイヤの構成法いろいろなアプローチ探索機械学習確率的手法完全に計算しきれない場合の対処法問題が複雑であるほどメタ計算が重要情報処理技術の進展のひとつの重要な方向 64

65 近山担当分のレポート課題十年後を見据えて機械学習の適用が有効と思われる領域をあげその根拠を述べよ考慮すべき点コンピュータの能力は百倍に Moore 則機械学習には大量データの利用が不可欠需要がないところに技術の発展はない期待する分量ワープロなら2 3ページ 65

66 成績評価方法出席回数学期末レポートの提出と評価全6教員の課題から3課題以上について提出どの教員の課題を選んで提出するかは自由調査は大事だが引用は引用と明示することコピペをオリジナルかのように偽るのは絶対ダメ 66

67 レポート提出について提出方法電子メールによる場合原則宛先タイトルに情報技術論氏名学生証番号紙媒体の場合特に指定のある場合等アドミニストレーション棟教務課前提出箱締切教務前提出箱 7月25日水電子メール 7月27日金 /07/11 67

<4D F736F F F696E74202D2091E F B835E B C >

<4D F736F F F696E74202D2091E F B835E B C > 機械学習とコンピュータゲームプレイヤへの応用工学部電子情報工学科近山隆 1 講義の概要機械学習 ( 前回 ) コンピュータ将棋プレイヤと機械学習 ( 今回 ) コンピュータゲームプレイヤ研究の状況コンピュータゲームプレイヤ激指ゲーム木の探索手法機械学習のゲーム木探索への応用の応用モンテカルロ法と機械学習 2 コンピュータゲームプレイヤとはコンピュータの誕生当初から研究されてきた人間の知性の象徴