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

Некоторые хабраюзеры уже участвовали в олимпиадах по программированию.
Например, в мае проходил ABBYY Cup. Сейчас на том же сервере проходит олимпиада факультета управления и прикладной математики МФТИ для школьников. Могут участвовать и студенты, но только вне конкурса, тем более, что сейчас сессия. Для студентов будут другие контесты.

Победители получат призы и сувениры от факультета и спонсоров. Турнир доступен до 15 января.

Турнир привлекал своей простотой и собрал широкую аудиторию. Идея пришлась по вкусу и старшеклассникам и умудренным опытом гуру, помнящим еще чемпионат мира по компьютерным шахматам 1972-го года.

Используемые лидерами алгоритмы были примерно одинаковые, базовых было два — поиск в ширину (BFS), для определения ближайшего пути к дальним целям и минимакс в ближнем бою. Дьявол скрывался в правильной методике выбора целей и тонкой настройке деталей.

После четырехмесячного перерыва Unknown Language Round возвращается на Codeforces: четвертый раунд этого типа состоится в воскресенье 20 ноября в 19:00 по московскому времени.

Соревнования этого формата предлагают участникам решить десяток задач за три часа времени. Все было бы довольно обычно, если бы не одно «но»: эти задачи можно решать только на одном языке программирования. Каком? О, это будет известно только в самом начале раунда. В том-то и прелесть формата, что выбирается язык, неизвестный большинству участников, и за отведенное время нужно не просто решить как можно больше задач, но еще и выучить заданный язык в объеме, достаточном для их реализации. Задачи подбираются простые и не требующие продвинутых алгоритмов, чтобы можно было сосредоточиться на новом языке.

На трех предыдущих раундах неизвестными языками оказались Tcl, Io и Pike; я участвовала только в первом, и, смею заверить, это было весело. В этот раз я раунд провожу и приглашаю всех в нем поучаствовать — особого опыта спортивного программирования для этого не нужно, а интересно будет (читатели моего блога здесь уже знают, какая я любительница языков позатейливее, а для такого случая грех было бы не подобрать что-нибудь особенное).

Для полноты картины приведу хабраанонс предыдущего раунда.

В этой заметке я расскажу как написать довольно неплохого бота для Google AI Challenge. Примечательно, что сложные технологии связанные с ИИ не понадобятся, а базовая реализация умещается в тысячу строчек кода на языке C++. Сами методы в совокупности могут быть рассмотрены как некоторый Generic алгоритм, и на базе них можно построить бота, учитывающего некоторые стратегические особенности, который возможно будет играть еще лучше. В любом случае — хороший «быстрый старт» для тех, у кого пока ничего не получилось.

Многие на Хабрахабр приняли участие в Google AI Challenge. Скачали инструменты для локального тестирования и уже ощутили прелесть и удобство их:

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

Сидел я так, сидел и в один прекрасный день задумался, а почему бы не сделать мини инструмент, который бы все это объединял в одном месте и забыть про консоль.

Краткое описание:
— один раз вводишь тесты — проверяешь на всех тестах с помощью одного клика;
— включает исходный код из библиотеки;
— создает юнит-тесты при архивировании задачи;
— специальная поддержка TopCoder (работает с plugin'ом moj) и Codeforces (парсит html странички и сохраняет sample-тесты).

Полное описание и ссылка для скачивания — тут.

На хабре уже имеется много информации по этому состязанию, однако вся она освещает отдельные моменты реализации, но не картину в целом. Постараюсь исправить это положение как можно более кратко, но в целом.
Данное описание предназначено для тех, кто что-то слышал о данном мероприятии, но всё желание что-то сделать отбила необходимость разбираться в тонкостях реализации. Пост состоит частично из перевода материалов с официального сайта, частично из анализа стратегий других ботов и чистой логики. Также в конце поста будет ссылочка на PHP-бота (чуть сложнее чем из starter-pack), который позволит вам попробовать собственные силы дописав имеющийся код. Официальный сайт состязания: aichallenge.org

Продолжаем разбираться в правилах проходящего сейчас турнира 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.