Алгоритм «минимакс» и его реализация на примере игры «крестики-нолики»

Авторы: Жданов Н.А., Бурханова Ю.М., Воронецкий Ю.О.
Опубликовано в выпуске: #5(34)/2019
DOI: 10.18698/2541-8009-2019-5-482
Раздел: Информатика, вычислительная техника и управление | Рубрика: Системный анализ, управление и обработка информации, статистика
Ключевые слова: алгоритм «минимакс», метод «альфа-бета отсечение», рекурсия, оценочная функция, Python, «крестики-нолики», максимизация, минимизация, метод ветвей и границ
Опубликовано: 06.06.2019

В настоящее время машинное обучение представляет собой актуальное и стремительно развивающееся направление в области информационных технологий, поскольку нынешнее аппаратное обеспечение обладает высокой эффективностью, необходимой для решения подобных задач. Цель машинного обучения — создание искусственного интеллекта, способного самостоятельно принимать решения, но на данном этапе развития технологии главное — автоматизировать процесс принятия решений человеком. В рамках данной статьи исследован и реализован алгоритм, способный принимать оптимальные решения для выбора хода в игре «крестики-нолики», а также представлен метод оптимизации полученного решения.
Результаты работы алгоритма предоставлены и проанализированы.

Литература

[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: веб-сайт. URL: https://www.neverstopbuilding.com/blog/minimax (дата обращения: 10.02.2019).

[4] Jain Sh. The ultimate beginners guide to analysis of algorithm. codeburst.io: веб-сайт. URL: https://codeburst.io/the-ultimate-beginners-guide-to-analysis-of-algorithm-b8d32aa909c5 (дата обращения: 10.02.2019).

[5] Turney K. Recursion is not hard: a step-by-step walkthrough of this useful programming technique. medium.freecodecamp.org: веб-сайт. URL: https://medium.freecodecamp.org/recursion-is-not-hard-858a48830d83 (дата обращения: 05.02.2019).

[6] Introduction to Minimax algorithm. baeldung.com: веб-сайт. URL: https://www.baeldung.com/java-minimax-algorithm (дата обращения: 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: веб-сайт. URL: https://www.hackerearth.com/blog/artificial-intelligence/minimax-algorithm-alpha-beta-pruning/ (дата обращения: 14.02.2019).

[10] Alpha-Beta. chessprogramming.org: веб-сайт. URL: https://www.chessprogramming.org/Alpha-Beta (дата обращения: 18.02.2019).