Здравствуйте дорогие друзья
MinMax есть основной переборный алгоритм поиска для 2х игроков. Он очень прост:
- 1. Мы получаем все ходы из данной позиции
- 2. Делаем по очереди все перемещения.
- 3. Оцениваем все позиции, полученные из исходной.
- 4. Запоминаем лучшую оценку и лучший ход.
- 5. Возвращаем лучшую оценку.
Основной неясный момент с функцией оценки – как она может точно оценить все промежуточные позиции в игре. До некоторой глубины поиска в качестве функции оценки используется вариант функции MinMax для оппонента. Затем вызывается функция статической оценки, приближенно подсчитываюшая все позиционные и материальные факторы.
Итак, нам нужно:
- 1. Функция MinMax для белых
- 2. Функция MinMax для черных
- 3. Оценочная функция
Вот, в принципе и все. Осталось сказать, что оценка берется разностная: все преимущества белых – все преимущества черных Этот алгоритм исследует все перемещения и общее кол-во узлов для глубины D и кол-ва перемещений в позиции N будет:
N^D
Рост дерева поиска носит экспоненциальный характер. Прошу запомнить этот очевидный, но такой неприятный факт.
Нашему Бени далеко до Ландау, поэтому подключим коллективный разум для решения задачи о неприкосновенном короле.
Подключайтесь к решению задачи.
Любые идеи приветствуются.
Файлы проекта (облако)