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

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

Автор: Радионов, Алексей Николаевич

Шифр специальности: 05.13.18

Научная степень: Кандидатская

Год защиты: 1999

Место защиты: Ульяновск

Количество страниц: 112 с.

Артикул: 244094

Автор: Радионов, Алексей Николаевич

Стоимость: 250 руб.

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 и др. В рамках этих вопросов в работе рассмотрены три варианта специальное усреднение промежуточных оценок в недетерминированных играх, человекоуправляемый перебор в аналитических вычислениях и при игре в шахматы построения алгоритмов поиска псевдооптимальных стратегий в некоторых играх и родственных переборных задачах, имеющих большое практическое значение. Все три направления объединяет одна общая задача задача выбора хорошего решения при имеющихся вычислительных ресурсах, чей недостаток влечет сокращение глубины анализа поставленной задачи игры, и, как следствие, неудовлетворительное качество решения. Введение. Большая часть введения посвящена краткому обзору успехов и проблем программирования игр. Обзор проводится на примере игр шахматы и короткие нарды. На примере этих игр в дальнейшем и будет иллюстрироваться работа новых подходов к решению переборных задач.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.581, запросов: 244