Минимальный перебор в игровых деревьях. Альфа - бета отсечения. Построение игровых программ Удалова Татьяна 85 М 21

Деревья решений Узел дерева – один шаг решения задачи Ветвь – решение, которое ведёт к более полному решению Листы – окончательное решение Цель : Найти « наилучший » путь от корня до листа. Проблема : Деревья решений обычно огромны

Игровые деревья Моделирование стратегических настольных игр ( крестики нолики ) Ветвь, выходящая из узла - ходы одного из игроков сценария развития игры [1]

Минимаксный перебор Минимизировать максимальное значение, которое может иметь позиция для противника после следующего хода Т. Е Ищем наименьшие потери из тех, которые нельзя предотвратить принимающему решения субъекту в наихудших для него обстоятельствах.

Крестики - нолики (1) 4 значения позиции поля : 4 – игрок выиграет 3 – ситуация не ясна 2 – ничья 1 – противник выиграет На основании заданных значений реализуется функция оценки состояния игры.

Крестики - нолики (2) Дерево игры крестики - нолики в конце партии [1] Игрок X минимизирует свои потери Игрок 0 максимизирует свой выигрыш 44

Альфа - бета отсечения (1) Оптимизация минимаксного перебора Сравнение наилучших оценок, полученных для полностью изученных ветвей, с наилучшими предполагаемыми оценками для оставшихся

Альфа - бета отсечения (2) Предположим, что z

Альфа - бета отсечения (4) Правила вычисления альфа - бета : у MAX вершины значение a равно наибольшему в данный момент значению среди окончательных возвращенных значений для ее дочерних вершин у MIN вершины значение b равно наименьшему в данный момент значению среди окончательных возвращенных значений для ее дочерних вершин

Альфа - бета отсечения (5) Правила прекращения поиска : можно не проводить поиска на поддереве, растущем из всякой MIN вершины, у которой значение b не превышает значения a всех ее родительских MAX вершин можно не проводить поиска на поддереве, растущем из всякой MAX вершины, у которой значение a не меньше значения b всех ее родительских MIN вершин

Альфа - бета отсечения (6) [2]

Программная реализация Игра крестики - нолики включающая в себя : Альфа - бета отсечения для расчёта следующего хода Возможность выбора глубины рекурсии при моделировании последующих ходов : Глубина рекурсии менее 5 ходов – приложение сопротивляется противнику Глубина более 5 ходов гарантирует конкурентоспособность приложения

Литература 1. Rod Stephens. Ready-to-run Delphi© Algorithms. Wiley Computer Publishing. 2. Интернет - Университет Информационных Технологий. Интеллектуальные робототехнические системы. Лекция : Методы поиска решений. Лекция : Методы поиска решений. 3. Википедия свободная энциклопедия. Альфа - бета отсечение. Альфа - бета отсечение. 4. Donald E. Knuth and Ronald W. Moor. Анализ альфа - бета отсечений. Перевод : Павел Н. Дубнер Анализ альфа - бета отсечений 5. Михаил Лопаткин. Минимаксный перебор в игровых деревьях. Зимняя студенческая школа - практикум « Высокопроизводительные вычисления » Нижегородский государственный университет, Intel

ВОПРОСЫ