What is a chess playing
program?
For
us a chess playing program (CPP) will be a step device which inputs the
move of the opponent and outputs a correct move as an answer on every step.
If this was the only requirement, then the random player would be chess
playing program, but this is not true because the random player plays too
bad. That is why we will want from the chess playing program to play no
worse than a human being.
Here you can ask the question: "Who
is the human being?" The answer is that this is not so important because
the difference between the average chess player and the world chess champion
is not that big. This is because the program which plays better than the average
chess player is almost the same as the program which plays better than the world
chess champion. The main difference is in the number of moves which are calculated
in order the next move to be chosen. Of course, the second program needs more time
or faster computer than the first one.
The definition which includes the world
human is not formal but it can be formalised.
To make the definition formal first
we have to formalise the opponent. We will suppose that the opponent of
our chess playing program is the random player. This is the opponent which
every time plays a random move. Of course, you can have many different
random players which have different possibility for choosing their random
moves, but we will assume that our random player chose its random move
with equal possibility. That means that if this player has N
possible correct moves, then the possibility for each of them to be chosen
is 1/N.
The random player is very weak opponent,
but, anyway, it is a dangerous partner because sometimes it makes genius
moves. Really, the possibility to make a genius move is pretty small. The
good side of the random player is that it is simple and well defined. Another
positive feature of the random player is that it has no memory. This means
that it cannot learn and that the next game will not depend on the previous.
We will make some additional assumptions.
We will assume that the rules of chess are fixed and that these rules do
not allow infinite game (for example, if 20 moves no pawn is moved and
no figure is taken then the game is draw). We will assume that our CPP
plays with whites in every game.
We may assume that our CPP is a deterministic
program (i.e. that it plays only one strategy). If we assume that CPP is
nondeterministic program and that it plays many different strategies, then
we have to know what is the possibility of each possible strategy. In the
first case the average success of CPP will be the average success of its
strategy. In the second case its average success will be the average from
the average successes of all strategies (the sum of AverageSuccesses(i).Possibility(i)
where i runs true all strategies
of CPP). Notice, that the number of all strategies is finite due to the
fact that the tree of the game is finite, which is so because the rules
of chess do not allow infinite games.

Now we have to ask the question
about the goal of the game. In the case of AI this question was difficult
and we had to introduce the notion of meaning of life. Here we have no
such problem because the goal is obvious and it is to win the game. Speaking
more formally, let us give to CPP one for victory, zero for lost and half
for draw game. The goal will be to make the biggest average success.
The perfect CPP
After this
formalisation we can say when one CPP is better than another and even something
more, we can show the perfect chess playing program (or the perfect chess
playing strategy, which is the same if the program is deterministic). The
perfect CPP will calculate the tree of all possible moves before making
any move, and that is why this program will be practically useless due
to the combinatory explosion. Anyway, it is interesting from the theoretical
point of view to have such a program.
The perfect CPP will evaluate all positions
in the tree of the game by MaxSum algorithm (maybe in this case
it is better to call this algorithm MaxAverage instead of MaxSum).
This algorithm is theoretically possible because the tree of the game is
finite. The MaxSum algorithm evaluates first the leaves of the
tree and gives one for these leaves whose position is victory for CPP,
zero respectively for victory for the opponent and half for draw positions.
After this, MaxSum algorithm evaluates the rest of the vertexes
calculating maximum from the evaluation of the successors when the move
is made by CPP and calculating average when the move is made by the opponent.
Of course, after this evaluation MaxSum algorithm plays by selecting
this move which leads to the vertex with maximal value. (Of course, if
vertexes with maximal value are more than one the MaxSum algorithm
chooses one of them. Because of this choice we can have more than one perfect
strategy and also we can have nondeterministic perfect CPP which combines
several perfect strategies.)
The perfect CPP is perfect but useless
due to the combinatory explosion. It is easy to see that this program will
make the best average success against the random player. Anyway, the perfect
CPP is a little bit strange. If it is in a winning position, then it will
win, which is OK, but if the perfect CPP is in draw position, then it can
lose the game. Actually, perfect CPP can move from draw position to losing
position, which is strange, but this is because the perfect CPP is perfect
against the random player. If the opponent was different then the perfect
CPP would be different.
