В 2002 году сборник MSRI More Games of No Chance опубликовал работу Дэвида Вулфа Go Endgames Are PSPACE-Hard. Автор рассматривал окончания, в которых каждая локальная область имеет каноническое дерево вариантов полиномиального размера и отделена от остальных живыми камнями.
Для этого семейства позиций доказана PSPACE-трудность. Независимость участков не снимает общей сложности выбора: на очередном ходу игрок решает, в какой из областей продолжать игру. Доказательство связывало задачу с булевыми формулами с кванторами через последовательность вспомогательных игр.
Работа дополнила математические способы анализа йосэ оценкой их общего вычислительного предела. Результат относится к семействам позиций растущего размера, а не к утверждению, что нельзя сильно играть на обычной доске. Вулф отдельно ограничил используемое понятие эндшпиля и не заявил решения вопроса о сложности всех правил с повторениями.
Основание материала
Источники и проверка
- Исследование
Вулф: трудность эндшпиля го
MSRI 42, 2002, с. 125–136
Проверен:
Раскрытие связи
Материал входит в общий проект сайтов о го.
История продолжается.
Другие события в хронике →