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

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

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

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

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

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

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

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

Винсент,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обычный игрок в Stratego кажется мне довольно сложным, но если у вас есть разумная программа для игры в Stratego, «Настройка доски Stratego» станет отличной проблемой 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

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