Programming through the Ages

I've been programming for around 45 years and in that time I've created hundreds of different programs, mainly games. For a brief time, early in my career, I was a professional programmer, writing COBOL on ICL Mainframes. But the vast majority of my programming is as a hobby and in this article, I'd like to present a curated history of what I have created, highlighting the things I'm most proud of.

One immediate problem is that a lot has been lost. For example, I created a Space Invaders game for a ZX81 (yes, I'm that old) and at University, I created an Olympic Decathlon game for a NASCOM (google it :)). Both unfortunately lost but below I give a number of examples that are still accessible and in many cases, still playable/usable)

Pi Picture

Let's start with computer art. Below is a picture of a circle. At first glance, it seems unremarkable.

But if we look a little closer; in fact if we zoom in a lot closer to the top left hand corner of the image, we would see this :-

In other words, the picture is made from the first 100,000 digits of pi itself. If you like it, feel free to download it here. (It would be nice if you credited me in some way)

pi140411.pdf

Download PDF • 178KB

Music Improvisation

Now let's turn to Computer Music. There are many ways of creating computer-generated music. This example uses the concept of something called a Cellular Automaton or CA, If you're new to this concept, probably best if you read my article that talks about what a CA is :-

https://joeamgaines.wixsite.com/morevoices/post/something-from-nothing

Now that you are armed with this information, we can look at one interesting use of CAs - creating music. We've all seen the news around AI creating music but CA's, especially in the form of Rule 110 (see above article), have some built-in advantages.

Rule 110

As per the article, Rule 110 operates on the edge of order and randomness. And if we think about music, doesn't it also operate on this 'edge'?

• Music that is too repetive quickly becomes boring.

• Music that is too random is, just well, too random.

For a nice example of 'too random', check out Cecil Taylor's 'Unit Structures' https://www.youtube.com/watch?v=Y2Tdye6xuGI&t=77s)

So, in principle, Rule 110 could be promising as a way of creating interesting music so I decided to try it out. I created a program that made it's note and chord choices based on the generated 'rows' from Rule 110.

And Voila! I present to you, 'On the Edge' by Steve Gaines featuring Rule 110 (or should that be the other way round?)

Rule110 On the edge.wav

Download WAV • 36.69MB

What do you think?

Chess

My first attempt at programming Chess was back in my University days in the mid-80's. For my final year project, I decided to create a chess program with the ambition of it being able beat me (I'm one or two notches above beginner). I failed quite badly. I remember submitting my program to the University 'mainframe' to run overnight, playing against itself. The idea was that I would analyze the game play the next morning in order to tweak the program to play better. After running on the computer for over 12 hours, my program had made a total of 4 moves (2 for white, 2 for black). Embarassing!

After this debacle, I did make some improvements to the extent that the program played without making colossal blunders every move, but it never achieved my ambition of being able to beat me.

I learned that the year after I left, one poor student's final year project was to 'improve the performance' of my program. I wonder how they got on?

Attempt 2

My second attempt was around 11 years ago and I experimented with a more advanced set of algorithms. Most chess engines (including mine) use an approach invented by the mathematician John von Neumann. Von Neumann is worthy of an article of his own but for now, let's focus on his MiniMax algorithm. The basic idea is that the program looks at all the available legal moves in a position. Then, for each of these, it looks at all the legal responses to each move, and all the legal responses to the responses etc etc.

At some point, the computer stops 'searching' and 'scores' the board. i.e. who is winning. It then selects the first move of the sequence with the best score.

You may be wondering why it stops searching. Why not keep searching until you know who has won? A little calculation will show you why.

At every position on the board, a player has, on average, 3o possible legal moves it can make. So we can calculate how many positions we have to search in order to look ahead just 4 moves (i.e. White, Black, White, Black)

30 x 30 x 30 x 30 = 900,000 positions.

An efficient algorithm can do this in a small fraction of a second on a modern PC. So what's the problem?

What if we look ahead 10 moves i.e.

30 x 30 x 30 x 30 x 30 x 30 x 30 x 30 x 30 x 30 = 590,490,000,000,000 positions.

And to think 10 moves is just 5 alternating moves by Black and White! A typical chess game is around 40 moves (by each player) so this is 30 to the power of 80. This number is in the ballpark of the number of atoms in the universe. In other words, if the program searched exhaustively to the end of the game, we would have to wait to beyond the end of the Universe for the first move.

But back to my program. I implemented the Minimax algorithm plus a number of improvements to make it more efficient. It worked and it played quite well. But as I was testing, I quickly discovered a fatal flaw. I played the program against itself where White was set to Beginner level and Black was set to the Top level (different levels are essentially how far ahead the program looks). Here's a screenshot of a typical game

The fatal flaw was that the algorithm ruthlessly took all of its opponent's pieces, queened a number of its own pawns but then systematically failed to deliver the coup-de-grace checkmate. I took a screenshot of the remarkable position above - I've never seen anything like it on a chess board before or since!

Although I cannot be sure, very likely the cause of the bug, was something like a simple minus sign in the wrong place somewhere! Welcome to the Joy of Programming - a tiny error of one character in some code can be magnified to change the behaviour of a program completely!

Attempt 3

I revisited chess programming back in 2018 now determined to achieve my ambition.

I started building a new chess engine called 'Joe' (named after my son).

Chess programming is certainly not trivial but at the same time there's a lot of help available on the internet. After a few months (mainly weekends), Joe was ready to play. Here's a screenshot :-

You can see 'Admin' (that's me!) in the early stages of a game against Joe. It plays a decent game and can usually beat me although it would be annihilated by the top engines (but they would annihilate even the very best human grandmasters).

So although I could keep improving the engine, I decided that I had achieved my ambition so I consider the project complete :)

Turing Machine

The concept of a Turing machine was created by Alan Turing in his paper

'On Computable Numbers with an application to the Entscheidungs problem'

(https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf).

In the paper, Turing describes a mechanical process for computation based on the idea of an 'infinite' moveable paper tape and a 'head' that is capable of reading the current symbol, erasing a symbol or printing a new symbol on the tape.

Below you can see an example of a 'Turing Machine' with its tape and symbols. Also note the triangle which is the 'head'.

Note that the tape can extend indefinitely to the left and right i.e. is infinite but in practise a real tape can be very long but of course not infinite.

'Inside' the head is a program that decides what to do.

The basic idea is that the head 'reads' the symbol at the current position on the tape and can perform one of 4 actions based on the read symbol:-

• Erase the current symbol

• Print a symbol (e.g. '1' or '0' or 'S' etc)

• Move the tape left one position

• Move the tape right one position
  

With just these operations, Turing created something very powerful - a Turing Machine that can perform any calculation that a modern supercomputer can perform, albeit trillions upon trillions of time slower.

Creating a Turing Machine

I decide to create a 'virtual' Turing machine and a program to run on it. By 'virtual' Turing machine I mean a simulation of a paper tape and head in software.

This was inspired by a truly wonderful book by Charles Petzold called "The Annotated Turing". In this book, Petzold walks you through Turing's paper and the concept of the Turing machine.

Writing a program to run on a Turing Machine is quite a laborious task. Modern programming languages like Java, C++ and others provide a rich vocabulary for writing code. But remember when writing programs for Turing machines there are just 4 possible instructions

ERASE, PRINT, LEFT, RIGHT

Plus of course making a decision based on the current symbol at the head

e.g.

If the symbol = 'S' then RIGHT

If the symbol ='1' then ERASE

To give a very simple example. A program to simply print the number 546 would be :-

PRINT 5

LEFT

PRINT 4

LEFT

PRINT 6

Why LEFT above and not RIGHT? I'll leave you to work that out!

The particular Turing machine program below will add two binary numbers together.

(If anyone is particularly curious , I can send you the code for the program.)

To start, the program 'primes' the tape with certain symbols.

Basically this is the input data for the machine. i.e. the machine will add the binary numbers 1011 and 1010 together.

We can see the machine (my simulation) run the program below :-

Note that the program requires 377 steps just to add two numbers together! Writing a program to do anything remotely useful would likely take millions of steps.

But the important point here is that all computers today derive from this fundamental conception: Turing's machines are Universal.

Turing never built a physical machine - his machines were a thought experiment created to solve a mathematical problem - but some people have taken him literally and built physical Turing Machines.

Take a look at this beautiful mechanical creation https://www.youtube.com/watch?v=E3keLeMwfHY

Survive!

I've not only been creating games for decades but also I have been playing computer games since they first arrived on the scene back in the 70's. Adventure(pure text!), Pong, Space Invaders, Asteroids (one of the best ever) and of course, Doom, the game that started the First Person Perspective revolution.

As an aside, there is now a tech challenge 'meme' of making Doom run on all forms of computer. Doom was released in 1994 and at the time required a powerful PC to play. Now, 30 years later, pretty much any form of computer has the horsepower to run Doom. Take a look at my favourite of these :- https://youtu.be/cO-Are8053g

One genre that really captured my attention was that of the survival game. In such games, the player has to collect resources, build a shelter, eat, drink and survive against the elements, various creatures and often, other players. My favourite of these is called Rust. In Rust, you are marooned on a beach on an island. You are naked and just have a solitary rock with which you can collect resources like wood or stone and, hit other players.

At this point, I imagine I've split the audience into two groups

• Group 1: 'What kind of person really are you, Steve?'

• Group 2: 'How can I play this game?!' (Try here https://store.steampowered.com/app/252490/Rust/)

Anyway, based on this experience, I had the ambition of creating my own survival game. I would say that this was perhaps the most ambitious project I have ever embarked upon. First of all, such survival games are invariably 'first-person' - in other words, what you see on the screen is your view of the world, through your eyes. The first challenge is therefore to create a realistic looking world.

Initially, I had created this manually after researching various algorithms for creating realistic looking terrain. The results were mixed. Here's a video of my first attempt, many years ago :-

Note that the spheres chasing you were taken directly from the 1960's cult TV series 'The Prisoner', hence the name.

For a first attempt, it wasn't bad but I wanted something that looked much more realistic. This brings us forward to around 2020 (during the pandemic - we had plenty of time) when I created 'Survive!'. This was much closer to what I wanted. Take a look :-

After this video was made, I made further progress with adding survival elements e.g. making a tent, cooking food, building a shelter but I realised that the mountain of work left to do was just beyond me, given I have a full-time job so I had to shelve it.

Will I regret this in the future? Perhaps, but I'm quite proud of how far I got.

Mah Jong

Mah Jong is an ancient game played with 'tiles' - small blocks, traditionally made of bamboo and ivory but typically plastic these days. It is a 4-player game where you need to create sets or melds of different tile types. Think 'Advanced Rummy'.

However, there is a simple puzzle form of the game where you need to remove pairs of tiles from an initial 'pile'. If you can remove all the tiles, you win.

Typically, the game cannot be solved by just randomly taking pairs of tiles. This is best explained with the video below that shows my implementation of this version of the game.

You can see that the tiles are stacked, sometimes 3 or 4 deep, and removing pairs in random order will often mean you get stuck and need to try a different sequence.

If this sounds like fun, the game is available to play for Windows or MAC - let me know :)

Duel

Back in 2011, I started learning how to program for Android. Back then, it wasn't so well documented so there was a lot of trial and error, mainly error. I eventually got my first Android program up and running on an actual Android phone! It just displayed 'Hello World'.

After that minor success, I was thinking about what my first real program would be. I noticed that Android phones had sensors that were able to detect things like the phone being tilted, or facing in a certain direction e.g. North. This triggered the ideal of Duel.

In Duel, the idea is that players race against the clock to perform a set of maneouvres e.g.

NORTH, UP, EAST, FLAT, DOWN, WEST

The fastest to perform the sequence wins..simple as that. There were various sequences to try and the possibility of setting a World Record.

I imagined young men in a pub, playing Duel to decide who pays for the next round. So, I published the game on Android Play Store and set a fee of one pound. A couple of people actually bought it so I could now legitimately claim that I was a professional programmer.

One problem remained. Every time I mentioned the game to people, the first question was invariably 'Is there an iPhone version?'. My answer was an emphatic No! because I only had the skills for Android at that time.

Fast forward a number of years and I became familiar with a language called JavaScript. JavaScript is built-in to every browser :- Chrome, Firefox & Apple's Safari. This triggered the thought, Could I write Duel in Javascript so it's playable by anyone?

Duel 3.0

This brings us to the present day. After a lot of tinkering - different browsers have an interesting approach to web standards (cough, cough Apple) - Duel v3.0 became available as a 'pre-release' (meaning it works but there's probably bugs lurking.)

It's not currently online but can be made so :)

Trader

I've always been fascinated with the fast-paced world of traders in a stock exchange. Buying, selling even shorting stocks sounded fun but of course dangerous.

Also, when I was young my father made such a game based on just electronic components. We loved playing that as a family.

Here's a picture of that game :-

Note that the whole game, including the wooden frame, painting, electronics etc was built by him - impressive!

Here's a details of the controls

The millionaire button lights up when you have a million!

Inspired by him, I decided to make a game that (hopefully) provided a similiar level of fun but updated for the modern age.

Trader

Trader is a multi-player game where players use their phones to buy & sell stocks on a virtual stock exchange. Each player has to make instant decisions just like real traders. And just like the real world, news events happen in real time which can affect stock prices dramatically.

Here's a screenshot from the game showing a newsflash :-

The game ends when one player has made a million dollars. Fast-paced and a little frantic but, in my view, a lot of fun.

The game is not currently available online right now but that could change :)

Gin Rummy

Card games are a perennial favourite to program and the App Stores are flooded with all kinds of games available to play on your phone. But I always thought there was one important element missing, namely that you have to look at a screen rather than play with real cards. Related to this, my wife and I like to play Bridge but we always found it difficult to find other couples to play (Bridge is a 4 player game). We would sometimes find a friend who wanted to play but they didn't have a partner or the partner wasn't interested in Bridge. This triggered the idea, back in 2007, of Fourth4Bridge.

Fourth4Bridge

The central idea is to create a computer player that was capable of understanding the game and specifically understanding what physical cards it 'held' and which cards are being played by the other players.

This first part was solved by using NFC/RFID technology since , at that time, RFID sensors were fairly cheap and could be plugged into a USB port on a PC. The other essential piece of tech were RFID tags. These tags are esentially small, thin stickers with RFID built into them - see here

Note: the sticker has to be very thin - fraction of a millimetre - or a hand of cards is difficult to hold!

By bringing the card close to the sensor, the PC can read the tag. Then with a relatively simple piece of programming, you can associate a tag with a particular card, and this forms the basis of making the game work. The other component was to to use speech generation in order for the computer player to communicate its decisions to the three human players.

Overall, Fourth4Bridge worked, albeit as a rather clunky user experience. In addition, programming Bridge logic, especially the Bidding, is a rather formidable task. For this reason, Fourth4Bridge was shelved.

This brings us to the next generation.

Gin Rummy

The idea for Gin Rummy came from seeing people use their phone to pay for things in shops and restaurants. The technology that powers such transactions is the exact same technology described above.

This inspired me to revisit the Fourth4Bridge project with a view to programming the whole thing on the phone itself - no need for a laptop or external sensors. At the same time, I realised that the Bridge logic problem remained so I decided to opt for a simpler game - Gin Rummy.

GinRummy is from the Rummy family of games and is perhaps considered to be one of the best of that genre. The essential idea is to create melds consisting of sets of the same card (e.g. 3 sevens) or sequences (e.g. 4, 5, 6 & 7 of diamonds).

The logic for GinRummy is an order of magnitude simpler than Bridge and this made it relatively simple to make work on an Android phone.

And NO!, there is no iPhone version :)

The phone detects the cards as they are dealt by the dealer brushing the card across the NFC sensor in the phone, and then the phone announces its moves through generated speech. Overall, this works pretty well.

Interestingly, every time I have played against the App, I have lost - it plays a pretty mean game.

If anyone would like this App, let me know.

BargePole

Have you ever heard someone use a phrase or saying incorrectly? The inspiration for this program came from many years ago when a former work colleague was very surprised by something at work and said :-

"You could have knocked me over with a bargepole"

It still makes me laugh to this day.

Another example was a friend of mine who's grandmother uttered the classic

"He smokes like a trooper"

From that point on, we were always using '..like a trooper' to describe something done to excess e.g "He drinks like a trooper" etc etc

Based on this inspiration, I created BargePole, a 'Random Saying Generator'. You click a button and BargePole, generates a phrase.

Here are some generated examples :-

• In the future, everyone will have fifteen minutes of wind

• Stick your head up above the omelette

• Genius is 1 percent inspiration and 99 percent money

• Beware of Greeks bearing socks

If this is your cup of porridge, give it a go here :-

BargePole

NOTE: This is NSFW - some of the generated phrases are not "family friendly"

Honourable Mentions

Sound Adventure

'Kids spend too long looking at screens' they say. Well what if they could play a computer game without looking at a computer? Impossible?

I decided to make a game that followed this principle. In Sound Adventure, you interact with the game through listening and speaking only - there is nothing to see.

For example, you would hear the computer (in fact a phone) say :-

"You are in a garden. To the North you can see a large country house. To the West is a small cottage"

The Player then speaks their command e.g. "Go North" and the game continues with player finding and picking up objects and solving puzzles.

It needs further development but I think it has potential - contact me if you agree.

3 Body Problem

A simulation based on the classical mathematical problem. Three gravitational bodies interact in very interesting ways.

Here's a video of a sample run.

Tubes

In Tubes, the player traverses a Tube Map (an imagined Kraków Metro system) in order to locate objects and at the same time avoid being caught by the Ticket Inspectors. As the levels increase, everything gets very fast and frantic. It's quite fun to play

Flying Biker

Sitting on an exercise bike, you fly over terrain and pick up objects. You guide the 'plane' with your body movement. Lean to the right or left. Cycle faster to gain altitude.

MetaMeta

I created MetaMeta around 15 years ago. In MetaMeta, the rules of the game change, as you are playing. There are two versions a computer version where you play against the computer or in fact, a better, board game version with no computers involved.