The preliminary prunings
The alpha-beta method allows substantial savings in calculations, but we can go further.
We will examine several types of preliminary prunings, i.e. prunings used before any evaluation in the branch.
- obviously useless sacrifices
When you play, there is a certain number of solutions which you eliminate quickly (sometimes unconsciously) because they are obviously too expensive. Let us try “to explain" to the computer this way of thinking.
We must make it eliminate a solution when it realizes that this solution leads to give or to lose pieces without any hope to recover them in the short term. It is necessary of course to differentiate this case from the gift of piece which constitute initial phases of a shot. The computer can make this distinction : as long as the player gives pieces and that its opponent must capture, or has only one number limited of moves to play (1 or 2), there is a possibility of shot or forced moves.
As soon as the opponent has a higher number of answers possible (more than 2 without capture), it is probably not a possible shot, and all the pieces which were lost until are definitively lost.
You will notice that I used some precautions there, and that I take refuge behind probabilities. Indeed, we are not any more in logical certainty but in empirical reasoning, i.e. founded on the experiment (the heuristics). Moreover, this reasoning presents, I am conscious of that, a certain number of faults, including two significant ones :
the possibility of a gambit, which lets us expect a later profit,
the possibility of giving pieces without immediate profit but which allows, in a future higher than the one that the computer can study, a passage to king line.
These two difficulties can be reduced (but not completely canceled) by fixing rather high the bar of the useless sacrifice (3 men for example, the gambit of more than 3 men being exceptional, and paying more than 3 men to go to king line being generally too much expensive, except perhaps at the end of the game).
You can also fix a lower usual bar, which grows up when the opponent is close to the king line, on the condition of knowing how to determine this “distance” to king line in a reliable way ( a double or triple jump may change things).
Let us notice that these algorithms must be neutralized at the end of the part, if not, the king being worth approximately 3 men, the computer will never plan to give two or three kings to capture the opponent's king after a rest period (blocking in the large diagonal or in the double corner).
- too open solutions
We are there still in dubious fields, which exploit more the probabilities and the experiment that logical unstoppable (still heuristics).
Imagine that, on a level N of the investigation of the possible futures, the opponent has the choice between 2 solutions. The first authorizes 4 answers of the computer, followed each one by 4 answers of the opponent, each one followed by 4 possibilities. The second solution authorizes 20 answers, followed each one by 20 answers of the opponent, and each one followed by 20 possibilities.
If the final evaluations are equivalent in each case, there is a chance on 4x4x4, or a chance out of 64, that one of the solutions is chosen by the opponent.
On the other hand, if it takes the second solution, there is only one chance out of 1000 that each one is chosen.
The computer will thus have spent a time 15 times higher to examine solutions 15 times less probable.
We can deduce from this that, more the tree of the possibilities is narrow, more the probability of detecting the path that will be selected increases. In the opposite, more it the tree is wide, more each solution is not very probable, but more it is probable that, when you will be in this direction, you be able to find a suitable solution, since the possibilities are more numerous.
So, we will examine each solution further in a narrow tree (since it is more probable), or (it is equivalent, but more shocking when I say that) limit the computing in a wide tree. The criterion of pruning can be, for example, the multiplication on each level of the number of viable branches. If you cut at 10 million, we will be able to examine 7 levels of average width 10, or 13 levels of average width 6 (in fact we will not examine all the branches, taking into account the application of the alpha-beta method and other preliminary prunings).
This method, theoretically not very satisfactory because it can let us avoid interesting possibilities at high levels, makes nevertheless save an appreciable time, with a limited risk. It is obviously not contradictory with the valorization of the liberty, but can be complementary. This method, used by Dames 2020, was described little in the literature up to now, perhaps because it is not adapted to the other games like chess.
- focused search
This method consists in making an exhaustive search up to a certain level, then to keep only 80% or 90% of the solutions (the best ones), then, at the higher level to still focus on 80% or 90%, etc...
The drawback of this method is that, if the best solutions on a level N often remain the best ones on the level N+1, it is not systematically true, and in the 10% or 20% which remain, there can be a hidden way that the opponent will choose, and which is, precisely, the one which will hurt us.
You have understood that I dislike this method and I prefer the pruning in the too open solutions, which appears better adapted.
- already examined solutions
We are there in a more mathematical concept !.
You undoubtedly understood what precedes that the dynamic evaluation studies moves, whereas the static evaluation studies positions. However, different sequences of moves can lead to identical positions. For example, following moves in International checkers :
1) 33-28, 18-23 2) 31-26, 16-21
or 1) 31-26, 18-23 2) 33-28, 16-21
or 1) 31-26, 16-21 2) 33-28, 18-23
or 1) 33-28, 16-21 2) 31-26, 18-23
lead, on level 4, i.e. at the end of two complete moves, exactly to the same position.
So, we must try to detect if the position studied has already been met, which makes possible to allot already calculated characteristics to it, and to prune all the branches starting from it.
To get a benefit from this characteristic, it will be interesting to memorize the studied positions, and to compare each new position with these ones. There is of course an optimum in the number of positions to memorize, because, beyond a certain number, he is faster to re-study the complete branch than to compare each position with the 10 or 20 thousand others already memorized. To help us in this approach, the checkers has a significant characteristic (which is not in chess), its one-way character. That means that a given position can be found only at a given level, and not before nor after since the men must advance and cannot move back (I simplify, by not considering the movement of the kings, who, indeed, destroyed this unidirectionnality, but I only risk to study several times some positions where the kings went up and down).
Thus, the example considered above gives a position which is reach in 4 levels (2 moves), but impossible to obtain in 3 or 5 levels. So, it will be interesting to use this characteristic by storing the positions studied by level, which limits the volume of the comparisons.