The years I’ve spent obsessing over the Zodiac ciphers have recently culminated in a new site, ZodiacKillerCiphers.com
Over forty years of analysis have yielded no viable solutions to three of the four cryptograms the Zodiac killer created to taunt the public. Do real solutions exist, or was the public hoodwinked by a master troll? Perhaps we’ll never know. Or perhaps someone will get lucky and figure out the “trick” that will unlock the mystery.
The Atlanta trip was a lot of fun. We stayed in a really nice rental house not far from Turner Field. The McCubbins managed to put up with me for a week and even went so far as to make dinner for me on several occasions. You haven’t had a good meal until you’ve tried their cooking. Mmm, tuna bites, fruit and goat cheese salad, steak, and black bottomed cupcakes. Our friends Jon and Kate are also accomplished cooks – we should host a cookoff between both couples so we can reap the delicious benefits.
Our rental house
Between home-cooked meals we sampled a variety of Atlanta dining options. Chris and I ate at Gladys and Rons Chicken and Waffles, a restaurant chain started by Gladys Knight that serves the most delicious fried chicken and waffles I’ve ever had. The waffles are warm and soft on the inside and nice and crispy on the outside. Perfect. And eating there has only amplified my weakness for fried chicken. I also managed to meet up with the Atlanta-based contingent of my LegalEdge coworkers at the Vortex Bar and Grill. While I did not sample the infamous bypass burgers, I did partake of the big-ass mushroom swiss burger, and my brain’s burger receptors were alight with glee. This celebration of manliness was a mere coverup for the earlier, emasculating experience of eating at the American Girl Boutique and Bistro to celebrate Eris’ fifth birthday. Despite the pink/pastel surroundings, bad service, and proliferation of little girls tending to their creepy shark-eyed dolls, we had a great time and the food was really good.
We checked out the Georgia Aquarium and World of Coca Cola during our stay. The aquarium is fantastic; definitely a must-see. The whale shark tank there is a massive, imposing, wondrous display. The Coca Cola museum is fun but they really hammer you with Coca Cola propaganda while you are there. YOU MUST DRINK IT. The tasting room is awesome, though. In it you can try unlimited samples of around 70 different Coca-Cola products sold around the world. We shuffled among dispensers over the sticky floors and tasted all sorts of delicious sugary carbonated water, and occasionally experienced horrid drinks such as Beverly. The tasting room gets you nice and high on sugar and caffeine before you go to the gift shop, which is the only way to exit the museum. A brilliant scheme to coax dollars from your wallet.
According to Nic McPhee’stwitters, GECCO 2008 had 471 attendees from 46 countries. This universal appeal of scientific research is one of things I liked about last year’s GECCO conference, too. This year’s conference, though, was almost as bad as last year’s when it came to feeding the attendees. Food was given out during the two hour poster session where I was presenting my poster, but all the food was gone in less than 20 minutes, and it was not replenished. Boo!
Keynotes
Nevertheless, there were plenty of fascinating presentations and workshops. The keynotes were again from experts in the field of biology, source of many of the great ideas in evolutionary computing. Dr. Martin I. Meltzer, senior health economist at the Centers for Disease Control, gave an interesting keynote talk about developing scientific models to study public health policy and how well we’d react to sudden outbreaks of disease. In particular, he used the example of pandemic influenza. Overall it was a fascinating but extremely depressing talk, since much of it dwelled on how unprepared we are for situations such as the 1918 flu pandemic. Well-known biology professor, popular science blogger, fierce skeptic, and “expelled from Expelled” victim PZ Meyers gave the second keynote talk. He spoke about the importance of development during evolutionary processes (aka “evo-devo”). For example, many animals share the same exact genes but the organisms themselves have vast differences. The differences are due to other important developmental processes outside of the animals’ genes. He talked about some interesting specific examples, such as development of bats and mice. Cretekos et al (2008) recently chopped out a regulatory sequence from bats and stuck them into mice. The mice then developed longer forelimbs, corresponding to the lengthened forelimbs of bats needed for flight. PZ’s blog post explains this in more detail (and with cool pictures!) This example showed that there are many elements at play that create variety in organisms, and many of these elements are strongly influenced by their environment. We are only barely beginning to understand how these things all work together to form life.
PZ’s other interesting example of environmental factors in evolutionary development was Suzuki and Nijhout’s 2006 paper “Evolution of a Polyphenism by Genetic Accommodation”. The researchers were able to evolve environmentally-driven traits in a type of caterpillar. In cooler temperatures, the evolved caterpillars remain black in color. But some of the ones exposed to hotter temperatures turn green in color; all the rest remain black. So the experimenters selected the greenest caterpillars and let them breed with each other. They also selected the black, unchanging caterpillars and bred them with each other. Over a small number of generations, descendants of the green-changing caterpillars more reliably changed colors, while the unchanging caterpillars reliably resisted changing colors in hotter temperatures. Read PZ’s post for more interesting info on how this all works. It reminds me of Ryan Somma’s post about Daisyworld, a thought experiment world in which black and white daisies affect the temperature of their planet as well as their own survival.
Chris and I entered the 2D packing problem contest, where you have to evolve a grid of numbers that yield the highest scores for adjacent pairs of numbers. We didn’t win but we did well enough to give a presentation about our approach. We developed an “embryonic” growth technique to evolve the 2D grid, using block-based growth, and something that ended up looking like mold.
Animation of the “mold” evolution technique. Brighter red spots indicate formation of high-scoring areas of the grid. Click to see the supersized version.
Other contests included evolving Rubik’s cube solvers on a massively parallel grid computing platform (the winner gets $1000), evolving L-systems to match pre-existing images, and evolving intelligent agents to search a virtual landscape for food as efficiently as possible. Nobody qualified for the Rubik’s cube contest, and nobody entered the L-system contest. Which is too bad, since they are very interesting problems. And the $1000 bounty for the Rubik’s cube problem remains unclaimed; Parabon is keeping the competition open and is upping the ante to $2000 for GECCO 2009.
There was also the so-called “HUMIES” awards, which is a competition to showcase evolutionary methods that match or outperform human efforts to solve problems. The winning paper used genetic programming to evolve ways to find special algebraic terms that no human has been able to accomplish.
Interesting research
Below is a list of some of the other presentations and papers that interested me:
Games: Moshe Sipper spoke about evolving artificial players for Robocode, backgammon, and chess. The evolved Robocode player was able to beat all of its competitors, which were all written by humans. The evolved backgammon player beat “pubeval”, a strong hand-written backgammon algorithm, 62% of the time. Sipper claims the evolved player will beat human players “most of the time”. The evolved chess-playing AI was able to win or draw against Crafty, a hand-written chess-playing program that is a top competitor at the World Computer Chess Championships.
Kenneth Stanley discussed “generative and developmental systems”. He explored the question, “how is it possible that 100 trillion connections in the human brain can arise from a mere 30,000 genes in the human genome?” The belief is that biological processes such as embryonic development cause complex things to emerge. If we stole some of these ideas from nature and used them in evolutionary computing, maybe we could solve some really interesting and difficult problems. Dr. Stanley cited the work of Gregory Hornby, who evolved robots and other objects using an L-system grammar. The advantage of using an L-system is you can get complex behaviors out of very compact, simplistic rules instead of describing or defining each part individually.
Dr. Stanley went on to describe a technique to evolve abstract representations for development, based on how evolutionary artwork is made. This was a big surprise to me; I’ve done a little bit of evolutionary art research, so I was happy to discover that there are real uses for the techniques other than just making pretty pictures. Along the way, the technique Dr. Stanley described turned into a side project called Picbreeder where computer-generated art is evolved via an online community. I’ve been wanting to see something like this!
In the defense applications track, we saw a talk about evolving swarm behaviors for unmanned aerial vehicles (UAVs). Some of the swarming, self-organizing, and attacking behaviors are inspired by behaviors of insects such as bees and wasps. Several interesting micro-UAV technologies were mentioned, such as the Black Widow, UAVs with flapping wings (including bat wings), and parasitic (!!!) UAVs such as SilentEyes (it is launched from larger UAVs). Don’t do anything suspicious, or a swarm of these damned things will form a stinging cloud around you.
Black Widow micro-UAV. Watch out for its poisonous bite.
In another talk, an Australian researcher described their technique of evolving collective intelligence for UAVs to detect and report bush fires (that’s Australian for “wildfires”). Their challenge was to evolve swarm behaviors so the UAVs have the best possible coverage of the surveyed area, and also so the UAVs can adapt if there are malfunctions in members of the swarm.
There were many more interesting papers, too numerous to describe, showcasing the widespread and diverse applications of evolutionary computing. Some examples include evolving circuits with high testability, automatic defect classification in electronic wafer manufacturing, quantifying quality degradation on voice-over-IP networks, detection of malware (including zero-day virus attacks) using techniques inspired by biological immune systems, evolving color schemes for people with color blindness, investment portfolio optimization, modeling the Milky Way galaxy using BOINC volunteer computing, developing no-loss strategies for tic-tac-toe, finding deadlocks in large concurrent java programs, radar jamming, evolving functions that can detect computer program code plagiarism by students (beware, cheaters!), automatic route planning that takes traffic into consideration, automatic composition of rock music using genetic algorithms (seriously?), interactive evolution of facial composites of suspects in criminal investigations, detection of moving objects in videos, using a bacterial foraging algorithm to detect circles on images (wait, what?), evolving a World Computer Chess Champion-beating chess program by mimicking the behavior of a mentor, and prediction of whether a company will have financial losses.
The list goes on. But I’ve punished you long enough with this mercilessly long post. Long story short: Trip good. Science good. Computers fun.
Last year, I used PowerPoint (gasp) to create the poster. What a huge pain that was. This year, I used OmniGraffle, by far the best damned diagramming software I have ever used.
It should be a fun conference; I’m excited to hear about the results of all the competitions. Chris and I entered the “2D Packing Problem” contest; alas, our entry did not win. Still, we had a lot of fun trying out different ideas – it was a very fun problem to work on. The other contests should be fun to hear about, especially the Rubik’s Cube Solver contest. Entrants in this contest get to use a commercial grid computing platform to breed Rubik’s Cube solving algorithms.
Last week was a good week for my strange little diversions with genetic algorithms. Two things happened that helped to validate the legitimacy (in my mind) of using genetic algorithms to solve certain problems. The first was receiving a copy of the March issue of Muse Magazine, a children’s magazine about science, art, and history. A little blurb about my evolutionary art project for last year’s GECCO conference appeared in the magazine.
Shiny!
I wish I had the time to continue to improve the art generated by that technique. It was a lot of fun to play with. There are many other ideas I want to try, such as adding new measurements to compare things like texture and composition, but, alas, not enough time to explore them. One day I hope to return to this.
Meanwhile, I’ve been wasting way too much free time trying to develop a genetic algorithm to attack the unsolved Zodiac killer cipher. The results have been somewhat minimal so far, but it’s a start. I’ve been playing with this stuff since March of last year, so I figured I should have something to show for all the time I’ve put into this research. I decided to write and submit a research paper to this year’s GECCO conference on evolutionary computing, and my paper was accepted as a poster presentation. W00t! I had a lot of fun at last year’s GECCO conference; I look forward to absorbing all the fascinating cutting-edge presentations this year. Here is the title and abstract from my paper:
Evolutionary Algorithm for Decryption of Monoalphabetic Homophonic Substitution Ciphers Encoded as Constraint Satisfaction Problems
ABSTRACT
A homophonic substitution cipher is a substitution cipher in which each plaintext letter maps to a set of one or more ciphertext symbols. Monoalphabetic homophonic ciphers do not allow ciphertext symbols to map to more than one plaintext letter. The selection of ciphertext symbol mappings is intended to conceal language statistics in the enciphered messages. Statistical-based attacks that are known to be quite effective on simple substitution ciphers are very difficult to apply to homophonic substitution ciphers that employ good selections of ciphertext symbol mappings. Word boundaries are often not known, increasing the difficulty of decryption. We present a dictionary-based attack using a genetic algorithm that encodes solutions as plaintext word placements subjected to constraints imposed by the cipher symbols. For a test case to develop the technique, we use a famous cipher (with a known solution) created by the Zodiac serial killer. We present several successful decryption attempts using moderate dictionary sizes of up to five hundred words. Attempts are ongoing to increase the robustness of this technique by making it work with larger dictionaries and a variety of test ciphers.
Since then, I’ve gotten the technique to work against the test cipher with dictionary sizes of 1200 words, but the algorithm is very sensitive to various parameters when it is running, so it’s not very robust yet. There is still a lot of work to do.
A new version of zkdecrypto is available for all you cipher enthusiasts. The zkdecrypto team has been very busy adding new features and fixing bugs.
* Program is now both smaller and MUCH faster
* Ability to now open both ASCII and numeric ciphers
* Ability to now save the loaded cipher
* Exclusions and locked letters are now saved in the “key” file
* New Redo function in addition to Undo
* New pattern analysis and sequential analysis reports
* 1-click ability to add full alphabet to “Additional Key Letters”
* New “Word List” feature that lists words found in the plaintext
…and more.
Click here for more information and download links.
A student at Rutherford High School was arrested Wednesday on a felony charge of making death threats against teachers and other students.
Freshman Dakota Gates, 14, is alleged to have written a coded note with detailed plans for an attack on the school. However, investigators have not yet turned up any weapons or other evidence the teen actually intended to carry out the threats, according to Bay County Sheriff Frank McKeithen.
The cryptogram was solved by authorities, but I could not find any mention of the solution in news sources. But Fark, ever the defender of justice and freedom for all, has become a source for the cryptogram’s solution. Look for postings by user “Mayhem of the Black Underclass” in this comment thread on the story. The interesting thing is that the news article claims that in the decoded crytogram, there are “detailed plans of an attack” on the school. But Mayhem’s solution reveals no such plans.
Brax Cisco, Wesley Hopper, and Michael Eaton have just beta-released their wonderful “Zodiac Decrypto” program, a fun piece of software designed to attack the Zodiac ciphers as well as other substitution ciphers. It uses letter-level n-gram frequency analysis (no, not Engram analysis!) to estimate the validity of solutions generated by the software’s hillclimbing process. The software runs in Windows.
The UK Daily Star confirms that I am not wasting my time with my fruitless pursuits of the Zodiac killer’s unsolved mysteries:
But that’s if [Britney Spears] can tear herself away from the internet where she has been indulging her latest obsession – trying to solve crime.
The star has become fascinated by the unsolved Zodiac killings that took place in California in the late 1960s.
They are the US equivalent of our Jack The Ripper murders. The recent film Zodiac about the case starring Jake Gyllenhaal, 26, captured Britney’s imagination.
She has been spending hours on a website called zodiackiller.com and is convinced she can crack the case as many people believe the culprit is still alive.
Gimme my Cheetos, y’all; We’re gonna crack this thing!!
Another quick update to the Zodiac webtoy: now there are links to flip and rotate the ciphertext. This was a popular feature request that I finally got around to implementing. Enjoy!
I’ve finally made some more updates to the Zodiac webtoy! The biggest change is the addition of simple letter-frequency statistics.
Remember when Ralphie cracked the “secret code” in A Christmas Story? Ralphie: [Reading his decoding]: “Be… sure… to… drink… your… Ovaltine. Ovaltine? A crummy commercial?!? Son of a bitch!!”
Here is the list of noteworthy changes:
Added frequency tabulations for symbols, decoded plaintext letters, and expected letter frequencies (as specified here). Frequency analysis of this sort might be useful to cracking the cipher. Eventually, I would like to include more n-gram statistics (occurrences of letter combinations of length n) to make this more useful.
Added the 408 cipher, which has a known (and creepy) solution. Click on the “Switch to 408 cipher” link to see it. The known solution link is below the 408 cipher (it is labeled “The correct one” next to “Interesting decoders”).
Fixed some formatting bugs that were causing the columns of the cipher grid to get squashed.
The webtoy seems to be getting much slower in Internet Explorer 6. I’ve not tested it in Internet Explorer 7. But it works pretty well in Firefox and Safari. I am afraid of all the horrible, horrible JavaScript code that I wrote – Please let me know of any problems you find! If you find the new version to be too crappy, you can still use the old version by clicking here.