Как выбрать хорошее представление для тактики настольной игры для генетического алгоритма?

Question

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

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

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

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

Answer 1

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

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

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

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

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

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

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

Answer 2

Винсент,

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

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

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

Функция оценки доски - это магия и, вероятно, хороший кандидат на использование либо генетического алгоритма, либо генетической программы, которую можно использовать вместе с нейронной сетью. Основная идея заключается в том, что вы пытаетесь спроектировать (или развить, на самом деле) функцию, которая принимает в качестве ввода позицию на доске и выводит одно число. Большие числа соответствуют сильным позициям, а маленькие - слабым. Есть знаменитая статья Chellapilla и Fogel, показывающая, как это сделать для игры в шашки:

http://library.natural -selection.com / Library / 1999 / Evolving_NN_Checkers.pdf

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

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

Answer 3

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

Проблема в том, что шахматная стратегия довольно сложная вещь.Вы предлагаете в своем ответе содержать множество переходов между позициями доски в ГА, но у шахматной доски есть больше возможных позиций, чем число атомов во вселенной, это явно не будет работать очень хорошо.То, что вам, вероятно, нужно будет сделать, - это кодировать в GA серию весов / параметров, которые привязаны к чему-то, что занимает позицию доски и запускает ход, я думаю, это то, на что вы намекаете во втором предложении.

Вероятно, самым простым предложением было бы использование какого-либо приближения обобщенной функции, например нейронной сети; Персептроны или Радиальные базовые функции - две возможности.Вы можете кодировать веса для различных узлов в GA, хотя есть и другие достаточно надежные способы обучения нейронной сети, см. Обратное распространение .Возможно, вы могли бы закодировать структуру сети вместо этого / также, это также имеет то преимущество, что я почти уверен, что было проведено немало исследований в области разработки нейронных сетей с использованием генетического алгоритма, чтобы вы не начинали полностью с нуля.

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

• Строка со всеми 64 квадратами один за другимдругой с числом, представляющим то, что присутствует в каждом квадрате.Наиболее очевидное, но, вероятно, довольно плохое представление, так как для фильтрации недопустимых ходов потребуется много работы.
• Битовая строка со всеми 64 квадратами один за другим с числом, представляющим, что может перемещаться в каждый квадрат.Преимущество этого состоит в том, что в нем реализована концепция покрытия шахмат, в которой вы можете получить как можно больше покрытия на доске своими фигурами, но при этом все еще возникают проблемы с нелегальными ходами и борьбой с дружественными / вражескими фигурами.
• Aбитовая строка со всеми 32 фигурами одна за другой с номером, представляющим местоположение этой фигуры в каждом квадрате.

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

В любом случае, надеюсь, что это вам поможет.

РЕДАКТИРОВАТЬ: В качестве быстрого дополнения стоит посмотреть, как работает стандартный шахматный ИИ, я полагаю, что большинство используют какую-то минимаксную систему .

Answer 4

Когда вы говорите «тактика», вы имеете в виду, что хотите, чтобы ГА предоставил вам общий алгоритм игры (то есть развить ИИ), или вы хотите, чтобы игра использовала ГА для поиска пространства возможных ходов? генерировать ход на каждом ходу?

Если вы хотите сделать первое, тогда посмотрите на Генетическое программирование (GP). Вы можете попытаться использовать его для получения наилучшего искусственного интеллекта для фиксированного размера дерева. JGAP уже поставляется с поддержкой GP. Смотрите пример JGAP Robocode . Этот подход означает, что вам нужен предметно-ориентированный язык для ИИ Stratego, поэтому вам нужно тщательно продумать, как вы выставляете доску и ее части.

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

Answer 5

@ Ответ ДонАндре абсолютно верен для движения.В общем, проблемы, связанные с решениями на основе состояния, сложно моделировать с помощью GA, требующих некоторой формы GP (либо явной, либо, как предположил @DonAndre, деревьев, которые по сути являются декларативными программами).

Обычный игрок в Stratego кажется мне довольно сложным, но если у вас есть разумная игровая программа для Stratego, «Настройка вашей доски Stratego» была бы отличной проблемой для GA.Начальные позиции ваших пьес будут фенотипом, а результат внешнего кода для игры Stratego - пригодностью.Интуитивно вероятно, что случайные установки окажутся в невыгодном положении по сравнению с установками, которые имеют несколько «хороших идей», и что небольшие «хорошие идеи» могут быть объединены в установки «все лучше и лучше».

...

В связи с общей проблемой того, что такое дерево решений, даже пытаясь придумать простой пример, мне было трудно найти достаточно маленький пример, номожет быть, в случае, когда вы решаете, атаковать ли фигуру того же ранга (что, IIRC уничтожает вас и другую фигуру?):

double locationNeed = aVeryComplexDecisionTree();
if(thatRank == thisRank){
   double sacrificeWillingness = SACRIFICE_GENETIC_BASE; //Assume range 0.0 - 1.0
   double sacrificeNeed = anotherComplexTree(); //0.0 - 1.0
   double sacrificeInContext = sacrificeNeed * SACRIFICE_NEED_GENETIC_DISCOUNT; //0.0 - 1.0  
   if(sacrificeInContext > sacrificeNeed){
      ...OK, this piece is "willing" to sacrifice itself

Так или иначе, основная идея заключается в том, чтоу вас все еще было бы много кода для Stratego-play, вы просто искали бы места, где можно было бы вставить параметры, которые могли бы изменить результат.Здесь у меня возникла идея «базовой» склонности к самопожертвованию (предположительно, выше у обычных предметов) и генетически определенного параметра «скидка», который бы определял, будет ли предмет «принимать или отвергать» потребность в жертве.