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

    Привет, Хабр!

    Меня зовут Миша, и я студент. На факультативе по теории игр мы решаем различные интересные задачи, и я хотел бы поделиться с вами одной из таких.

    Описание игры
    «Я люблю вархаммер, поэтому решил адаптировать условие»
    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) хранить не собираюсь. Удалю их после получения результатов

    upd2: Результаты эксперимента https://habr.com/ru/post/441728/
    Поделиться публикацией

    Комментарии 24

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

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


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

        0

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

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

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

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

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

              +1

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

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

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

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

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

                  0
                  Я так понимаю это факультатив теория игр в НИУ ВШЭ, так как ровно такое же задание выдали там. Это не совсем честно выполнять свое задание таким образом
                    0
                    Привет
                    Да, я хожу на этот факультатив, но за честность можешь не переживать
                    Я уже отправил свое решение. Отправлять лучшее решение как домашку нет смысла, так как вряд ли оно будет лучшим внутри факультатива. (у этой игры оказывается нет идеального решения)
                    Я сделал это, потому что мне это действительно интересно
                    +1
                    Интересная идея, но 10 игр — мало. Кажется, что доверительный интервал мат. ожидания для винрейта будет слишком большим: отправил одно и то же решение два раза подряд, в первый раз было 992е место, во второй раз 251е. Но если для итоговых результатов будет игра «каждый с каждым по одному разу», то таких проблем не будет.
                      0
                      Изначально я хотел, чтобы каждый с каждым играл при отправке, но при таком кол-ве участников пришлось бы очень долго ждать, пока все результаты запишутся в БД. Согласен, что метрику реал тайм лидерборда нужно поменять, и если я буду еще запускать подобные игры, то обязательно над эти поработаю
                        0
                        Если это несложно сделать — думаю, многим будет интересно увидеть более полный лидерборд (например, топ100 или, в идеале, всех участников) с их решениями.

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

                          Сегодня выложу топ 100 лидерборд.
                          Было бы интересно послушать про метрики.

                      0
                      Я требую второга раунда, я должен отыграться!!!
                        0
                        Посмотрим
                        Возможно, еще буду запускать подобные игры
                          0
                          Жду с нетерпением. А где можно посмотреть топовые расстановки игроков, скажем топ 10?
                            +1
                            Я как раз сейчас пишу статью для хабра по результатам игры. Надеюсь сегодня выложить ее.

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое