Демон Максвелла(2009г)

ДЕМОН МАКСВЕЛЛА

Ура! очередной конкурс успешно прошел!
Очный этап состоялся 09.01.10 на базе СЮТ. И надо сказать, что по общему мнению участников и судей, удался! Он прошел в теплой дружественной обстановке, и настолько напряженной, что участники отказались даже от предложенного администрацией чая с рулетом! :-)

Как всегда не обошлось и без накладок. Каким-то образом на сайте СЮТ было установлено время начала конкурса не в 11 а в 12! Кто-то заболел, кто-то проспал. Пришлось обзванивать участников и перенести начало конкурса аж на 45 минут! Сказалась и низкая температура, и плохо ходящие автобусы, и длинные праздники тоже :-). Однако все трудности были успешно преодолены, и конкурс начался!

Чтобы все было понятно, условия заочного этапа c основной преамбулой конкурса сначала нужно посмотреть здесь:
" страничка во время предварительного этапа"

На очном этапе были предложены следующие изменения:

Во первых предложена новая DLL, которая позволяла открывать заслонку на произвольное число условных едениц от 0 (закрыта) до 25(открыто половина стенки). Желающие могут скачать DLL ЗДЕСЬ и распаковать ее вместо той, что была в проектах на заочном этапе.

Конкурсантам было предложено написать три варианта подпрограммы управления.
В первом учитывается только условная разность температур
Во втором учитывается только разность количества атомов (так как это эквивалент давления, этот вариант назвали "Демон Бойля-Мариотта" в честь соответствующего закона физики)
В третьем учитывались обе цифры(температура+давление).

Таким образом, победитель определялся беспристрастным жюри по сумме 4-х цифр. :-)

Итак все трудности были успешно преодолены, задания понятны и участники приступили к работе. Минут через двадцать после начала работы, когда результаты по температуре приближались к 600-700 попугаям, Господин Печеницын заявил, что ему при помощи подпрограммы длиной в 2-е строчки удалось достичь результата 1500! Причем этот результат достигался в первые 80 ходов при помощи ошибки в основной функции! (функция не возвращала вообще никакого значения)

Такой результат всех потряс (особенно организаторов конкурса :-) ) Шутка-ли, практически без усилий можно выиграть все подряд! Однако организаторы не сдались и в течении 5-и минут причина была обнаружена и баг исправлен. Оказалось, что к такой ситуации привела целая цепочка ошибок.
Во-первых, в начальный момент времени все молекулы начинают двигаться с разными скоростями вправо и вниз (это было сделано для упрощения алгоритма моделирования и усиления зрелищности. Первоначально даже рассматривался взрыв, появление всех молекул из одной точки)
Во-вторых, в заключительном проекте DLL оказалась по ошибке отключена проверка на максимально возможное открытие (25)
И в-третьих, совершенно случайно у Печеницына в проекте из-за ошибки (отсутствие присвоения значения) Функция возвращала большое число (теоретически могло оказаться любое и, кстати, такой "фокус" работал не у всех).

Баг был исправлен, но было решено оставить движение как есть. Таким образом почти у всех при максимальном открытии в первые ходы можно было получить 631-о "халявное" очко :-). Так как дальше все равно нужно было попытаться увеличить приимущество "правильным" алгоритмом, Конкурс продолжился.

Еще через 15 минут у конкурсанта, работавшего на СИ, возникли подозрения, что у него заслонка не открывается на полную величину. Проверили - точно! Все вроде нормально, DLL новая, а работает как старая! еще 10 минут организатор пил валидол и искал баг :-) Проверили все, и когда дошли до отладки DLL, оказалось, что все работает! Тут-то до организатора и дошло, что у конкурсанта проект настроен так, что EXE-шник создается в другой директории, а там лежит.....ПРАВИЛЬНО! Старая DLL! :-) В общем как всегда в очередной раз подтвердилась истина, что чудес в программировании не бывает! Вот иной раз кажется, ну вот оно! Ан нет, оказывается опять сами виноваты!

Так что конкурсанты умело держали администрацию в напряжении в течении практически всего конкурса. И уже "под занавес" один из конкурсантов объявил, что ему удалось хакнуть саму DLL, найти в ней адрес с очками, что теоретически, позволяет поставить там любое число! Так как по правилам конкурса, такие приемы не допускаются, никто такой возможностью не воспользовался. Но сам факт указывает на достаточно высокий уровень конкурсантов (и их высокие моральные принципы) :-).

Картинки с очного этапа:

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

Процедура награждения

Ну а после награждения состоялся заинтересованный "разбор полетов", в ходе которого конкурсанты совместно с администрацией обсудили различные алгоритмы решения данной задачи, поделились опытом управления демонами различных видов, наметили перспективы дальнейшего повышения повышаемости :-)

Разбор полетов.....

ЭЭХ! При всем том, что творилось на конкурсе не совсем понятно, почему не все воспользовались халявными очками. (лично у меня за счет начального "броска" получился по температуре 631 попугай!) тем более странно, что автор этой идеи ею не в полной мере воспользовался. Странная история...

Некоторые так и остановились только на этом "рубеже". Но победу одержали те, кто пошел дальше. А дальше уже было труднее. Для получения значительного результата нужно было реализовать(и отладить) несколько веток программы, что является достаточно сложной задачей. Тем более в условиях ограниченного времени.

Но ведь на то и был почти месяц заочного этапа! Можно было черта (демона) лысого отладить! :-)

Кроме "честного" алгоритма, основанного на прогнозе и расчете, некоторые попробовали алгоритм подбора параметров генератора случайных чисел для управления. И это был сомнительный и совсем не легкий путь (хотя и более доступный). Алгоритм основывался на том, что по случайному закону можно подобрать такое опорное число, чтобы результат был подходящим. Для такой модели как наша, это допустимо, хотя в реальной жизни такому алгоритму доверия нет!

И все-таки самым результативным на наш взгляд стал-бы "честный" алгоритм, реализованный полностью, и победители пытались изобразить именно его. Вот как выглядят программы победителей:

Беглый анализ, кстати, не очень веселую картину показывает. Так, например, у Климова, несмотря на сложный алгоритм, на самом деле работает только ветка основанная на начальном броске :-) хотя из этого алгоритма выжат максимум во всех трех заданиях.

Ну а Павленко хотелось-бы пожелать более простых алгоритмов :-) которые и отладить проще.

P.S.
Последние 30 минут удалось самому пощупать алгоритм. Я подошел по-честному. Ну сначала взял "халявные" 631-о очко. :-) А далее сделал тест на прохождение ворот (при размере ворот в 1 попугай). И посчитал параметры молекул которые на текущем ходе могут просочиться в правую и левую части.
Сначала реализовал ветку, которая сравнивает энергию просочившихся вправо и влево, и если результат улучшается, то открывает, а иначе закрывает! Результат подскочил до 874! Еще не первое место, но уже как минимум второе :-)
После этого добавил ветки, которые анализируют случаи, когда только в одну сторону просочились. Если влево, то открываю, если средняя энергия меньше чем слева, а если вправо, то если больше. И результат сразу 1560! ВОТ ТАК! :-).
Попробовал то же самое для размеров ворот 2 и 3. Получил 1450 и 1340 соответственно (то есть результат хуже). Но при размере 1 часто вообще ни одна молекула не просачивалась, вот для такого случая можно было бы пошире открыть и проверить. В общем, явно есть куда расти. Думаю до 2000 запросто догнать можно было бы! И кстати у меня намного проще программа получилась. правда-правда. :-)

Так что анализ показывает, что еще есть куда расти :-)

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

Кроме того, администрация сайта выражает благодарность всем работникам СЮТ, которые приняли участие в организации конкурса.