プロローグ

「みすちゃんは辛いものが大好き」ーーそう持てはやされたのはいつのころのことだったか。辛いものが大好きだったMISWのみんなはいつしかぎやに行かなくなってしまった。アフターでぎやに向かった賑やかな日々が懐かしい。今やぎやへの道のりすら、思い出せないのだ。それでもやっぱりみすちゃんはぎやに行きたかった。

ぎやへの道のりは遠く

みすちゃんはぎやに辿り着きたい。そのためには手段を厭んでいる余裕はないのだ。

ぎやへの道のりは遠く、多くの障害物に阻まれている。
みすちゃんには上下左右のどちらに進んでいいか分からない。ぎやへの道程を覚えていないからだ。
みすちゃんはぎやにどれくらい近づいているか感じ取ることができる。辛いものには敏感なのだ。
みすちゃんには能力があり、あったかもしれない他の可能性の自分の記憶を呼び出したり¹、世界線を超えて変動前の世界線の記憶を失わずに保持したりすることができる²。
みすちゃんには時間がない。活動終了後からぎやが閉店するまでの僅かな時間で辿り着かなければならないのだ。

みすちゃんは赤い部分のぎやを目指す。茶色い部分は壁になっていて残念ながら進むことができない。0/400はみすちゃんが移動した回数を表し、400回移動し400/400になってもぎやに辿り着けないとぎやが閉店してしまう。そうしたとき、みすちゃんは自らの能力で世界線を超えて（世代を重ねて）もう一度始めからやりなおすのだ。 f:id:shira7867:20180408205701p:plain 移動中は以下のように分身したような見た目になるが、これはみすちゃんが複数の可能性について同時に検証している様子を表している。このそれぞれの可能性について、みすちゃんはどういう方向に進むとどれくらいぎやに近づくことができたか記憶することができ、ぎやに辿り着けなかった場合もその記憶を引き継いで、次世代の行動指針に役立てることができるのだ（みすちゃんは賢い）。 f:id:shira7867:20180408211023p:plain

辿り着きたい場所、掴み取りたい未来がある～ダイバージェンス1%の向こう側へ～

第1世代

なにも始めから上手く行くとは思っていない。不思議と絶望感はなかった。寧ろもしかしたらと僅かでも期待をしていた自分の甘さに腹が立った。先はまだまだ長い、根気よく諦めずに行こう。 f:id:shira7867:20180408235125p:plain

第10世代

ーー何度繰り返せばぎやに辿り着くことができるのか。一向に近づく気配のなさにみすちゃんはいわれのない不安を感じ始めていた。本当にぎやに辿り着くことができるのか、もうダメなんじゃないか。胸がはちきれそうになった。でもそんなとき胸に浮かんできたのは、辛いものを美味しそうに食べるMISWのみんなの笑顔。あの光景は過去のものになってしまったけど、無かったことになんかさせない。絶対に諦めない。 f:id:shira7867:20180408235156p:plain

第36世代

あれから長い時間が経った。まだまだぎやには届かないけど、みすちゃんは手応えを感じ初めていた。ぎやは確実に近づいている。 f:id:shira7867:20180408235224p:plain

第59世代

もう何度同じ時を繰り返したのか、分からなかった。着実に近づいているということだけがみすちゃんにとって救いだった。あともう一歩、あともう少し。 f:id:shira7867:20180408235613p:plain

第64世代

みすちゃんは遂にぎやに辿り着いた。 f:id:shira7867:20180408235303p:plain 「辛〜めん１つ」久々に食べるぎやはやっぱり辛くて、涙がこぼれ落ちた。それは辛さからか、辿り着いた喜びからか、みんなと来ることができなかった悲しさからか、みすちゃんにも分からなかった。
〜FIN〜

解説

ふざけてスミマセン。新入生の皆さんこんにちは、51代のしらすです。プログラミング研究会に所属しています。今回は遺伝的アルゴリズムを用いてキャラクターをある地点まで自動的に移動させることが出来るかというものでした。遺伝的アルゴリズムとはパラメータを遺伝子に見立ててランダムなパラメータで作成した遺伝子を、選択・交叉・突然変異の操作を繰り返していると、自然に見られる進化の過程と同様に問題に適した解が自然に求まるというものです。遺伝的アルゴリズムについては世の中にごまんと素晴らしい記事があるので説明は省きます。特に以下のスライドが分かりやすかったです。

遺伝的アルゴリズム（Genetic Algorithm）を始めよう！ from Kazuhide Okamura

www.slideshare.net

今回の場合、みすちゃんの上下左右の移動を遺伝子に見立てました。遺伝子が優れているかどうかを評価するものを適応度関数と呼びますが、みすちゃんとぎやとの直線距離の逆数を適応度として、適応度を最大化するように適応度関数を設定しました。行動回数制限のある中でぎやに近づけたほど適応度が高くなります。みすちゃんが分身して見えたのは、遺伝子のシミュレーションを１世代に含まれる遺伝子は同時に行っていたからです。「あったかもしれない他の可能性」というのは同一世代の自分以外の遺伝子を指し、「世界線を移動する」というのは世代を更新するということに見立てていました（何をやっているのか）。実装はProcessingで行いました。ソースコードは記事末尾につけておきます。一世代あたり20の遺伝子があり、ルーレット選択・１点交叉で次世代を決定します。ここで結果が良かった遺伝子ほど次世代で優遇されるので、世代を重ねる毎に徐々に結果が改善していきました。かなりエグい感じになってしまったのと、選択・交叉の方針が賢くないので、これから遺伝的アルゴリズムをやってみようという人にとってはあまり参考にはならないと思います。

さいごに

プロもすなる遺伝的アルゴリズムといふものを情弱もしてみむとてするなり、という感じでヘナヘナな実装になってしまいましたが、日曜日を１日潰してやったので一人ハッカソンという感じがしてとても楽しかったです。また、今回プログラムを作るにあたってみすちゃんのドット絵を51代のおいなりから提供してもらいました！ありがとう！最後にプログラム実行中の動画をつけておきます。

youtu.be