本日のメニュー（6/12～） 人間が（あるいは人間も）行う知的処理をコンピュータ上で実現しようという研究としての人工知能について考える。

Presentation on theme: "本日のメニュー（6/12～） 人間が（あるいは人間も）行う知的処理をコンピュータ上で実現しようという研究としての人工知能について考える。"— Presentation transcript:

1 本日のメニュー（6/12～） 人間が（あるいは人間も）行う知的処理をコンピュータ上で実現しようという研究としての人工知能について考える。
人工知能は： 何を目指すか 何を実現しえたか どのような原理、方法（論）、技術に基づいているか どういう困難や問題点があるか 人間の認知研究とどのような関わりを持つか 本日は特に、数学・ゲーム・パズルについて考える 1

2 本日のキーワード 人工知能（AI） ヒューリスティックス 記号主義・ 記号処理パラダイム 計算論的認知観 人工知能の研究手法 表象主義
（エージェント） Marr の視覚理論 自然言語理解 ELIZA と SHRDLU 最近の動向 エキスパートシステムDENDRAL, MYCIN, AM, Eurisko, Cyc 数学⇒（人工知能から独立） 事例： ゲーム等 Deep Blue, あから2010、 Alpha-Go、将棋電王戦、WATSON 等 人工知能批判 強い AI と弱い AI フレーム問題

3 人工知能の現状（１） 直接的な意味での「人間の知能」の実現には至っていない。 しかし個別には様々な重要な成果がある。
ヒューマノイド・ロボット（鉄腕アトム、．．．） HAL 9000 （「2001 年宇宙の旅」） “AI”　（「攻殻機動隊」） 人間社会で暮らす人工知能 参考：　ロボットスーツ（ガンダム） そもそもそれが研究目的にはなっていない？ しかし個別には様々な重要な成果がある。 知能観のジレンマ：「人工知能は逃げ水？」 実現されてしまった機能は、もはや「知的」、「知能の実現」とはみなされなくなる傾向がある。

4 人工知能の現状（２） そもそも何をもって「人工知能」とするかは、人によっても時代によっても様々。 AI という研究分野自体が「拡散的」
研究面においても、当初は AI 研究として開始されたものが、解決手法の研究が進む、特にアルゴリズム的な扱いが可能になると AI とはみなされなくなる（AI から独立する）。 AI 研究の過程で生まれた様々な理論・言語・ツール・技術が、spin-off として情報処理技術全般に広範に使われる。 ある意味では、この面に AI の最大の成果があるかもしれない。

5 人工知能の現状（３） 人工知能研究が社会的に認知され、アカデミズムとしても確立される反面、「人工知能」としての自立性・アイデンティティ（あるいはその必要性）が弱まっている。 研究内容についても、大規模コーパスが容易に利用できるようになったことも背景にして、HMM (Hidden Markov Model) のような確率モデル的手法、統計的なパラメタ調整・学習手法によるアプローチ（SVM 等）が全盛になっている。

6 人工知能の現状（４） 人工知能の弱い面 常識的な判断・推論　　（⇒後述） 自然言語処理：　日常的な会話の実現 社会的文脈、他者との関係・協力・共同作業 感性、感情・情動 これらは認知科学の他部門との最大の接点であり、こういった面での研究が（他に比べて）進展しないことは、人工知能さらにはコンピュータ科学一般と、認知科学一般との関係が希薄になってきていることにつながっている。

7 人工知能の現状（５） 近年の様々なイベントは、人工知能に耳目を集め、また復権・再認識させるきっかけとなっている。 課題
ゲーム： 囲碁、チェス、将棋、オセロ、... WATSON (IBM) 各種ロボットの開発・発展 自動制御（オートパイロット、自動運転、ロボット掃除機、．．．） 「感性情報処理」 脳波、筋電等の生体データの直接利用 課題 どこまで「理解」しているか？ どこまで人間に近づいているか？近づく必要はあるか？ “Technological Singularity”、 “General AI” 実現するか？　どのように？　いつごろ？

8 人工知能マップ （未完成） 確定要因 人間の認知 問題解決 不確定要因 （機械学習） deep learning等 ゲーム・パズル 数学
人工知能マップ 　（未完成） 確定要因 ゲーム・パズル 数学 データマイニング (VR・AR) 行動計画 画像認識 人間の認知 情報検索 問題解決 自然科学 文字認識 音声認識 入試問題 常識・推論 ロボット 自然言語理解 対話システム 自動運転 感性情報処理 脳波・筋電利用 芸術（音楽・文学等） 不確定要因

9 人工知能の成果（１）： 数学 数式処理（計算機代数）
人工知能の成果（１）：　数学 数式処理（計算機代数） Slagle の SAINT（大学初年級の積分） 　　　　　　　　　　 この当時では AI 研究の代表例だったが、アルゴリズムベースの数式処理研究が進み、AI とは一線を画する。 現在では Macsyma, Reduce, Mathematica, Maple などのシステムは科学技術領域における不可欠のツールになっている。 単純な計算問題はできても、複合問題、応用問題は解けるか？　（cf. 東ロボ君（東大入試）） 数学を「作れる」か？　(cf. Lenat の AM)

10 人工知能の成果（２）： ゲーム （参考： 2012年度のスライド）
人工知能の成果（２）：　ゲーム 　　　　　　（参考：　2012年度のスライド） ゲーム（知能ゲーム、特に２人ゼロ和有限確定完全情報ゲーム） チェッカーズ 世界チャンピオンクラス、ゲームそのものがほぼ「解決」 （Chinook: 2007） オセロ 世界チャンピオンクラス（Logistello 1997） チェス 世界チャンピオンクラス（DeepBlue, ） 将棋 アマチュア高段、さらにはプロレベルに接近 詰将棋は専門家レベル（以上？）　　　　→あから2010 等 囲碁 アマ初段～有段程度　（モンテカルロ法により急進）

11 人工知能の成果（２）：ゲーム (2018) ゲーム（知能ゲーム、特に２人ゼロ和有限確定完全情報ゲーム） 詳しくは後のスライドで
人工知能の成果（２）：ゲーム　(2018) ゲーム（知能ゲーム、特に２人ゼロ和有限確定完全情報ゲーム） チェッカーズ　世界チャンピオンクラス、ゲームそのものがほぼ 「解決」（Chinook: 2007） オセロ　世界チャンピオンクラス（Logistello 1997） チェス　世界チャンピオンクラス（DeepBlue, ） 将棋　プロレベル（公式対戦ではプロはほとんど勝てない） 囲碁　プロレベル？プロを超えた？ Deep Learning 採用による AlphaGo, 絶芸、Zen などのシステムが 2016～2017 に（突如）台頭 詳しくは後のスライドで

12 人工知能の成果（３）： 応用（１） カーナビ、道案内システム 情報検索（Web ページ検索等） 状態空間探索の典型的問題
人工知能の成果（３）：　応用（１） カーナビ、道案内システム 状態空間探索の典型的問題 一般には探索空間が巨大なため、全探索（最適解）は不可能 ほとんどの場合、実用的には十分高い水準にある。 ⇒　自動運転システムへ 情報検索（Web ページ検索等） テキストの検索手法、索引語抽出手法、検索結果の順位付け、類似語の推定など

13 人工知能の成果（４）：視覚・聴覚 視覚・聴覚関係 文字認識 音声認識 画像理解・解析 音声合成 音楽認知・分析、作成
初期の重要な成果は郵便番号読み取り機 現在では Windows の IME パッドをはじめ、標準的なツールになっている。 音声認識 画像理解・解析 音声合成 自然な発話・発音 音楽認知・分析、作成

14 人工知能の成果（５）：自然言語 人間との情報交換・意思疎通の根幹 人工知能研究のあらゆる場面に関係する 処理手法も多様
音声入力、文字入力インタフェース 対話システム 機械翻訳 人間による膨大な資料の収集、分析、記録 ．．．．．．． 処理手法も多様 単に言語だけでなく、背景知識、常識なども関係する 見かけでは理解できているようにみせかけるのも比較的容易 （あとの資料も参照）

15 人工知能の成果（６）：応用（２） 科学技術関係 Spin-off 技術
エキスパートシステム DENDRAL による化合物についての新発見など、様々な成果がある。 Spin-off 技術 プログラミング言語（Lisp, Prolog, ...） プログラミングパラダイム（関数型・論理型プログラミング、オブジェクト指向、エージェントプログラミング、...） TSS システム（時分割処理システム）、対話型処理

16 人工知能の成果（７）：認知モデル 人間の認知について何がわかったか 認知アーキテクチャ（認知過程の計算的モデル）
ある意味、「最大の成果」は、人間の認知がいかに複雑な情報処理過程であるかを（再）認識させられたこと。 認知アーキテクチャ（認知過程の計算的モデル） EPAM (Feigenbaum), GPS (Newell & Simon), ACT (Anderson), SOAR (Newell), ... 多くの認知モデルが作成されているが、人間が実際に行っている処理過程をそのまま反映している保証はない。　⇒　「メタファ」としてのモデル

17 人工知能の成果（８）：一般知識 WATSON http://www-03.ibm.com/innovation/us/watson/
常識推論、一般的な質疑応答システム Cyc, OpenCyc (1984～) Open Mind Common Sense, ConceptNet 　　(1999～) …. WATSON 2011年、クイズ番組 Jeopardy! で人間のクイズ王と対戦し、総合優勝した。 現在では IBM の汎用サービスとして実用化されている。

18 人工知能の成果（９）： 学習 記号的な学習・類推 パラメタ学習（機械学習） 記号的に表された知識構造や概念の帰納的な学習・獲得。
人工知能の成果（９）：　学習 記号的な学習・類推 記号的に表された知識構造や概念の帰納的な学習・獲得。 初期の例：　Evans の類推プログラム、Winston の学習研究など。 パラメタ学習（機械学習） 状態を表す数値的なパラメタを操作して学習・最適化を行う。 パーセプトロン、ニューラルネットワーク 最近では数値的な機械学習手法が基礎技術として広範に応用されている。（データ検索、マイニング、自然言語処理、パターン認識、ゲーム等々　cf. deep learning

19 人工知能の成果（１０）： 適応 Subsumption Architecture (Brooks, 1986～)
人工知能の成果（１０）：　適応 Subsumption Architecture (Brooks, 1986～) 虫や小動物の行動などを例に、認知的行動はトップダウンの、合目的的な行動計画によってではなく、動作単位（モジュール）の適応的動作によりボトムアップに形成されるという立場。 ロボットの行動形成などで成果を上げた。 （参考：　掃除機ロボット） 認知一般にまで適用しうるかについては難しそう。

20 人工知能の成果（１１）： 感情 人間の感情・情動のモデル化 人間に対する感情・情動面での対応 今後は様々なアプリケーションが登場する？
人工知能の成果（１１）：　感情 人間の感情・情動のモデル化 記述的なモデル 何を原理と考えるか？（アージ理論（戸田）等） 人間に対する感情・情動面での対応 「癒しロボット」　（パロ等） （とりとめのない）対話を行うシステム 起源は 60年代の ELIZA/DOCTOR 感情移入型ゲーム、そこでの対話システム 人間の感覚・感情の喚起・拡張（VR, AR システム） 今後は様々なアプリケーションが登場する？

21 人工知能の成果（１２）： 日本の例 カナ漢字変換は日本の人工知能研究の重要な成果と評価されている（「第5世代レポート」等）。
人工知能の成果（１２）：　日本の例 カナ漢字変換は日本の人工知能研究の重要な成果と評価されている（「第5世代レポート」等）。 コンピュータ将棋 ロボット関連諸技術（各種ロボット（産業用、ヒューマノイド型、愛玩用（AIBO、パロ）、．．．） 歌唱分析・合成 Vocaloid　（初音ミクシリーズ等） 様々な分野で成果は上がっている　（が、世界全体にインパクトをもたらすにはまだ至っていない）

22 Technological Singularity
用語は Stanislaw Ulam, 提唱者： Verner Vinge, Ray Kurzweil 等 背景：　コンピュータの知的能力がどんどん増大している（ここ数年特に顕著）。 機械が人間を「追い越したら」どうなるか？ そもそも追い越すか？追い越せるか？ 追い越したら、その後の「発展」はもはや予測や追随が不能になる？（本来の意味） 人間は不用になる？機械が人間を支配する？倫理的問題、等々 （これらは世俗的・曲解的理解） 参考：　人工知能学会は人工知能の倫理綱領制定に着手 （2016/6。　参考：ロボット３原則（アシモフ））

23 人工知能は何を実現すべきか 正確で公平な判断 間違えたり、対象外であった場合の対処 説明力を持つ
「フレーム問題 (Frame problem)」 破綻（Breakdown）を生じさせない 正常・妥当に対処できているかの判断（メタ判断） 説明力を持つ 自分の動作、判断の根拠を（人間に）説明できる Expert System が目指したこと 学習ベースシステムでは極めて難しい

24 参考：　フレーム問題 McCarthy & Hayes: Some Philosophical Problems from the Standpoint of Artificial Intelligence, Machine Intelligence 4 (1969) 外界（実世界）で活動する人工知能が、判断・行動計画に必要なすべての情報を入手しうるかの問題 もちろん原理的には不可能⇒行動できない？ どこで必要な情報取得を打ち切るか 人間はどうやっているか （先例・「常識」の利用等）

25 数学・ゲーム・パズル （問題解決型課題） 数学・ゲーム・パズルと認知 数式処理 ゲームプログラミングの基本 ゲームプログラムの現状
状態空間と探索 ゲーム木とその探索（mini-max 探索） ゲームプログラムの現状 コンピュータ将棋 コンピュータ囲碁

26 人工知能の要： Heuristics（再掲）
Heuristics （発見的手法） ⇔ algorithm アルゴリズム 問題解決のための機械的に実行可能な処理手順がある。 その手順には十分な一般性がある。 問題のパラメタを変えることで、他の場合にも適用できる。 処理のための時間・手間を問わなければ、有限時間内で必ず解決できることが保証されている（「解がない」ことが示される場合も含む）。

27 人工知能の要： Heuristics(2) ヒューリスティックス（発見的手法） 人間の場合：思いつき、発想、ひらめき等に相当？
問題に応じて個別的に「発見」、開発されるような解決手法。 いつでもうまくいく保証は（必ずしも）ない。 アルゴリズムが存在しない場合（知られていない場合）、存在しても実用的な価値がない場合などに適用される。 問題の解決法自体を探し出すことを含んで言う場合もある（メタ解決）。 人間の場合：思いつき、発想、ひらめき等に相当？ 人間でも行き当たりばったりではなく、有望な道筋を組織的に考えているはず

28 数学（数式処理・記号的計算） 微分、積分、方程式の解、式の整理（因数分解等）
個々の問題（特に文章題）の解決はまた別の話（自然言語理解、定式化・立式などが必要になる） 記号的な微分と積分とでは大きな違いがある 微分：　アルゴリズム化できる 積分：　（初期の／人間的アプローチでは）ヒューリスティックが必要 一番難しいのは式の整理（因数分解等） 方程式（連立・非線形方程式、微分方程式）も一般には解けない（アルゴリズム化できない）

29 記号微分 微分公式をルールとして定式化 公式の機械的適用により、「より簡単な式の微分」に還元できる プログラムで数十行あれば書ける
個別関数の公式 (xn, ex, log, sin/cos, ...) 一般公式（加減乗除、べき乗、合成関数、逆関数） 公式の機械的適用により、「より簡単な式の微分」に還元できる 合成関数の微分公式（変数変換）に相当する計算も、ヒューリスティックに依らずに機械的に適用できる 公式の範囲（初等関数等）ならこれですべてできる プログラムで数十行あれば書ける 結果を整理して見やすくするのは別問題

30 記号積分 記号微分と同様、公式を用意するのだが、アルゴリズミックにはいかない（ヒューリスティックが必要、そもそも（考えている関数の範囲では）解けない等） 置換積分（変数変換）、部分積分を適用の場合 Slagle のSAINT も適用のヒューリスティックを探るのがポイント 現在では、初等関数の積分等は（かなり）アルゴリズム化されている (eg.Risch Algorithm) ただし完全にインプリメントされているわけではない 初等関数の範囲で積分可能かの判定可能 人間の解法からはかなりかけ離れている

31 人工知能の成果（１）：ゲーム（再掲） ゲーム（知能ゲーム、特に２人ゼロ和有限確定完全情報ゲーム）
チェッカーズ　世界チャンピオンクラス、ゲームそのものがほぼ 「解決」（Chinook: 2007） オセロ　世界チャンピオンクラス（Logistello 1997） チェス　世界チャンピオンクラス（DeepBlue, ） 将棋　プロレベル（公式対戦ではプロはほとんど勝てない） 囲碁　プロレベル？プロを超えた？ Deep Learning 採用による AlphaGo, 絶芸、DeepZenGo などのシステムが 2016～2017 に（突如）台頭

32 ゲームの複雑さ ゲーム 盤面数 ゲーム木 チェッカーズ 1018 1031 オセロ 1028 1058 チェス 1050 10123 将棋
1071 10226 囲碁 10172 10360 Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 　　他

33

34 コンピュータ将棋（１） 基本は評価関数を用いたゲーム木探索 しかしコンピュータの高性能化、多重並列化などにより性能そのものが大幅アップ
第3回電王戦５局の GPS 将棋は 700近いマシンによる並列処理 定跡的な手順のデータベース化 またプロ棋士の棋譜等による学習を本格的に利用 譜例が少ないと役に立たない（入玉戦など） Deep Learning 等の採用（自己対戦による強化）

35 コンピュータ将棋（２） プロ棋士（女流棋士）との公式対戦 あから 2010 対清水（女流棋士）：コンピュータ勝利
将棋電王戦（１）　2012 対米長（元名人：引退棋士）：コンピュータ勝利 将棋電王戦（２）　2013 ５戦の「団体戦」：コンピュータ側の３勝１敗１分 将棋電王戦（３）　2014 コンピュータ側の４勝１敗 将棋電王戦（４）　2015 コンピュータ側の２勝３敗 将棋電王戦（再編１期）　2016 ponanza 2-0 山崎隆之八段　（来年から羽生も参戦？）

36 コンピュータ将棋（３） （第２回電王戦） 観戦記などによれば、人間側の優劣判断とコンピュータ側の優劣判断とは食い違っている。
プロ棋譜データに基づいているにも関わらず、なぜ違いが生じたのか？ コンピュータは新しい「戦略」を見出している？ 疲労・思いこみなどの「人間的」要因 第４戦の引き分けは、コンピュータ必勝の状況を入玉戦に持ち込まれたため。

37 コンピュータ将棋（４） 第3回電王戦（2014） 電王戦 FINAL（2015） 新制第１期電王戦（2016） 第２期電王戦 (2017)
クラスタを使用せず、同一スペックのマシンで対戦 それでもコンピュータ側が4勝1敗 電王戦 FINAL（2015） 人間側が3勝2敗と勝ち越し 新制第１期電王戦（2016） ponanza 2-0 山崎隆之八段 第２期電王戦 (2017) ponanza　2-0　佐藤天彦　叡王（名人）

38 コンピュータ将棋（５） 「ソフト指し問題」 (2016) 今後はどうなる？ 三浦八段が、対局中に将棋ソフトを使ったという疑惑
「ソフト指し問題」　(2016) 三浦八段が、対局中に将棋ソフトを使ったという疑惑 当初、出場停止処分を受けたが、その後の第３者委員会判定で取り消し。 今後はどうなる？ コンピュータがプロレベルに達しているのは間違いない。 人間を超えたか？ 現時点ではまだ断定はできない。が、超えたかもしれない 情報処理学会は「コンピュータ将棋プロジェクト」終結を宣言 人間側の「巻き返し」、新しいタイプの戦略・作戦の登場？ 人間に学べることは？ 人間が学べることは？ （プロ棋士でもツールとして使う人は多い）

39 コンピュータ囲碁（１） 2010 年ぐらいまでは、人間と比べて勝負にならなかった（アマチュア有段程度）
2006 年頃から、Monte Carlo Search 及びその応用である UCT により、急速に強くなった （CrazyStone 等） 2015 年に登場した AlphaGo (DeepMind 社）は Deep Learning を採用し、人間のプロを連破した。また絶芸（中国）、DeepZenGo（日本）などもやはり人間のプロ（以上）の強さを見せている。

40 コンピュータ囲碁（２） AlphaGo DeepMind 社が開発（2010 英、Google 傘下） Monte Carlo Search, Deep Learning に基づく （value network, policy network の併用） AlphaGo とプロ棋士との対戦 2015 年、Fan Hui（二段）に 5-0 2016 年、李世乭（イ・セドル：韓）に 4-1 2017 年、柯潔（カ・ケツ：中）に 3-0 「人間との対局はこれが最後」との宣言

41 コンピュータ囲碁（３） 絶芸（Fine Art, Tencent 社：中国）、DeepZenGo （日本）なども、AlphaGo ほどではないが、高いレベルを有している。 絶芸は UEC コンピュータ囲碁大会 2017 で優勝、DeepZenGo は２位 その後の電聖戦でともに一力遼七段に勝利 絶芸は　AlphaGo に非公式戦で勝った（？）

42 コンピュータ将棋・囲碁 なぜ強いか？ なぜ急に強くなったか？ 将棋における強さと囲碁における強さとは異質に感じられる
なぜ強いか？　なぜ急に強くなったか？ よくわからない。予想をはるかに上回る向上振り（特に囲碁） 将棋における強さと囲碁における強さとは異質に感じられる 将棋は理詰めのゲームであり、定跡・戦略もよく研究されている その理詰めの探究で負けている？ 囲碁は感覚的な面も多いし、プロ棋士でも盤面全体を一体で把握しえているわけではない（後述の「数独」の項参照） しかしコンピュータはそれができている可能性がある ⇒　そうだとすると、本当に人間より強いかもしれない

43 コンピュータ将棋・囲碁（文献） Wikipedia の項参照（コンピュータ囲碁の日本語版は少し古い： Computer Go (en) 参照） 文献等は授業ページでも案内する。 コンピュータ囲碁関係 伊藤・村松：ディープラーニングを用いたコンピュータ囲碁：情報処理学会誌 vol.57 no , 2016） D. Silver et al. “Mastering the game of Go with deep neural networks and tree search”, Nature, vol.529, 2016, doi: /nature16961.

44 ゲーム・パズルの基本事項 以下ではゲームやパズルに取り組んだり、プログラミングをする場合の基本的な事項を記す。
それ自体がそのまま人工知能というわけではないが、本格的な AI プログラムにつながる基礎となる。

45 パズル・ゲームの解法（原理） 問題の表現 解法の大分類 制約条件（パズルのルール等）の定式化 問題（盤面等）の表現形式の定式化
個別の問題の表現 解法の大分類 探索（状態空間探索）　　仮定法（trial & error） 制約伝播　　　　　　　　　 候補の「絞り込み」

46 例題：川渡り問題 問題 旅人 (T)、狼(W)、ヤギ(G)、キャベツ(C) が旅をしていて川に行き着いた。川には渡し舟が1艘あり、一度に乗れるのは TWGC のうちの２つまでで、操船は T にしかできない（つまり T は必ず舟に乗らなければならない）。 全員が川を渡るにはどうすればいいか。 制約：　旅人 T がいないとき、 狼、ヤギ（W, G ）だけだと狼がヤギを食べてしまう。 ヤギ、キャベツ（G, C） だけだとヤギがキャベツを食べてしまう。 （したがって無事なのは W, C の組み合わせだけ）

47 状態空間 state space 状態： 問題解決途中の場面・状況。 それを表すデータ表現（知識表現）
状態：　問題解決途中の場面・状況。 それを表すデータ表現（知識表現） 初期状態：　問題で与えられた最初の状態。 目標状態：　問題が「解決された」状態。 一般には１つとは限らないし、具体的にわからない場合もある。 複数の解がある 解がない 具体的な目標状態が不明（ゲームの終了盤面など） 操作：　１つの状態から別の状態に移動するための処理

48 状態空間（２） state space 制約・ルール 状態や操作についての制限。
可能な状態、不可能な（違法な）状態 可能な操作 状態空間：　状態をノード、操作（による移動）をリンクで表したグラフ構造。 問題解決：　状態空間中で、初期状態から出発して目標状態に至る経路を示すこと（状態空間探索）。 目標状態・経路が複数ある場合： 解を１つ求めればよい、すべての解を求める、最善の解を求める。 目標状態が存在しない場合

49 状態空間（３） 状態の個数： 有限個、無限個 状態が事前に展開できる場合
状態の個数：　有限個、無限個 状態が事前に展開できる場合 状態数が有限ですべて特定可能 個数がそれほど多くない。 そうでない場合は、到達可能な状態を探索とともに展開していくことになる。

50 状態空間探索（１） 前方探索 （forward search） 初期状態から出発し、可能なリンクをたどって目標状態に至る経路を見出す。
同じ状態を何度も調べないことが重要。 後方探索 （backward search） 目標状態から出発して初期状態に至る。 一般にこちらのほうが効率がいいことが多いが、目標状態が具体的にわからなければ使えない。 発見的探索 (heuristic search) ムダな探索経路をできるだけ探さないで済ませる。

51 状態空間探索（２） 縦型探索（深さ優先探索、depth-first search）
ある経路をたどれるだけたどる。 記憶効率がよい、無限経路にはまると帰れない。 横型探索（広さ優先探索、breadth-first search） 初期状態から近いノードの順に探索する。 記憶効率は悪いが、解があれば確実に見つかる。 最良優先探索（best-first search） 「見込みの高い」経路から順に探す。 ヒューリスティックな探索法 単純な探索とは異なるアプローチもある。（制約充足等）

52 川渡り問題の状態表現（１） 川の左岸・右岸に TWGC のどれがいるかが状態になる。
（渡っている途中の状態（船上にあるとき）は考えなくてよい。） 実際には左岸・右岸の一方だけでよい。 初期状態：　　　　　目標状態： 最初に TG が渡った後：　 T W G C T W G C W C T G

53 川渡り問題の状態表現（２） 状態の総数： T, W, G, C が左右どちらかの岸にあるから、 24 = 16 通り
禁止状態：　T のいない側に WG, GC の組み合わせがある。 これが右の６通り 可能な状態数： 16 – 6 = 10 通り W G C T W G T C G C T W T W G C T C W G T W G C

54 制約伝播 (Constraint Propagation)
問題を構成するグラフ（状態空間とは違う）の各ノードでは、一般にとりうる値の複数の候補がある。 ノード間の関係によって、実現可能な値、実現不可能な値が生じる。 実現不可能な値を取り除いていくと、その影響が他のノードにも波及していく。 「制約充足」などとも言う。

55 制約伝播： 例 覆面算等、各種パズル 線画のラベリング (D. Waltz) 時系列、スケジューリング パズルサイト
制約伝播：　例 覆面算等、各種パズル パズルサイト ニコリ： パズルジャパン：　 人間がパズルを解くとき、探索的方法（仮定法）ではなく、制約充足的方法が中心 線画のラベリング (D. Waltz) 時系列、スケジューリング

56 ＳＥＮＤ ＋ ＭＯＲＥ ＭＯＮＥＹ 例題：覆面算 ルール 正しい式になるように各文字に 0-9 の数字を 割り当てる。
　 ＳＥＮＤ ＋ ＭＯＲＥ ＭＯＮＥＹ ルール 正しい式になるように各文字に 0-9 の数字を　割り当てる。 同じ文字には同じ数字が入る。 異なる文字には異なる数字が入る。 各行の先頭の数字は 0 ではない。

57 　 ＣＲＯＳＳ　 ＋ ＲＯＡＤＳ　 ＤＡＮＧＥＲ　 　　　ＴＷＯ ＋ＴＨＲＥＥ 　ＳＥＶＥＮ 　　（解２つ） 　　　ＳＩＸ 　ＳＥＶＥＮ ＋ＳＥＶＥＮ ＴＷＥＮＴＹ

58 覆面算の解法（全数探索） n 文字（n ≦ 10）のそれぞれに 0...9 を割り当てる。割り当て方はたかだか 10Pn 通り
それぞれの場合について、計算式が満たされるかを試す。 効率が極めて悪い。 人間の解き方とは全然違う。

59 ＳＥＮＤ ＋ ＭＯＲＥ ＭＯＮＥＹ 覆面算：解法(1) S, M は 0 ではない（ルール）
　 ＳＥＮＤ ＋ ＭＯＲＥ ＭＯＮＥＹ S, M は 0 ではない（ルール） <20000: M = 0, 1　→ M = 1 M 以外の文字は 1 ではない（ルール） < → S ≧ 8 < → O = 0, 1 → O = 0 O 以外の文字は 0 ではない（ルール） D, E は 0 ではない。 （E = 0 なら D+0=Y → D=Y) O=0 だから、N=E+1 (mod 10)

60 ＳＥＮＤ ＋ １０ＲＥ １０ＮＥＹ 解法 (2) 1 2 3 4 5 6 7 8 9 S E N D M O R Y
1 2 3 4 5 6 7 8 9 S × E N D M ○ O R Y 　 ＳＥＮＤ ＋ １０ＲＥ １０ＮＥＹ E+1=N+0 に繰り上がりは ないから、S=9

61 ９ＥＮＤ ＋ １０ＲＥ １０ＮＥＹ 解法 (3) 1 2 3 4 5 6 7 8 9 S E N D M O R Y
1 2 3 4 5 6 7 8 9 S × ○ E N D M O R Y 　 ９ＥＮＤ ＋ １０ＲＥ １０ＮＥＹ N+R+c=E+R+1+c=10+E だから R=8 （c は繰り上がり）

62 ９ＥＮＤ ＋ １０８Ｅ １０ＮＥＹ 解法 (4) 1 2 3 4 5 6 7 8 9 S E N D M O R Y
1 2 3 4 5 6 7 8 9 S × ○ E N D M O R Y 　 ９ＥＮＤ ＋ １０８Ｅ １０ＮＥＹ D+E>10 であり、Y>1 だから D=7

63 数独 http://www.nikoli.com/ja/puzzles/sudoku/ 各マスに１～９の数字 を入れる。
同じ行・列・３×３ ブロックに同じ数字が 入ってはいけない。

64 数独解法（基本戦略） 戦略 A 戦略 B 初心者は戦略 B で考えがちだが、それで決まるマスは少ない。戦略 A が中心。
どの数字も必ずブロック（縦・横列、3×3ブロック）に１つ入る。 ある数字が入る場所が1か所ならそこに確定。 戦略 B 同ブロックには同じ数字は１つしか入らない。 あるマスに入る数字が1個ならそれに確定。 初心者は戦略 B で考えがちだが、それで決まるマスは少ない。戦略 A が中心。 難しい問題になると、上の基本戦略では行き詰る。 複数のマスの組み合わせを考える必要が生じる。

65 数独の変種 数独は 9×9 サイズが基本だが、様々な変種がある。
変種の中には基本の戦略がそのまま使えるものもあるが、別の考え方やアプローチが必要になる場合もある。 以下ではサイズについての変種、16×16 や 25×25 のバージョンのみ取り上げる。 参考：　今年（2013年度）の慶大 SFC 入試（数学）でもろに（変形）数独が出題された。これまでも縮小版 （4×4 とか）の数理を扱う問題はあったのだが。

66 数独の上達法（１） 理詰めに、論理的に考えれば必ずできるのだから、所要時間は気にせずに、冷静に取り組めば、誰でも必ず解けるのではないか？
解き方指南（ハウツー本、攻略本）を勉強すればいくらでもうまくなるのではないか？ そういった戦略は解いているうちに自然に発見・身につくものではないか？ またそうでなければ活用できないのではないか？

67 数独の上達法（２） 初心者の場合 何をやればいいかわからない、どこから手をつけていいかわからない、何に注目すればいいかわからない。
考えが同じところを堂々巡りする。 当てずっぽうをやる。 ミスを犯す。 現在初心者レベルの人は、今の自分が考えていることをよく記憶・記録しておいてほしい。（上達したあとで振り返るために）

68 数独の上達法（３） 外部記憶（補助記憶）の利用 メモ等を欄外に手書きするなど。 何を記すか、どのような形式で記すか。
表現方法を整理する、効果的な方法を編み出すこと自体が大事。 盤面に試しに答候補を書き込む ⇒「消すこと」 コンピュータ上のツールなどの作成・利用。 逆に、メモ書などを使用せず頭の中で考える。 ⇒　上達につながる。

69 数独の上達法（４） 戦略の必要性 定型的な手段・手順等をまとめた「知識」。 囲碁・将棋の「定石（定跡）」など。
適用できると思考の省力化になる。 一般性のある戦略、特殊な戦略。 戦略によっては適用できるかどうかの判断自体が大変、手間がかかる。

70 数独の上達法（５） 戦略以外のテクニック・能力 同じように戦略を「勉強」しても、解き方の速さ、うまさに違いがあるのはなぜか？
盤面状態の掌握能力 「気づき」、「見落とし」 人間の認知能力の特性と限界 「出題者の意図を読む、裏を読む」

71 数独の上達法（６） 頭の中（だけ）で考える。 当然、メモ書きを利用したりする場合より難しくなるし、間違いやすくもなる。
しかし速い上達にはつながる。 トレーニングとしては極めて有効。 囲碁・将棋のプロ（上級者も）は頭の中だけで手を読む。

72 Magical Number Seven Miller, G. A. (1956). "The magical number seven, plus or minus two: Some limits on our capacity for processing information". Psychological Review 63 (2): 81–97. Web 版 最もよく知られ、引用される心理学論文の１つ 短期記憶の存在とその容量 情報の「チャンク化」 認知心理学・認知科学誕生の契機

73 Subitizing Wikipedia (en): Subitizing
点などの個数を「瞬時に」認識する能力 ⇔　counting, estimating 6, 7 点ぐらいが限度 デモ参照

74 問題の難易度（１） 問題により、易しさ、難しさの度合いが格段に違うのはまちがいない。 問題集などでの難易度評価は人間が行っている。
どのように判断しているか？ どの程度的確か、安定性・信頼性があるか？ 客観的な評価方法はあるか？ 評価は誰にでも共通か？個人差はないか？ 解決プログラムは問題評価に使えるか？ どういう要因・処理が難易度と関係するか？

75 問題の難易度（２） 客観的な指標 主観的・個別的な要因 直ちに決定するマスはいくつあるか？ 基本戦略 A, B のどちらによるか？
それにより決定できないマスがある場合はどうか？（上級問題） 主観的・個別的な要因 発見しやすいか？ 列（縦・横）とブロック（3×3）との違い 列同士は１マスのみ共有、ブロックとは３マス共有。

76 問題解決の心理実験 取得するデータ 時間データなどは、紙に書くのではなく、コンピュータ入力したほうが正確に取得できる。 記入した用紙
記入手順、時間 記入時の行動（ビデオ撮影等） 時間データなどは、紙に書くのではなく、コンピュータ入力したほうが正確に取得できる。 しかし問題をとく環境・状況が紙の場合とは大きく違ってしまう。

77 参考： 一般性、個別性 形式的・論理的な定式化は一般性・汎用性があり、多様な問題に同じ手段が出来ようできる。（例： 文章題への代数の適用）
参考：　一般性、個別性 形式的・論理的な定式化は一般性・汎用性があり、多様な問題に同じ手段が出来ようできる。（例：　文章題への代数の適用） 人間はそのような形式的・機械的手段をうまく適用・運用できるか？ 実際には、問題の個別性に引きずられる面が大きい。 例：　４枚カード問題、ハノイの塔の変形版

78 探索技法 再帰的アルゴリズム 非再帰的： 制御用データ構造の利用 状態の生成・展開 探索過程の制御 縦型探索、（横型探索）
非再帰的：　制御用データ構造の利用 縦型探索（スタック stack） 横型探索（キュー queue） 状態の生成・展開 事前にすべて、探索と平行して動的に（on the fly） 探索過程の制御 既訪状態のチェック 探索順の選択　　⇒　Hill Climbing, 最良優先探索

79 各種の探索 現実的な問題では全探索はできない 局所評価（評価関数）と「山登り法」 最良優先探索 深さ限定探索 AND/OR 木 ゲーム木
複数の「探索前線」の保持 (Genetic Algorithm) 深さ限定探索 AND/OR 木 ゲーム木 制約伝播法

80 ゲーム木 「２人完全情報ゼロ和ゲーム」 チェス、碁、将棋、オセロ、三目並べ、…
２人の対戦、有利・不利が相反的関係にある ゲームの各状態（盤面）における情報が、両者にすべて共有されている。 全探索は不可能であることが前提 ⇒　評価関数が中心的な役割を果たす。

81 ゲーム木（２） 評価関数： max: 先手有利、min: 後手有利 Mini-max tree mini-max 探索
一方の有利な状況　＝　他方の不利な状況 １手ごとに、探索目標が入れ替わる。 １手目：　先手にとって最も有利な手を選ぶ ２手目：　後手にとって最も有利（先手にとって最も不利）な手を選ぶ。 … mini-max 探索 α-β pruning

82 評価関数の利用 評価関数 ある状態における探索状況の良し悪し（解までの距離、得られる解の良し悪し等）を、探索を行わずに、少ないコストで計算する関数。 「山登り法」　(Hill Climbing) 評価値の良い状態から順に探索していく local peak, plateau 最良優先探索 レベル間にわたる複数の「探索前線」から評価値の高いものを優先して探索する。

83 mini-max 探索 A B C G E I K L N O Q H P F M J D max min 6 4 8 5 7 3 1 9
評価関数値

84 mini-max 探索 A B C G E I K L N O Q H P F M J D 6 max min (min) 6 3 6 8
7 3 9 6 4 8 5 7 3 1 9

85 αーβ pruning（枝刈り） 基本の mini-max 探索は、あるレベルでの評価関数値がすべて算定されていることが前提。
しかし評価関数の計算にはコストがかかる。 実際には計算しなくてもいい（探索に影響しない）ものもある。 αーβ pruning は探索範囲を一定の割合で減らすが、指数オーダーを改善するわけではない。

86 αーβ pruning max min × (min) 610 A B C G E I K L N O Q H P F M J D 66
<=39 63 >=84 >=75 39 × 61 42 84 × 75 37 18 × × （肩付きの数：　値が決定する順番。 ×は計算の必要がない部分）

87 ゲーム木（３） その他の探索テクニック 評価関数の良否 盤面が急激に変わる状況 「水平線効果」 各種の発見的探索
選択的深化 (selective deepening) 特定の有望そうな枝だけを重点的に探索する 事前探索 局面・手順データベース（終盤データベース、「定石」） 評価関数の良否 盤面が急激に変わる状況 「水平線効果」

88 ゲームプログラムを強くする 「仕込み」：あらかじめ調べた結果をデータベース化する。 機械学習手法の発展とその利用
終盤データベース、定石データベース等 過去の対戦記録（特に上級者の） 機械学習手法の発展とその利用 自分自身、あるいは他のソフトと対戦するなど 新規な手法・アルゴリズムの開発 囲碁におけるモンテカルロ法の適用など

89 本日の課題 人工知能における基本概念・用語、研究の動向を理解する。 典型的・代表的な研究例について、原論文などを含めて内容を調べる。
パズルなどの問題について、自分で解いてみてその解き方を観察・考察する。