Архивы: по дате | по разделам | по авторам

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

Архив
автор : Дмитрий Финоженок   05.09.2003

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

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

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

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

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

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

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

И наконец третий, особый подход к написанию программы использовал победитель нынешней 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.

© ООО "Компьютерра-Онлайн", 1997-2022
При цитировании и использовании любых материалов ссылка на "Компьютерру" обязательна.