The minimax algorithm and its implementation on the example of the noughts-and-crosses game

Authors: Zhdanov N.A., Burkhanova Yu.M., Voronetskiy Yu.O.
Published in issue: #5(34)/2019
DOI: 10.18698/2541-8009-2019-5-482
Category: Informatics, Computer Engineering and Control | Chapter: System Analysis, Control, and Information Processing, Statistics
Keywords: minimax algorithm, alpha-beta clipping, recursion, evaluation function, Python, noughts-and-crosses, maximization, minimization, branch and bound method
Published: 06.06.2019

At present, machine learning is an actual and rapidly developing area in the field of information technologies, since the current hardware is highly efficient for solving such problems. The goal of machine learning is the creation of artificial intelligence capable of making decisions independently, but at this stage of technology development the main thing is to automate the decision-making process by humans. In this article, we investigated and implemented an algorithm capable of making optimal decisions for the choice of a move in a noughts-and-crosses game, and also presented a method for optimizing the solution obtained. The results of the algorithm are provided and analyzed.

References

[1] Pollice G., Selkow S., Heineman G.T. Algorithms in a nutshell. O’Reilly Media, 2008.

[2] Tadelis S. Game theory: an introduction. Princeton University Press, 2013.

[3] Tic Tac Toe: understanding the Minimax algorithm. neverstopbuilding.com: website. URL: https://www.neverstopbuilding.com/blog/minimax (accessed: 10.02.2019).

[4] Jain Sh. The ultimate beginners guide to analysis of algorithm. codeburst.io: website. URL: https://codeburst.io/the-ultimate-beginners-guide-to-analysis-of-algorithm-b8d32aa909c5 (accessed: 10.02.2019).

[5] Turney K. Recursion is not hard: a step-by-step walkthrough of this useful programming technique. medium.freecodecamp.org: website. URL: https://medium.freecodecamp.org/recursion-is-not-hard-858a48830d83 (accessed: 05.02.2019).

[6] Introduction to Minimax algorithm. baeldung.com: website. URL: https://www.baeldung.com/java-minimax-algorithm (accessed: 08.02.2019).

[7] Lutz M. Programming Python. O’Reilly Media, 2011.

[8] Lutz M. Learning Python: powerful object-oriented programming. O’Reilly Media, 2013.

[9] Jain R. Minimax algorithm with Alpha-beta pruning. www.hackerearth.com: website. URL: https://www.hackerearth.com/blog/artificial-intelligence/minimax-algorithm-alpha-beta-pruning/ (accessed: 14.02.2019).

[10] Alpha-Beta. chessprogramming.org: website. URL: https://www.chessprogramming.org/Alpha-Beta (accessed: 18.02.2019).