
## 4.3 Alphabeta Pruning

One can note that it is not forcing useful to explore the branch in où measurement the score of this position to depth 1 is already with less good than that found in the branch In the same way the bran need does not have completely to be explored. As of the calculation of Q7, we obtain a score lower than that of (always completely explored). Calculates Q8 and Q9 will not be able to improve this situation even if their respective score is better than Q7. In a minimizing stage, the weakest score went up. Already is known that it will not bring anything again. The alternative alphabeta of the MiniMax  uses this pruning to decrease the number of branches to be explored. This reduction causes an increase in the performances in time and in space. With the alphabeta pruning, we generate only a number of nodes necessary to decide if each branch will bring us to a better value of that already exist.

## Algorithm Minimax Revisited 4.4

The MiniMax algorithm with alphabeta pruning is created for games with two players in which, after each turn the hand changes. By the specificity of the Kalah game, there is a rule which alows to keep the hand (replay again), then it was necessary to make modifications on this algorithm. In the traditional exploration tree, one makes the maximization of the wire values to the root (one wants the value the greatest value for the player MAX who is, by definition, that calls the algorithm. In the following level, one makes minimization because it is the turn of the adversary (player MIN . One continues thus while alternating until the end. In the play of Kalah, the problem comes from the fact, that by generating the depth tree of game, it is necessary to store the information which says if the player who made the last movement must replay or not. Alternation is not systematic any more, one looks at initially if that which has just played owes replay. In this case, if the player is the MAX, it will again be necessary to maximize in the following level. If not, it will be necessary to minimize. This modification implies that alphabeta pruning cannot be bracket in all the cases. It will be able to apply it only in the following cases:
- One is in a node MAX and his/her father is MIN

## - One Is In A Node Min And His/Her Father Is Max

The reason is rather obvious. Indeed, let us consider the example of figure 3, First of all, one goes down, in-depth, by the first branch, when we go up, we obtain value 2 out of B, then in A,
like temporal value. Now, we go down by the second branch to the sheet, we go up -1, whatever the values which can be obtained they will not exceed -1 is thus will be always lower than 2. We can prune these branches, because they will not bring additional information.

Let us consider the case where the player MAX keep the hand, and suppose that the node C is of type MAX. A priori it is not known if one of wire of C will not be able to go up a higher value. They will thus have to be go through all. For example in figure 4, the last wire has value 5 and this one is finally the gone up value with A.

With this alternative that appears clear that one loses because each time that a player keep the hand, our algorithm generates more nodes and consequently, more time. But the nature of Kalah game does not make it possible to optimize more than what we did.

## 4.5 Levels Of Difficulty

In the program, we introduced four levels of difficulties which can be chosen by the user when it asks a play against the computer. More the selected level is more high, the difficulty increases