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

Size: px

Start display at page:

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

かねろうさくいし
5 years ago
Views:

1 第三回計算機科学入門 ( アプリケーション ) 九州大学大学院システム情報科学研究院情報学部門横尾真 yokoo@inf.kyushu-u.ac.jp 小テストの予定来週 (/) は小テスト内容 :. 制約充足問題を解く. 問題の表現方法は与えられており, 解法はバックトラック.. ある問題を制約充足問題として定式化し, 解を求める. 解法は任意. 3. 簡単なゲームに関して, 必勝法を求めるゲーム木探索コンピュータが知能を持つ / 知的な振る舞いをするとはどういうことか? 一つの候補として, チェス等の ( 知的な ) ゲームで人間を負かすことができれば, コンピュータは十分知的になったと考えることができるゲーム木の探索 : 人工知能の基礎的な分野例題二人で交代に, から順にまでの数を言う. 言う数の個数は, 個, 個,3 個のいずれか好きなのを選んでよい最後にを言った方が負け 8 8 必勝法を言って, 相手に順番を回せば絶対勝ち一方,0 を言って, 相手に順番を回せば, 相手が何個を選んでも, 次にを言える --- 絶対勝ち同様に,6 を言って, 相手に回せば次に 0 を言える --- 絶対勝ち同様に,, 8, を言って回せば勝ち先手が何を言おうと, 後手はを言って回せる結局, 後手が必勝このゲームの性質二人で交代に順番が回ってくる自分の前の相手の行動 / 手は完全に観測できる偶然の入る余地がない多くのゲームは同様な性質を持つチェス, 将棋, オセロ, 囲碁, 五目並べ,etc. 上記の性質を満たさないものバックギャモン : さいころポーカー : 相手の手は見えないブリッジ : プレイヤの協調 86 87

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

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

4 ゲーム木の評価 (MIN-MAX 法 ) 途中の状態に関して, その良さを評価する関数を作る ( 静的評価関数 ) 評価関数は数値を返す ( 大きいほうが良い ) チェス / 将棋 : 所有するコマの数 / 価値, 配置等オセロ : コマの数, 位置 ( スミ, 端 ) ( ゲームが終了している訳ではない ) 端点の評価値を, 静的評価関数の値とする他のノードの評価値を, 必勝法を決める方法と同様にして決める (MAX ノードは最大値,MIN ノードは最小値 ) ルートの MAX ノードで, 最大値を与える経路を選ぶ tic-tac-too ( 三目並べ ) で, まだ自分が取れる可能性のある列の数ー相手が取れる可能性のある列の数静的評価関数の例 MIN - MAX 6-= -=0 6-= -=0 -=- -6=- MIN 6-6=0 - MIN -= 6-= -6=- 6-6=0-6= 先読みの効果 ( とりあえずの ) まとめ基本的には, 深く読めば読むほど強い終盤の方が静的評価関数の値が信用できる先読みの深さが一定の場合の問題点 : 水平線効果将来の損失が明らかな場合に, 本質的でない先延ばしの手を選んでしまう可能性がある» ほぼ負けが決定の状態で, 無意味な王手を繰り返す» 頭を砂に埋めるダチョウみたいなもの 0 二人, 完全情報, 決定的ゲームはゲームの木で記述される原理的には先手必勝 / 後手必勝 / 引き分けゲーム木を完全に展開すれば分かる完全に展開できない場合は, 静的評価関数を用いて, 一定の先読みで MIN- MAX 法を用いる 03 ゲームプログラムの歴史 () ゲームプログラムの歴史 () ゲームをプレイするプログラムの作成は, 人工知能の fruit fly ( ショウジョウバエ ) と呼ばれていた. 90 年 Shannon, Turing がコンピュータチェスの可能性を示す論文 90 年代初めてチェスを指すプログラムが作成される 90 年代 Herbert Simon が 0 年で世界チャンピオンに勝つと予想 960 年代哲学者のヒューバートドレイファスがチェスのプログラムは永久に世界チャンピオンに勝てないと予想 960 年代 Arthur Samuel のチェッカープログラム静的評価関数の学習 ( 強化学習の一種 ) 強い! 0 0

5 ゲームプログラムの歴史 (3) 980 年代チェス専用コンピュータスーパーコンピュータ Deep Thought CMU 秒間に70 万局面人間のベスト00に到達 Deep Blue IBMが989 年から開発を開始 990 年世界チャンピオンのカスパロフと対戦戦敗 996 年再度カスパロフと対戦 6 戦勝 3 敗分け 997 年ニューヨーク 6 戦勝敗 3 引き分け秒間に億個の状態を評価 3 分で手先読みスーパーコンピュータ +チェス専用の論理回路台将棋難しさの要因持ち駒制度» 平均分岐数の大きさ勝負の長さ静的評価関数のむずかしさ» 小駒が多い将棋 ( 続き ) 平均分岐数の多さから,MIN-MAX 法 ( 実際にはもう少し工夫したα-β 探索 ) を使うことは困難で, 従来は, あらかじめ有望な手を絞り込む手法が中心最近の強いソフト ( ボナンザ ) は, 絞込みをあまり行わないことが特徴評価関数の自動学習を頑張っているらしい宝石の分配問題設定 : A, B, C, D, E の人の海賊が,00 個の宝石を分配しようとしている A から順に, 分配方法 ( 誰がいくつ取るか ) を提案する. 提案された分配方法に対して, 提案者も含めて多数決を取る ( 同数の場合は否決とみなす ) 可決の場合は提案方法を採用, 否決の場合は, 提案者を皆で殺して, 次の順番の海賊が提案を行う仮定 : 自分は死にたくない ( 全く宝石がもらえなくても死ぬよりはまし ) よりたくさんの宝石がもらえる方が ( 他者の生死に関わらす ) うれしいもらえる宝石の数が同じなら, 大勢殺した方がうれしい A は何を提案したら生き延びて, より多くの宝石を手に入れられるか? 0 A, B, C が殺され,D が提案する場合を考える. E は D のどんな提案も反対し,D の提案は否決される E が 00 個手に入れ, 効用は (A:-, B:-, C:-, D:-, E:00+ε)

6 A, B が殺され,C が提案を行う場合を考える. E は C のどんな提案も反対する D は C のどんな提案でも受け入れる ( 自分の番になれば死ぬのは確実 ) C の提案, 俺が全部取るは,C, D の賛成で可決, 効用は (A:-, B:-, C:00+ε, D:0+ε, E:0+ε) A が殺され,B が提案を行う場合を考える. C は B のどんな提案も反対する D, E は一個もらえれば満足 (C の番になれば何ももらえない ) B の提案, 俺が 98, D, E は一個ずつは,B, D, E の賛成で可決, 効用は (A:-, B:98+ε, C:0+ε, D:+ε, E:+ε) 3 A が提案を行う場合を考える B に順番が回った場合は (A:-, B:98+ε, C:0+ε, D:+ε, E:+ε) 自分以外の二人以上の賛成が得られればよい例えば, 俺が 97, C は, D (or E) はなら, 可決された場合の利益は, (A:97, B:0, C:, D:, E:0), よって A, C, D の賛成多数で可決! A 以外が共謀すればもう少し利益を増やせるか? C の提案に D, E が共謀して反対することはない --- 絶対 E は D を裏切るよって C に回った場合の結果は安定同様に,B の提案に,C, D, E 中の少なくとも二人が共謀して反対することはないよって B に回った場合の結果は安定同様に,A の提案に B, C, D, E 中の少なくとも三人が共謀して反対することはない ( 人質を取るとかの ) 強制力がないと, 安定した共謀は成立しない 6

Microsoft PowerPoint - ゲーム理論2018.pptx

Microsoft PowerPoint - ゲーム理論2018.pptx 89 90 ゲーム理論 ( 第回ゲーム木探索 I) 九州大学大学院システム情報科学研究院情報学部門横尾真 E-mail: yokoo@inf.kyushu-u.ac.jp http://agent.inf.kyushu-u.ac.jp/~yokoo/ ゲーム木探索行動の選択が一回だけではなく交互に繰り返し生じる前の番に相手の選んだ手は分かる 9 9 例題二人で交代に, から順にまでの数を言う.