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

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

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

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

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

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