Nicknameless Feb 20 2019 at 19:26

Онлайн контест по решению задачи из теории игр

2 min

8.5K

Mathematics*Machine learning*Logic games

+24

Comments 24

Sirion Feb 20 2019 at 21:09

А есть какая-нибудь защита от накрутки результатов? Или я могу опубликовать 1001 стратегию, из которых одна побеждает остальную тысячу, и выйти в лидеры?

Nicknameless Feb 20 2019 at 21:22

Защиты от этого нет, так как она здесь не нужна. В реал тайм лидерборде выбирается 10 случайных оппонентов для решения, не факт, что именно те самые попадутся. При финальном подсчёте, если эти 1000 решений будут проигрывать только одной стратегии, то это будет очень круто и интересно, в противном случае они будут также поднимать счет и других игроков.

Но кстати при проверке финальной можно будет также прогнать только на уникальных стратегиях

koldyr Feb 20 2019 at 21:43

Простите, а в чём смысл этого мероприятия?
Чистой стратегии выигрыша нет.

Sirion Feb 20 2019 at 21:50

Попытаться угадать наиболее распространённые стратегии среди других игроков и хаточить своё решение под них.

koldyr Feb 20 2019 at 21:57

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

a3aquB Feb 21 2019 at 11:50

не лучше оптимальной, но вдруг окажется, что большинство близки к оптимальной стратегии. Или, наоборот, равновесная стратегия — не оптимальная. Ну и прочие вещи

Nicknameless Feb 20 2019 at 21:55

Так как это конечная игра (у игроков есть конечный набор стратегий), то здесь соблюдается равновесие Нэша, что значит — существует такое решение, при котором как бы другие игроки не меняли свои ответы, они не смогут увеличить свой выигрыш. Хотя здесь возможна ничья, так что насчёт этого я не совсем уверен, надо будет поизучать еще материалы по этой теме. Но какое-то идеальное решение в теории здесь должно существовать

koldyr Feb 20 2019 at 22:03

Эта игра имеет равновесие Нэша в смешанных стратегиях. В силу симметрии средний выигрыш — 0.

Nicknameless Feb 20 2019 at 23:26

Да, вы правы.
Нашел как называется такой тип задач «Игра полковника Блотто». Действительно здесь нет идеального решения. Тогда просто интересно узнать как будут отвечать люди, может выделить какие-то зависимости. Придумаю, когда увижу данные. Основная цель была — сделать что-нибудь прикольное и интересное, и пока все идет по плану.

fusioneer Feb 20 2019 at 23:17

Наверно, стоит валидировать форму на сервере, потому что сейчас он принимает форму, заполненную произвольными числами, хоть INT_MAX, или сколько там отведено.

Nicknameless Feb 20 2019 at 23:19

ага, спасибо за совет. Только что обнаружил, что так можно накручивать (чем 20 человек и воспользовалось, но я сам виноват)

Eldhenn Feb 21 2019 at 06:15

Контест должен быть не по решению задач, а по солвингу тасков.

a3aquB Feb 21 2019 at 11:52

Очень круто! А видели эмулятор для игр типа «дилемма заключенного» notdotteam.github.io/trust

Nicknameless Feb 21 2019 at 12:08

Ага, видел. Классная реализация

saqer220 Feb 21 2019 at 21:11

Я так понимаю это факультатив теория игр в НИУ ВШЭ, так как ровно такое же задание выдали там. Это не совсем честно выполнять свое задание таким образом

Nicknameless Feb 21 2019 at 21:13

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

zuko3d Feb 21 2019 at 21:13

Интересная идея, но 10 игр — мало. Кажется, что доверительный интервал мат. ожидания для винрейта будет слишком большим: отправил одно и то же решение два раза подряд, в первый раз было 992е место, во второй раз 251е. Но если для итоговых результатов будет игра «каждый с каждым по одному разу», то таких проблем не будет.

Nicknameless Feb 21 2019 at 21:16

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

zuko3d Feb 22 2019 at 03:12

Если это несложно сделать — думаю, многим будет интересно увидеть более полный лидерборд (например, топ100 или, в идеале, всех участников) с их решениями.

По поводу метрик и лидербордов в целом — у винрейта как метрики есть немало проблем (если интересно — могу более подробно описать). В качестве хорошей и проверенной альтернативы советую посмотреть на TrueSkill от Microsoft.