Investigating the Performance of Minimax Search and Aggregate Mahalanobis Distance Function in Evolving an Ayo/Awale Player
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:56707", author = "Randle O. A. and Olugbara and O. O. and Lall M.", title = "Investigating the Performance of Minimax Search and Aggregate Mahalanobis Distance Function in Evolving an Ayo/Awale Player", 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", volume = "6", number = "8", pages = "1002-4", }
