Моделирование и нестандартные алгоритмы выбора стратегий в недетерминированных антагонистических играх и родственных задачах

• Автор: Радионов, Алексей Николаевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Ульяновск
• Количество страниц: 112 с.

1. Введение

1.1. О программировании игр.

1.1.1. Шахматы.

1.1.2. короткие нарды.

2. Поиск оптимальной стратегии в дереве игры

2.1. Используемые понятия и определения.

2.2. Представление игры в виде дерева.

2.3. Метод минимакса

2.3.1. Построение динамических оценок в детерминированном случае

2.3.2. Построение динамических оценок в недетерминированном случае

3. Минимаксный алгоритм с функцией риска

3.1. Модель Шеннона
3.2. Оценочная функция
3.3. Функция риска .
4. Особенности финала в
4.1. Описания алгоритмов
. Анализ результатов.
5. Интерактивное моделирование дерева преобразований тригонометрических выражений
5.1. Основные понятия и определения.
5.2. Древовидное представление выражений
5.3. Построение Едерева и разбор Еслов
5.4. Интерактивное управление перебором.
5.4.1. Представление процесса перебора
5.4.2. Оценочная функция для выражений
5.4.3. Направленность программы.
6. Интерактивное моделирование дерева игры
6.1. Дерево допустимых ходов
6.2. Недостатки игровых программ
6.2.1. Отсутствие стратегии.
6.2.2. Эффект горизонта.
6.3. Постановка проблемы.
6.4. Проектирование системы.
6.5. Сценарий работы программы
6.6. Анализ результатов.
7. Заключение 4
шение задачи ,4 5, Му 5о, Я. Внутренность для задачи без циклов можно представить схемой на рисунке 1.2. Изображенный алгоритм представляет собой некоторое преобразование Я. На вход алгоритма подается ранг Ь позиции П 5, сама позиция П 5, возвращаемый параметр , в котором будет храниться сумма найденного решения и возвращаемый параметр Я , который представляет собой цепочку она будет заполнена найденным оптимальным решением2. Представленный на схеме алгоритм является рекурсивным так, на шаге 6, он производит вызов самого себя с новыми параметрами. Результатом работы этого алгоритма является максимальная сумма решения Я, а также само решение.
Однако для практических переборных задач часто невозможно рассмотреть все варианты решений. Поэтому для таких задач строятся модельные задачи, в которых модифицируется правило выбора М, а также функция предпочтения с целью уменьшения объема перебора. Таким образом задачу сокращения перебора можно решать подбирая функцию предпочтения рис. 1.1.
Наиболее подходящими для исследования такого вида переборных задач являются задачи игрового программирования. Программирование игр представляется интересным и само по себе. В процессе создания игровой программы возникают различные задачи, от качества решения которых зависит скорость работы алгоритма, его гибкость и возможность адаптации к другим задачам. Основной проблемой, возникающей перед разработчиками играющей программы, является проблема выбора оптимальной стратегии. Хорошо организованный перебор3 позволяет получать стратегии хорошего качества при сравнительно малой глубине перебора. Этому аспекту игрового про
2В шаге 1 схемы на рис. 1.2 они обозначены звездочками.
Фразу хорошо организованный перебор можно понимать и с точки зрении оптимизации кода программы. Но здесь больший акцепт делается именно на алгоритмическую оптимизацию перебора за счет попыток получить больше полезной информации об игровой позиции без дополнительного погружения в дерево игры.
грамм ирования, а также построению алгоритмов поиска близких к оптимальным решений задач с иерархическим перебором посвящена большая часть диссертации.
Вопрос о принципиальной возможности построения приемлемых моделей различных игр занимает много места в литературе. Вопрос этот может порождаться просто бытовым любопытством или же потребностью практического использования алгоритмов поиска игровых стратегий в решении сложных практических задач. Игровое моделирование всегда порождает вокруг себя множество споров. Например, попытки создать сильную шахматную программу когдато вызвали дискуссию о том, может ли компьютер в принципе хорошо играть в шахматы Достаточно ли для этого только вычислительных ресурсов Как успешно могут применяться жадные 6, 5 и др. с минимумом эвристик, алгоритмы поиска стратегий
В рамках этих вопросов в работе рассмотрены три варианта специальное усреднение промежуточных оценок в недетерминированных играх, человекоуправляемый перебор в аналитических вычислениях и при игре в шахматы построения алгоритмов поиска псевдооптимальных стратегий в некоторых играх и родственных переборных задачах, имеющих большое практическое значение. Все три направления объединяет одна общая задача задача выбора хорошего решения при имеющихся вычислительных ресурсах, чей недостаток влечет сокращение глубины анализа поставленной задачи игры, и, как следствие, неудовлетворительное качество решения.
Коротко о структуре этой работы
Введение


Но здесь больший акцепт делается именно на алгоритмическую оптимизацию перебора за счет попыток получить больше полезной информации об игровой позиции без дополнительного погружения в дерево игры. Вопрос о принципиальной возможности построения приемлемых моделей различных игр занимает много места в литературе. Вопрос этот может порождаться просто бытовым любопытством или же потребностью практического использования алгоритмов поиска игровых стратегий в решении сложных практических задач. Игровое моделирование всегда порождает вокруг себя множество споров. Например, попытки создать сильную шахматную программу когдато вызвали дискуссию о том, может ли компьютер в принципе хорошо играть в шахматы Достаточно ли для этого только вычислительных ресурсов Как успешно могут применяться жадные 6, 5 и др. В рамках этих вопросов в работе рассмотрены три варианта специальное усреднение промежуточных оценок в недетерминированных играх, человекоуправляемый перебор в аналитических вычислениях и при игре в шахматы построения алгоритмов поиска псевдооптимальных стратегий в некоторых играх и родственных переборных задачах, имеющих большое практическое значение. Все три направления объединяет одна общая задача задача выбора хорошего решения при имеющихся вычислительных ресурсах, чей недостаток влечет сокращение глубины анализа поставленной задачи игры, и, как следствие, неудовлетворительное качество решения. Введение. Большая часть введения посвящена краткому обзору успехов и проблем программирования игр. Обзор проводится на примере игр шахматы и короткие нарды. На примере этих игр в дальнейшем и будет иллюстрироваться работа новых подходов к решению переборных задач.