Two Programs Enter, One Program Leaves | Hacker News Reader

Two Programs Enter, One Program Leaves

codinghorror.com

132 pointsgnosis37 comments

I would like to share with you a funny story about Corewar:

5 or 6 years ago, a group of students at the local university organized a Corewar contest. The group of organizers were, how to say it, "theorethical nerds", some of them in their way to be professors (two of them are in fact professors today). Big egos too.

I was no more a student at the time so I didn't join the contest, but I commented about it to my girlfriend because I had read about Corewar before and found it interesting. My girl was a student and she liked so much what I told her, that she decided to compete herself.

I can say that when she is obsessed with something, as she got with the contest, she doesn´t stops at anything. So in less than a couple of weeks she had serveral 'strains' of working bots each with different behaviours and abilities. Until the last minute she was testing which were her bests programs to compete.

So, the day arrived, and the more or less 10 MALE ppl at the competition saw my girl, coming with no one but 3 (or 4) programs. I wish I could have been at the event because my girl beat them all and with all of her bots. They even disqualified one of her bots because it almost always tied (was a replicator)

I don't think they learned not to underestimate a confident blonde girl, but the contest was conveniently forgotten and Corewar was never mentioned again at the place :D.

Microsoft did something similar to promote the .NET framework in it's early days. They launched the Terrarium competition http://terrarium2.codeplex.com/ where you would code your creature's AI in C# or Managed C++ and ship it as a DLL that would compete against other peoples creatures.

Woah. Blast from the past. I remember that from the .NET launch. I still think it's a really awesome initiative, and this sort of thing would be great for getting high school kids interested in programming.

They've got one for Azure now, I haven't checked it out though:

http://www.rockpaperazure.com/

Back in the day I tried applying genetic algorithms to corewars as a high school science fair project.

I lost. They had no idea what was talking about. Early lesson in the importants of communicating technical ideas.

Three weeks ago, I was at a science fair demonstrating a genetic algorithm that would create AIs for two-player boardgames, and included a test case with tic-tac-toe.

Guys from the IEEE talked to me at length, loved it, and gave me their grand prize. Two judges (both Lisp hackers (and both thrilled to see an 18-year old doing AI with CL)) also loved it...but the other judges did not understand it at all, so I didn't even place at the actual fair. Sigh.

Oh, you lost the science fair. How did your code perform in battle?

The evolved warriors weren't all that impressive either.

Really required a large number of generations, which my poor turbo pascal skills or lack of hardware didn't really provide. I wonder if I can find that code on a floppy somewhere...

In recent years some evolved warriors were able to compete with human crafted warriors. Optimizing just parts of a warrior with GAs is also a popular method.

I'm reminded of a story I read a while back (around 20 years ago) about engineers pointing out a security flaw in a vendor's Unix system, which the vendor did not take seriously. So they wrote a pair of programs: Falstaff and Othello, if I remember correctly... where if you killed one, the other would output to the console something to the effect of "I'll save you!" and would resurrect the other program, making it extremely difficult to eradicate from the system.

I've been trying to find this... anyone have a reference to the original?

That sounds like a story that is recounted in the Jargon File (http://www.catb.org/jargon/html/meaning-of-hack.html).

I wonder if it's a bit apocryphal. I feel sure I've also read a version where the two processes were called “sheriff” and “deputy”, and you suggested yet a third naming scheme.

“Back in the mid-1970s, several of the system support staff at Motorola discovered a relatively simple way to crack system security on the Xerox CP-V timesharing system. Through a simple programming strategy, it was possible for a user program to trick the system into running a portion of the program in ‘master mode’ (supervisor state), in which memory protection does not apply.

[…]

Months passed. The Motorola guys pestered their Xerox field-support rep, to no avail. Finally they decided to take direct action, to demonstrate to Xerox management just how easily the system could be cracked and just how thoroughly the security safeguards could be subverted.

They dug around in the operating-system listings and devised a thoroughly devilish set of patches. These patches were then incorporated into a pair of programs called ‘Robin Hood’ and ‘Friar Tuck’. Robin Hood and Friar Tuck were designed to run as ‘ghost jobs’ (daemons, in Unix terminology); they would use the existing loophole to subvert system security, install the necessary patches, and then keep an eye on one another's statuses in order to keep the system operator (in effect, the superuser) from aborting them.

One fine day, the system operator on the main CP-V software development system in El Segundo was surprised by a number of unusual phenomena. […] Naturally, the operator called in the operating-system developers. They found the bandit ghost jobs running, and killed them... and were once again surprised. When Robin Hood was gunned, the following sequence of events took place:

!X id1 id1: Friar Tuck... I am under attack! Pray save me! id1: Off (aborted) id2: Fear not, friend Robin! I shall rout the Sheriff of Nottingham's men!

id1: Thank you, my good fellow!

Each ghost-job would detect the fact that the other had been killed, and would start a new copy of the recently slain program within a few milliseconds. The only way to kill both ghosts was to kill them simultaneously (very difficult) or to deliberately crash the system.”

Thank you... that is the one. I may have misremembered the characters involved or perhaps read it from a different source.

After watching that animation for a bit I can't help contemplating some combination of Core War and Minecraft.... :-)

Somebody make such a game and I will buy it. I will pre-buy it.

Bomb SSSS #0

You are going to have to explain that one...

He's referring to the sound a creeper (Minecraft enemy) makes right before it blows up.

I couldn't find a Javascript environment for running this. Anybody knows if it exists?

If not, who's up for a github night ? ;-)

I've been thinking about creating one, having been an active Corewars player back in the day.

A problem could be compatibility with the pmars parser, which has been the standard for a long time. I tried writing a parser for corewars years ago and run into trouble emulating some aspects of the pmars parser.

yep I'm currently wrestling with it. I've a prototype that precompiles EQU and FOR/ROF and I'll try uploading it to github when it's a bit more tested.

Even a JS Corewars interpreter that can only compile "assembly" would be nice to have. Then people could compile their warriors with pmars and put fancy simulations on their web sites. Not saying that it is impossible to clone the pmars compiler, but it is a mess :-)

I've got the precompiler working quite well. Interestingly, it translates the redcode/pMARS code line-to-line to Javascript which is then executed to produce the assembly.

redcode is indeed a mess, clearly the result of an evolving and blurry standard :)

anyway, I'm spitting out assembly for 90% of the bots I've tried and have the Imp running. From now on it will indeed be a job of implementing each instructions and addressing modes. I'm definitely uploading this on github in a few hours and will be very happy to have some help ! :)

There you go !

https://github.com/joshfire/corewarjs

I've got imps and a few other running :)

Not exactly CoreWars in JS, but PDP11 in JS, with real Unix V6. Enjoy :)

http://aiju.de/code/pdp11/

In university, we did something vaguely similar for class projects using Robocode: http://robocode.sourceforge.net/

Which was inspired by Robot Battle on Windows, which was inspired by Robot Wars on the Apple ][.

I played Robot Wars on the Apple ][. And Rocky's Boots and A Robot Odyssey. Awesome games for hacker/maker personalities. And yes, I'll be on my rocker.

What happens if the instruction pointer for, say, process A, steps into the code space for another process, B? Does the simulator treat it as an illegal instruction causing A to lose? Or does process A continue, but executing B's code?

The processes are all in the same code space; there's nothing distinguishing process A's instructions and process B's instructions, so process A would continue executing code created by process B. Some Corewar programs ("vampires") use this to hijack their opponents.

I think it treats it as a legal instruction.

What I don't get is the replicator strategy. How does replicating yourself help not die? Even if you replicate yourself to all the memory except one address -- but that one address is where your IP is you're screwed. It seems like repairing yourself and attacking the opponent are the only feasible strategies -- at least if I understand correctly.

That is what the SPL instruction is for: the program copies its preferably short code to some random location and then splits its execution to continue with both. You are only dead once your last execution pointer hits an illegal instruction.

Replicators split into multiple processes, each with its own IP. A program isn't considered dead until all its processes are killed. If one of its processes stumbles across a bad address, the others aren't affected.

Ah OK, didn't read carefully enough. Thanks.

It does not treat it as an illegal instruction. It keeps running their code just fine. This is how Imps fight.

The most basic imp is defined as

   mov 0 1

It copies itself to one instruction ahead of itself. On the off chance it hits the opponents pointer, the opponent becomes an imp too and they both just circle around the core forever.

See elwin's comment below on vampires (for now, hopefully above soon).

Ah, good old Core Wars!

It is perhaps interesting to know that the next installment of the Google AI Challenge (http://ai-contest.com) is a couple of weeks away and it allows a wide range of programming languages.

The nice thing about them is that they are very short and so you can try a lot of different strategies, but there were also long scripts like Mule DNA. I think this is a great way to teach kids the basics of addressing and low level programming. I remember writing these bots for a friends computer science class, good times.

This looks like a fun alternative to the typical weekend hackathon. I'll give it a whirl.

Reply on news.ycombinator.com