NandGame – Build a computer from scratch

https://www.nandgame.com

by OuterVale • 2 years ago

353 51 2 years ago

nandgame.com

michael-online• 2 years ago

This looks awesome! I never finished working the book and I regret it. Can't wait to try even more of this out.

insane_dreamer• 2 years ago

Awesome! Will do this with my child.

dang• 2 years ago

NandGame – Build a Computer from Scratch - https://news.ycombinator.com/item?id=36862274 - July 2023 (3 comments)

NandGame – Build a Computer from Scratch - https://news.ycombinator.com/item?id=31055307 - April 2022 (14 comments)

NandGame – Build a Computer from Scratch - https://news.ycombinator.com/item?id=25282507 - Dec 2020 (136 comments)

Show HN: Online challenge: Build a CPU from scratch - https://news.ycombinator.com/item?id=17508151 - July 2018 (60 comments)

Patrick_Devine• 2 years ago

Not sure how I missed this those other times, but I have read the book and implemented the computer before. It's a super fun exercise.

ziofill• 2 years ago

Very nice! Related: https://turingcomplete.game/

kelnos3• 2 years ago

Ugh, this just reminded me how far I've fallen. I did EE in college (>20 years ago), specializing in computer architecture. Never did anything with it professionally; I ended up in software. I couldn't remember how to do any of these. I managed to trial-and-error my way to the half-adder, at least.

lifeisstillgood• 2 years ago

I get the reaction but I suggest that your previous work has set you up to make decisions “in the right direction” time and again.

It’s a bit like saying “darn I can never remember which Prime Minster passed the corn laws or the name of the guy who started refrigerated shipping in the USA.

The point is if we have a grasp of the essential narrative (something like “wars require engineering, agricultural revolution, Industrial Revolution, history is class warfare” that background acts like a magnetic field for all the new pieces of information, aligning them correctly.

Anyway, relax, be kinder to yourself.

kelnos3• 2 years ago

Thanks for that! I think I wrote that comment a little more negative-sounding than it was in my head. While I do lament skills I've lost and forgotten over the years, I know my EE background came in handy when writing software professionally for embedded and semi-embedded devices, earlier in my career. These days I've moved on to distributed systems, so all that low-level knowledge isn't quite as useful as it once was.

tonetheman• 2 years ago

I wish there were more hints.

I have done this before in another version of this game but for the life of me cannot see how to get to a single output from all of the components I have placed on the screen.

It does look cool but without more directions or hints I am done for.

kelnos3• 2 years ago

One option might be to search the web for "nand gate using relays". That will give you the answer, which might be a little spoilery, but you can try to puzzle out how it works from the solution.

I found this[0], which is nice in that it's interactive (you can click the inputs to change their values and see how the current flows), though I think the visuals are a little harder to understand. Would be nicer if it had clearer delineation of the relays, and their inputs and outputs labeled with more than just their voltages.

[0] https://everycircuit.com/circuit/4954026060021760/relay-base...

chrisbrandow• 2 years ago

yeah, there's something missing in the instructions regarding the first Nand gate. I understand how a NAND Gate is constructed but I can't figure out how to combine the outputs of the two relays in this tool

magicalhippo4• 2 years ago

The components that are available is usually a hint. Have you used both types?

Arnavion• 2 years ago

A nand B = not(A and B)

One of the relays gives you "A and B". The other gives you "A and not B". "A and not B" with A = 1 is just "not B".

magicalhippo4• 2 years ago

for the life of me cannot see how to get to a single output from all of the components I have placed on the screen

That should be a clue that you're up the wrong alley. A single output means a single output...

schoen2• 2 years ago

And thus, something will have to happen in series in order to end up with just one output.

theamk3• 2 years ago

Well, unless it's a relay, in which you can easily connect multiple outputs together with no ill effects.

(or a 3-state buffer, but I don't think that'll appear in the game)

theamk3• 2 years ago

If you have electrical experience then the first level is simply wrong. Your instinct should be to parallel relays' outputs where possible (less delay, less relay wear, fewer glitches, more similar to TTL logic), but the software does not support this.

My advice is to treat it like a puzzle: "how do you implement NAND in relays _if_ you can not do any parallel connections". When formulated this way, it is pretty easy to solve.

(The relays disappear in level 2 and we switch to digital logic, so "cannot parallel outputs" limitation makes much more sense there. I am guessing they didn't want to make up a new mechanic just for a single level, but I wished they'd explain it better)

sergex2• 2 years ago

Author here. Yeah, the first level is special and perhaps half-baked. It felt like cheating to start with the NAND-gate as the atomic component since transistors are not NAND-gates. So I start with electric relays (since they logically correspond to transistors but are easier to visualize). But I didn't want to get into realistic simulation of electronic circuits with all the complexity this entails.

May I ask how you would have preferred to solve the first level if the game didn't have limitations?

sergex2• 2 years ago

Is your problem with the user interface, i.e. how to connect wires from input to output, or is is with the logical problem of getting the correct output?

ivanbelenky• 2 years ago

this is awesome, I recommend everyone to also peek into or play MHRD

https://store.steampowered.com/app/576030/MHRD/

ActorNightly• 2 years ago

Some food for thought:

Once you complete this (ignoring the first level where you actually build a NAND gate) you essentially get very much what looks like a Neural Network (since it takes 2 neurons to represent a NAND gate), n layers deep, with a lot of zeros in the weight matrices, and some storage.

Here is my question: given the input/output semantics at the assembly level, is it possible to train a blank neural network to look like this? Backprop obviously wouldn't work, but perhaps there is some form of directed search one could use?

iterance• 2 years ago

Some of the earliest tests of neural networks decades upon decades ago were done to prove they could be used to model logic gates successfully.

greenbit• 2 years ago

Playing around with classic three layer feed-forward classifier networks decades ago, it became apparent that successful networks tended to converge on a sort of standard solution: layer 1 would be various linear discriminators - each node would cut the input space into two half spaces, such that any input point was either in the selected half-space or not, essentially reducing the N dimensional real-valued input to some number of bits. Layer 2 nodes tended toward AND functionality, using some subset of the layer 1 outputs to identify convex regions of the input space. Layer 3 nodes tended to OR together outputs of layer 2 to combine convex regions into arbitrary subsets of the input space. I.e. more often than not, the 2nd and 3rd layer were just doing Boolean logic.

Of course, occasionally there would be a system where this didn't fully happen, and you'd get some node/s doing some funky stuff with the linear parts of the activation function, but that doesn't negate the fact that such networks can and often do find the slice/AND/OR solutions.

barrenko• 2 years ago

Yup, but the other way around is tricky as mentioned by others.

Really intrigued by the "similarity" of logical gates - nn - batteries/ transistors

programjames• 2 years ago

I tried this with a friend last year (using 3-majority and a variety of other gates). We couldn't get backprop to work past one layer, probably because there isn't enough bit precision. The "train without backprop" issue is actually pretty difficult to accomplish, so we gave up.

Does anyone have a decent method to train neural networks without backprop? I think the information bottleneck sort-of works, but it's hard to evaluate the mutual information without a neural network.

schoen2• 2 years ago

I did both this and the Nand2Tetris course before realizing that they are implementing the same computer -- this is an interactive graphical version, while the original Nand2Tetris uses a textual HDL where you write down the connections between logic gates as text, instead of clicking and dragging to indicate them.

I found them both fun and educational, but I thought the NandGame was more fun. But it's good to know about the connections, for example because there are more follow-on exercises that you can do from Nand2Tetris (working with higher layers of computer software) after you complete the NandGame. Or you can just be aware that you can talk about the experience and the substance with people who have done the other version!

kevstev• 2 years ago

I tried nand2tetris and my hardware class was one I did best in in college. Yet I found this class and book to be very much "rest of the Fine owl" and I had to refer back to my college textbooks and even my tests to do the assignments. I gave up about halfway through as you had to complete more or less the main part of the CPU. I felt the lectures and text were lacking to say the least. Maybe in the age of the internet (I graduated a bit over 20 years ago) this is the norm these days but I expected the course and text to be more or less self contained.

leoc• 2 years ago

There's also at least one other drag-and-drop Nand2Tetris-compatible simulator out there, Andrew Wilkes' desktop-based LogicSimX/Logic Simulator 2 https://logicsimx.com/about/ https://andrew-wilkes.itch.io/logic-simulator-2 . It seems nice but I don't know enough to review it properly.

AlchemistCamp• 2 years ago

I played a similar game called Turing Complete and really enjoyed it! https://store.steampowered.com/app/1444480/Turing_Complete/

It's very similar to the Nand2Tetris book.

XorNot• 2 years ago

Dropped 30 hours into Turing Complete before I realised what was happening to me. Upgraded the machine to 32 bit instructions and wrote documentation of my assembly language for it and everything.

Fantastic game even in early release!

NanoCoaster• 2 years ago

Yup, definite recommendation for Turing Complete. It looks nice, is really well done and very addictive.

Also, it's on GOG (https://www.gog.com/game/turing_complete) which is always nice.

rahen• 2 years ago

Does a similar game but with neural networks exist?

magicalhippo4• 2 years ago

Love the game, and it inspired me to get a small FPGA dev board and make my own instruction set and soft-CPU for it. Not very practical, but a fun exercise.

I got an iCE40 board[1] as the open-source story was decent and price was low. There might be better options now.

[1] https://www.digikey.com/en/products/detail/lattice-semicondu...

Taniwha• 2 years ago

Tiny Tapeout https://www.tinytapeout.com/ is the next step ......

082349872349872• 2 years ago

Niklaus Wirth did the same, but his excuse was that he couldn't find a commercial box that would talk to his favourite (Xerox PARC souvenir) mouse.

Some people might have wimped out and just cobbled up a USB translator, but Wirth knew how to take care of things properly: he got an FPGA board, made a soft CPU, and then put all the stuff on top (his OS, his windowing system, his language toolchain, etc.) that would enable him to run his h/w design app and text editor, thereby allowing him to play with more soft CPU-designs ... but this time while using his favourite mouse.

woodrowbarlow• 2 years ago

that's hilarious and inspirational. i can barely imagine the work it took just to get a reliable system with basic UART i/o. i can't imagine how much additional work it took before the system was sophisticated enough to even justify a mouse as a peripheral.

theogravity3• 2 years ago

I have zero experience with this, and I wish it explained what these components do. What does a relay do, what is the "c" and "in"? Why is there a separate power source, but if you hook up a / b to it and flip it on, it gets power without it?

naruhodo• 2 years ago

C for coil or control. Not sure.

A relay is a mechanical switch controlled by an electromagnet composed of a coil of wire wrapped around an iron core, as depicted on the icon. When current flows through the coil, it pulls the metal spring towards it, which can either allow current to flow from "in" to the output or disconnect the current flow from "in" to the output. Those are the two types of relay components on offer.

theogravity3• 2 years ago

That definitely helps, thanks.

Jtsummers2• 2 years ago

A relay is an electrically controlled switch. If the coil (c) is powered then the switch state goes from its default state to the alternate. So a default on switch passes on the value of in to its output if c = 0, but when c = 1 (the coil is powered) the switch is opened, or toggled off. For a default off switch it is the reverse.

c = coil, if it is powered it will toggle the switch.

in = the value (1 or 0 here) that will pass through if the switch is closed.

In code:

  def default_on(c, in):
    if c == 1: return 0
    if c == 0: return in
  def default_off(c, in):
    if c == 1: return in
    if c == 0: return 0

The separate power source allows you to obtain a 1 value (since this is around digital logic I'm not going to break it down further) regardless of what the two input values are.

Consider a situation like this: How would you output 1 every time both inputs are 0? You need some high value to draw from, that's what the power source is for. So the input signals themselves may not be enough.

theogravity3• 2 years ago

Thank you.

asdefghyk• 2 years ago

I was thinking maybe they meant starting from sand

hellavapid• 2 years ago

cant wait to waste a few hours later :3

lencastre• 2 years ago

Reminds of the Turing Machine game from Steam

nachox999• 2 years ago

How much time will pass until someone is playing Doom on this page?

robblbobbl• 2 years ago

Cool thx!

NandGame – Build a computer from scratch

Related Stories