スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
このエントリーをはてなブックマークに追加

マリオメーカー学会の研究成果サーベイ【電子計算機部門】

はじめに


本投稿は、日進月歩の進化を続けてきたマリオメーカー計算機の主要な発展を辿り、その全体像を把握することを目的としたサーベイです。
マリオメーカー計算機とは、任天堂より発売された「スーパーマリオメーカー」のコースエディット機能を用いて、足し算を始めとする主要な演算を自動で行うコースのことを指します。
これらの動画の正確な理解には、どうしてもある程度の予備知識が必要となるでしょう。もちろん、それらが無くてもある程度は把握できるように努めますが、より深い理解を求める方は、最低でも二進数と論理回路の知識を必要とします。なぜなら、通常のコンピュータと同様に、マリオメーカー計算機でも0と1の二進数を利用し、論理演算を再現する構造をとるからです。
これらについては、以下にWikipediaのページを挙げますので参考にしてください。
加算器 - Wikipedia
また、発展の主要な部分のみを追っているため、どうしても全ての動画を紹介できないことをお許しください。
以下、「だ・である」調に統一します。

1.黎明期


マリオメーカー学会に初めてマリオメーカー計算機が発表されたのは、out of survice氏の以下の動画であった。

この動画では、コース中に配置されたブロックを破壊することで0を、破壊しないことで1を入力する形式をとっている。出力は、コースに甲羅を走らせ、その甲羅がハテナブロックを叩いたか否かによって表現した。
この形式では、AND演算やOR演算が視覚的に表現しやすく、これらを使った単純な論理回路の構成も容易であった。
しかし、半加算器に不可欠であったXOR演算がひとつの入力のみで表現できず、二箇所に同じ入力を行う必要があるという致命的な欠陥があり、それはそのまま全加算器に引き継がれた。

しかし、2日後にmuratsubo氏が新たな動画を発表し、この欠陥を改善した。

この動画では、無限にクリボーの沸き出る土管を設置し、その土管をブロックで塞ぐという独自の入力方式をとった。ブロックを破壊し、クリボーが沸き出る状態が1で、そうでない時が0である。
この構想の重要なところは、複数体のクリボーがコースを横断するクリボーフローを作ることにより、一箇所の入力で二箇所以上の操作を行うことが可能になった点である。これにより入力の欠陥は改善された。
また、出力もこのクリボーフローがどの位置から流出するかという視覚的にわかりやすい形をとることに成功した。
しかし、同時にコース全体が長くなることで、マリオが少しづつ動く必要があること、そして、画面外のクリボーや仕掛けが消えるもしくは正常に動作しないという問題点も発見された。この段階における対処としては、画面の切れ目に新たな土管を配置し、その入り口をクリボーフローによって操作することでフローを引き継ぐ方法を取っていた。
またこの動画の重要な点として、他人の動画の欠点を修正して計算機の発展に寄与するという、以降のマリオメーカー学会全体の風潮を作り出したことも見逃せない。

これを受け、最初に動画を発表したout of survice氏が、自らのコースを最適化した。

入力の構想はmuratsubo氏のものをそのまま流用している。コースの長さによる問題についても、対処は変化していない。
ここでの独自性として、出力方式の簡易化が挙げられる。ノコノコフローにコインを所定枚数獲得させることで、獲得コイン数による10進法表記を出力とした。この方法は最近の計算機には採用されていないが、優秀ではあり、いずれ顧みられる可能性もある。

ここまでがマリオメーカー計算機の発見~基礎的な考え方の確立までを追った、黎明期といえる部分である。

2.桁数更新期


この時代では、マリオメーカー学会の英雄とも言うべき人物が複数登場し、次々と桁数の革新を行った。
まず大幅に技術革新を行ったのはブルー氏の発表した以下の動画だ。

この動画では入力方式に砲台からメットを発射する形式を用いており、出力方式にはout of survice氏のコイン獲得枚数方式が採用された。メット発射方式はクリボーフローと違って動作が速く、これ以降のスタンダードとなる。
この装置には全体に様々な工夫が見られるが、回路の小型化、回路の端に到達した甲羅を次の回路への入力とする構想、マリオを自動コンベアに乗せることによる画面制御の三点が特に重要である。
これらの特長により、装置を繋ぎ合わせて16bitまでの計算を可能にした。
ただし、桁数の増加に伴って、入力をひたすら手作業で行うことに限界が見え始めた最初の動画でもあった。

少し補足をする。
この時代の特徴として、半加算器や全加算器をXOR演算とAND演算の繋ぎあわせで作成する古典的な方法を棄却し、独自に「加算器の挙動をする回路」を再構成する工夫が盛んになったことがある。
基本的な構想はブルー氏の考案した以下の方法をとる。
・下のメットはそのまま下の回路を走る。
・上のメットは「穴」に落ちて下の回路を走る。
・ただし、メットが下の回路を通ると仕掛けが作動して上の「穴」を塞ぐ。このため両方のメットが発射された場合は上のメットがそのまま上の回路を走る。
・メットが上の回路を走ると、仕掛けが作動して下の回路を進行不能にする。このため両方のメットが発射された場合は上のメットが上の回路を通ることで、下のメットが止まる。
この一連の挙動により半加算器を完全再現する。従来の方法に比べて回路が大幅に短く、一画面で1bitの加算が行える。これにより画面外の挙動に関する問題が一時的に解決された。

次は、未だに第一線で活躍する研究者、doppanpan氏の以下の動画である。

この動画ではブルー氏の方法を最適化し、装置の大幅な小型化に成功した。
これにより32bitの計算が可能となる。
最適化の方法として、いくつかの雲パーツを空間に設置し、その中にメットを飛び回らせることで二次元的に計算を行う「クラウドコンピューティング」が初めて発表された動画でもある。
また移動砲台により装置の挙動を同期させるというアイデアを利用している。

これも少し補足をする。
半加算器の原理としてはブルー氏の方法をクラウドコンピューティングに置き換えただけだが、全加算器の原理として、「メットの相殺」という画期的な挙動が採用されている。これは二つのメットがぶつかると、その両方が消滅するという挙動である。
実は、前述のブルー氏の動画でこの挙動は発見されていた。ブルー氏の研究では相殺を利用してXOR演算を再現できる可能性を指摘していたが、回路の長さのため二つのメットが同期せず、実用を諦めざるを得なかった。しかしdoppanpan氏は移動砲台によって強制的に甲羅を同期させる方法をとり、実用化に成功したのである。

またこの発表により、マリオメーカーの1コースに使うことの出来るパーツ数上限と言う新しい問題が初めて指摘された。
以降、研究者たちの間ではこのパーツ数上限の中で装置を簡略化し、桁数を増加させる挑戦が進むことになる。

4日後、再びdoppannpan氏が動画を発表。これが大きなターニングポイントになった。

この発表では、別の学派である「普通に面白いコースを作って遊ぶ」動画のひとつから着想を得て、入力を何度でもやり直せる「無限スイッチ」の開発に成功した。
この「無限スイッチ」を入力1、入力2、桁上がり入力の三箇所に利用し、一定周期で発射されるメットが三つの無限スイッチによって軌道を変える装置を開発。ここで重要な点は、入力の状態によって桁上がり入力のスイッチを叩き、次の桁に繋げるようにしたことである。
これにより、ひとつの全加算器を半永久的に使いまわす構想を実現した。
出力方式としては、メットの軌道に対応して画面上部にブラックパックンまたはPスイッチのどちらかが流れてくる方法をとった。それがそのまま画面上部に整列していくことで、視覚的にわかりやすい出力表示を得たことは大きい。
しかし、今度はそのブラックパックンとPスイッチの同時出現数上限に阻まれ、34bitの計算に留まった。

また、この発表は、思想的な部分でも重要なターニングポイントになった。
動画の冒頭で、現状のマリオメーカー計算機の問題点を3つに整理し、それぞれを以下のように名付けたのである。
・環境問題:回路の使い捨てによる資源の浪費(パーツ数制限に関する問題)
・人権問題:配管工の劣悪な労働環境(制限時間に関する問題)
・健康問題:出力の見にくさによるストレス(出力表示に関する問題)
この定義付けは研究者の間に、以降の発表で何を目標にすればよいかという指針を与えた。

次に桁数を更新したのは、faidra氏のこの動画である。

この発表ではdoppanpan氏の無限スイッチを使った装置をそのまま流用しているが、出力を工夫することで45bitの計算が可能となった。
予めワンワンを殺害し、それにより残った「ワンワンの杭」がパーツ数に数えられないことを利用して、ブラックパックン側の追加出力に使ったのである。
残りの出力に使うブラックパックンも、ワンワン殺害後に遅延的に生成することで配置数を増やした。
またこの動画で、出力の最終パーツに達したことをEOF(End Of Flowers)と呼ぶ慣習が定着した。

これに研究欲を煽られ、みたびdoppanpan氏が動画を発表。

この動画では、ファイアフラワーの配置数が他の仕掛けとは別にカウントされる「夢の資源」であることを利用している。
この資源は他の仕掛けに重なってしまうという重大な欠点を抱えており、その性質のためにコンベアで運搬することが困難であった。
しかしdoppanpan氏はこれをPスイッチの上に乗せて運搬するという「生け花メソッド」を開発、問題に対処した。
それでもなおコースの時間制限の問題や、65桁を越えたフラワーが溢れる「スタックオーバーフラワー」の問題などが残ったが、この時点で64bitの計算を可能にしており、桁数についての競争はひとまずの収束を見ることとなった。

3.研究期


ひとまずの完成形を見たことで、研究者たちは別の問題に目をつけた。
doppanpan氏の提案した三つの問題、環境問題と人権問題と健康問題である。

まず、そー氏が出力表示の改善を試みた。

これは出力を十進法とするための基礎研究に位置づけられる。
それまでの発表では二進数による表示を人間が読み取る必要があり、なんらかの十進法の表示方法が求められていた。
この発表ではそのうちのひとつの案として、「10進カウンター」と呼ばれる表示方法を考案。
実際にルート2の値を求める(これはマリオメーカーの物理的条件を利用して計測したため、ルート演算が可能となったわけではない)ことで、10進カウンターの効果を実証した。
ただし、これを加算器にどう組み込むかという議論には至っていない。

また表示問題に関しては、ohara氏による7セグ回路(二進数→十進数のデジタル表示に変換する回路)の基礎研究も発表されており、こちらも今後の実用化に期待される。


次に、計算速度に関する基礎研究をfaidra氏が発表した。

これはPスイッチがブロックを一斉にコインに変換する挙動を利用して十個のメットを同期させ、並列計算を行わせる構想である。
ブルー氏の発見したメットの相殺を効率よく用いて、計算速度の短縮ができる可能性を指摘した。
実際にこれを使った回路をfaidra氏本人が実装している。

桁数は最高記録の64bitに届かないものの、計算速度については大幅な革新といえる。

次に再びそー氏が動画を発表。

これまでの計算機では入力と出力で0と1を表す方式が異なっていたことを問題視し、これらを統一する方法を考案した。
その中で、ブラックパックンとPOWブロックの物理的挙動が異なることを発見。これを入力方式として加算器を実装し、出力にもこれらを使うことでフォーマットを統一した。
また、出力結果を回収することで永久的に加算器が動かせる状態を実現した。
さらに、出力結果をコピーする別の回路を作成。これらを組み合わせることで「計算結果を再び入力に代入する」再帰計算が可能であることを示し、具体的にいくつかの漸化式からその数列の値を求めて見せた。
そー氏は16日後にこの回路を小型化・高速化し、時間制限の壁を緩和している。


まとめ


マリオメーカー計算機は日進月歩の世界であり、これからも技術革新が続くことが期待される。
現時点で、64bitの加算が可能であり、桁数は少ないが乗算回路も発表されている。

今後の方針としては、以下のようにまとめられるだろう。
・パーツ数上限、時間制限への対策
・出力表示の改善
・ひとつの装置の再帰的利用や複数の装置を繋ぐことによる、より複雑な演算の実現
・上記を満たしながら桁数をどこまで落とさずに実装できるか
これらの課題については先行する基礎研究が複数発表されているため、それらをどう活かすかという議論になるだろう。
また先日、マリオメーカーのアップデートにより、中間地点など新たな要素が追加されたこともあり、より斬新な装置の開発も待望される。
マリオメーカー学会の今後の発展に期待したい。
関連記事
スポンサーサイト
このエントリーをはてなブックマークに追加

コメントの投稿

管理者にだけ表示を許可する
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。