Программа представляет из себя визуализацию алгоритма Minimax на дереве поиска. Данный проект упрощает понимание работы алгоритма Minimax c методом Альфа-Бета отсечений.
Minimax - это алгоритм принятия решений, используемый в теории игр и ИИ. Он помогает определить оптимальный ход игрока в двухпользовательской игре, рассматривая все возможные исходы игры.
Работа минимакса заключается в рекурсивной оценке всех возможных ходов, которые могут сделать текущий игрок и игрок-соперник. Алгоритм начинается с корня дерева игры и применяет minimax к каждому дочернему узлу. На каждом уровне дерева алгоритм чередует минимизациюю с максимизацией.
Основная идея метода состоит в сравнении наилучших оценок, полученных для полностью изученных ветвей, с наилучшими предполагаемыми оценками для оставшихся ветвей. Можно показать, что при определенных условиях некоторые вычисления являются лишними. В отличие от метода минимакса, который заключается в построении пространства ходов путем их прямого перебора, в методе отсечений значительная часть ходов подвергается неявному перебору, проводимому с помощью процедуры отбрасывания частей дерева.
Реализация алгоритма минимакса основана на алгоритме DFS, т.е. мы проходим дерево в глубину, рекурсивно обрабатывая каждый узел.
Альфа-бета отсечение - это метод оптимизации алгоритма minimax, который позволяет игнорировать некоторые ветви в дереве поиска. Это позволяет намного глубже оценить дерево поиска, используя те же ресурсы. Это метод оптимизации, который позволяет отсекать те ветви дерева поиска, где гарантировано будут невыгодные ходы (хуже всех уже найденных)
альфа - наилучшее значение, которое игрок MAX может гарантировать на текущем уровне или выше.
бета - наилучшее значение, которое игрок MIN может гарантировать на текущем уровне или выше.
