Существует теория, которая позволяет решать такие игры.
Ваша игра - беспристрастная игра, в которой оба игрока имеют одинаковые ходы с каждой позиции.Шахматы не беспристрастны, поскольку белые могут контролировать только белые фигуры.Игра заканчивается, когда у игрока нет хода, затем он проигрывает.Предположим, что каждая игра заканчивается в ограниченное время.
Вы можете проанализировать позиции и пометить их, как предложил PengOne, L и W. Проигрышная позиция - это та, где все возможные ходы приводят к выигрышной позиции и выигрышной.позиция - та, где есть по крайней мере один ход в проигрышную позицию.Рекурсивная, но четко определенная маркировка.Когда у игрока нет хода, все последовательные позиции выигрывают ( пустая правда ), поэтому это помечается как проигрышная позиция.
Вы можете вычислить немного больше информации, которая поможетвы.Назовите mex (A) наименьшим неотрицательным целым числом не в A. Например, mex ({0,1,5}) = 2 и mex ({1,2,3}) = 0.Теперь вы помечаете каждую позицию меткой всех меток, куда вы можете перейти.Это также рекурсивная и четкая маркировка.Позиция проигрывает, если ее значение равно 0. В соответствии с этой классификацией позиция с меткой 0 проигрывает, но у вас есть точная классификация выигрышных позиций с номерами 1,2, ....
Эти числа позволяютВы рассчитать стоимость суммы двух игр.Вы можете добавить две игры, играя в них самостоятельно.Во время хода вы можете играть в первой или во второй игре.Позиция в вашей игре ___X__X__ на самом деле представляет собой сумму трех игр ___, __, __.
Теорема Спрейга-Гранди. Сумма из N оцененных игрa_1, a_2, ..., a_N ценится a_1 xor a_2 xor ... a_N.Поэтому сумма N игр теряется, если их значения xor равны 0.
Ваша начальная позиция - это сумма K независимых игр, разделенных Xs.Вам нужно найти значение Sprague-Grundy для каждой пустой полосы ___...__, xor их и вернуть, если результат равен 0. Я думаю, вы можете получить подсказку о том, как вычислить значения, если вы попытаетесь вычислить первые 50 из них.
Поскольку я не люблю использовать этот сайт в качестве замены для работы, я останавливаюсь здесь.Надеюсь, вы сможете закончить, если вы застряли, задавайте вопросы.