レポート課題：人工知能

講義のホームページはこちらです.

締め切り

第一回レポート（第1問～第6問）：12月22日の２３：５９まで。

第二回レポート（第7問～第12問）：2月4日の２３：５９まで。

注意事項

講義の内容により変更の可能性がある。最終的な内容は必ず講義の際に確認すること。
各回で提出する課題数は任意であるが、最低数は1問である。問題の難易度を印で示しているので、提出の際の参考にすること。簡単な問題であれば2問以上を提出することがのぞましい。
原則として、締切日より遅れて提出された場合は採点の対象としない。ただし、何らかの理由があれば、締め切りまでに提出したレポートについて更新・修正版をのちに提出することは認めることがある。
また、特段の理由があれば提出期限を延長する。

レポート採点方針

当然ながら提出したからといって満点とは限らない。
とりあえず適当に書いて提出するというのは印象が悪いので注意せよ。
最終評価は合計点をもとにした相対評価となる。
難しい問題に挑戦したり、多くの人が解かないような問題を解答するとポイントが高い。
ＡＩらしいユニークな解答も評価する。
参考までに★で難易度を示しておく。

課題内容

（第1問：課題番号01★）昨年度のノーベル化学賞はゲームAIに関連している。
その詳細はこのHPなどに詳しい。

では、Folditを遊んでみてその実体験を報告せよ。ただし個人の責任でゲームに参加すること。

とくに、
- ゲームに直観が有効だったか
- 本格的な科学に貢献できる意識があったか
- 共同作業・闘争意識の効果はあるか
- ShakeやWiggleなどのツールは局所解の脱出に役立ったか
- チュートリアルを含めてどのくらいの時間で何位まで達成したか
- 将来のAIの応用に貢献するか
について具体的な例（画面のスナップショットやデータ・記録）を示して、詳しく考察することが必要である。

また、ある程度の順位(過去で受講した者の最高記録：7000+,10位)は必須である。「ちょっとやってみた」というようなレポートは評価が低い。

Hint1: Foldit!の解説は教科書の6.1節にある。
Hint2: 説明のスライドはここにある。また、Foldit!をもとにしてNatureに掲載された論文はここにある。
（第2問：課題番号02★）

三段論法推論

メンタルモデル

教科書1.3節

三段論法推論には教科書の図1.7で説明しているように全部で64種類ある。これらの問題をいろいろな用語や何気ない会話で試してみる。
LLMがいかに間違えるのか・正しく答えるのかを観察し、集計する。
さまざまなChain of Thoughtや呪文を工夫してみよ。
どのように錯覚して回答するのかを記述する。

ここ

Hint1:

参考書

Hint2:

ここ

（第3問：課題番号03★）次の2問にすべて答えること。

進化計算の原理を身近な例を用いて分かりやすく説明せよ。少なくとも以下の項目についてアナロジーで解説すること。

交叉
突然変異
世代交代
集団初期化
選択・淘汰
適合度計算
探索が上手くいくようす

採点しない。

進化計算の面白い応用例・実用例について調べて考察せよ。

著名な例は除く

学術論文や技術的詳細ではない

（第4問：課題番号04★★）

最初の配置
〇	Ｘ	Ｘ
〇	Ｘ	〇
Ｘ	〇	Ｘ

Stamp 1
□	□
□	□

次の配置
Ｘ	〇	Ｘ
Ｘ	〇	〇
Ｘ	〇	Ｘ

Stamp 2

□	□
□	□

さらに次の配置
Ｘ	〇	Ｘ
〇	Ｘ	〇
〇	Ｘ	Ｘ

（１）次の初期配置について、L型のスタンプを押してすべての印を〇にする手順を探索せよ。A*,深さ優先,広さ優先探索をそれぞれ実行して探索の効率（解に到達するまでのノードの展開数）を比較すること。ただしスタンプは回転して使っても良い。自分でA*用の効果的なヒューリスティックスを考えて実験してみるとポイントが高い。

Stamp
□	□
□

初期状態１
Ｘ	〇	〇	Ｘ
〇	〇	〇	〇
〇	〇	〇	〇
Ｘ	〇	〇	Ｘ

初期状態２
〇	〇	〇	Ｘ
〇	〇	Ｘ	〇
〇	Ｘ	〇	〇
Ｘ	〇	〇	〇

初期状態３
〇	Ｘ	〇	〇
Ｘ	〇	Ｘ	〇
〇	Ｘ	〇	Ｘ
Ｘ	〇	Ｘ	〇

初期状態４
〇	Ｘ	〇	Ｘ
Ｘ	〇	〇	〇
〇	〇	〇	Ｘ
Ｘ	〇	Ｘ	〇

（２）次のそれぞれのスタンプを使って、（１）の問題の初期状態のいくつかを解け。ただしスタンプは回転して使っても良い。 A*,深さ優先,広さ優先探索をそれぞれ実行して探索の効率（解に到達するまでのノードの展開数）を比較すること。自分でA*用の効果的なヒューリスティックスを考えて実験してみるとポイントが高い。

Stamp 1
□	□

Stamp 2
□	□
□	□

Stamp 3
□	□	□

Hint1:

Hint2:

Hint3:

（第5問：課題番号05★★★）

ノーベル化学賞

HPモデル格子型構造予測問題

標準的なGA（ダーウィン進化）
ボールドウィン進化型GA：個体の適合度を評価するため、その個体をスタート地点としてとり、局所解に達するまで山登り法などで局所探索を実施する。もとの個体の適合度は上で得られた局所最適解である。しかし子孫を作るときには、局所探索による「学習済み」の改善個体ではなく、オリジナルの個体の遺伝子型が用いられる。
ラマルク進化型GA：ボールドウィン進化と同じく、局所探索を行い適合度を評価する。ただし、局所探索で改良された個体によって子孫が作られる。つまり獲得形質を受け継ぐ。

Hint1:

参考書

Hint2:

配列20 (HP)2PH2PHP2HPH2P2HPH
配列48 P2HP2H2P2H2P5H10P6H2P2H2P2HP2H5
配列48 HPH2P2H4PH3P2H2P2HPH2PHPH2P2H2P3HP8H2
配列48 PHPH2P2HPH3P2H2PH2P3H5P2HPH2(PH)2P4HP2(HP)2
配列48 PH2P6H2P3H3PHP2HPH2(P2H)2P2H2P2H7P2H2

Hint3:

ここ

（第6問：課題番号06★★★）

美しく

個性

例えば、10個の点であれば以下のようなものが考えられる。
進化計算を推奨するが、ニューラルネット、強化学習、その他のAI手法で探索してもよい。
評価関数（「美しさ」の基準、適合度）を工夫すること。例えば、対称性の個数、直線状に並んだ数、思いつきにくさ、希少性、力学的エネルギ―最小化などが考えられる。
個性を生かすことが重要なので、他の点数でも配置可能なもの（円周上、直線上など）はポイントが低い。
他の個数の点でも同じ基準ではできるだけ面白くなってはいけない。
得られた結果がどのように面白いかを考察したかも重視する。
必ずしも最適解(?)が得られなくても成績評価には関係しない。どれだけ工夫したか、考察したかで評価する。
AI探索が目的なので、LLMに聞いたというような解答は原則的に認められない。

Hint:

ここに

（第7問：課題番号07★）ヒトは確率推論が必ずしも得意ではない。またランダム性の認識に関しても間違えやすい。これらのことから、スティーブン・ピンカーは「人間は合理性に反して、ある事象に明確な原因があると断定することがある」と述べている。では、LLM(や生成AI)とヒトはどのように違うのだろうか。これについて、自分の経験や検証実験などを通して考察せよ。
少なすぎるもの・内容がないものは採点しない。
以下のような手順をとること。

（１）LLM(や生成AI)でいくつかの確率的推論を試す。promptや呪文、CoTなどさまざまに試して、答え方の違いや錯覚（hallucination）に注目すること。有名な問題例を直接使うとLLMは訓練例からそのまま回答する可能性があり、有用なデータが得られない。そのため以下のような点を自分で工夫して実験を行うとポイントが高い。
- 複数のLLMでの比較をしてみる
- 温度を変えたり、質問の仕方をかえてみる
- 可能なら図形を利用してマルチモーダルに質問する
（２）ヒトについての生データが以下にある。これらのいくつかを集計・整理する。すべてのデータを利用することはない。各自で取捨選択して回答すること。ヒトのコメントの錯覚部分が重要かもしれない。
（３）以上をもとにして、LLM(や生成AI)とヒトにおける確率推論の類似性・相違点について考察せよ。とくに、スティーブン・ピンカーやダニエル・デネットらの批判（「ベイズ推定や確率モデルをもとにした機械学習や深層学習では強いAIは造れない」）について思うところ（反論もしくは賛同など）を述べよ。
（４）このような実験に関して今後工夫すべき点について考察せよ。例えば、LLMにどのような質問をすればよいか、ヒトに対してどのようなアンケートを集めるべきか、など。

Hint1: ランダム性の錯誤（星座・ヒカリムシとランダムドット）、ギャンブラーの誤謬、ロンドンの爆撃については参考書の3.2節に説明されている。

Hint2: 参考書の2章、3章にある以下のような問題を利用すると良い。このうちの一部についてはアンケートや講義で説明している。当然ながら有名な問題をそのまま利用すると、解答例がLLMにあるので注意すること。
- 乳がんの危険性
- 山田さん夫妻のこども
- 落雷の確率
- ３囚人の問題
- モンティホール問題
- Truel
（第8問：課題番号08★★）

教科書の例題3.2

最初にチェス盤上にチェスの駒が１つ置かれている。
先手はその駒を普通のチェスの動きでどこかへ動かす。
後手もその駒を普通のチェスの動きでどこかへ動かす。ただし前にいたことのあるマス目の再訪は禁じられている。
これを交互に繰り返す。
最初に動けなくなった方が負けである。

ケース１：駒がルーク（将棋の飛車）のとき
ケース２：駒がキング（将棋の王将）のとき

初期状態１


		●

初期状態2



			●

初期状態3



			●

盤面１（５ｘ５）

盤面２（６ｘ６）

講義で説明した以下のプログラムを拡張するとよい。オリジナルな実装でないものは採点しない。

alpha-betaカットのプログラム(Tit-tac-toe)
- gcc common.c ab.c -lm　としてコンパイルする。
min-maxのプログラム(Tit-tac-toe)
- gcc common.c minmax.c -lm　としてコンパイルする。
３次元Tit-for-tat（4x4x4）のプログラム（その１）
- UTC法との対戦を行う。
- コマンドライン引数によってオプションが指定できる。
- ./main [先手:0, 後手:その他(default:0)] [UCTの総playout回数(default:10000)]
- 例) ./main 0 10000
３次元Tit-for-tat（4x4x4）のプログラム（その２）
- UTC法 v.s. min-max(α・βカット)の対戦を行う。
- 実行には引数にplayout数を入れる。
- 評価関数は単純に隅や真ん中が強くなるようにするだけである。

（第9回問：課題番号09★）講義では人間のリスク認知の偏りやヒューリスティックスとしてのプロスペクト理論について説明した。では、LLM(や生成AI)も同じような認知や知覚の偏りを示すのであろうか？実験的に検証してみよう。
少なすぎるもの・内容がないものは採点しない。
以下のような手順をとること。

（１）質問をLLM(や生成AI)に対して行い、promptや呪文・CoTなどさまざまに工夫して答え方の違いを観察する。
とくに無関係な選択肢からの独立性や一億円のチャンスおよび最後通牒ゲームについて面白そうな題材を試すとポイントが高い。
また、講義で説明したフレーミング効果、授かり効果、損失回避、Rabinの定理、アレのパラドクスなどに関する検証をするとよい。
なお、有名な問題例を直接使うとLLMは訓練例からそのまま回答する可能性があり、有用なデータが得られない。そのため自分で工夫した例で検証すること。
（２）（Option）画像を用いたLLMに対して、以下のような実験を行ってどのように心理効果を誘発するかを確かめてみる。
- ブーバ/キキ効果を真似て質問する
- さまざまな錯視の画像を見せる
- スーパーの値引き画像（参照点の比較）、授かり効果などを図で検証する
（３）ヒトのデータと比較して、ヒトとLLM(や生成AI)との認知の相違点・類似性について考察せよ。これらをふまえて、LLMを実世界（金融やマーケットなど）に応用するときの課題・問題点を考慮すると良い。
（４）このような実験に関して今後工夫すべき点について考察せよ。例えば、LLMにどのような質問をすればよいか、ヒトに対してどのようなアンケートを集めるべきか、など。

Hint1: 講義資料はここにある。プロスペクト理論については参考書の６章に、最後通牒ゲームについては同じ本の4.5節において説明されている。
Hint2: ヒトに対するデータは、上の講義資料に書かれている。また関連するアンケートデータは以下にある。適宜集計や編集して使用してほしい。
Hint3: GPTにプロスペクト理論が適応するかについて調べた研究論文がここにある。また、プロスペクト理論を想定した金融やマーケットにLLMを利用する研究はここにある。 LLMにおいてブーバ・キキ効果を検証した論文はここにある。
Hint4: 以下のような点を自分で工夫して実験を行うとポイントが高い。
- 複数のLLMでの比較をしてみる
- 温度を変えたり、質問の仕方をかえてみる
- 可能なら図形を利用してマルチモーダルに質問する
（第10問：課題番号10★★）メタヒューリスティクスには、数多くの手法が提案されている。たとえば以下のようなものがある。これらのいくつかは講義で説明した。
- Artifical Bee Colny (ABC)
- Ant colony optimization (ACO)
- Particle Swarm Optimization (PSO)
- カッコウ探索：Cuckoo search　
- Harmony Search (HS)
- カエル探索：Shuffled Frog-Leaping Algorithm (SFLA)
- Honey-Bee Mating Optimization (HBMO)
- Invasive Weed Optimization (IWO)
- Teaching-Learning-Based Optimization (TLBO)
- ホタル探索：Firefly Algorithm (FA)
- コウモリ探索：Bat Algorithm (BA)
- Plant Propagation Algorithm (PPA)
- Water Cycle Algorithm (WCA)
- Symbiotic Organisms Search (SOS) algorithm
- Harris hawks optimization (HHO)
- Black Hole Algorithm (BHA)
- Fruit fly optimization algorithm (FOA)
- Ant lion optimizer (ALO)
- Moth-flame optimization algorithm (MFO)
- Elephant herding optimization (EHO)
- Coral reef optimization
- Monarch butterfly optimization
- Egyptian Vulture Optimization
- Lion swarm optimization
- ネコ探索：Cat swarm optimization
- ゴキブリ探索：Cockroach Swarm Optimization
- バクテリア探索：Bacterial Foraging Optimization
- 灰色オオカミ探索：Grey Wolf Optimiation (GWO)
- 花火アルゴリズム：fireworks algorithm
- クジラ探索：Whale optimization algorithm
- リス探索：Squirrel search algorithm
- 重力探索：Gravitational search algorithm (GSA)
- ひらめき探索：Brain Storm Optimization (BSO)
- 集団心理療法探索：Group Counseling Optimization (GCO)
なお、メタヒューリスティックス研究に関しては、玉石混交であったり、同じような手法の重複提案であるような批判もなされている。その詳細は『深層学習とメタヒューリスティクスディープ・ニューラルエボリューション（6.8節）』にある。
ここでは、LLM(や生成AI)に基づいて新しいメタヒューリスティックを提案し、実際にコード化をして動作確認をしてみよう。以下の手順にしたがうこと。

（１）LLMにメタヒューリスティックスの例を３～６個程度あげさせて、その詳細について説明してもらう。特定のキーワードをpromptに入れた方がよい。例：大域的探索のため、群知能、組み合わせ探索、など。

（２）（１）であげられたそれぞれのアルゴリズムに関して、重要な特徴や探索性能に影響を与える要素に関して説明させる。それの妥当性について考察せよ。幻覚症状（hallucination）に注意すること。

（３）特定のタスクに対して、（１）であげられたメタヒューリスティックスのハイブリッド版やそれらの改良版を提案させる。それについて説明させ、pseudo-codeやpython codeを出力させる。特定タスクとしては、TSPやNクィーンのような具体的な問題などでよいが、有名な問題には解答例がLLMにあるので面白くない。より一般的な探索問題として指定することを奨励する。
Hint: promptとしては、「多様性を維持せよ」、「exploration(探査)とexploitation(利用)の効果的なバランスをとれ」、「局所解に陥らない」、「目的関数の評価回数をできるだけ少なくする」など講義で説明した探索に重要な要素を入れるのが好ましい。

（４）実際にpseudo-codeを実行させてLLMの提案を検証する。（３）で想定したタスクを実際に解かせてみる。その上で、fatal　error（明確なバグ）があるか・修正可能か、実行レベルでの性能、計算効率、すでにあるメタヒューリスティックスとの比較、などについて考察せよ。

なお、ここではLLMを利用してメタヒューリスティックスのハイブリッド法や新手法を提案することを目指しているので、得られたメタヒューリスティックスが不十分であっても問題ない。むしろ、LLMを利用する場合の有用性や欠点、拡張点を考察してほしい。

Hint1: メタヒューリスティックスについて、最近の解説には以下のような論文がある。
1. Crow Search Algorithm: Theory, Recent Advances, and Applications
2. Sea Lion Optimization Algorithm for Solving the Maximum Flow Problem
Hint2: LLMでメタヒューリスティックスのアルゴリズムを創る論文はここにある。
（第11問：課題番号11★★★）講義ではBoidによる魚や鳥の群れのシミュレーションについて説明した。群れるのは捕食者から逃れるためと思われているが、一方で群集は捕食者から目立つのに群れるのはなぜだろうか。これに関していくつかの仮説が知られている。
- 希釈効果仮説 dilution effect hypothesis
- 攪乱効果仮説 confusion effect hypothesis
- 利己的な群れ仮説 selfish herd hypothesis
ここではシミュレーションでconfusion effectについてシミュレーションで検証してみよう。
以下のようにするとよい。
1. BoidもしくはCouzinアルゴリズムにより小魚（被捕食者）の群れを実装する。
2. そこに大きな魚（捕食者）を導入する。小魚は大魚に対して逃げるようにする。捕食者は小魚よりもスピードを大きくする。
3. 大きな魚が小魚を捕食するアルゴリズムとしては以下の方法を実装する。
  - 捕食者にはある半径の視野がある
  - さらにBlind spotもある
  - 視野内に入った最後の小魚を追う（Hint2の論文のFig.2参照）
4. 小魚のパラメータ（集団数、集団の密度、群れのパラメータ）を変えることで、どのように捕食されるかを観察する。
捕食の成功の度合いを、
- 時間当たりの捕食数
- 最初に捕食に成功するまでの時間
などで計測するとよい。

ただし、必ずしも的確に比較できなくても成績評価には関係しない。どれだけ工夫したか、考察したかで評価する。

Hint1: BoidやCouzinのシミュレーションプログラムは参考書「Unity シミュレーションで学ぶ人工知能と人工生命創って理解するAI」などで提供されている。
Hint2: SwarmとConfusion effectに関するシミュレーション実験に関する論文はここにある。ここでは、大きな魚が最後に視野に入った小魚を追うように設計されている（Fig.2参照）。小魚は大魚からの攻撃を避けるように学習（進化）した結果Swarm現象を創発するようになる。
Hint3: 小魚のパラメータの群れのパラメータとしては、Boidにおけるベクトル和の係数、Couzinのアルゴリズムにおける半径が考えられる。
（第12問：課題番号12★★★）メタヒューリスティックスを用いた多目的最適化のシミュレータを作成せよ。 2次元のパレートフロントをうまくとらえられるかを実験してみよう。
以下のいずれかの手法を１つ以上(できれば２つ)用いること。
- Harmony Search
- Gravitational search
- ホタル探索：Firefly Algorithm (FA)
- Sea Lion Optimization Algorithm
- Lion swarm optimization
講義で説明した多目的最適化のVEGAシミュレータはここにある（java executable file）。またシミュレータの使用方法はここにある。 javaソースファイルははここにある。
以下に述べられている例題か自分で考えた面白い例題を試すこと。パレートフロントが異なる問題（凸型フロント、凹型フロントなど）の実験を行って結果を観察するとよい。
- 多目的最適化例題集
- 多目的最適化の分かりやすい説明と例題のある論文
探索で得られたパレート解の精度に対する評価指標としては以下の2つを用いるとよい。
- 優越個体割合（Ratio of Non-dominated Individuals: RNI）
- 解の多様性の評価指標として被覆率（Cover Rate: CR）詳しくはこの資料を参照。
Hint1: VEGAのアルゴリズムとシミュレータの解説はこの本の5.6節にある。
Hint2: 以下の論文などが参考になる。

提出方法

以下のものを提出すること。提出方法はここに示す通りである。

プログラムを作成した場合、実現したシステムに関する説明（どの部分をどう創意工夫したかなど）。さらにアルゴリズム、ソースリストの説明。
結果の表示（グラフなどを用いると分かりやすい）。
結果に関する考察と評価。
授業に関するコメント、要望など（次回の参考にするので是非書いて下さい）。