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 Max-Sum algorithm (maybe in this case it is better to call this algorithm Max-Average instead of Max-Sum). This algorithm is theoretically possible because the tree of the game is finite. The Max-Sum 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, Max-Sum 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 Max-Sum 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 Max-Sum 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.