FasterHarder: Всем хай! Сходу к делу!

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

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

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

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

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

спс за внимание)

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845433