General information about the evaluation
I will first present general information about how the programmers make their software "think".
They use algorithms, i.e. blocks of elementary operations. You will hear, in this topic, the words "heuristic methods ".which are methods, often based on precise calculations, but also using empirical techniques, which make possible to find ways of approaching step by step of a good final solution.
We can distinguish several types of algorithms, used simultaneously by the programs, through two steps of " thinking ":
1) the dynamic evaluation , which corresponds to the forecast of the movements of the opponent, the answer of the computer, the answers to the answer, the answer to the answer to the answer,....etc..., and this, as far as possible in the future. This vision of the computer is " tactical ", because it evaluates the movements of the pieces, without global evaluation of the position.
If the processors had a capacity and a speed several billion times higher than their current performances, this step would be enough for the computer which, from the first move, would analyze all the possible alternatives until the last move, and would play at each turn the best move.
But (fortunately ?), the computers are not so powerful ; it is necessary that the machine stops its analysis at the end of some move, and proceed to second type of analysis.
2) the static evaluation of the situation, which is like a "glance" that one can have on a position. Independently of possible moves that you would not have seen, you can say, by looking at a game in progress, " the black side has a better position than the white side". That is that sort of static evaluation that must be learnt to the program.
This static evaluation is easier to explain than dynamic evaluation.
But it is a less " mathematical ", because it is made of very subjective methods (just like your appreciation of a position can be discussed by your neighbor). It can be compared to a strategic " vision " of the position.
I will begin the explanation by the static evaluation, easier to explain.
The static evaluation
That is a way of objectively quantifying the subjective impression that you can have by a glance on a position, without making an analysis of possibilities of development.
You made probably often this exercise, while looking over the shoulder of players trying to see which one has the best position.
The subjectivity of the this exercise undoubtedly appeared to you when your neighbor (who looked over the other shoulder) made a judgment very different of yours.
How can we program a computer, to make it say " black side has a better position than white side" (or the reverse) with only few risks of error?
Let us examine the criteria which we will take into account. They are of two kinds, often associated, the number of pieces and the position.
Let us analyze each one of these criteria:
1) - the difference of the number of pieces
That seems easy (you only have to count), but, there, raises the eternal question, often discussed in the bar (the one which lays just in front of the checkers club): how many men is the king worth ?
Of course, I let you the answer, but you must know that the programmers generally choose a value about three, often a little less than three at the beginning of the game, a little more than three at the end of the game (3 is for international, Russian, Spanish and pool rules ; for American checkers, it is very different, between 1.2 and 1.9 in function of other criterions ; in Italian game, it is very very different ; it is much more than 3 at beginning, less than 2 at the end).
2) - the position
The position is evaluated according to a few number of secondary criterions:
- the value of the occupied squares.
That is the problem of developing the occupation of the checkerboard squares according to the strategic importance that you think they have.
If you want that your computer plays a traditional game, it would be wise to privilege the bottom central square (square 3 in international 10x10 rules, if we suppose that the computer plays with the black pieces) as well as the central squares in thebeginning and the medium of the game (at the end of the game the things are different, of course).
In the same way, some "bad squares" must have "bad values" (square 5 in International 10x10 rules, 4 in Brazilian, Russian and pool, 6 in Canadian).
To make this evaluation, it is necessary to assign a value to each square, according to the importance that you think it have.
Then, the computer will look at the color of the piece laid on each square, and, if it plays with black pieces, it will add the values of the square if it is occupied by a black man, and it withdraws the value if it is occupied by a white man.
The value associated with the occupation by a white or a black piece is generally not the same one. For example in International 10x10, if computer is on black side, square 6 occupied by a black man will have a positive value of some points, while, occupied by a white man, it will have a very strong negative value, generally opposite of to the value of square 45 when it is occupied by a black man (which may be able to get a king quickly).
Like that, you will be able to privilege a type of game (traditional, or Roozenburg, or side game [difficult for a computer], etc...).
A good program will include several values, according to the type of the game (which it will be able to recognize according to the occupation or non occupation of some squares), but also according to the phase of the game (beginning, medium, end)
You can see it is very simple ; indeed, the selected values must respect two criteria:
* to be representative of the value of the position,
* to respect logical differences between squares corresponding to possible movements from one to the other one.
- formations
It is often interesting to give some additional points to the positions which allow some strong positions (arrows, ...) and which avoids, in the doubt, the weak position. The good program will take account all that.
You can also privilege the blocking of the adversary, but this is particularly difficult, because in the absence of human judgment, it is often difficult to say who blocks and who is blocked.
I suppose that you already understood that, if the good formations of the computer add points, those of the opponent will withdraw points.
- liberty
The principle is that, when you cannot look anymore in the future because it is too far, it is better to have a great number of possibilities of moves (that we call liberty), than a little number, because there will be then more choices, and thus more chances to find a good solution.
It will be necessary of course to try to decrease the liberty number of the opponent, but it should be noticed here that the analysis is not symmetrical. Indeed, one can speak about liberty number only for the player who has to move, because the liberty number of his opponent can be modified by the move of the first one.
In practice, this distinction is not always made, to make possible the comparison between positions where the player's turn is not the same.
- advance
This concept looks like the liberty, but it corresponds to an evaluation in number of moves, and not in space. A good player always prefers to be as near as possible as king line, but he also prefers to be sure that he can still play several moves before being obliged to exchange men, because it can break his position, or make him lose pieces.
It is thus advisable to check that our game leaves us sufficient moves in advance. This criterion is not always taken into account by the programs, for two reasons:
* it is specific to the checkers game, and principal research in programming was done for chess,
* it may be an absolute non-sense in some situations. For example when you have a classical central game with very few moves possible for each player, it may be better to be "late".
So, a lot of programers like better have an other evaluation, between liberty number and advance :
they count the number of empty squares in front of each man, before the contact with the opponent. That is a good way to evaluate both liberty number and advance.
- other
You can add other criterions to give a good avaluation of the position.
For example, you can give points if the men are grouped (that's of course better than if they are spread out), if they are empty corridors leading to king line, if there is weak side, etc...
I let you imagine other criterions, that will be better if the computer can evaluate them without long computations.
When the computer has made these evaluations, what does it with them ?
It mixes them, et gives a global value which lets it compare all the positions that it analyzed.
In some programs, it gives 2 values, one for the number of pieces to which it gives an absolute priority, and one for the other criterions. In that case, it must examine gambits through dynamic evaluation. My very old program, Dames 2020, has this sort of double value. But most of other programs (Among them Quidam and Windames series) use only one value, like the ches programs. So they add the 2 values, with appropriate factors, to have only one number. They often multiply the difference of pieces by 100 before adding the position evaluation ; but some ones use a multiplication by 1000 or even 100 000 (like Dam 2.2). That method has the advantage of letting the program use only 1 value instead of 2.
I think that you have now understood that all that is an alchemy, which lets a large place for programmers opinion.
But it may be interesting when you play against a program to try to find what the programmer thought to be important and to be not important, and then use these weak points.