Блог пользователя ftc

Автор ftc, 13 лет назад, По-русски

Наверное многие из присутствующих здесь участвовали в разнообразных турнирах стратегий, когда нужно написать программу, играющую во что-нибудь. Обычно это очень весело, особенно когда есть визуализатор и можно смотреть, как программы играют друг с другом. В декабре мы проводили подобный турнир стратегий в ПетрГУ, народу очень понравилось, поэтому мы решили проводить подобные конкурсы на более-менее регулярной основе. Первый из таких "регулярных" конкурсов будет проводиться с 15 по 29 февраля. В течение этого времени можно будет отсылать своё решение в систему и смотреть, как оно играет с другими участниками и улучшать его. Участвовать в конкурсе приглашаются все желающие. Вся информация будет публиковаться здесь. Ну а пока можно порешать задачи с декабрьского конкурса, выложенные у нас на сайте.

UPDATE: Открыта регистрация на контест, на этой странице.

UPDATE: Контест начался. Выложены условие задачи и утилита для локального запуска игр с визуализатором.

UPDATE: Мне тут подсказали, что стоит огласить список имеющихся компиляторов. Так вот, доступны G++ 4.5.2, G++ 4.6.0, Free Pascal 2.2.2, Java 1.6, Visual C++ 2005, Visual C++ 2010, Visual C# 2005, Perl 5.10, Python 2.7.2, Python 3.2.1 и PHP 5.3.8.

UPDATE: Контест завершился, предварительные результаты. Из тестирующей системы можно скачать логи партий всех игроков со всеми. Также задача контеста добавлена в архив игровых задач, где можно помахать кулаками после драки ;-)

  • Проголосовать: нравится
  • +87
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Зарегился :)

»
13 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Я вот что-то не могу зарегистрироваться. Письмо на e-mail не пришло. А по второму разу зарегистрироваться с теми же данными не дает.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Странно, в логах почтовика написано, что все хорошо отправилось. Попробуй зарегаться еще раз, а по регистрации проверь папку "Спам" в гмейле — может туда письмо попало?

»
13 лет назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

Несколько комментариев по поводу условия и не только, не нашел куда написать в системе поэтому напишу сюда.

  1. В формате вывода написанна полная чушь, не соответствующая ничему.
  2. Логично добавить правило что нельзя выбирать свой цвет тоже, а не только цвет соперника. Иначе игру можно зациклить следующим образом: Допустим внутри поля соперника есть дырка. Причем он уже набрал больше половины, то есть игрок однозначно проиграл. Тогда берем и перманентно занимаем цвет этой дырки. Соперник ее никогда не захватит, игра не закончится, мы не проиграем, система повиснет, PROFIT.
  3. Во избежание подобной чуши, которая придет в голову кому-то еще, стоит сказать что игра заканчивается как только кто-то захватил больше половины поля. Это убьет большую часть подобного бреда. Хотя возможно, это противоречит задумке авторов о подведении результатов при равном числе побед.
  4. Аналогично многое лечится правилом о том, что надо захватить хотя бы одну клетку. Впрочем из-за дырок внутри соперника может быть так что игра не закончилась, а осмысленный ход сделать нельзя.
  5. Было бы очень приятно если бы чекер и game_run выдавал хоть какую-то информацию о том что происходит, а то не понятно кто висит даже.
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    По пункту 2: можно зациклить не только когда у кого-то половина, например у игрока1 как и у игрока2 есть тоже такое "защищённое поле" (дырка), но количество занятых им клеток меньше половины, но больше, чем у игрока2, тогда игрок1 будет занимать цвет защищённого поля второго игрока, таким образом у него очков больше и ни один ход второго игрока не изменит ход игры. Хотя вариантов придумать такое может быть много, в том числе и если только у игрока2 есть дырка, но она больше половины поля.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    По поводу пунктов 1-4, может быть стоит тогда сделать правило, что игра заканчивается через некоторое K ходов, тогда зацикливать игру будет либо невыгодно либо бессмысленно. Хочется, чтобы участники оценили, если разумно, то сделаю.

    По поводу пункта 5 — понял, сделаю.

    В системе можно отправить сообщение (на вкладке "Сообщения"), но лучше всего в комментах здесь.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Почему бессмысленно. У соперника большая дырка. Я ее не даю ему захватить и у меня больше очков, хотя набрать 50% я не могу чисто технически. Во всяком случае он очки точно не получит а при удачной системе оценки еще и я получу.

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Согласен, не бессмысленно. Но в любом случае, если противник оставил внутри себя большую одноцветную дырку — наверное он это зря :-)

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Кстати вспомнил как с этим борятся в оригинальной игре. То что окружил — автоматически твое. И еще было бы круто, если бы была возможность играть со своей программой.

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            ты можешь же это делать — локально!

            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Руками чтобы играть, не пиша с нуля свой визулоализатор и все остальное я не умею.

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

              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                Эм? http://acm.petrsu.ru/files/article/585/game_run_filler.zip есть же утилита для игры.

                1) пишешь: Плауер_1 — свое решение_1, Плауер_2 — свое решение_2

                2) запускаешь экзешник нужный

                3) запускаешь визуализатор

                4) изучаешь поведение своего бота

                5) ....

                6) PROFIT!!!

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится +5 Проголосовать: не нравится

                  ИМХО, имелась в виду возможность поиграть со своей прогой тебе в смысле человеку

              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Скачай новую версию условия — там есть лимит в 2000 ходов на обоих участников. Как только ходы кончились — считаем сколько у кого территории и все

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится -8 Проголосовать: не нравится

                  А как узнать, даётся ли ход противнику после моего или нет? Ну т.е. я хожу первым или вторым...

»
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Если напишете локальный тестер под линукс, было бы здорово, если бы выложили в открытый доступ, а то у меня всё руки не доходят его написать, а для сообщества было бы полезно.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      Без проблем. Сейчас займусь.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится

      На topcoder-е потому не заморачиваются и пишут визуализаторы на java — в итоге оно работает в любой более-менее популярной ОС. ;)

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

У моего сабмишна куча FT, это нормально?

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    FT это не нормально. Разбираюсь

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Баг с FT локализован, решение будет перетестировано в ближайшее время

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Кстати, в частности в твоем сабмите есть все равно баг — надо выводить \n\n после своего хода, а не просто \n

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Что значит вердикт QU?

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я так понял, что запускать решения, которые не являются екзешниками, нельзя?

Player1CommandLine = "java Filler" или Player1CommandLine = myRun.bat

ругается:

CreateProcess failed, GetLastError = 2 Job done, result = 6 Comment: Unable to run child process: CreateProcess failed

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Был баг в модуле, который процессы запускает. Теперь должно работать — скачайте новый комплект отсюда

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Та же ошибка.

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
          Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

          Пытался Player1CommandLine = “java Filler” говорит, что не может запустить.

          Создал батник:

          @echo off
          java Filler

          Player1CommandLine = 1.bat

          Running thread... Job done, result = 0 Comment: Player 1 terminated

          И возникла еще одна проблема: все мои посылки на сервере получают CE, даже

          import java.io.*;
          import java.util.*;
          import java.math.*;
          
          public class Main {
              public static void main(String[] args) throws IOException {
          
              }
          }
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            При посылке решений на джаве надо либо посылать файл Main.java (если public-класс Main) — прицеплением файла.

            Если хочется вставлять код в форму — тогда public-класс должен называться solution.

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The requested URL /files/article/585/game_run_filler.zip was not found on this server.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Линк поменялся — проще всего качать с этой страницы

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Что значит Accepted? Как вообще происходит процесс тестирования с другими участниками? По какому принципу сталкиваются стратегии?

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Accepted в данном случае значит, что система приняла сабмит. Стратегии сталкиваются по круговой системе, с каждым другим участником по 10 партий (5 за первого игрока, 5 за второго).

        Можно смотреть лог тестирования (пока это не закрыто — на странице "Результаты тестирования" картинка в колонке "Log"). Там написано, как твоя программа играет с каждым из других участников. Ближе к концу контеста эта фича будет прикрыта.

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          А зачем прикрывать? Интересно же! Может оставите?

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            а как же соревновательный момент, интрига?)

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Вроде как для сохранения интриги :-)

            UPD: Правда с таким количеством народу, мне кажется закрывать ничего не надо будет — в более-менее реальном времени все равно ничего будет не посмотреть.

»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

А еще не забываем...что если идеи по этой задачки кончились...то можно попытаться "поиграть" в четыре других....и посоревноваться с сабмитами оттуда....а то скучно в дорешивании=)

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

может стоит в чекере нумеровать ходы?

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В формате вывода по прежднему что-то странное.

»
13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Ребята, смелее. Только 9 участников выше рандомного — ну что так мало?

»
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

А что значит Player * terminated? У меня на локале работает нормально, а на серваке все игры с таким вердиктом. UPD. Уже разобрался. Странно что у меня не валилось...

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Это значит, что решение завершается раньше времени. Может быть из-за рантайма например. В частности, в твоём решении много локальных массивов заведено — может в сумме стека не хватает (для G++ он ставится опцией командной строки на сервере, а вот для Visual C++ надо самому ставить прагмой).

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Нет. Там был выход за границы вектора. Но почему-то у меня на компе не валилось решение.

»
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

А как я оказался единственным с нечетной суммой баллов? У вас что игры несимметрично идут? UPD. Видимо я слепой все таки.

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Что-то я не понял, а что у вас с ТЛ'ем? Написано 10 секунд на 10 ходов — т.е. секунда на ход? Моё решение упорно ТЛится, даже если отсекать по CLOCKS_PER_SEC/2. Или на вашем сервере clock() не работает?

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Не совсем секунда на ход — суть примерно такова, что даётся 10 секунд, а после каждых 10 ходов ещё по 10 секунд.

    clock() должен работать, но выдавать не особо понятные результаты, поскольку как минимум половину времени, которое меряется, ваше решение ждёт отрабатывания другого решения, так что я бы на него особо не полагался.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Эм, т.е. это 10 секунд не процессорного времени моего решения, а 10 секунд астрономического времени моего решения + чекера + решения соперника? Это было бы совсем странно. Я clock()'ом замеряю время между моментом, когда я закончил читать данные, и моментом, когда я вывожу ход. Казалось бы, это ровно процессорное время моего решения... Так что странно, буду разбираться, что не так.

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Да, действительно странно. Я тоже попробую разобраться, что здесь не так.

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          У меня тоже была такая странная ситуация: даже когда мое решение работало 0.1 сек на ход, оно умудрялось TL-ить в некоторых партиях.

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          +1 работает всегда на одном ходе 0.3 сек, много tl'ей

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            Кстати, с именно в партиях с тобой TL-ится почти всегда. Ты читер.

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Для всех кто получает "странные" TL-и — проверьте поведение проги при "странных позициях" вида "съедено всё поле, кроме нескольких дырок внутри одного из участников" — практически все TLи случаются именно в таких ситуациях.

  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Гарантировано работает меньше 0.4 секунды (и в таких ситуациях тоже), куча TLей.

    Собственно, почему так странно устроен учет времени работы программы? Написал тестер, который просто кормит проге поле и ответа секунда. Почему бы не сделать так же?

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Такой хитрый учет времени работы сделан для того, чтобы дать возможность проге "потупить" при запуске (ну мало ли предподсчитать ченить), а потом работать шустрее. В любом случае, проблему с TL-ями буду исследовать дальше.

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В общем, проблема с таймлимитом должна тем или иным образом пофикситься. Суть в том, что при учете времени работы считалось время и в user space и в kernel space. На обычных задачах это работает вполне адекватно, поскольку все разумные решения проводят в kernel space пренебрежимо мало времени.

Здесь же проблема в том, что достаточно много времени решение проводит в ожидании ввода-вывода, что приводит к высокому использованию процессорного времени в kernel space (особенно сильно, видимо, это сказывается на решениях, написанных на Java). Короче, теперь учитываем только время в user space.

Всем, кто получал TL и из-за этого подкручивал решение, чтобы оно использовало меньше времени, рекомендуется подкрутить его обратно и перепослать.

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

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Что-то не очень она пофиксилась... Зато в процессе нашлась ещё одна проблема. В Visual Studio C++ если кинуть исключение, программа немедленно прибивается, даже если это исключение дальше ловится. Так что у меня возник закономерный вопрос (раз ваш invoker как-то узнаёт про брошенное исключение) — а как вы запускаете программы? Надеюсь, не в debug-режиме? Это бы объяснило все проблемы со временем.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Нет, не в debug-режиме (иначе все программы использующие много динамической памяти тормозили бы по-страшному). Вообще, там для отлова runtime error-ов отслеживается только код выхода, так что про исключения система по идее ничего знать не должна.

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

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Run id = 39442 (ну или могу сам исходник выслать). Ещё я поставил assert на то, что clock() перед выводом данных — clock() после чтения данных < CLOCKS_PER_SEC * 0.9. Assert не падает, но выдаётся ТЛ. Так что всё же с ТЛем что-то странное.

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Есть подозрение, что время расходуется при ожидании ввода (там же функция чтения должна периодически проверять пайп на предмет поступления новых данных). До вечера постараюсь проверить и отписаться.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    А то что с некоторыми у меня каждый раз TL, это моя проблема? У меня 60 ходов за 3 сек проходит.

  • »
    »
    13 лет назад, # ^ |
    Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

    А как на Java получать время, потраченное процессором в user space? Желательно без использования JNI, т.е. без написания динамической библиотеки на C++. Обычно же в задачах, где контестанту надо ориентироваться по времени, используют wall time (в марафонах на топкодере, например).

    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Как это сделать "изнутри" Java — мне если честно не известно. "Снаружи" я замеряю время потраченное java-машиной при помощи функции GetProcessTimes в WinAPI.

      А, да, использовать wall clock time наверное нехорошо, поскольку тогда время, которым может пользоваться участник, будет очень сильно зависеть от того, что происходит в системе (ну например если что-то еще ресурсоемкое помимо проги участника запустить, оно же будет использовать процессор и участнику меньше его времени останется).

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Ну, на topcoder-е не заморачиваются и используют для марафонов wall time (хотя для algorithm используют cpu time). Наверно они параллельно больше ничего не запускают просто... А так как-то нечестно немного получается, потому что в Java без использования JNI померять CPU time не как, а проверяющая система не рассчитана на использование JNI.

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Ну мы к сожалению не топкодер и найти где-нибудь хотя-бы 30-40 одинаковых железок (чтобы отдельно запускать каждого участника), увы не можем.

          С другой стороны могу посоветовать, как можно по-другому сделать отсечение по времени (мы таким пользовались, когда clock() оказывался недостаточно точен). Надо разбить работу программы на элементарные действия (типа "обработать состояние") и отсекаться не по времени, а по количеству таких действий (а сколько их можно успеть за таймлимит, можно определить экспериментально).

»
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

В связи с долгим тестированием в некоторых ситуациях, я предлагаю уменьшить число полуходов до 100 или 200. Смотрю за своими программами — им 100 почти всегда хватает до впадения в цикл. Для порядку можно поставить 200.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Господа участники, если есть какие-то возражения, то отпишите их здесь. В противном случае сделаю уже сегодня 200 ходов на обоих игроков (по 100 каждому).

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ну в общем так как против никто не высказался, лимит на количество ходов уменьшен до 400 (по 200 на каждого игрока).

    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Я могу сделать по-другому: передавать в качестве параметра командной строки решению участника номер того игрока, за которого оно играет (первому соответственно 1, второму 2). Так пойдёт?

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Про таймлимит (ага, опять): откопал баг при определении таймлимита. Хороший фикс пока сделать не успел, но зато сделал "грязный хак". В общем, у кого были TL-и — перепошлите, пожалуйста, ваши результаты могут поменяться (и скорее всего поменяются).

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я, наверно, плохо знаю C++, но можно объяснить зачем в примере из условия надо:

// чтобы программа не завершилась раньше времени
scanf("%d", &i);

после while(1){...}? ;)

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    В конкретно данной задаче — совершенно незачем. Оно осталось от другой задачи, в которой было ровно 10 ходов :-)

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

После окончания, если это возможно, хотелось бы взять лог вот этой игры 92376 photon190573 (2) FAndES (0) First: 49 Second: 47 Какой-то уж очень интересный счёт у неё :)

  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Логи всех игр можно будет после окончания скачать в системе (при просмотре лога, для каждой партии есть ссылка на скачивание её лога).

    Да, такой счёт может возникать, если игра зациклилась и никто больше ничего не хочет делать :-) Хотя действительно странно, обычно игра зацикливается при более крупном счёте.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Ещё одна такая игра :) 93019 optimus_prime (0) FAndES (2) First: 32 Second: 53 UPD. щас посмотрел и обнаружил много таких игр.. что-то тут не то...

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Проблему обнаружил — она заключается в структуре поля для 4-й партии (грубо говоря, там можно "запереть" соперника). Поле переделал, запустил перетестирование.

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          То есть поля не всегда рандомные? Мне кажется сервер и до завтра не справится с перетестированием всех решений (все мои решения помечены QU... это оочень долго)...

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            Тестироваться будут конечно же только последние отправленные решения. Занимает это развлечение примерно 2 с половиной часа.

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          А зачем переделывать поле? Какой у вас критерий приемлемости поля? По-моему логично бы было на каждом поле запускать две партии с обменом местами игроков — так было бы честно, игроки были бы в равных условиях... а то, что есть возможность на 30-40 занятых ячейках запереть противника — только плюс, который позволит лучше выявлять думающий алгоритм.

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            А на 1 ходу?

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Там проблема именно с первым ходом.

            Каждая пара игроков запускается на 5 полях, по два раза на каждом (со сменой местами игроков), так что в принципе все вроде честно :-)

            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              На первом ходу получалось заблокировать противника с 32-мя или 47-ю ячейками? Это при рандомном заполнении??

              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Там при этом еще чекер криво считал результат — как сумму клеток того цвета, в который окрашена левая верхняя и правая нижняя соответственно, потому 32, 47 и прочие такие цифры

            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              А посмотрел логи — а все 10 полей то, как ни транспонируй, а разные... :(

              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Да, я тоже обнаружил этот баг. Я его уже пофиксил, но перетестировать уже прошедший контест не буду. В следующем контесте баг не появится (по крайней мере я на это надеюсь).

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      98692 optimus_prime (0) FAndES (2) First: 1 Second: 3 Это вообще прикольный счёт :)

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        А у меня есть 1-1. Даже целых две штуки.

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Есть некоторая проблема с полем номер 5 — оно получилось не очень удачным. Я его перегенерирую сегодня после полуночи, после чего запущу ретест.

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Так сегодня же конец контеста? :(

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

            Сделал по-другому, смотри коммент ниже.

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Обнаружил небольшой косяк в пятом поле — поле перегенерировал, после полуночи будет финальный ретест всего. Кому интересно посмотреть свой результат на новом поле — welcome to resubmit :-)

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Запустил финальное перетестирование. Окончательные результаты вместе с логами партий будут доступны завтра утром (ориентировочно около 10-11 утра по Московскому времени)

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Наконец-то понял откуда 1-1 появляется :) противник запирает на первом своём ходе, взяв цвет, который полностью меня окружает.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ага, именно оттуда оно и берётся

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Мда, внезапно, в итоге моя программа на первом месте... Неожиданно, учитывая, что я забил на этот контест, после того как понял, что моя программа делает полный бред :)

Интересно, а что писали все остальные? Что-то умное, но с багами, так, что оно моему бреду сливало? :)

  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Ушло под спойлер. Можно не читать...

  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    В начале я написал простой перебор всех цветов (считай на 1 полуход), и очень удивился тому, что этот наивный жадный алгоритм оказался в середине таблицы (к тому времени random player был месте на 20-м). Я себе смутно представляю десяток алгоритмов, которые лучше рандомного, но хуже этого (разве что специально с какой-то вероятностью думать, а с оставшейся вероятностью — рандомить).

    Дальше я сделал обычный минимакс на 5 полуходов с альфа-бета отсечением. Но даже с такой небольшой глубиной реализация на Java иногда TL-илась. Но, не смотря на это, даже эта фигня умудрялась выигрывать 1-2 партии у несменного лидера, т.к. первоначальное заполнение поля очень сильно влияет на расстановку сил (но варианты полей при финальном тестировании сложились не в мою пользу).

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я написал обычный перебор. Из не озвученных еще идей моя функция учитывала количество соседних клеток. Очевидно что хорошо если их много. По моему перебирал первые 5 полуходов, причем 20 первых запусков перебирал только свои ходы.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Т.о. Ваша программа не умела запирать противника на первых ходах? Как жалко что такого поля нам не выпало...

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        То есть это вы и есть, кто наделал толпу тех ботов, о которых я писал ниже? Почему я так подумал: достаточно подробно описали, зачем это может быть нужно; фишку с запиранием на первых шагах я видел только с играми как раз тех ботов..

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          У Вас хорошее чутье, но логика Ваша как-то не логична. Если есть возможность запереть и выиграть — это очень правильная стратегия, и так делали очень многие из соревнующихся алгоритмов. Я даже по финальным логам могу видеть партии, где меня запирали алгоритмы, находящиеся чуть выше рандомного. А мне вот стоило специально добавить такую проверочку, бо если существует способ набрать больше очков за 5 ходов, нежели выиграть запиранием, мой алгоритм будет играть.

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Кстати, может я и ошибаюсь, но мне кажется, что пользователи r2d2, evangelion01, photon190573, bender, optimus_prime это чей-то чит, ибо все они появились довольно поздно почти в одно время и довольно сильно и примерно наравне играли (в таблице кстати они тоже все рядышком).

  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Очень похоже. Только зачем кому-то создавать 5 идентичных аккаунтов в контесте, который исключительно "for fun" — мне решительно непонятно

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Нуууу... кому-то fun бота написать, а кому-то fun посрать в контесте.

    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      А как это Вы не поняли в чём fun ботов?... Всё кроется в системе подсчёта очков!

      Давайте возьмём пример — 3 игрока. Представьте, что Ваш модный алгоритм "сделал" каждого из двух остальных, выиграв по 6 партий из 10 (абсолютно все партии Ваш супер-алгоритм не мог чисто теоретически выиграть исходя из особенностей некоторых полей). Вы можете подумать, что Ваш алгоритм — самый лучший и должен занять первое место? Ан нет — всё зависит от того, как эти, во Вашему мнению, слабочки сыграют между собой. Один из них может спокойно набрать 28 баллов и обойти Ваши 24. Т.о. осталось за малым — написать друзей-ботов, которые смогут распознавать Вас и будут Вам покорно сдаваться. Если эти боты смогут выигрывать хотя бы по одной партии у лидера, то при достаточном их количестве можно выйти на первое место. Раз контест исключительно "for fun", то и решение just for fun :)

      P.S. В каком-то смысле это является эволюционно стабильной стратегией. Эта идея была успешно реализована проф. Ником Дженнингсом на ежегодном турнире по дилемме заключённого в 2004-м году.

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        < trololo> Что ж тогда ботоводы не смогли выиграть? :) < /trololo>

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Для этого надо несколько сотен ботов... негуманно так сервер нагружать.

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Ежели бы (к моему великому удивлению) набежало бы несколько сотен участников — я бы переделал принцип генерации партий с кругового на какой-нибудь еще и подобные стратегии были бы не столь эффективны.

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Мда...

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да уж, это конечно забавно получилось :-)

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Этот "контест" не анонсировался ни на snarknews, ни на codeforces, и задачу взял проверенную временем. Так что можно с чистой совестью обсуждать тут идеи. Если кто в нём вдруг решил участвовать — могу выложить свой код в открытый доступ, feel free to improve :)

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Когда ещё будет игрушка? :)

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Как только я ее придумаю и напишу условие и чекер. Вообще, хочу запустить в районе 10-15 марта :-)