Комментарии 77
Четвёртый. Увы, пропустил большую часть веселья и начал только после объявления о продлении. Интересно услышать отчёты участников, приславших топовые два решения (875 и 89b).
мне бы вообще интересно было узнать о стратегиях первой всей пятерки. результаты у всех достойные, а подходы различаются сильно, отталкиваясь от беглого взгляда на код.
Стратегии ладно, в конце концов есть код. Любопытно, кто как шёл к решению.
Мою стратегию смотрите в README, хоть там нет многих деталей. А остальные четверо
избрали кривую олимпиадную стёжку: сначала посчитаем всё, залипнув на месте,
а потом разом выплюнем лучший найденный путь. У меня тоже был соблазн, и может, я б дёрнулся ещё туда, зайдя в тупик, — но время, время.
Мою стратегию смотрите в README, хоть там нет многих деталей. А остальные четверо
избрали кривую олимпиадную стёжку: сначала посчитаем всё, залипнув на месте,
а потом разом выплюнем лучший найденный путь. У меня тоже был соблазн, и может, я б дёрнулся ещё туда, зайдя в тупик, — но время, время.
Это да, можно вполне целую статью напилить на эту тему, причём толстую.
К слову, из-за проблемы непредсказуемого пропуска хода в боевом (с воркерами) режиме, залипание это вынужденная мера. Серьёзно, я даже когда оставил боту на текущий расчёт 30 мс из 100, всё равно в один из сотни запусков нештатный пропуск хода случался. Поэтому и я позже пришёл к идее «олимпиадности» решения и неизбежности прогрева, но уже не успел её запилить до дедлайна.
Да и хотел изначально сделать более приближенного к реальности бота — конкретные условия конкретными условиями, но всё же, блин, карта может в реале быть иного размера, игрок может находиться в нескольких клетках под падающей бомбой или в нескольких клетках на пути ножниц… то есть бабочек, и ему нужно бежать, бежать, сразу бежать. Или может если он будет стоять то упустит возможность сожрать какие-то близкие алмазы, пока всё изначально падает-бежит в уровне и всё такое.
Так что сейчас в предварительных результатах моё 7-е чудо тоже бежит сразу с места стартуя и размышляя на ходу. И доступное процессорное время в тике для него решающе важно. Ридми не делал, зато с именами переменных порядок, комментарии семантические присутствуют и всё такое.
Да и хотел изначально сделать более приближенного к реальности бота — конкретные условия конкретными условиями, но всё же, блин, карта может в реале быть иного размера, игрок может находиться в нескольких клетках под падающей бомбой или в нескольких клетках на пути ножниц… то есть бабочек, и ему нужно бежать, бежать, сразу бежать. Или может если он будет стоять то упустит возможность сожрать какие-то близкие алмазы, пока всё изначально падает-бежит в уровне и всё такое.
Так что сейчас в предварительных результатах моё 7-е чудо тоже бежит сразу с места стартуя и размышляя на ходу. И доступное процессорное время в тике для него решающе важно. Ридми не делал, зато с именами переменных порядок, комментарии семантические присутствуют и всё такое.
etc
Правда там кучу лишнего временного/старого закомментированного кода и пару старых функций не выкинул, дебаг недочищен, — думал успею что-то ещё путное дописать и красоту навести, но чутка не хватило времени, как ж без этого.
У меня ограничение 50 мс и 1-2 фрейма таки теряется, судя по логам — но бот умеет ликвидировать рассинхрон.
Кстати, сиды, на которых решения не могут позволить себе залипнуть на 600 ходов, всё же существуют (хотя встречаются редко и в тестовый набор не попали). Например, 1711738677 и 1907642739. Игроку там необязательно бежать с первого же хода, но и долго оставаться на месте тоже опасно.
А 597493a7a4e2889d0388f597 и 597496daa4e2889d0388f598 — дубли.
Интересно, процессор работал в тесте на максимальной частоте? Снизил частоту до 2300 MHz, только тогда получил такой же результат как в тестировании…
Переиграл несколько уровней на i5-2400 (чуть производительнее Xeon E5-2680 v2, если верить тестам). В режиме performance ведёт себя чуть лучше, чем в powersave (впрочем, они оба динамические), но всё равно гибнет, например, на сиде 113691004 в нижнем правом углу доски. Решение чувствительно к пропуску хода?
Именно
Без пропусков разница больше чем в 2 раза,
однопоточный рейтинг у E5-2680 v2 даже выше чем у i5-2400
www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i5-2400+%40+3.10GHz
www.cpubenchmark.net/cpu.php?cpu=Intel+Xeon+E5-2680+v2+%40+2.80GHz
www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i5-2400+%40+3.10GHz
www.cpubenchmark.net/cpu.php?cpu=Intel+Xeon+E5-2680+v2+%40+2.80GHz
Спасибо, что обратили наше внимание на проблему: мы по ошибке проводили тестирование не на том типе AWS-инстанса. Вместо c3.large было m3.large. Важная опечатка! Все решения будут перетестированы на c3.large, и результаты будут опубликованы незамедлительно.
Да уж, 2,8 ГГц вместо не тех 2,5 ГГц должны дать заметную разницу. И кстати отжельный интерес представляет и то как решения справлялись с задачей на том и другом типе процессоров, раз уж уже протестировано.
А, да, и ещё интересный вопрос ко всем. Кто сколько времени от фрейма 100мс позволял считать ходы своим решениям?
Просто в однопроцессном (-p) режиме не было никаких проблем, когда разрешал считать своему 80 мс из 100, зная, что возможное лишнее время от разрешённых 80 мс не уйдёт более +5..10 мс. Но в «боевом режиме» такой формат обсчёта приводил к непредсказуемым пропускам хода (при этом никаких явных вылетов за разрешённые рамки не было), и для стабильности пришлось урезать доступное время расчёта до, блин, 30 мс из 100.
Не знаю, может что делал не так, но очень неприятный момент, и не совсем понятно, что же именно мешает при запуске в воркер режиме.
А суть кода главного цикла примерно такая:
где ai.frameCalcTimeout пришлось ставить 30 мс.
Признателен, если кто-то пояснит, в чём тут может быть проблема, и как «вернуть» в пользование время порядка 80-90мс из 100.
Просто в однопроцессном (-p) режиме не было никаких проблем, когда разрешал считать своему 80 мс из 100, зная, что возможное лишнее время от разрешённых 80 мс не уйдёт более +5..10 мс. Но в «боевом режиме» такой формат обсчёта приводил к непредсказуемым пропускам хода (при этом никаких явных вылетов за разрешённые рамки не было), и для стабильности пришлось урезать доступное время расчёта до, блин, 30 мс из 100.
Не знаю, может что делал не так, но очень неприятный момент, и не совсем понятно, что же именно мешает при запуске в воркер режиме.
А суть кода главного цикла примерно такая:
function getNow() {
return Date.now() * 1000;
//var ht = process.hrtime();
//return (ht[0] * 1000000 + ht[1] / 1000)|0;
}
// ...
exports.play = function*(screen)
{
// ...
var ai = new DashAI(screen);
var timeStart = getNow();
var timeTill = timeStart + (ai.frameCalcTimeout * 0.5)|0;
ai.think(timeTill);
while (ai.frame < ai.framesMax) {
var move = ai.getNextMove();
ai.think(timeTill);
yield move;
timeStart = getNow();
timeTill = timeStart + ai.frameCalcTimeout;
}
}
где ai.frameCalcTimeout пришлось ставить 30 мс.
Признателен, если кто-то пояснит, в чём тут может быть проблема, и как «вернуть» в пользование время порядка 80-90мс из 100.
А под какой осью, и что с энергосбережением? ;)
Под любой, полагаю. Тестировалось под виндой семёркой и у товарища под макосью. Нестабильность проявляется одинаково примерно. И это при полном контроле за фактическими временами выполнения обдумывания ходов, все без исключений укладывались с огромным запасом (20мс+) в 100мс.
А каким образом это может быть связано с энергосбережением (опять же при учёте что мы фактические тайминги измеряем)? Процы на экспериментальных системах имели по более чем 2 физических ядер и не были заняты ничем иным.
А каким образом это может быть связано с энергосбережением (опять же при учёте что мы фактические тайминги измеряем)? Процы на экспериментальных системах имели по более чем 2 физических ядер и не были заняты ничем иным.
'use strict'; /*jslint node:true*/
exports.play = function*(screen){
let frame = 0;
while (true) {
let time = Date.now();
while (Date.now()- time < 70) {}
yield ' ';
frame++;
console.info(120-Math.floor(frame/10));
}
};
Предполагаем, что нам достанется 70 мс.
В режиме высокой производительности счетчик кадров решения совпадает со счетчиком управляющего скрипта.
В экономии энергии сразу начинает круто отставать. В сбалансированном отстает, но на небольшую величину.
windows 7, core i7 4770
exports.play = function*(screen){
let frame = 0;
while (true) {
let time = Date.now();
while (Date.now()- time < 70) {}
yield ' ';
frame++;
console.info(120-Math.floor(frame/10));
}
};
Предполагаем, что нам достанется 70 мс.
В режиме высокой производительности счетчик кадров решения совпадает со счетчиком управляющего скрипта.
В экономии энергии сразу начинает круто отставать. В сбалансированном отстает, но на небольшую величину.
windows 7, core i7 4770
если уменьшить частоту до 75%, что приближается к тестовому серверу, совпадает уже только при 60 мс. Но не 30
BegeX, интересное наблюдение, спасибо.
А что касается дела — так всё равно нас обманули :) Обещали, у вас будет 100-мс-минус-одна-пикосекунда на размышления о следующем ходе, но нет.
А что касается дела — так всё равно нас обманули :) Обещали, у вас будет 100-мс-минус-одна-пикосекунда на размышления о следующем ходе, но нет.
Ну не совсем уж обманули))
на все про все, то бишь на ход + отрисовку, как раз идет ровно 100 мс (99-101). Как в условии и написано: «Состояние игры обновляется раз в 100 мс».
НО опять же в режиме «высокая производительность». В экономии энергии (или сильном снижении фиксированной частоты процентов эдак до 20) прыгает 70 — 235…
'use strict'; /*jslint node:true*/
exports.play = function*(screen){
while (true) {
let time = Date.now();
yield ' ';
console.info(Date.now()-time);
}
};
на все про все, то бишь на ход + отрисовку, как раз идет ровно 100 мс (99-101). Как в условии и написано: «Состояние игры обновляется раз в 100 мс».
НО опять же в режиме «высокая производительность». В экономии энергии (или сильном снижении фиксированной частоты процентов эдак до 20) прыгает 70 — 235…
'use strict'; /*jslint node:true*/
exports.play = function*(screen){
while (true) {
let time = Date.now();
yield ' ';
console.info(Date.now()-time);
}
};
Интересно, Алексей feldgendler, а в каком режиме работают те целевые конкурсные процессоры на Амазоне? Хотя мы наверное не хотели устраивать челендж на особенности такого-то процессора, но так получилось… )
А вообще, как насчёт формата следующего игрового конкурса с двумя машинами и взаимодействию по JSON API?
На одной сервер, реализующий это API, с игрой, которая (возможно, после обмена синхронизационными запросами) по команде старта от клиента или же самостоятельно, отвечая клиентам статусом со временем предстоящего запуска, начинает свой неумолимый ход жизни мира с метрономскими тиками.
На другой машине — игровой клиент, который будет это API использовать. Пытаться управлять своим игроком в этом мире, пытаясь набрать счёт.
Синхронизация решается достаточно просто, были б таймстампы в соотв. методах API.
Независимость работы машин очевидна.
В случае параллельной игры нескольких игроков в равные условия все могут быть легко поставлены, когда клиентские машины с решениями, например, размещаются в одном и том же ДЦ. Можно заодно устранить значимую часть лагов, поместив их в тот же ДЦ, что сервер, а можно в другой и сделать из (умеренных) лагов фишку.
На мой взгляд может получиться очень, очень интересный челендж, лишённый многих проблем одномашинного запуска и очень приближенный к боевым условиям.
А вообще, как насчёт формата следующего игрового конкурса с двумя машинами и взаимодействию по JSON API?
На одной сервер, реализующий это API, с игрой, которая (возможно, после обмена синхронизационными запросами) по команде старта от клиента или же самостоятельно, отвечая клиентам статусом со временем предстоящего запуска, начинает свой неумолимый ход жизни мира с метрономскими тиками.
На другой машине — игровой клиент, который будет это API использовать. Пытаться управлять своим игроком в этом мире, пытаясь набрать счёт.
Синхронизация решается достаточно просто, были б таймстампы в соотв. методах API.
Независимость работы машин очевидна.
В случае параллельной игры нескольких игроков в равные условия все могут быть легко поставлены, когда клиентские машины с решениями, например, размещаются в одном и том же ДЦ. Можно заодно устранить значимую часть лагов, поместив их в тот же ДЦ, что сервер, а можно в другой и сделать из (умеренных) лагов фишку.
На мой взгляд может получиться очень, очень интересный челендж, лишённый многих проблем одномашинного запуска и очень приближенный к боевым условиям.
Не участвовавшие в прошлом (этом) конкурсе будут поставлены в невыгодные условия.
Тогда будет больше проблем, а не меньше. Добавятся проблемы сети и особенности сетевого оборудования в конкретном датацентре.
Официальных конкурсов по игре JSDash больше не будет. Неофициальные, без призового фонда, участники могут, конечно, сами устроить. Но если Hola выделяет деньги на призовой фонд пару раз в год, то от меня как устроителя этих конкурсов ожидают разнообразия. В прошлый раз задача была совершенно другая, ничего общего. В следующий раз тоже будет другая.
Но я польщён и очень рад тому, что конкурс получился таким, что вам хочется продолжать.
Официальных конкурсов по игре JSDash больше не будет. Неофициальные, без призового фонда, участники могут, конечно, сами устроить. Но если Hola выделяет деньги на призовой фонд пару раз в год, то от меня как устроителя этих конкурсов ожидают разнообразия. В прошлый раз задача была совершенно другая, ничего общего. В следующий раз тоже будет другая.
Но я польщён и очень рад тому, что конкурс получился таким, что вам хочется продолжать.
Если брать в рамках одного ДЦ и понимать что больше 600 запросов в минуту от одного клиента точно не будет и одновременно сражаются, скажем, не более 8 участников, то о факторе сети можно практически забыть.
Да, конкурс получился на славу!
Да, конкурс получился на славу!
Алексей, а рассматривалась ли такая альтернативная идея контроля над зависанием и прочим «несанкционированным потреблением CPU» — нода с игрой и решением запускаются в одном процессе, но по команде специального второго примитивного процесса-раннера, который через 120+1 секунду кидает контролируемому процессу килл-сигнал и всё. Есть --log=log.json, хорошо, решение отработало нормально. Нет значит переело процессора любым способом. Естественно, требование «ничего нельзя require, в том числе пользоваться файловой системой (и как-либо взламывать движок игры)» остаётся в силе.
Конкурс отличный! Спасибо!
Хотелось бы еще «живой статистики», чтобы отправлять решения и видеть результаты сразу (или в течение часа, например).
Хотелось бы еще «живой статистики», чтобы отправлять решения и видеть результаты сразу (или в течение часа, например).
Конкурс хорош, спасибо!
Задача, главное, из общего ряда конкурсов выбивается, не напоминает о работе, многих заставила вспомнить школьные годы чудесные)). Ради такого не жалко было и с javascript разобраться. Очень странно, что так мало участников.
В общем, ждем новых!
Задача, главное, из общего ряда конкурсов выбивается, не напоминает о работе, многих заставила вспомнить школьные годы чудесные)). Ради такого не жалко было и с javascript разобраться. Очень странно, что так мало участников.
В общем, ждем новых!
А вот такой еще вопрос. Конкурсы эти же, всего скорее, не с благотворительной целью организованы (ну, или не только с благотворительной), а еще чтобы штат команды расширить. Как по опыту предыдущих мероприятий, есть смысл в такой вербовке?
Все решения были перетестированы, и результаты на GitHub обновлены.
Отлично!
А можно ли в дозабег до 50 сидов взять не пятёрку, а десятку? Интересно! Тут тоже результат заметно плавает и на большей выборке уверенней можно будет о силе решений (в группах 6-8 и 9-10) сказать.
А можно ли в дозабег до 50 сидов взять не пятёрку, а десятку? Интересно! Тут тоже результат заметно плавает и на большей выборке уверенней можно будет о силе решений (в группах 6-8 и 9-10) сказать.
Тогда чего бы не всех 67 взять на дозабег? Разрыв между двумя последними местами тоже совсем маленький :-P
Дозабег для пятёрки на 50 уровнях показал кое-что интересное. Чтобы всё было справедливо, поставил тестировать все решения на 100 уровнях (из которых 20 уже сделано). Больше сделать не успеем до заявленной даты окончательных итогов (31 августа).
Ого! Вот это масштаб, здорово! С интересом ждём результатов большой гонки.
Тысяча чертей! Что же могло к такому привести? ;)
Так и так пришлось бы тестировать все, — обещание:
> Мы оставляем за собой право увеличить число уровней (для всех участников)
habrahabr.ru/company/hola/blog/332176
> Мы оставляем за собой право увеличить число уровней (для всех участников)
habrahabr.ru/company/hola/blog/332176
Помогло, но не критично (с 3000 до 3700, без пропусков выдает больше шести, до победы далеко, но все же), пропусков много все равно, потери виртуализации, наверное. Видимо, надо было в расчете на это уменьшать глубину расчета хода или ставить костыль. Зато решительно не понятно, почему многие решения, наоборот, просели по очкам…
НЛО прилетело и опубликовало эту надпись здесь
Возможно это потому, что они на слабом железе не успевают сделать даже какого-то критического минимума за отведённые 100мс +- random(0, 1) * 60мс. Базовый расчёт до конца доходит, но случайные пропуски хода, фьють. Попробуйте ради интереса с -p флагом, может внезапно окажется, что большинство решений вполне годные. :-)
Честно говоря, эти странные непредсазуемые пропуски хода в воркер режиме полсилы решения отправили в ведро. =/
Уже при 50мс начинались значимые случайные… сбои синхронизации? Что-то начиналось. Даже при 40мс иногда. И бот ловил внеплановый пропуск хода, после чего остальные продуманные им ходы летели в печь. И из-за нестыковки того, какой он думает сейчас фрейм и какой в действительности фрейм, происходило вот это вот долбление о стены, умирание под камнями и прочее подобное.
PS: Ну и если, вдруг, тестирование будет решено производить в формате -p с контролем уже общего времени работы процесса игры = 120 +- 1 секунд (чтоб решения ну не могли «тупить» в зачёте) — то было бы вполне справедливо поправить решениям настройку «сколько можно думать» со слишком урезанных таймингов до 80мс. Наверняка такая настройка есть у многих вариантов. Или, не знаю, дать всем какой-нибудь «вторник допиливания», о котором объявить завтра. … Ну или оставить как есть, честно не знаю.
Честно говоря, эти странные непредсазуемые пропуски хода в воркер режиме полсилы решения отправили в ведро. =/
Уже при 50мс начинались значимые случайные… сбои синхронизации? Что-то начиналось. Даже при 40мс иногда. И бот ловил внеплановый пропуск хода, после чего остальные продуманные им ходы летели в печь. И из-за нестыковки того, какой он думает сейчас фрейм и какой в действительности фрейм, происходило вот это вот долбление о стены, умирание под камнями и прочее подобное.
PS: Ну и если, вдруг, тестирование будет решено производить в формате -p с контролем уже общего времени работы процесса игры = 120 +- 1 секунд (чтоб решения ну не могли «тупить» в зачёте) — то было бы вполне справедливо поправить решениям настройку «сколько можно думать» со слишком урезанных таймингов до 80мс. Наверняка такая настройка есть у многих вариантов. Или, не знаю, дать всем какой-нибудь «вторник допиливания», о котором объявить завтра. … Ну или оставить как есть, честно не знаю.
Конечно же, оставить как есть. Условия тестирования были объявлены заранее, и мы их придерживались (за исключением ошибки с типом инстанса, из-за чего сейчас идёт перетестирование). Изменить сейчас правила тестирования по сравнению с заявленными означало бы наказать тех, кто оптимизировал своё решение под то, что было объявлено.
Да, правильно. Да скорее это уже бурчание на то, что за дела в этом воркер режиме происходят, — сори за многобукв и в дцатый раз спасибо за классный конкурс.
Заголовок спойлера
Что ж там за магия синхронизации такая…
Это нормальное бурчание ) Полагаю, что многих тут беспокоят пропуски хода и непредсказуемое время на ход.
Мысль была, что дело еще может быть в сборщике мусора, которому тоже нужно процессорное время.
Я изначально потратил кучу времени на то, чтобы предусмотреть пропуски — холодный старт, проверка времени на ход, проверка времени на каждой ветке при поиске в глубину, расчет хода на случай его пропуска. Если время хода вышло, то возвращаю не лучший ход, а ход с учетом пропуска.
Но в конце решил, что это борьба с ветряными мельницами и все закомментировал. Оставил только сравнение моего мира с реальным для подгонки его к реальному в случае пропусков.
Судя по результатам, успешно прошел только 5 уровней, получив 41 место. Хотя сам тестировал на амазоновском сервере, аналогичном заявленному в условиях, но одноядерном, и результаты должны быть лучше. Посмотрим, что будет после перетестирования.
Мысль была, что дело еще может быть в сборщике мусора, которому тоже нужно процессорное время.
Я изначально потратил кучу времени на то, чтобы предусмотреть пропуски — холодный старт, проверка времени на ход, проверка времени на каждой ветке при поиске в глубину, расчет хода на случай его пропуска. Если время хода вышло, то возвращаю не лучший ход, а ход с учетом пропуска.
Но в конце решил, что это борьба с ветряными мельницами и все закомментировал. Оставил только сравнение моего мира с реальным для подгонки его к реальному в случае пропусков.
Судя по результатам, успешно прошел только 5 уровней, получив 41 место. Хотя сам тестировал на амазоновском сервере, аналогичном заявленному в условиях, но одноядерном, и результаты должны быть лучше. Посмотрим, что будет после перетестирования.
Да я уже потом вне конкурса ради спортивного интереса запилил суровый холодный старт, мол сиди 600 фреймов думай как будешь карту рулить, а потом всё почти как и в оригинальном решении: от оставшихся фреймов (600) он 1/3 времени (200) гоняется за бабочками пока они есть, и в оставшиеся 2/3 (400 фреймов) лопает алмазы. А почти — потому как при беге весь «дорасчёт» выкинут в комментарий и оставлена только отдача очередной буквы из (ранее найденного) лучшего пути развития событий.
Можно конечно меньше разогреваться, 400 или 300 (на моём железе хватало вполне), но зачем, если практически каждый уровень разбирается примерно за 400 ходов.
Получаю 8451 очков на финальном сете (правда на моём проце) и 6-е место. Но это ж он минуту целую стоит и курит. Сколько раз его за это время могли лопатой по голове стукнуть в случае двух игроков. =)
Можно конечно меньше разогреваться, 400 или 300 (на моём железе хватало вполне), но зачем, если практически каждый уровень разбирается примерно за 400 ходов.
Получаю 8451 очков на финальном сете (правда на моём проце) и 6-е место. Но это ж он минуту целую стоит и курит. Сколько раз его за это время могли лопатой по голове стукнуть в случае двух игроков. =)
PS: так мало тут картинок по ходу решений (не про гифки прохождения) — добавлю такую свою :)
Дебагдамп первого фрейма (после нулевого). Состояния падающих объектов и направления движения ножниц… бабочек отрисовываются по разному. Нос бабочек указывает их текущее направление.
Игрок только что сделал шаг вниз, потому бомба над ним ещё не перешла в режим падения.
Дебагдамп первого фрейма (после нулевого). Состояния падающих объектов и направления движения ножниц… бабочек отрисовываются по разному. Нос бабочек указывает их текущее направление.
Игрок только что сделал шаг вниз, потому бомба над ним ещё не перешла в режим падения.
Некоторые вручную сконструированные уровни, на которых мой бот научался штукам-трюкам:
imgur.com/a/s0nQY
imgur.com/a/s0nQY
НЛО прилетело и опубликовало эту надпись здесь
Второе место с конца хахахах))! 66 место! второпях допустил где-то ошибку перед отправкой. Звездочки мой бот умел собирать.
Я потестил два лидирующих решения и хочу поделиться наблюдением, которое мне кажется важным с точки зрения определения победителя конкурса.
Я заметил два случайных фактора, которые оказывают очень большое влияние на результаты — достаточно большое, чтобы реальная средняя разница между двумя решениями просто «утонула» в нем.
Во-первых, насколько я понимаю, решение 5991606f3cc1d6947da0b875 использует рандом и поэтому его результаты весьма нестабильны.
Во-вторых, очень многое зависит от набора сидов. То есть не просто, как сказано в посте, «на некоторых уровнях лучший результат показывает одно из двух решений, на других — другое», но даже на целых двадцатках-тридцатках сидов то одно, то другое решение может существенно превзойти конкурента. Например, на первой двадцатке сидов решение 5991606f3cc1d6947da0b875 у меня превосходило конкурента в среднем примерно на 65 очков, но при расширении набора сидов до 50 картина менялась на противоположную: на дополнительных 30 сидах уже 5995c8e13cc1d6947da0b89b выигрывает в среднем 150 очков. При этом лучший за 10 тестов результат 5991606f3cc1d6947da0b875 на 30 дополнительных сидах превосходит его же худший результат на 261 очко! То есть по сути тестирование на 20-50 сидах оказывается в бОльшей степени «измерением везения», чем измерением реальной разницы между решениями. Поэтому мне кажется, что два лидирующих решения (если никто другой к ним не подберется на 50 сидах, но, по-моему, этого не должно случиться) стоит протестировать по крайней мере на нескольких сотнях сидов, чтобы влияние рандома и удачности того или иного набора сидов для конкретного решения перестали оказывать доминирующее влияние на результат и стала заметной реальная средняя разница между этими решениями. До четверга еще три дня и за это время, в принципе, можно и на тысяче сидов сравнить пару решений :)
Я заметил два случайных фактора, которые оказывают очень большое влияние на результаты — достаточно большое, чтобы реальная средняя разница между двумя решениями просто «утонула» в нем.
Во-первых, насколько я понимаю, решение 5991606f3cc1d6947da0b875 использует рандом и поэтому его результаты весьма нестабильны.
Во-вторых, очень многое зависит от набора сидов. То есть не просто, как сказано в посте, «на некоторых уровнях лучший результат показывает одно из двух решений, на других — другое», но даже на целых двадцатках-тридцатках сидов то одно, то другое решение может существенно превзойти конкурента. Например, на первой двадцатке сидов решение 5991606f3cc1d6947da0b875 у меня превосходило конкурента в среднем примерно на 65 очков, но при расширении набора сидов до 50 картина менялась на противоположную: на дополнительных 30 сидах уже 5995c8e13cc1d6947da0b89b выигрывает в среднем 150 очков. При этом лучший за 10 тестов результат 5991606f3cc1d6947da0b875 на 30 дополнительных сидах превосходит его же худший результат на 261 очко! То есть по сути тестирование на 20-50 сидах оказывается в бОльшей степени «измерением везения», чем измерением реальной разницы между решениями. Поэтому мне кажется, что два лидирующих решения (если никто другой к ним не подберется на 50 сидах, но, по-моему, этого не должно случиться) стоит протестировать по крайней мере на нескольких сотнях сидов, чтобы влияние рандома и удачности того или иного набора сидов для конкретного решения перестали оказывать доминирующее влияние на результат и стала заметной реальная средняя разница между этими решениями. До четверга еще три дня и за это время, в принципе, можно и на тысяче сидов сравнить пару решений :)
Я тут посчитал сколько времени заняло тестирование всех решений на 20 сидах.
В каталоге res:
grep -r duration_time . | perl -ne '$s; /([\d\.]+),\s*$/;$s+=$1; print "$1 \t$s\n"'получилось 145488 секунд. A чтобы протестировать еще на 80 сидах нужно 145488*4 = 581952 секунд, это 162 часа или более 6.5 суток. Получается, что нужно использовать несколько машин, чтобы успеть к сроку. Чтобы обеспечить равенство — нужно чтобы один и тот-же сид для всех решений прогонялся на одной и той-же машине, верно?
На самом деле просто сделаем столько, сколько успеем на одной, а потом примем решение или немного отложить результаты, или взять меньше 100.
Тут к слову "культурные решения" после того как всё собрали или ничего больше сделать нельзя отправляют "q", чтобы досрочно завершить игру. Правда моё ещё нет, — потом уже научил, но стабилизировать новый вариант не успел до дедлайна.
Интересно, сколько штук таких участвующих решений из всех? Судя по всему единичные, т.к. 145488 / 20 / 66 ~= 110 секунд из макс 120.
Видимо для мотивации (чтоб потом быстрее было считать результаты) в подобном конкурсе стоило добавить дополнительное правило в игру, что досрочный выход даёт округлённое к меньшему (макс_фрейм - текущий_фрейм) * 0.1 очков плюсом.
Неправильная у вас арифметика, дядя Фёдор.
Трое суток. Впритык.
res$ grep -rh duration_time | awk 'BEGIN{s=0}{s+=$2}END{print s*4/60/60/24}'
3.36777Трое суток. Впритык.
В ожидании официальных результатов, неофициально протестировал двух лидеров на 300 сидах. Для [использующего рандом] решения 5991606f3cc1d6947da0b875 я сделал 2 прогона тестов, и по итогам первой сотни оно опередило конкурента (набравшего на одном из сидов 0 очков) в среднем на 570 очков (более 1%). Казалось бы, убедительное превосходство. Но на второй сотне превосходства уже не было: тут 5991606f3cc1d6947da0b875 на одном из сидов набирает 0 очков (как я говорил в одном из каментов выше, на некоторых сидах надолго залипать на месте нельзя), а 5995c8e13cc1d6947da0b89b в среднем набрало на этой сотне на 39 очков больше конкурента. На третьей сотне лидирующие решения ни на одном из сидов настолько явно не проваливаются, тем не менее разрыв между ними внезапно оказался наибольшим: 5995c8e13cc1d6947da0b89b набрало в среднем на 665 очков больше (чуть меньше 1.2% преимущества — если рассматривать в отрыве от остальных тестовых сотен, то тоже вроде бы «убедительно») и по сумме всех 300 сидов вышло вперед на 134 очка (менее 0.1% преимущества — явно меньше статистической погрешности). В общем, не только от сида к сиду, и не только от двадцатки сидов к двадцатке, но даже от сотни к сотне результаты очень сильно колеблются (даже сильнее, чем из-за рандома). Похоже, сиды, специфика которых выявляет слабые места того или иного из лидирующих решений, встречаются редко и разбросаны по тестовому набору слишком неравномерно (грубо говоря, если сиды какого-то типа встречаются в среднем раз в 100 случаев, то в одной сотне их может оказаться 2, а то и 3, а в каких-то других сотнях не оказаться вовсе, и если этот тип оказывается намного удобнее для одного из решений, то такое решение на конкретной сотне получает большое преимущество).
Тот случай, когда конкуренты примерно равны. Тем не менее, у нас нет ресурсов для тестирования на многих тысячах уровней, да и не факт, что это помогло бы. Поэтому остановились на первых 100 сидах из последовательности.
Когда встречаются претенденты на звание чемпиона мира по шахматам, они не играют тысячу партий. Если Каспаров в финале обыграл Карпова, то не исключено, что, сыграй они ещё партию, было бы наоборот. Поэтому приходится принимать определённую роль случайности в определеии победителя.
Когда встречаются претенденты на звание чемпиона мира по шахматам, они не играют тысячу партий. Если Каспаров в финале обыграл Карпова, то не исключено, что, сыграй они ещё партию, было бы наоборот. Поэтому приходится принимать определённую роль случайности в определеии победителя.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Конкурс по программированию: JSDash (предварительные результаты)