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

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

Условие: Есть игра, а точнее набор правил которые описывают правила хода. Игра конечна и с открытой информацией. Играют 2 человека. Задача: Построить граф игры.

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

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

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

http://e-maxx.ru/algo/sprague_grundy По переходам в новые состояния функции Гранди можно посторить граф.

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

    Спасибо. Я смотрел статью, меня интересует сам автомат построения, а точнее различные альтернативы-методы построения. Так-же интересны технические аспекты. Они не особо описные на емаксе(Методы хранения графа-игры, а также механизмы работы с его частями. Мне не всегда нужен весь граф).

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

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

      Хранить вершины можно по-разному. В олимпиадах чаще всего это либо обыкновенный граф, либо массив по типу динамики, либо, если вершины довольно сложные по структуре, их можно хранить в map'е или set'е.

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

        Спасибо, это больше помогло. Какую теорию посоветовал бы почитать?

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

          Я посоветую статью Андрея Станкевича "Игры на графах". Шикарная статья с глубоким теоретическим анализом комбинаторных игр. Я оттуда извлёк массу полезной информации. Жаль, только, что она сейчас как-то не гуглится. Или я плохо искал...