Possible variants of the
definition
Now we have
the perfect CPP and the question is how to define what is a CPP. We can
say that this is any program which is as good as the perfect CPP. At least
the perfect CPP covers this requirement. This is not a good idea for definition
because we need a program which can play in real time. Also, we do not
need a player so perfect as the perfect CPP.
That is why we will define CPP in the
following way:
First variant of the definition:
CPP will be the program which makes average success which is on smaller
distance than ε from the perfect.
If this ε
is chosen smaller enough, then the chess playing program will play no worse
than a human.
Here we have one problem. We do not
know how big is the perfect result. If the starting position in chess is
winning for the whites, then the perfect result is one (or 1  δ
where δ is zero). If the starting position
is not winning for the whites, then the perfect result is 1  δ,
where δ is some very small number bigger
than zero. We have an algorithm for calculating the value of δ,
but we cannot calculate it because this algorithm will not end in reasonable
time (i.e. before the end of the universe). The conclusion is that the
previous definition is not convenient because it includes two constants
whose value cannot be calculated (δ
cannot be calculated due to the combinatory explosion and ε
cannot be calculated at all because it depends on the human beings, which
means that this constant has no exact value). Even if we choose a value
for ε we will still not know the value
of the δ+ε. This is the reason to define
a CPP in a different way.
Second variant of the definition:
CPP will be the program which makes average success which is bigger than
1  α.
Here α
is some small positive number. It must be equal to δ+ε
in order to be the new variant of the definition the same as the previous
variant. In any case α must be greater
than δ because in the opposite case
CPP will not exist.
The second variant of the definition
gives us the possibility to check it for a concrete program by the tools
of the statistics. There are two problems. First, we cannot say how big
should be α for the CPP to exist and
in order to play no worse than a human being. Of course, such value exists
but we cannot say which it is. The second problem is that the value of
α is very small, which makes it extremely
difficult to calculate it by the methods of the statistics.
In order to eliminate the second problem
we will change the opponent. We need a stronger player as opponent in order
to have bigger expectation for δ+ε.
Let us try with human being as an opponent.
Third variant of the definition:
CPP will be the program which makes average success against human being
bigger than 1/2.
The third variant of the definition
is not formal, but this variant is usually used as a definition of CPP.
The good side of this definition is that it can be checked by the methods
of the statistics. For example, if we make ten games between one program
and a human being and if the average success of the program is 60% (0.6),
then we can say with big possibility that this program satisfies the definition
for CPP. Really ten games are too few and for bigger certainty we may make
100 or even 1000 games. Here our expectation for δ+ε
is 1/2. Really the game is not symmetric (opponent plays always with the
blacks) and that is why we are not sure that human against human will make
1/2 average success. Also, you have to notice that this variant of the
definition is not formal and that the results will depend on the humans
we use for opponents.
New fixed opponent
Anyway, we
need a formal definition of CPP and that is the reason why we will use
a welldefined opponent. Such opponent is the standard chess playing program
which calculates N moves in the tree
of the game and by MinMax algorithm selects the best move. The
problem is that this opponent is deterministic. We prefer the opponent
to be nondeterministic because if both CPP and the opponent are deterministic,
then the result of the game between them is also deterministic (actually,
there is only one possible game between them). In this case we cannot use
the methods of the statistics. Also, it is not a good idea to use deterministic
opponent for the definition because all deterministic programs which have
average success one will be CPP but maybe some of them accidentally made
victory in this only game, which does not prove that these programs are
CPP.

For opponent we will use nondeterministic
variant of the standard chess playing program. Let our opponent depend
on one integer N and two functions
 F and P.
Let function F evaluate positions and
on every position F return an integer.
Let function P give the possibility
for one move to be chosen. This means that the input of P
is a list of integers which represent the values of the positions which
can be obtained on the next move and the output is a list of the possibilities
each of these positions to be obtained. The integer N
and the functions F and P
should be concrete and fixed because they will be parameters in our definition.
If we change one of these parameters, then the definition will also be
changed.
How will this fixed opponent work. It
will evaluate by the function F all
positions which are obtainable after N
moves from the current position. After this, by the MinMax algorithm,
it will calculate the values of the positions which are obtainable on the
next move. After that, by P, it will
calculate the possibility of each of these positions to be obtained and
on the end will randomly choose one of the moves, but in such a way that
the possibilities of the next positions to be the same as the ones given
by P.
This fixed opponent is nondeterministic
(except the case when P gives 1
to one of the numbers and zero to the rest of them).
After the change of the opponent we
also have change in the perfect CPP. It will be constructed almost in the
same way, but instead of average value it will calculate the sum of Value(i).Possibility(i)
where i runs true all possible
moves of the opponent. Here Possibility(i)
will be given by the function P. (Of
course, before applying the function P
we have to use function F and MinMax
for N moves in order to calculate the
values of all positions which are obtainable on this move.)
If the number N
is big enough and if the functions F
and P are reasonable, then our fixed
opponent is a good chess player. This means that our expectation for δ
and ε will be high. Let us assume that
ε is 10%. This means that we suppose
that a human being will make average success against the fixed opponent
10% worse than the perfect CPP. Let us assume that the average success
of the perfect CPP is 80% (i.e. that δ
is 20%). If the starting position is winning for the whites, then δ
is zero but our expectation is that the starting position is not wining
and not losing. This leads us to the following:
Final variant of the definition:
CPP will be the program which makes average success against the fixed opponent
which is bigger than 70%.
As we mentioned, this definition depends
on the fixed opponent and from the number α,
which here is fixed to 30%. If we fix also the number N
and functions F and P,
then we will have one concrete definition. We can easily check whether
one program satisfies the requirement of this definition by the methods
of statistics. Really, we cannot check this for sure, but with a great
percent of possibility (which percent grows with the number of the test
games).
This definition is made with one assumption:
Assumption 1: Here we assume
that the average success of the perfect CPP is about 80%. If this conjecture
is true, then there exists a program which satisfies the definition (at
least the perfect CPP does). If the average success of the perfect CPP
is smaller than 70%, then there is no such a program (of course, in such
case we can change this parameter and make it smaller than 70%).
Conclusions
The first
concussion is that CPP exists and that the perfect CPP satisfies the demands
of the definition. Really, this is true if assumption 1 is true, but if
we take the fist variant of the definition then this is true without assumption
1.
The second conclusion is that the perfect
CPP is CPP but it is useless due to the combinatory explosion. In order
to obtain a real CPP we have to optimise the perfect CPP and make a program
which may be a worse player than the perfect but which can play in real
time. That is an easy task in the case of chess, but not so easy in the
case of AI.
References
[1] Dobrev D. A Definition of Artificial Intelligence. In: Mathematica
Balkanica, New Series, Vol. 19, 2005, Fasc. 12, pp.6774. (The
same in popular form)
[2] Dobrev D. Formal Definition of AI.
In: IJ ITA, Volume
12, Number 3, p.277.
