Перейти к содержанию

Новости го · хроника событий, люди и первоисточники

ГО-ДАЙДЖЕСТВесь мир го. История продолжается.
Материалов на сайте: 1698Историческая хроника 400–2026
Рубрики
Найти по теме
Страны и регионы

Весь архив: статьи и биографии. Материал может относиться к нескольким странам.

Выбрать другую страну
Исторические периоды
■ Популярные темы архиваЧемпионатыЛенинградКонгрессы
Архивная хроникаНаука и технологии

Вулф доказал вычислительную трудность разделённого эндшпиля го

Новый результат касался даже позиций, где живые камни отделяют локальные области друг от друга.

2002ВРЕМЯ СОБЫТИЯ

В 2002 году сборник MSRI More Games of No Chance опубликовал работу Дэвида Вулфа Go Endgames Are PSPACE-Hard. Автор рассматривал окончания, в которых каждая локальная область имеет каноническое дерево вариантов полиномиального размера и отделена от остальных живыми камнями.

Для этого семейства позиций доказана PSPACE-трудность. Независимость участков не снимает общей сложности выбора: на очередном ходу игрок решает, в какой из областей продолжать игру. Доказательство связывало задачу с булевыми формулами с кванторами через последовательность вспомогательных игр.

Работа дополнила математические способы анализа йосэ оценкой их общего вычислительного предела. Результат относится к семействам позиций растущего размера, а не к утверждению, что нельзя сильно играть на обычной доске. Вулф отдельно ограничил используемое понятие эндшпиля и не заявил решения вопроса о сложности всех правил с повторениями.

Основание материала

Источники и проверка

  1. Исследование

    Вулф: трудность эндшпиля го

    MSRI 42, 2002, с. 125–136

    Проверен:

Раскрытие связи

Материал входит в общий проект сайтов о го.

История продолжается.

Другие события в хронике →