Программирование логических игр с помощью подходов СИИ. Методы работы с Windows Forms в языке С#, алгоритм поиска в пространстве состояний. Формализация дерева состояний. Описание использованных алгоритмов. Иерархическая схема и блок-схемы программы.
Аннотация к работе
В настоящее время теория искусственного интеллекта активно развивается. Это позволяет разработчику формализовать поиск в пространстве состояний, что является ключевым методом искусственного интеллекта.Ним - математическая игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. Выигрывает игрок, взявший последний предмет.Пространство состояний - это граф из множества вершин и дуг, соединяющих пары вершин. В модели пространства состояний решаемой задачи вершины графа представляют дискретные состояния процесса решения, например различные сочетания размеров кучек. Дуги графа описывают переходы между состояниями. Фрагмент пространства состояний для игры Ним представлен на рис.Эвристикой может считаться оптимальное состояние игры, требуемое для выигрыша. Так как мы не можем просматривать граф состояний полностью, каждой вершине присваивается значение, определяемое эвристической функцией. Алгоритм поиска затем использует эти значения, чтобы выбрать наилучший среди возможных ходов из очередной корневой вершины.Определение эвристических оценок для состояний на последнем (горизонтном) уровне дерева состояний (листья). Принятие решения об очередном ходе в соответствии со значениями минимаксного переноса: Max ходит в сторону максимального из детей, Min - в сторону минимального.Смысл игр Ним таков, что при правильном алгоритме можно после первого хода определить победителя. Поэтому достаточно просматривать пространство состояний на 1 уровень вперед для определения наилучшего хода. Если ходит Max, то перейти к пункту 4, иначе перейти к пункту 6.Form1_Load запускает функцию DRAWSTONES, получает начальное состояние игры. DRAWSTONES генерирует начальное состояние игры с помощью генератора случайных чисел, инициализирует поля для изображений, выводит на экран изображения камней. button1_Click - процедура при нажатии на кнопку.using System.Windows.Forms; {lines2.Add(String.Format("{0}-{1}-{2} = {3}", Convert.TOSTRING(POSSIBLESTATES[i].x), Convert.TOSTRING(POSSIBLESTATES[i].y), Convert.TOSTRING(POSSIBLESTATES[i].z), Convert.TOSTRING(POSSIBLESTATES[i].x ^ POSSIBLESTATES[i].y ^ POSSIBLESTATES[i].z))); STATELIST.Add(state); STATELIST.Add(state); STATELIST.Add(state);Появляется главное окно программы (рис. Для хода необходимо выбрать положительное количество камней из одного ряда и нажать на изображение руки. При этом выбранные камни исчезнут (рис. Спустя секунду компьютер производит свой ход (рис.6).Цель данной курсовой работы - получение практических навыков в СИИ - была выполнена. Подобные программы позволяют изучить математические методы искусственного интеллекта, в частности поиск в пространстве состояний и эвристический поиск.
План
СОДЕРЖАНИЕ
1. ПОСТАНОВКА ЗАДАЧИ
2. ОПИСАНИЕ ИГРЫ
3. ФОРМАЛИЗАЦИЯ ДЕРЕВА СОСТОЯНИЙ
4. ОПИСАНИЕ ПРЕДЛОЖЕННЫХ ЭВРИСТИК
5. КРАТКОЕ ОПИСАНИЕ ИСПОЛЬЗОВАННЫХ АЛГОРИТМОВ
6. ОПИСАНИЕ АДАПТАЦИИ АЛГОРИТМОВ К ВАШЕЙ ЗАДАЧЕ
7. СТРУКТУРА ПРОГРАММЫ ИЛИ АЛГОРИТМОВ
7.1 Иерархическая схема программы
7.2 Блок-схемы программы
8. ИСХОДНЫЕ ТЕКСТЫ ПРОГРАММЫ
9. ПРИМЕР РАБОТЫ ПРОГРАММЫ
10. ПРИМЕР ДЕРЕВА СОСТОЯНИЙ
ВЫВОДЫ ПО ДОСТИГНУТЫМ РЕЗУЛЬТАТАМ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. ПОСТАНОВКА ЗАДАЧИ
Список литературы
1. Дж.Ф.Люгер, Искусственный интеллект. Стратегии и методы решения сложных проблем, 2003 г.