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

Question

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

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

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

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

Answer 1

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

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

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

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

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

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

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

EDIT: В качестве быстрого дополнения стоит обратить внимание на то, как работают стандартные шахматные AI, я считаю, что большинство используют Minimax system.

Answer 2

Когда вы говорите «тактику», вы хотите сказать, что вы хотите, чтобы GA предоставил вам общий алгоритм для игры (т. Е. Развил AI) или вы хотите, чтобы игра использовала GA для поиска пространства возможных движется, чтобы генерировать ход на каждом шагу?

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

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

Answer 3

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

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

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

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

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

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

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

Answer 4

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

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

...

В общей задаче о том, что дерево принятия решений, даже не пытаясь придумать простой пример, я находил, что трудно придумать достаточно небольшой пример, но, возможно, в том случае, где вы оценка ли атаковать же-место кусок (который, 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 

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

Answer 5

Vincent,

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

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

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

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

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

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

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