Re: Genetic Tic-Tac-Toe Help (long)
- Posted by Roderick Jackson <rjackson at CSIWEB.COM> Mar 02, 1999
- 420 views
Well, since there's an interest, I'll post the code here. However, since = I again haven't completed the documentation, it'll just be the code and = an email description. Rob, I'll zip all of this into a file for = submission to the web site as soon as the docs are finished. But just to let everyone know, I think I actually have the problem = solved... apparently, I wasn't passing in a high enough value for the = mutation rate. I had thought I wouldn't need as large a number as I'm = using now. That, combined with about 10x more iterations improved the = results greatly. Anyhow... I call the library EU-Genes (pronounced either way you want ). It = generates specimens with 2D gene structures, based on the number of = states and the number of inputs you want. For example, if you want = specimens that respond values 1-4 at each pass (must be whole numbers, = starting at 1), and having 5 different states, you'd pass 5 as the = number of states and 4 as the number of inputs. The output of the = specimens will be within the input range, so if the output range is = larger, you'll want to increase the number of inputs, even if some won't = be used. You can also specify: - the maximum number of iterations you want the algorithm to run - the fitness goal (the fitness should be squeezed to a 0-100 range; = you can set a fitness of 50-100, or 0 if you don't want to stop at = 100... good for a game like tic-tac-toe where a pool of perfect = specimens have a score of 0 - the number of gene pools (and how often the top specimens from each = are copied and swapped across pools) - the pool size (how many specimens are left in each pool after the = lower-scoring ones are trimmed - how many specimens are copied and mutated per iteration - how many mutations take place per mutated specimen Here's a few things to note: - the routines aren't optimized yet. I'm working on it. - it's a bit slow; start with small pool sizes, one pool, and a low = number of iterations, and work your way up from there. Multiple pools = are much slower than a single, larger pool, or more iterations. - I haven't cleaned up the library or example programs to make them = look pretty yet, so don't expect too much elegance... To use EU-Genes, you have to design your own evaluator procedure, then = send its routine ID (along with the other parameters) whenever you call = the eu_genes() function. Your evaluator will be called once per = iteration, so it will have to loop through all of the pools and = specimens itself to evaluate them. This is so you can do things like = skip evaluations, evaluate by comparing specimens, etc. You'll have to = set the fitness scores for each specimen yourself too. The global = variable that holds the specimens is GenePools. Also, global constants = SPECIMEN_SCORE, SPECIMEN_GENE_SET, GENE_NEXT_STATE, and GENE_OUTPUT are = provided to aid access. The structure of GenePools is: GenePools (seq.) Pool 1 (seq.) Specimen 1 (seq.) Specimen Score (atom) Specimen Gene Set (seq.) Genes for State 1 (seq.) Gene for Input value 1 (seq.) The next state to advance to after "using" this = gene (int.) The output after "using" this gene (int.) Gene for Input value 2 ... Genes for State 2 ... Specimen 2 ... Pool 2 ... The eu_genes() function returns the number of iterations actually run = (this is great for telling if you're hitting your fitness goal well = within the limit, or if you should increment the number of iterations). As an example, the bit_gene.ex program is probably the best. The genes = there are really 1's and 2's to work with the library, but decrementing = each "bit" by 1 to get the true value is trivial. The program produces = 9-state specimens with 2 inputs. Starting at state 1, and given as input = the first bit of the bit string we're trying to reproduce, we output the = value specified by the state-input gene, then move the next state, and = use the output as the next input. This continues until we've output 9 = bits. We then compare these with the last 9 bits of the 10-bit string, = and rank the specimen based on how close it came to matching it. Below = is an example of a 100%-scoring specimen from the program, generated in = 16 iterations (although letters are only used here to illustrate; the = program uses numbers): 1 2 ----------- A | H2 | F1 | ----------- B | G1 | E2 | ----------- C | C2 | C2 | ----------- D | B2 | A1 | ----------- E | D2 | H1 | ----------- F | E2 | I2 | ----------- G | F2 | I2 | ----------- H | C1 | A2 | ----------- I | B1 | H2 | ----------- The bit string trying to be matched is: {1, 2, 2, 1, 2, 1, 1, 2, 2, 2} By starting at state A, input 1 (the first bit of the string), we find = H2 as the gene. This means we begin out output string with {2}, then go = to state H. Now, using the 2 we just output as our input at state H, we = find the gene A2. So we ouput another 2, making our total output {2, 2}, = and move to state A. At state A, input 2, we find gene F1. We output the = 1 to get {2, 2, 1}, and move onto state F. By following this until the = 9th output, we wind up with {2, 2, 1, 2, 1, 1, 2, 2, 2}, which is the = rest of the bit string. Granted, this is a trivial example, and I know I'm giving it a few more = states than it needs to accomplish this task. But I hope it illustrates = the point. The tictac.ex program is an attempt to get the tic-tac-toe playing = specimen. I've gotten much better results lately, although I should warn = you... I'm running on a Pentium II, 233MHz, and if you have something as = fast or faster, expect a 2+ hours of run time... those of you with = slower systems may just want to let it run overnight. I've gotten = "decent" results after 25,000 iterations, and am planning on trying = 100,000 shortly. Both tictac and bit_gene show the number of iterations = run through & the "winning" specimen; if it's a large specimen, tictac = will output all of the gene pools (or the first specimen, if one pool) = to a file called tictac.txt on your desktop. That's it... a simple library that could probably be done much better; = but at least it's a start. Let me know what you think! Rod Jackson =20 ---------- From: Lucius Hilley III[SMTP:lhilley at CDC.NET] Sent: Monday, March 01, 1999 6:47 PM To: EUPHORIA at LISTSERV.MUOHIO.EDU Subject: Re: Genetic Tic-Tac-Toe Help Could you post the code to the list or make it available at a FTP site? Lucius L. Hilley III --This message was brought to you in part by Hollow Horse. --The company that, like a horse, is well endowed. 8^)