and more the possibilities of gaining decreases. There is a direct correspondence between each one of the levels and the size of the exploration tree generated by the algorithm MiniMAx . The easy level corresponds to a tree of depth 2, the mean level with 4, the difficult level with 6 and the very difficult level with 8. We used a parameter which is used as coefficient. In our case this parameter is worth 2. We obtain levels of depth 2,4, 6 and 8. It can be changed, for example into 3, and in this case one obtains depths 3, 6, 9 and 12. However, it should not be forgotten that the number of nodes generated by the algorithm believes in an exponential way in each increase of a unit of level. For level 8, with 6 branches(game with 6 holes), the complete tree contains more than two billion nodes. For reason of response time of the machine, we decided not to go beyond. With eight levels, we obtain an acceptable response time.

## 4.6 Comparison Minimax And Our Algorithm

We measure the number of nodes generated by the exploration tree, instead of time, because, in this way, we will obtain a measurement which is always independent on the computer which serves the tests. For the algorithm without pruning alphabeta, the number of generated nodes is equal ∑ i=0 6 i . We tested with various states of the apron and various levels. The computed value is the number of nodes generated on average.  To measure the improvement, we give the percentage of nodes generated by our algorithm compared to the traditional one.

The improvement is very considerable especially with regard to the highest levels.

| Level   | traditional Minimax   | Our algorithm   | Percent age   |
|---------|-----------------------|-----------------|---------------|
| 40%     |                       |                 |               |
| 2       | 43                    | 17 2            |               |
| 4       | 1555                  | 26.4            | 15%           |
| 6       | 55987                 | 302 7           | 6%            |
| 8       | 2015539               | 4471,1          | 2%            |

## Conclusion

We used a universal algorithm, the MiniMax, that one uses for the games with two players. It is a question of creating a tree of a limited depth containing all possible blows for this depth. In exploring the tree, the machine can decide its next movement. The computing time to generate this tree posed a serious problem.  To reduce this computing time we implemented a more efficiency version of this algorithm. We limited ourselves to the presentation of our MiniMax algorithm without speaking about various implemented strategies.

## References

[1] E. Rich Intelligence Artificial. Ed. Masson 1987
[2] J.P. Delahaye. Outils logiques pour l'intelligence artificielle. Ed Eyrolles 1988
[3] Bruce Eckel Thinking in Java. Printice Hall Inc. 1988
[4] M. Fowler Refactoring : Improving the Design of Existing Code Addison-Wesley Sept 2000 [5]
J.L. Lauriere Intelligence Artificielle. Résolution de problèmes parl'homme et la machine.

Ed Eyrolles 1987.

## 5
