coding
mighty biomorphin’ power rangers
It’s been a while since my last post, mainly because I’ve seen a lot of impressive work in various places and I’ve felt very small and insignificant in comparison. I also went on a training course recently which claimed that 80% of people achieve only 20% of their potential. As someone who likes to potter about and explore different things, I know that I fit into this category. Perhaps I ought to buckle down and concentrate on one particular thing. But the use of the word ‘ought’ is enough to put me off. Like most people, I’m not good at persevering at something I’m not been interested in.
I’d been feeling this despondency to such an extent that I was beginning to wonder whether I’d reached the end of my little experiment in genetic algorithms. For various reasons I’d not had a session with Ollie on Skype for several weeks until tonight , and I was starting to wonder whether it was worth chasing down every little aspect of code. I know now how to implement these algorithms, so perhaps it was time to move onto something else.
Well, how foolish was that thought? Very.
Tonight’s session was stimulating. Ollie suggested a technique to overcome a particular coding problem (showing me that I needed to convert in one place from an Integer object to a primitive int), as well as getting me to think of a way to speed up the routine that checks whether each fly has been trapped by a web. Those are both very useful for the sketch, but what really got me interested was the discussion afterwards about where we could take this next.
I was getting bogged down in the appearance of the sketch and in the limited number of characteristics included in the coding. So far I’ve been using ellipses as a quick and dirty representation of webs. These are both boring and limited, but because the webs are a class, it would be easy to replace the ellipses with something else, such as Richard Dawkins’ biomorphs. Rather than use human intervention to select which creatures breed, they could be ranked on their success in trapping flies. This opens up a lot of possibilities. If a fly successfully moves past the outer edge of the biomorph, then an inner arrangement would be useful to add another layer to trap it. This means that sheer size isn’t the only aspect of a successful predator.
The more successful webs could have more energy to use in the next generation, so some might evolve to require lots of energy but therefore need to trap a lot of flies, while others might need less, and therefore survive on very few flies. It would be possible to reach a point where some creatures have evolved so far from each other that they can’t breed with each other. The flies could evolve too. Very soon there could be enough complexity that it would be difficult to predict the results. Suddenly I’m very interested again in this exercise.
private functions
I’m on a roll now, with a second abstract class, this time to handle the breeding of creatures. I’ve kept it general, so it could be used for other genetic algorithm sketches.
One method, for the first generation, returns a string of random 1s and 0s, while another (still to be tested) accepts two ‘parents’ and breeds them, with an optional chance of mutation. I’ve also moved some functions, such as building the webs out of the DNA, into the web class and made them private so they can’t be accessed from outside. It’s all looking a lot more organised and controlled.
class converters
Got it! Rather than think of classes as objects, think of them as containers for groups of related actions.
I now have my first abstract object: a function to convert four digits of zeroes and ones from Gray Code to Base 10. My genetic algorithm sketch doesn’t require conversion in the other direction or alternative class constructors to handle different quantities of digits, but it would be simple to add the required functions to the class. Next subject for a class: breeding new generations of webs.
apologies in advance for the geek talk
I spent most of the weekend struggling with the genetic algorithm sketch in Processing. I’d created a version that worked but was coded very inefficiently using strings, so I wanted to rewrite it using arrays. It was galling to find that my attempt at efficiency refused to work at all.
A few hours away from the computer, however, allowed me to think it through afresh, and I saw where I was making a mistake. I hurried home on Monday after work to rewrite the troublesome section in time for the Skype session with Ollie, and voila! It worked. I quickly added the ‘fly‘ class from previous versions, only to find, on calling one of the fly methods, that I received an error message I’ve never seen before: ‘Badly formed character constant’. All that the method does is draw a small rectangle to represent the current position of the fly object.
OK, so I’ve searched my Processing books and Google for an explanation of this, and found some oblique references, but what startled me was that during the Skype session, when I was demonstrating this problem, it worked fine, but as soon as the session was over and I tried again, I got the same error message. I must have changed something somewhere, but I have no idea what. Grrr.
Anyway, after discussing the latest version of the sketch, we agreed that I should refactor the code to use more classes and some ArrayLists. Neither step is completely new for me, but I’m taking tentative steps into unfamiliar territory, especially the idea of using abstract classes that have no real world counterparts like ‘fly‘ and ‘web’. The next week will be busy with other things, so it can be simmering at the back of my mind. If I appear distracted over the next few days, you’ll know why.
but you still need a human to replace the car on the track…
In what may well be the best (in the sense of most fun) use of Arduino that I’ve yet seen, someone has created an equivalent of Scalextric. It has an arcade game cockpit for the remote control of a car with an on-board camera, where the video feed is sent back to the cockpit. Yes, it looks like a lo-tech game of Wipeout without any competitors, but I’d love to have a go.
mr jack
I’ve just played Mr Jack, a board game with a Jack the Ripper theme that’s a mixture of Cluedo and Mastermind. The mechanics are simple – there are only eight character pieces, any one of which could be the murderer, plus a few streetlamps, cordons and manhole covers that can also be moved. One player knows who the murderer is and has to prevent his or her identity becoming known, while the other has to deduce the identity correctly within a limited number of moves. Each character piece, however, has particular abilities, so there are sufficient variations and permutations to make it difficult to work out the best moves.
The reason I mention this game here is that the simple mechanics would make it a good candidate for a computer to play as the computer wouldn’t be distracted by the major changes to the board after each turn, rather like Reversi, though there would be more potential moves per turn. Looking several moves ahead as in chess would be impossible because of the random play of cards, which would limit the depth of the search of options. I’m tempted to try to write a version of the game as practice in coding, so I’ve just dug out from a box my old book Computer Gamesmanship by David Levy, with its useful suggestions about evaluating decision trees. I’m still working on the genetic algorithm sketch in Processing, but this might be my next project.
arduino designer required for LED perfomance costume
That’s the first time I’ve seen a request for an arduino designer. It’s just a shame that it’s unpaid and in London. Still, it might be the start of a trend.
gray matter
Last night’s session with Ollie Glass in developing a genetic algorithm for spiders’ webs led to discussion of Gray code in place of binary numbers to represent characteristics of the webs. I’d never come across the concept before, but I can see the benefits for genetic algorithms. Two successive numbers only ever differ by one bit, so an arbitrary mutation of one bit won’t lead to a massive change in value. (The rest of the discussion on Wikipedia left me cold though.)
There won’t be a session next Monday, but I’ve got a lot of work to do to follow up the material we covered last night. This is where the algorithm starts…
and then there was one…
I’ve completed the next step in my genetic algorithm project: collision detection between flies and webs, based on the colour of the pixels.
It’s slowed the code right down, so as a first step in improving its efficiency, I changed it so that it only checks flies that haven’t already been trapped. Without any other improvements, it means that the remaining flies appear to move faster and faster, as though they’re trying to escape, until the last fly, alone in a dangerous world and surrounded by the corpses of its fellow creatures, desperately searches for salvation until it too is inevitably trapped and killed.
Empathy for a few pixels? What a ridiculous idea!
genetic algorithms for webs
I had the first Skype session with Ollie Glass last night, where we discussed the first stages of exploring the use of genetic algorithms to evolve spiders’ webs. It was very useful, and I learned a lot.
The first reveleation was a different technique for checking to see whether a web had trapped a spider. I’d assumed that we would have to check each strand of each web for every fly, and suggested that we ran a first-pass check to see whether a fly was within the outer edges of a web, and only if it was would we then run a more detailed check against each strand.
Ollie, however, suggested a cunning alternative: check the colour of the pixel that a fly was on, and if it was web-coloured then it would be trapped. The downside is that this technique wouldn’t identify which web had trapped the fly, which would be important if we were going to rank webs according to how many flies they succeeded in catching. Or would it? Each web could be a very slightly different colour, so the colour of the pixel the fly was on would, in fact, identify the successful web!
We then had a fascinating discussion on whether the detection routine should be a method for the ‘fly’ class or the ‘spider’ class. In the end, we agreed that although it might be more realistic for the web to detect the presence of a fly, it was a neater programming solution for the fly to check, since we would only have to check one pixel per fly, rather than every pixel of ever web. The fly would then send a signal to the environment (in the shape of the overall programme), which would in turn signal other parts of the environment.
Discussion turned to how we might develop the webs. Ollie was keen to advance in small increments, though keeping a note of ideas for fture stages, which makes sense, and is well suited to the approach of object oriented programming.
Immediately after the session I tried to write the code for checking the colour of pixels. We’d run a small sketch during the session to test it, and the principle worked fine, but my first attempt for the web simulation slowed the code to a crawl. I’ll try again, reducing the number of flies, and see if I can code it more efficiently.
Sorry, no Tweets were found.