Спортивное программирование *

Продолжаем разбираться в правилах проходящего сейчас турнира Google AI Challenge. Дальше вы можете прочитать перевод официальных правил расчета результатов муравьиных боев.

Фонд Викимедиа сообщает о начале конкурса по программированию October 2011 Coding Challenge. Авторы Википедии хотят найти программистов, которым близки ценности мира, в котором каждый человек обладает свободным доступом к любому знанию. Гран-при в каждой задаче — оплата расходов на какое-нибудь (по выбору победителя) событие фонда в 2012 году. Все успешные участники получат сертификат с отличием от фонда. На мой вкус — намного более осмысленное мероприятие, нежели гонять муравьёв.

Правила турнира

• Результаты турнира определяются с помощью ПО написанного организаторами. Опубликованные результаты являются окончательными. Текущий рейтинг игроков не является официальным и может отличаться от опубликованных окончательных результатов.
• Каждый участник турнира может иметь единственную учетную запись. При выявлении участника управляющего несколькими учетными записями, и несмотря на то, что эти учетные записи зарегистрированы на других людей, нарушитель будет дисквалифицирован.
• Участники (или их программы), которые нарушают дух правил и спорта (вероятно не нарушая официального текста правил), отстраняются от участия в турнире, без возможности обжалования. В частности: сканирование памяти, умышленный проигрыш и изменение поведения в зависимости от имени оппонента — запрещены.
• Производить запись в файлы запрещено. Разрешено производить чтение из файлов которые вы высылаете для участия. Файлы располагаются в текущей директории.
• Использование нескольких процессов или потоков запрещено.
• Любая попытка нарушить нормальную работу программного обеспечения турнира или серверов приведет к немедленному привлечению сотрудников правоохранительных органов. Наш принцип — всегда преследовать нарушителей в судебном порядке.
• Организатор оставляет за собой право, изменить эти правила в любой момент, без предварительного уведомления участников турнира.

Этот топик — перевод первых двух частей руководства по написанию своего бота для Google AI Challenge.
Весь код написан на языке Python.

Шаг 1: Как избежать столкновений

План

Чтобы муравьи не сталкивались надо:
1) Предотвратить перемещение одного муравья на другого;
2) Предотвратить перемещение двух муравьев в одну и ту же точку;
3) отслеживать информацию о местонахождении всех наших муравьёв.

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

Рассказывая о конференциях, форумах, съездах и лан-пати, нельзя обделить вниманием хакерские и программерские чемпионаты. А ведь их немало, за призовые места там платят неплохие деньги, да и в целом участие в подобных мероприятиях — это очень полезный опыт.

Меня очень давно заинтересовала тема программирования поведения объектов в виртуальном мире. Но практические знания в этой области оставляют желать лучшего, поэтому недавно начал искать небольшой проект для вложения сил. В итоге я его нашел, благодарен гуглу и ideas4ru за анонс.

Совсем скоро стартует Google AI Challenge Ants. Два дня назад уже был анонс на хабре про это состязание:
http://habrahabr.ru/blogs/sport_programming/130457/
. Для тех, у кого есть желание поучаствовать или хотя бы просто узнать поподробнее, как это делается, я написал этот «Быстрый Старт».
Из статьи вы узнаете как запустить у себя на машине игру, написать своего первого бота и запустить две копии бороться друг против друга.

Если в прошлом году боты соревновались в игру под названием Planet Wars, то в этом году игра будет называться Ants или Муравьи. Неокончательные правила и описание игры уже доступны на сайте конкурса: beta.aichallenge.org.

Участникам соревнования предстоит реализовать алгоритм, который будет руководить колонией муравьев. На симметричной карте, состоящей из земли и воды (препятствия), каждому боту будут выделены один или несколько муравейников — места, в которых рождаются новые муравьи. Целью игры является захват и уничтожение муравейников противников при этом сохранение и защита своих. За уничтожение чужих муравейников начисляются очки, а за сдачу своего очки вычитаются.

На этой неделе проходили соревнования 2011 TopCoder Open. Проходит сие мероприятие во Флориде, с 26 сентября. Спонсорами мероприятия выступают: facebook, intel, MemSQL, Mashery. Соревнования проводятся в 6 категориях, это Algorithm, Marathon, Design, Development, Studio, Mod Dash.

Под катом — список из 15 лучших ресурсов, посвящённых Спортивному Программированию.

Благодаря инициативе группы пользователей из Ирана, на Codeforces в субботу, 30-го июля в 10:00 по Москве
состоится Unknown Language Round #3. Если коротко — это оригинальная форма спортивно-программистского развлечения, впервые предложенная мной в феврале этого года. Чуть подробнее можно прочитать здесь.

Доброго времени суток, уважаемое Хабрасообщество.

В последнее время все большее и большее распространение получает олимпиадное программирование, неотъемлемой частью которого является знание алгоритмов (и, разумеется, умение их применять).

Я хочу рассказать вам основы теории Игр, доказать функцию Шпрага-Гранди, разобрать несколько классических impartial-задач и проиллюстрировать их кодом на python.

Довольно часто в спортивном программировании или же просто реализации алгоритмов необходимо отсортировать массив входных данных по определённому критерию. В то время как в ответе требуется исходный порядок. В статье я рассмотрю несколько способов сделать это минимальной кровью на C++. Если интересна эта тематика или имеются интересные предложения, прошу под кат…


Автор изображения: Tobias Rad, лицензия Creative Commons Attribution-Share Alike 3.0 Unported

Вступление

Людям, которые увлекаются спортивным программированием, хорошо известны соревнования корпорации TopCoder. Среди них, пожалуй, самым популярным видом является Single Round Match, или SRM. Схема SRM'ов достаточно специфическая, и в чем-то неповторимая. Если кратко — сначала участники решают 3 задачи разных уровней сложности, потом некоторое время ищут ошибки у оппонентов, получая за это дополнительные очки.

Для организации таких соревнований TopCoder создали Java-апплет (TopCoder Arena). Также нашлись умельцы, которые для этой самой арены написали плагины, чтобы упростить жизнь себе и другим. Но установка последних часто вызывает трудности у начинающих SRM'щиков. Именно эта проблема стала мотивом для написания этой статьи.

Вчера вечером прошел третий и последний отборочный раунд ежегодного турнира по спортивному программированию Google Code Jam.
Top-25 участников прошли в финал, который будет проходить 29 июля в Токио. В него вошли представители следующих стран:

• 10 участников из России:
  • vepifanov (Владислав Епифанов)
  • ilyaraz (Илья Разенштейн)
  • Egor (Егор Куликов)
  • ashmelev(Алексей Шмелев)
  • ilyakor (Илья Корнаков)
  • bsod (Евгений Капун)
  • darnley (Михаил Дворкин)
  • natalia (Наталья Бондаренко)
  • andrewzta (Андрей Станкевич)
  • winger (Владислав Исенбаев)
• 5 участников из Китая: Bin.Jin, g201513, hanshuai, acrush, zyz915
• 3 участника из Японии: ir5, omeometo, rng..58
• По одному участнику из
  • США: neal.wu
  • Индонезии: Dolph
  • Польши: meret
  • Беларуси: mystic (Иван Метельский)
  • Словакии: misof
  • Грузии: nika
  • Великобритании: linguo

Официальные результаты

«В наше время считается общепризнанным,
что из всего, так или иначе касающегося искусства,
ничто более не может считаться общепризнаным»
Теодор Адорно

Все началось с того, как один человек пытался выяснить решение задачи контеста, который проходил в данный момент. Задача была очень простая, всем было очевидно, что этот человек не займет хорошего места, не получит футболку и т.п. Но тем не менее ни один из 5000+ членов сообщества не дал ни одной подсказки (ну или хотя бы из 30+ человек, которые это видели и знали ответ). Мне такой результат уже давно кажется закономерным и я попробовал объяснить его в двух словах. Теперь попробую чуть более подробно. Заранее прошу прощения у людей, которые в это понятие вкладывают не то, что я. Я лишь хотел изложить свой взгляд.

С 06.08.2011 по 17.08.2011 в Севастополе на базе Севастопольского Национального университета ядерной энергии и промышленности пройдет II-я Международная летняя школа программирования. Планируется 7 рабочих и 3 организационных дня. В каждый из рабочих дней проводится лекция, пятичасовой контест, разбор задач. Вечером море :). Важная информация: практические туры проводятся на личных ноутбуках участников. Более подробная информация на официальном сайте школы http://issps.org.ua. Регистрация открывается с 6-го июня 2011 года. Контактный телефон +38-068-926-15-61. Контактный e-mail: keem.mss@gmail.com

Медали получили следующие команды:

1. Университет Чжэцзян, Китай (8 задач)
2. Мичиганский университет, США (8 задач)
3. Университет Цинхуа, Китай (7 задач)
4. Санкт-Петербургский государственный университет, Россия (7 задач)
5. Нижегородский государственный университет, Россия (7 задач)
6. Саратовский государственный университет, Россия (7 задач)
7. Университет Эрлангена-Нюрнберга, Германия (7 задач)
8. Донецкий национальный университет, Украина (7 задач)
9. Ягеллонский университет, Польша (7 задач)
10. Московский государственный университет, Россия (7 задач)
11. Уральский государственный университет, Россия (7 задач)
12. Университет Ватерлоо, Канада (7 задач)

Все результаты можно увидеть здесь.

Здесь пойдет речь немного не о том спортивном программировании, к которому многие привыкли. Недавно,
на Codeforces был проведен экспериментальный раунд Unknown Language Round #1.
На нем участникам было предложено решить несколько несложных задач (первая,
вторая, а вот и все
остальные). Особенность раунда — задачи можно решать только на одном языке программирования, который
не известен участникам до начала раунда. Было анонсировано, что язык не является
mainstream языком. Иначе говоря, участникам предлагалось за 2.5 часа соревнования на скорость разобраться
в незнакомом языке и решить задачи на нем.