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