На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Игра на ориентированном графе , прям сильно много нюансов возникло
    Всем хай! Сходу к делу!

    Дан граф (ациклический, ориентированный невзвешенный). Кол-во вершин и дуг может быть несколько сотен тысяч (поэтому частные случаи даже можно не рассматривать). На произвольной вершине (стартовая вершина) кладут фишку. Есть 2 игрока. За один ход каждый из них может передвинуть фишку на смежную вершину по дуге. Игроки ходят по очереди. Цель игрока - загнать противника в тупик, т е получить ситуацию, когда у соперника нет хода. Побеждает тот, кто загнал противника в тупик.
    ------------------------------------------------------------------
    Сначала показалось, что это несложно, но, подумав, осознал, что здесь что-то совсем для меня непростое...
    Самая главная проблема - наличие параллельных путей при достижении тупика. Если бы их не было, тогда поиском в глубину все бы решилось нормально.

    Это ведь задача на поиск оптимальной стратегии, как я понимаю. Но я не уверен, что ее можно в принципе получить, т к каждый ход все меняется и КАЖДЫЙ из игроков в каждый момент своего хода выбирает как бы "новую" оптимальную стратегию или по крайней мере ухудшает оптимальную стратегию противника.

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

    Какие были мысли:
    1. получать расстояния для каждого игрока от вершины с фишкой до всех тупиковых вершин (только тупиковых) + смотреть на четность-нечетность сделанных шагов. Но вроде это бессмысленно, т к алгоритмы типа Дейкстры находят кратчайшие пути, а ведь далеко не факт, что противник будет также следовать по этим кратчайшим путям и свернет на параллельный путь, убив весь этот анализ.
    2. построить матрицу расстояний между всеми вершинами (алгоритм Флойда или +Уоршелла). Возможно, что это пригодится в каком-то моменте основного алгоритма. Но сама по себе эта матрица не решает проблему исходной задачи.
    3. задействовать поиск в глубину(DFS). Уверен, что здесь это точно надо юзать!). Но, вообще, ДФС ведь нужен для ОБХОДА вершин графа, а НЕ для прокладки путей. Но благодаря дфс можно достаточно легко получить тупиковые вершины. Проблема, что вариантов достижение тупика от заданной вершины может быть тысячи (параллельные пути) + противник своим ходом может свернуть куда ему выгодно.
    4. как-то применить топологическую сортировку графа. Это я от балды говорю)
    ---------------------------------------------------------------------
    Как я понимаю, ведь по сути игроки равносильные исполнители, у них одинаковая возможность хода и анализа, т е достаточно понять, как действовать одному игроку, значит, 2ой будет действовать аналогично со своей колокольни только)
    Я правильно понимаю, что анализ нужно проводить динамически, т е от вершины, где лежит фишка и НИКАКОГО предварительного анализа (до начала игры) делать НЕ нужно, да??

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

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

      Реально это решается обратной задачей - т.е. после построения всех путей начинаем "закрашивать" проигрышные пути, сначала от тупиков, потом на "чётных" ветвлениях. Если в итоге получился незакрашенный путь от исходной вершины - первый выиграл, иначе выиграл второй (само собой предполагаем, что игроки делают наилучшие ходы).
        Akina, я лишь частично (очень частично) понял твое сообщение.
        Как мне показалось, ты намекаешь на выигрышную стратегию, например для игрока №1. Выигрышная стратегия - стратегия, приводящая к победе, независимо от ходов противника (при безошибочной игре противника не всегда существует). Смысл ее в том, что игрок №1 "направляет" игрока №2 по нужному пути независимо от того, как сходит игрок №2.
        Игроку №1 надо, чтобы расстояние до тупика было НЕЧЕТНЫМ (1, 3, 17, 9999 шагов и т.д.) или четным, если рассматривать случай, когда игрок №1 уже походил в какую-то вершину. Например, стоит игрок №1 в стартовой вершине, перед ним развилка на 173 смежных вершины. Ему нужно сходить в вершину, расстояние от которой до тупика четное число. Затем ходит игрок №2 - куда захочет. Игрок №1 снова выбирает из набора возможных путей ту вершину, расстояние до тупика которое четно и т.д. Т е игрок №1 постоянно "навязывает" свой путь независимо от того, куда сходил игрок №2. Все это хорошо, но ведь возможны случаи, когда ходит игрок №1 и перед ним стая вершин и у КАЖДОЙ вершины расстояние до тупика - нечетное число. Выбора как бы нет, но это не означает, что игрок №1 не может выиграть. Он может временно согласиться пройти по "неправильному" для него пути, а через несколько итераций снова задать свое направление.
        Да, я понимаю, что в своем сообщении ты не это описывал), просто решил написать про выигрышную стратегию, которая здесь вот таким образом не применима.

        Akina, я бы хотел провести декомпозицию алгоритма на подалгоритмы, т к мне не хватает ума все это охватить и понять сразу. И пусть будет неоптимально, просто бы хоть как-то понять. (хотя в задаче еще есть ограничение по времени 8-) , т е как бы намек на то, что метод грубой силы тут не нужен, хотя я не уверен, что без него вообще можно реализовать)
        ---------------------------------------------------------
        Вот хотелось бы понять, насколько все это пригодится в решении (забыл сделать ремарку, что тупиков может быть больше одного, разумеется + из конкретной вершины можно проложить путь разной протяженности до разных тупиков):
        1. Получение всех тупиков достижимых из заданной вершины. В этом может помочь DFS+стек (вроде стек, а не очередь, т к она для BFS вроде). В результате будет сформирован одномерный массив вершин в том или ином виде. Хотя структуры данных оч.важны тоже, разумеется - без них дело гиблым оказывается при кодировании)
        2. Получить множество всех вершин, через которые может проходить какой-либо путь до какого-либо тупика
        3. ДЛЯ КАЖДОЙ вершины из п.2 найти расстояние ДО КАЖДОГО тупика! Это двумерный массив, где по оси Ох, допустим откладываются тупики, по оси Oy - №вершины, а на пересечении - расстояние между ними (или можно просто true/false аля чет/нечет длина)

        И вот владея этой информацией (из п.3) разве невозможно проанализировать победу игрока №1 или №2??
        Например, есть стартовая вершина и ходит игрок №1. Он может "просмотреть" все возможные пути (конкретно расстояния) до каждого достижимого тупика из этой вершины. Проблема выбора остается, т к путей нечетной длины может быть несколько...непонятно какой взять... :unsure: ... а может ЛЮБОЙ)) навряд ли...

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

          Изначально все вершины непомеченные (помечены как неопределённые).
          1a. Тупиковые вершины помечаются как выигрышные - поставив в них фишку мы выигрываем.
          2. Вершины, из которых можно передвинуть фишку в выигрышную позицию помечаем как проигрышные - если мы поставим в них фишку, противник передвинет её в выигрышную позицию и выиграет.
          1b. Вершины, из которых все пути ведут в проигрышные позиции, помечаем как выигрышные - если мы поставим в них фишку, противник будет вынужден передвинуть её в проигрышную позицию.

          Закрасив исходную позицию, мы получаем оптимальную стратегию и определяем, кто при оптимальной стратегии выигрывает.
          Алгоритм работает и для некоторых графов с циклами, если выигрывающей стороне удаётся обойти цикл.

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

            но есть ряд моментов!
            1. некая взятая вершина может принадлежать разным путям. Для одного пути - победная, для другого - проигрышная. Как понимаю приоритет имеет "проигрышный" статус вершины, т к никто из игроков не хочет оказаться в этой вершине независимо от того по какому пути дошел до нее, т к немедленно будет наказан соперником??
            2. чтобы понять, побеждает игрок №1 или №2 надо раскрасить граф и просто посмотреть на ПЕРВЫЙ ход 1ого игрока: есть ли смежная хотя бы ОДНА победная вершина?? Их может быть НЕСКОЛЬКО - игрок №1 может вставать в любую.
              Цитата FasterHarder @
              1. некая взятая вершина может принадлежать разным путям.

              А тут зависит от того, чей ход. Если твой, и есть выигрышный путь - вершина выигрышная. Если не твой, и есть проигрышный путь - вершина проигрышная. Варианты, когда все пути одного типа - тривиальны.
                Цитата Akina @
                А тут зависит от того, чей ход.

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

                на мое ИМХО, "чей ход" вообще учитывать НЕ нужно.
                мы ведь раскрашиваем граф как бы волнами (через BFS, наверное, надо будет сделать), где эпицентром является один из тупиков.
                и в конце концов волны доходят до стартовой вершины и все.
                и вроде достаточно просто посмотреть на:
                Цитата FasterHarder @
                чтобы понять, побеждает игрок №1 или №2 надо раскрасить граф и просто посмотреть на ПЕРВЫЙ ход 1ого игрока: есть ли смежная хотя бы ОДНА победная вершина


                т е раскраска автоматически чередует ходы игроков и дополнительно это уже не надо анализировать...
                прикладываю картинку-доказательство)
                Прикреплённая картинка
                Прикреплённая картинка


                p.s. может быть я здесь сильно ошибаюсь и поторопился с таким выводом
                Сообщение отредактировано: FasterHarder -
                  Цитата Akina @
                  3

                  :no:

                  -----------------------------
                  Akina, приведи граф, где на твой взгляд важен порядок ходов и цвет как-то особо нужно учитывать. Я считаю, не сможешь привести)

                  Добавлено
                  Подытожим алгоритм! Кому не лень и несложно, плиз проверьте + поправьте, если что.

                  1. находим все возможные тупики от заданной вершины. Всего в графе N вершин. Будет одномерный массив, состоящий из N элементов. У тупиков будут стоять 1цы, у остальных 0. Поиск тупиков через ДФС(стек)
                  2. помечаем все тупики статусом "победа"
                  3. инвертируем дуги исходного графа!
                  4. в цикле перебираем все тупики и от каждого тупика запускаем BFS (очередь). Помечаем чередованием вершины статусом "победа-поражение". ВАЖНО! Если встретилась вершина со статусом "победа", а ей для данного пути надо поставить статус "поражение", то ставим "поражение", т к у "поражения" высочайший приоритет. Также не меняем статус "поражение" на "победа" при возникновении обратной ситуации. Есть такой момент здесь: при обходе BFS будет задействовано много "лишних" вершин, которые не принадлежат ни одному из возможных путей. Это некритично - не обращаем на это внимания) На самом деле не оч.понятно, в какой момент заканчивать BFS, запущенный от текущего тупика. Ладно, пусть работает до упора - это НЕ оптимально и здесь можно как-то усовершенстовать.
                  5. после назначения статуса "победа-поражения" смотрим смежные вершины от стартовой. Если есть хотя бы одна вершина со статусом "победа" - победил игрок №1, иначе игрок №2.

                  Для статуса "победа-поражение", наверное, завести отдельный одномерный массив из N элементов (0 - поражение, 1 - победа). По дефалту поставить всем статус = 1.
                  язык Си, никаких STL-ских (делающих всю работу) приблуд

                  примерно так
                    Цитата FasterHarder @
                    1. некая взятая вершина может принадлежать разным путям. Для одного пути - победная, для другого - проигрышная.
                    В таких играх не рассматриваются пути - только позиции. Путь интересен только проигрывающему - для него выгодно затянуть игру в надежде, что выигрывающий игрок ошибётся.
                    Цитата FasterHarder @
                    2. чтобы понять, побеждает игрок №1 или №2 надо раскрасить граф и просто посмотреть на ПЕРВЫЙ ход 1ого игрока: есть ли смежная хотя бы ОДНА победная вершина?
                    Не надо смотреть смежные вершины, пометка вершины уже сообщает тебе, выигрываешь ты или нет (см поправку в описании алгоритма). Смежные

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

                    С этой поправкой алгоритм выглядит так:
                    Изначально все вершины непомеченные (помечены как неопределённые).
                    1. Тупиковые вершины помечаются как проигрышные - начиная в них игру игрок сразу проигрывает.
                    2. Вершины, из которых можно передвинуть фишку в проигрышную позицию помечаем как выигрышные - из них мы может передвинуть фишку в позицию, из которой противник проиграет.
                    3. Вершины, из которых все пути ведут в выигрышные позиции, помечаем как проигрышные - из них мы вынуждены передвинуть фишку в позицию, ведущую к выигрышу противника.

                    При маркировке позиций можно дополнительно определить число полуходов до окончания игры.
                    Вершины помеченные по первому пункту алгоритма получают оценку 0.
                    По второму - минимальная из оценок соседних проигрышных вершин + 1.
                    По третьему - максимальную из оценок соседних вершин (все они выигрышные) + 1.

                    При ходе из выигрышной позиции оптимальный ход делается в проигрышную позицию с минимальной оценкой - выигрывающий стремится как можно быстрее выиграть.
                    При ходе из проигрышной позиции оптимальный ход делается в позицию с максимальной оценкой - проигрывающий стремится затянуть игру.
                    Сообщение отредактировано: amk -
                      Цитата FasterHarder @
                      Akina, приведи граф, где на твой взгляд важен порядок ходов и цвет как-то особо нужно учитывать. Я считаю, не сможешь привести)


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

                          P. S. У тебя на картинке цвета инвертированы. По-моему нагляднее так: красный цвет - "ты туда не ходи", зеленый цвет - "ты сюда ходи".
                          Сообщение отредактировано: AVA12 -
                            Цитата AVA12 @
                            У тебя на картинке цвета инвертированы. По-моему нагляднее так: красный цвет - "ты туда не ходи", зеленый цвет - "ты сюда ходи".

                            изначально так и было (в первых сообщениях), а потом уже по совету amk инвертировал, но это ведь НЕ принципиально с т.з. алгоритма
                            Цитата AVA12 @
                            если из непокрашенной вершины можно попасть в зеленую (ход в которую гарантирует победу), то красим текущую вершину в красный цвет (ход сюда ведет к поражению), если из непокрашенной вершины все ребра ведут в красные, то красим текущую вершину в зеленый. В цикле гуляем по всем непокрашенным вершинам графа и применяем эти два правила (если возможно) до тех пор, пока все вершины не будут покрашены.

                            AVA12, выше ведь писал, что планирую запускать BFS от каждого тупика, а сам тупик закрашен "красным". Насчет правил, да, согласен, конечно, и они выработаны, но здесь все равно, что-то не всегда четко, т к к конкретной вершине можно подойти разными путями, при этом она может иметь разный цвет в зависимости от подхода.

                            Вообще, надо бы разобраться подетальнее с этой раскраской, конечно, чтобы снять любые сомнения.
                            Все тупики получены. Сразу их все безраздумья красим в красный цвет. Тут однозначно!
                            Перебираем в цикле все тупики. Берем i-й тупик и запускаем от него BFS. Не уверен, что бфс тут идеально подходит, но вроде должен подходить) (прим. дуги к этому моменту в орграфе инвертированы + также все вершины кроме тупиковых имеют "серый" цвет, якобы непосещенные). Т е все возможны 3 цвета: красный (ход туда ведет к победе), зеленый (ход туда приводит к победе противника), серый.

                            возможные случаи раскраски:
                            1. стоим на красной вершине и дуга к серой ---> красим серую в зеленый - тут вроде однозначно.
                            2. стоим на зеленой вершине и дуга к серой ---> красим серую в красный - тут вроде однозначно.
                            3. стоим на зеленой и дуга к зеленой. хм... Тут момент: а надо ли зеленую перекрашивать в красный? получается, что, НЕТ! сделав вершину-достижения красной будем обман игрока, он подумает, что надо в нее заходить, а соперник потом переведет его дальше в красную). Т е вариант "зеленая-зеленая" оставляем без изменений
                            4. стоим на красной и дуга к красной. хм... Тут момент: а надо ли красную перекрашивать в зеленую? получается, что, ДА! если оставить красной, то это будет обманкой для игрока, т к соперник его следующим ходом переведет в красную.
                            все, др.комбинаций здесь нет.

                            что-то мне подсказывает, что это НЕТОЧНЫЙ алгоритм раскраски, который не учитывают все возможные случаи. Как обычно с графами, все намного тоньше и умнее)
                            что не так с подалгоритмом раскраски??
                              Да просто запусти обход вглубь из текущей вершины
                              ExpandedWrap disabled
                                // True - побеждает тот, кто из этой вершины начинает, false - побеждает второй игрок
                                bool can_win(int vertex_number)
                                {
                                    if(уже_считали_эту_вершину) return старый_результат;
                                    // В тупике мы проигрываем, т.е. побеждает другой игрок
                                    if(это_тупик) return false;
                                    for(auto v : соседи_текущей_вершины)
                                        // Если в той вершине побеждает второй игрок, то мы пойдём туда, т.к. в этом случае мы будем этим "вторым"
                                        if(!can_win(v)) return true;
                                    // Не судьба, тут побеждает наш противник
                                    return false;
                                }
                                Метод минимакса, который используют для игр двух лиц с полной информацией, описан в книге Нильса Нильсона "Принципы искусственного интеллекта".
                                Есть два игрока, назовём их Мин и Макс. Мин минимизирует свой проигрыш, Макс максимизирует свой выигрыш. Каждая позиция - вершина игрового дерева. Дерево "слоистое", чередуются слои с ходом Мина и слои с ходом Макса. Мы играем за Макса, неважно, какой ход он делает, первый или второй. Начинаем строить дерево от текущей позиции с ходом Макса.
                                Теперь, внимание, игровое дерево строится с порождением всех возможных ходов для каждой позиции. Это полный перебор. И его (дерево) для данной размерности мы не построим вплоть до позиций, где игра заканчивается. Строим, докуда можем. Построили. Теперь придумываем эвристическую оценочную функцию, чтобы оценивать позицию одним числом. Её придумывают так, чтобы позиции с большей оценкой были выгодны Максу. Для листов (позиций без продолжения) рассчитываем оценку согласно эвристике, затем оценка распространяется вверх к корню дерева и Макс выбирает из всех возможных ходов ход с большей оценкой.
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,1198 ]   [ 21 queries used ]   [ Generated: 28.03.24, 12:18 GMT ]