Старкрафт: генетический алгоритм - новая основа победы

Я не играю в "Старкрафт", поэтому мне трудно оценить насколько позиция 7-roach rush действительно ценна, и полагаюсь на мнение других обозревателей. Суть мультиплейера игры "Старкрафт" - развиваясь из примерно одинаковых начальных условий, получить преимущество над противником к моменту столкновения с ним. Например, успеть произвести больше бойцов или успеть этих бойцов "проапгрейдить". Для этого в ходе игры необходимо предпринимать различные действия, такие как "постройка здания", "исследование апгрейда", "производство юнита" и другие. Каждое действие требует затрат ресурсов, возобновление которых требует времени. В некоторых случаях (как в случае расы zerg) правила обмена настолько сложны, что традиционные "жадные" алгоритмы не могут найти оптимального решения, так как попадают в ловушку: состояние, в котором любое действие невыгодно.

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

Разработанная программа позволяет построить оптимальный сценарий для достижения любой желаемой позиции за минимальное время при условии, что столкновения с реальным противником еще не произошло. В том числе, максимально быстро достичь позиции 7-roach rush, то есть, произвести 7 бойцов, которые на начальном этапе игры почти гарантированно сокрушат противника, не успевшего обзавестись собственными бойцами. Приложение использует генетический алгоритм следующим образом:

• Сценарий (последовательность действий) кодируется в виде последовательности "генов" (идентификаторов действий), такая последовательность называется "хромосомой";
• Не любой сценарий "валиден": некоторые действия не могут быть выполнены из позиции, достигнутой предыдущими действиями. При расшифровке и "оценке" хромосомы такие действия игнорируются (их можно рассматривать как "скрытый генетических код", отсюда и эпитет "Грязный", используемый для генетических алгоритмов с такой схемой декодирования);
• Эффективность сценария можно оценить по затрачиваемому времени и ценности дополнительных ресурсов, необходимых для достижения заданной позиции после завершения сценария.

Для расы zerg игры Starcraft-2 удалось построить как функцию оценки, так и модель, проигрывающую сценарий. Как правило, именно описанные выше три шага требуют изобретательности от разработчика программы на основе генетического алгоритма, остальная часть алгоритма проста и обычна:

• Случайным образом генерируется определенное количество сценариев ("популяция");
• При помощи функции оценки определяются худшие сценарии и убираются из популяции;
• При помощи "генетических операций" - скрещивания и мутации - на основе лучших сценариев генерируются особи, взамен убранных;
• Последние два шага - оценка и размножение - повторяются до прекращения улучшения функции оценки.

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

Результат: нахождение сценария, позволяющего достичь состояния 7-roach rush за 45 секунд, что, по оценке некоторых экспертов, гарантирует выигрыш при любых условиях. Остается добавить, что состояние 7-roach rush было выбрано игроком-экспертом, как наиболее выгодное (т.е. он знает как играть дальше и выиграть), если вдруг найдется противник, способный побеждать игрока с 7-roach rush, то можно выбрать другое состояние и найти сценарий его достижения.

Более подробно алгоритм описан в статье Using genetic algorithms to find Starcraft 2 build orders, автор которой, кстати, знает что такое "Старкрафт" и утверждает, что найденный сценарий достижения 7-roach rush не характерен для игрока в "Старкрафт" :).

В мире поклонников "Старкрафт", разумеется, наступил легкий шок: получена "серебряная пуля", с которой выиграть может любой. Остался ли в игре смысл? Или теперь все сведется к запоминанию "правильных" сценариев?

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

Вывод из этой истории прост: пока одни особи вида "Человек Разумный Раз-разумный" пытаются уйти от реальности в прекрасный мир детства, с деревянными автоматами и суперкомпьютером "Арифмометр Феликс", другие эволюционируют к виду "Человек Разумный Делегирующий": особи нового вида умеют выделять задачи, соответствующие своему уровню и способностям, а рутину отдавать тому, кому это интересно: хотя бы и искинам.

Подробнее о других взглядах на морально-этические проблемы можно прочитать в статье Genetic algorithms find unbeatable starcraft tactics.