Comments
Description
Transcript
第13回 7月11日+レポート課題
情報技術論 第 第13回 機械学習 と コンピュ コンピュータ タ ゲームプレイヤへの応用 工学部 電子情報工学科 近山 隆 情報技術論 第13回 1 講義 概要 講義の概要 機械学習（前回） コンピュータ将棋プレイヤと機械学習（今回） コンピュータゲームプレイヤ研究の状況 コンピ タゲ ムプレイヤ研究の状況 コンピュータゲームプレイヤ激指 ゲーム木の探索手法 機械学習のゲ ム木探索 の応用 機械学習のゲーム木探索への応用 モンテカルロ法と機械学習 情報技術論 第13回 2 コンピュータゲームプレイヤとは ピ ゲ コンピュータの誕生当初から研究されてきた 人間の知性の象徴 もともとゲームは現実世界の縮図 もともとゲ ムは現実世界の縮図 組合せ探索問題の一種 多数の選択肢の中から最適なものを選択 多数 選択肢 中 最適 選択 初期局面から必勝手を選べれば最高だが無理 与えられた時間内に、できるだけ良い手を選択 情報技術論 第13回 3 種々 ゲ 種々のゲームのプレイヤ オセロ: 1990年代に人間を凌ぐ チェス: 人間のトップを破る IBM Deep Blue vs 世界チャンピオン カスパロフ （1997） 将棋: アマチュアトップクラス 6x6のオセロは完全に解かれている（必勝手順が既知） 現在コンピュータに確実に勝ち越せる人は100人はいない 囲碁: 初級者レベル ⇒ 近年急激に実力向上 新しいアルゴリズムが大きな役割 情報技術論 第13回 4 コンピュータ将棋プレイヤ「激指」 ピ 将棋 「激指 現時点でトップのプレイヤのひとつ 近山研究室の大学院生が開発 世界コンピュータ将棋選手権で 活躍し、商品化も 開発者の修了 就職後も 開発者の修了・就職後も 開発チームは継続 研究室 後輩 研究室の後輩による関連研究 関連研究 情報技術論 第13回 5 「激指 歴史（誕生 成長） 「激指」の歴史（誕生⇒成長） 1999.秋 2000.3 大学院生4人、将棋でもやってみようか 「速い実装をすれば勝てるんじゃないの?」 世界コンピュータ将棋選手権（WCSC）挑戦 二次予選 9 位 決勝進出ならず 2000秋 実現確率打切りを提案、実装（鶴岡） 2001.3 WCSC二度目の出場 決勝進出 4位 他 他ソフトと違う特徴的棋風に注目集める 違う特徴的棋風 注目集め 2001.12 商品版 毎日コミュニケーションズより発売 情報技術論 第13回 6 「激指 歴史（円熟期） 「激指」の歴史（円熟期） 2002 5 2002.5 WCSC初優勝 2003.5 WCSC 3位 2004.5 WCSC 2位 2005 5 2005.5 WCSC 全勝で全勝優勝 勝又プロ五段との記念角落ち戦にも勝利 ア 竜王戦全国大会出場 ベスト16 アマ竜王戦全国大会出場 スト16 2005 6 2005.6 2005.7 「将棋世界」企画 将棋世界」企画 トッププロとの角落ち戦 渡辺竜王に敗れるも、木村一基7段に勝利 情報技術論 第13回 7 「激指 歴史（停滞 ⇒ 復活） 「激指」の歴史（停滞 2006.5 WCSC 5位 2007.5 2007 5 WCSC 4位 2008.5 WCSC 3度目の優勝 優 エクシビションで清水上アマ名人に勝利 2009 5 WCSC 6位 2009.5 2010.5 WCSC 4度目の優勝 この間にどの強豪ソフトも確実に強くなってきている 情報技術論 第13回 8 「激指 歴史（ 「激指」の歴史（ここ数年） 数年） 2006.5 WCSC 4位 2007 5 2007.5 WCSC 2位 （YSS、ISと三すくみ状態） （YSS ISと三すくみ状態） 2008.5 WCSC 3度目の優勝 情報技術論 第13回 9 決定的完全情報零和ゲ ム 決定的完全情報零和ゲーム 決定的: 偶然性なし （⇔ backgammon） 完全情報: 全情報は開示 （⇔ contract bridge） ⇒ 互いに最善を尽くした場合の勝負は 原理的には決まっている (たとえば、○×ゲームで賭けられる?) ゼロサム: ゼ サム 自分の勝ちは相手の負け 自分 勝ちは相手 負け 情報技術論 第13回 10 AND O 木探索 AND-OR 局面 指し手 OR 自分の手番: ひとつ勝つ手が あればいい 相手の手番: ひとつでも 負ける手が あると困る AND 情報技術論 第13回 11 最後 最後までは読みきれない 読 6手先 1秒 6手先: ある局面で可能な手は60種ぐらい 7手先: 1分 ∴1手深く読むには約60倍の時間 8手先: 1時間 9手先 2.5日 9手先: 2 5日 ゲームの終了まで探索するのは 10手先: 半年 11手先: 30年 事実上不可能 12手先: 1800年 … ⇒ 最後まで読むのはあきらめて、 読める範囲 なる く有利になる手を探索 読める範囲でなるべく有利になる手を探索 勝ち負けの二値 ⇒ 有利不利の度合いの多値 局面の評価が重要に AND/OR 探索 ⇒ Mini-Max Mi i M 探索 情報技術論 第13回 12 Mi i M 探索 Mini-Max探索 先手番 後手番 先手番 選択手 1 -2 2 -5 5 -2 2 Mi 節 Min 1 -2 2 7 3 1 6 7 6 -4 4 -8 8 もっとも後手有利 も とも後手有利 の手を選択 1 情報技術論 第13回 もっとも先手有利 の手を選択 Max 節 13 探索 省略 α枝刈り 探索の省略： 枝刈 先手番 後手番 先手番 先手は左の枝をとれるので この局面の評価は 2以上 ？ 2 後手が左の枝をとれるので この局面の評価は-3以下 2 2 -5 7 2 7 -3 3 ？ -3 -4 ？ ？ 情報技術論 第13回 ここがどうだろうと、 この手は選ばない 14 β枝刈 α枝刈りと先後逆 β枝刈り: 枝刈 先後逆 先手番 後手番 先手番 後手は左の枝をとれるので この局面の評価は 2以下 ？ ？ ？ 2 -5 2 先手が左の枝をとれば この局面は 7以上 ？ 7 ？ ？ ？ ？ ？ ？ 情報技術論 第13回 ここがどうだろうと、 この手は選ばない 15 探索窓 探索窓：α値とβ値の範囲 値 β値 範囲 各局面で考慮すべき評価値の下界 上界 各局面で考慮すべき評価値の下界・上界 先手番 後手番 先手番 ？ [2,∞] [2 -3] [2,-3] 2 2 -5 5 7 2 ここは最低でも評価値 2 最高は不明（∞） 7 -3 3 ここは最高でも評価値 -3 親から2 以下は不要とわかる ⇒ これ以上の探索不要 ？ -3 3 -4 4 ？ ？ 情報技術論 第13回 16 αβ枝刈りの効率向上 β枝刈 効率向上 有望な手を先に探索するのが大事 ⇒ 早く大きく枝刈りできる 理想的探索順なら約倍の深さ読める 反復深化 iterative deepening 繰返し段々深く読んでいく 浅い読みの結果で深い読みの際の順序を決める 浅い読みは何度も行なうので冗長だが… 浅い読みは何度も行なうので冗長だが 深さ優先の探索がメモリコスト上で有利 探索コストは深さの指数関数⇒浅い探索は安価 情報技術論 第13回 17 探索窓 縮小 探索窓を縮小した探索 探索 探索窓をあらかじめ縮小して探索 探索窓の決め方 結果が窓の外だと、どちら側かしかわからない 結果が窓の外だと どちら側かしかわからない 結果が窓の内なら、探索が効率的 ∵ 悪い着手を早くあきらめられる 以前の着手決定の際の結果から推定 反復深化の際 浅い読みの結果から推定 反復深化の際、浅い読みの結果から推定 幅0の探索を繰り返す手法も 情報技術論 第13回 18 水平線効果 Horizon H i Effectt 限られた深さの mini-max 探索の本質的問題 読める深さは限られている 読める範囲内で最適なものを探す 読める範囲のちょっと先の不利に気づかない どうやっても先が不利になりそうな局面で 小さな不利の手伸ばし（歩の打捨てなど）で、 小さな不利の手伸ばし（歩の打捨てなど）で 大きな不利を視界の外に追いやる振舞い 情報技術論 第13回 19 どこまで深く読むか 深く読 単純には最大「n 手」先まで 最後の一手がはんぱだったら? 駒の交換で n 取ったところまで（大きく有利?） 取られたところまで（大きく不利?） 「ほんのちょっと先まで読むと全然違う」 ほんのちょっと先まで読むと全然違う」 という局面は、少し先まで読みたい 情報技術論 第13回 20 選択深化 selective l ti deepening d i 枝によって先読みの深さを変える 少し読めば精度が大きく高まるなら、より深く i e 限界効用の高いところに資源投入 i.e. 従来からゲームプレイヤで広く採用 広 採用 連続王手が終わるまで 駒の取り合いが一段落するまで… ⇒ アドホックに人手で設定するのでは 将棋の知識が必要 考え落ちが生じやすい 将棋の知識が必要、考え落ちが生じやすい 情報技術論 第13回 21 実現確率打切り 実現確率打切 選択深化の一手法 方針: 実現しそうな局面は深く読む 現局面から始めて、各局面の実現確率を推定 現局面から始めて 各局面の実現確率を推定 実現確率は棋譜から得た統計データから推定 打切り閾値以上の実現確率の部分木のみ探索 情報技術論 第13回 22 局面 実現確率 算定手法 局面の実現確率の算定手法 指し手の実現確率を求める 指し手を表す特徴を適宜設定 約600局のプロ棋士の棋譜から各特徴を持つ手に ついて、指せるときに実際に指した率を計算 現在の局面からある局面に至る指し手の確率の 積が その局面の実現確率 積が、その局面の実現確率 e.g., 大駒の交換は、たいがい取り返す ⇒ 取った局面、取り返した局面はほぼ同確率 情報技術論 第13回 23 実現確率打切り 実現確率打切 局面の実現確率 p = p1×p2×p3 p1 p2 実現確率 q1 以上 実現確率 q2 以上 p3 実装は対数で管理 乗算⇒加算 情報技術論 第13回 24 実現確率打切 実現確率打切りは、なぜ有効？ ぜ有効？ 強いプレイヤが実際に指すことが多い手は 良い手である可能性が高い 良い手は有利な局面をもたらしやすい 有利な局面に至る手は詳しく調べる価値あり 注： 「強いプレイヤが指しそうな手を選ぶ」のではない 「強いプレイヤが指しそうな手は詳しく調べる」 すなわち、資源投入量の制御にあたる 情報技術論 第13回 25 コンピュータ将棋と機械学習 ピ 将棋 機械学習 コンピュータ将棋の黎明期: 職人芸 激指の実現確率: データからの学習の導入 局面のどこに注目、どの局面を探索、… 局面のどこに注目 どの局面を探索 計算機が遅いときには、これしかなかった 職人芸的プログラミングからの解放 近年では機械学習の適用が当然に コンピュータが十分速くなった 大量のデータが扱えるようになった 扱 情報技術論 第13回 26 実現確率算定 改良 実現確率算定の改良 指し手の確率＝指し手を生成する尤度を学習 特徴として盤面パタ ンなどを追加 特徴として盤面パターンなどを追加 手の移動先・移動元の3x3のパターンなど 約4000局のプロ棋士の棋譜(約50万局面)で、 指された手を正例、指されなかった手を負例とし、 Maximum Entropy 法で学習 「ひと目」で「この手は65%指しそう」とわかる ひと目」で この手は65 指しそう」とわかる 情報技術論 第13回 27 局面評価関数 機械学習 局面評価関数の機械学習 かつてはなかなかうまくいかなかった コンピュータ将棋プレイヤ コンピュ タ将棋プレイヤ Bonanzaの登場 評価要素: 玉と他の2個の駒の位置関係すべて 比較学習を導入して初出場で優勝 (2006) 大きなインパクトを与えた 100万におよぶ次元の重みを調整する学習 今日では多くのコンピュータプレイヤが 同様の方法を採用 情報技術論 第13回 28 比較学習： 局面評価パラメタの学習法 Deep Thought: IBMによるチェス専用機 世界チャンピオン 世界チ ンピオン Kasparov K を破 た を破った Deep Blue (1997) の前身 評価関数の重みを自動学習 (1988) 強いプレイヤが指したと同じ手を指すように調整 指した手/指さなかった手の評価値の相対値が問題 指した直後の局面の評価を高くするのではダメ 先まで読んだ結果、その手を指すように調整 情報技術論 第13回 29 詰将棋 指将棋 関係 詰将棋と指将棋の関係 詰将棋は読み切る ⇒ 指将棋とは異なる発展 指将棋でも詰の判定は重要 証明数・反証数に基づく選択深化による探索 プロ棋士を大きく上回る実力 それでも殊に「不詰」の判定には時間がかかる 終盤はもちろん、序盤でも「頓死」の可能性あり 激指では全体の30%の時間が詰み探索 詰むはずもない局面では時間をかけたくない 情報技術論 第13回 30 証明数と反証数 proof number/disproof number AND OR 木全体の真偽を決める問題 AND-OR たとえば詰将棋 木をあまり展開せずに真偽を決めたい 証明数：あと 明数 p ノード展開するだけで真とわかるかも 展開 だ 真 反証数：あと d ノード展開するだけで偽とわかるかも 証明数・反証数の小さなノードを優先して展開 証明数 反証数の小さなノ ドを優先して展開 ∵ 最小限のコストで結論を得られそうな戦略 情報技術論 第13回 31 「直感 重要性 「直感」の重要性 強い将棋指しは先読みで手を探さない? 「よい手は直感的に思いつく」 「時間をかけて読むのは直感を確かめるだけ」 時間をかけて読むのは直感を確かめるだけ」 「実はよくない手だった」とわかる場合も ⇒ 「直感」は「どの手をよく読むべきか」の 資源配分制御に使っている 資源配分制御に使っている! ⇒ 詰み判定への資源配分を「直感」で制御 情報技術論 第13回 32 詰 不詰 予測 （三輪2004） 詰・不詰の予測 将棋の局面をいくつか の特徴量で表現 多くの局面について 詰将棋プログラムで 詰・不詰を決定 詰・不詰と特徴量との 詰 不詰と特徴量との 関係を SVM で学習 特徴量２ 情報技術論 第13回 特徴量１ 33 ソフトマージンの ソフトマ ジンの SVM 線形分離不能の場合 線形では誤分類 誤分類の程度を数値化 誤分類コスト最小となる 分離超平面を選択 Support Vector 情報技術論 第13回 34 局面 特徴129種 人手 選択 局面の特徴129種を人手で選択 玉将について: 絶対位置、玉間の距離 玉周辺の状況: 周辺の各位置は盤端/空/味方/敵 玉の可能な動きの数 守 駒 攻 駒 合 駒状態 駒 数 守り駒、攻め駒、合い駒状態の駒の数 手駒の種類と数 可能な王手の種類 情報技術論 第13回 35 学習 用 学習に用いたデータ 終局に近い四万局面を生成 プロ棋士の四千局の棋譜を用意 終局近くからランダムに進めて各十局面を生成 詰将棋プログラムで判定（最長３０秒で判定） 全四万局面中10,159局面が詰み 棋譜 2010/07/12 進行 局面集 情報技術論 第13回 判定 詰み 不詰 36 C Cross Validation V lid ti 限られた数のデータを学習と評価に使いまわし ３-fold cross validation では: データ全体 学習 学習 評価 評価 評価 学習 学習 情報技術論 第13回 37 実験 結果(4 実験の結果(4-fold ld cross valid.) lid ) 実際は 詰と判定 詰 不詰 6,414 1,865 計 8,279 不詰と判定 3 745 27,976 3,745 27 976 31,721 31 721 計 10,159 29,841 40,000 この精度の判定が 数マイクロ秒で可能 詰 不詰 正解率 0.775 0 882 0.882 再現率 F値 0.631 0.696 0 938 0.909 0.938 0 909 情報技術論 第13回 詰み判定 としては 信用できない 詰みの見逃しは 少なくない 38 詰判定 時間 詰判定に時間をかける価値 価値 いかにも詰みそう 特徴量２ 詰み判定超平面との 距離に注目 大きく離れていれば なんともいえない 判定は信頼できそう 距離にしたがって 詰み判定にかける いかにも詰まなさそう 時間を調節 情報技術論 第13回 特徴量１ 39 詰判定 詰判定への資源投入量制御 資源投入量制御 局面と分離超平面との距離で詰判定ルーチン への時間配分を制御（Sigmoid関数） 詰み判定にかける時間 詰まなそうなら 詰みを読むのに 時間をかけない － ← 0 → ＋ 情報技術論 第13回 詰みそうなら 時間をかけて 詰みを読む 分離超平面との距離 40 資源投入量制御 効果 資源投入量制御の効果 この制御を行わない版と千局対戦させたら… 平均計算時間を 65.6% に削減して、勝率 53.4% 3/4 の計算時間だと、勝率55.3%（3.26σ） の計算時間だと、勝率55 3%（3 26σ） ⇒ 強さを保って 2/3 の計算時間 ⇒ 少ない計算時間で有意に強くなった 情報技術論 第13回 41 特徴量 自動生成（三輪2005） 特徴量の自動生成 局面を表す特徴量は人間が選ぶのが普通 問題領域の知識が必要 見落としが生じる可能性 多数の事例から自動生成できないか？ 単純で自明な特徴の組合せを特徴量に 有利不利との関係が強い組合せを自動選択 2010/07/12 情報技術論 第13回 42 特徴パ 特徴パターンの生成手順 生成手順 選択 有用なパターン 2010/07/12 頻出飽和パターン これだけは人手で 特徴パターン 単純な特徴要素 組合せ 頻出する もの抽出 棋譜＋ラベル付け 情報技術論 第13回 43 パ パターン選択と評価関数構築 選択 評価関数構築 1. 2. 頻出するパターンの中から、 頻出するパタ ンの中から 独立して意味を持つ（飽和）パターンのみ選択 有用なパターンを選択 ① ② 条件付相互情報量の大きいものを選択 各訓練局面の持つ頻出飽和パターンのうち、 ラベル付けとの相互情報量上位のもののみ考慮 ∵ すべて考えるとメモリに載りきらない Naive Bayesian classifier で評価関数構築 2010/07/12 情報技術論 第13回 44 詰将棋問題 詰将棋問題での実験 実験 基本特徴要素： 駒の位置、効きの 41,224 種 訓練用 80,000局面 80 000局面（← オンライン将棋対局サイト） 組合せは論理積のみ考慮 2%以上の局面で出現するもの 38,173,197 種 事前選択 上位100 200, 事前選択を上位100, 200 500, 00 1000 種で試行 種 試行 評価関数に用いる評価要素数 100～10,000 9,768 局面を用いて評価 2010/07/12 情報技術論 第13回 45 処理 要 処理に要した時間 時間 2種類のシステムを利用 Xeon 3.06 GHz ×2, メモリ 2GB Opteron 250 2 2.4 4 GHz ×2, ×2 メモリ 8GB 頻出飽和パターン抽出: Xeon で 38分 有用なパターンの抽出: Opteron で5日間 実用的な時間でできる範囲内に設定 2010/07/12 情報技術論 第13回 46 詰将棋問題 詰将棋問題への適用結果 適用結果 2010/07/12 情報技術論 第13回 47 詰将棋のための評価関数 自動構築実験のまとめ 上位200, 評価要素数 2,000 で最良の結果 正解率 約74％ 計算量膨大: さまざまな工夫をして計算量を 削減して、なんとか実現可能に 人手で評価要素を選択 SVM で評価関数を 人手で評価要素を選択、SVM 作った場合の 84% にはまだ及ばない ゲーム以外の問題への適用も十分考えられる 2010/07/12 情報技術論 第13回 48 局面評価 見直 （構想段階） 局面評価の見直し 局面の評価値 ≒ その局面から勝てる確率？ 強い棋士は： 不利な局面では紛れを求める 実力差があるときの駒落ち将棋は最初から不利 上手はわかりにくい局面に持ち込もうとする 有利な局面からは紛れにくい手を選ぶ 紛れを定式化・数量化したい ⇒ 情報技術論 第13回 49 局面評価 勝率 関係 局面評価と勝率の関係 局面評価関数は優勢度の推定値 所詮は推定値 ― 実際の値は広がりがある 敗 勝 形勢不利なら 勝敗ラインの 推定 推定が不正確な 右側部 右側部分の 方が高い可能性 面積が問題 不正確な評価 真 優勢度 真の優勢度 情報技術論 第13回 50 局面評価 誤差 推定 局面評価の誤差の推定 局面評価値は「真の優劣」の期待値を表現 分散までわかれば「勝率」を表現できる 機械学習で分散を推定 局面評価値と深い読みの結果を大量に比較 評価要素ごとに誤差を推定 ⇒ 分散がわかれば「勝率」を計算可能 分散がわかれば「勝率 を計算可能 情報技術論 第13回 51 コンピュータ将棋がプロ棋士に挑戦 戦 2010年10月11日 東京大学本郷で開催 2010/07/12 情報技術論 第13回 52 対局当日 様子 対局当日の様子 「激指」開発者 鶴岡慶雅 清水市代女流王将 市代 流 将 大盤解説会場 工学部2 工学部 2号館 号館213 213号室 号室 コンピュータ将棋システム「あから2010」 コンピ コンピュータ将棋４システムの合議制 タ将棋４システムの合議制 合議制 「激指」「GPS将棋」「Bonanza」「YSS」 いずれも過去に世界コンピュータ将棋選手権 世界コンピュータ将棋選手権優勝 多数決が基本； 票が割れたら少し長考 それでも割れたら「激指」が優先 ハ ドウ ア 分散配置した計約600CPUコア ハードウェア： 対局結果 86手で清水女流王将が投了 86 86手で清水女流王将が投了、 手で清水女流王将が投了 手で清水女流王将が投了、 あから2010 あから 2010の勝利 の勝利 将棋 強 将棋の強さの尺度 尺度 段位は現在の強さを表すものではない 在 強 レーティング：チェスなどのゲームで使われる指標 レーティング 対局成績からの相対尺度 相対尺度 敗者から勝者に得点を移動 ⇒ 合計は 合計は一定 定 レーティングが高い相手に勝てば大きくプラス レ ティングが低い相手に勝てば小さくプラス レーティングが低い相手に勝てば小さくプラス 勝敗が３：１の割合なら２００点差 レ ティングが１０００点違えば千勝 敗の差 レーティングが１０００点違えば千勝一敗の差 コンピュータは時間を3倍使うと約200点強くなる コンピュータ将棋は名人に勝てる？ 勝 コンピュータは2 2年ごとに倍程度速く 年ごとに倍程度速くなっている 10年では25＝32倍 ⇒ 3倍が3回程度（∵33＝27） レ レーティングで200×3＝600 ティングで200 3 600 600点ぐらい強くなる計算 点ぐらい強くなる計算 現状で女流トップやアマチュアトップより少し強い トッププロ棋士との差は 差は600 600点ぐらい 点ぐらいか ソフトが現状でも、コンピュータが速くなるので、 10年後には勝てる？ 10 年後には勝てる？ ⇒ という単純な考えは成り立ちそうにない そ 単純 そう単純ではない理由 理由 そんなに早くは勝てないかも CPU単体はもうあまり速くできず、並列化が必須 将棋のような最適化探索は並列処理が難しい 並列処理が難しい （現状は並列処理に何台使っても実質数倍程度） 日本将棋連盟が対局を承知しないかも 対局を承知しないかも もっと早く勝てるかも 画期的な並列処理手法 画期的な並列処理手法が出てくるかも 画期的なアルゴリズム 画期的なアルゴリズムが出てくるかも 異なるアプローチ：モンテカルロ法 ランダム試行を何度も繰り返し、 それらの平均で真の値を推定する確率的手法 例） 円周率の計算 ① 正方形中に一様に ランダムに点をバラ撒く ② 内接円内の割合を計算 ③ 点の数を増やしていけば 割合は π/4 に近づくはず 情報技術論 第13回 59 ゲ ゲームへのモンテカルロ法適用 法適用 モンテカルロ法の最適探索への適用 ① 候補手を指した局面から開始 ② その後は合法手中からランダムに着手していく ③ その結果の勝敗数を記録 これを繰り返し、勝ちが多かった候補手を選ぶ ○ 簡単に並列処理できて高速化可能 × ランダムプレイに対して勝率が高くても… 情報技術論 第13回 60 M lti A Multi-Armed d Bandit B dit 問題 One-Armed Bandit（片腕の盗賊＝スロットマシン） 何本もレバーがあるスロットマシン それぞれ当たり確率が違う（かもしれない） 何回か試した後、次はどのレバーがいい？ 今まで当たりが多かったもの？ ⇒ 高確率だが運が悪かっただけのがあるかも ランダムに選ぶ？ ⇒ よいレバーの見当が少しはついてるのに… 情報技術論 第13回 61 M lti A Multi-Armed d Bandit B dit の最適解 最適解 レバーを引いてみることによって得られるのは 当たりが出ることによって得る直接の利得 試してみることによって得る情報 ⇒ 将来の利得 両者の適切なミックスが最適 両者の適切なミ クスが最適 理論上は、試行回数 n のうち最適でないものを 選ぶ回数を（確率1で）O （log n)回以内にできる 最適な選択方法は複雑で非実用的 → 近似的方法を使うのが有力 情報技術論 第13回 62 UCB: CB Upper Confidence C id Bound B d 以下のUCB値最大の選択肢を試す（UCB１） 全体の試行回数 選択肢 i のUCB値 選択肢 i の勝率 選択肢 i の試行回数 最適手以外を試す回数はO （log n)回に漸近 理論上最適な手法との違いは定数倍程度 他にも近似方式はいくつかある 情報技術論 第13回 63 UCT: C UCB CB for Tree UCB に基づく選択を探索木のノードごとに適用 に基づく選択を探索木のノ ドごとに適用 ⇒ 見込みの高い手、試行の少ない手を優先 コンピュータ囲碁では大成功 単純な UCT 探索ではなく、知識との組合せ 探索ではなく 知識との組合せ 大規模な並列処理が比較的容易 将棋などより局面評価が難しい 局 価 難 ⇒ ランダムに近くてもいいから 終局 終局まで打ってみた方が確かな結果 打 方 結果 将棋でも成功する可能性はある？ 情報技術論 第13回 64 機械学習 視点 機械学習の視点でUCTを見ると… C 見 どの手を多く試すか＝どこに資源を投入 資源投入をそれまで得られた結果で制御 ⇒ 自ら作ったデータからの学習による 自ら作 たデ タからの学習による 資源投入制御 情報技術論 第13回 65 メタ計算の重要性 計算 重要性 メタ計算： 計算の進め方についての計算 コンピュータが速くなっても計算量は有限 ⇒ 「どの計算をすべきか」が重要 どの計算をすべきか」が重要 賢い人は何を考えればよいかわかる人 賢いコンピュータは何を計算すればよいか わかっているコンピュ タ わかっているコンピュータ 情報技術論 第13回 66 成長 成長するコンピュータ ピ コンピュータは学べる 機械学習が有利な領域は急速に拡大中 入手可能な電子データはますます大量に 入手可能な電子デ タはますます大量に 解析のための処理能力も向上していく コンピュータは経験を積める コンピュータ自身が熟考して結果を蓄積 蓄積した結果（経験）から知識を抽出して利用 人間 場合 人間の場合より経験の共有はずっと容易 経験 共有 容易 情報技術論 第13回 67 まとめ め コンピュータゲームプレイヤの構成法 いろいろなアプローチ 探索 機械学習 確率的手法 … 探索、機械学習、確率的手法、 完全に計算しきれない場合の対処法 問題が複雑であるほどメタ計算が重要 情報処理技術の進展のひとつの重要な方向 情報技術論 第13回 68 成績評価 出席回数 学期末レポートの提出 全6担当教員のうち3教員の課題について提出 課題は担当教員ごとに出題 どの教員の課題を選んで提出するかは自由 調査は大事だが引用は引用と明示すること コピペをオリジナルかのように偽るのは絶対ダメ 締切： 7月21日（木） 提出先： 教務課 情報技術論 第13回 69 近山担当分 近山担当分のレポート課題 ポ 課題 十年後を見据えて、機械学習の適用が有効 と思われる領域をあげ、その根拠を述べよ 考慮すべき点 コンピュータの能力は百倍に ← Moore 則 機械学習には大量デ タの利用が不可欠 機械学習には大量データの利用が不可欠 需要がないところに技術の発展はない 期待する分量： ワープロなら2～3ページ 情報技術論 第13回 70