Investigating the Performance of Minimax Search and Aggregate Mahalanobis Distance Function in Evolving an Ayo/Awale Player

Authors: Randle O. A., Olugbara, O. O., Lall M.

Abstract:

In this paper we describe a hybrid technique of Minimax search and aggregate Mahalanobis distance function synthesis to evolve Awale game player. The hybrid technique helps to suggest a move in a short amount of time without looking into endgame database. However, the effectiveness of the technique is heavily dependent on the training dataset of the Awale strategies utilized. The evolved player was tested against Awale shareware program and the result is appealing.

Keywords: Minimax Search, Mahalanobis Distance, Strategic Game, Awale

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1334147

References:

[1] Donkers, H.H.L.M., Uiterwijk, J.W.H.M. and Voogt, A.J.D.V., Mancala Games- Topics in Artificial Intelligence and Mathematics. Step by Step Proceedings of the 4th Colloquium Board Games in Academia, (eds. J. Retschitzki and R. Haddad-Zubel). Editions Universitaires, Frbourg, Switseland, pp 133-146, 2002.
[2] Romein, J.W. and Bal, H.E., Notes Awari is Solved, Journal of the ICGA, vol. 25, pp. 162-165, 2002.
[3] Knuth, D.E. and Moore, R.W., An Analysis of Alpha-beta Pruning, Artificial Intelligence 6, 4, 293-326, 1975.
[4] Thompson, K., Computer Chess Strength, in Advances in Computer Chess 3, M.Clarke (ed.), Pergamon Press, Oxford, pp. 55-56, 1982.
[5] Thomson, K., 6-piece Endgames, ICCA Journal, vol. 19, no. 4, pp. 215- 226, 1996.
[6] Hamilton, S. and Garber, L., Deep Blue's hardware-software synergy, IEEE Computer, 30, 10, pp. 29-35, 1997.
[7] Allis, V., Muellen, M. V.D. and Herik, J.V.D, Proof-number Search, Artificial Intelligence, vol. 66, pp. 91-124, 1994.
[8] Lincke, T.R and Marzetta, A., Large endgame databases with Limited Memory Space. ICGA Journal, 23, 3, pp. 131-138, 2000.
[9] Thomson, K., Retrograde Analysis of Certain Endgames, ICCA Journal, vol. 9, no. 3, pp. 131-139, 1986.
[10] Lincke, T.R., Strategies for the Automatic Construction of Opening Books: Computers and Games, pp. 74-86, 2000.
[11] Davis, J.E. and Kendall, G., An Investigation, using co-evolution, to evolve an Awari Player. In proceedings of Congress on Evolutionary Computation (CEC 2002), pp. 1408-1413, 2002.
[12] Daoud, M., Kharma, N., Haidar, A. and Popoola, J., Ayo, the Awari Player, or How Better Representation Trumps Deeper Search, Proceedings of the 2004 IEEE Congress on Evolutionary Computation, pp. 1001-1006, 2004.
[13] Rijswijck, J.V.D., Learning from Perfection: A Data Mining Approach to Evaluation Function in Awari. In proceedings of the 2nd International Conference (CG-00), vol. 2063, pp. 115-132, 2001.
[14] Olugbara., O.O.,Adewoye, T.O and Akinyemi, I.O. An Investigation of Minimax Search technique for Evolving Ayo/Awari Player. Proceedings of IEEE-ICICT 4th International Conference on Information and Communication Technology, Cairo, Egypt, 2006.
[15] Olugbara, O.O., Adigun, M.O., Ojo, S .O. and Adewoye, T.O., An efficient heuristic for evolving an agent in the strategy game of Ayo, ICGA Journal, 30, 92-96, 2007.
[16] Bruin, A.D., Pijls, W. and Plaat, A. Solution Trees as a Basic for Game Tree Search, ICCA Journal, 17(4), pp. 207-219, 1994.
[17] Pijls, W. and Bruin,A.D, Game Tree Algorithms and Solution Tree, theor.Compt.Sci., 252 (1-20:pp. 197-215, 2001).
[18] Pijls, W. and Bruin, A.D., Game Tree Algorithms and Solution Trees, theor.Compt. Sci., 252 (1-20: pp. 197-215, 2001.
[19] Iyegun, C. and Ben-Isreal, A., Probabilistic Distance Clustering Adjusted for Cluster Size. Probability in the Engineering and Informational Sciences, 22, 603-621, 2008.
[20] Jain, A.K., Murty, M.N., Flynn, P.J., 1999. Data clustering: a review. ACM Comput. Surveys 31 (3), 264-323.
[21] Bradley, P., Fayyad, U., Reina, C., 1998. Scaling clustering algorithms to large databases. In: The Fourth International Conference on Knowledge Discovery and Data Mining, AAAI, NY.
[22] Mahalanobis, P.C., On the generalized distance in statistics. Proceedings of the national Institute of Science of India, pp. 49- 55, 1936.
[23] Maesschalck, D. R., Jouan-Rimbaud, D., massart, D.L., The Mahalanobis distance. Chemometrics and Intelligent Laboratory Systems, 50, pp. 1-18, 2000.
[24] Broline, D.M. and Loeb, D.E., The Combinatorics of Mancala-type games: Ayo, Tchoukaillon and 1/¤Ç, http:/www.arxiv.org/ps_cache/math/.pdf/9502/95022225.pdf,, 1995.
[25] Adewoye, T.O., On Certain Combinatorial Number Theoretic Aspects of the African Game of Ayo. AMSE REVIEW, 14( 2), pp. 41-63, 1990.
[26] Myraid software, http://www.myraid-online.com/awale.htm.