Show HN: Online challenge: Build a CPU from scratch | Hacker News Reader

Show HN: Online challenge: Build a CPU from scratch

nandgame.com

143 pointssergex60 comments

This is an attempt to make an educational online game, where the mission is to build a microprocessor starting from simple logic gates.

Hopefully it is both fun and challenging, while at the same time educational about some of the fundamental principles of how a CPU works.

It still lack some explanatory texts, but is should be playable as it is.

It is inspired by the first chapters of the brilliant Nand2tetris course (and I have gotten permission to use the same general CPU design). My hope is this is more accessible since it is web-based and does not require any text-based coding or CS background.

FYI: I'm not able to drag components from the toolbox in mobile chrome.

I'm sorry, it does not work with touch yet.

This is great! I've been reading up on low level logic during long builds at work. Any chance you could add a clear all button?

You mean for just wiping all components from the canvas? That should be possible.

Exactly. Sometimes I realize my plan is no good. It takes a lot of clicking to start over.

This is really neat, good job!

This reminded me of "Code" by Charles Petzold, which I saw you reference in the About page. As a software engineer with an interest (but no professional training) in hardware design, I think it's useful and interesting to have at least a basic understanding of how a CPU handles logic.

Can I ask what library (if any) you used for the canvas interactions? I'm looking for something similar for a project of my own.

Thank you. I'm using Angular, but no library beyond that. I was looking for a library for the diagram, but didn't find anything that suited my needs, so it is just custom code. I would like to find a library which could draw nicer arrows at least, since the diagram currently gets pretty confusing when there are many connections.

I know what you mean about libraries. There are so many out there that cover 80% of my use case, but they're all missing 20% in different areas.

I think I've finally found what I'm looking for in Raphael.js + Raphael.FreeTransform though.

My fiancee is starting computer science this fall. I'm already using this to teach fundamentals. Thank you!!

Great to hear. I would love to hear feedback from someone without CS background.

This is fun. Reminds me a lot of Euclid the Game: http://eu.jugregator.org/Level1/

Would be awesome if you compare your answer to the "best" solution, i.e. which uses the minimum number of components (or even the minimum number of nand gates!)

Great idea! I don't know the optimal solutions, only that each task can be solved. Perhaps someone smarter than me can prove that a certain solution is optimal. But I could record the solutions provided and show if someone else have solved the task with fewer components or less nand-gates.

It would also be cool to show the overall cost in nand-gates or even transistors. And to be able to show the solutions decomposed into only transistors and wires.

Didn't know Euclid the Game, but it seems very cool and close to what I wanted to achieve.

I'd be happy to have a crack at the optimality part. The first few are obvious but it gets quite interesting. Email my username at protonmail.com if you're interested =]

If you have a look at any Zachtronics games you can see one way of doing it. It is just a leaderboard represented as a histogram. A separate one for instructions, cycles, etc. No need to know the best, just keep track of what other people have achieved.

Gate count is interesting from a "how much would this const to make" perspective, but I think minimum clock cycle time is a more interesting metric, as that will show how fast you can run the thing. Maybe a two dimensional plot? It would be very interesting to have a worldwide "leaderboards" section with a dot on the plot for every entry, and a link to see how they did it.

Interesting idea, but how should this be determined? Would it be a "cost" per transistor and wirelength, and then the minimum clock cycle time would be the "worst case" path through the circuit?

Yes exactly. The 6.004 course at MIT already has software that does this sort of thing.

Thanks, it is a very cool idea. I wanted to make the game really simple and accessible, but there seem to be interest in optimization challenges like finding the smallest/cheapest/fastest possible solution.

I'm not a huge fan of the fact that when I want to drag a component, if I initiate the click&drag on the little "i" information button, it lets me drag the component but when I release it snaps back to the previous location and opens the info.

Perhaps a toggle for the info boxes on components?

Overall, I love this though.

Cool! Very similar to MHRD -- give that a look if this is your thing.

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

I had a lot of fun with MHRD but I hope the developer some day updates it to not be a sluggish Java implementation. The puzzle of working through all the levels was a fun throwback to my processor design courses 15 years ago, but the unresponsive typing in the IDE was a little less so.

I'm enjoying this; but it looks like a few of the levels might be out of order. In State Selector uses Decoder in the library but it is before decoder. Then in the Arithmetics the "Bus" comes into play before it's described (I forget exactly which ones are out of order)

Doh, you are correct about selector - the decoder should no be available here (and is not needed). And the bus definitely needs an introduction.

The usual convention for logic gates is to draw them so that information flows from left to right (or, less usually, top to bottom) and they're connected in the direction of information flow. Is there any reason why these conventions aren't followed here?

No, just ignorance on my part. I would be easy to flip input and output though.

In the full adder level, shouldn't the input/output table in the specification read 01 for the h/l on row 3? Had me a little confused trying to get my head around how the adder works.

I'm really enjoying the whole thing though, great work!

Thank you. You are correct, this is a bug. Thank for pointing it out. Fixed now.

Holy crap! this brings back memories. I actually did this many years ago with real logic gates, eventually ending up with a 4-bit CPU that could address an entire 16 nybbles of RAM. That was so much fun!

I would love to be able to get as close as possible to the "feel" of working with actual physical components.

same! We actually built an 8-bit cpu, and while debugging some very strange, seemingly random bit flips, learned why you coil wires.

I always want to read The Elements of Computing Systems, but never finish it. Playing this game for a few minutes let me pick up the book again.

Feedback....

I wanted to send a bit into two separate components and I was looking for some sort of "hub" object. It wasn't clear (to me) that you could connect many lines to a single node.

Removing lines takes a lot of clicking.

Is my design the best possible? Rather than just being told my design fits the requirements, I'd like to be told that I could have done it with one less component and offer to try again.

Yeah I'm unsure how to clearly communicate how the connectors work.

Looks as if we have hugged it to death

I can't see why my instruction decoder is failing: https://imgur.com/a/PCgkQhb

Otherwise, it's fun, although the node connections are fiddly! Maybe allow dragging from either end? Or snapping together.

Edit to add: and on the next level, the m flag doesn't exist. So, will stop there, but fun!

You need to special case "target a", it should be 1 in case bit 15 is 0. The error reporting could definitely be improved. It should probably display the exact mismatch, something like "with input XXX connector Y was 0 but was expected to be 1". Otherwise it gets to tedious to debug.

The m issue is a bug in the spec, thanks for discovering it.

Thank you for the feedback, it is much appreciated.

As for debugging, why not just put checkboxes in the input-output lookup table(s) shown on the left. And highlight the currently input line + mark wrong outputs. I think that would be intuitive.

To further build on this; If there is an intermediate state, show its pins in the diagram like output and input. If the table becomes wide, perhaps show it on the bottom. Perhaps let users add a "debug probe" from the toolbox that becomes a column in that table.

I've looked through the code a bit, I think your assembler is actually buggy. The expected results for the tests are correct, however the encoded instructions that you're feeding to the decoder are not. For example, A=1 should be 0x89F8, but you're encoding it as 0x8FE0. This causes the tests to fail despite the logic being correct.

Thank you very much for bringing this to my attention!

Actually there was a bug both in the text and in the code. A=1 should be 0x8FE0, but this was not specified correctly. I have fixed it now (I hope).

Thanks! I think this could be improved further by changing the names of the destination and source flags (all four of them) to make things clearer.

While I'm at it, here's another bug: the last test of the program engine feeds a 5 into j, which breaks things because the counter doesn't expect it at all. Also the final level doesn't have any tests but I'm sure you know that.

I want to add that besides some issues that have already been pointed out, it's a really nicely made tutorial. I went through all of it pretty fast because I already have a good background, but I would definitely point a beginner to it as a learning resource.

Thank you for finding the bugs! It shouldn't even be possible feed a 5 to a one-bit connector.

Yes I think I shot myself in the foot by designing the connectors so the labels could only be one or two letters. There is no technical reason they couldn't have descriptive labels like "clock" rather than "c". But it would probably require to turn the design "on the side", so the connectors are left-right rather than top-bottom.

I know I miss tests for a few of the levels.

Thanks for the nice words, it is encouraging!

This is really awesome. I just killed about an hour playing it part way through.

I was saddened by the fact that I lost progress when I left the page. It would be nice if progress could be save via cookies or something.

One other thing that would be nice is the ability to offer hints. These could even be just an external link to relevant material on wikipedia or equivalent.

I can't figure out why this isn't accepted as an answer for latch? Admittedly there's probably something simpler, but this seems to adhere to spec.. https://i.imgur.com/mnePQc7.png

The design does not seem to fully adhere to the spec. If you have output 0 and both w and d is 0, and then set d=1, then output changes to 1. But output should only change when w=1. Admittedly the specification is not very clearly written.

Really nice! Ideas for features i missed: Reset button. Way to see diagram of previous components. Level goal text is not equal to whats shown left. Possibly mislabeled C in full adder level. Hint option to show the count of needed components.

Thanks for the suggestions, much appreciated.

Reset for clearing all components off the canvas, or for resetting the input signals and state? Or both?

The level on subtraction doesn't mention how negative numbers are handled at all.

Thank you for noticing this error. I will add the necessary information.

In the chapter on RAM, it says we can index upto 64KB of memory in a 16 bit architecture. Shouldn't it be '128K words of memory', since we can index '2 words' with a single bit.

You are correct, the text is wrong. It should be 128KB, not 64KB. A word is two bytes (on a 16-bit architecture) so we can address 64K words which is 128KB. (I think you mixed up byte and word in your comment, but I understand what you meant.)

The explanatory text for the level does not really define neither "byte" or "word", so beside fixing the error it also need more details. (But I want to avoid going down the rabbit hole of explaining that bytes can have different sizes than 8 and so on)

That's certainly easier compared to that Build a standard conforming C++ compiler along with std libs from scratch challenge, awhile ago.

Will it be released under an opensource license? It would be nice to try to improve, especially because it is an educational tool.

Love the game. What's a good solution to the increment gate? My answer worked but seemed way too complicated.

Thanks! A possible solution [spoiler alert!] is inv(add(inv(input), inv(0)) where inv(0) is an inverter without any input.

By the way I suppose the subtraction component should be available in this task. This would make is simpler. I had trouble deciding if increment should be before or after subtraction.

There is a very annoying bug that causes a component to get stuck (output triangles disappear) and if you try to move it a copy is created.

May I ask about browser/platform and what you did to make this happen? I am not able to reproduce the issue.

I had more fun with this than I expected to. The only problem is that I got to the Full Adder level, then clicked on "About" and when I went back, my progress was not saved. It would be nice to have a way of saving and a way of showing how I built each component.

Yes that is annoying. Also all progress is lost if you leave the page. I am considering saving the state in local storage so you can return to the page and continue where you left of. Also a great suggestion to save previous levels so you can go back and review them.

Reply on news.ycombinator.com