1. Понятие дерева возможностей 2. Методы подрезки дерева возможностей 3. Обучение игровых программ

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

Принципы работы многих игровых программ опираются на исследования дерева возможных продолжений игры Комбинаторный взрыв … …

Принципы игры в шахматы Корневая вершина дерева возможностей представляет собой текущее положение фигур на шахматной доске, а работа программы состоит в выборе очередного хода Все вершины могут быть двух типов: альфа-вершина – ход компьютера бета-вершина – ход его противника Дерево возможностей представляет собой чередующиеся слои альфа- и бета-вершин В интеллектуальных играх типа шахмат удаётся построить и просмотреть лишь небольшую часть дерева возможностей - дерево возможностей подвергается подрезке

Методы подрезки дерева возможностей

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

Метод обратного усечения поиск по дереву включает в 2 этапа: 1. построение дерева возможностей с приписыванием его терминальным вершинам числовых значений оценочной функции 2. применение минимаксной процедуры для передачи значений вверх по дереву значения оценочных функций связываются с вершинами по мере формирования дерева: 1. оценивающие функции для альфа-вершины с ростом дерева могут только увеличиваться 2. для бета-вершины – только уменьшаться наблюдение за динамикой изменения оценивающих функций даёт возможность определить нерезультативные ветви

Обучение игровых программ

Некоторые принципы используемые А.Сэмюэлом в программе

программа содержала больший ассортимент критериев (а 1, а 2 и т.д.), чем допускался для использования в конкретной оценивающей функции. Используемое множество критериев видоизменялось во время игры. А. Сэмюэль предложил замкнуть игровую программу саму на себя – организовать работу программы таким образом, что она могла вести игру и самообучаться непрерывно днем и ночью, имитируя одновременно двух игроков (x и y).