DOI: 10.7763/IJCTE.2013.V5.799
Evolving Tic-Tac-Toe Playing Algorithms Using Co-Evolution, Interactive Fitness and Genetic Programming
Abstract—This paper presents a novel use of Genetic Programming, Co-Evolution and Interactive Fitness to evolve algorithms for the game of Tic-Tac-Toe. The selected tree-structured algorithms are evaluated based on a fitness-less double-game strategy and then compete against a human player. This paper will outline the evolution process which leads to producing the best Tic-Tac-Toe playing algorithm. The evolved algorithms have proven effective for playing against human opponents.
Index Terms—Co-evolution, game algorithms, genetic programming, interactive fitness, tic-tac-toe, tournament selection
H. Mohammadi is with the Electrical and Computer Engineering Department, University of Toronto, Ontario, Canada (e-mail: helia.mohammadi@utoronto.ca).
Nigel P. A. Browne was with the Computer Science Dept., Ryerson University, Toronto, Ontario, Canada (e-mail: nbrowne@acm.org).
Anastasios N. Venetsanopoulos is with the Department of Electrical and Computer Engineering, University of Toronto and also Department of Electrical Engineering, Ryerson University, Toronto, Ontario, Canada (e-mail: anv@comm.utoronto.ca).
Marcus V. dos Santos is with the Computer Science Dept., Ryerson University, Toronto, Ontario, Canada (e-mail: m3santos@ryerson.ca).
Cite:Helia Mohammadi, Nigel P. A. Browne, Anastasios N. Venetsanopoulos, and Marcus V. dos Santos, "Evolving Tic-Tac-Toe Playing Algorithms Using Co-Evolution, Interactive Fitness and Genetic Programming," International Journal of Computer Theory and Engineering vol. 5, no. 5, pp. 797-801, 2013.