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

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

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

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

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