Wednesday, December 17, 2008

Maximal Esotericism

Redundancy is an important aspect of any code which has intentions of evolving through natural selection. Imagine a program, for example, which performs a certain task such as generating a sequence of prime numbers. If such a program were written to be as small or efficient as possible, it is highly probable that any modification made to a single instruction would cause the system to malfunction and no prime numbers would be generated. Since evolution depends on the accumulation of beneficial random mutations of a program, the program must at least be partially tolerant of changes.

A simple solution to this problem is to construct the initial program in a reduced instruction set environment, such as the OISC. Having only a single parameter based command, this one instruction set computer has no need for explicit coding of the opcodes and programs can become extraordinarily long even to achieve relatively simple tasks. To move data from one register to another, a very important and commonly used operation which is typically executed in a single instruction cycle, requires four instruction cycles in OISC using the subtract-and-branch-if conditional statement. See the example below.

MOV a, b ==
subleq b, b
subleq a, Z
subleq Z, b
subleq Z, Z

With simple instructions being expanded in this way, the program as a whole has a greater toleration of occasional mutation and is now ready to perform a massive evolution attempt. A simple Tetris playing artificial intelligence, written in OISC, provides an interesting experiment. First, several thousand slightly different versions of the AI are automatically synthesized by a mutation algorithm. Obviously, a very large number of these different version will be malformed and will not succeed in playing the game. However, occasionally, some of these variants will have acquired an advantage and will out perform their cousins. A simple scoring procedure can be written to evaluate the effectiveness of different AIs and only allow those which perform better to make it to the next generation. The cycle repeats when those which succeed are then selected for mutation of several thousand new variants, each with different mutations. Eventually a high performance Tetris solving algorithm will emerge. The system as a whole can continue to evolve and seemingly learn to play better and better. With accumulation of millions of mutations the final result will be something completely alien to the original human generated algorithm. It may develop intelligence and even self awareness, anything it needs to play the game.

No comments: