X-O в PSPACE/решение Сеилов

Материал из DISCOPAL
< X-O в PSPACE
Версия от 03:53, 11 мая 2017; Темирлан (обсуждение | вклад) (Новая страница: «*X-O в PSPACE На рабочей ленте для каждой клетки игровой доски заведем свою ячейку. Использ…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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