ペーパーマリオのバトル（パズル）をアルゴリズムで解く

アルゴリズム

※ この記事は、ゲーム進行が（任天堂の意図しない形で）不正に有利になる遊び方を推奨するものではありません。また、本記事の内容を実践したことによって生じたいかなる損害も保証しかねます。

ペーパーマリオオリガミキングが面白そうな件

今年の夏休みはコロナ禍で帰省もできなくて暇だなぁ……。

こんなときはゲームで遊ぼう。

ペーパーマリオが面白いらしいよ。

え、、

もしかして、買ったの？

いや、人が遊んでいるのを見ているだけなんだけど、バトルがパズルなんだよねこれ。

www.youtube.com

どういうルールなの？

敵をスライドさせて、どちらかのパターンを作る。

❶ 敵4体の塊を1列に整列させる

❷ ステージの内周に2行2列に整列させる

ふむ。

きちんと揃えないと、マリオの攻撃が届かないんだよ。

子供向けのゲームだろうし、じっくり考えればいけそうだね。

ところが、時間制限と回数制限があって、熟考もできなければ試行錯誤もできない。

ロジカルな思考力だけじゃなく、ひらめきも大事。

これを30秒以内に閃いて解けといわれたら、解けない自信がある。

時間制限があると、「既に出来上がっているものを壊したくない心理」が勝ってしまうのだ。

納期ギリギリで、品質はクソだけどせっかくここまでプログラムができてるからなんとか既存部を生かそうとして、結局死ぬパターンに似ている。
— たーせる (@tercel_s) August 8, 2020

なにこれむずいじゃん。

むずかしいよ。

ザコ戦のバトルが毎回コレなので、なんとかコンピュータにパズルを解かせることはできないかなと思って、ちょっと考えてみたんだ。

ペーパーマリオオリガミキングザコ戦パズル解法アルゴリズム（草案）

f:id:tercel_s:20200809170201j:plain
f:id:tercel_s:20200809170228j:plain

なにこれ……やば。

やばくないよ。

基本情報技術者試験によく出る探索アルゴリズムを応用したものだよ。

こういう探索アルゴリズムってどうやって実装するの？

for ループだとネストがどんどん深くなりそう。

こういうのは for 文で書いちゃダメで、再帰処理を使って実装するんだよ。

プログラミング言語の入門書にはあまり載っていないテクニックで、どちらかというとアルゴリズムとデータ構造の本によく出てくるね。

再帰処理かー……。

あれって鬼門だよね。苦手な学生も多かったし……。

機会があれば、実装例も載せて再帰処理の勘所を紹介したいのだけど、あいにく身に付けたところで使いどころが限られているからね、、、

再帰的データ構造と Composite パターン

再帰処理と相性のよいデータ構造には、木やグラフといったデータ構造があるよ。

あるね。

配列やリストは、データ同士の繋がりも分かりやすいし、多くのプログラム言語がサポートしているけど、木構造のデータってどう表現するの？

それについては昔、すごい雑な記事を書いた気がする……。

tercel-tech.hatenablog.com

構文として木構造をサポートしている言語は無いの？

Lisp とかはサポートしてた気がする……。

そういえば、Common Lisp では、実行時のパフォーマンスを上げるために、再帰呼び出しが関数の末尾にくるように最適化したりするけど、まぁその話は今関係ないからいいや。

もっとメジャーな言語でお願いします。

それでいうと、C++とかJavaとか、その派生言語であれば「再帰的なデータ構造はこうやってクラス設計しましょう」という方法論は確立されているよ。

Composite パターンって言うんだ。

なるほど。

このへんをしっかり学びたければ、デザインパターンの本を読んでみよう。

最近は拡大解釈され過ぎて、「インフラデザインパターン」とか「クラウドデザインパターン」とかネコも杓子もデザインパターンという用語が濫用されがちだけど、ここでは「オブジェクト指向における再利用のためのデザインパターン」だよ。

ソフトウェア工学の分野のデザインパターンだね。

というか、マリオの話をしていたはずなのにどうしてここまで脱線したのか。

いつもの事だね。

おまけ

ペーパーマリオ、ストーリーが素晴らしくて、ラストでうるっときました。

危うく泣くところでした。

2020-07-29

1 on 1

雑記

エニアグラム診断

ねぇねぇ、なにやってるの？

エニアグラム診断というやつだよ。

性格診断みたいなやつ。

珍しいね。

たーせるくんは普段そういうのを絶対にやらないのに。

ちょっと上司と面談をして、自分が大事にしている価値観はいったい何なのかを、ふと探ってみたくなったんだ……。

ふむ……。

で、どうだった？

一応、こんな結果が出たんだけど……。

f:id:tercel_s:20200729204110p:plain:w300

わぁ。わりと特徴的な結果が出たね。

統率者を除いて、けっこうオールラウンダーみたいな。

この結果は、けっこう自分自身を象徴している気がして、実は気に入っているんだ。

思い返せば、もくもく型だけど、相性のよい人とはどこまでも仲良くなるな……と。

Udemy for Business

そうそう、そういえば、たーせるくんの会社は、Udemy for Business に加入しているから、申し込めばタダで講座を受けまくれるらしいよ。

まじか。

知らなかった。

ボクも今日知った。

自腹で受けた AWS 資格対策講座に 1,500円も払っちゃったよ……。

超ドンマイ。

まぁ1発で受かったからいいじゃん。

2020-07-25

Angularでガラクタを作ったのでゆるく紹介するお話

Angular

そういえば、このブログってけっこう見た目が凝っている気がするけど、どうやって更新してるの？

実はね、タグを一つひとつ手打ちしているんだ。

匠の技で。

まじか……。

そりゃ更新も億劫になるよ……。

さすがに非効率極まりないなと思ったので、思い立って自分用のツールを作ってみたんだ。

このツールにそっくりなものが夢に出てきて、そこからインスパイアされて3時間くらいで作った。

3時間で作れるなら、なぜ今まで作らずにいたのか……。

我ながらなかなかいい感じにできたので、動画を撮っちゃった。

作る様子ではなく、作ったツールを操作する様子なんだけど。

通知めっちゃうるさいなｗｗｗ

ていうかドラッグ & ドロップすごいね。

ドラッグ & ドロップは Angular/CDK のお陰だよ。

未だに Angular が好きな理由は、こういうコンポーネント開発用のユーティリティが充実しているから。

ふむ……。

おもしろいね。

あと、こだわりポイントとしては……

まだあるの？

僕たち、実はレスポンシブ対応している。

レスポンシブというと、一般的には CSS の @media クエリを用いるのが定石なんだけど、HTML のスタイル属性には残念ながら使えない。

はてなブログって CSS を書けないんだっけ？

書けるけど、テーマによってはPC用とスマホ用で読まれる CSS が異なったり、無料プランだとスマホ向け CSS が制限されたり、いろいろ面倒なのだよ。

ふむ。

そこで代替手段として、The Fab Four technique と呼ばれる技法を用いて、@media クエリ無しでレスポンシブを実現している。

この話はいつかしようと思っていたのだけど。

あ、なんか話がヘンな方向に脱線しそうだから、そろそろいいです。

おやすみなさい。

えぇ……（せっかくいいところだったのに）。

2020-07-24

正規分布の確率密度関数を -∞ から +∞ にかけて積分すると、結果が1になる件について（小ネタ）

数学

このへんの続き。

tercel-tech.hatenablog.com

ところで、正規分布の裾野ってどこまで広がっているの？

無限に、どこまでも、果てしなく広がっているよ。

え……、それっておかしくない？

だって、-∞ から +∞ にかけて積分すると面積 1 になるんだよね？

図形として閉じていないと、そもそも面積って求められないのでは……？

これは、無限に広がる図形の面積をいきなりイメージすると混乱するので、まずは有限の積分区間から考える。

直感的には、積分区間を広げれば広げるほど、1に限りなく近づいていくので、「きっと積分区間を -∞ から +∞ に広げたら、行き着く先は1なんだろうな」というイメージ。

ふむー……。

2020-07-12

AWSソリューションアーキテクトアソシエイト受けました（そして受かった）

AWS

以前、「AWS の試験を受ける」という記事を上げたきりブログの更新を放置していましたが、1週間ほど前に合格してました。わーい。

認定証っぽいのもらったーわーい∩( ･ω･)∩ pic.twitter.com/fQUkmJuUww
— たーせる (@tercel_s) 2020年7月6日

以上、ご報告まで。

2020-07-05

統計のお話（正規分布と母集団と標本について）

数学

コロナのせいで引きこもり生活を始めたばかりの頃、密かに統計のお勉強をしていた。

まだほんの序盤ではあるが、なかなか楽しい学問であり、学生時代にもう少し学んでおけばよかったと思った。

復習と数学的準備

反復試行の確率

1回の試行で、事象 ${A}$ が起こる確率を ${p}$ とおくと、事象 ${A}$ が起こらない確率 ${q}$ は ${q = 1 - p}$ となる。

この試行を ${n}$ 回行って、そのうち ${k}$ 回だけ事象 ${A}$ が起こる確率 ${P_{k}}$ は、 ${ P_{k} = {}_{n} \mathrm{C}_{k} p^{k} q^{n-k} }$ である。

二項分布

ここで、確率変数 ${ X = k }$ とおくと、 ${P_{k}}$ はそのまま確率関数となり、離散型の確率分布が定まる。

この確率分布を 二項分布 と呼び、 ${B(n,\,p)}$ で表す。

正規分布

二項分布 ${B(n,\,p)}$ の ${n}$ を ${\infty }$ に近付けると、最終的に 正規分布 と呼ばれる連続型の確率分布になる。

正規分布は、その期待値 ${\mu}$ と分散 ${ \sigma^{2}}$ を用いて、 ${N(\mu,\,\sigma^{2})}$ と表す。

確率密度関数（積分すると確率になる関数）は ${ f_{N} (x) = \displaystyle\frac{1}{ \sqrt{ 2 \pi } \sigma } e^{ - \displaystyle\frac{ ( x - \mu )^{2} }{ 2 \sigma^{2} } } }$ である。

ちなみに、この正規分布の確率密度関数の導出はちょっと難しい。

せめてヒントだけでも！！

わかったよ。これ知ってる？

${x}$ が十分大きいときに ${ \displaystyle\frac{ \log (x!)}{dx} \sim \log (x) }$ と近似できること
${ \displaystyle\int_{-\infty}^{\infty} e^{- \displaystyle\frac{x^{2}}{2}} dx = \sqrt{2 \pi} }$ であること

なんで $ \int_{-\infty}^{\infty} e^{- \frac{x^{2}}{2}} dx = \sqrt{2 \pi} $ になるの？

これはガウス積分といって、大学の試験で出題されるレベルなので、ちょっとここでは……。

やだやだ！知りたい！！

いきなり $ \int_{-\infty}^{\infty} e^{- \frac{x^{2}}{2}} dx $ を求める前に、こんな重積分 $ \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} e^{-x^{2}-y^{2}} dx dy $ を考えてみようか。

あ、これ、極座標変換しないと苦しいやつだ。

そうだね。

頑張って計算すると、$ \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} e^{-x^{2}-y^{2}} dx dy = \pi $ になる。

左辺を式変形すると、$ \left( \int_{-\infty}^{\infty} e^{ -x^{2} } dx \right)^{2} $ となり、さらに両辺のルートを取ると $ \int_{-\infty}^{\infty} e^{ -x^{2} } dx = \sqrt{\pi} $ になる。

あ、、$ \pi $ が出てきた。

あとは $ x = \frac{z}{ \sqrt{2}} $、$ \frac{dx}{ dz} = \frac{1}{\sqrt{2}} $ で置換して $ z $ で積分するといいよ。

なるほど……（思った以上にめんどくさい）。

身に付けておきたい考え方

離散型確率分布と連続型確率分布

動いている時計をカメラで撮ったとき、秒針がちょうど文字盤の真上（0秒地点）にある瞬間にシャッターが切れる確率について考える。

実は、その時計がチクタクと動いて離散的に時を刻むタイプかヌルヌルと止まらずに動き続けるタイプかで確率が変わってくる。

チクタクと動く場合は ${\displaystyle\frac{1}{60}}$ だが、ヌルヌル動く連続型の場合、円周上の無限にある点のうちの一点を指す確率になるので、 ${\displaystyle\frac{1}{\infty} = 0}$ になる。

連続型確率分布を扱う場合、確率変数は点ではなく範囲で考える。

つまり、0秒ぴったりを指す確率は ${0}$ だが、0秒〜15秒のどこかに入る確率は ${\displaystyle\frac{1}{4}}$ である。

この 0秒〜15秒という範囲の中に、0秒や15秒といった境界値を含むか含まないは考えなくてよい。なぜなら、含もうが含むまいが、0秒（もしくは15秒）ぴったりになる確率はどうせ ${0}$ だからだ。

母集団と標本

巨大な母集団から、無作為に ${n}$ 個の標本 ${X_{1},\, X_{2},\, \cdots ,\, X_{n}}$ を取り出すことを考える。

ここで、 ${X_{i}}$ を標本の取り方によって変化する確率変数と見なす。

母集団は非常に巨大なので、 ${X_{1}}$ を抽出したとしても、それ以外の標本の要素の抽出結果に影響を与えない。

よって、 ${X_{1},\, X_{2},\, \cdots ,\, X_{n}}$ は、同一の確率分布に従う母集団から、それぞれ個別に抽出された、互いに独立な確率変数と見なすことができる。

いきなり訳がわからなくなったぞ。

標本が、確率変数？？

まぁ、あれだよ。

たとえば動いている時計をカメラで 100 回撮って、その秒針が指す位置を記録するとするでしょ？

うん。

そうすると、100回分の記録が取れるでしょ？

うん。

その100回分の記録が入る変数を、$X_{1} , \, X_{2}, \, \cdots , \, X_{100}$ で表すイメージ。

独立な変数って、どういうこと？

すごく雑な説明なんだけど、$ X_{1},\, X_{2},\, \cdots ,\, X_{n} $ が、他のどの変数を使っても書き表せないことだね。

どういうこと？

たとえば $ X_{3} = 2 X_{1} + 5X_{2} $ みたいに、他の変数を使って表現できる場合、それらは独立ではないんだ。

あれ、、ちょっと混乱したかも。

「時計の写真を100回撮る操作」を何回も何回も繰り返せば、偶然たまたま $ X_{3} = 2 X_{1} + 5X_{2} $ が成り立っちゃうこともあるんじゃない？

標本を取るたび、$ X_{1},\, X_{2}, \, X_{3} $ は毎回変わるでしょ？

$ X_{3} = 2 X_{1} + 5X_{2} $ は、確率変数の中身が何であっても成り立つという意味だから。

そうか、、確かに $ X_{1},\, X_{2} $ の結果で $ X_{3} $ が常に決まるわけではないもんね……。

そうそう。

確率変数 $ X_{1},\, X_{2},\, \cdots ,\, X_{n} $ が、ほかのどの確率変数を使っても書き表せない場合、独立な確率変数って言うんだ。

もう一つ質問。

母集団って離散型なの？連続型なの？

えーっと、厳密には離散型なんだけど、ほぼ連続型と考えていい。

でも、もはや離散値として扱いきれなくなっていることが多いから、連続型の確率分布に従うものと見なしてしまうね。

でも、さっきの話だと、連続型の場合は確率変数を点で考えちゃダメなんだよね？

確率がゼロになっちゃうから。

ボクも極限について厳密に理解しているわけではないので、ここはもうフィーリングになっちゃう。

限りなく連続型に近いんだけど実は離散型だから、標本 $ X_{i} $ を取ってきて、その実現値を確認することができるのだと都合よく考えている。

ふむ……。

2020-06-20

Former2 と CloudFormation の話 #AWS

AWS

TL; DR

Former2 というツールを使うと、既に構築済みの AWS リソースの設定情報をエクスポートできるよ。

これを、AWS の CloudFormation に喰わせば、インフラを簡単に再構築できるんだ。

ふむ……？（それのなにが便利なんだろう）

Former2

ナイスな導入

AWS には、たーせるくんのようにインフラの素人でも簡単にネットワークを構築したりサーバを立てたりできる GUI が整っているでしょ。

いわゆるマネジメントコンソールってやつだね。

そうそれ。

ただ、場合によってはマネジメントコンソールではなく、設定ファイルからリソースを一括で自動作成する方が早いこともあるんだよ。

さらば憂鬱すぎるやり直し作業

ところで、キミのその設定、なんかおかしくない？

ああああ…… CloudWatch で監視設定したら、アラーム名をタイポしてしまった……。

一度設定したアラーム名はもう変更できないから、もう一度はじめからやり直しになっちゃう……。

ドジっ子さんめ。再作成が1つや2つならいいけど、10個、20個になるとキツいね。

マネジメントコンソールの GUI をチマチマ操作する作業を何十回も繰り返すのは切ない。

やる気なくすわー。

せめて現状の設定内容をテキストにエクスポートして、アラーム名を grepグレップで文字列置換して、再度インポートできればラクなのに。

それなら Former2 を使えば AWS リソースの設定内容をエクスポートできるよ。

なるほど！

エクスポートした設定はどんな形式になるの？

YAMLヤムルという一種のテキスト形式だね。

テキストエディタで編集もできるし、AWS の CloudFormation というインフラ自動化サービスを使えば同じ設定のリソースを一括作成できる。

それはすごい。

まさしく僕が求めていたものだ。

Former2 は、サードパーティ製ツール

ちなみに Former2 は公式ツールではなく、サードパーティ製のツールなんだ。

公式じゃないのか……。

一応、公式にも CloudFormer というツールがあるにはあるけど、ずっとベータ版だし、もうアップデートされる見込みはないし、公式が Former2 を使えと言っているくらいだし……。

必要なのは、ReadOnlyAccess ポリシーを持つ IAM ユーザ

Former2 はものすごく直感的に使えるので、改めてここで手順を説明するほどでもないんだけど、注意点が2つあるんだ。

一つはリージョンを間違えないこと、そしてもう一つは実行用の IAM ユーザを用意する必要があること。

ユーザ……？

Former2 を使うには、ReadOnlyAccess という権限を持った IAM ユーザが必要なんだ。

既存のユーザを使うのはダメなの？

アクセスキーとシークレットアクセスキーを委ねてしまうし、不運に不幸が重ならないとも限らないので、使い捨ての IAM ユーザを用意した方がいいね。

スタックを削除すると、作成したリソースも道連れになる

CloudFormation を使ってリソースを作成するには、最初にスタックというものを作る必要があるんだ。

スタックは、リソースを作り終えたあとは消していいの？

それを消すと、リソースも一緒に消えるよ。

もし、スタックを消してもリソースを残したい場合は、設定ファイルのリソースのところに DeletionPolicy 属性を明示的に設定しないとダメだよ。

AWSTemplateFormatVersion: '2010-09-09'
Resources:
  myS3Bucket:
    Type: AWS::S3::Bucket
    DeletionPolicy: Retain

まぁ、せっかく CloudFormation の管理下にあるリソースを、管理から外してしまうのはどうなんだろ。

設定ファイルにはインスタンス ID とかがベタで書かれていたりするので、いまいち長持ちしない気がするけどね。

もともと手作りしたリソースだったら、DeletionPolicy 属性を Retain にして、スタックは消しておいた方が地球に優しいと思う。

今日のまとめ

既存のリソースをエクスポートしたいときは Former2 を使おう。

マネジメントコンソールで同じ設定作業を何度も繰り返しているなーと思ったら、自動化を検討した方がいいね。

マネジメントコンソールの手順書を作って、「この設定を100箇所に適用して」と人にお願いするくらいなら、テンプレート化して自動生成して機械にやらせる方がみんな幸せになりそう。

単純な定型作業はできるだけ自動化して、僕たちは開発に集中したいよね。

それでは今日はこの辺で。

ではでは。

ペーパーマリオ オリガミキングが面白そうな件

ペーパーマリオ オリガミキング ザコ戦パズル解法アルゴリズム（草案）

再帰的データ構造と Composite パターン

おまけ

エニアグラム診断

Udemy for Business

復習と数学的準備

反復試行の確率

二項分布

身に付けておきたい考え方

離散型確率分布と連続型確率分布

母集団と標本

TL; DR

ナイスな導入

さらば憂鬱すぎるやり直し作業

Former2 は、サードパーティ製ツール

必要なのは、ReadOnlyAccess ポリシーを持つ IAM ユーザ

スタックを削除すると、作成したリソースも道連れになる

今日のまとめ

ペーパーマリオオリガミキングが面白そうな件

ペーパーマリオオリガミキングザコ戦パズル解法アルゴリズム（草案）