45358

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

Доклад

Информатика, кибернетика и программирование

Таким образом накопление позволяет либо экономить время либо достичь лучшего качества игры за то же время путем использования несколько большего дерева. Оно позволяет программе в ходе игры улучшать свои оценивающие функции. Качество игры зависит от подходящего выбора весовых коэффициентов k1 k2 k3 .

Русский

2013-11-16

41 KB

5 чел.

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

Представляет интерес программа для игры в шашки, разработанная Артуром Сэмюэлем. В этой программе Сэмюэлю удалось реализовать две формы обучения: накопление и обобщение.

Накопление сводится к хранению в памяти компьютера большого числа конфигураций на шашечной доске из тех, что реально (а не гипотетически) возникают в ходе шашечных игр. Вместе с каждой конфигурацией в памяти хранится также её числовая оценка, которая получилась путём построения дерева, применения оценивающей функции к терминальным вершинам и передачи значений вверх по дереву посредством минимаксной процедуры. Имея в памяти некоторое множество конфигураций вместе с их оценками, программа в процессе работы ищет соответствие между конфигурацией, отвечающей каждой из вершин дерева, и конфигурациями из числа запомненных. Если такое соответствие установлено, то хранимая в памяти оценка передаётся в эту вершину. В результате отпадает необходимость строить какую-либо ветвь, которая могла бы возникнуть под этой вершиной.

Таким образом, накопление позволяет либо экономить время, либо достичь лучшего качества игры за то же время путем использования несколько большего дерева.

Естественно, размер списка конфигураций, который может храниться в памяти и использоваться, ограничен сверху. А. Сэмюэль построил свою программу так, что наименее употребляемые конфигурации вычеркиваются, а часто встречающиеся остаются в памяти компьютера.

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

S = kl al + k2 a2 + k3 a3 + ...,

Полином может быть также и более высокой степени относительно переменных а, например,

S = kl al + k2 a2 + k11 a12 + k12 a1 a2 + ...,

Качество игры зависит от подходящего выбора весовых коэффициентов k1, k2, k3, ..., и обобщение является средством их подгонки, обеспечивающей улучшение игры. Метод обобщения представляет собой пример оптимизации с использованием процедуры, называемой "подъем в гору". Имеется начальный набор значений k1, k2, k3, ..., и в каждый момент времени эти коэффициенты определяют рабочую точку. Рабочая точка перемещается в пределах многомерного пространства по мере подгонки величин весовых коэффициентов в поисках положения, в котором оптимизируется определенная реакция или целевая функция.

Чтобы воспользоваться методом подъема на гору, следует дать программе возможность сыграть некоторое число игр с определенным партнером, выбрав какое-то начальное множество коэффициентов ki, а затем сыграть еще некоторое число игр, сделав пробные изменения в положении рабочей точки. Если программа во втором множестве игр выигрывает чаще, то принимается новое значение ki. В противном случае происходит возвращение к старой величине и производится какое-то новое пробное изменение.

Недостатки данного метода в следующем: во-первых, этот путь предполагает очень медленное движение, во-вторых, поскольку партнер не может играть абсолютно ровно, необходимо, чтобы два указанных множества игр были достаточно емкими.

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

Если S – результат прямой оценки с помощью оценочной функции, a Sb – результат передачи оценки по дереву (с большой глубиной), то можно считать их разность ошибкой е, где

e = S - Sb.

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

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

Таким образом, А. Сэмюэлем был создан алгоритм программы, обладающий свойством самообучения (обучение без учителя). Эту программу считают первой в мире действующей самообучающейся программой.

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

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

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

Таким образом, А. Сэмюель создал программу, которая позволяла не только правильно играть в шашки, но и улучшать стратегию игры, используя опыт, накопленный в предыдущих партиях.

Современные обучающиеся игровые программы имеют недостаток.

Дело в том, что в современных игровых программах, как правило, реализованы сразу две парадигмы обучения – с учителем и без него. Результат обучения таких программ зависит от конкретного учителя. И очень часто вместо того чтобы учиться играть в игру, такие программы учатся обыгрывать учителя. Например, после победы DeepBlue над Гарри Каспаровым программисты IBM отказались от матча с другими гроссмейстерами. В результате чемпион мира заявил, что программа просто была "натаскана" на его партиях, она изучила его стиль и потому просто не способна конкурировать с другими гроссмейстерами.

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


 

А также другие работы, которые могут Вас заинтересовать

23573. Различие между транскрипцией фонологической и транскрипцией фонетической 34.5 KB
  Обозначение фонем 3. Обозначение отдельной фонемы должно четко отличаться от обозначения группы фонем. Если в данной транскрипционной системе отсутствуют специальные знаки для некоторых фонем например для аффрикат или дифтонгов и если они обыкновенно передаются группой из двух или более букв символизирующих их конститутивные элементы то группа знаков соответствующих фонеме такого рода должна связываться снизу дужкой например чешское ou немецкое pf. Когда обозначение определенных дизъюнктивных фонем диакритиками или определенных...
23574. ФОНЕТИКА 37 KB
  расчленяется в четырех направлениях: 1 антропофоника физиология звуков речи изучающая произносительную собственно физиологическую и слуховую акустическую сторону языка и фонология изучающая использование звуков для выражения значений для образования слов и фраз; 2 учение о фонетических элементах аналитическая Ф. Схематический разрез гортани и надставной трубы: a голосовая щель; b щитовидный хрящ; c надгортанный хрящ; d увула Звучание речи создается модификацией выдыхаемой воздушной струи истекающей изо рта и из носа в...
23575. Теория языка 2.51 MB
  bz Карл Бюлер Теория языка Оглавление Предисловие автора Введение. Теория языка вчера и сегодня Глава I. Модель языка как органона а формы существования конкретных языковых явлений 3. Знаковая природа языка в модель структуры языка 4.
23576. ЭЛЕМЕНТЫ ОБЩЕЙ ЛИНГВИСТИКИ 1.42 MB
  Иными словами выяснение общеязыковых закономерностей внутренней логики и механизма действия языка с необходимостью входит в сферу общего языкознания. В то же время автор надеется что адекватным окажется и западноевропейское понимание этого слова: ср. Передача информации один из существеннейших видов и аспектов общения между людьми поэтому по словам В. 246 иначе говоря всякое слово есть результат абстрагирующей работы мысли слово дерево обозначает дерево вообще и наоборот абстрактное понятие общее для всех членов данного...
23577. История языкознания: Учебное пособие для cтудентов старших курсов и аспирантов 1.4 MB
  Здесь даны очерки посвящённые истории формирования и развития самобытной лингвистической мысли в государствах Востока и в странах Западного мира где лингвистическая традиция сложилась на основе грекоримских идей по философии языка и грамматике. Читатель обратит внимание на то что становление и развитие языкознания в восточных и западных культурных ареалах шло во многом своими путями отражая особенности как своих языков так и своих культур и что лишь в последние одиндва века наблюдается переориентация ряда восточных школ на европейские...
23578. Плезиохронная цифровая иерархия 32.5 KB
  Технологии передачи информационного сигнала развивались параллельно с развитием телефонных сетей. Постоянно растущее число пользователей и рост телефонного трафика привел к появлению систем мультиплексирования сигналов с разделением по частоте
23579. Отсутствующая структура Введение в семиологию 2.96 MB
  Код [2. Коды и лексикоды [2. Коды и их модификации [2. Кодифицируемость уровней [2.
23580. Россия в метафорическом зеркале: когнитивное исследование политической метафоры 1.25 MB
  Чудинов Россия в метафорическом зеркале: когнитивное исследование политической метафоры 1991 2000 УДК 408. Ч84 Россия в метафорическом зеркале: Когнитивное исследование политической метафоры 1991 2000: Монография Урал. ISBN 5718602778 Монография посвящена исследованию закономерностей моделирования образа современной России в зеркале концептуальной метафоры в котором вне зависимости от чьихлибо симпатий и антипатий достаточно объективно фиксируется подлинная картина национального самосознания в котором отражаются как традиционные...
23581. Семиосфера. Культура и взрыв Внутри мыслящих миров 5.53 MB
  ЛОТМАН Семиосфера Культура и взрыв Внутри мыслящих миров Статьи Исследования Заметки СанктПетербург ИскусствоСПБ О метаязыке типологических описаний культуры О семиотическом механизме культуры Миф имя культура Культура как коллективный интеллект и проблемы искусственного разума Феномен культуры Технический прогресс как культурологическая проблема Культура как субъект и самасебе объект О семиотике понятий стыд и страх в механизме культуры Память в культурологическом освещении [1] Содержание [2] Люди и знаки1 [3] Культура и взрыв...