人 工 知 能 第3回 探索法 （教科書21ページ～30ページ） http://www.tbgu.ac.jp/ait/atushi/

前回の復習 人工知能と探索 前回の復習

探索手法の必要性 人工知能の対象となる問題には解法が不明な問題も含まれる 迷路 パズル ⇒ 人間なら試行錯誤して解法を探す ゲーム 前回の復習 探索手法の必要性 人工知能の対象となる問題には解法が不明な問題も含まれる 迷路 パズル ⇒ 人間なら試行錯誤して解法を探す ゲーム 探索手法とは 試行錯誤的なプログラムを実現するための手法

迷路 どの経路なら出口に出れる？ A F K P U V W X Y B G L Q R M H C D I J E T O S N 前回の復習 迷路 どの経路なら出口に出れる？ A F K P U V W X Y B G L Q R M H C D I J E T O S N 経路１ : 10 steps A → F → K → P → U　 → V → W → X → Y → T 経路２ : 12 steps A → F → K → P → Q　 → L → M → R → S → N → O → T

前回の復習 3目並べ × ○ どこに「×」を入れると 引き分ける？ 負け ○ A B C D E × ○ 引き分け F G H

前回の復習 状態空間と探索木 前回の復習

前回の復習 状態遷移図(1) 状態遷移図とは 状態を点 とした有向グラフ 行動を枝 朝 昼 夜 時間経過

状態遷移図(2) 迷路問題での状態と行動 状態 S := (sA, sB, sC, sD, … , sY) A F K P U V W X 前回の復習 状態遷移図(2) 迷路問題での状態と行動 状態 S := (sA, sB, sC, sD, … , sY) A F K P U V W X Y B G L Q R M H C D I J E T O S N 初期状態 : sA 終了状態 : sT 行動 A := (aU, aD, aL, aR) aU := 上に移動 aD := 下に移動 aL := 左に移動 aR := 右に移動

状態遷移図(3) sA sF sK sP sU sV sW sX sY sB sG sL sQ sR sM sH sC sD sI sJ 前回の復習 状態遷移図(3) sA sF sK sP sU sV sW sX sY sB sG sL sQ sR sM sH sC sD sI sJ sE sT sO sS sN aR aD aU A F K P U V W X Y B G L Q R M H C D I J E T O S N

探索木(1) 探索木の構築 初期状態をルートノードとする 遷移する可能性のある状態を子ノードとする 状態遷移図との比較 前回の復習 探索木(1) 探索木の構築 初期状態をルートノードとする 遷移する可能性のある状態を子ノードとする 状態遷移図との比較 同じ状態が複数ノードで表現される可能性がある ⇒ 大規模なグラフになりやすい ループが存在しない ⇒ 簡単なアルゴリズムで計算可能

探索木(2) A F K P U V W X Y B G L Q R M H C D I J E T O S N sO sA sF sK 前回の復習 探索木(2) A F K P U V W X Y B G L Q R M H C D I J E T O S N sO sA sF sK sP sU sV sW sX sY sB sG sL sQ sR sM sH sC sD sI sJ sE sT sS sN

知識を用いた探索法

知識を用いた探索法の概要(1) 網羅探索法との比較 深さ優先・幅優先探索 ⇒ 指標無しで探索する 探索の効率が悪い 知識を用いた探索方 ⇒ 指標を用いて探索する 探索の効率を向上させる

知識を用いた探索法の概要(2) 知識を用いた探索法の手順 次の手順を終了状態まで繰り返す 状態の評価を行う 最も高い評価の状態を探索する 状態の評価を行う ＝ 評価のための知識が必要

知識を用いた探索法の概要(3) 状態の評価例 迷路の場合 ⇒ ゴールまでの直線距離を評価値とする A F K P U V W X Y B G L Q R M H C D I J E T O S N 5 2 4 1

最良優先探索法(1) 最良優先探索法の手続き 手順1 : 未探索状態の中で最も評価がよい状態を選択 手順2 : 選択された状態にルールを全て適用し、ルール適用後の新しい状態を生成する 手順3 : 新たに生成された状態を調査 手順3a : 終了状態が含まれていれば終了 手順3b : 終了状態が無い場合、新たに生成された状態を未探索状態に加えて手順1に戻る

最良優先探索法(2) 最良優先探索法の探索手順 A F K P U V W X Y B G L Q R M H C D I J E T O S N 1 4.2 2 3.6 3 3.2 4 3.0 5 2.0 sO sA sF sK sP sU sV sW sX sY sB sG sL sQ sR sM sH sC sD sI sJ sE sT sS sN 5.0 6 4.5 7 4.1 3.6 9 3.0 10 3.2 8 4.0 11 2.2 12 2.0 13 1.0 14 1.4 15 1.0 16 4.1

A*アルゴリズム(1) A*アルゴリズムの概要 探索手順は最良優先探索法と同じ 評価値として『過去のコスト＋未来のコスト』を使う 『過去＋未来のコスト』が最小となる状態から探索する ⇒ コストが最小となる解を探索できる

A*アルゴリズム(2) A*アルゴリズムの探索手順 A F K P U V W X Y B G L Q R M H C D I J E T O S N 1 4.2 3 3.6 5 3.2 6 3.0 7 2.0 sO sA sF sK sP sU sV sW sX sY sB sG sL sQ sR sM sH sC sD sI sJ sE sT sS sN 1 2 3 4 5 5.0 2 4.5 4 4.1 1 2 3.6 6 9 3.0 11 3.2 4 5 8 4.0 12 2.2 16 2.0 17 1.0 1.4 3 6 7 8 9 10 4.1 4 13 3.2 14 2.2 15 1.4 18 1.0 19 5 6 7 8 9

山登り法(1) 山登り法の手続き 評価値のよい状態のみを探索する ⇒ 探索対象外となった状態は二度と探索しない 少ない計算量・メモリ量で探索することが可能 局所解に陥る可能性がある 評価値に変化がないと使えない

山登り法(2) 山登り法の探索手順 A F K P U V W X Y B G L Q R M H C D I J E T O S N sO 1 4.2 2 3.6 3 3.2 4 3.0 5 2.0 sO sA sF sK sP sU sV sW sX sY sB sG sL sQ sR sM sH sC sD sI sJ sE sT sS sN 5.0 4.5

ゲームプレイング

ゲーム探索の概要(1) 通常の探索との違い 自分の操作以外の不確定要素が存在する 相手の操作により状態が変化する サイコロ等により確率的に状態が変化する 不確定要素を考慮した探索をする必要がある

ゲーム探索の概要(2) 相手の存在するゲーム（三目並べ） × ○ × ○ ○ × × ○ × ○ × ○ × ○ ○ × ○ ○ × × ○ ・・・ ・・・

ゲーム探索の概要(3) 確率的に状態が変化するゲーム（人生ゲーム） 職工 となる 事務員 となる 作家 となる 経営者 となる 結婚する スタート 中学卒業 大学入学 高校卒業 職工 となる 事務員 となる 作家 となる 経営者 となる 結婚する 学生生活 給料10万 給料12万 給料14万 給料16万 給料50万 給料日 大学卒業 作家 となる 銀行員 となる 科学者 となる 公務員 となる 弁護士 となる 医者 となる 給料16万 給料20万 給料24万 給料26万 給料30万 給料40万

ミニマックス法(1) ミニマックス法の概要 相手の存在するゲームの手段を探索する 相手の行動も含めた探索木を構築し、以下の考えに従って探索する 相手の行動時には最も悪い評価となる状態を選択する 自分の行動時には最も良い評価となる状態を選択する 相手が最良の手段を講じた場合を想定して探索する

ミニマックス法(2) ミニマックス法の探索手順 3 s0 a0 a1 a2 MAXを選ぶ 3 2 2 s00 s01 s02 MINを選択 <自分> a0 a1 a2 MAXを選ぶ 3 2 2 s00 s01 s02 <相手> MINを選択 3 12 8 2 4 6 14 5 2 s000 s001 s002 s010 s011 s012 s020 s021 s022

ミニマックス法(1) ミニマックス法の探索例 × ○ × ○ × ○ × ○ × ○ max min max min -1 × ○ × ○ <相手> <自分> <相手> <自分> <相手> × ○ × ○ × ○ × ○ × ○ max min max min -1 × ○ × ○ × ○ × ○ -1 1 -1 -1 × ○ × ○ × ○ × ○ -1 1 ・・ ・・

アルファベータ法(1) アルファベータ法の概要 ミニマックス法による効率のよい探索を行うための枝刈り ⇒ 探索の必要のない枝は切り捨てる 6 <自分> s0 MAXを選ぶ a0 a1 a2 6 2 5 s00 s01 s02 <相手> MINを選択 6 12 8 2 4 6 14 5 2 s000 s001 s002 s010 s011 s012 s020 s021 s022

アルファベータ法(2) アルファベータ法を用いた探索例 × ○ × ○ × ○ × ○ × ○ max min -1 × ○ × ○ × ○ <相手> <自分> <相手> <自分> <相手> × ○ × ○ × ○ × ○ × ○ max min -1 × ○ × ○ × ○ × ○ -1 -1 × ○ × ○ × ○ × ○ ・・ ・・

期待ミニマックス法(1) 期待ミニマックス法の概要 ミニマックス法に確率の概念を加えた手法 ⇒ サイコロ等の確率的選択に対応

期待ミニマックス法(1) 期待ミニマックス法の探索手続き 5.2 s0 a0 a1 a2 MAX 4.2 5.2 2 s00 s01 s02 <自分> a0 a1 a2 MAX 4.2 5.2 2 s00 s01 s02 <Dice> 0.6 0.4 0.2 0.8 1.0 期待値 3 6 2 6 2 s000 s001 s010 s011 s020 <相手> MIN 3 12 8 6 2 4 6 14 5 2 s0000 s0001 s0010 s0011 s0100 s0101 s0110 s0111 s0200 s0201

ゲームプログラミングの現在

ゲームプログラミング(1) オセロ 探索空間は比較的狭いため、コンピュータが得意とする 1997年、世界チャンピオンがコンピュータに敗北 コンピュータは人間よりもはるかに強い チェス 探索空間が広大だが、終盤は収束するという特徴がある 1997年、世界チャンピオンがコンピュータに敗北 コンピュータはプロ上位者レベル

ゲームプログラミング(2) 将棋 探索空間は非常に広く、終盤になっても収束しない ただし、終盤のみ局地的な全探索を行うことが可能 コンピュータはプロ初段程度の実力 囲碁 探索空間は広大であり、数手先を読むのも難しい 評価関数の開発が難しいため、効率的な探索が不可能 コンピュータはアマチュア程度の実力

小テスト

課題 今日の問題（ホット6） 最初に何振りすればラーメンを食べずにすませられるか？ 2人のプレイヤーの前にラーメンと胡椒がある 交互にラーメンに胡椒を振りかけ、6回目の胡椒を振りかけたプレイヤーがそのラーメンを食べなければならない。 1人は連続して3回までしか胡椒を振りかけられない 胡椒は自分が最初に振りかける（自分→相手→自分・・）