NandGame – コンピュータを最初から作る方法

 (nandgame.com)
5 ポイント 投稿者 GN⁺ 2024-11-02 | 1件のコメント | WhatsAppで共有
  • NandGameは、単純な論理部品から出発して最終的にプログラム可能なコンピュータを組み立てる教育用パズルゲーム
  • 各レベルは仕様どおりに動作するコンポーネントを作る課題で、完成した部品が次の段階のビルディングブロックになる
  • コンピュータアーキテクチャやソフトウェアの事前知識は不要で、数学も足し算と引き算のレベルで十分だが、一部の課題には時間がかかることがある
  • 最初の課題は、入力 a と b がどちらも 1 のときだけ出力が 0 になる nand コンポーネントを、配線とリレーで実装すること
  • ツールボックスの部品を青い領域にドラッグして配置し、スペースキー・方向キー・Escape でドラッグとキャンセルを操作する

基本部品からコンピュータまで

  • NandGameは、基本コンポーネントを組み合わせて徐々により強力な部品を作り、最後にはプログラム可能なコンピュータを構成していく方式で進む
  • 複数のレベルに分かれており、各段階で与えられた仕様に合うように動作するコンポーネントを作らなければならない
    • 完成したコンポーネントは、その後のレベルで使える部品になる
    • 出発点は最も単純な論理コンポーネント

必要な事前知識と難易度

  • コンピュータアーキテクチャやソフトウェアに関する事前知識は不要
  • 数学は足し算と引き算以上を要求しない
  • 一部の課題は解くのに時間がかかることがあり、忍耐が必要

最初の課題: nand を作る

  • 最初の課題は、配線とリレーを使って nand コンポーネントを実装すること
  • 入力 a と b を出力に接続しつつ、仕様に合う動作になるよう回路を構成しなければならない
  • 1 は電流が流れている状態、0 は電流が流れていない状態を意味する
  • V 入力は常に 1 の定電流を伝える

nand の仕様

  • nand の出力は、2つの入力がどちらも 1 のときだけ 0 になる
  • 正確な入出力仕様は次のとおり
a b 出力
0 0 1
0 1 1
1 0 1
1 1 0

操作方法

  • ツールボックスのコンポーネントを青い領域へドラッグして配置する
  • ドラッグ可能な項目をつかむにはスペースキーを押す
  • ドラッグ中は方向キーで項目を移動する
  • もう一度スペースキーを押すと新しい位置に置かれ、Escape を押すとキャンセルする

関連記事

1件のコメント

 
GN⁺ 2024-11-02
Hacker Newsのコメント

  • このゲームが気に入って、小さな FPGA開発ボードを買い、自分で命令セットとソフトCPUを作ってみた
    実用的ではないけれど楽しい練習になったし、オープンソースのエコシステムがそこそこ良く価格も安かったのでiCE40ボードを選んだ: https://www.digikey.com/en/products/detail/lattice-semicondu...
    今ならもっと良い選択肢があるかもしれない

    • Niklaus Wirthも似たようなことをしていて、その口実は、自分が気に入っていた Xerox PARCの記念品マウスと通信できる市販の箱が見つからない、というものだった
      普通ならUSB変換器を適当に作っただろうが、Wirthはきちんと処理しようとしてFPGAボードを持ち出し、ソフトCPUを作り、その上にOS、ウィンドウシステム、言語ツールチェーンなどを載せた
      おかげでハードウェア設計アプリとテキストエディタを動かし、お気に入りのマウスでさらに多くのソフトCPU設計を試せるようになった
    • 次のステップは Tiny Tapeout かもしれない: https://www.tinytapeout.com/

  • 似たゲームの Turing Complete をやってみたが、本当に面白かった: https://store.steampowered.com/app/1444480/Turing_Complete/
    Nand2Tetrisの本にとても似ている

    • Turing Completeに30時間費やしてから、ようやく何が起きたのかに気づいた
      マシンを 32ビット命令 にアップグレードし、それに合わせたアセンブリ言語のドキュメントまで書いていた
      まだ早期アクセスなのに素晴らしいゲーム
    • Turing Complete は間違いなくおすすめできる
      見た目がよく完成度も高く、かなり中毒性がある
      GOGにもあるのが良い: https://www.gog.com/game/turing_complete

  • 関連記事:
    NandGame – Build a Computer from Scratch - https://news.ycombinator.com/item?id=36862274 - 2023年7月
    NandGame – Build a Computer from Scratch - https://news.ycombinator.com/item?id=31055307 - 2022年4月
    NandGame – Build a Computer from Scratch - https://news.ycombinator.com/item?id=25282507 - 2020年12月
    Show HN: Online challenge: Build a CPU from scratch - https://news.ycombinator.com/item?id=17508151 - 2018年7月

    • 昔の記事をどうして見逃していたのか分からないが、本は読んだし、コンピュータも自分で実装してみた
      本当に面白い練習だった

  • これを見て、自分がどれだけ多くを忘れてしまったかを思い出し、少し苦い気持ちになった
    20年以上前に大学で 電気工学 を学び、コンピュータアーキテクチャを専攻していたが、仕事ではまったく使わずソフトウェアのほうへ進んだ
    ここにあることをどうやるのか一つも覚えておらず、試行錯誤の末にようやく半加算器まで作れた

    • そういう反応は分かるが、以前に学んだことが、繰り返し 正しい方向の判断 をする助けになっていたのだと思う
      誰が穀物法を可決したのか、米国で冷蔵輸送を始めたのが誰だったのかを覚えていないと自分を責めるのに似ている
      重要な筋書き、たとえば戦争は工学を必要とし、農業革命と産業革命が続き、歴史とは階級闘争である、といった背景理解があれば、新しい情報は磁場の中の小片のように収まるべき場所に収まっていく
      だからあまり自分を責めず、もう少し自分に寛大でいてもいい

  • このゲームと Nand2Tetris のコースを両方やってみて、ようやく両者が同じコンピュータを実装しているのだと気づいた
    このゲームは対話型のグラフィカル版で、元のNand2Tetrisは論理ゲート間の接続をクリック＆ドラッグする代わりに、テキストのHDLで書く方式
    どちらも面白く教育的だったが、NandGameのほうがより楽しかった
    ただ、両者のつながりは知っておくとよい。NandGameを終えたあと、Nand2Tetrisの後続課題、つまりより高い階層のコンピュータソフトウェア作業へ進めるし、反対側のバージョンをやった人たちと経験や内容を共有しやすい

    • nand2tetrisに挑戦してみたし、大学時代もハードウェア系の科目はかなり得意だったのに、この授業と本は「残りのフクロウを描く」に近かった
      課題をやるには大学の教科書や試験問題まで探し直す必要があり、CPUの中核部分をほぼ完成させなければならないあたりで諦めた
      講義とテキストは正直かなり不十分だと感じたし、インターネット時代にはこれが普通なのか分からないが、授業と教材にはある程度自己完結していることを期待していた
    • Nand2Tetrisと互換性のあるドラッグ＆ドロップ式シミュレータが少なくとももう1つある
      Andrew Wilkesによるデスクトップベースの LogicSimX/Logic Simulator 2 だ: https://logicsimx.com/about/ https://andrew-wilkes.itch.io/logic-simulator-2
      良さそうに見えるが、きちんと評価できるほどは詳しくない

  • 考えてみる材料として、最初のステップで NAND ゲートを実際に作る部分を除けば、このプロセスを終えたとき、結局 ニューラルネットワークにかなり近い形になる
    NAND ゲート 1 個を表現するのにニューロンが 2 個必要で、深さ n 層、重み行列には多くの 0、そして少しの記憶領域がある構造のように見える
    問いはこうだ。アセンブリレベルの入出力の意味だけが与えられたとき、空のニューラルネットワークを訓練して、このような構造にできるだろうか？ 逆伝播は当然無理だろうが、何らかの形の方向性のある探索は可能ではないだろうか？

    • 去年、友人とこれを試してみた
      3多数決ゲートやほかのいくつかのゲートを使ってみたが、1 層を超えると逆伝播がうまくいかず、おそらくビット精度が足りなかったのだと思う
      「逆伝播なしで訓練する」問題は実際かなり難しく、結局あきらめた
      逆伝播なしでニューラルネットワークを訓練する良い方法はあるのだろうか？ 情報ボトルネックはある程度ありそうだが、ニューラルネットワークなしで相互情報量を評価するのは難しい
    • 数十年前の初期の ニューラルネットワーク実験の一部は、論理ゲートをうまくモデル化できることを示すためのものだった

  • この分野の経験がまったくないので、各構成要素が何をするのか説明してほしい
    リレーが何をするのか、c と in が何なのかが分からない
    別電源があるのに、a や b を電源につないでオンにすると、それだけで電源が入るように見えるのも混乱する

    • リレーは 電気で制御されるスイッチ
      コイル（c）に電源が入ると、スイッチの状態が標準状態から反対の状態に変わる
      標準オンのスイッチは、c = 0 のとき in の値を出力へ渡すが、c = 1 だとコイルに電気が流れてスイッチが開く、つまりオフになる
      標準オフのスイッチは逆に動作する
      c はコイルで、電気が入るとスイッチをトグルする
      in はスイッチが閉じているときに通過する値で、ここでは 1 または 0
      別電源は、2 つの入力値とは無関係に 1 の値を得るために必要
      たとえば 2 つの入力がどちらも 0 のとき常に 1 を出力したいなら、引き上げるための高い値が必要で、その役割を電源が担う
    • C はおそらく coil または control の C だと思う
      リレーは、鉄心に巻いたコイルで作った電磁石が制御する機械式スイッチ
      コイルに電流が流れると金属ばねを引き寄せ、その結果 in から出力へ電流を流したり、逆に遮断したりできる
      提供されている 2 種類のリレー部品が、まさにこの 2 つの動作を表している

  • 本当にすばらしい。みんな MHRD も一度のぞいてみるか、プレイしてみることをおすすめする
    https://store.steampowered.com/app/576030/MHRD/

  • すごく良さそう。本を最後までやれなかったのが残念で、これをもっと試してみたい