Comments 77
Мою стратегию смотрите в README, хоть там нет многих деталей. А остальные четверо
избрали кривую олимпиадную стёжку: сначала посчитаем всё, залипнув на месте,
а потом разом выплюнем лучший найденный путь. У меня тоже был соблазн, и может, я б дёрнулся ещё туда, зайдя в тупик, — но время, время.
Да и хотел изначально сделать более приближенного к реальности бота — конкретные условия конкретными условиями, но всё же, блин, карта может в реале быть иного размера, игрок может находиться в нескольких клетках под падающей бомбой или в нескольких клетках на пути ножниц… то есть бабочек, и ему нужно бежать, бежать, сразу бежать. Или может если он будет стоять то упустит возможность сожрать какие-то близкие алмазы, пока всё изначально падает-бежит в уровне и всё такое.
Так что сейчас в предварительных результатах моё 7-е чудо тоже бежит сразу с места стартуя и размышляя на ходу. И доступное процессорное время в тике для него решающе важно. Ридми не делал, зато с именами переменных порядок, комментарии семантические присутствуют и всё такое.
Именно
Без пропусков разница больше чем в 2 раза,
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
Просто в однопроцессном (-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.
А каким образом это может быть связано с энергосбережением (опять же при учёте что мы фактические тайминги измеряем)? Процы на экспериментальных системах имели по более чем 2 физических ядер и не были заняты ничем иным.
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
А что касается дела — так всё равно нас обманули :) Обещали, у вас будет 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);
}
};
А вообще, как насчёт формата следующего игрового конкурса с двумя машинами и взаимодействию по JSON API?
На одной сервер, реализующий это API, с игрой, которая (возможно, после обмена синхронизационными запросами) по команде старта от клиента или же самостоятельно, отвечая клиентам статусом со временем предстоящего запуска, начинает свой неумолимый ход жизни мира с метрономскими тиками.
На другой машине — игровой клиент, который будет это API использовать. Пытаться управлять своим игроком в этом мире, пытаясь набрать счёт.
Синхронизация решается достаточно просто, были б таймстампы в соотв. методах API.
Независимость работы машин очевидна.
В случае параллельной игры нескольких игроков в равные условия все могут быть легко поставлены, когда клиентские машины с решениями, например, размещаются в одном и том же ДЦ. Можно заодно устранить значимую часть лагов, поместив их в тот же ДЦ, что сервер, а можно в другой и сделать из (умеренных) лагов фишку.
На мой взгляд может получиться очень, очень интересный челендж, лишённый многих проблем одномашинного запуска и очень приближенный к боевым условиям.
Официальных конкурсов по игре JSDash больше не будет. Неофициальные, без призового фонда, участники могут, конечно, сами устроить. Но если Hola выделяет деньги на призовой фонд пару раз в год, то от меня как устроителя этих конкурсов ожидают разнообразия. В прошлый раз задача была совершенно другая, ничего общего. В следующий раз тоже будет другая.
Но я польщён и очень рад тому, что конкурс получился таким, что вам хочется продолжать.
Да, конкурс получился на славу!
Хотелось бы еще «живой статистики», чтобы отправлять решения и видеть результаты сразу (или в течение часа, например).
Задача, главное, из общего ряда конкурсов выбивается, не напоминает о работе, многих заставила вспомнить школьные годы чудесные)). Ради такого не жалко было и с javascript разобраться. Очень странно, что так мало участников.
В общем, ждем новых!
А можно ли в дозабег до 50 сидов взять не пятёрку, а десятку? Интересно! Тут тоже результат заметно плавает и на большей выборке уверенней можно будет о силе решений (в группах 6-8 и 9-10) сказать.
Тысяча чертей! Что же могло к такому привести? ;)
> Мы оставляем за собой право увеличить число уровней (для всех участников)
habrahabr.ru/company/hola/blog/332176
Честно говоря, эти странные непредсазуемые пропуски хода в воркер режиме полсилы решения отправили в ведро. =/
Уже при 50мс начинались значимые случайные… сбои синхронизации? Что-то начиналось. Даже при 40мс иногда. И бот ловил внеплановый пропуск хода, после чего остальные продуманные им ходы летели в печь. И из-за нестыковки того, какой он думает сейчас фрейм и какой в действительности фрейм, происходило вот это вот долбление о стены, умирание под камнями и прочее подобное.
PS: Ну и если, вдруг, тестирование будет решено производить в формате -p с контролем уже общего времени работы процесса игры = 120 +- 1 секунд (чтоб решения ну не могли «тупить» в зачёте) — то было бы вполне справедливо поправить решениям настройку «сколько можно думать» со слишком урезанных таймингов до 80мс. Наверняка такая настройка есть у многих вариантов. Или, не знаю, дать всем какой-нибудь «вторник допиливания», о котором объявить завтра. … Ну или оставить как есть, честно не знаю.
Мысль была, что дело еще может быть в сборщике мусора, которому тоже нужно процессорное время.
Я изначально потратил кучу времени на то, чтобы предусмотреть пропуски — холодный старт, проверка времени на ход, проверка времени на каждой ветке при поиске в глубину, расчет хода на случай его пропуска. Если время хода вышло, то возвращаю не лучший ход, а ход с учетом пропуска.
Но в конце решил, что это борьба с ветряными мельницами и все закомментировал. Оставил только сравнение моего мира с реальным для подгонки его к реальному в случае пропусков.
Судя по результатам, успешно прошел только 5 уровней, получив 41 место. Хотя сам тестировал на амазоновском сервере, аналогичном заявленному в условиях, но одноядерном, и результаты должны быть лучше. Посмотрим, что будет после перетестирования.
Можно конечно меньше разогреваться, 400 или 300 (на моём железе хватало вполне), но зачем, если практически каждый уровень разбирается примерно за 400 ходов.
Получаю 8451 очков на финальном сете (правда на моём проце) и 6-е место. Но это ж он минуту целую стоит и курит. Сколько раз его за это время могли лопатой по голове стукнуть в случае двух игроков. =)
Дебагдамп первого фрейма (после нулевого). Состояния падающих объектов и направления движения ножниц… бабочек отрисовываются по разному. Нос бабочек указывает их текущее направление.
Игрок только что сделал шаг вниз, потому бомба над ним ещё не перешла в режим падения.
imgur.com/a/s0nQY
Я заметил два случайных фактора, которые оказывают очень большое влияние на результаты — достаточно большое, чтобы реальная средняя разница между двумя решениями просто «утонула» в нем.
Во-первых, насколько я понимаю, решение 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 суток. Получается, что нужно использовать несколько машин, чтобы успеть к сроку. Чтобы обеспечить равенство — нужно чтобы один и тот-же сид для всех решений прогонялся на одной и той-же машине, верно?
А сейчас тоже одно из проявлений эффекта обманчивой тишины, как будто ничего не происходит у участников. На самом деле, уверен, все как и я в ожидании новостей, но поскольку это настолько очевидно, то никто и не пишет. Вот возьму и напишу что ли. :) Как идёт процесс?
Тут к слову "культурные решения" после того как всё собрали или ничего больше сделать нельзя отправляют "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
Трое суток. Впритык.
Когда встречаются претенденты на звание чемпиона мира по шахматам, они не играют тысячу партий. Если Каспаров в финале обыграл Карпова, то не исключено, что, сыграй они ещё партию, было бы наоборот. Поэтому приходится принимать определённую роль случайности в определеии победителя.
Конкурс по программированию: JSDash (предварительные результаты)