Как бы я пошел о кодировании этого генетического алгоритма? - PullRequest
Новая
       4

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

3 голосов
/ 12 августа 2011

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

Игра:

  • Сетка, 12x16.
  • Вы должны очистить блоки от сетки.
  • Ряд новых блоков добавляется каждые 5 тиков вниз, толкая блоки вверх.
  • Вы можете очистить кластеры только одного блока типа.
  • Количество типов блоков увеличивается с продолжением игры.
  • Вы можете очистить только кластеры из 3 или выше.
  • Для каждого очищенного кластера * BLOB_SCORE добавляется (CLUSTER_SIZE - 3)^2.
  • После того, как кластер был удален из сетки, блоки выше скользят вниз, чтобы заполнить промежутки, и если после этого есть горизонтальные промежутки (в нижнем ряду), левая сторона промежутка перемещается, чтобы заполнить его.
  • Цель этой игры - выжить как можно дольше. Время измеряется в тиках или количестве ходов, которые вы сделали.
  • Ваша оценка (или Фитнес) определяется по (TIME_ALIVE * BLOCK_SCORE)
  • Игра заканчивается, когда блок достигает вершины сетки.

Оценка этой игры включает в себя как долговечность, так и эффективность. Чем больше кластеров, которые вы очищаете, тем выше пригодность.

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

Как я могу начать кодировать GA для этого? Я не могу на всю жизнь решить это.

.

Спасибо всем,

Стеффан 'Ruirize' Джеймс

Ответы [ 2 ]

2 голосов
/ 12 августа 2011

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

1 голос
/ 17 августа 2011

Альтернативное кодирование может включать: 

for each possible move
  set phenotypeBehavior to 0
  calculate the post-move position 
  foreach block cleared add a perBlockClearedEmphasis value to phenotypeBehavior
  foreach column add a perColumnHeightEmphasis value to your phenotypeBehavior
  foreach cluster of size x, add a clusterSizeXEmphasis value to your phenotypeBehavior
choose the move that produces the highest phenotypeBehavior

Генетически кодируйте различные значения _foo_Emphasis и развивайте их. Предположительно, например, perBlockClearedEmphasis будет приводить к высоким значениям, в то время как ваша эвристическая «высота плохая» будет приводить к тому, что perColumnHeightEmphasis будет отрицательным, а clusterSizeXEmphasis будет отрицательным для малых X и положительным для больших X.

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

...