X-O в PSPACE/решение Сеилов — различия между версиями
Материал из DISCOPAL
Темирлан (обсуждение | вклад) (Новая страница: «*X-O в PSPACE На рабочей ленте для каждой клетки игровой доски заведем свою ячейку. Использ…») |
(нет различий)
|
Текущая версия на 00:53, 11 мая 2017
На рабочей ленте для каждой клетки игровой доски заведем свою ячейку. Используем рекурсивный алгоритм - ставим крестик/нолик и проверяем уже новый экземпляр на выигрышность. Позиция выигрышная тогда и только тогда, когда из нее есть путь в проигрышную, а проигрышная тогда и только тогда, когда все пути из нее ведут в выигрышные. Можно проверять доску на полиномиальной памяти непосредственно на то, есть ли в ней строка из нулей/крестиков - это выигрышная для нулей/крестиков стратегия (граничное условие). и дальше перебор всех вариантов (ячейки можно использовать много раз, это соответствует тому, что стерли крестик/нолик и перешли к рассмотрению другой конфигурации). Ясно, что все эти операции на полиномиальной памяти.