Month: May 2025

The Sweet Learning Computer: Learning Ladder

The board for the ladder game with the piece on the bottom rung
The Ladder board. Image by Paul Curzon

Can a machine learn from its mistakes, until it plays a game perfectly, just by following rules? Donald Michie worked out a way in the 1960s. He made a machine out of matchboxes and beads called MENACE that did just that. Our version plays the game Ladder and is made of cups and sweets. Punish the machine when it loses by eating its sweets!

Let’s play the game, Ladder. It is played on a board like a ladder with a single piece (an X) placed on the bottom rung of the ladder. Players take it in turns to make a move, either 1, 2 or 3 places up the ladder. You win if you move the piece to the top of the ladder, so reach the target. We will play on a ladder with 10 rungs as on the right (but you can play on larger ladders).

To make the learning machine, you need 9 plastic cups and lots of wrapped sweets coloured red, green and purple. Spread out the sheets showing the possible board positions (see below) and place a cup on each. Put coloured sweets in each cup to match the arrows: for most positions there are red, green and purple arrows, so you put a red, green and purple sweet in those cups. Once all cups have sweets matching the arrows, your machine is ready to play (and learn).

The machine plays first. Each cup sits on a possible board position that your machine could end up in. Find the cup that matches the board position the game is in when it is its go.  Shut your eyes and take a sweet at random from that cup, placing it next to the cup. Make the move indicated by the arrow of that colour. Then the machine’s human opponent makes a move. Once they have moved the machine plays in the same way again, finding the position and taking a sweet to decide its move. Keep playing alternately like this until someone wins. If the machine ends up in a position with no sweets in that cup, then it resigns.

The possible board positions showing possible moves with coloured arrows.
The 9 board positions with arrows showing possible moves. Place a cup on each board position with sweets corresponding to the arrows. Image by Paul Curzon

If the machine loses, then eat the sweet corresponding to the last move it made. It will never make that mistake again! Win or lose, put all the other sweets back.

The initial cup for board position 8, with a red and purple sweet.
The initial cup for board position 8, with a red and purple sweet. Image by Paul Curzon

Now, play lots of games like that, punishing the machine by eating the sweet of its last move each time it loses. The machine will play badly at first. It’s just making moves at random. The more it loses, the more sweets (losing moves) you eat, so the better it gets. Eventually, it will play perfectly. No one told it how to win – it learnt from its mistakes because you ate its sweets! Gradually the sweets left encode rules of how to win.

Try slightly different rules. At the moment we just punish bad moves. You could reward all the moves that led to it by adding another sweet of the same colour too. Now the machine will be more likely to make those moves again. What other variations of rewards and punishments could you try?

Why not write a program that learns in the same way – but using data values in arrays to represent moves instead of sweets. Not so yummy!

– Paul Curzon, Queen Mary University of London

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Signing Glasses

Glasses sitting on top of a mobile phone.
Image by Km Nazrul Islam from Pixabay

In a recent episode of Dr Who, The Well, Deaf actress Rose Ayling-Ellis plays a Deaf character Aliss. Aliss is a survivor of some, at first unknown, disaster that has befallen a mining colony 500,000 years in the future. The Doctor and current companion Belinda arrive with troopers. Discovering Aliss is deaf they communicate with her using a nifty futuristic gadget of the troopers that picks up everything they say and converts it into text as they speak, projected in front of them. That allows her to read what they say as they speak.

Such a gadget is not so futuristic actually (other than in a group of troopers carrying them). Dictation programs have existed for a long time and now, with faster computers and modern natural language processing techniques, they can convert speech to text in real time from a variety of speakers without lots of personal training (though they still do make mistakes). Holographic displays also exist, though such a portable one as the troopers had is still a stretch. An alternative that definitely exists is that augmented reality glasses specifically designed for the deaf could be worn (though are still expensive). A deaf or hard of hearing person who owns a pair can read what is spoken through their glasses in real time as a person speaks to them, with the computing power provided by their smart phone, for example. It could also be displayed so that it appeared to be out in the world (not on the lenses), as though it were appearing next to the person speaking. The effect would be pretty much the same as in the programme, but without the troopers having had to bring gadgets of their own, just Aliss wearing glasses.

Aliss (and Rose) used British Sign Language of course, and she and the Doctor were communicating directly using it, so one might have hoped that by 500, 000 years in the future someone might have had the idea of projecting sign language rather than text. After all, British SIgn Language it is a language in its own right that has a different grammatical structure to English. It is therefore likely that it would be easier for a native BSL speaker to see sign language rather than read text in English.

Some Deaf people might also object to glasses that translate into English because it undermines their first language and so culture. However, ones that translated into sign language can do the opposite and reinforce sign language, helping people learn the language by being immersed in it (whether deaf or not). Services like this do in fact already exist, connecting Deaf people to expert Sign language interpreters who see and hear what they do, and translate for them – whether through glasses or laptops .

Of course all the above so far is about allowing Deaf people (like Aliss) fit into a non-deaf world (like that of the Troopers) allowing her to understand them. The same technology could also be used to allow everyone else fit into a Deaf world. Aliss’s signing could have been turned into text for the troopers in the same way. Similarly, augmented reality glasses, connected to a computer vision system, could translate sign language into English allowing non-deaf people wearing glasses to understand people who are signing..

So its not just Deaf people who should be wearing sign language translation glasses. Perhaps one day we all will. Then we would be able to understand (and over time hopefully learn) sign language and actively support the culture of Deaf people ourselves, rather than just making them adapt to us.

– Paul Curzon, Queen Mary University of London

More on …

Magazines …

Front cover of CS4FN issue 29 - Diversity in Computing

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Sign Language for Train Departures

BSL for CS4FN
Image by Daniel Gill

This week (5-11th May) is Deaf Awareness Week, an opportunity to celebrate d/Deaf* people, communities, and culture, and to advocate for equal access to communication and services for the d/Deaf and hard of hearing. A recent step forward is that sign language has started appearing on railway stations.

*”deaf” with a lower-case “d” refers to
audiological experience of deafness,
or those who might have become deafened
or hard of hearing in later life, so might identify
closer to the hearing community.
“Deaf” with an upper-case “D” refers
to the cultural experience of deafness, or those
who might have been born Deaf and
therefore identify with the Deaf community.
This is similar to how people might describe themselves
as “having a disability” versus “being disabled”.

If you’re like me and travel by train a lot (long time CS4FN readers will be aware of my love of railway timetabling), you may have seen these relatively new British Sign Language (BSL) screens at various railway stations.

They work by automatically converting train departure information into BSL by stitching together pre-recorded videos of BSL signs. Pretty cool stuff! 

When I first saw these, though, there was one small thing that piqued my interest – if d/Deaf people can see the screen, why not just read the text? I was sure it wasn’t an oversight: Network Rail and train operators worked closely with d/Deaf charities and communities when designing the system: so being a researcher in training, I decided to look into it. 

A train information screen with sign language
Image by Daniel Gill

It turns out that the answer has various lines of reasoning.

There’s been many years of research investigating reading comprehension for d/Deaf people compared to their hearing peers. A cohort of d/Deaf children, in a 2015 paper, had significantly weaker reading comprehension skills than both hearing children of the same chronological and reading age.

Although this gap does seem to close with age, some d/Deaf people may be far more comfortable and skilful using BSL to communicate and receive information. It should be emphasised that BSL is considered a separate language and is structured very differently to spoken and written English. As an example, take the statement:

“I’m on holiday next month.”

In BSL, you put the time first, followed by topic and then comment, so you’d end up with:

“next month – holiday – me”

As one could imagine, trying to read English (a second language for many d/Deaf people) with its wildly different sentence structure could be a challenge… especially as you’re rushing through the station looking for the correct platform for your train!

Sometimes, as computer scientists, we’re encouraged to remove redundancies and make our systems simpler and easy-to-use. But something that appears redundant to one person could be extremely useful to another – so as we go on to create tools and applications, we need to make sure that all target users are involved in the design process.

– Daniel Gill, Queen Mary University of London

More on…

Magazines …

Front cover of CS4FN issue 29 - Diversity in Computing

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Was the first computer a ‘Bombe’?

Image from a set of wartime photos of GC&CS at Bletchley Park, Public domain, via Wikimedia Commons

A group of enthusiasts at Bletchley Park, the top secret wartime codebreaking base, rebuilt a primitive computing device used in the Second World War to help the Allies listen in on U-boat conversations. It was called ‘the Bombe’. Professor Nigel Smart, now at KU Leuven and an expert on cryptography, tells us more.

So What’s all this fuss about building “A Bombe”? What’s a Bombe?

The Bombe didn’t help win the war destructively like its explosive name-sakes but using intelligence. It was designed to find the passwords or ‘keys’ into the secret codes of ‘Enigma’: the famous encryption machine used both by the German army in the field and to communicate to U-Boats in the Atlantic. It effectively allowed the English to listen in to the German’s secret communications.

A Bombe is an electro-mechanical special purpose computing device. ‘Electro-mechanical’ because it works using both mechanics and electricity. It works by passing electricity through a circuit. The precise circuit that is used is modified mechanically on each step of the machine by drums that rotate. It used a set of rotating drums to mirror the way the Enigma machine used a set of discs which rotated when each letter was encrypted. The Bombe is a ‘special purpose’ computing device rather than a ‘general purpose’ computer because it can’t be used to solve any other problem than the one it was designed for.

Why Bombe?

There are many explanations of why it’s called a ‘Bombe’. The most popular is that it is named after an earlier, but unrelated, machine built by the Polish to help break Enigma called the Bomba. The Bomba was also an electro-mechanical machine and was called that because as it ran it made a ticking sound, rather like a clock-based fuse on an exploding bomb.

What problem did it solve?

The Enigma machine used a different main key, or password, every day. It was then altered slightly for each message by a small indicator sent at the beginning of each message. The goal of the codebreakers at Bletchley Park each day was to find the German key for that day. Once this was found it was easy to then decrypt all the day’s messages. The Bombe’s task was to find this day key. It was introduced when the procedures used by the Germans to operate the Enigma changed. This had meant that the existing techniques used by the Allies to break the Enigma codes could no longer be used. They could no longer crack the German codes fast enough by humans alone.

So how did it help?

The basic idea was that many messages sent would consist of some short piece of predictable text such as “The weather today will be….” Then using this guess for the message that was being encrypted the cryptographers would take each encrypted message in turn and decide whether it was likely that it could have been an encryption of the guessed message. The fact that the German army was trained to say and write “Heil Hitler” at any opportunity was a great help too!

The words “Heil, Hitler” help the German’s lose the war

If they found one that was a possible match they would analyze the message in more detail to produce a “menu”. A menu was just what computer scientists today call a ‘graph’. It is a set of nodes and edges, where the nodes are letters of the alphabet and the edges link the letters together a bit like the way a London tube map links stations (the nodes) by tube lines (the edges). If the graph had suitable mathematical properties that they checked for, then the codebreakers knew that the Bombe might be able to find the day key from the graph.

The menu, or graph, was then sent over to one of the Bombe’s. They were operated by a team of women – the World’s first team of computer operators. The operator programmed the Bombe by using wires to connect letters together on the Bombe according to the edges of the menu. The Bombe was then set running. Every so often it would stop and the operator would write down the possible day key which it had just found. Finally another group checked this possible day key to see if the Bombe had produced the correct one. Sometimes it had, sometimes not.

So was the Bombe a computer?

By a computer today we usually mean something which can do many things. The reason the computer is so powerful is that we can purchase one piece of equipment and then use this to run many applications and solve many problems. It would be a big problem if we needed to buy one machine to write letters, one machine to run a spreadsheet, one machine to play “Grand Theft Auto” and one machine to play “Solitaire”. So, in this sense the Bombe was not a computer. It could only solve one problem: cracking the Enigma keys.

Whilst the operator programmed the Bombe using the menu, they were not changing the basic operation of the machine. The programming of the Bombe is more like the data entry we do on modern computers.

Alan Turing who helped design the Bombe along with Gordon Welchman, is often called the father of the computer, but that’s not for his work on the Bombe. It’s for two other reasons. Firstly before the war he had the idea of a theoretical machine which could be programmed to solve any problem, just like our modern computers. Then, after the war he used the experience of working at Bletchley to help build some of the worlds first computers in the UK.

But wasn’t the first computer built at Bletchley?

Yes, Bletchley park did build the first computer as we would call it. This was a machine called Colossus. Colossus was used to break a different German encryption machine called the Lorenz cipher. The Colossus was a true computer as it could be used to not only break the Lorenz cipher, but it could also be used to solve a host of other problems. It also worked using digital data, namely the set of ones and zeros which modern computers now operate on.

– Nigel Smart, KU Leuven

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Delia Derbyshire: Say it sounds like singing

Image by Gerd Altmann from Pixabay

Many names stand out as pioneers of electronic music, combining computer science, electronics and music to create new and amazing sounds. Kraftwerk would top many people’s lists of the most influential bands and Jean-Michel Jarre must surely be up there. Giorgio Moroder returned to the limelight with Daft Punk, having previously invented electronic disco in producing Donna Summer’s “I feel love”. Will.i.am, La Roux or Goldfrapp might be on your playlist. One of the most influential creators of electronic music, a legend to those in the know, is barely known by comparison though: Delia Derbyshire.

Delia worked for the BBC radiophonic workshop, the department tasked with producing innovative music to go with the BBC’s innovative programming, and played a major part in its fame. She had originally tried to get a job at Decca records but was told they didn’t employ women in their recording studios (big loss for them!) In creating the sounds and soundscapes behind hundreds of tv and radio programmes, long before electronic music went mainstream, her ideas have influenced just about everyone in the field, whether they have heard of her or not.

The first person to realise that machines
would one day be able to not just play music
but also be able to compose it,
was Victorian programmer, and Countess, Ada Lovelace.

So have you heard her work? Her most famous piece of music you will most definitely know. She created the original electronic version of the Dr Who theme long before pop stars were playing electronic music. Each individual note was created separately, by cutting, splicing, speeding up and slowing down recordings of things like a plucked string and white noise. So why didn’t you know of her? It’s time more people did.

– Paul Curzon, Queen Mary University of London

Magazines …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

The virtual Jedi

Image by Frank Davis from Pixabay

For Star Wars Day (May 4th), here is a Star Wars inspired research from the archive…

Virtual reality can give users an experience that was previously only available a long time ago in a galaxy far, far away. Josh Holtrop, a graduate of Calvin College in the USA, constructed a Jedi training environment inspired by the scene from Star Wars in which Luke Skywalker goes up against a hovering droid that shoots laser beams at him. Fortunately, you don’t have to be blindfolded in the virtual reality version, like Luke was in the movie. All you need to wear over your eyes is a pair of virtual reality goggles with screens inside.

When you’re wearing the goggles, it’s as though you’re encased in a cylinder with rough metal walls. A bumpy metallic sphere floats in front of the glowing blade of your lightsaber – which in the real world is a toy version with a blue light and whooshy sound effects, though you see the realistic virtual version. The sphere in your goggles spins around, shooting yellow pellets of light toward you as it does. It’s up to you to bring your weapon around and deflect each menacing pulse away before it hits you. If you do, you get a point. If you don’t, your vision fills with yellow and you lose one of your ten lives.

Tracking movement with magnetism

It takes more than just some fancy goggles to make the Jedi trainer work, though. A computer tracks your movement in order to translate your position into the game. How does it know where you are? In their system, because the whole time you’re playing the game, you’re also wandering through a magnetic field. The field comes from a small box on the ceiling above you and stretches for about a metre and a half in all directions. Sixty times every second, sensors attached to the headset and lightsaber check their position in the magnetic field and send that information to the computer. As you move your head and your sabre the sensors relay their position, and the view in your goggles changes. What’s more, each of your eyes receives a slightly different view, just like in real life, creating the feeling of a 3D environment.

Once the sensors have gathered all the information, it’s up to the software to create and animate the virtual 3D world – from the big cylinder you’re standing in to the tiny spheres the droid shoots at you. It controls the behaviour of the droid, too, making it move semi-randomly and become a tougher opponent as you go through the levels. Most users seem to get the hang of it pretty quickly. “Most of them take about two minutes to get used to the environment. Once they start using it, they get better at the game. Everybody’s bad at it the first sixty seconds,” Josh says. “My mother actually has the highest score for a beginner.”

The atom smasher

Much as every Jedi apprentice needs to find a way to train, there are uses for Josh’s system beyond gaming too. Another student, Jess Vriesma, wrote a program for the system that he calls the “atom smasher”. Instead of a helmet and lightsaber, each sensor represents a virtual atom. If the user guides the two atoms together, a bond forms between them. Two new atoms then appear, which the user can then add to the existing structure. By doing this over and over, you can build virtual molecules. The ultimate aim of the researchers at Calvin College was to build a system that lets you ‘zoom in’ to the molecule to the point where you could actually walk round inside it.

The team also bought themselves a shiny new magnetic field generator, that lets them generate a field that’s almost nine metres across. That’s big enough for two scientists to walk round the same molecule together. Or, of course, two budding Jedi to spar against one another.

– the CS4FN Team (from the archive)

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Bits with Soul (via a puzzle)

Image by Gerd Altmann from Pixabay

In January 2025 computer scientist Simon Peyton Jones gave an inspiring lecture at Darwin College Cambridge on “Bits with Soul” about the joy, beauty, and creativity of computer science … from simple ideas of data representation comes all of virtual reality.

Our universe is built from elementary particles: quarks, electrons and the like. Out of quarks come protons and neutrons. Put those together with electrons in different ways to get different atoms. From atoms are built molecules, and from there on come ever more complexity including the amazing reality of planets and suns, humans, trees, mushrooms and more. From small things ever more complex things are built and ultimately all of creation.

The virtual world of our creation is made of bits combined using binary, but what are bits, and what is binary? Here is a puzzle that Simon Peyton Jones was set by his teacher as a child to solve, to help him think about it. Once you have worked it out then think about how things might be built from bits: numbers, letters, words, novels, sounds, music, images, videos, banking systems, game worlds … and now artificial intelligences?

A bank cashier has a difficult customer. They always arrive in a rush wanting some amount of money, always up to £1000 in whole pounds, but a different amount from day to day. They want it instantly and are always angry at the wait while it is counted out. The cashier hatches a plan. She will have ready each day a set of envelopes that will each contain a different amount of money. By giving the customer the right set of envelope(s) she will be able to hand over the amount asked for immediately. Her first thought had been to have one envelope with £1 in, one envelope with £2 in, one with £3 and so on up to an envelope with £1000 in. However, that takes 1000 envelopes. That’s no good. With a little thought though she realised she could do it with only 10 envelopes if she puts the right amount of money in each. How much does she put in each of the 10 envelopes that allows her to give the customer whatever amount they ask for just by handing over a set of those envelopes?

Simon Peyton Jones gives the answer to the puzzle in the talk and also explores how, from bits, come everything we have built on computers with all their beauty and complexity. Watch the video of Simon’s talk on youtube to find out. [EXTERNAL]

– Paul Curzon, Queen Mary University of London (inspired by Simon’s talk as I hope you will be)

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos