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

Спешим поделиться с вами новостью: 29 октября 2012 мы запустили соревнование для программистов под названием Russian AI Cup 2012: CodeTanks! Нет, здесь вам не надо будет решать алгоритмические задачи на скорость — в этот раз участникам предстоит написать искусственный интеллект для танка и принять участие в сражениях.

Всем привет! В сентябре прошла международная олимпиада по программированию, IOI 2012. И мы, сборная России, на неё весьма успешно съездили, как вы могли видеть.

Я — Макс Ахмедов. Мне предложили поделиться с общественностью, что представляют собой подобные соревнования и какие задачи нам приходится решать. Я расскажу о последней задаче второго тура «Jousting Tournament». Английский вариант условия можно найти здесь. К слову, это наиболее простая из трёх задач в тот день :-)

Легенда

В задаче идёт речь о церемонии обручения герцога Лодовико Сфорца, наместника Милана, и герцогини Беатриче д’Эсте, произошедшей в 1491. Организовывать празднества и управлять культурной программой герцог пригласил своего хорошего друга Леонардо да Винчи, который ему предложил, в частности, устроить шикарный рыцарский турнир.

И вот, к началу празднеств оказалось, что вовремя прибыли все рыцари, кроме одного, который опаздывает, но не настолько сильно, чтобы помешать проведению турнира. По случайному совпадению, этот рыцарь был фаворитом толпы, и все сражения с его участием пользовались большой популярностью. Леонардо знает расписание боёв турнира и то, как будут выбираться рыцари для участия в них, и он хочет слегка повлиять на ход турнира таким образом, чтобы рыцарь-фаворит поучаствовал в как можно большем количестве сражений. Так хитрый пиарщик Леонардо собирается увеличить значимость события.

Такая вот захватывающая история.

Сегодня ровно в 16.00 по Москоскому времени закончился Московский этап международной олимпиады по программированию acm icpc.
Как обычно, особо отличились команды от МГУ и Физтеха, подробнее о выходе команд в полуфинал, который состоится в Санкт-Петербурге можно почитать на сайте acm МГУ. Желам удачи и успехов нашим парням!
P.S. А так же девушкам, которые так же входят в состав некоторых команд.

Впервые в истории международный финал крупнейшего, самого популярного и наиболее признанного сообществом конкурса информационных технологий Imagine Cup 2013 приходит в Россию. Это настоящая международная интеллектуальная олимпиада открывающая участникам дорогу в большую успешную карьеру. Участвуя в Imagine Cup 2013, вы не просто получите диплом или медаль, или какой-то приз, вы получите возможность показать себя перед руководителями ведущих IT компаний мира.

Прошел первый раунд отбора участников в школу программистов HeadHunter, анонс на хабре
Где после заполнения анкеты предлагалось решить 5 задачек

На достаточно престижном соревновании TopCoder Open первое место в категории «Алгоритмы» занял Егор Куликов. Этот программист работает в компании «Яндекс», и ранее он уже занимал призовые места на разного рода конкурсах программистов.

В этом году Imagine Cup будет вдвойне замечательным! Во-первых, международный финал будет проходить в России, в Санкт-Петербурге, летом 2013 г. (и у российских студентов будет намного больше шансов в них поучаствовать). Во-вторых, сами соревнования в этом году существенно обновились и стали намного лучше! Подробности — ниже!

Яндекс знает. Телеканал Россия 24 знает. Даже на Первом канале информация имеется. А мы тут сидим и молчим всем бложиком!
Каждый из участников IOI 2012 от России привёз по золотой медали!

Если кто не в курсе, то IOI – это один из самых престижных в мире ежегодных конкурсов по программированию, который проходит под патронатом UNESCO и IFIP. На соревновании команды из разных стран мира, состоящие из четырех участников, на протяжении двух дней решают алгоритмические задачи.

Россию на олимпиаде этого года представляли Максим Ахмедов и Олег Иванов из Москвы, Егор Суворов из Санкт-Петербурга и Алексей Гордеев из Перми. Все они являются победителями Всероссийской олимпиады школьников по информатике этого года. Их сопровождали бессменные руководители нашей сборной Кирюхин Владимир Михайлович и Цветкова Марина Серафимовна.

Для интересующихся не составит труда найти информацию о заданиях (для этого есть официальный сайт), ходе олимпиады (тут, например), да и вообще почти о любых аспектах меропрятия (пресс-релиз SnarkNews, таблица командного зачёта, да и вообще что угодно — поисковик в помощь :)). Я же под катом постараюсь хоть чуть-чуть рассказать о самих победителях, а точнее, дать представление о том, сколько всего разного было на их пути к этой олимпиаде.

10 сентября 2012 года завершился чемпионат по программированию Russian Code Cup 2012. Подробный рассказ о том, как все происходило, публиковался ранее, а сегодня мы разберем задачи, которые были предложены финалистам. Их было всего шесть, и каждая из них — отдельная интересная история:

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

На решение этих задач выделялось три часа. Единственным решившим пять задач из шести оказался победитель Russian Code Cup 2012 Владислав Епифанов. Чуть менее половины финалистов решили по четыре задачи. Первые три задачи сделали почти все. Задачу про колоду карт правильно решил только один Евгений Капун. Второе место на турнире заняла Наталья Бондаренко, решившая четыре задачи быстрее других и с меньшим числом попыток.

В минувший понедельник завершился уже второй по счету пятимесячный марафон Russian Code Cup 2012. Первое место занял Владислав Епифанов из Нижнего Новгорода, сохранив первую позицию с отборочного и квалификационного туров, второе место заняла Наталья Бондаренко, доцент Саратовского государственного университета — одного из лидеров в подготовке программистов высочайшего класса. В этом году третье место занял Егор Куликов. Поздравляем победителей!



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

UPDATE:
Небольшой отчетный видеоролик c Russian Code Cup 2012.

• Цифры и факты
• Как проходил турнир
• Трансляция, техника, интернет и другие организационные моменты
• Содержательная часть: круглые столы и панельная дискуссия
• Интерактивные развлечения на площадке и культурная программа
• Сильнейшие программисты и их трофеи
• Планы на 2013

Итак, оглашены результаты Djangodash 2012. 48 активных команд, 48 часов и 6873 коммита, а победителями стали:

Первое место команда BUSI-TEC Industries с проектом Busitizer (демо). Приложение добавляет Гэри Бьюзи в фотографии в Facebook.

Второе место команда UFO с проектом EasyNotice (демо). Приложение выводит фотки из instagram, flickr и google картинок существующих чудес свет в сгруппированном виде.

Третье место — WebRiders с проектом Lemidora (демо). Приложения для того, чтобы делиться фотками с друзьями, можно накидать фотки на рабочий стол приложения и отправить ссылку на него друзьям.

Полная таблица результатов — djangodash.com/judging/2012/results

Я тут написал статью Проблема «двух и более учителей». Первые штрихи, пытаясь показать одну сложную нерешенную проблему. Но первые штрихи оказались немного за сложными. Поэтому я решил для читателей немного разжевать теорию. Увы, сейчас видимо учат/(учатся ?) несколько шаблонно — типа как для каждой задачи свои методы.

Так мне указали, что для задачи классификации — нейронные сети (обучение с учителем), генетические алгоритмы (обучение без учителя) — задача кластеризации, а еще есть обучение с подкреплением (Q-обучение) — как задача агента, который бродит и что-то делает. И вот такими шаблонами многие и судят.

Попробуем разобраться, что дает применение нейронных сетей, как некоторые заявляют, к задаче которую они не могут решить — а именно к обучению с подкреплением.

И заодно проанализируем диссертацию Бурцев М.С., «Исследование новых типов самоорганизации и возникновения поведенческих стратегий», в которой не больше не меньше красиво сделано именно применение простеньких нейронных сетей в задаче обучения с подкреплением.

В двух предыдущих статьях я по касательной затронул проблему, которую назвал проблемой «двух и более учителей»:

1. Модель функционального разделения сознания и бессознательного. Введение
2. Модель проявления сознания или ИНС без эффекта забывания

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

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

Было время, когда я был фанатом игры в Цивилизацию. Надо сказать, что её первые версии были наиболее интеллектуальны, а в версии после Civilization II: Test of Time можно вообще не играть — они испортили важную интеллектуальную начинку. Поэтому совсем не удивительно, что ниже я предложу компьютерно сыграть в этюд по этой игре.

Важно отметить, что устраивают турниры с подобными сценариями, например, ICFPC 2012 с краудсорсингом и нейронными сетями, играя в игру Supaplex. Это тоже интересная задача, но в ней не возникает проблемы «двух и более учителей». Поэтому цель этой статьи понять когда же эта проблема возникает.

upd. Кажется, первые штрихи оказались несколько сложноваты. Прошу для понимания прочитать предваряющую статью Обучение с подкреплением на нейронных сетях. Теория.

Согласно расписанию, вчера позавчера состоялся последний день финала VK Cup 2012, а у меня появилась возможность поделиться впечатлениями о прошедшем мероприятии.

Пишу я в большей степени от себя и от лица проекта Codeforces, хотя с участниками я успел пообщаться, внимательно прочел все комментарии — так что, наверное, где-то выражу и общее мнение.

Чемпионат по программированию VK Cup 2012 задумывался как полезное и интересное мероприятие именно для молодых программистов, и, судя по отзывам, нам удалось его таковым сделать. В правилах чемпионата значился необычный пункт «возраст не менее 14 и не более 23 полных лет на момент регистрации». Именно таким образом получилось вырваться из круга профессиональных, опытных участников, сделать соревнование для школьников и студентов. Например, среди финала многие в первый раз участвовали в подобном мероприятии.

Данный материал изначально был подготовлен в качестве раздела статьи “Первые шаги в Robocode”, но я решил вынести его, т.к. он значительно увеличивал размер и без того большой первоначальной статьи и не является базовым и необходимым для осуществления первого шага. Если вы сразу заинтересовались вторым шагом или постепенно доросли до него, то прошу под кат.

Я пишу эту статью по просьбам в комментариях к статье “Как я стал чемпионом Robocode” и продолжая начатое в ней дело по привлечению внимания к Robocode русскоговорящих разработчиков. Robocode — это игра для программистов, в которой задача заключается в разработке системы управления танком. Для затравки приведу несколько роликов, чтобы показать о чём вообще пойдёт разговор:

• http://www.youtube.com/watch?v=dqHmp_kMz-U — Дуэль
• http://www.youtube.com/watch?v=eqlPbtO3rQY — Дуэль
• http://www.youtube.com/watch?v=zx7xFJiBGZQ — Схватка, >2 роботов, каждый за себя
• http://www.youtube.com/watch?v=EJPskFGvGi8 — Схватка, стоит обратить внимание на робота Portia (бирюзовый) — это один из лучших бойцов в этой категории

Всего несколько часов назад начался конкурс ICFPC-2012, который продлится все выходные. Я решил перевести задачу для этого конкурса в надежде, что кто-то из заинтересовавшихся людей успеет принять участие.

Задача вполне понятная, так что дерзайте.

В задачу вносились изменения: вода, телепорты, борода и суперкамни.

Шахты с лямбдами обнаружены в Шотландии! Ваша задача — прочитав карту шахты суметь составить программу для робота.


Ссылка на красивый симулятор: icfp.stbuehler.de/icfp2012

В прошлую субботу, 16 июня, завершился отборочный раунд Russian Code Cup 2012. Задачи отборочного раунда посложнее, чем были на квалификации – ну на то он и полуфинал. Я уже рассказывал о том, что предлагалось участникам на предыдущих онлайн-турах, разбирал подробно варианты решений (Q1, Q2, Q3).

В отборочный раунд было приглашено 600 человек. 434 человек смогли решить хотя бы одну задачу. Все задачи решили только двое. 50 лучших перешли в финал. Всего за 3 часа тура было отправлено в проверяющую систему 3190 решений.

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

MetaQuotes Software Corp. ежегодно проводит чемпионат по автоматическому трейдингу для тех, кто хочет своими профессиональными навыками и умом заработать $80 000. Победители прошлых Чемпионатов своим примером доказали, что это возможно.

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

Как известно интересующимся, больше месяца назад прошёл ABBYY Cup, студенческая online-олимпиада по спортивному программированию. Тем, кто не слышал о ней совсем ничего, рекомендую сначала прочитать этот топик.

В каждом туре мы предложили участникам по 6 задач, за каждую можно было получить по 100 баллов, но для легкого дивизиона Codeforces сочинил дополнительную седьмую, чтобы развлечь тех участников, которым легкий дивизион начинает казаться очень легким.

Как и в прошлом году, решения оценивались с помощью автоматических тестов разного уровня сложности. На ABBYY Cup было несколько групп тестов, в легком дивизионе – две, в сложном – три. Разные тесты нужны, чтобы отличать тех, кто сделал задачу хорошо, от тех, кто сделал очень хорошо. Отработал код в заданных рамках при 20 входных значениях? Получите-ка на вход 50, посмотрим :)

Помимо этого была дополнительная система оценки. Если человек пытался решить задачи много раз и отправлял, скажем, 10 раз неправильное решение и на 11-й отправил правильное, он будет ниже в рейтинге, чем человек, который решал дольше, но отправил решение, которое сразу прошло все тесты.