7c0h

Articles tagged with "programming"

Moon landing in Basic

As many other people around my age, I learned programming from a book. In particular, I started programming with a 3-books series called Computación para niños (Computers for kids). Volume 3 was dedicated to programming in BASIC, and it opened the door to what is now both my profession and hobby.

That said, that book was also the source of a 25-ish-years-long frustration, and that story is the point of today's article.

In the ancient times known as "the 90s", it was still common to get printed code for games that you had to to type yourself. This book, in particular, included a game called "Lunar rocket" in which you were supposed to (surprise!) land a rocket on the moon. For context, this is how the game was sold to me:

Picture of a book page, showing
illustrations of how to play the game

And this is what the code looks like:

Picture of a book page,
showing BASIC code for a program

Suffice to say, the program never worked and I couldn't understand why. I spent weeks trying to tweak it to no avail, getting different errors but never making a full run. And no matter how hard I tried, I could never get a single picture to show on screen. Eventually I gave up, but the weeks I spent trying to understand what I did wrong have been on my mind ever since.

That is, until last Sunday, when I realized that I should go back to this program and establish, once and for all, whose fault all of this was.

Problem number one was that the book shows pretty pictures, but the program is text-only. That one is on me, but only partially. Sure, it was too optimistic of me to expect any kind of graphics from such a short code. But I distinctly remember giving it the benefit of the doubt, and thinking "the pictures are probably included with BASIC, and one or two of these lines are loading them". That was dead wrong, but I'll argue that young me at least had half of a good idea. A few years later I would learn that the artwork and the game rarely had anything to do with each other, a problem that has not entirely gone away.

Now, problem number two... That code I showed above would never, ever work. My current best guess is that someone wrote it in a rush leaving some bugs in, and someone else typed it and introduced a lot more. In no particular order,

  • Syntax errors: Line 130 has a typo, the variable name "NÚMERO" is invalid because of the accent, and line 150 is plain wrong. The code also uses ";" to write multiple instructions in a single line, but as far as I know that's not valid BASIC syntax.
  • The typist sometimes confuses "0" with "O" and ":" with ";" and " ". This introduced bugs on its own. Line 150 (again) shows all mistakes at once.
  • Error handling is a mess: if you enter the wrong input, you are simply asked to enter it again. No notification of any kind that you did something wrong.
  • The logic itself is very convoluted. GOTOs everywhere. Line 440 is particularly bad, and could be easily improved.
  • Some of the syntax may be valid, but it was definitely not valid in my version of Basic. And seeing how my interpreter came included with the book, I feel justified in not taking the blame for that one.

And so I set out to get this to run once and for all. The following listing shows what a short rewrite looks like:

LET DISTANCE=365000
LET BARRELS=100
LET MASS=1000
LET TIME=60
LET A0=0
LET VO0=0
LET V0=0
LET EO0=0
LET E=0
LET F=0
LET THROWS=0
DO WHILE BARRELS>0 AND E<=364900 AND THROWS <= 30 
    LET REMAINING=DISTANCE-E
    PRINT "DISTANCE SO FAR="; E
    PRINT "DISTANCE TO GO="; REMAINING
    PRINT "SPEED"; V
    PRINT "BARRELS LEFT="; BARRELS
    PRINT "THROWS LEFT(MAX 30)="; THROWS
    PRINT "-----"
    INPUT "NUMBER OF BARRELS?"; NUMBER
    INPUT "DO YOU WANT TO BRAKE (Y/N)"; RESP$
    IF NUMBER>BARRELS THEN
        PRINT "NOT ENOUGH BARRELS!"
    ELSEIF RESP$ <> "Y" AND RESP$ <> "N" THEN
        PRINT "INVALID INPUT!"
    ELSE        
        LET THROWS=THROWS+1
        LET BARRELS=BARRELS-NUMBER
        IF RESP$="N" THEN
            LET F=(F+NUMBER*1000)*0.5
        ELSE
            LET F=(F-NUMBER*1000)*0.5
        END IF
        LET A=F/MASS
        LET V=VO+A*TIME
        LET E=EO+VO*TIME+0.5*A*TIME*TIME
        LET EO=E
        LET VO=V
    END IF
LOOP
IF BARRELS <= 0 THEN PRINT "MISSION FAILED - NOT ENOUGH FUEL"
IF THROWS > 30 THEN PRINT "MISSION FAILED - NOT ENOUGH OXYGEN"
IF E>364900 THEN
    IF V<5 THEN
        PRINT "MISSION ACCOMPLISHED. ROCKET LANDED ON THE MOON."
    ELSE
        PRINT "MISSION FAILED. ROCKET CRASHED AGAINST THE MOON SURFACE."
    END IF
END IF

I think this version is much better for beginners. The code now runs in a loop with three clearly-defined stages (showing information, input validation, and game status update), making it easier to reason about it. And now that the GOTOs are gone, so are the line numbers. However, and in order to keep that old-time charm, I kept all strings in uppercase and added no comments whatsoever.

I also added some input validation: the BASIC interpreter I'm using (Bywater Basic) will still crash if you enter a letter when a number is expected, but that's outside what I can fix. At least you now get a message when you use too many barrels and/or you choose other than "Y" or "N".

It is only fair to point out something that I do like about the original code: that the variable names are descriptive, and in particular that the physics equations use the proper terms. If you are familiar with the physics involved here, those equations will jump at you immediately.

If I had time, I would still tie a couple loose ends in my version. A proper rewrite would ensure that the new code behaves exactly like the old one, bugs and all. And there's a good chance that I have introduced some new bugs too, given that I barely tested it. I also feel like making a graphical version, using the original artwork and adding some simple animations on top.

But even then, I finally feel vindicated knowing that younger me had no chance of making this work. Even better: the next exercise, a car race game, just gave you a couple pointers on how to draw something on the screen, and then left you on your own. That one would take me some time today.

Next on my list: finally read the source code of Gorilla.bas. I know I tried really hard to understand it when I was 10, so maybe I should get closure for that one too.

A neural network in Javascript

A couple days ago I found a very interesting article, titled A neural network in 11 lines of Python. I always wanted to get a visualization of how a neural network works, so I took this as my opportunity. Taking that article as a base, I created a nice visualization of the simple case, and it ended up looking very nice.

This post is a small version of that. I'm going to show you how a neural network does its magic, using the magic of Javascript and SVG graphics.

InputsOutput
0010
1110
1011
0111

This is the function we'll learn. Implementing XOR is pretty much the "Hello, World" of neural networks, so we'll be doing the same here.

Also, note that the third input column is all 1's. This will be our bias unit (i.e., a column that always equals 1).

Now, let's plug this into our network.


This is a graphical representation of our neural network. The weights have been randomly initialized (you can check that by reloading the page). Neurons 0-2 are input, neurons 3-4 are the hidden layer, and neuron 5 is output. Given that we have 4 training examples, we'll follow each training example individually.

The computation should proceed as follows: for neuron 3, we'll first multiply neurons 0-2 by the value of the edge that connects both neurons, sum those three values, and apply the sigmoid function to the result. In formal terms, $$n_3 = sigmoid(n_0 w_{0,3} + n_1 w_{1,3} + n_2 w_{2,3})$$ where ni is the i-th neuron, and wi,j is the weight that connects the neuron wi with the neuron nj.
The sigmoid function guarantees that the value for neuron 3 will be a value between 0 and 1. We repeat the same process for neurons 4 and 5.


So here we can see what our network is actually computing. If you have not yet read the article to the end, there's a very good chance that our network is returning random garbage, and that's fine - we haven't trained it yet, so of course the output makes no sense. This is called the forward step, in which I test my network and see what it's being computed.
For the second step, backpropagation, we'll need to write a couple tables, and see how bad our results are.


Output
(expected)
Output
(network)
Error
0000
01-10
1100
1010

Here is an interesting fact. We will call the difference between the value I expected and the one I actually got the "error" of the network. Similarly, sig(x) will represent the sigmoid function, and sig'(x) will be its derivative. Having defined that, the following equation $$error*sig'(output)$$ tells me how much should I correct my weights, and in which direction (whether they should be bigger or smaller). I won't delve in the math for that now, but if you need more details there are some links at the end that can help you.

So we have now applied our corrections to the green weights, but how about the red and blue ones? We'll also correct those by applying a variation of the same principle: once I corrected the value for the output, I have to distribute the amount of error into every weight that contributed to its computation. This will allow me to correct the values for neurons 3 and 4, which I'll finally use to correct the values for the remaining weights.
This process is called backpropagation, because I'm analyzing the network backwards to correct the errors I made when computing forwards.

Now all that remains for the training process is for me to repeat these steps over and over, until the er ror (shown underneath) is small enough.

Error
0
0
1
1

You can click any of the buttons here. One of them will perform one step of the calculation (both forward and backpropagation), while the other ones will perform one hundred and one thousand steps respectively. Using this, you can verify that the network eventually learns how to perform XOR, and then it stabilizes. Reloading the page will start all over again, but with different random weights for the network.

This is a very simple neural network (although not the simplest), implemented in Javascript. I've skipped some details in order to make the whole process simpler - If you want something slightly more challenging, I definitely suggest you to read the original article, which goes into the right level of detail.

I still want to improve on this, but I'm not entirely sure how. I think it would be nice to see how some neurons are given more (or less) weight, but I'm not sure how this should look like. If you have any ideas, feel free to tweet me.

Note: If you are quick enough, you might have noticed that the bias unit is missing in the hidden layer. The short version is: yes, it is. I only noticed once it was too late. I'll try and fix it in future revisions of this article.