認知科学 問題解決（３） ２０１８年１２月３日（月）

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

制約条件とバックトラックを用いた探索 宣教師と人喰い人種問題（ＭＣ問題） ３人の宣教師(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>

ＭＣ問題の解答 左岸 ボート位置 右岸 □人喰い人種 ■宣教師 ■■■□□□ ○ ■■■□ □□ ■■■□□ □ ■■■ □□□ ■□

冬休みを「楽しむ」ための クリスマスプレゼント ＆ お年玉 人の知能をシミュレート 冬休みを「楽しむ」ための クリスマスプレゼント　＆　お年玉

上記のような作業をプレーヤーが相互に行う 思考による対戦ゲーム 相手の意図や考えを推測する． 相手には本当の自分の意図や考えを知られないよう にする． ときとして相手に偽りの意図や考えを信じさせるための 振る舞いを行う． 相手の目論み通りに実行できないように手を打ち，自 分にとって有利な展開になるようにする． 上記のような作業をプレーヤーが相互に行う

とりあえずやってみる（１） レーダー作戦ゲーム http://chibicon.net/a/31.html １０×１０マスの戦場　（0,1,2,3, …, 9 / A, B, C, D,…, J) 航空母艦（５マス），戦艦（４マス），巡洋艦（３マス），潜水艦（３マス），駆逐艦（２マス） 軍艦に装甲はない（耐久力なし） 各軍艦の大きさ（マス数）の分被弾すると撃沈 移動なし 相手の軍艦に砲弾が命中すれば，外れるまで連続攻撃が可能（通常は交互の攻撃権） FLASHを使えるようにしてください

とりあえずやってみる（２） レーダー作戦ゲーム １０×１０マスの戦場２つ（自軍用／相手用）を適当な用紙に作成する． 各軍艦を任意に配置する． ３ ４ ５ ６ ７ ８ ９ A B C D E F G H I J １０×１０マスの戦場２つ（自軍用／相手用）を適当な用紙に作成する． 各軍艦を任意に配置する． 隣の人と勝負する． 先攻・後攻はじゃんけんで決める． 攻撃権は交互．例「４-Hにドン！」 相手の軍艦に砲弾を命中させたら攻撃権は外すまで継続する． 命中したら「命中」とコールする． 撃沈されたら「撃沈」とコールする． 相手よりも先にすべての自軍艦が撃沈されたら負け．

軍艦の最小サイズは２マス分であることの意味を考える．．． 検討（１） 自軍の軍艦の配置 ルールの定義 軍艦を配置できるマスは？配置できないマスは？ ヒューリスティックスの適用 相手に探索されやすい配置は？ 相手に探索されづらい配置は？ 軍艦の最小サイズは２マス分であることの意味を考える．．．

検討（２） 相手への攻撃 ルールの定義 ヒューリステックスの適用 砲弾を撃ってもいいマスは？ダメなマスは？ 砲弾を撃ち込んでも無駄なマスは？ すでにどの軍艦を撃沈済かどうかに依存 ヒューリステックスの適用 相手の軍艦を探索するために砲弾を撃つマスの効果的 な選択方法は？ さまざまな探索アルゴリズムの活用 どの軍艦から探索していくか？

参戦エントリー 艦隊司令エージェントを作成するチームのエントリー 人としてのエントリー １〜３名で１つのチームを構成する 情報科学科の学生はエージェントを作ることMUST 艦隊司令エージェントを作成するチームのエントリー １〜３名で１つのチームを構成する 優勝賞品＋副賞はチーム人数で按分する チーム名を決めておく 勝負をするのはあくまでもエージェント 人はエージェントの入出力のインタフェースの仕事だけ 人としてのエントリー 個人単位でのエントリー（複数人は不可）する 個人名でのエントリーする 勝負は自分自身で行う 履修者は全員いずれかの形（チームが望ましい）でエントリーすることが義務

https://goo.gl/forms/QkPHivfSrcizWDUu1 エントリー方法 https://goo.gl/forms/QkPHivfSrcizWDUu1 上記URLからエントリー １２月７日（金）　 １７：００まで

実装仕様 自軍の各軍艦の配置はエージェントが自律的に行う． 相手への攻撃は，エージェントによる砲弾を撃ち込む座標｛(A,0), (A,2),…, (B,1),…, (B,10), (C,1),…,(J,9)｝（計100通り）の出力とし， 対戦相手にその出力結果を人が口頭で伝える．「(F,3)にドン！」 相手から伝えられた座標を人が手入力し，それに基づきエージェ ントが命中判定を行う．命中した場合には，人が音声で「命中」， 命中しなかった場合は，「外れ」と相手に伝える． 攻撃側は砲撃の結果（命中／外れ）を人が入力する． 命中した場合は，攻撃権は持続する．外れた場合は交替． 撃沈されたときには「撃沈」と相手に伝える． どちらからの軍のすべての軍艦が撃沈されるまで，戦闘は続く．

考えてみよう 人間はランダムさに勝てるか？ 人間らしい知的振る舞いと，人間らしいとは言えない知 的な振る舞いでは，どちらの方が「賢い」か？ 人間に強いエージェントだけど，エージェントには必ずしも強くないエージェントが作られる可能性． 人間はランダムさに勝てるか？ なぜ人間はランダムさに弱いのか？ 相手が人間であるという知識，または相手が機械である という知識が事前にあることで，人間の行動に違いはあ るかのか？ 人間らしい知的振る舞いと，人間らしいとは言えない知 的な振る舞いでは，どちらの方が「賢い」か？ 日常生活空間（人間が作った環境）での問題解決 非日常生活空間（自然あるいは統計的・アルゴリズム的 環境）での問題解決

〜１２／２６までの作業 エントリーした艦隊司令エージェント実装チーム・プ レーヤーによるプレゼンテーションを教員に必ず行う． 自軍の軍艦の配置戦略 探索を兼ねた攻撃に用いるヒューリスティックス 命中した場合の次の攻撃に用いるヒューリスティックス Offie hour 月 火 水 木 金 今週 ３ 13:00-15:00 ４ 15:00-17:00 ５ 09:00-14:00 ６ 0900-12:00 ７ 13:00-17:00 来週 １０ none １１ 09:00-17:00 １２ none（伊勢） １３ １４ 再来週 １７ none（英国） １８ １９ ２０ ２１ 再再来週 ２４ none（東京） ２５ ２６ 09:00-12:00 電子メールでアポイントメントを取ること．柔軟に対応してください．

対戦方法 予選リーグ 艦隊司令エージェント同士の対戦 艦隊司令エージェントと人との対戦 人と人との対戦 いずれかの対戦形態 艦隊司令エージェント同士の対戦 艦隊司令エージェントと人との対戦 人と人との対戦 艦隊司令エージェントが勝ったとき　勝ち点４ 人が艦隊司令エージェントに勝ったとき　勝ち点２ 人同士の対戦で勝った方の人　勝ち点１ 予選リーグ１組あたりＮチームの総当たり戦 各チームＮ−１試合の実施

対戦方法 決勝トーナメント 不可にならない唯一の方法 各予選リーグ１位のチームによる勝ち抜き戦 優勝チームには豪華賞品および副賞 優勝チームが艦隊司令エージェントの場合 価値Ｘ相当の〇〇 優勝チームが人の場合 価値Ｘの50%分の〇〇 副賞：最終期末レポートの成績評価に１ポイントUP D→C C→B B→A A→S 不可にならない唯一の方法

今日中・今週中に やっておくこと 今日中のタスク 今週中のタスク チームで勝負するか？個人（自分の頭脳）で勝負するか？ チームで勝負するなら，仲間を募ろう． エントリー　１２月７日（金）１７：００まで 今週中のタスク レーダー作戦ゲームの理解 「負けないため」「勝つため」の戦術・ヒューリスティックスの 検討 １２月２６日（水）まで行うプレゼンテーションの準備 個人エントリーの場合はトレーニング．チームの場合は，コ ンピュータプログラムとしての実装．

最強の艦隊をつくる 冬休みの課題 ルールの適用と効果的なヒューリスティックスの活用による天才艦隊司令エージェントをプログラム・実装する． 鉄壁の守りとなる軍艦の配置 効率的な戦場の探索 相手に対する連続した砲弾の命中 ルールの適用と効果的なヒューリスティックスの活用による天才艦隊司令エージェントをプログラム・実装する． 冬休みの課題

年明け最初の授業 １/７ (Mon)の予定 冬休み期間中にしっかり実装すること 予選リーグ リーグの組み分けは，プレゼンテーションの内容を参 考に授業担当者の方で行う． 組（対戦相手）は当日発表． 各リーグの１位（予定）のチーム・プレーヤーが１月１４ 日（月）の決勝トーナメントでガチンコ対決． 冬休み期間中にしっかり実装すること

次回授業は１２月１０日（月） チームのプレゼンテーション まとめ 冬休みが始まるまでに チーム作りおよびエントリー　12/7 (Fri) 17:00まで 戦術ヒューリスティックスの言語化とアルゴリズムの検討 プレゼンテーション　12/26 (Wed)まで 冬休み期間中 最強の艦隊司令エージェントを実装する さまざまなケースでのテストを行っておく 対戦中ハングアウトしたら負け 対戦中バグ等でルールで許されていないことをしたら負け 次回授業は１２月１０日（月）　チームのプレゼンテーション