From: "trans.  (T. Onoma)" <transami@...>
Date: 2004-12-13T23:01:23+09:00
Subject: Re: [QUIZ] Learning Tic-Tac-Toe (#11)

On Monday 13 December 2004 03:17 am, martinus wrote:
| Has anyone tried a genetic programming approach? I have tried it, but
| it does not work as expected. My problem is how to represent the logic
| of the individuals so that mutation/crossover makes sense.
|
| martinus

I did. It's interesting b/c genetic agents are absolutely stupid and take a 
long time to learn. Nonetheless I ran a population of 100 through a 5000 
generations and they did improve, but still not perfect. I worry that it is 
difficult to escape local maxima (which tells you something about Darwinian 
evolution itself.)

As to the logic. I simply gave them a "tiny" abstract computer which gets 
programmed with a simple AST. To do this I divide the board into three parts: 
slots, and X's and O's postions. The slots are numbered as follows:

  256 | 128 | 64
 -----+-----+----
  32  | 16  | 8
 -----+-----+----
  4   | 2   | 1

X's and O's representation of the board are simply a binary number 
cooresponding to the above board for the slots they have. Quick example:

  OXO
  __O
  X_X

  X: 0b010000101
  O: 0b101001000

I also represent whose turn it is with 0b111111111 and 0b000000000.

So with that data I create an AST of logical operations:

  AST = [ "|m", "&m", "^m",
          "|e", "&e", "^e",
          "|s", "&s", "^s",
          "|t", "&t", "^t"  ]

m = current players board
e = enemy players board
s = a slot (per above chart)
t = turn

During mutation one of the three operators (|,&,^) and an arbitrary number can 
also be added. So you might end up with something like this (completely made 
up example):

  "|m&m|s^e^234|t|t"  

I process this using #eval (first character gets removed). For each turn I 
loop through each available slot on the board (s) and pick the one that 
returns the highest value. Perhaps not the most elegent design, but I'm 
pretty certain it is a sufficiant formalism.

Of course that doesn't help with heredity b/c a slight change to these little 
programs has drastic effects. We need something with smoother variance. So I 
gave each agent any number of these little programs and average out the 
results.

I'm not quite finished with my program. And unfortunately I won't be able to 
get to it til tommorrow --but I'll post it then if you would like to look at 
it.

What approach have you been working on?

T.