Published on

NandGame・Nand2Tetris・Turing Completeの比較

Table of Contents

はじめに

皆さんコンピュータの中身がどうなっているのか気になったことはありませんか?

コンピュータの仕組みを学べるゲームや本はたくさんあると思いますが、今回はその中でも私が取り組んだ以下の 3 つを紹介してこれらの違いやおすすめについて書きたいと思います。

結論から言うと、初心者や多くの人にはNandGame、大変でもちゃんと学びたい人にはNand2Tetris、この 2 つの中間くらいの難しさでゲームとして楽しみたい人にはTuring Completeがおすすめです。

これら 3 つで学べる内容はほとんど同じで、大きくハードウェアパートとソフトウェアパートの 2 つに分けられます。

ハードウェアパートでは、簡単な論理ゲート(Nand ゲート)からスタートしてそれらを組み合わせてだんだんと複雑な論理回路(加算器・ALU・RAM など)を構築していき、最終的にコンピュータを作成することでコンピュータの中身を学べます。

ソフトウェアパートでは以下のような内容を作りながら学びます。

  • 作成したコンピュータを操作するための機械語・アセンブリ言語
  • 複雑な処理をするためのスタック・関数
  • 高級言語・コンパイラ(Turing Complete は除く)

すべて手を動かして作りながら学ぶスタイルなので、勉強するというよりも楽しくゲームをしていたらいつの間にかに知識が深まっているという感じになると思います。

NandGame の特徴

NandGame の特徴は何と言ってもブラウザでプレイできる手軽さです。
ハードウェアパートは基本的にクリックやドラッグだけで操作するので、スマホでも問題なくプレイできてしまいます。
また、日本語でプレイできる点も手軽さに貢献していると思います。

実現すべき論理回路ごとにステージがあり、各ステージでは今までに作った論理回路を組み合わせて新たな論理回路を作っていきます。

nandgame_stages_hard_ja

例えば半加算器のステージは下のようになっています。
左には半加算器の説明と真理値表(正しい入出力の関係)が示され、そこまでに作ったnand, inv, and, or, xorの 5 つを論理回路が並んでいます。
プレイヤーはこの説明と真理値表を見ながら右側のキャンバス内で、入力a, bと出力h, l、さらには自分で配置した論理回路を自由に配線して、半加算器を作っていきます。
最終的に、解答をチェックボタンを押したときに正しい入出力の関係が実現されていれば半加算器の完成となりステージのクリアです。

nandgame_halfadder

ソフトウェアパートでは簡単なプログラミングをするので、英数字と記号が入り混じったテキストを入力することになります。
スマホではプレイしづらいと感じる人が多いでしょうし、ハードウェアパートほどの手軽さはないかもしれません。

例えばこのDをプッシュのステージでは、説明された機能を実現するために 5 行程度のアセンブリ言語のプログラムを書くことになります。
右側のcomputerの部分に現在のコンピュータの内部状態が表示されていますが、Nand2Tetris とは違って RAM のすべてが見れるわけではないのでうまく行かなかったときにどこが間違っているのかわかりづらいと感じました。

nandgame_pushd

Nand2Tetris の特徴

NandGame がブラウザゲームなのに対して、Nand2Tetris は講義や本です。
高校や大学の講義に使われていたり、本として出版されていたりするようです。

講義資料はNand2Tetris の Projects ページで公開されていて、原著は英語ですが日本語版の本も出版されています。

コンピュータシステムの理論と実装

コンピュータを理解するための最善の方法はゼロからコンピュータを作ることです。コンピュータの構成要素は、ハードウェア、ソフトウェア、コンパイラ、OSに大別できます。本書では、これらコンピュータの構成要素をひとつずつ組み立てます。具体的には、NANDという電子素子からスタートし、論理ゲート、加算器、CPUを設計します。そして、オペレーティングシステム、コンパイラ、バーチャルマシンなどを実装しコンピュータを完成させて、最後にその上でアプリケーション(テトリスなど)を動作させます。実行環境はJava(Mac、Windows、Linuxで動作)。

● 本書のサポートサイト
● 本書で使用するツール「Nand2tetris Software Suite」
● 「Nand2tetris Software Suite」のチュートリアル

https://www.oreilly.co.jp/books/9784873117126/
www.oreilly.co.jp
https://www.oreilly.co.jp/books/9784873117126/

NandGame の About ページ

The Nand Game is inspired by the amazing course From NAND to Tetris - Building a Modern Computer From First Principles which is highly recommended.

とあるように、NandGame 作者も Nand2Tetris をおすすめしています。

Nand2Tetris の内容は Project 1 から Project 12 までの 12 個に分かれています。
Project によって言語は違いますが、各 Project はプログラミングをしてその結果を与えられたツールで検証するという流れになっています。
与えられたツールというのは、ハードウェアシミュレーター・CPU エミュレーター・VM エミュレーターなどでいずれも Java で作られているため、基本的にパソコンでプログラミングしていくことになります。

しかし、この記事を書いているときにNand2Tetris の Software ページを見ていたら、ブラウザで利用できるオンライン IDEも用意されていることに気づきました。
オンライン IDE を利用するのであればパソコンである必要はないかもしれません。
また、公式はパソコンであっても Java 製のデスクトップバージョンよりオンライン IDE を推奨しているようです。

各 Project で利用する言語は以下のとおりです。

Project 番号言語
1, 2, 3, 5HDL
4Hackアセンブリ
9, 12Jack
6, 7, 8, 10, 11任意

HDL とは Hardware Description Language の略称で、デジタル回路の構成や動作を記述するための言語です。
Nand2Tetris では論理回路を記述するために使われています。

例えば半加算器は HDL で書くと下のようになります。
GUI 上で配置・配線ができる NandGame や Turing Complete より視覚的に理解しづらいと思います。

HalfAdder.hdl
CHIP HalfAdder {
    IN a, b;    // 1-bit inputs
    OUT sum,    // Right bit of a + b
        carry;  // Left bit of a + b

    PARTS:
        Xor(a=a, b=b, out=sum);
        And(a=a, b=b, out=carry);
}

Hack アセンブリはこの講義で作成するコンピュータ用のアセンブリ言語です。
自分で書くのは Project 4 でだけですが、その後の前提となるため理解しておく必要があります。

Jack もこの講義オリジナルの言語で、Java と似た高級言語です。
Project 12 では Jack で OS を作成しますが、これは Nand2Tetris だけの特徴的な内容となっています。

任意と書いているのはそのとおり任意で、自分の好きな言語を使うことができます。
Project 6 ではアセンブラ、7 と 8 では中間言語からアセンブリ言語への変換器、10 と 11 ではコンパイラを作成するのですが、それなりの量をコーディングするので使い慣れた言語を選ぶと楽だと思います。

Nand2Tetris の大きな特徴はこのアセンブラやコンパイラを自分で作成するという部分です。
NandGame にも同じ内容はありますが簡易なものになっていますし、Turing Complete にはそもそも同じ内容はありません。
自分で作成することで、知った内容に対する理解が正しいかどうか確認できると思います。

また、自分で書くことはありませんが、中間言語が登場することも Nand2Tetris だけの特徴です。
Nand2Tetris ではコンパイラが直接機械語を出力せず、Java のように一度中間言語に変換してから機械語に変換するという 2 ステップのやり方を採用しています。

Turing Complete の特徴

Turing Complete は Steam で配信されているゲームです。
Windows だけでなく Mac や Linux でもプレイできます。

基本的な内容や流れは NandGame と同じですが、違う点もいくつかあります。

違う点 1 つ目はステージに分岐があるということです。

下の画像はステージ選択画面です。
緑色がクリアしたステージ、黄色がプレイできるがクリアしていないステージ、赤色がまだプレイできないステージを表しています。
各ステージは上下に線で結ばれていて、あるステージをプレイしたいならその下側に繋がっているステージをすべてクリアしなければなりません。
これによって自分の好きな場所から進めることができて、なおかつ各ステージ間にどんな依存関係があるのか一目瞭然です。

turingcomplete_stage_select

2 つ目は自由度の高さです。

Component Factoryという仕組みがあり、自分で作ったオリジナルの論理回路を使うことができます。
ここで面白いのは、論理回路を構築したときの回路の大きさや形、入出力ピンの位置が反映されることです。

例えば、このような回路を構築すると、次のような見た目のパーツができあがります。

turingcomplete_alu_circuit
turingcomplete_alu_preview

また、後半では ALU の設計まで自由で、プレイヤーによって機械語(オペコード)が異なるのも大きな特徴です。
まず実装が要求されるのは以下の 6 つですが、私の場合は空いている00000110に左シフト演算を00000111に右シフト演算をそれぞれ割り当てました。
その後も関数に関するcallreturnの処理を自分の好きなオペコードに割り当てることになると思います。

オペコード処理
00000000足し算
00000001引き算
00000010And
00000011Or
00000100Not
00000101Xor

3 つ目はゲーム要素がある点です。

例えばBinary Racerというステージがあります。
このステージでは 2 進数について理解しているかテストされます。
表示された 10 進数を素早く 2 進数に変換して正しいビットをクリックするだけですが、レベルが上がるとだんだん表示される数も大きくなっていき難しくなっていきます。
最低でもレベル 4 まで行かなければクリア判定をもらえません。
ちなみに、16 進数を 2 進数に変換するHex Racerというステージもあります。

turingcomplete_binaryracer

最近のゲームによくある実績の要素もあります。
全部で 15 個あり、普通にプレイしていれば達成されるものもあれば、狙わないと難しいものもあります。
実績の達成を目指してプレイするのもいいかもしれません。

turingcomplete_achievements

4 つ目はプログラミングの実践が多いことです。

他 2 つよりもアセンブリ言語でプログラムを書くステージが多く用意されています。
本質的な内容はソートや再帰などのアルゴリズムですが、それが下のようにゲームっぽい課題になっていて楽しみながら取り組めるようになっています。

  • ロボットを迷路から脱出させる
  • 食べ物を美味しい順に並べ替える
  • ロボットにランダムな動きをさせる
  • ベルトコンベアに同じフルーツが流れてきたらボタンを押す
  • 石取りゲームで必ず勝たせる
  • ハノイの塔を解く
turingcomplete_game_ai
turingcomplete_game_maze

5 つ目は 2 つのアーキテクチャを学べることです。

このゲームでは下の 2 つのアーキテクチャのコンピュータを作ることになります。
後に作るLEGアーキテクチャのほうが命令長が長く、1 つの命令で複雑な処理を記述できます。
スタックや関数を使うのもLEGアーキテクチャでだけです。

  • OVERTURE: 命令長が 1 Byte(8 bit)
  • LEG: 命令長が 4 Byte(32 bit)

2 つのアーキテクチャを扱うことでコンピュータの仕組みについて俯瞰でき、理解が進むと思います。

比較

3 つの基本的な情報は以下のとおりです。

NandGameNand2TetrisTuring Complete
形態ブラウザゲーム講義・本PC ゲーム(Steam)
値段無料本は 3960 円(講義資料は無料)2050 円
言語日本語対応日本語本あり(講義資料は英語のみ)英語のみ

それぞれの特徴をまとめると以下のようになります。

NandGame
  • スマホでも気軽にプレイできる
  • 簡易的だが高級言語に関する内容がある
  • まだ開発中でこれからステージが増えそう
Nand2Tetris
  • 本でしっかり学べる
  • アセンブラ・中間言語用の変換器・コンパイラを自分の好きな言語で作る体験ができる
  • OS についても学べる
Turing Complete
  • ゲーム要素がある
  • 自由度が高い
  • 2 つのアーキテクチャを学べる

これらを踏まえて、それぞれ以下のような人におすすめします。

  • NandGame: 初心者や多くの人
  • Nand2Tetris: 大変でもちゃんと学びたい人
  • Turing Complete: この 2 つの中間くらいの難しさでゲームとして楽しみたい人

おわりに

コンピュータの仕組みを学べる NandGame・Nand2Tetris・Turing Complete の 3 つを比較しました。

どれもよくできているのでぜひ気になったものをやってみてください。