From news@stormking.com Thu May 12 01:29:42 1994 Received: by stormking.com with UUCP id AA54155 (5.65c/IDA-1.4.4 for cbx.rec.games.corewar); Fri, 13 May 1994 06:35:21 -0400 Path: valhalla.stormking.com!speedway.net!news.world.net!news.sprintlink.net!hookup!paladin.american.edu!darwin.sura.net!news.Vanderbilt.Edu!stst From: stst@vuse.vanderbilt.edu (Stefan Strack) Subject: Re: Genetic algorithms for corewars Message-Id: <1994May12.012942.22862@news.vanderbilt.edu> Sender: news@news.vanderbilt.edu Nntp-Posting-Host: vvcs.vuse.vanderbilt.edu Organization: Vanderbilt University School of Engineering, Nashville, TN, USA References: <2qruqc$7e5@cwis.isu.edu> Date: Thu, 12 May 1994 01:29:42 GMT Lines: 207 Apparently-To: cbx.rec.games.corewar@stormking.com In article <2qruqc$7e5@cwis.isu.edu> fullanto@cwis.isu.edu (Antonette Nixon) writes: > A little while ago, I recall hearing about somebody that was evolving >corewars warriors with genetic algorithms. [..] Karl Lewin (lewin@alife.santafe.edu) has developed a GA based warrior evolution system based on John Perry's paper (soda.berkeley.edu: /pub/corewar/documents/evolving.warriors). He's been meaning to post the following to this newsgroup, but apparently wasn't successful. Here goes: -------BEGIN OF INCLUDED TEXT-------------------------- I have had a couple of requests for more information on what, for lack of a better name I am calling EC94 Evolver. It is a set of programs I have developed to try and evolve successful corewar warriors. Here is a little background. Some time ago a paper (2 actually) by John Perry appeared on the corewar archive titled _Core_Wars_Genetics:_The_Evolution_of_Predation. After reading it I started to wonder what it would take to do something similar. I made a brief attempt but then other things came up so I shelved the idea for awhile. A few months after that I became interested in Genetic Algorithms/Genetic Programming and remembered the evolving warriors stuff and decided to try again. I based most of what I did on the Perry paper because that seemed as good as any place to start. This was about two months ago. I decided to use the proposed '94 standard in my system, I think that this was a good choice because it seems less restrictive about which addressing methods can be used with which instructions. The system was developed using VX-REXX on a 486 under OS/2. The system basically works like this: 0 Randomly generate the base generation 1 Rank the warriors based on their scores against some test programs 2 Apply a selection technique to chose parents 3 Use a genetic algorithm/operators on the parents to produce new programs 4 go back to step 1 To date I have made several runs with the system and while no "super-warriors" have evolved there have been some interesting results. None of the warriors evolved so far have been able to make it onto the the hill (pizza '94) but some have had limited success against certain warriors currently on the hill, unfortunately the ones that do well against several warriors get clobbered unmercifully against about 10 or 12 others so they end up scoring around 90 - 95. The following are the best results I have gotten so far they are for a warriors named G050W071 & G054W073 (50th generation, warrior 71 & 54th generation, warrior 71) These were from a few days ago: Opponent G054W073 G050W071 ======================================================== vs Torch 43/36/21* 69/19/12* vs Der Zweite Blitzkrieg - 94 04/71/25 04/66/30 vs Iron Gate 1.5 41/56/03* 50/50/00* vs Request v2.0 04/46/50 00/13/87 vs Blue Funk 00/30/70 00/21/79 vs Cannonade 08/84/08 22/58/20 vs Dragon Spear 49/51/00* 24/65/01 vs NC 94 05/52/43 05/38/57 vs Lucky 3 00/99/01 00/75/25 vs Twimpede+/Small-X 00/60/40 00/33/67 vs Christopher 34/28/38* 17/39/44 vs SJ-4 80/20/00* 76/24/00* vs Rave 4.1 08/88/04 19/81/00 vs ^C 00/95/05 01/73/26 vs Splash 07/90/03 11/57/32 vs Imperfection v3.4 03/36/61 00/12/88 vs Yop La Boum v2.1 06/87/07 06/71/23 vs Clown 69/31/00* 75/25/00* vs Jazz 01/34/65 00/29/71 vs self 00/00/100 00/00/100 81.09 94.57 The source for G050W071 is below. If anyone wants to analyze it and post a summary please do, I have never been very good at writing warriors myself so I have'nt really tried. Some general observations about evolved warriors: They like to use DJN and SPL (attack/stay alive?) If the run has evolved down the SPL line then they don't seem to be able to beat themselves which losses points on hill (I think) The choice of which warriors to use as opponents during fitness testing is important. If anyone has been saving the '94 regular hill warriors that have been posted I would very much appreciate it if you could mail them to me this could possibly provide for some interesting experiments. I hope that I have not rambled on to much. If anyone has any questions or would like more details let me know and I will post some more info. I apologize if this post has been confusing and choppy but I am in kind of a hurry today. Karl ;redcode-94 ;name G050W071 ;author RC94 Evolver ;Parents: G049W013 G049W062 org 2 JMN.AB >2383,$4229 DJN.F #0619,<0008 DJN.F #0684,<0002 DJN.X #0315,$0186 MOV.I >2123,@3078 ADD.F <1774,<0003 DJN.F #0558,<0024 MOV.I #2108,@1159 SPL.A #3608,@1547 MUL.I $0291,$1295 SPL.AB #8362,@2071 SPL.AB >2078,@1219 SPL.AB #2842,#2051 DAT.I #0043,<1039 SPL.AB #6172,@1089 MOV.F @0049,$4738 MUL.F $0581,<1035 SLT.F #0044,<0010 ADD.BA >3114,<2158 DJN.F #0687,<0000 SPL.AB #3624,@1035 CMP.AB #3892,#0519 JMN.F #0644,<2090 MOV.AB #2330,@3127 MOV.A @0303,<3151 MOD.F @3911,<3456 SPL.AB #2334,@1155 MUL.AB <4111,<0293 DJN.A #6162,>0517 JMP.A <0047,<0008 DAT.B @5134,#4167 ADD.BA @4157,$6400 DJN.AB $1410,$0551 ADD.F #1258,<0535 ADD.X >0153,@1344 DJN.AB $0154,<0018 JMZ.BA <8756,#1063 SLT.F <7107,<0522 JMZ.BA >2531,<0011 DJN.F #6089,<0520 ADD.F #0687,<2048 DAT.B @5134,#4211 DIV.X $2097,<2144 ADD.F #4650,<4112 MOV.B @0049,@0002 DAT.I $4119,>0044 MOD.I #0258,@0058 JMZ.F #0039,<0291 JMZ.F <0051,@0065 JMN.I <2178,<1189 MUL.F >4111,<0293 JMZ.AB #0523,$4121 ADD.I @6240,#0044 DJN.A @2057,<0610 CMP.A @8216,#0018 SLT.I @2586,@0060 DJN.BA <5447,>0006 JMP.A @0034,<4780 JMZ.F $0310,>1051 SPL.B #2078,@1223 ADD.F >0014,<4360 DJN.A #0060,<0159 DJN.F #1583,$0019 DAT.F @0126,<1085 MUL.B @2119,@2114 DAT.I $8956,@0375 JMZ.F #8879,<0170 MUL.A <0339,$0041 DJN.F #1039,<2574 JMP.AB $4138,<4174 SLT.AB #3129,$0032 MUL.AB $2594,#4142 DAT.X $0038,<1292 MOV.I @1027,>0224 JMZ.I $0008,#0594 SLT.I @2586,@0056 DAT.X <0102,@0012 JMN.I <2178,<1189 JMZ.F <0386,#0522 SLT.F @0045,<0106 JMZ.F >0507,<1035 DJN.B $0029,@1059 MOV.I <4143,<0232 DAT.F @0041,<4110 JMZ.X $0024,>2198 DAT.F >2347,<0538 DAT.I $8750,$6191 DAT.F @0104,<1279 DIV.A #2071,@1037 ADD.I <4685,<0005 MOV.BA @8305,>5280 -------END OF INCLUDED TEXT----------------- If you analyze this warrior, you'll notice it spends its entire time executing the second instruction (DJN.F #683,<2), which is a bit disappointing. In fact, many of his creations seem to converge to this one-liner. We're currently working together to make the evolving warriors more competitive by applying better selection rules. One idea is to initially select for complexity, favoring offspring that executes larger loops (this can be automated via cdb macros). Another idea is to exclude DJN from the primordial instruction soup, but have it appear later by chance mutation. Stay tuned. -Stefan (stst@vuse.vanderbilt.edu)