📄 lithos.html
字号:
<html>
<head>
<title>Lithos</title>
</head>
<body>
<center><h1>Lithos</h1></center>
<p>
Lithos is a stack based evolutionary computation system. Unlike most EC systems, its representation language is computationally complete, while also being faster and more compact than the S-expressions used in genetic programming. The version presented here applies the system to the game of Go, but can be changed to other problems by simply plugging in a different evaluation function. Source code and Windows executable are provided. Let me know by <a href="mailto:rwallace@esatclear.ie">email</a> if you have any queries or interesting results or modifications.
<p>
This software is in the public domain.
<p>
THIS SOFTWARE IS PROVIDED STRICTLY AS IS. THE AUTHOR MAKES NO REPRESENTATION OR WARRANTY OF ANY KIND, INCLUDING BUT NOT LIMITED TO ANY WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. UNDER NO CIRCUMSTANCES SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT OR INDIRECT EXPENSES OR DAMAGES AS A RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE.
<p>
<a name="Contents"><h2>Contents</h2></a>
<p>
<ul>
<li><a href="#The genetic algorithm"><b>The genetic algorithm</b></a></li>
<ul>
<li><a href="#Parameters">Parameters</a></li>
<li><a href="#The next generation">The next generation</a></li>
<li><a href="#The log file">The log file</a></li>
</ul>
<li><a href="#The virtual machine"><b>The virtual machine</b></a></li>
<ul>
<li><a href="#The instruction set">The instruction set</a></li>
<li><a href="#Control flow">Control flow</a></li>
</ul>
<li><a href="#Example programs"><b>Example programs</b></a></li>
<ul>
<li><a href="#Factorial(n) recursive style">Factorial(n) recursive style</a></li>
<li><a href="#Factorial(n) iterative style">Factorial(n) iterative style</a></li>
</ul>
<li><a href="#The game of Go"><b>The game of Go</b></a></li>
<li><a href="#Download"><b>Download</b></a></li>
</ul>
<p>
<a name="The genetic algorithm"><h2>The genetic algorithm</h2></a>
<p>
Like other evolutionary computation systems, Lithos evolves a population of individuals. In each generation, every individual is tested for fitness at a task, then the less fit ones are replaced by offspring of the more fit ones, using crossover and mutation to achieve variety.
<p>
In this case, the individuals are programs, each represented as a sequence of instructions. In testing fitness, each program is run on some input and the output is evaluated according to some measure of quality. In the version presented here, the input is the current state of the board in the game of Go, and the output is interpreted as a decision about the next move to make.
<p>
<a name="Parameters"><h3>Parameters</h3></a>
<p>
The system is controlled by the following parameters:
<p>
<b>Population</b> is the number of programs. This doesn't change over time; offspring of more fit programs replace less fit ones.
<p>
<b>Max Size</b> is the maximum allowed size of a program. (At the start of a run, the entire population is initialized to empty programs. Crossover and mutation may produce longer or shorter programs as generations go by, up to <i>Max Size</i> instructions.)
<p>
<b>Max Memory</b> is the number of words of memory available to each program at run time. (This does not include the memory to store the program code.) Must be at least large enough to hold the program's input data; for the game of Go, this means at least 383 words.
<p>
<b>Max Time</b> is the number of instructions can execute during its "thinking time" in each move of the game (or step of the task or whatever). If this is exceeded, the program times out and whatever it has left on the stack at that point is taken as its output.
<p>
<b>Max Moves</b> is the maximum number of moves the game is allowed to continue for. (In practice this will rarely be reached.)
<p>
<b>Overselection Rate</b> is the number of individuals in each generation guaranteed to be transmitted unchanged to the next. With the default value of 2, the best 2 individuals are copied to the next generation before tournament selection takes place for the rest of the population slots.
<p>
<b>Tournament Size</b> is the number of individuals involved in each selection tournament.
<p>
<b>Crossover Rate</b> and <b>Mutation Rate</b> control how often these two operators will be applied when producing offspring programs for the next generation. The default values of 50 and 50 mean they are equally likely to be applied; 90 and 10, for example, would apply crossover 90% of the time and mutation only 10%. At least one of these values must be nonzero.
<p>
<b>Autosave Frequency</b> controls how often the current population is automatically saved to the <code>data</code> file in case of power failure or other external interruption. The default value of 100 saves every 100 generations. A value of 1 would save every generation, 0 would turn off autosave altogether.
<p>
<b>Log Frequency</b> controls how often entries are written to the <code>log</code> file. The default value of 1 writes a log entry every generation. A value of 10 would log every 10 generations (suitable for runs with a small population for very many generations), 0 would turn off logging.
<p>
The parameter values are read from a file called <code>params</code> if it is present, otherwise the following defaults are used:
<p>
<pre>
[Population] 100
[Max Size] 1000
[Max Memory] 1000
[Max Time] 10000
[Max Moves] 1000
[Overselection Rate] 2
[Tournament Size] 4
[Crossover Rate] 50
[Mutation Rate] 50
[Autosave Frequency] 100
[Log Frequency] 1
</pre>
<p>
This is the format used, so creating a <code>params</code> file and inserting the above into it will keep the defaults; individual entries can then be changed. Note that if the file is present at all, it must have all the entries in this exact order.
<p>
<a name="The next generation"><h3>The next generation</h3></a>
<p>
When all the individuals in a generation have been evaluated for fitness, the program chooses some of them to be transmitted to the next generation. Taking the default values of <i>Population</i> = 100, <i>Overselection Rate</i> = 2 and <i>Tournament Size</i> = 4, the procedure is as follows:
<p>
<ol>
<li>Fill the first 2 slots of the next generation with the 2 best individuals of this one.</li>
<li>Fill each of the other 98 slots with an offspring of one or two current individuals.</li>
</ol>
<p>
To fill a slot:
<p>
<ol>
<li>Choose a parent by tournament selection.</li>
<li>Decide whether to use crossover or mutation according to the <i>Crossover Rate</i> and <i>Mutation Rate</i> parameters.</li>
<li>If mutation, fill the slot with a mutated version of the parent.</li>
<li>If crossover, choose another parent by tournament selection, and fill the slot with an offspring based on a combination of the parents' codes.</li>
</ol>
<p>
To choose a parent by tournament selection:
<p>
<ol>
<li>Choose 4 individuals at random.</li>
<li>Select the most fit of those 4.</li>
</ol>
<p>
To mutate an individual:
<p>
<ol>
<li>Choose at random whether to perform insertion, substitution or deletion (equal probabilities, except if the individual is of zero length then only insertion can be performed; if of length equal to <i>Max Size</i> then insertion cannot be performed).</li>
<li>If insertion, choose an insertion point (between any two adjacent instructions, or at the start or end, equal probability for each point) and insert a random instruction there.</li>
<li>If substitution, choose an instruction and change it at random. (1 in 30 chance of changing it to the same instruction, i.e. leaving it unchanged.)</li>
<li>If deletion, choose an instruction and delete it.</li>
<li>Flip a coin; if it comes up heads, go back to step 1. (So usually only one or two instructions will be mutated, but in theory any number could be.)</li>
</ol>
<p>
To cross over two individuals:
<p>
<ol>
<li>Choose a break point in each individual.</li>
<li>Copy the first individual's code up to its break point, then copy the second individual's code from its break point on.</li>
</ol>
<p>
To choose a break point:
<p>
<ol>
<li>The start and end are valid break points.</li>
<li>Every point between a label and a nonlabel instruction is also valid. (Labels are explained under <a href="#Control flow">Control flow</a>; the theory is that code should get spliced at reasonable breaks between functional units. Informal eyeballing of debugging output suggests this works fairly often.)</li>
<li>Choose a valid break point at random.</li>
</ol>
<p>
When all the slots in the population have been filled, the process of evaluating all the individuals for fitness begins again.
<p>
<a name="The log file"><h3>The log file</h3></a>
<p>
The <code>log</code> file has columns for the following values:
<p>
<b>Generation:</b> The current generation number.
<p>
<b>Complexity:</b> The size of the most fit individual.
<p>
<b>Diversity:</b> The number of "subspecies" in the population, where two programs belong to the same subspecies if their first and last instructions are equal. (Zero length programs are ignored in this count, thus the maximum possible value is 30 * 30 = 900. A crude measure, but simple to define and cheap to compute.)
<p>
<b>Score:</b> A measure of the performance of the most fit individual at the task. For games, it's the number of points scored by that individual when playing against the second most fit one.
<p>
The columns are tab separated so the file can easily be loaded into a spreadsheet for plotting graphs.
<p>
<a name="The virtual machine"><h2>The virtual machine</h2></a>
<p>
Lithos uses a stack based virtual machine. A program within it consists of a sequence of instructions, normally executed one after the other; most instructions take their inputs from the stack and push their outputs onto it.
<p>
The virtual memory is an array of words. Taking the default value of <i>Max Memory</i> = 1000, memory addresses go from 0 to 999. Inputs are placed at the bottom of memory - for the game of Go, words 0 to 382 are initialized to the current state of the game, with the rest being zero.
<p>
Each word contains an integer, 32 bits on typical hardware. (Or in general, whatever the C compiler decides an <code>int</code> is. Note that <i>Population</i> * <i>Max Size</i> cannot exceed the range of an <code>int</code>; in practice, this means that the total size of all the VM programs cannot exceed 2 gigabytes, which is a restriction that 32 bit machines would impose anyway.) Thus, VM programs can directly handle, on typical systems, numbers in the range of approximately -2 billion to +2 billion.
<p>
The stack grows from the top down and is initially empty. It wraps around on overflow or underflow. So if the first instruction is <code>CONST1</code>, the value 1 will be placed in location 999. If the first instruction is <code>ADD</code>, the stack will underflow so the input words in locations 0 and 1 will be added together and the result will be placed in location 1. (Evolved programs quite often exploit this.)
<p>
Stack words are left unchanged unless explicitly overwritten, so in the above <code>ADD</code> example, location 0 will retain its original contents.
<p>
When a program terminates (either by executing its last instruction or by staying in a loop and timing out after <i>Max Time</i> instructions), whatever it has left on top of the stack is taken as its output. (Because of wraparound, this means that a null program will effectively echo its input - the first words of the input will be "on top" of the stack.)
<p>
While a single memory space is used for input, data stack and subroutine return addresses, it is not used for program code. This is in a separate memory area, and programs have no way to directly access their own code.
<p>
<a name="The instruction set"><h3>The instruction set</h3></a>
<p>
There are 30 instructions, each consisting of an opcode only (no immediate operands). In the table below, the inputs are taken from the stack, pushed in the order given (i.e. the last operand is on top of the stack) and the outputs are pushed onto the stack.
<p>
<table border>
<tr>
<th>Instruction</th>
<th>Inputs</th>
<th>Outputs</th>
<th>Description</th>
</tr>
<tr>
<td colspan=4>Numbers</td>
</tr>
<tr>
<td><code>CONST0</code></td>
<td></td>
<td><code>0</code></td>
<td>Constant 0</td>
</tr>
<tr>
<td><code>CONST1</code></td>
<td></td>
<td><code>1</code></td>
<td>Constant 1</td>
</tr>
<tr>
<td><code>RANDOM</code></td>
<td></td>
<td><code>random(0..1)</code></td>
<td>Random number, either 0 or 1</td>
</tr>
<tr>
<td colspan=4>Arithmetic</td>
</tr>
<tr>
<td><code>INC</code></td>
<td><code>x</code></td>
<td><code>x + 1</code></td>
<td>Increment</td>
</tr>
<tr>
<td><code>DEC</code></td>
<td><code>x</code></td>
<td><code>x - 1</code></td>
<td>Decrement</td>
</tr>
<tr>
<td><code>ADD</code></td>
<td><code>x, y</code></td>
<td><code>x + y</code></td>
<td>Addition</td>
</tr>
<tr>
<td><code>SUB</code></td>
<td><code>x, y</code></td>
<td><code>x - y</code></td>
<td>Subtraction</td>
</tr>
<tr>
<td><code>MUL</code></td>
<td><code>x, y</code></td>
<td><code>x * y</code></td>
<td>Multiplication</td>
</tr>
<tr>
<td><code>DIV</code></td>
<td><code>x, y</code></td>
<td><code>x / y</code></td>
<td>Division</td>
</tr>
<tr>
<td colspan=4>Comparison</td>
</tr>
<tr>
<td><code>EQ</code></td>
<td><code>x, y</code></td>
<td><code>x == y</code></td>
<td>Equal</td>
</tr>
<tr>
<td><code>NE</code></td>
<td><code>x, y</code></td>
<td><code>x != y</code></td>
<td>Not equal</td>
</tr>
<tr>
<td><code>LT</code></td>
<td><code>x, y</code></td>
<td><code>x < y</code></td>
<td>Less than</td>
</tr>
<tr>
<td><code>GT</code></td>
<td><code>x, y</code></td>
<td><code>x > y</code></td>
<td>Greater than</td>
</tr>
<tr>
<td><code>LE</code></td>
<td><code>x, y</code></td>
<td><code>x <= y</code></td>
<td>Less than or equal</td>
</tr>
<tr>
<td><code>GE</code></td>
<td><code>x, y</code></td>
<td><code>x >= y</code></td>
<td>Greater than or equal</td>
</tr>
<tr>
<td colspan=4>Logic</td>
</tr>
<tr>
<td><code>AND</code></td>
<td><code>x, y</code></td>
<td><code>x and y</code></td>
<td>And</td>
</tr>
<tr>
<td><code>OR</code></td>
<td><code>x, y</code></td>
<td><code>x or y</code></td>
<td>Or</td>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -