NandGame – Wie man einen Computer von Grund auf baut

 (nandgame.com)
5 Punkte von GN⁺ 2024-11-02 | 1 Kommentare | Auf WhatsApp teilen
  • NandGame ist ein Lern-Puzzlespiel, in dem man aus einfachen Logikbauteilen startet und am Ende einen programmierbaren Computer zusammensetzt
  • In jedem Level besteht die Aufgabe darin, eine Komponente zu bauen, die gemäß der Spezifikation funktioniert; das fertige Bauteil wird im nächsten Schritt zum Baustein
  • Vorkenntnisse in Computerarchitektur oder Software sind nicht nötig, und in Mathematik reichen Addition und Subtraktion aus; einige Aufgaben können jedoch Zeit brauchen
  • Die erste Aufgabe besteht darin, mit Drähten und Relais eine nand-Komponente zu implementieren, deren Ausgabe nur dann 0 ist, wenn die Eingaben a und b beide 1 sind
  • Komponenten aus der Werkzeugleiste werden per Drag-and-drop im blauen Bereich platziert; Ziehen und Abbrechen werden mit Leertaste, Pfeiltasten und Escape gesteuert

Von Grundbauteilen bis zum Computer

  • NandGame funktioniert so, dass man einfache Komponenten kombiniert, daraus immer leistungsfähigere Bauteile erstellt und am Ende einen programmierbaren Computer aufbaut
  • Es ist in mehrere Level unterteilt; in jedem Schritt muss eine Komponente erstellt werden, die der vorgegebenen Spezifikation entspricht
    • Fertiggestellte Komponenten werden zu Bauteilen, die in späteren Leveln verwendet werden können
    • Ausgangspunkt ist die einfachste Logikkomponente

Erforderliche Vorkenntnisse und Schwierigkeitsgrad

  • Vorkenntnisse in Computerarchitektur oder Software sind nicht erforderlich
  • In Mathematik wird nicht mehr als Addition und Subtraktion verlangt
  • Einige Aufgaben können Zeit zum Lösen brauchen, daher ist Geduld nötig

Erste Aufgabe: nand bauen

  • Die erste Aufgabe besteht darin, mit Drähten und Relais eine nand-Komponente zu implementieren
  • Die Eingaben a und b müssen mit der Ausgabe verbunden werden, wobei die Schaltung so aufgebaut sein muss, dass sie der Spezifikation entspricht
  • 1 bedeutet, dass Strom fließt, 0 bedeutet, dass kein Strom fließt
  • Der Eingang V liefert einen konstanten Strom, der immer 1 ist

nand-Spezifikation

  • Die Ausgabe von nand wird nur dann 0, wenn beide Eingaben 1 sind
  • Die genaue Ein-/Ausgabe-Spezifikation lautet wie folgt
a b Ausgabe
0 0 1
0 1 1
1 0 1
1 1 0

Bedienung

  • Komponenten aus der Werkzeugleiste werden in den blauen Bereich gezogen und dort platziert
  • Um ein ziehbares Element aufzunehmen, drückt man die Leertaste
  • Während des Ziehens bewegt man das Element mit den Pfeiltasten
  • Durch erneutes Drücken der Leertaste wird es an der neuen Position abgelegt, mit Escape wird abgebrochen

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-11-02
Meinungen auf Hacker News

  • Mir gefiel dieses Spiel so gut, dass ich mir ein kleines FPGA-Entwicklungsboard gekauft und selbst einen Befehlssatz samt Soft-CPU gebaut habe.
    Praktisch war das nicht, aber eine unterhaltsame Übung; ich habe mich wegen des ordentlichen Open-Source-Ökosystems und des niedrigen Preises für ein iCE40-Board entschieden: https://www.digikey.com/en/products/detail/lattice-semicondu...
    Inzwischen gibt es vielleicht bessere Optionen.

    • Niklaus Wirth hat etwas Ähnliches gemacht; sein Vorwand war, dass er keine handelsübliche Box finden konnte, die mit seiner geliebten Xerox-PARC-Souvenir-Maus kommunizieren konnte.
      Normalerweise hätte man wohl schnell irgendeinen USB-Konverter gebastelt, aber Wirth wollte es richtig machen: Er nahm ein FPGA-Board, baute eine Soft-CPU und setzte darauf ein OS, ein Fenstersystem, eine Sprach-Toolchain und Ähnliches.
      Dadurch konnte er Hardware-Design-Apps und einen Texteditor ausführen und mit seiner Lieblingsmaus weitere Soft-CPU-Designs ausprobieren.
    • Der nächste Schritt dürfte Tiny Tapeout sein: https://www.tinytapeout.com/

  • Ich habe ein ähnliches Spiel namens Turing Complete gespielt, und es hat wirklich Spaß gemacht: https://store.steampowered.com/app/1444480/Turing_Complete/
    Es ist dem Buch Nand2Tetris sehr ähnlich.

    • Erst nachdem ich 30 Stunden in Turing Complete versenkt hatte, wurde mir klar, was da passiert war.
      Ich hatte die Maschine auf 32-Bit-Befehle aufgerüstet und sogar eine dazu passende Dokumentation für die Assemblersprache geschrieben.
      Obwohl es noch im Early Access ist, ist es ein großartiges Spiel.
    • Turing Complete kann man auf jeden Fall empfehlen.
      Es sieht gut aus, ist sehr ausgereift und ziemlich süchtig machend.
      Schön ist auch, dass es auf GOG verfügbar ist: https://www.gog.com/game/turing_complete

  • Verwandte Beiträge:
    NandGame – Build a Computer from Scratch - https://news.ycombinator.com/item?id=36862274 - Juli 2023
    NandGame – Build a Computer from Scratch - https://news.ycombinator.com/item?id=31055307 - April 2022
    NandGame – Build a Computer from Scratch - https://news.ycombinator.com/item?id=25282507 - Dezember 2020
    Show HN: Online challenge: Build a CPU from scratch - https://news.ycombinator.com/item?id=17508151 - Juli 2018

    • Keine Ahnung, wie ich die früheren Beiträge verpasst habe, aber ich habe das Buch gelesen und auch selbst einen Computer implementiert.
      Eine wirklich unterhaltsame Übung.

  • Das hier erinnert mich auf bittere Weise daran, wie viel ich vergessen habe.
    Vor über 20 Jahren habe ich an der Uni Elektrotechnik studiert und mich auf Rechnerarchitektur spezialisiert, beruflich aber nie etwas davon genutzt und bin in Richtung Software gegangen.
    Ich konnte mich an nichts mehr erinnern, wie man die Dinge hier macht, und habe es erst nach viel Trial and Error gerade so bis zum Halbaddierer geschafft.

    • Ich verstehe diese Reaktion, aber ich denke, das frühere Studium hat dir geholfen, immer wieder Entscheidungen in die richtige Richtung zu treffen.
      Das ist ein bisschen so, als würde man sich Vorwürfe machen, weil man nicht mehr weiß, wer die Corn Laws verabschiedet hat oder wer in den USA den Kühltransport eingeführt hat.
      Wenn man das Grundnarrativ versteht, etwa dass Kriege Ingenieurwesen erfordern, dass auf die Agrarrevolution die Industrielle Revolution folgt und dass Geschichte Klassenkampf ist, dann ordnen sich neue Informationen wie Teilchen in einem Magnetfeld an ihrem Platz ein.
      Sei also nicht zu streng mit dir und gönn dir etwas mehr Nachsicht.

  • Erst nachdem ich sowohl dieses Spiel als auch den Kurs Nand2Tetris gemacht hatte, wurde mir klar, dass beide denselben Computer implementieren.
    Dieses Spiel ist die interaktive grafische Version, während man im ursprünglichen Nand2Tetris die Verbindungen zwischen Logikgattern nicht anklickt und zieht, sondern als Text-HDL aufschreibt.
    Beide waren unterhaltsam und lehrreich, aber NandGame hat mir mehr Spaß gemacht.
    Trotzdem ist es gut, die Verbindung zu kennen. Nach NandGame kann man mit den Folgeaufgaben von Nand2Tetris weitermachen, also mit der Arbeit an höheren Schichten der Computersoftware; außerdem ist es einfacher, Erfahrungen und Inhalte mit Leuten zu teilen, die die jeweils andere Version gemacht haben.

    • Ich habe nand2tetris ausprobiert, und obwohl ich an der Uni auch in Hardware-Kursen ziemlich gut war, fühlten sich dieser Kurs und das Buch eher nach „den Rest der Eule zeichnen“ an.
      Um die Aufgaben zu lösen, musste ich wieder Uni-Lehrbücher und sogar Prüfungsunterlagen hervorkramen, und etwa an dem Punkt, an dem man den Kernteil der CPU fast fertigstellen musste, habe ich aufgegeben.
      Die Vorlesungen und Texte fand ich ehrlich gesagt ziemlich unzureichend, und ich weiß nicht, ob das im Internetzeitalter normal ist, aber ich hatte erwartet, dass Kurs und Lehrmaterialien bis zu einem gewissen Grad in sich geschlossen sind.
    • Es gibt mindestens einen weiteren Drag-and-drop-Simulator, der mit Nand2Tetris kompatibel ist.
      Es handelt sich um den desktopbasierten LogicSimX/Logic Simulator 2 von Andrew Wilkes: https://logicsimx.com/about/ https://andrew-wilkes.itch.io/logic-simulator-2
      Sieht ganz ordentlich aus, aber ich kenne ihn nicht gut genug, um ihn richtig zu bewerten.

  • Als Denkanstoß: Wenn man im ersten Schritt den Teil ausklammert, in dem man das NAND-Gatter tatsächlich baut, erhält man am Ende dieses Prozesses letztlich eine Form, die einem neuronalen Netz sehr ähnlich ist.
    Um ein einzelnes NAND-Gatter darzustellen, braucht man 2 Neuronen; es sieht aus wie eine Struktur mit n Schichten Tiefe, vielen Nullen in der Gewichtsmatrix und ein wenig Speicherplatz.
    Die Frage ist: Wenn nur die Ein-/Ausgabe-Semantik auf Assembly-Ebene gegeben ist, könnte man ein leeres neuronales Netz so trainieren, dass es eine solche Struktur annimmt? Backpropagation geht natürlich nicht, aber wäre nicht irgendeine Form gerichteter Suche möglich?

    • Letztes Jahr habe ich das mit einem Freund ausprobiert.
      Wir haben ein 3-Mehrheitsgatter und mehrere andere Gatter verwendet, aber über eine Schicht hinaus funktionierte Backpropagation nicht gut; vermutlich lag das an unzureichender Bit-Präzision.
      Das Problem des „Trainierens ohne Backpropagation“ ist tatsächlich ziemlich schwierig, und am Ende haben wir aufgegeben.
      Gibt es eine brauchbare Methode, neuronale Netze ohne Backpropagation zu trainieren? Einen gewissen Informationsengpass scheint es zu geben, aber ohne neuronale Netze ist es schwierig, die gegenseitige Information zu bewerten.
    • Einige der frühen Experimente mit neuronalen Netzen vor Jahrzehnten sollten zeigen, dass sich Logikgatter erfolgreich modellieren lassen.

  • Ich habe in diesem Bereich überhaupt keine Erfahrung und würde mir wünschen, dass jemand erklärt, was die einzelnen Komponenten tun.
    Ich weiß nicht, was ein Relais macht und was c und in bedeuten.
    Außerdem verwirrt mich, warum es eine separate Stromversorgung gibt, aber wenn man a oder b an die Stromversorgung anschließt und einschaltet, allein dadurch Strom anliegt.

    • Ein Relais ist ein elektrisch gesteuerter Schalter.
      Wenn die Spule (c) mit Strom versorgt wird, wechselt der Schalterzustand vom Grundzustand in den entgegengesetzten Zustand.
      Ein standardmäßig geschlossener Schalter gibt bei c = 0 den Wert von in an den Ausgang weiter, aber bei c = 1 wird die Spule bestromt und der Schalter öffnet sich bzw. schaltet ab.
      Ein standardmäßig offener Schalter funktioniert umgekehrt.
      c ist die Spule; wenn sie Strom bekommt, toggelt sie den Schalter.
      in ist der Wert, der durchkommt, wenn der Schalter geschlossen ist; hier also 1 oder 0.
      Die separate Stromversorgung ist nötig, um unabhängig von den beiden Eingabewerten einen Wert 1 zu erhalten.
      Wenn man zum Beispiel immer 1 ausgeben will, wenn beide Eingaben 0 sind, braucht man einen hohen Wert, auf den man hochziehen kann; diese Rolle übernimmt die Stromversorgung.
    • C steht vermutlich für coil oder control.
      Ein Relais ist ein mechanischer Schalter, der von einem Elektromagneten gesteuert wird, der aus einer um einen Eisenkern gewickelten Spule besteht.
      Wenn Strom durch die Spule fließt, zieht sie eine Metallfeder an, wodurch Strom von in zum Ausgang fließen kann — oder umgekehrt unterbrochen wird.
      Die zwei bereitgestellten Relais-Bauteile repräsentieren genau diese beiden Verhaltensweisen.

  • Wirklich großartig. Ich empfehle allen, sich auch MHRD einmal anzusehen oder es zu spielen.
    https://store.steampowered.com/app/576030/MHRD/

  • Sieht toll aus. Schade, dass ich das Buch nie bis zum Ende durchgearbeitet habe; ich würde das gern öfter ausprobieren.