人工知能入門 -探索による人工知能Lecture 12 敵対探索：Alpha-beta枝刈りと評価関数 http://www2.teu.ac.jp/gamelab/LECTURES/ArtificialIntelligence/index.html 1 合理的エージェントこれの設計方法は？センサ知覚 ? エージェント環境動作エフェクタ 2 競合の環境知覚環境探索探索探索エージェント探索探索動作 3 ゲームの中の敵対探索ゲームが持っている抽象性は興味深い研究対象ゲームの状態は表現が容易かなり少数の動作しかできないようになっている競合的な環境の理想モデル 4 二人ゲームにおける完全な決定二人でプレイするゲームの一般的な場合二人をそれぞれをMAXとMINと呼ぶ MAXが先手ゲームが終わるまで交互に指し続けるゲームが終わったときにある得点が勝者に与えられるゲームの問題定式化初期状態：盤面の状態とどちらの手番かの指示オペレータ：プレイヤーが指すことのできる合法手を定義する終端テスト：ゲームの終了を決定する効用関数（報酬関数）：ゲームの結果を数値として与える 5 Min-max探索 A1 A11 A12 3 12 A13 A3 A2 A21 A23 A22 8 2 4 6 A31 A32 14 A33 5 2 6 Alpha-beta枝刈り Min-max探索と同じ結果が早く終わるアイデア：最終結果に関係ないノードを「刈る」 7 Min-max探索 A1 A11 A12 3 12 A13 A3 A2 A21 A23 A22 8 2 4 6 A31 A32 14 A33 5 2 8 Alpha-beta枝刈り A1 ≤2 3 A11 A12 3 12 A3 A2 A13 8 2 A21 A31 A32 2 14 A33 5 2 9 演習問題１２－１：Alpha-beta枝刈り A1 A11 A12 A21 A24 A22 –4 5 3 A3 A2 17 A23 –5 128 A31 A32 –6 A33 5 –12 10 Alphaとbetaの違い 20 b A - a + Q 4 B 20 d c J 23 g e 20 C e b d i G 20 K 23 j k d c E F H 8 4 20 4 D c N β-cut R h a + 84 4 - S V d i o I L M T U W 25 23 54 28 4 -3 + p X -3 α-cut 11 不完全な決定 Min-max探索は無理ほとんどの場合、終端状態まですべての道筋を探索する時間がない Min-max探索を利用できる方法早めに探索を打ち切る探索木の葉に評価関数を適用する効用関数を評価関に置き換える終端テストは打ち切りテストに置き換える 12 評価関数評価関数ゲームのある局面から得ることが期待される効用の見積もり将棋の例 • 駒の価値：「歩」は１点、「金」は６点、「飛」は10点 • 他の特徴：「玉の安全度」などゲームプログラムの性能が評価関数の質に極めて存在している終端ノードに対して効用関数と合致していなければならないあまり長い時間かかってはいけない実際に勝つ可能性を正確に反映していなければならない • 同じ勝つ可能性がある局面は同じ評価になる 13 演習問題１２－２：五目並べの評価関数演習問題：五目並べの評価関数には何が必要かを討論してください 14 まとめ Alpha-beta枝刈り Min-max探索と同じ結果が早く終わる最終結果に関係ないノードを「刈る」 α枝刈りとβ枝刈りの2種類がある評価関数終端状態まですべての道筋を探索する時間がない途中で探索を打ち切って、効用関数の変わりに評価関数を利用ゲームのある局面から得ることが期待される効用の見積もり 15 ミニテストについて明日の朝は3回目のミニテストを行う持ち込み可遅刻しないように内容：ヒューリスティック探索と敵対探索（第9回～第12回） 16 最終日についてのお願い五目並べの大会をスムーズに実施するためにフラッシュメモリを持ってきて下さい 17