Pfthb

I want to develop a genetic program that can solve generic problems like surviving in a computer game. Since this is for fun/education I do not want to use existing libraries.

I came up with the following idea:

The input is an array of N integers.
The genetic program consists of up to N ASTs, each of which takes input from some of the array elements and writes its output to a single specific array element.

The ASTs can be arbitrary complex and consist only of four arithmetic operators (+,-,*,/) and can operate on constants and fixed elements of the given array (no random access).

So for [N=3], we have 3 ASTs, for example:

a[0] = a[0] + 1
a[1] = a[0] + a[1]
a[2] = a[0] * 123 + a[1]

The N ASTs are executed one after another and this is repeated infinitely.

Now my question, is this system "mighty" enough (turing complete?) or will it fail to solve some kinds of problems common for an game AI?

From my perpective the Turing completness of the system is not the main problem here. When using a genetic algorithm to evolve some kind of a strategy applied to some game environment one of the features of the algorithm - that would be helpful - is - I believe - that the small change in the "genome" of the solution lead to a reasonably small change in the behavior. If this is not true then every mutation or cross over can produce an entity that behaves completely different and in this kind of landscape it can be problematic for the genetic algorithm to arrive to some optima - as the landscape of the fitness function is not continuous enough.

Having said that it makes sense to me to try to somehow encode a form of decision tree in the genome and evolve that. However - from my experience - the genetic algorithms in AI for games works best when used to "compute" the optimal values of some parameters of some particular behavior then to "evolve" the behavior itself.