Quote: Seuss, that's really interesting. I'm not a programmer, but I did follow a decent Java course for my study, is there any way I could understand the basics of the code of a simple evolution program you wrote?
It has been a while since I have worked with this, but I will try to find my old code. The games I mostly work with are tic-tact-toe, connect four, and Othello. Tic-tac-toe is a very simple game and takes very little time for a solution to evolve. This is a good way to test that a network is learning properly. Connect four builds upon tic-tac-toe increasing the board size and the goal size. Othello builds again, increasing the complexity of the game yet again.
The heart of the code I wrote is based around a self-organizing map (SOM). This is a form of unsupervised learning. For example, it takes a newborn baby around a week to learn how to focus it's eyes. The newborn learns this on it's own, not with somebody teaching it how to focus. A self-organizing map works the same way. It learns to distinguish patterns based upon the patterns that it has previously seen.
The SOM is implemented with a feed-forward neural network. The network shape is defined by an artificial DNA... just a long string of numerical values. Rather than try to encode all the weights and connections, I encode functions that will build the neurons and connections. When the DNA is expressed, a finite set of SOMs are grown. The outputs from one SOM become the inputs to others. Each neuron decides who it gets input from, based upon the DNA coded function for that neuron. Weights are initially set to -1 or 1 (inhibit or excite) and are normalized to unity. Again, and DNA coded function determines the connections and the initial weight (-1 or 1).
A population of organisms is created. Initially, the population watches a computer program play the game. During this time, the SOM is learning the pattern (rules) of the game and play. As the organism ages, it is eventually allowed to compete in the games. As the organisms play each other, their fitness is recorded based upon how well they play. The fitness function is also scaled by the age of the organism. The allows young organisms to survive before they learn how to play and rewards older organisms that have not been killed off as well.
After some set length of time (number of games played), the population is culled by fitness. The least fit of the population are deleted, and the remaining population is allowed to 'mate' until the population size is back to normal. I have used many different mating rules. My current implementation actually mixes up several different strategies... some blocks of DNA are averaged together, other times the section from only one parent is used, other times random crosses occur, and yet other times random mutations are inserted.
I tend to run several populations simultaneously. Organisms from each distinct population are crossed from time to time to help prevent local minimums and help maintain genetic diversity. Children in the population are never culled, allowing a mutation to find its way into the population even if the overall fitness of that mutated organism is poor.
Inputs and outputs into the system are treated as bits in a number. For an Othello board, I have 128 inputs (two neurons for each tile). A value of 00 or 11 means the tile is empty. A value of 10 means the tile is white while a value of 01 means the tile is black. The output for Othello is a 64-bit value with each bit representing a single tile on the board. The bit with the highest value (the most excited neuron) is the play that is made. (I use the word 'bit' loosely here... implementation is a floating point number normalized between -1 and 1...) Sometimes I simply ignore (mask out) all the bits that are not valid moves while other times I end the game as a loss (depending upon the experiment that I am doing).
I also use a decaying timeout after a neuron fires limiting the fire rate of the neuron. Again, this is determined on a neuron by neuron basis by a DNA defined function. Once a neuron fires, it will not be able to fire again for so many 'clock' ticks. This allows the system to create state machines and timers more easily.
I also assign inputs to a timer that represents the percentage of time left in game play. An output neuron acts to signal that the current state of the network should be used for a move. Rather than cycle the network for a fixed number of clock tics, I allow the network to think as long as it likes for each move. The organism must learn to manage it's own game time.
Another adaptation I have made on the above is using the network as a board evaluation function only within an AB-minimax search tree. In these cases, I use many multiple networks. One as the evaluation function, one as a predictor for the opponent's move, one to sort the moves at each node from most likely best move to least likely best move, one to decide time management, etc.
The networks are constantly learning while they play through the self-organizing model. This means that the organism (usually) gets better at the game as it lives longer. However, this learned knowledge is not passed on to the children. Only the design of the network is passed, not what the network learned. This tends to produce organisms that can quickly learn how to play the game rather than organisms that are born with instinctual knowledge of how to play the game. The entire population of organisms that are not currently playing 'watch' the organisms that are playing. During this time, the watching organisms are still modifying their networks, but their fitness functions are not altered.
-------------------- Just another spore in the wind.
|