Элементы теории игр: Деревья решений и минимаксный алгоритм
Теория игр — это раздел математики, изучающий оптимальные стратегии в ситуациях конфликта интересов. В то время как экономическая теория игр изучает непрерывные вероятностные модели (равновесие Нэша, дилемма заключенного), в дискретной математике и искусственном интеллекте акцент делается на комбинаторные игры с полной информацией. Шахматы, шашки, крестики-нолики — все эти игры поддаются строгому математическому анализу через построение деревьев решений.
Комбинаторная игра с полной информацией характеризуется тем, что в ней нет элемента случайности (как бросок кубиков), оба игрока видят все состояние системы, и игра обязательно заканчивается выигрышем, проигрышем или ничьей. Математически такая игра представляется в виде ориентированного дерева.
Дерево игры — это граф, где корень представляет текущую позицию на доске. От корня отходят ребра к вершинам-потомкам, которые представляют все возможные легальные ходы первого игрока. От этих вершин отходят ходы второго игрока, и так далее до достижения терминальных (конечных) состояний. Терминальным вершинам присваивается математическая оценка: например, +1 (победа первого), -1 (победа второго), 0 (ничья).
Для нахождения идеальной стратегии в таком дереве применяется алгоритм Минимакс (Minimax). Его логика опирается на предположение, что оба противника играют идеально. Первый игрок (Максимизатор) всегда выбирает ход, который ведет к ветке с максимально возможной оценкой. Второй игрок (Минимизатор) всегда выбирает ход, ведущий к минимальной оценке. Алгоритм рекурсивно спускается до листьев дерева, а затем поднимает оценки наверх, вычисляя математически гарантированный исход игры при текущей доске.
Проблема минимакса заключается в комбинаторном взрыве: для шахмат количество узлов в дереве игры превышает число атомов во вселенной (число Шеннона), поэтому просчитать игру до конца невозможно. Для решения этой проблемы программисты ограничивают глубину поиска, применяя эвристические функции оценки позиции, и используют альфа-бета отсечение (Alpha-Beta Pruning).
Альфа-бета отсечение — это математическая оптимизация минимакса. Если алгоритм видит, что какая-то ветвь гарантированно хуже для текущего игрока, чем ранее найденный вариант, он просто перестает исследовать эту ветвь (отсекает её). Это не меняет итоговый результат, но позволяет программам вроде Stockfish анализировать в два раза большую глубину за то же время, делая современные шахматные движки непобедимыми для человека.
