NandGame が面白過ぎて年末年始ハマった

NandGame のすすめ

皆さん NandGame と言うゲームを御存じだろうか。
名前の通り Nand を使ったゲームである。内容は Nand ゲートから始めて徐々に複雑な論理回路部品を構成していき、最終的にコンピュータっぽいものを完成させるというものである。

昨年 12 月あたりに Gigazine でも紹介されてたし、ご存知の方も多いのではないかと思うが、もし知らなかった、あるいは、知ってたがやってはいないと言う方は、ちょっとでも論理回路に興味があったり論理回路に興味はなくてもパズルゲームが好きだったりするのであれば是非やってみて欲しい。絶対面白いから。

と言うわけで（？）年末年始ハマってしまった。いや、ドはまりした。もしかしたらこのゲームをやった事がある方はどこにそんなにハマる要素があるのか不思議に思うかもしれない。やってみたらさっくり解けてしまって、私の鳥頭具合が丁度よかっただけなのではないかと思われるかもしれない。（いや実際その可能性は捨てきれないが…）

だが本当に面白いのだ。この面白さは私如きでは説明しきれないのでとにかくぜひやってみて欲しい（2 回目）。あまりにも気に入ったので寄付をしようかと思ったのだが、残念ながら PayPal で寄付しようとしたらお前の国からは寄付出来ないと言われてしまい、Bitcoin も持っていないため断念した…（何か他に良い方法は無いだろうか…

ちなみに、組み立てていく論理回路は必須のものが 28 種類、任意の物が 4 種類ある。それぞれカテゴライズされていて、必須は Logic Gates → Arithmetics → Plumbing → Memory → Arithmetic Logic Unit → Processor の 6 カテゴリ、任意は Logic → Arithmetics の 2 カテゴリある。前から順に組み立てていくのであるが、前段をクリアしていなくても Levels タブをクリックすれば名前だけはいつでも見える。

で、ゲームの面白さを説明出来ないくせに何でこんな物を書いているかと言うと、ゲームをクリアした成果を披露しつつ出来れば皆さんのお知恵を拝借したいと思ったからだ（なぜ拝借する必要があるのかは下記を見れば分かると思う）。と言うわけで、ここからはがっつりネタバレになってしまうので、まだやってない方は是非最後までゲームを楽しんでからこの先を読んで欲しい（3 回目）。

それでは、早速成果を書いていこうと思う。
（ちなみに、これを書くために 3 度目の挑戦をしている）

Logic Gates

Logic Gates カテゴリでは基本的な論理回路、Invert（Not）、And、Or、Xor を構成する。
と言ってもこれらはどれも簡単に構成できるので、特段取り上げるようなものはないだろう。

Arithmetics

Arithmetics カテゴリからようやく計算機っぽくなってくる。

Half Adder

半加算器である。1 ビット＋ 1 ビットの答えを 2 ビットで出すのである。
まぁ愚直に考えて上位桁は And で、下位桁は Xor でやる。

オーケー、正解だ。
だがちょっと待って欲しい。カッコ内に但し書きがある。

そう、オマエの回路は Nand 使い過ぎだとダメ出しされているのである。
オーケー、分かった。そっちがその気ならこちらにも考えがある。きっちり落とし前を付けてやろうじゃないか（ちなみにこれが原因でハマったのである）。
上の解は軟弱にも構成済み回路を使い過ぎてしまったから Nand 過多になってしまったのだ。であれば、これらを分解してから再構成すれば良いだけの話だ。
と言うわけで作ったのがこちら。

オーケー、今度こそ間違いなく正解だ。

Full Adder

全加算器である。1 ビット＋ 1 ビット + キャリーの答えを 2 ビットで出すのである。
こちらも半加算器 2 つと Or で簡単に構成可能だ。

まぁ予想通りだ。これも分解して再構成だ。

絵面的にちょっと厳しくなってきたが許して欲しい。これで正解だ。

Multi-bit Adder

複数ビットの加算器である。ここでは 2 ビットなので全加算器 2 つで構成できる。
で、愚直に構成すると、18 Nand で特に何も文句を言われない。

もしかしたらもうちょっと良い（少ない Nand での）構成もあるのかもしれないが、思いつかなかったのでそのままとした。
もし良い構成方法があれば是非教えて欲しい。
ちなみに、ホンモノ（？）の加算器の場合キャリールックアヘッドしたりするのかもしれないが、そんなことしていると Nand が増える一方なのでここではガン無視する。

Increment

インクリメントである。ここから突然演算対象が 16 ビットになる。そしてツールボックスに 16 ビットの加算器とゼロが生えている。
従って、インクリメントは簡単に構成できる。

折角ツールボックスにゼロが生えてはいるが、接続しないとゼロになるので使わなくても良い（使っても Nand 数が増えたりはしない）。
で、これも 145 Nand で特に何も文句を言われない。
だかちょっと待って欲しい（2 回目）。16 ビット同士の加算器を使っておきながら、片方は常にゼロ、辛うじてキャリー入力を使うだけになってしまっている。これはどう考えても Nand の浪費である。こんな事が許されて良いのだろうか。いや良いはずがない（反語）。

と言うわけで、まず入力の 16 ビットを 1 ビットずつに分解して半加算器で足し上げていきたい。
のだが、左のツールボックスを見ると、何と入力をバラすことも出来そうになければ半加算器も無い。

そんなバカな、と考えているところで、ふと上に「Custom Components」と言うタブがある事に気付いた。
行ってみると、名前の通り自分で構成済み論理回路部品を作れるのだが、何とここに所望の分解器や半加算器もある。よし、これで勝てる！
と言うわけで、まずはここで全部作ってしまうことにした。それがこれ。

絵面がだいぶ酷いことになっているが、16 個も半加算器を使ってるので許して欲しい。
そしてこの自作部品に hinc 16（半加算器 16 個で作ったから）と名付けた後、これを使った（と言うか置いただけの） Increment がこれ。

Nand 145 が 81 まで減った！しかも何故か "the simplest possible solution!" とか言われてる。自作部品 1 つなんだから確かにこれだけ見ればシンプルっちゃあシンプルだが、それでいいのか？

それはさておき、再度先程構築した hinc 16 をよくよく見てみると、まだまだムダがありそうであり、このままだと Dio 様にタコ殴りにされそうである。
まず、最下位ビットの半加算器は片方のビットが 1 固定なので、明らかに簡略化可能である。ウンウン唸って考えてみると、出力の最下位ビットは入力を反転してるだけ、最下位からのキャリーは入力そのままである。
また、最上位ビットの半加算器はキャリーは生成するだけしてどこにも使われていない。つまりこれは Xor だけで良い。
と言うわけでそれらを組み込んだ hinc 16 がこれ。

そして、絵面は全く変わってないが、Increment の結果がこれ。

75 まで減った！初期の 145 からするとおおよそ半分だ、勝った！
もしこれより減らせたら是非教えて欲しい。
ところで完全にどうでもいい話だが、各種アセンブラではインクリメントを inc と書くことが多いせいで、外国の社名にあるなんちゃら Inc. と言うのを見るとなんちゃらインクリメントとしか読めない呪いにかかっている。

Subtraction

16 ビット減算器である。加算器が Adder なのに何で減算器は Subtractor じゃないんだとか野暮なことは言わない。
例によってツールボックスを見ると先程作った inc 16 の他に inv 16 と言うのも生えている。
なるほど、こいつらを使えば 16 ビット減算器を構成できる。

正解、235 Nand だ。
しかし、ここで満足してはいけない。加算器はビットあたりたかだか 9 Nand で構成できるのだ。ビットあたり 14 超 は多すぎる。もっと少なく出来るはずだ。Nand を大切に！
と言うわけで、例によって自作部品を作る。まずは半減算器だ。名前は sub。半加算器の時と同様一旦 Xor と Inv と And で構成した上で分解し、悩んだ挙句、こうなった。

何のことは無い、半加算器とほぼ一緒だ。Nand 数も一緒。
ちなみに右側の出力端子はボローなので本当は B の方がよいのだろうが、何か間違えそうだから加算器と一緒の C と言う名前にしてしまった。
次に全加算器を参考に全減算器も作る。これも名前は sub だ。半減算器 2 つと Or で構成した上でごにょごにょした結果、以下のようになった。

これもだいぶ絵面が厳しいが、全加算器と同様 9 Nand で構成できた。
いよいよ 16 ビット減算器を作るわけだが、あろうことかこいつもまた 16 ビット分解君がツールボックスにいないので、16 ビット減算器そのものを自作部品として作るしかない。
と言うわけで作ったのがコレ。

最早何が何だか良く分からないが、最下位ビットが半減算器、最上位ビットが Xor × 2 になっているところがチャームポイントだ。
そして、最後に完全におまけでしかないが本体側を作る（置くだけ）。

139 Nand、半分とまではいかなかったが、約 100 Nand 減らすことができた！
もしこれより減らせたら是非教えて欲しい。

Equal to Zero

条件判定の一つ、ゼロ判定である。
何も難しい事はなく全ビットの Or を取って最後に反転すればいいだけだ。

さすがに 16 ビットやらせるのは酷だと思ったらしく（とは言えこっちは既にいくつか 16 ビット演算器を作ってきている）、入力はバラの 4 ビットであるが、10 Nand で構成できた。これで良いらしい。
Nand 削減は難しいと思う。

Less than Zero

条件判定の一つ、負判定である。
ここでようやく 16 ビット分解君がツールボックスに出てきた。
負、つまり最上位ビットが 1 なら 1 を出力すれば良いので簡単だ。

何と 0 Nand である。完璧すぎる。これ以上どうしようもない。

先はまだまだあるが…

ようやく Arithmetics カテゴリが終わったところだが、既にだいぶ長くなってしまったのでここで一旦区切ろうと思う。
実は皆さんに一番教えて欲しかったのは Memory カテゴリの Data Flip-Flop なのだがそこまで辿り着けなかった。
もし精神力が続けばまた続きを書きたいと思う。
万一ここまでゲーム自体をせずに読んでしまった方は、今からでも遅くないので是非やってみて欲しい（4 回目）。