Microsoft PowerPoint - ゲーム理論2018.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - ゲーム理論2018.pptx"

なつきおとべ
5 years ago
Views:

1 89 90 ゲーム理論 ( 第回ゲーム木探索 I) 九州大学大学院システム情報科学研究院情報学部門横尾真 yokoo@inf.kyushu-u.ac.jp ゲーム木探索行動の選択が一回だけではなく交互に繰り返し生じる前の番に相手の選んだ手は分かる 9 9 例題二人で交代に, から順にまでの数を言う. 言う数の個数は, 個, 個,3 個のいずれか好きなのを選んでよい最後にを言った方が負け必勝法を言って, 相手に順番を回せば絶対勝ち一方,0 を言って, 相手に順番を回せば, 相手が何個を選んでも, 次にを言える --- 絶対勝ち同様に,6 を言って, 相手に回せば次に 0 を言える --- 絶対勝ち同様に,, 8, を言って回せば勝ち先手が何を言おうと, 後手はを言って回せる結局, 後手が必勝 93 9 このゲームの性質二人で交代に順番が回ってくる自分の前の相手の行動 / 手は完全に観測できる偶然の入る余地がない多くのゲームは同様な性質を持つチェス, 将棋, オセロ, 囲碁, 五目並べ,etc. 上記の性質を満たさないものバックギャモン : さいころポーカー : 相手の手は見えないブリッジ : プレイヤの協調必勝法二人, 完全情報, 決定的なゲームは, 原理的には必勝法が存在する先手必勝 / 後手必勝 / 引き分け先手 / 後手を決めた時点で勝負はついている ( ゲームをするまでもない )!

2 9 96 必勝法 ( 続き ) ゲームの木簡単なゲームなら必勝法が分かる ( 三目並べ ) 引き分け五目並べ先手必勝 6x6 オセロ後手必勝複雑なゲームでは分かっていない分かってしまえばゲームは終り? 状態 / ノード : ゲームの可能な状態状態の遷移 / リンク : 正しい手により遷移可能な状態間を結ぶ ( 一方向 ). 先手を MX プレイヤ, 後手を MIN プレイヤ, 先手の順番 ( 手番 ) に対応する状態を MX ノード, 後手の手番の状態を MIN ノードと呼ぶ. 勝ち負けが決まったノードを端点と呼ぶ例 : を言ったら負け 97 ノードのラベル付け ( 考え方 ) お互いに自分が勝つようにベストを尽くす / のラベルは先手 (MX プレイヤ ) の立場 MX プレイヤは, 絶対勝てる手があればそれを選び, 後手 (MIN プレイヤ ) は, MX プレイヤを絶対負かすことができる手があれば, それを選ぶノードのラベル付け以下のように再帰的に定義端点に関して, そのまま / MX ノードに関しては, 子ノードに少なくとも一つがあれば, すべてなら MIN ノードに関して, 子ノードに少なくとも一つがあれば, すべてならを 00, を -00 とすると, 上記の処理は MX ノードでは子ノードの最大値,MIN ノードでは最小値を取ることに対応 3 ノードのラベル付け 3 3 3

3 0 0 例題 : ニム ( コイン取り ) コインが個と 6 個の列交互に, 個もしくは隣り合う個を取る最後に個もしくは隣り合う個を取った方が勝ち先手必勝 / 必負?, 木を書いて確かめよう状態 / ノード各列の個数の ( 小さい順に並べた ) リストで表現 : 初期状態は (, 6) 初期状態から遷移可能な状態 : (6), (, ), (, ), (,, ), (,, 3) すべての木を展開するのは大変なので, とりあえず (, ) から木を展開してみよう 03 0 ゲーム木の展開必勝法を見つけるためには必ずしも木を完全に展開する必要はないある MX ノードに関して, 子ノードに少なくとも一つの WIN があれば, その MX ノードは WIN 他の子ノードは展開しなくても良いある MIN ノードに関して, 子ノードに少なくとも一つ LOST があれば, その MIN ノードは LOST 他の子ノードは展開しなくて良いゲーム木のサイズチェッカー 0の30 乗世界チャンピオンオセロ 0の60 乗世界チャンピオンチェス 0の0 乗世界チャンピオン将棋 0 03 の0 年乗級プロ棋士に勝利アマ段! 囲碁 0の360 乗モンテカルロ碁が強い 06 アマ年アルファ碁が級チェッカーでも必勝法はまだ見つかっていないトッププロに勝利! 007 年に引き分けであることが証明された 0 06 例題先手は, 後手は上段か下段のどちらか片方の自分の駒を動かす. 左右どちらでも, いくつでも動かすことができるが, 相手の駒を飛び越すことはできない. 自分の番で動かせないと負けこのゲームは先手必勝 / 後手必勝? ゲーム木が大きすぎる場合普通のゲームでは, 端点まで木を展開するのは不可能途中まで展開されたゲーム木で, どの手が良いかを選ぶ必要がある ( 一手, 二手, 三手先まで読む等 ) 3

4 ゲーム木の評価 (MIN-MX 法 ) 途中の状態に関して, その良さを評価する関数を作る ( 静的評価関数 ) 評価関数は数値を返す ( 大きいほうが良い ) チェス / 将棋 : 所有するコマの数 / 価値, 配置等オセロ : コマの数, 位置 ( スミ, 端 ) ( ゲームが終了している訳ではない ) 端点の評価値を, 静的評価関数の値とする他のノードの評価値を, 必勝法を決める方法と同様にして決める (MX ノードは最大値,MIN ノードは最小値 ) ルートの MX ノードで, 最大値を与える経路を選ぶ. 07 tic-tac-too ( 三目並べ ) で, まだ自分が取れる可能性のある列の数ー相手が取れる可能性のある列の数静的評価関数の例 MIN - MX 6-= -=0 6-= -=0 -=- -6=- MIN 6-6=0 - MIN -= 6-= -6=- 6-6=0-6= MIM-MX 探索の高速化分岐を b, 深さを d とすると,O(b d ) のノードを展開するしかし, 良く考えると, 深さ d までのすべてのノードを展開する必要は必ずしもない高速化 (I) ノードに行ったら MX プレイヤの勝ち MIN プレイヤはに行く手は選ばないの他の子ノードは展開する必要はない高速化 (II) に行くと,MIN プレイヤの勝ち MX プレイヤはに行くパスは選ばないの他の子ノードは展開する必要がない高速化手法の一般化 ( アルファベータ探索 ) 各ノードの評価値の下界値 ( それ未満には絶対ならない値 ), 上界値 ( それより大きくは絶対ならない値 ) を管理する下界値を α 値, 上界値を β 値と呼ぶ親が MX, 子が MIN の場合 : 子ノードの評価値が親の下界値以下となることが分かったら, その子ノードに関する探索は打ち切って良い親は MX, この子ノードは選ばれない親が MIN, 子が MX の場合 : 子ノードの評価値が親の上界値以上になることが分かったら, 子ノードに関する探索は打ち切って良い親は MIN, この子ノードは選ばれない

5 3 具体例 (β カット ) の評価値がであることが分かった時点で,MIN ノードに関して, αβ()=(-, ) の一つの子ノードの評価値が, よって, αβ()= (, ) > なので, に関する探索は打ち切ってよい 3 具体例 (α カット ) の評価値がであることが分かった時点で,MX ノードに関して, αβ()=(, ) の一つの子ノードの評価値が, よって, αβ()= (, ) < なので, に関する探索は打ち切ってよい 6 具体例 ( 深い β カット ) αβ()=(-, 3) であったとする 3 はの祖先から得られた情報の最初の子供をチェックした時点でαβ()=(, 3) ここでに関する探索は打ち切られる具体例 ( 深い α カット ) αβ()=(, + ) であったとするはの祖先から得られた情報の最初の子供をチェックした時点で αβ()=(, ) ここでに関する探索は打ち切られる具体的なアルゴリズム関数 Vmax(n, α,β) を定義する.n はノード,α,β はそれぞれ下界値, 上界値, この関数はノード n の評価値を返す. ルートの MX ノード r に関して, Vmax(r, -, + ) を実行すると n の評価値が得られる. 7 関数の ( 再帰的な ) 定義 Vmax(n, α,β). If n が端点 then return 静的評価関数の値 else set n k for each child n, n,..., n b. set α=max(α,vmin(n k, α,β)) 3. If α β,return β. If k=b, return α,otherwise, goto step. Vmin(n, α,β). If n が端点 then return 静的評価関数の値 else set n k for each child n, n,..., n b. set β=min(β,vmax(n k, α,β)) 3. If β α,return α. If k=b, return β,otherwise, goto step. 8

6 9 0 例題 : アルファベータ探索アルファベータ探索で探索されるノードはどれか? 答えアルファベータ探索の効果ノードを展開する順序に依存する MXノードに関しては, なるべく大きな評価値となる子ノード,MINノードに関しては, なるべく小さな評価値となる子ノードから展開する方が良い運が悪いと展開するノード数はミニマックス探索と同じ ( ぜんぜん枝刈りができない ) アルファベータ探索の効果運が良ければ, 深さd, 分岐 bとして, 探索される端点の個数は MIN-MX: b d アルファベータ : b d/ - 効果は莫大であることに注意 b=として, = =6 8 =6 6 =636 3 =

Microsoft PowerPoint - 計算機科学入門2014.pptx

Microsoft PowerPoint - 計算機科学入門2014.pptx 第三回計算機科学入門 ( アプリケーション ) 九州大学大学院システム情報科学研究院情報学部門横尾真 E-mail: yokoo@inf.kyushu-u.ac.jp http://agent.inf.kyushu-u.ac.jp/~yokoo/ 小テストの予定来週 (/) は小テスト内容 :. 制約充足問題を解く. 問題の表現方法は与えられており, 解法はバックトラック.. ある問題を制約充足問題として定式化し,