GridWars II: битва за процессоры

В конце июня в Сан-Хосе (США) в рамках выставки ClusterWorld Expo прошел второй турнир GridWars Challenge — соревнование разработчиков систем параллельных вычислений на базе классических клеточных автоматов.

В конце июня в Сан-Хосе (США) в рамках выставки ClusterWorld Expo прошел второй турнир GridWars Challenge — соревнование разработчиков систем параллельных вычислений на базе классических клеточных автоматов. Задуманный Engineered Intelligence Corporation как способ обратить внимание разработчиков ПО на новый язык CxC¹, чемпионат стал ярким шоу кластерных технологий. Ход борьбы лучших компьютерных программ за контроль над системой, состоявшей из нескольких тысяч процессоров, отображался на огромном экране и своей увлекательностью не уступал настоящему сражению.

В турнире участвовало более 250 программ со всего мира. Только в списке победителей — представители пяти стран: Марк Вениг (США), Василий Громов (Россия), Пауль Клинге (Финляндия), Шаньмин Ло (Сингапур), Роберт Макрей (Великобритания). Кстати, такой популярности² состязание не в последнюю очередь обязано призам от корпорации Hewlett-Packard, для которой этот чемпионат был важен как дополнительный повод лишний раз привлечь внимание к выставке ClusterWorld Expo.

Итак, о задаче. Поле битвы — матрица заранее заданных размеров, зацикленная по горизонтали и вертикали. Каждая ячейка — отдельный процессор. Все процессоры работают одновременно. В любой момент времени программа, выполняемая на данном процессоре, знает лишь о том, кому принадлежат соседние ячейки. Используя эту информацию, она должна решить, на какие из них нужно выставить предоставленные ей в каждом такте три флага³. И если своих флагов в данной ячейке больше, чем вражеских, причем своих флагов не менее трех, то эта ячейка становится нашей и контроль над ней переходит к нашей программе. Первоначально каждая программа загружается в одну случайным образом выбранную ячейку, а заканчивается битва захватом всей матрицы одной из программ⁴. От претендента, таким образом, требуется написать программу на языке CxC⁵, управляющую работой этого клеточного автомата.

Все присланные программы были проверены на соответствие правилам соревнований, после чего их случайным образом распределили на 32 группы по семь-восемь участников. На предварительном этапе в каждой группе был определен победитель. Далее 32 лучшие программы сражались за звание чемпиона по олимпийской системе. Финальный матч между программами Cobra-109 москвича Василия Громова и Rogue-382 Марка Венига из Мэриленда состоялся 26 июня — и победителем оказался наш соотечественник!

Чемпионат выявил несколько подходов к написанию программ для GridWars. Первый и самый распространенный — попытка подобрать оптимальный набор стратегий. Композиционно большинство матчей в GridWars состоит из нескольких этапов: свободное распространение, столкновение, борьба после возникновения непрерывной линии фронта по вертикали или горизонтали. Каждый этап имеет свои особенности и требует собственной стратегии.

Второй подход — использование генетических алгоритмов. Суть этого метода — непрерывный турнир внутри популяции программ. Чем сильнее программа, тем больше у нее шансов выжить. Последовательное применение генетических алгоритмов могло бы, в принципе, позволить выработать чрезвычайно сильную стратегию. К сожалению, огромная размерность пространства поиска и нетранзитивность отношения «сильнее»⁶ заметно сказываются на качестве решений. Поэтому приходится принудительно ограничивать возможности вариаций и прилагать усилия для невырождения популяции. Тем не менее, этот подход так перспективен, что уже сейчас всерьез обсуждается необходимость разнесения программ сторонников двух методик по разным турнирам.

И наконец третий, особый подход к написанию программы использовал победитель нынешней GridWars. Это путь исследования оболочки, в которой борются программы-роботы. Обнаруженная Василием Громовым возможность прерывать вычисление функции доминирования над данной ячейкой помогла его программе обрести «статус бессмертия» в любой из занятых ячеек. И задача, таким образом, свелась к разработке достаточно агрессивной стратегии, которая позволяла бы захватывать ячейки любого врага. Организаторы подтвердили, что программа Cobra-109 не противоречит правилам и стала победителем на законных основаниях, но согласились, что подобный способ ведения борьбы не соответствует духу турнира, и обещали в правилах следующих соревнований запретить его использование.

Чемпионат закончился, началась подготовка к новым состязаниям, которые намечены на ноябрь 2003 и апрель 2004 года. Желающие принять в них участие могут найти всю необходимую информацию на сайте www.gridwars.com.

1 (назад)Читается «C by C». Язык программирования для организации параллельных вычислений в кластерных системах.
2 (назад) В Интернете можно найти множество так называемых игр для программистов (programming games) (см., например, www.necrobones.com/atrobots), в которых, чтобы победить, нужно написать программу на встроенном языке. Многие из этих игр позволяют программам сражаться друг с другом как настоящим боевым роботам. Но интересны они в основном начинающим программистам. Ситуация меняется, когда речь идет об участии в чемпионате мира, где борьба к тому же идет за реальные призы.
3 (назад) В оригинальном руководстве — «bullets», но автору термин «флаг» кажется более адекватным сути происходящего.
4 (назад) Кроме основной лиги, в которой приняло участие 226 программ, соревнование проходило и в дополнительной лиге — MEGA GridWars. Размеры поля битвы в ней значительно увеличены и введены дополнительные типы полей: стены, телепорты, поля-невидимки. Чемпионат в этой лиге проводился впервые, и потому участников было мало.
5 (назад) По своему синтаксису язык CxC весьма прост, и если вы пишете на обычном С или C++, то без труда освоите CxC.
6 (назад) То есть если программа A побеждает программу B, а программа B побеждает программу С — это не означает, что A сильнее C. Зачастую программа C легко выигрывает у A.