Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon openaccess Randomised fast no-loss expert system to play tic-tac-toe like a human

This study introduces a blazingly fast, no-loss expert system for tic-tac-toe using decision trees called T3DT, which tries to emulate human gameplay as closely as possible. It does not make use of any brute force, minimax, or evolutionary techniques, but is still always unbeatable. To make the gameplay more human-like, randomisation is prioritised and T3DT randomly chooses one of the multiple optimal moves at each step. Since it does not need to analyse the complete game tree at any point, T3DT is exceptionally faster than any brute force or minimax algorithm, this has been shown theoretically as well as empirically from clock-time analyses in this study. T3DT also does not need the data sets or the time to train an evolutionary model, making it a practical no-loss approach to play tic-tac-toe.

References

    1. 1)
      • 47. Karamchandani, S., Gandhi, P., Pawar, O., et al: ‘A simple algorithm for designing an artificial intelligence based tic tac toe game’. 2015 Int. Conf. on Pervasive Computing Advance Communication Technology Applied Society (ICPC 2015), Pune, India, 2015, vol. 00, no. c, pp. 14.
    2. 2)
      • 33. Diderich, C.G., Gengler, M.: ‘Minimax game tree searching minimax game tree searching’, in Floudas, C.A., Pardalos, P.M. (Eds.): ‘Encyclopedia of optimization’ (Springer, USA, 2009), pp. 20792087.
    3. 3)
      • 50. Sriram, S., Vijayarangan, R., Raghuraman, S., et al: ‘Implementing a no-loss state in the game of tic-tac-toe using a customized decision tree algorithm’. 2009 IEEE Int. Conf. on Information Automation (ICIA 2009), Zhuhai/Macau, China, 2009, pp. 12111216.
    4. 4)
      • 4. Shannon, C.E.: ‘XXII. Programming a computer for playing chess’, London, Edinburgh, Dublin Philos. Mag. J. Sci., 1950, 41, (314), pp. 256275.
    5. 5)
      • 9. Baudet, G.M.: ‘On the branching factor of the alpha–beta pruning algorithm’, Artif. Intell., 1978, 10, (2), pp. 173199.
    6. 6)
      • 24. Russell, S., Wefald, E.: ‘On optimal game-tree search using rational meta-reasoning’. 11th Int. Joint Conf. on Artificial Intelligence, 1989, pp. 334340.
    7. 7)
      • 31. Ahmed, A., Abdel, M., Gadallah, M., et al: ‘A comparative study of game tree searching methods’, Int. J. Adv. Comput. Sci. Appl., 2014, 5, (5), pp. 6877.
    8. 8)
      • 22. McAllester, D.A.: ‘Conspiracy numbers for min-max search’, Artif. Intell., 1988, 35, (3), pp. 287310.
    9. 9)
      • 32. Campbell, M.S., Marsland, T.A.: ‘A comparison of minimax tree search algorithms’, Artif. Intell., 1983, 20, (4), pp. 347367.
    10. 10)
      • 8. Darwish, N.M.: ‘A quantitative analysis of the alpha–beta pruning algorithm’, Artif. Intell., 1983, 21, (4), pp. 405433.
    11. 11)
      • 20. Berliner, H.J., McConnell, C.: ‘B∗ probability based search’, Artif. Intell., 1996, 86, (1), pp. 97156.
    12. 12)
      • 37. Chellapilla, K., Fogel, D.B.: ‘Evolution, neural networks, games, and intelligence’, Proc. IEEE, 1999, 87, (9), pp. 14711496.
    13. 13)
      • 36. Fogel, D.B.: ‘Using evolutionary programming to create neural networks that are capable of playing tic-tac-toe’. IEEE Int. Conf. on Neural Networks – Conf. Proc., San Francisco, CA, USA., 1993, pp. 875880.
    14. 14)
      • 18. Kaindl, H., Shams, R., Horacek, H.: ‘Minimax search algorithms with and without aspiration windows’, IEEE Trans. Pattern Anal. Mach. Intell., 1991, 13, (12), pp. 12251235.
    15. 15)
      • 52. Ayock, R.: ‘How to win at tic-tac-toe’, 2002.
    16. 16)
      • 30. Li, L., Liu, H., Wang, H., et al: ‘A parallel algorithm for game tree search using GPGPU’, IEEE Trans. Parallel Distrib. Syst., 2015, 26, (8), pp. 21142127.
    17. 17)
      • 40. Yau, Y.J., Teo, J.: ‘An empirical comparison of non-adaptive, adaptive and self-adaptive co-evolution for evolving artificial neural network game players’. 2006 IEEE Conf. on Cybernetics and Intelligent Systems, Bangkok, Thailand, 2006, pp. 16.
    18. 18)
      • 15. Ibaraki, T., Katoh, Y.: ‘Searching minimax game trees under memory space constraint’, Ann. Math. Artif. Intell., 1990, 1, (1), pp. 141153.
    19. 19)
      • 25. Anantharaman, T., Campbell, M.S., Hsu, F.: ‘Singular extensions: adding selectivity to brute-force searching’, Artif. Intell., 1990, 43, (1), pp. 99109.
    20. 20)
      • 38. Hochmuth, G.: ‘On the genetic evolution of a perfect tic-tac-toe strategy’, Genet. Algorithms Genet. Program., 2003, pp. 7582.
    21. 21)
      • 10. Pearl, J.: ‘Scout: a simple game-searching algorithm with proven optimal properties’, in ‘AAAI 1980’, 1980.
    22. 22)
      • 39. Soedarmadji, E.: ‘Decentralized decision making in the game of tic-tac-toe’. 2006 IEEE Symp. on Computational Intelligence Games, Reno, NV, USA., 2006, vol. 6, pp. 3438.
    23. 23)
      • 44. Ling, S.S., Lam, H.K.: ‘Playing tic-tac-toe using genetic neural network with double transfer functions’, J. Intell. Learn. Syst. Appl., 2011, 3, pp. 3744.
    24. 24)
      • 19. Berliner, H.: ‘The B∗ tree search algorithm: a best-first proof procedure’, Artif. Intell., 1979, 12, (1), pp. 2340.
    25. 25)
      • 35. de Groot, A.D.: ‘Thought and choice in chess’ (Amsterdam University Press, Amsterdam, Netherlands, 2008).
    26. 26)
      • 49. Garg, S., Songara, D., Maheshwari, S.: ‘The winning strategy of tic tac toe game model by using theoretical computer science’. 2017 Int. Conf. on Computer, Communications and Electronics (COMPTELIX 2017), Jaipur, India, 2017, pp. 8995.
    27. 27)
      • 43. Mohammadi, H., Browne, N.P.A., Venetsanopoulos, A.N., et al: ‘Evolving tic-tac-toe playing algorithms using co-evolution, interactive fitness and genetic programming’, Int. J. Comput. Theory Eng., 2013, 5, (5), pp. 797801.
    28. 28)
      • 34. ‘Mathematical recreations, repository for mathematical diversions’. Available at http://www.mathrec.org/old/2002jan/solutions.html, accessed May 2019.
    29. 29)
      • 21. Rivest, R.L.: ‘Game tree searching by min/max approximation’, Artif. Intell., 1987, 34, (1), pp. 7796.
    30. 30)
      • 13. Roizen, I., Pearl, J.: ‘A minimax algorithm better than alpha–beta? Yes and no’, Artif. Intell., 1983, 21, (1–2), pp. 199220.
    31. 31)
      • 29. Marsland, T.A., Campbell, M.: ‘Parallel search of strongly ordered game trees’, ACM Comput. Surv., 2002, 14, (4), pp. 533551.
    32. 32)
      • 14. Plaat, A., Schaeffer, J., Pijls, W., et al: ‘SSS* = alpha–beta + TT’, December 1994.
    33. 33)
      • 27. Hyatt, R.M., Suter, B.W., Nelson, H.L.: ‘A parallel alpha/beta tree searching algorithm’, Parallel Comput., 1989, 10, (3), pp. 299308.
    34. 34)
      • 11. Reinefeld, A.: ‘An improvement to the scout tree search algorithm’, ICGA J., 1983, 6, (4), pp. 414.
    35. 35)
      • 3. Copeland, A.H.: ‘Book review: theory of games and economic behavior’, Bull. Am. Math. Soc., 2008, 37, (1), pp. 103104.
    36. 36)
      • 12. Stockman, G.C.: ‘A minimax algorithm better than alpha–beta?’, Artif. Intell., 1979, 12, (2), pp. 179196.
    37. 37)
      • 28. Borovska, P., Lazarova, M.: ‘Efficiency of parallel minimax algorithm for game tree search’. Proc. 2007 Int. Conf. on Computer Systems and Technologies, Rousse, Bulgaria, 2007, pp. 14:114:6.
    38. 38)
      • 51. Puzzleland: ‘Tic tac toe: 8 strategies to win every game’ (Puzzleland, 2016).
    39. 39)
      • 2. Kjeldsen, T.H.: ‘John von Neumann's conception of the minimax theorem: a journey through different mathematical contexts’, Arch. Hist. Exact Sci., 2001, 56, (1), pp. 3968.
    40. 40)
      • 45. Rajani, N.F., Dar, G., Biswas, R., et al: ‘Solution to the tic-tac-toe problem using hamming distance approach in a neural network’. Proc. 2011 2nd Int. Conf. on Intelligent System Modelling Simulation (ISMS 2011), Kuala Lumpur, Malaysia/Phnom Penh, Cambodia, 2011, no. 1, pp. 36.
    41. 41)
      • 16. Slagle, J.R., Dixon, J.E.: ‘Experiments with some programs that search game trees’, J. ACM, 1969, 16, (2), pp. 189207.
    42. 42)
      • 5. Plaat, A., Schaeffer, J., Pijls, W., et al: ‘Best-first fixed-depth minimax algorithms’, Artif. Intell., 1996, 87, (1), pp. 255293.
    43. 43)
      • 6. Korf, R.E., Chickering, D.M.: ‘Best-first minimax search’, Artif. Intell., 1996, 84, (1), pp. 299337.
    44. 44)
      • 53. Oracle: ‘Java™ platform, standard edition 8 API specification’. Available at https://docs.oracle.com/javase/8/docs/api/index.html, accessed April 2020.
    45. 45)
      • 17. Shams, R., Kaindl, H., Horacek, H.: ‘Using aspiration windows for minimax algorithms’. 12th Int. Joint Conf. on Artificial Intelligence, vol. 1, Sydney, Australia, 1991, pp. 192197.
    46. 46)
      • 26. Björnsson, Y., Marsland, T.A.: ‘Risk management in game-tree pruning’, Inf. Sci., 2000, 122, (1), pp. 2341.
    47. 47)
      • 46. Singh, A., Deep, K., Nagar, A.: ‘A ‘never-loose’ strategy to play the game of tic-tac-toe’. Proc. 2014 Int. Conf. on Soft Computing Machine Intelligence (ISCMI 2014), New Delhi, India, 2014, pp. 15.
    48. 48)
      • 7. Knuth, D.E., Moore, R.W.: ‘An analysis of alpha-beta pruning’, Artif. Intell., 1975, 6, pp. 293326.
    49. 49)
      • 23. Lister, L., Schaeffer, J.: ‘An analysis of the conspiracy numbers algorithm’, Comput. Math. Appl., 1994, 27, (1), pp. 4164.
    50. 50)
      • 41. Yau, Y.J., Teo, J., Anthony, P.: ‘Pareto evolution and co-evolution in cognitive neural agents synthesis for tic-tac-toe’. Proc. 2007 IEEE Symp. on Computational Intelligence Games (CIG 2007), Honolulu, HI, USA., 2007, pp. 304311.
    51. 51)
      • 1. Neumann, J. v.: ‘Zur theorie der gesellschaftsspiele’, Math. Ann., 1928, 100, (1), pp. 295320.
    52. 52)
      • 48. Garg, S., Songara, D.: ‘The winner decision model of tic tac toe game by using multi-tape turing machine’. 2016 Int. Conf. on Advances Computing Communications and Informatics (ICACCI 2016), Jaipur, India, 2016, pp. 573579.
    53. 53)
      • 42. Bhatt, A., Varshney, P., Deb, K.: ‘In search of no-loss strategies for the game of tic-tac-toe using a customized genetic algorithm’. Genetic and Evolutionary Computation Conf. (GECCO 2008), Atlanta, GA, USA., 2008, pp. 889896.
http://iet.metastore.ingenta.com/content/journals/10.1049/ccs.2020.0018
Loading

Related content

content/journals/10.1049/ccs.2020.0018
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address