Re: Genetic Tic-Tac-Toe Help (long)
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^)
|
Not Categorized, Please Help
|
|
