Pete's Log: evolution
Entry #1233, (Coding, Hacking, & CS stuff)(posted when I was 23 years old.)
I'm playing God for fun and ... well, no profit yet. How, you ask?
I started playing with core wars again a few days ago. The premise of core wars is that you have a memory core (usually 8000 or so words in size) into which are loaded two or more programs written in redcode, a special assembly language. These programs then battle each other for control of the core. The programs are loaded at random locations, so they do not know where the enemy is. The way to win is to cause the other program to execute an illegal instruction. For more information, www.koth.org is a good place to start.
So I read that people were using genetic algorithms to evolve core war warriors. I thought that was a cool idea, and figured it was about time I learn genetic algorithms in more detail. So having only a basic concept of how genetic algorithms work, I decided it'd be most fun to write a preliminary version of my evolver without consulting any literature, just to see what happened.
A few hours of coding later, I've got something that sorta works. Happy me. My program starts out creating n random warriors, battles them against a variety of test warriors (some simple ones such as imp and imp-gate, as well as some more advanced warriors) and determines a score based on the number of wins, ties, and losses. The next generation then consists of the top 2/3rds of the previous generation (with mutations) as well as children generated by crossbreeding programs in the previous generation. To determine the score, losses are worth 0 points. Wins are worth 3 times as much as a tie. If a program wins all its battles, it scores 100. If it ties all its battles, it scores 33.
I've not run this for any huge numbers yet. In my biggest run so far I started out with 1000 randomly generated warriors. The lowest score among that population was a 0, the mean was a 2, and the max was a 77. After 25 generations the low was still a 0, the mean was a 73, and the max a 92. Detailed numbers at the end. It's fun to watch them evolve, though. I feel almost like I'm watching my kids grow up.
So now I want to actually go read some literature on genetic algorithms to get some ideas to improve my evolver. I figure I'll also look at some of the pages that deal with evolving core war programs in specific. I also want to run my evolver on some big data sets. I'm thinking about using MPI to feed the battles out to multiple nodes to speed things up. It's big fun. More later, maybe.
generation 0: min: 0, mean: 2, max: 77 generation 1: min: 0, mean: 4, max: 77 generation 2: min: 0, mean: 6, max: 84 generation 3: min: 0, mean: 10, max: 86 generation 4: min: 0, mean: 16, max: 88 generation 5: min: 0, mean: 23, max: 87 generation 6: min: 0, mean: 31, max: 88 generation 7: min: 0, mean: 34, max: 88 generation 8: min: 0, mean: 40, max: 89 generation 9: min: 0, mean: 48, max: 88 generation 10: min: 0, mean: 58, max: 89 generation 11: min: 0, mean: 68, max: 89 generation 12: min: 0, mean: 69, max: 89 generation 13: min: 0, mean: 70, max: 91 generation 14: min: 0, mean: 71, max: 90 generation 15: min: 0, mean: 72, max: 89 generation 16: min: 0, mean: 71, max: 90 generation 17: min: 0, mean: 71, max: 89 generation 18: min: 0, mean: 72, max: 91 generation 19: min: 0, mean: 73, max: 89 generation 20: min: 0, mean: 72, max: 91 generation 21: min: 0, mean: 73, max: 89 generation 22: min: 0, mean: 72, max: 90 generation 23: min: 0, mean: 73, max: 90 generation 24: min: 0, mean: 73, max: 92
I've had some runs where after a while the min became greater than 0, but this run was not one of them (I figure that with 1000 warriors, it'll probably take more than 25 generations to get rid of all the badness). Here's the winning program from that evolve session:
dat.i $ 3854 , $-1669
djn.x * 10 , * 2059
spl.ab $ 6 , { 8
dat.i $ 3675 , $ 2799
sub.x # 7 , $ 9
spl.a $ 43 , * 0
start djn.x # 18 , < 7
mov.ab > 1 , * 7
spl.x # 22 , $ 15
nop.x } 2065 , { 10
mov.x } 128 , $ 10
sne.ba } 7 , < 10
dat.i $ 3113 , $ 1319
dat.f $ 512 , $ 0
dat.f $ 0 , $ 0
dat.f $ 0 , $ 0
slt.b > 1 , > 2
mul.ab # 15 , > 2
Yes, redcode may possibly be the ugliest assembly language ever created ... it supports such things as pre-increment indirect addressing! And no, I have no idea how that winning warrior works.