エージェントアプローチ人工知能 第3版 五章
- 1. 人 工 知 能 特 論 第五章 ゲーム探索 17646104岩佐幸翠
- 2. 5.1 ゲーム
- 3. ゲーム ? 競争的環境 ? マルチエージェント環境 他のエージェントが自分の将来に影響する 競争的 協調的 ゲーム
- 4. ゲーム理論におけるゲーム ? 手番交代 ? 2人プレイヤ ? 決定的 ? 環境の次の状態が完全に現在の状態から決定 ? エージェントだけが行為する ? 完全情報 ? 全てのエージェントは環境の全ての情報を知る ? 零和 ? 片方が勝てば片方が負ける
- 5. 本章におけるゲーム ? 複数プレイヤ 麻雀など、ゲームは二人とは限らない ? 零和 ? 決定的も非決定的も扱う ? 偶然の要素を含むゲームも扱う
- 6. ゲームを解くことの難しさ① 探索しなければならない手数が膨大 ? チェス ? 平均分岐数は35手 ? 一局の手数は先手後手各50手 ? 一局の探索木のノード数は10154
- 7. ゲームを解くことの難しさ② 10倍速く探索Aくん Bくん ? 普通の探索 - 迷路 目的: ゴールすること Aくんは時間をかけてもゴールできる ? ゲームの探索 - オセロ 目的: 勝利すること Aくんはおそらく1回も勝てない ゲームでは時間を有効に使って よりマシな解を探さないと何も得られない場合がある
- 9. ゲームの定式化 ? ? ? : 初期状態 ? ??????(?) 状態s に遷移したプレイヤを定義する ? ???????(?) 状態s にいるプレイヤが次に指せる手の一覧を返す ? ??????(?, ?) : 遷移モデル 状態s から手a を指した場合に遷移する状態を返す ? ????????????(?) : 終端テスト ゲームが終了していればtrueを返す ? ???????(?, ?) : 効用関数 プレイヤpにとっての終端状態sにおける最終スコアを返す
- 10. ゲームの定式化: 図解 S0 S1 ? ? ? ? S2 S1 状態(= 盤面) 指し手(= 駒を動かすこと)
- 11. ゲームの定式化: 図解 S0 S1 ? ? ? ? S2 ??????? ? ? = {? ?, ? ?}
- 12. ゲームの定式化: 図解 S0 S1 ? ? ? ? ?????? ? ?, ? ? = ? ? S2
- 13. ゲームの定式化: 図解 S0 S1 ? ? ? ? ?????? ? ?, ? ? = ? ? S2 ??????? ? ? = {? ?, ? ?} ゲームの探索木(ゲーム木)は ACTIONS(s)とRESULT(s, a)で表すことが出来る
- 14. ??ゲーム ? ? ? ? ? ? ? … …
- 15. 5.2 ゲームにおける意思決定
- 16. 戦略 ??ゲームで?を勝たせたい ? 普通の探索問題なら ?が勝ちとなる終端状態にたどり着ける 指し手ならばどの指し手でも良い ? ゲームの探索問題なら ?も自分が勝ちとなるように反撃する 上記のようになることはない ? ? ? ? ? ? ? ? ? ? ? 状況に応じた「戦略」が必要
- 17. ミニマックス値 ? ここからは… MAXさんとMINさんがゲームする MAXさんに勝たせたい ? ミニマックス値 その局面から最後まで両者が共に最善手を指すと 仮定した時の、その局面の効用 ??????? ? = ???????(?) ??? ? ???????(?????? ?, ? ) ??? ? ???????(?????? ?, ? ) … ?が終端ノード … ?が???のターン … ?が???のターン
- 18. ミニマックス値 ? ここからは… MAXさんとMINさんがゲームする MAXさんに勝たせたい ? ミニマックス値 その局面から最後まで両者が共に最善手を指すと 仮定した時の、その局面の効用 … ?が終端状態 … ?が???のターン … ?が???のターン ??????? ? = ???????(?) 最も??????? ? の高い手が選択される 最も??????? ? の低い手が選択される ? ミニマックス決定 最もミニマックス値が高くなるように手を指すこと
- 19. ミニマックス法 ミニマックス値を用いて最善手を求める MAX MIN 3 12 8 2 4 6 14 5 2
- 21. ミニマックス法 MAX MIN 2 4 6 14 5 2 2
- 23. ミニマックスアルゴリズム MAX MIN 3 12 8 2 4 6 14 5 2 3 2 2 3
- 24. 多人数ゲームので最適決定 今までは二人ゲームの話… ミニマックス法を多人数ゲームに適用する S0 S1 ? ? ? ? S2 ? ? = ? ? ? = ? ? ? = ? ? ? = ? ? ? = ? ? ? = ? ? ? = ? ? ? = ? ? ? = ?
- 25. 同盟関係 ? 多人数ゲーム特有の問題 ? A?B?Cの三名がプレイするゲーム ? A?Bの立場は弱く、Cの立場は強い ? A?Bは協調してCを弱体化させる ? 同盟関係の破棄 ? Cが弱体化したらA?Bはいずれ約束を破る ? 約束を破ると長期に渡って信用を失う ? 約束を破ることにより失う信用と 得られる利益を天秤にかけることになる
- 26. 5.3 α-β枝刈り
- 27. ミニマックス法の問題点と解決 時間計算量は?(? ?) ? 問題点: 膨大な時間計算量 ? ゲーム木の最大の深さをm ? 各局面において選択できる手の数をb ? 解決策: α-β枝刈り 時間計算量を?( ? ?)まで減らせる
- 28. α-β枝刈り αとβはそれぞれ次の意味 ? α:それまでのMAXにとっての最善の選択の値 ? β:それまでのMINにとっての最善の選択の値 α-β枝刈りは以下の2つに分けられる ? αカット: MAXが手番の時にするカット ? βカット: MINが手番の時にするカット
- 32. α-β枝刈り: αカット ? MIN は MAX の評価値を最小化させるので 指し手B のミニマックス値は 2 が上限 ? 「?」がどうであれ MAX は指し手Bより 指し手Aを選ぶので、指し手Bは探索不要 MAX MIN 8 10 2 8 ≦2 指し手A 指し手B
- 33. α-β枝刈り: βカット ? MAX は MAX の評価値を最大化させるので 指し手B のミニマックス値は 10 が下限 ? 「?」がどうであれ MIN は指し手Bより 指し手Aを選ぶので、指し手Bは探索不要 MAX MIN 2 -1 10 ? 2 10>= 指し手A 指し手B
- 35. 5.4 不完全リアルタイム決定
- 37. 特徴 ? 評価関数は、その状態における様々な特徴 を 計算することによって成り立っている ? それらの特徴がまとまってカテゴリを形成する ? 実際は非常に多くのカテゴリを必要とするため、 カテゴリを考慮せず特徴そのものに得点を付ける場 合が多い ???? ? = ? ? ? ? ? + ? ? ? ? ? + ? + ? ? ? ? ? EVAL: 評価関数 f: 特徴 w: 重み
- 38. 探索の打ち切り ? これまでは終端テストで終端と判断された 場合に探索を終了していた ? しかし現実には終端までの探索は不可能 ? ある程度の深さまで探索が進んだら or 持ち時間を経過したら探索を打ち切ればよい ? 探索を打ち切るか否かを決定するテストを 切断テストと呼ぶ
- 40. 水平線効果 ? 探索の深さを有限とした時に発生 ? 短期的に見ればプラスに見えるが 長期的に見ればマイナスな指し手を 探索範囲が有限なせいで選んでしまう ? 例: 将棋 10手先まで探索できるエージェント ちょうど10手先に飛車を取られてしまう → 他の駒を捨てることで飛車が取られるのを 11手先まで先延ばしできるとしたら その手を選んでしまう
- 41. 前向き枝刈り ? ある状態からとりうる指し手候補の一部を 先読みなしにその場で枝刈りすること ? 最善手をも刈る恐れがある危険な方法 ? 次のような安全な時に使う: ? 2つの指し手が対称的 ? 2つの指し手がほぼ同じ
- 42. 5.5 偶然の要素を含むゲーム
- 44. 偶然があるゲームの局面評価 ? 偶然節点 MINの手番とMAXの手番の間など、 偶然要素が入る部分には「偶然節点」を設ける ? 期待ミニマックス値 ミニマックス値と生起確率を掛け合わせ これを足し合わせる ? 期待ミニマックス法 全ての偶然節点を校了する必要があるため 計算量は? ? ? ? ? を必要とする
- 45. 5.6 不完全情報ゲーム
- 46. 不完全情報ゲーム 「相手に見えない情報が存在する」ゲーム ? ババ抜き 相手に手札が見えない ? 大富豪 相手に手札が見えない ? 人狼 相手に役職が分からない
- 49. 引っ掻き回し?撹乱 自分のスコアが高くなるようなアルゴリズムを 組む方が簡単であることが判明(Gordon, 1994) ? あえて相手の思考のウラを突いた 動きをすれば相手は混乱するのでは？
- 50. 5.7 最先端のゲーム問題
- 51. チェス IBMのDEEP BLUEが勝利 ? NULL MOVE 自分がパスしても十分に局面の評価値が高い場合 その局面を探索しない枝刈り法 ? FUTILITY PLUNING ? 以下の条件に当てはまる場合枝刈り β値<=切断ノードの１つ前のノードの評価値?マージン ? マージンを動的に推定する手法もある
- 52. その他のゲーム コンピュータが勝ったゲーム一覧 ? オセロ ? 囲碁 ? バックギャモン ? ブリッジ モンテカルロ木探索で勝ちました
Editor's Notes
- #9: 评価関数は一般的にはヒューリスティックであったが、将棋ソフトの笔辞苍补苍锄补などは自动で获得する