Sunday, December 28, 2008

RedArena - Core War and Warrior Evolution

There was something interesting going on before I was born, and it was called Core War. If you prefer the short overview, it's something of a programmer's game. Warriors written (or not written, but we'll get to that...) by people battle for space in a Core by utilizing Redcode. (A sort of assembly language.)


When I first found out about this, about a week ago, my first thought was "Where has this been all my life?" Maybe I've just been living under a rock, but it's never too late to start now. Yes, you heard me right. This game is still going strong, even after almost 25 years!


So what have I accomplished so far? Not very much. I've attempted to hand-code some warriors, but none have yet to be successful. Will that stop me from trying again? Of course not. I'll just change tactics. It wasn't long after I began looking around for information about Core War and Redcode, and chatting with some very nice competitors on IRC (#corewars on irc.koth.org) that I discovered that people were actually utilizing their programming skills to evolve warriors, as opposed to hand-writing them.


I bet you can tell where I'm going with this. Naturally, since I'm not doing so well at hand-coding warriors, I think it's time I gave this whole evolution bit a try. Hopefully my higher level programming skills will really shine through. I've dubbed my entire evolution process RedArena (or "the process"), and to start off with, it will be mostly, if not entirely, in python. Right now, it's very abstract, and I haven't coded a single line, and won't until I get the design down as I want it. To start off with, I have some core ideas about the process, which will be guidelines throughout, and they are (but not limited to):

  1. Never throw good data away.
  2. Give second chances.
  3. Analyze the data, and use the analysis.
  4. Start from scratch. Measure against the Elite.


Never throw good data away.

Because the evolution process is dependant on generational building for progress, I think it would be great to never throw any warriors away. Sure, they can lose, burn, and die, but they won't be forgotten, because they're all part of the process of "life."


There are other benefits to this, like being able to rewind through the process, in case we want to start off from somewhere besides the bare ground on a future run, or for logging, statistical, or bragging purposes.


However, there may be some downsides to this. One is that it adds complexity to the process. The second downside that I can envision is that, depending on what way we store this data, there may be issues with the speed of access (or lack thereof) bogging down the process.


Give second chances.

A warrior is not doing well. In fact, it's at the bottom of it's generation. What's a warrior to do? Usually they would probably just be discarded as useless, but what if just one little change was enough to make it into a Tron? (Much to my MCP's chagrin...) In order to try to catch these very rare happenstances, I will give these poor contenders a second chance. It will take the form of a forced mutation, and only ever a forced mutation. (Bad code cannot be rewarded with reproduction.) The degree of this mutation is, as of yet, undecided; The mutation will have to be more dramatic than a normal one, though, as to give the bad code a solid second chance at being good.


Should the rare program actually turn out well, then all the better! However, I can see some issues with this. Firstly, I have little knowledge of how often this will actually work for the better, and there will be a steady drain on the speed of execution caused by having this extra logic and "another" warrior to process. We shall see, I suppose.


Analyze the data, and use the analysis.

Since we're going to have oodles and oodles of data, including the warriors, their scores, and other things, I'll be doing a large amount of analysis of this data, and depending on how things turn out, shake things up a bit, or leave it as is. In the beginning, this may be more of a manual process until I can get a feel for how things are affected by the changes, if any. An example of this kind of change would be toggling the chances for mutation, mating warriors randomly, generating new warriors based on statistics, (e.g. This strategy isn't used much, so let's increase it's chance to be a mutation, so the pool can work effectively with and/or against warriors who use it.) or other changes that I have yet to envision.


Some good things with this is that it will enable a deeper understanding of just what is going on with my precious babies, and furthermore, should make for more well-performing warriors, when done correctly.


Of course, this is not without it's drawbacks. As always, it adds complexity, and more processing to the requirement. Despite that, I feel that this is one of the most useful things that I could do within the process.


Start from scratch. Measure against the Elite.

This is something of a risky venture, I think, but I can't be sure until I see it in action. The idea is to start from completely random warriors, but benchmark against well established already-evolved or hand-written warriors that have done well on actual hills.


This is good, because it should ensure a good measuring of how well my precious babies will perform on the same actual hills. However, beginning from scratch may add a lot of time to the process, particularly in the beginning, where chances are my precious babies will be slaughtered in the benchmarks.


Community

One thing of note is that so far, I've noticed that there exists a core community centered around Core War, which is very active, though things seem to have died down some in the past 24 years. Nevertheless, I've found a great deal of good code, good advice, and camaraderie from contenders John Metcalf, bvowk, and flyduck. (All from the #corewars IRC channel on irc.koth.org)


I probably would have lost interest in competing vicariously through my precious babies, hand-written or not, and quickly, if it weren't for these friendly folks.


I'm opening this up to all, for comments, ideas, debates... Whatever you feel I should know, comment here, and your voice will be heard!


-AndrewBC

5 comments:

  1. Interesting thoughts.

    I would have thought you need to give thousands of "chances" before you consider code "bad".

    ReplyDelete
  2. When it comes to the amount of chances a warrior gets, perhaps I could have used more numerically agnostic language. At the time of writing, I probably was thinking merely in terms of one chance, and then a second chance for "bad" performers.

    But with your prodding, I'd have to agree that I couldn't possibly know their worth with such little testing, which I somewhat allude to with the idea of giving second chances to begin with.

    I've still yet to actually put down effort in implementing these thoughts into a working system, as time has not permitted. When I do, I'll be trying "thousands" before I try "two." (If I try "two" at all.)

    Thanks for your input.

    ReplyDelete
  3. I'm just about makeing my bachelor thesis about envolving CoreWars wariors using genetic algorithms. I found your article very usefull and i'd like to ask you if you made any prograss and achived any results since it was written.

    best regards
    Martin Triska

    ReplyDelete
  4. Hi kofola,

    Pretty cool that you're doing a thesis over this kind of thing. Unfortunately, I've made little progress beyond this initial post, due to it being a low priority hobby project.

    However, there are plenty of people who have made much more progress than I in #corewars on irc.koth.org. I wish you the best of luck!

    ReplyDelete
  5. I was just now searching for about this when I discovered your post. I’m just stopping by to say that I really enjoyed reading this post, it’s very well written. Are you planning to write more on this? It seems like there is more depth here for more posts.

    http://www.sms4pc.com/

    ReplyDelete