X-O в PSPACE/решение Сеилов — различия между версиями

Текущая версия на 00:53, 11 мая 2017

• X-O в PSPACE

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