認知科学 思考のメカニズムと実践（２） ２０１８年１１月２６日（月）

ハノイの塔 ルール タスク 3本の杭（ペグ）と中央に穴の開いた大きさの異なる複数の 円盤（ディスク）から構成される． 最初はすべての円盤が左端の杭に小さいものが上になる ように順に積み重ねられている． 円盤を一回に一枚ずつどれかの杭に移動させることができ るが，小さな円盤の上に大きな円盤を乗せることはできな い． タスク 一番左のペグに下から大きいディスクの順で積み重ねられた状態か ら，ルールに従ってこの状態のものを一番右のペグに作る．

問題解決場面（ブロックの移動）における心的過程 タスク Ｐ２にブロックＡ，Ｂ，Ｃを重ねる 条件 自分より大きなブロックの上だけに重ねられる 自分より小さなブロックの上には重ねられない ブロックの移動は１個ずつ Ｃ Ｂ Ａ Ｐ１　　　　　　　　　　Ｐ２　　　　　　　　　　Ｐ３

問題解決場面（ブロックの移動）における心的過程 タスク Ｐ２にブロックＡ，Ｂ，Ｃを重ねる 条件 自分より１つ大きなブロックの上だけに重ねられる 自分より小さなブロックの上には重ねられない ブロックの移動は１個ずつ Ａ Ｂ Ｃ ゴールの状態 Ｐ１　　　　　　　　　　Ｐ２　　　　　　　　　　Ｐ３

記号と操作の形式 記号 操作 初期状態 ブロック： Ａ，Ｂ，Ｃ 位置： Ｐ１，Ｐ２，Ｐ３ 状態記述： Ｐ１（Ａ，Ｂ） ブロック： Ａ，Ｂ，Ｃ 位置： Ｐ１，Ｐ２，Ｐ３ 状態記述： Ｐ１（Ａ，Ｂ） 操作 移動： Ｍ（Ｂ，Ｐ１，Ｐ２） 位置Ｐ１にブロックＢの上にＡが重なっている 位置Ｐ１にあるブロックＢをＰ２に移動（重ねる） 初期状態 Ｐ１（Ｃ） Ｐ２（Ｂ） Ｐ３（Ａ） ゴール状態 Ｐ２（Ａ，Ｂ，Ｃ）

操作ルールの記述 （プロダクションルール） Ｒ１：移動できるブロックの選択 if （任意のブロックが１番上にある） then （そのブロックだけを選択できる） Ｒ２：空いている場所へのブロックの移動 if （移動先にブロックがおいていなければ） then （ブロックを移動できる） Ｒ３：すでにブロックがある場所への移動 if （移動先にブロックが自分よりも大きければ）

中国のお茶会の問題 　ヒマラヤのある村では非常に洗練された茶会が行なわれている．茶会ではホスト１人と客２人というのが慣例であり，それより多くても少なくてもいけない．客人の１人は，もう１人の客人よりも年長である．２人の客人が席につくと，ホストが客人に次の３つのもてなしを行なう．これらのもてなしには，ヒマラヤ人が抱いている気品度の低い順に次の順位がついている． 火をともす（低い気品度） 茶をいれる（中くらいの気品度） 詩を吟ずる（高い気品度） 　茶会の最中には，この茶会に出席してる３人の誰でも，「失礼ながら，あなたのためにそのもてなしをしてさしあげましょうか」と尋ねることができる．尋ねられた人は，今もてなそうとしているもてなしのうち気品度の最も低いもてなしだけをするようにお願いすることができる．しかし，その人がすでに何かもてなしをしているのであれば，そのもてなしのなかで最も気品度の低いもてなしよりも高いもてなしをお願いすることができない． 　この洗練されたお茶会が終わる時間には，ホストから年長者の客人すべてのもてなしが移動しているという．どのように達成されるのだろうか？

ハノイの塔の問題とまったく同じ構造をもち，同じ解法で解決できる． 理解すること 中国のお茶会の問題 (Simon & Hayes, 1976) の解決は 難しく感じてしまう． しかし実態は極めて簡単な問題である． 大 中 小 詩 茶 火 左 右 ホスト 客人 客人（年長） ハノイの塔の問題とまったく同じ構造をもち，同じ解法で解決できる．

思考過程をモデル化する いくつかの記号とその記号に対する手続きに よって思考過程を記述することができる． 抽象的な形式的処理としての思考過程をモデ ル化することによって，複雑（そう）な思考過程 の本質を理解することが容易になる． コンピュータ上にモデルを実装することによっ て，さまざまなパラメータを変化させることによ るシミュレーション実験が可能になる．

ヒューリスティクス (heuristics) どのようにしてよいかわからない場合に，うまくゆくという保証はないが，以前の経験に頼って役に立ちそうなことをやってみるという方略．将棋や碁，チェスなどの問題解決に多い． 人間は複雑な問題解決場面においては，しばしば ヒューリスティクスを暗黙に用いている． ヒューリスティクスによって生じる認識上の偏りを認知 バイアスと呼ぶ． 日常の多くの問題は不良定義問題（解法が存在しな い）が大半なため，ヒューリスティクスが有効な問題解 決の方法になることが多い．

思考と問題空間の探索 思考（≠白昼夢）とは，知識を系統立てて問題を解決す る認知的過程である． 系統立てて処理すること →情報処理過程として捉えることが可能 問題解決の手掛かりとなる使える情報（知識）を利用 して，スタート地点からゴール地点まで空間を系統立 てて移動すること →探索

ヒューリスティクスが使われる状況 問題の解法があらかじめ定まっていない場合． →世の中のほとんどは正しい解があるとは言えない． 問題の解法があらかじめ定まっていない場合． →世の中のほとんどは正しい解があるとは言えない． 複数の解法が存在し，いずれの方法でもゴールに到 達する可能性がある場合（ゴールに到達できるとは限 らない）． 人間の場合，過去の成功事例を踏襲することが多い． 保守主義もこのようなバイアスの具体例といえるかも．

ヒューリスティック探索 探索すべき状態空間を削減する方法の１つに，そ の問題に関するさまざまなこの情報（知識）をうまく 利用する方法を考える． 展開した子の状態をなんらかの評価基準で優先 順位をつけ，その順序で調べていくことで探索効 率を向上させることができる． 場合によっては解の探索に失敗する可能性がある ものの，多くの場合探索効率を向上させることが 期待できる． 探索における経験的知識を表現するためのヒュー リスティック関数を利用する．

山登り法 (hill climbing) 勾配降下法 (gradient descent) 山頂（谷底）を目指す登山（谷くだり？）をイメージ． ある地点に立ったとき，次の一歩はその周囲で一番 高い（低い）地点に踏み出す． これを繰り返すと，次の一歩が選択できない地点に至 る→山頂（谷底）に到達

自分の生活の中でのヒューリスティックス 水筒 鏡 塩 マッチ 毛布 医薬品

探索の方法 ヒューリスティック関数 →山頂との高さの差 局所的最小値(local minima) に陥る可能性がある ８ ヒューリスティック関数 →山頂との高さの差 局所的最小値(local minima) に陥る可能性がある 高原(plateau)のような状態に なると，進む方向を見失ってし まう ６ ５ ７ ８ ４ ３ ４ ５ plateau local minima

例題： 迷路問題 迷路の交差点を自然数の座標の組（ｘ，ｙ）で表す ことにする． 例題：　迷路問題 迷路の交差点を自然数の座標の組（ｘ，ｙ）で表す ことにする． 交差点ｑ＝（ｘ，ｙ）と出口ｇ＝（ａ，ｂ）の距離 ｄ（ｑ，ｇ） を次のように定義する． ｄ（ｑ，ｇ）＝｜ａーｘ｜＋｜ｂ－ｙ｜ このとき経験的知識として 「ある状態ｑを展開したとき，距離ｄ（ｑ，ｇ）が最小 となる子の状態ｑについてのみ，次の展開を行 う」 を用いる． このときのヒューリスティック関数は２で定義した 式を用いる． 入口 (s) 出口 (g) P → ↓ 上の図の迷路に対して，入口sから迷路に入った人間Pが出口gに到達するための解を求めよ． s 1 2 3 4 7 5 6 8 g （ｓ→１→２→５→８→ｇ），（ｓ→１→４→８→ｇ） 状態１を展開した状態２と状態４は同じヒューリスティック関数をもつので，どちらを選ぶかはランダムに決める．

縦型（深さ優先）探索 (DFS) 初期状態から離れた状態を 優先的に調べる探索方法． 行き止まり状態になると，解 を探索するために，それまで の経路を次の探索を再開で きる状態まで後戻りする （バックトラック）． バックトラックを効率よく制御 するために，スタックが用い られる． １ ２ ５ ３ ４ ６ ９ ７ ８ １０ １１

最良優先探索 (best first search) 山登り法が第３ステップで，{7,8}か ら最小値を選択する． 最良優先探索は未探索の前節点 集合{6,7,8}から最小値を選択する． 適切なヒューリスティック関数を定 めることが可能なら，方向性を有す る探索なので，ブラインド探索より 効率よく目標状態を探索できる． 未探索節点の格納なのに多くのメ モリ量が必要となってしまう． ８ ６ ５ ９ ６ ７ ８ ３ ２

局所的最小値からの脱出 山登り法のように，局所的最小値に 至っても，それを回避し，目標状態に 向かうことができる． しかし，得られた経路が最良の経路であ ることは保証されない． ヒューリスティック関数がうまく定義できれ ば，多くの場合，妥当な精度の解を高速 で探索可能． 過去の経路の情報を記憶しているた め，ある状態において次に移動すべ き状態を探すときに，そのときにはあ まり有望に思えなかった状態も選択 の対象とする． 局所的最小値 [4,3] ｙ ３ ２ ｇ ４ ３ ２ １ [1,1] ｓ ３ ２ ｘ ○の中は評価関数（ヒューリスティック関数） f(n) の値．ただし，n の座標を[x,y]とすると， f(n) = (4-x) + (3-y)

制約条件を用いた探索の効率化 解の探索に制約を加える手法 →解の探索範囲を減らすことで探索効率を向上 解の探索に制約を加える手法 →解の探索範囲を減らすことで探索効率を向上 問題の表現において定義される状態を「許容状態」「禁止状 態」に分離する． 探索の過程で禁止状態に移る作用素は適用しない条件を設 ける． 探索しなければならない領域は増加するため探索効率は低下する． 弱く定義 「禁止状態」を定義する「制約条件」 探索しなければならない領域は減少するが，「禁止状態」の中に目標状態が含まれてしまい，解が見つからなくなる可能性が生じる． 強く定義 トレードオフ関係

制約条件とバックトラックを用いた探索 宣教師と人喰い人種問題（ＭＣ問題） ３人の宣教師(missionaries)と３人の人喰い人種(cannibals) が，左岸から右岸に２人乗りのボートで川を渡ろうとしている． 川の両岸，あるいはボートの上で宣教師の数より人喰い人種 の数が多くなったとき，宣教師は人喰い人種に食べられてし まうものとする．このとき宣教師が食べられてしまうことなく， ボートを使って川を渡る手順を考えよ．

ＭＣ問題の状態空間の表現 定義 状態空間の表現 時刻ｔに，左岸Ｌにいる宣教師の数： Ｍ（ｔ） 人喰い人種の数： Ｃ（ｔ） 時刻ｔに，左岸Ｌにいる宣教師の数：　　　 Ｍ（ｔ） 　　　　　　　　　　　　　　人喰い人種の数：　Ｃ（ｔ） 時刻ｔでボートが右岸Ｒに接岸している状態：　Ｄ（ｔ）＝Ｒ 　　　　　　　　　　左岸Ｌに接岸している状態：　Ｄ（ｔ）＝Ｌ ボートが岸に着いたときすべての人間は一旦ボートを降りる． 状態空間の表現 状態　ｓ（ｔ）＝＜Ｍ（ｔ），Ｃ（ｔ），Ｄ（ｔ）＞ ただし，　０≦Ｍ（ｔ）≦３，０≦Ｃ（ｔ）≦３ 　　　　　｜Ｍ（ｔ）－Ｍ（ｔ＋１）｜＋｜Ｃ（ｔ）－Ｃ（ｔ＋１）｜≦２ 初期状態　ｓ０＝＜３，３，Ｌ＞ 目標状態　ｓｇ＝＜０，０，Ｒ＞

ＭＣ問題の禁止状態と許容状態 禁止状態（右岸か左岸で人喰い人種が宣教師の数より多くな る状態のすべて） ＳＦ＝｛＜Ｍ（ｔ），Ｃ（ｔ），Ｄ（ｔ）＞｜Ｍ（ｔ）＜Ｃ（ｔ） または　３－Ｍ（ｔ）＜３－Ｃ（ｔ）｝ SF={<2,3,D>, <1,3,D>, <1,2,D>, <2,1,D>, <2,0,D>, <1,0,D>} ただし，ＤはＲまたはＬ． 全状態集合をＳで表し，許容状態をＳＧで表す と， ＳＧ＝Ｓ－ＳＦ SG={<0,0,R>, <0,3,D>, <0,2,D>, <0,1,D>, <1,1,D>, <2,2,D>, <3,0,D>, <3,1,D>, <3,2,D>, <3,3,L>}

解の探索 縦型探索を用いる． 禁止状態を行き止まり状態と見なして，バックト ラック（前の状態に戻る）する． 適用する作用素（N1～N10の１０個） if ((D(t)=L) && (M(t)≧1) then M(t+1)←M(t)-1, C(t+1)←C(t), D(t+1)←R if ((D(t)=L) && (M(t)≧2) then M(t+1)←M(t)-2, C(t+1)←C(t), D(t+1)←R if ((D(t)=L) && (C(t)≧1) then M(t+1)←M(t), C(t+1)←C(t)-1, D(t+1)←R

課題（１） N4～N10を記述せよ ヒント N5 if ((D(t)=L) && (M(t)≧1) && (C(t)≧1) then M(t+1)←M(t)-1, C(t+1)←C(t)-1, D(t+1)←R N10 if ((D(t)=R) && (M(t)≦2) && (C(t)≦2) then M(t+1)←M(t)+1, C(t+1)←C(t)+1, D(t+1)←L

許容状態を満たす条件と移動方法 M(t)≧C(t)　かつ　3-M(t)≧3-C(t)　を満たす状態 ⇒任意のｔに対して， 　　M(t)=0　または　M(t)=3　または　M(t)=C(t) M(t)=3 or M(t)=0 →　宣教師はボートに乗らない，または　 M(t+1)=C(t+1)　になるように移動させる． M(t)=C(t) →　M(t+1)=3　または　M(t+1)=0　になる移動を行う， あるいは，宣教師と人喰い人種を１人ずつ移動させる．

適用する作用素（続き） if ((D(t)=L) && (C(t) ≧2)) then M(t+1)←M(t), C(t+1)←C(t)-2, D(t+1)←R if ((D(t)=L) && (M(t)≧1) && (C(t)≧1) then M(t+1)←M(t)-1, C(t+1)←C(t)-1, D(t+1)←R if ((D(t)=R) && (M(t)≦2)) then M(t+1)←M(t)+1, C(t+1)←C(t), D(t+1)←L if ((D(t)=R) && (M(t)≦1)) then M(t+1)←M(t)+2, C(t+1)←C(t), D(t+1)←L if ((D(t)=R) && (C(t)≦2)) then M(t+1)←M(t), C(t+1)←C(t)+1, D(t+1)←L if ((D(t)=R) && (C(t)≦1)) then M(t+1)←M(t), C(t+1)←C(t)+2, D(t+1)←L if ((D(t)=R) && (M(t)≦2) && (C(t)≦2) then M(t+1)←M(t)+1, C(t+1)←C(t)+1, D(t+1)←L

課題（２） ＭＣ問題の状態空間を生成し，完成させよ． <2,3,R> <2,2,R> <3,1,R> <2,1,L> <3,2,L> <2,3,R> <3,0,R> <3,3,L> <3,1,L>