Лабораторная работа № 29 (к § 60) Построение стратегии на основе оценочной функции

Определения и обозначения

Оценочная функция — правило, которое по текущему состоянию игры вычисляет числовую оценку его выгодности для выбранного игрока. Чем больше число, тем предпочтительнее позиция, если именно так задан смысл функции. Она нужна, чтобы сравнивать варианты хода не только по названию, но и по измеримому критерию.

Игровая позиция — состояние игры, определяемое расположением объектов и другими условиями, важными для выбора хода. Например, это могут быть клетки игрового поля, количество ресурсов и очередь хода. Позиция нужна программе как точное описание ситуации, по которому можно получить дальнейшие действия.

Ход — допустимое действие игрока, переводящее игру из одной позиции в другую. Допустимость означает, что действие не нарушает правила игры. Перечень ходов позволяет стратегии выбрать только реальные варианты, а не произвольные изменения позиции.

Стратегия на основе оценочной функции — способ выбирать ход, сравнивая оценки позиций, к которым приводят возможные ходы. Сначала программа получает список действий, затем оценивает их последствия. Такая стратегия нужна, когда полный расчёт всей партии слишком сложен.

Как это устроено

Сначала точно задают правила игры и способ представления позиции. В описании должны быть видны расположение объектов, игрок, которому принадлежит ход, и условия окончания партии. Это необходимо потому, что без однозначной позиции нельзя надёжно определить допустимые действия и проверить, завершилась ли игра.

Оценочную функцию выбирают из цели конкретного игрока. Если нужно сохранить больше ресурсов, приблизиться к победе или ограничить соперника, эти свойства включают в расчёт. Более выгодным позициям присваивают большие значения, а проигрышным и опасным — меньшие, чтобы сравнение действительно помогало выбирать действие.

Для каждого допустимого хода строят новую позицию и вычисляют её оценку. Затем полученные числа сравнивают между собой, например выбирают максимальное значение. Оценивают именно результат действия, потому что положение до хода одинаково для всех рассматриваемых вариантов и не показывает, какой из них лучше.

Одного собственного хода часто недостаточно для разумной стратегии. Для каждого варианта рассматривают возможные ответы соперника и предполагают, что он выберет наиболее невыгодный для нас. Поэтому среди ответов берут худшую оценку, а затем выбирают такой собственный ход, у которого эта худшая оценка выше, чем у альтернатив.

После создания стратегии её проверяют на разных начальных позициях и партиях. Одна функция может хорошо работать в простых ситуациях, но ошибаться там, где важны отдалённые последствия или особая структура поля. Серия испытаний помогает сравнить число побед, поражений и качество промежуточных позиций, а затем изменить саму функцию или глубину анализа.

Элементы построения стратегии на основе оценочной функции

Таблицу удобно читать сверху вниз: сначала описывают ситуацию, затем получают варианты и последствия. После этого к позициям применяют оценочную функцию и выбирают действие. Последняя строка показывает, подтверждается ли полезность выбранного правила на практике.

Разбор задач

Задача 1

Условие: для заданной позиции нужно перечислить все допустимые ходы, получить позиции после каждого хода и выбрать ход с наибольшей оценкой. Обозначим варианты как A, B и C, а оценки результатов — E(A), E(B) и E(C). Числовые значения должны быть вычислены одной и той же оценочной функцией.

1. Опишите исходную позицию и выпишите только разрешённые правилами ходы.
2. Последовательно примените каждый ход, чтобы получить позиции A, B и C.
3. Вычислите оценки E(A), E(B) и E(C), затем сравните их.
4. Выберите вариант с максимальной оценкой, если функция задана с точки зрения текущего игрока.

Ответ: выбирается ход, для которого значение оценочной функции максимально. Если два результата равны, применяют дополнительное правило или выбирают любой из равных вариантов.

Задача 2

Условие: в позиции доступны два хода, A и B. Для каждого нужно определить ответы соперника и выбрать ход, при котором худшая для нас оценка лучше. Пусть после A соперник может создать оценки 4 и 1, а после B — оценки 3 и 2.

1. Для хода A найдите худший для нас ответ: min(4, 1) = 1.
2. Для хода B аналогично определите худший результат: min(3, 2) = 2.
3. Сравните худшие исходы: 2 больше 1, поэтому ход B лучше защищён от ответа соперника.

Ответ: следует выбрать ход B. Он не гарантирует самый высокий возможный результат, но его неблагоприятный исход оценивается выше, чем худший исход хода A.

Задача 3

Условие: нужно сравнить две оценочные функции на нескольких начальных позициях одной игры и выяснить, какая чаще приводит к победе или выгодным положениям. Одной партии недостаточно, поскольку её результат может зависеть от случайного расположения объектов или первого хода.

1. Подберите одинаковый набор начальных позиций и запустите обе стратегии в одинаковых условиях.
2. Для каждой функции запишите победы, поражения, ничьи и среднюю оценку позиции после хода.
3. Сравните результаты по всей серии, а не по отдельному случаю.
4. Проверьте позиции, где функции дали разные решения, чтобы понять причину различий.

Ответ: лучше считается функция, которая в серии чаще приводит к победе или к устойчиво более выгодным позициям. Вывод нужно подтверждать повторными испытаниями на разнообразных исходных данных.

Типичные ошибки

Считать, что большая оценка выгодна обоим игрокам. Так происходит, когда забывают, для кого определён знак числа. Проверьте функцию на очевидно выигрышной позиции каждого игрока и убедитесь, что оценки меняют смысл относительно выбранной стороны.

Выбирать ход по оценке позиции до хода. Исходная позиция одинакова для всех вариантов, поэтому такое сравнение ничего не решает. Проверьте, что программа сначала применяет каждый ход, а затем оценивает полученный результат.

Игнорировать ответы соперника. Быстрый выигрыш на первом шаге может исчезнуть после обязательного ответного действия. Проверьте для каждого кандидата хотя бы самые сильные ответы соперника и сравните худшие исходы.

Проверять стратегию только на одной партии. Удачный результат может оказаться случайностью и не отражать качество функции. Запустите серию на разных позициях и сопоставьте статистику побед, поражений и ничьих.

Связь с другими темами

До этой работы нужно уметь формально описывать правила игры, позиции и допустимые действия. В программе понадобятся условные конструкции для проверки правил и циклы для перебора вариантов. Без такого описания оценочная функция не сможет получать одинаково интерпретируемые данные.

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

Что запомнить

• Оценочная функция присваивает игровой позиции числовую оценку.
• Смысл оценок задают относительно выбранного игрока.
• Стратегия сравнивает позиции, возникающие после допустимых ходов.
• При выборе хода важно учитывать возможные ответы соперника.
• Оценочная функция служит приближённым критерием выгодности позиции.
• Качество стратегии проверяют на разных позициях и партиях.