Bhatt, Anurag ; Varshney, Pratul ; Deb, Kalyanmoy (2008) In search of no-loss strategies for the game of Tic-tac-toe using a customized genetic algorithm Proceedings of Genetic and Evolutionary Computation conference (GECCO-2008), (Atlanta, USA) . pp. 889-896.
![]()
|
PDF
- Publisher Version
1MB |
Official URL: http://dl.acm.org/citation.cfm?id=1389269
Related URL: http://dx.doi.org/10.1145/1389095.1389269
Abstract
The game of Tic-tac-toe is one of the most commonly known games. This game does not allow one to win all the time and a significant proportion of games played results in a draw. Thus, the best a player can hope is to not lose the game. This study is aimed at evolving a number of no-loss strategies using genetic algorithms and comparing them with existing methodologies. To efficiently evolve no-loss strategies, we have developed innovative ways of representing and evaluating a solution, initializing the GA population, developing GA operators including an elite preserving scheme. Interestingly, our GA implementation is able to find more than 72 thousands no-loss strategies for playing the game. Moreover, an analysis of these solutions has given us insights about how to play the game to not lose it. Based on this experience, we have developed specialized efficient strategies having a high win-to-draw ratio. The study and its results are interesting and can be encouraging for the techniques to be applied to other board games for finding efficient strategies.
Item Type: | Article |
---|---|
Source: | Copyright of this article belongs to Proceedings of Genetic and Evolutionary Computation conference (GECCO-2008), (Atlanta, USA). |
Keywords: | Tic-tac-toe; Evolutionary Games; Learning Strategies |
ID Code: | 81641 |
Deposited On: | 07 Feb 2012 06:10 |
Last Modified: | 18 May 2016 23:06 |
Repository Staff Only: item control page