X-O в PSPACE/решение Сеилов
Материал из DISCOPAL
На рабочей ленте для каждой клетки игровой доски заведем свою ячейку. Используем рекурсивный алгоритм - ставим крестик/нолик и проверяем уже новый экземпляр на выигрышность. Позиция выигрышная тогда и только тогда, когда из нее есть путь в проигрышную, а проигрышная тогда и только тогда, когда все пути из нее ведут в выигрышные. Можно проверять доску на полиномиальной памяти непосредственно на то, есть ли в ней строка из нулей/крестиков - это выигрышная для нулей/крестиков стратегия (граничное условие). и дальше перебор всех вариантов (ячейки можно использовать много раз, это соответствует тому, что стерли крестик/нолик и перешли к рассмотрению другой конфигурации). Ясно, что все эти операции на полиномиальной памяти.
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.