Это моя попытка смоделировать Королевскую игру Ура и провести турнир ИИ по этой игре перед моим первым годом в Калифорнийском университете в Беркли.

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

Смотрите первую часть здесь.

Как компьютер запускает мою игру

При кодировании программистам разрешается кодировать и моделировать реальные объекты в своей программе, сообщая компьютеру, каковы правила и свойства реальных объектов. Компьютер получает специальный код, написанный для моделирования объекта, и создает эти моделируемые объекты для программиста. Этот принцип программирования системы с пользовательскими объектами называется объектно-ориентированным программированием (ООП) и уже очень давно довольно популярен в приложениях, которые вы используете ежедневно. В этом случае я буду моделировать внутриигровые аспекты, такие как «фишки», «игровое поле», «игроки» и «ячейки на игровом поле», как настраиваемые объекты в моей программе, что имеет смысл, поскольку каждый из этих объектов имеет свои особенности. соответствующее поведение для имитации (перемещение по доске, разрешение повторных бросков… и т. д.).

Однако использование объектов в каждой отдельной ситуации сопряжено с недостатком: хранением памяти. Как минимум, смоделированные объекты на компьютере имеют свойства, которые их представляют; например, объекты-собаки будут иметь «имена» и «возраст» в своих компьютерных версиях точно так же, как и в реальной жизни. Однако в компьютерах такие слова, как имена, занимают довольно много памяти для хранения, и числа, такие как возраст, также могут подойти. Сам объект собаки стоит, по крайней мере, воспоминаний как списка символов, представляющих имя, так и числа, представляющего возраст. Это означает, что в своей основе объекты представляют собой своего рода вместилище значений, которые их характеризуют.

Объект собаки кажется разумным для реализации, но есть также вещи, которые можно структурировать просто без необходимости использования объектов. Подумайте об этом в следующем сценарии реальной жизни:

Я делаю большую сумку моей любимой закуски, жареного лука. Либо упаковка жареного лука в многочисленные маленькие пакеты, а затем помещение их в большой пакет, либо прямое выплескивание их в большой пакет завершают цель предоставления луку контейнера. Но, в конечном счете, подход с маленькой сумкой требует больших затрат. Какая упаковка эффективнее?

Вернемся в мир информатики! Чтобы прояснить расположение кода для каждого объекта и создать более короткие файлы, я написал код, позволяющий моему компьютеру имитировать каждый тип внутриигровых объектов в соответствующих файлах, и связь между каждым объектом выглядит следующим образом:

Некоторые более простые объекты для описания в первую очередь:

Объект Player: просто содержит имя игрока и стратегию, которую он использует.
Объект Piece: имеет числовой идентификатор для определения того, какая фигура отсутствует. всего, чем владеют его владельцы. Он также содержит число, указывающее идентификатор игрока, которому принадлежит фигура.
Объект Cell: может содержать или не содержать фигуру и следует за кодом, определяющим ее положение на игровом поле. а также дает ли он особые способности для ячеек на нем.

Объект Board немного сложнее. Это контейнер объектов Cell (поскольку доски содержат ячейки). Но в более широком плане это «контейнер контейнеров с деталями».
Хотя мой компьютер способен отслеживать все контейнеры, встречающиеся в игре, такой дизайн кажется немного избыточным. Здесь мы возвращаемся к аналогии с мешками с жареным луком. Клетки — это маленькие мешочки, игровые фигуры — это луковицы, а доска — это большой мешок. Почему я не могу найти способ просто позволить моей доске содержать мои игровые фигуры вместо того, чтобы строить контейнер из ячеек, которые являются контейнерами для фишек? По крайней мере, теперь мы видим место для улучшения в моем неприличном коде! Но, тем не менее, объектно-ориентированный дизайн, подобный этому, немного более инстинктивен для разработчика, чем вышеупомянутая альтернатива, поскольку каждая ячейка также имеет свои собственные специальные эффекты (реролл, мирный режим…).

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

И последнее, но не менее важное: наш внутриигровой алгоритм искусственного интеллекта, вдохновленный ожидаемым минимаксом, примерно устроен следующим образом:

Эвристика:

f(board) = distance current cell makes + distance of deported cell from its start, if any.

Псевдокод алгоритма:

util = 0
for i from 1 to n:
    calculate the current util according to f(board)
    if the current predicting player is myself:
        util += f(board)
        // by making a move I am expanding my own advantage
    else if the current predicting player is my opponent:
        util -= f(board)
        // because my opponent makes a move that reduce my advantage
    alternate the current player to the opposite player
return util

Или, говоря простым языком:

Синтез

Теперь мы смоделируем игру, предоставив объекту Game два объекта Player, объект Board с несколькими Cells и Pieces на доске. Игра на самом деле делается довольно быстро, и если игра превышает 500 ходов, она автоматически считается тупиковой. Делегирование обязанностей по каждому объекту при поддержании игры также происходит плавно.

Затем нам просто нужно выбрать процедуру для проверки различных стратегий друг против друга. Для стратегии A и стратегии B, переданных виртуальными игроками A и B соответственно, мы позволим A и B идти соответственно первым и вторым и запишем процент побед для каждого матча стратегии. Отдельные пары стратегий будут соответствовать каждому возможному порядку, в котором ходят игроки. Если стратегия идет вразрез с самой собой, для такого матча будет протестирован только один порядок игроков. Мы протестируем две разные стратегии: одну упрощенную, а другую — алгоритм прогнозирования, который мы обсуждали ранее.

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

Таким образом, ход турнира будет примерно таким:

Matchup 1: Simple vs Simple
Matchup 2: Simple vs Predict Depth 1
…
Matchup 8: Predict Depth 1 vs Simple
…
Matchup 49: Predict Depth 6 vs Predict Depth 6

Полученные результаты

Затем мы можем сделать два вывода из этих результатов:

  1. В конечном счете, выбор первого или второго места имеет очень незначительное значение для стратегий, разработанных в этом эксперименте.
  2. Для прогностической стратегии, чем выше обозначенная глубина предсказания (или сложность мышления), тем ниже ее эффективность по сравнению с другими стратегиями и тем хуже она справляется с более простыми стратегиями этого эксперимента.

Возможные изменения

Вот несколько основных вопросов, которые я хотел бы обсудить в отношении улучшения проекта.

Вопрос 1.Почему стратегия работала все хуже и хуже в зависимости от глубины предсказания? Или какие именно части являются «плохим мышлением» в функции стратегии?

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

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

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

Вопрос 2.Почему моделирование потребовало так много ресурсов для моего оборудования?

Каждый отдельный ход в игре создает очень большое игровое дерево, учитывая множество возможных досок, и каждая доска, используемая для моделирования, также копирует каждую отдельную ячейку и часть, которую она использовала для переноски. Это означает, что алгоритм должен сделать много-много симуляций, чтобы закончить игру. В простом приближении для игры, которая длится 150 ходов, с алгоритмом, который думает на 3 шага вперед, и при условии, что каждый ход имеет 5 возможных исходов (поскольку существует 5 возможных значений костей), это уже указывает минимум на более чем 2000 симуляций за один раз. игра.

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

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

Вопрос 3.Как мы можем повысить эффективность функции стратегии?

Как упоминалось ранее, функция стратегии должна быть более консервативной в своих предположениях и выполнять более точную оценку для каждого хода. Это намекает на следующие направления:

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

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

Есть также интересное направление, в котором мы пишем какой-то алгоритм для программы, чтобы узнать, какая комбинация наград лучше всего подходит для игрового процесса. Для этого нам нужно определить начальную комбинацию вознаграждений за выбранный вручную набор внутриигровых действий, а также алгоритм, чтобы программа оценивала различные комбинации вознаграждений и решала, должны ли вознаграждения увеличиваться или уменьшаться за каждое действие. . Теперь это действительно звучит так, как мы представляем, что ИИ делает в научно-фантастических статьях или новостных статьях:

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

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

Не технические примечания

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

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

Если у вас есть какие-либо мысли по этому проекту или исправления, вопросы по этому отчету, не стесняйтесь комментировать ниже!

Репозиторий Github для кода: https://github.com/Bransthre/project-ur