人工知能入門
-探索による人工知能-

早稲田大学
メディアネットワークセンター

お知らせ

最終レポートについて
- 最終レポート：WasedaFinal2011.pdf．
- 最終成績の7割になるので必ず提出してください．
- 提出期限：8月21日（日）
- 提出方法：メール（grimbergen＠cs.teu.ac.jp)

五目並べのプログラム

実行ファイル

Min-max探索
Alpha-beta枝刈り
大会用のプログラム例

プログラムソース

五目並べのプログラム例

学期曜日と使用教室

前期、木曜日14：45～16：15（４時限）、２４号館Ｅルーム

配当年次

１年以上

講師

Reijer Grimbergen
東京工科大学、コンピュータサイエンス学部

授業概要

人工知能研究の中に人間の問題解決をモデル化するために「探索」は最も一般的な方法である．「探索」というのは現在の状態（スタート）から目的（ゴール）を満たしている状態までの行動系列を作成することである．その行動系列があれば現在の状態から目標を満たすためにどの行動を実行すれば良いかが分かる．

はじめに、パズル等の解決したい問題を探索のために定式化する方法を学び、盲目探索とヒューリスティック探索という主な探索方法を解説し、解の探索をどのようにすれば効率よく行えるかについて述べる．

後半は、「五目並べ」というゲームを利用して、ゲーム木の探索を解説する．ミニマックス探索、アルファベータ枝刈りなどの一般的なゲーム木探索の方法を紹介し、実際に五目並べのプログラムを作りながらゲーム木探索を学ぶ．最後に、作成したプログラムの「五目並べ大会」を行う．

授業目的

１）簡単の問題を探索のために定式化する方法を理解すること．
２）盲目探索とヒューリスティック探索の方法を理解すること．
３）実際のボードゲームの探索方法を理解すること．

教科書

資料を配布する

参考書

Russel and Norvig, Artificial Intelligence: a Modern Approach, Prentice Hall, 1995

成績評価方法

ミニテスト（3回、60点），五目並べ大会の結果（20点）、プログラムの内容（20点）を合計し100点満点で判定する．単位認定は60点以上とする．

備考

本講義で説明する五目並べのプログラムはC言語で書かれたものである．自分で細かいプログラミングしなくても単位取れる講義だが、講義の内容を深く理解するためにプログラミングの講義・演習を4単位以上を取得していることが望ましい．

授業計画

[第 1回] 人工知能と問題解決
[第 2回] 問題定式化：問題について
[第 3回] 問題定式化：最適解
[第 4回] 問題定式化：応用例
[第 5回] 探索：行為系列の生成
[第 6回] 盲目探索：幅優先探索
[第 7回] 均一コスト探索と深さ優先探索
[第 8回] 深さ制限探索と反復深化探索
[第 9回] ヒューリスティック探索：欲張り探索
[第10回] ヒューリスティック探索：A*探索
[第11回] 五目並べプログラム：人間同士
[第12回] 五目並べプログラム：1手探索（局面の評価）
[第13回] 五目並べプログラム：Min-max探索、Alpha-beta枝刈り
[第14回] 五目並べプログラム：大会用のプログラムについて
[第15回] 五目並べプログラム：五目並べ大会

人工知能入門-探索による人工知能-

早稲田大学 メディアネットワークセンター