認知科学 問題解決(3) 2018年12月3日(月).

Slides:



Advertisements
Similar presentations
ロボット制御のソフトウェ ア: シミュレータ試作 情報理工学部 情報知能学科 H 207051 中谷聡太郎.
Advertisements

あみだくじ AMIDA-KUJI 井上 康博 Statistical analysis on Amida-kuji, Physica A 369(2006)
模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
 C 川船 美帆.  強い人工知能の作成 o 「遺伝的アルゴリズム」  「どうぶつしょうぎ」のアプリケーショ ン作成 o スマートフォン向けアプリケーション.
東京工科大学 コンピュータサイエンス学部 亀田弘之
情報・知能工学系 山本一公 プログラミング演習Ⅱ 第3回 配列(1) 情報・知能工学系 山本一公
本日のスケジュール 14:45~15:30 テキストの講義 15:30~16:15 設計レビュー 16:15~16:30 休憩
UECコンピュータ大貧民大会 参加後の考察
「わかりやすいパターン認識」 第1章:パターン認識とは
ML 演習 第 8 回 2007/07/17 飯塚 大輔, 後藤 哲志, 前田 俊行
第11回 整列 ~ シェルソート,クイックソート ~
知識情報演習Ⅲ(後半第1回) 辻 慶太(水)
コンピュータ囲碁の仕組み ~ 将棋との違い ~
社内での競争は組織が払う犠牲は大きい ⇒全体の幸せに無関心 競争原理を持ち込むのはほかの手段より公平で利用価値アリ!
東京大学工学部 丁友会学生委員会 学生委員長 竹内健登
ブロック運びゲーム.
座 席 表(CP教室) 出席番号.
班紹介 描画班一同.
プログラミング演習Ⅱ 第12回 文字列とポインタ(1)
電子黒板を活用した 小学校外国語活動研修 (入門編)
「データ学習アルゴリズム」 第3章 複雑な学習モデル 3.1 関数近似モデル ….. … 3層パーセプトロン
人 工 知 能 第3回 探索法 (教科書21ページ~30ページ)
経済情報処理ガイダンス 神奈川大学 経済学部.
クロスワードゲームの 作り方を学ぼう/やってみよう ‐ボードゲームの動作機構‐
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
Observable modified Condition/Decision coverage
単位 おねだり ☆オセロ おねだり隊☆D班.
システム開発実験No.7        解 説       “論理式の簡略化方法”.
特別支援学校中学部生徒がUNO(ウノ)を使って,友だち同士で遊べるようになるための支援
経済情報処理ガイダンス 神奈川大学 経済学部.
第4回 カルノー図による組合せ回路の簡単化 瀬戸 目標 ・AND-OR二段回路の実現コスト(面積、遅延)が出せる
変数のスコープの設計判断能力 を育成するプログラミング教育
(ラプラス変換の復習) 教科書には相当する章はない
JAVAでつくるオセロ 伊東飛鳥、宮島雄一 長畑弘樹、ソギ原直人.
経済情報処理ガイダンス 神奈川大学 経済学部.
シミュレーション演習 G. 総合演習 (Mathematica演習) システム創成情報工学科
法政大学 情報科学部 2008年度「離散数学」講義資料
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
プログラミング 設計資料 メンバー:.
二分探索木によるサーチ.
迷宮師 コードレビュー チームカテキン.
ディジタル回路 3. 組み合わせ回路 五島 正裕 2018/11/28.
その他の図 Chapter 7.
決定木とランダムフォレスト 和田 俊和.
1DS05175M 安東遼一 1DS05213M 渡邉光寿 指導教員: 高木先生
只見町 インターネット・エコミュージアムの「キーワード」検索の改善
人工知能概論 第2回 探索(1) 状態空間モデル,基本的な探索
WEBアプリケーションの開発 2002年度春学期 大岩研究会2.
前回の練習問題.
6. ラプラス変換.
4人版リバーシYoninの解析 情報論理研究室 藤本 侑花
G班メンバー リーダー 橋本望 SE 北本理紗と服部友哉 PPT作成 橋本望と山田侑加
基礎情報技術 平成27年7月3日(金) 担当:亀田.
変換されても変換されない頑固ベクトル どうしたら頑固になれるか 頑固なベクトルは何に使える?
シナリオのアニメーション表示による 妥当性確認支援
東京工科大学 コンピュータサイエンス学部 亀田弘之
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
JavaScript プログラミング演習 - じゃんけんゲーム - 「ホームページを動的に制御したい…」
スポーツの最適化 優勝決定可能性問題 スポーツスケジュール問題.
Microsoft PowerPoint 2001 Netscape Communicator Fetch 3.03
★C++/オブジェクト指向実践企画★ Othelloゲーム作成
シミュレーション論 Ⅱ 第1回.
情報基礎Ⅱ (第1回) 月曜4限 担当:北川 晃.
数値解析ⅡーI ~オセロゲームのプログラム~
Othelloのプログラム 班長:佐々木 悠二 班員:石黒 護     井上 雄滋     齊藤 良裕     清水 裕亮.
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
ソフトウェア工学 知能情報学部 新田直也.
Q q 情報セキュリティ 第8回:2004年5月28日(金) の補足 q q.
今年の学年のルール 自分の名前をここに入力します.
認知科学 思考のメカニズムと実践(2) 2018年11月26日(月).
Presentation transcript:

認知科学 問題解決(3) 2018年12月3日(月)

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

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

MC問題の状態空間の表現 定義 状態空間の表現 時刻tに,左岸Lにいる宣教師の数: M(t) 人喰い人種の数: C(t) 時刻tに,左岸Lにいる宣教師の数:    M(t)               人喰い人種の数: C(t) 時刻tでボートが右岸Rに接岸している状態: D(t)=R           左岸Lに接岸している状態: D(t)=L ボートが岸に着いたときすべての人間は一旦ボートを降りる. 状態空間の表現 状態 s(t)=<M(t),C(t),D(t)> ただし, 0≦M(t)≦3,0≦C(t)≦3      |M(t)-M(t+1)|+|C(t)-C(t+1)|≦2 初期状態 s0=<3,3,L> 目標状態 sg=<0,0,R>

MC問題の禁止状態と許容状態 禁止状態(右岸か左岸で人喰い人種が宣教師の数より多くな る状態のすべて) SF={<M(t),C(t),D(t)>|M(t)<C(t) または 3-M(t)<3-C(t)} SF={<2,3,D>, <1,3,D>, <1,2,D>, <2,1,D>, <2,0,D>, <1,0,D>} ただし,DはRまたはL. 全状態集合をSで表し,許容状態をSGで表す と, SG=S-SF 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の10個) 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

課題(1) 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) を満たす状態 ⇒任意の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 になる移動を行う, あるいは,宣教師と人喰い人種を1人ずつ移動させる.

適用する作用素(続き) 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) MC問題の状態空間を生成し,完成させよ. <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>

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

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

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

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

とりあえずやってみる(2) レーダー作戦ゲーム 10×10マスの戦場2つ(自軍用/相手用)を適当な用紙に作成する. 各軍艦を任意に配置する. 3 4 5 6 7 8 9 A B C D E F G H I J 10×10マスの戦場2つ(自軍用/相手用)を適当な用紙に作成する. 各軍艦を任意に配置する. 隣の人と勝負する. 先攻・後攻はじゃんけんで決める. 攻撃権は交互.例「4-Hにドン!」 相手の軍艦に砲弾を命中させたら攻撃権は外すまで継続する. 命中したら「命中」とコールする. 撃沈されたら「撃沈」とコールする. 相手よりも先にすべての自軍艦が撃沈されたら負け.

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

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

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

https://goo.gl/forms/QkPHivfSrcizWDUu1 エントリー方法 https://goo.gl/forms/QkPHivfSrcizWDUu1 上記URLからエントリー 12月7日(金)  17:00まで

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

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

〜12/26までの作業 エントリーした艦隊司令エージェント実装チーム・プ レーヤーによるプレゼンテーションを教員に必ず行う. 自軍の軍艦の配置戦略 探索を兼ねた攻撃に用いるヒューリスティックス 命中した場合の次の攻撃に用いるヒューリスティックス Offie hour 月 火 水 木 金 今週 3 13:00-15:00 4 15:00-17:00 5 09:00-14:00 6 0900-12:00 7 13:00-17:00 来週 10 none 11 09:00-17:00 12 none(伊勢) 13 14 再来週 17 none(英国) 18 19 20 21 再再来週 24 none(東京) 25 26 09:00-12:00 電子メールでアポイントメントを取ること.柔軟に対応してください.

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

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

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

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

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

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