Distributing Evolution using a Queue Genetic Algorithm
Read the QGA paper
One of the difficulties with Xpilot is that it is meant to be run at speeds playable to a human; speeding up the game can cause network packet loss and display problems. To evolve a Genetic Algorithm using non-distributed Xpilot takes days. That is why we made the Queue Genetic Algorithm (QGA). It easily distributes the evolution of one GA to multiple simulations, speeding evolution many times over.
Functionality
Let's say we want to evolve a GA bot named "learnbot" to control a ship fighting against a hard-coded bot named "tim" on a map named "block.xp". We would get our simulation going with something like this:
xpserver -map block.xp &
./tim "join localhost" &
./learnbot "join localhost"
Within the learnbot file we would need code to initiate a GA, either creating a new random population, or loading an old one from file; get the chromosome of the current individual, and convert it to meaningful behavior; test the individual and when finished assign a fitness; evolve the population at the appropriate time.
Our qga_server script handles most of the GA operations for you. Here is the format of the script:
qga_server [test name] [population size] [num genes] [bits per gene] [port]
So we might run for our above test "learnbot":
qga_server bot3 128 50 6 1440
This would look for any bots that already have been saved named "bot3" and if found, load their saved chromosomes. If not found, it would create a population of 128 individuals which have chromosomes that are made of 50 genes, 6 bits per gene, as specified in the command-line.
To connect to the QGA server, we would use the qga_client extension in the "learnbot" script, and now specify the location of the qga_server and the port. We might run the whole simulation like this:
xpserver -map block.xp &
./tim "join localhost" &
./learnbot "join localhost" localhost 1440
This would connect learnbot to the qga_server running on localhost on port 1440. Now let's say we want to double the speed of the evolution, we could run another simulation on the same computer and connect it to the same qga_server. We just have to specify different ports for the xpserver and for "tim" and "learnbot" accordingly:
xpserver -map block.xp -port 2055 &
./tim "join localhost -port 2055" &
./learnbot "join localhost -port 2055" localhost 1440
You can connect and disconnect as many times as you like, and you can connect to the same QGA server from different computers around the internet, with virtually no limit to the number of connections (limited by hardware).
Using the qga_client
For the above example "learnbot", the code might look something like this:
#!/usr/local/bin/csi -script
;load xpai
(use xpai)
;load the qga_client library
(use qga_client)
;load the xpilot client window
(xpilot (string-append (car (command-line-arguments)) " -name Prj2_" (number->string (random 49867))))
;connect to the QGA server specified in the command line
(qga.connect (cadr (command-line-arguments)) (string->number (caddr (command-line-arguments))))
(define AImain
(lambda ()
(qga.main)
(if qga.new
(printf "A new bot!\n"))
(if qga.died
(printf "Died!\n"))
(if (= 1 (AIself.alive?))
(begin
(set! currentindiv.fitness (add1 currentindiv.fitness))
(bot-control)))))
(define bot-control
(lambda ()
(if (> 32 (qga.genetonum (car currentindiv)))
(AIself.thrust 1))
(if (> 32 (qga.genetonum (cadr currentindiv)))
(AIself.shoot 1))
(if (> 32 (qga.genetonum (caddr currentindiv)))
(AIself.turn 15))))
;make the code loop so csi doesn't exit
(define dosleep (lambda () (thread-sleep! 1) (dosleep)))
(dosleep)
This sample code will evolve a very simple bot that will read its first three genes, convert them to numbers (between 0 and 63 because it's a 6 bit gene), and if the number is greater than 32 it will thrust, or shoot, or turn. This bot gets fitness for every frame that it stays alive by increasing the variable currentindiv.fitness. When it dies, which it can tell by seeing if the variable qga.died is true, a message "Died!" is printed, which would be a good spot to finalize the fitness, like to square it. When a new bot's chromosome is loaded, the variable qga.new will be true for one frame; this is a good time to calculate information from the bots chromosome, such as weights to a neural network.
The function (qga.main) is run every frame, and must be called at the start of your AImain function.
If you want to skip a death, such as if you want the same chromosome to play for several lives, call the function (qga.skipdeath) when qga.died is true.
Installation
Note: You must have first installed SDL and SDL_net.
Run all of the following:
chicken-setup http://xpilot.conncoll.edu/easyfile.egg
chicken-setup http://xpilot.conncoll.edu/glorytcp.egg
chicken-setup http://xpilot.conncoll.edu/qga.egg
To look at the source code, just "tar xfz qga.egg".
matparke@cs.indiana.edu