Парный постмортем: как победить Ктулху и ещё 2000 человек

[green_hippo]

Ну вот, а я играл по наитию, использовал тривиальную оценочную функцию и занял 241 место :) В следующем контесте попробую воспользоваться советами и напишу какой-нибудь простой симулятор.

Не понял только, что значит, что spaceorc «использовал Вороного» в оценочной функции. Диаграммы Вороного я знаю, но как их тут применить?

[spaceorc]

Я считал диаграмму Вороного для себя и вандереров (без слэшеров). Количество «моих» клеток входило как часть оценочной функции… Это позволяет не давать себя зажать, если перебираешь достаточно глубоко. Поскольку все расстояния были предрасчитаны заранее, расчет был очень быстрым — просто цикл по всем координатам (их 255 штук) по сравнение расстояния до меня и всех вандереров (их 8 — ближайших в моей симуляции, остальные игнорируются).

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

[Akarachudra]

Получилось уделить этому контесту где-то час времени. Реализовал алгоритм A*. Веса ребер на основе текущей ситуации на доске. Кажется, что алгоритмы на графах тоже были перспективны в данном контесте. По поводу необходимости писать симуляцию — не соглашусь, контесты CodinGame выгодно отличаются тем, что вполне допускают конкурентноспособную эвристику. В топе есть участник Khao (9 место) — он принципиально пишет эвристику на js. От себя добавлю, если есть цель попасть в топ 20, то это практически всегда бешеные трудозатраты.

[Tsvetik]

На мой взгляд, когда появляются исходники рефери, все эти игры превращаются в соревнование «перепиши рефери на свой любимый ЯП как можно быстрее» и посчитай 100500 ходов вперед.

Вот бои или гонки автономных роботов должны быть интереснее. Там исходный код противника уже не посмотришь и не просимулируешь.

[ser-mk]

Можно и сильно усложнить игру, а условием сделать полное уничтожение типа как здесь
Вроде на CD не посмотришь код соперников.

[Ollisteka]

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

Допустим, Петя думает, что вражеский исследователь следующим ходом перейдёт на соседнюю клетку. А враг бах, и делает YELL на Петю. А Петя уже 100500 ходов просимулировал в расчёте на то, что враг просто убежал. Скорее всего, ход, который он получил в итоге — не очень, и выиграть ему не поможет.

[Qbit]

когда появляются исходники рефери, все эти игры превращаются в соревнование «перепиши рефери на свой любимый ЯП как можно быстрее» и посчитай 100500 ходов вперед.

Нет, просто вместо борьбы эвристик начинается борьба оценочных функций и стратегий сортировки ходов и отсечения ветвей. 100500 ходов вперёд получится только у того, кто сможет оптимально отбросить 100^500 ходов вбок.

[spaceorc]

На самом деле, конечно, в борьбе оценочных функций нет ничего плохого. Фичи люди придумывают самые разные. Да и в условной "сортировке ходов и отсечении ветвей" много вариантов. Можно делать альфабету, mcts, генетические алгоритмы, что-то, наверное, еще. Если соперники ходят одновременно, как, скажем, в любых гонках, то можно потратить часть времени хода и пытаться предсказывать ходы соперника разными стратегиями, и считать статистику по ходу игры, чтобы выбирать, какая лучше предсказывает.

Это все есть почти в любом "стандартном" игровом контесте. А бывают и нестандартные контесты, типа code4life, когда у меня была чистая эвристика, потому что не придумал, что там можно перебирать.

В общем, я играю год всего, и мне пока не надоело. :)

[Qbit]

Это да, мало запилить симуляцию. Надо ещё понять, что с ней делать в отягчающих обстоятельствах, как то: больше двух игроков (не работает наивная альфа-бета), недискретность (непрерывное пространство без ячеек/графов, большой фактор ветвления), одновременность ходов (нет шахматных plies), неопределённость («туман войны», «природа»).

[ser-mk]

Только посматриваю в сторону CD, поэтому может задам пару нубских вопросов:

В какой-то момент я даже была на 84 месте в мировом лидерборде, но потом закоммитила новую версию и обратно не вернулась

А почему нельзя было загрузить старую версию и вернуть место?

я так понимаю это ваша симуляция?

Заголовок спойлера

вроде нагуглил есть локальные ранеры от самого CD и энтузиастов
ими нельзя воспользоваться для симуляции?

[Ollisteka]

К тому моменту, когда откатилась обратно, другие игроки уже тоже поменяли свои стратегии, против них старая версия играла не очень хорошо.

Это визуализация симуляции :) Делал spaceorc, для удобства отладки.

Ранеры (или brutaltester-ы) — это не про симуляцию. Они только запускают матчи локально, вызывая в нужных местах методы из реализаций бота и из кода рефери. Поэтому, если у вас уже есть своя симуляция и несколько разных стратегий, то можно сохранить их, скормить brutaltester-у, и он уже покажет статистику, какая из стратегий круче.

[green_hippo]

Я вижу там ShelterMe.java. Неужели spaceorc отвернулся от C# и перешёл на тёмную сторону :)

[Ollisteka]

Я думаю, он просто импортировал карту из исходников, а они как раз таки на Java :)

[spaceorc]

Это джавовские классы из рефери, описывающие лабиринты.
Я просто парсю их регулярками в брутал-тестере :)

[dbf]

Если кто, прочитав статью, захочет поиграть, то вчера игру добавили в мультиплеер-режиме: www.codingame.com/ide/puzzle/code-of-kutulu