Меня зовут Миша, и я студент. На факультативе по теории игр мы решаем различные интересные задачи, и я хотел бы поделиться с вами одной из таких.
1. Играют двое.
2. Поле игры представляет собой доску размера 3 на 3.
3. Каждый игрок располагает армией в 100 космодесантников.
4. Перед битвой ночью каждая сторона втайне размещает свои отряды произвольным способом на 9 клетках. На каждую клетку можно поставить любое целое число космодесантников от 0 до 100.
5. Утром начинается сражение за очередную планету. На каждой из 9 клеток побеждает тот игрок, у кого на этой клетке стоит больше астартес. За победу на каждой из 9 клеток дается 1 очко. Если на некоторой клетке стоит одинаковое число, то сражение на этой клетке заканчивается вничью, и оба игрока получают 0,5 очка.
6. Сражение выигрывает тот, кто выиграл больше полей. Если оба игрока выиграли по 4,5 поля, сражение заканчивается вничью.
Свою стратегию я придумал, но мне пришла идея как сделать этот контест интереснее, а также провести исследование. Я подготовил соревнование для всех желающих, где вы можете посоревноваться с другими людьми в решении этой задачи.
В данный момент при отправке ваше решение сыграет 10 игр со случайными людьми, а также с какой-то вероятностью будет играть с новыми стратегиями, а в пятницу произойдет перерасчет по всем решениям и будет вывешен финальный лидерборд.
И это не все — в данный момент каждые 2 минуты 2 нейронки отыгрывают друг с другом 10000 игр, и, конечно же, мне интересно, кто окажется лучше: нейронка или человечество
К выходным же я подготовлю статью о результатах моего исследования.
Ссылка на игру: game.pavlukhinlab.com
upd: Собранные личные данные (e-mail) хранить не собираюсь. Удалю их после получения результатов
Комментарии (20)
koldyr
20.02.2019 21:43Простите, а в чём смысл этого мероприятия?
Чистой стратегии выигрыша нет.
Sirion
20.02.2019 21:50Попытаться угадать наиболее распространённые стратегии среди других игроков и хаточить своё решение под них.
koldyr
20.02.2019 21:57Опять же известно, что любая стратегия не лучше оптимальной.
Или задача максимизировать выигрыш исходя из нерационального поведения большинства игроков?axtrace
21.02.2019 11:50не лучше оптимальной, но вдруг окажется, что большинство близки к оптимальной стратегии. Или, наоборот, равновесная стратегия — не оптимальная. Ну и прочие вещи
Nicknameless Автор
20.02.2019 21:55Так как это конечная игра (у игроков есть конечный набор стратегий), то здесь соблюдается равновесие Нэша, что значит — существует такое решение, при котором как бы другие игроки не меняли свои ответы, они не смогут увеличить свой выигрыш. Хотя здесь возможна ничья, так что насчёт этого я не совсем уверен, надо будет поизучать еще материалы по этой теме. Но какое-то идеальное решение в теории здесь должно существовать
koldyr
20.02.2019 22:03Эта игра имеет равновесие Нэша в смешанных стратегиях. В силу симметрии средний выигрыш — 0.
Nicknameless Автор
20.02.2019 23:26Да, вы правы.
Нашел как называется такой тип задач «Игра полковника Блотто». Действительно здесь нет идеального решения. Тогда просто интересно узнать как будут отвечать люди, может выделить какие-то зависимости. Придумаю, когда увижу данные. Основная цель была — сделать что-нибудь прикольное и интересное, и пока все идет по плану.
fusioneer
20.02.2019 23:17Наверно, стоит валидировать форму на сервере, потому что сейчас он принимает форму, заполненную произвольными числами, хоть INT_MAX, или сколько там отведено.
Nicknameless Автор
20.02.2019 23:19ага, спасибо за совет. Только что обнаружил, что так можно накручивать (чем 20 человек и воспользовалось, но я сам виноват)
axtrace
21.02.2019 11:52+1Очень круто! А видели эмулятор для игр типа «дилемма заключенного» notdotteam.github.io/trust
saqer220
21.02.2019 21:11Я так понимаю это факультатив теория игр в НИУ ВШЭ, так как ровно такое же задание выдали там. Это не совсем честно выполнять свое задание таким образом
Nicknameless Автор
21.02.2019 21:13Привет
Да, я хожу на этот факультатив, но за честность можешь не переживать
Я уже отправил свое решение. Отправлять лучшее решение как домашку нет смысла, так как вряд ли оно будет лучшим внутри факультатива. (у этой игры оказывается нет идеального решения)
Я сделал это, потому что мне это действительно интересно
zuko3d
21.02.2019 21:13+1Интересная идея, но 10 игр — мало. Кажется, что доверительный интервал мат. ожидания для винрейта будет слишком большим: отправил одно и то же решение два раза подряд, в первый раз было 992е место, во второй раз 251е. Но если для итоговых результатов будет игра «каждый с каждым по одному разу», то таких проблем не будет.
Nicknameless Автор
21.02.2019 21:16Изначально я хотел, чтобы каждый с каждым играл при отправке, но при таком кол-ве участников пришлось бы очень долго ждать, пока все результаты запишутся в БД. Согласен, что метрику реал тайм лидерборда нужно поменять, и если я буду еще запускать подобные игры, то обязательно над эти поработаю
zuko3d
22.02.2019 03:12Если это несложно сделать — думаю, многим будет интересно увидеть более полный лидерборд (например, топ100 или, в идеале, всех участников) с их решениями.
По поводу метрик и лидербордов в целом — у винрейта как метрики есть немало проблем (если интересно — могу более подробно описать). В качестве хорошей и проверенной альтернативы советую посмотреть на TrueSkill от Microsoft.Nicknameless Автор
22.02.2019 10:11Сегодня выложу топ 100 лидерборд.
Было бы интересно послушать про метрики.
Sirion
А есть какая-нибудь защита от накрутки результатов? Или я могу опубликовать 1001 стратегию, из которых одна побеждает остальную тысячу, и выйти в лидеры?
Nicknameless Автор
Защиты от этого нет, так как она здесь не нужна. В реал тайм лидерборде выбирается 10 случайных оппонентов для решения, не факт, что именно те самые попадутся. При финальном подсчёте, если эти 1000 решений будут проигрывать только одной стратегии, то это будет очень круто и интересно, в противном случае они будут также поднимать счет и других игроков.
Но кстати при проверке финальной можно будет также прогнать только на уникальных стратегиях