Алгоритм Бенсона (Go) - Википедия - Bensons algorithm (Go)

В игре Идти, Алгоритм Бенсона (названный в честь Дэвид Б. Бенсон ) можно использовать для определения камней, которые не могут быть захвачены независимо от того, сколько ходов подряд получает противник, т.е. безусловно жив.[1]

Алгоритм

Не теряя общий смысл, мы описываем алгоритм Бенсона для черного игрока.

Позволять Икс быть набором всех черных цепей и р быть набором всех черных областей Икс. Затем алгоритм Бенсона требует итеративного применения следующих двух шагов до тех пор, пока ни один из них не сможет удалить больше цепочек или регионов:

  1. Удалить из Икс все черные цепи с менее чем двумя важными закрытыми черными регионами в р, где закрашенная черным область жизненно важный к черной цепи в Икс если все его пустые пересечения также являются свободами цепи.
  2. Удалить из р все области, окруженные черным, с окружающим их камнем в цепочке не в Икс.

Последний набор X - это набор всех безусловно живых Чёрных цепей.[2]

Смотрите также

Рекомендации

  1. ^ Тапани Райко (5 мая 2005 г.). «Алгоритм Бенсона». Получено Двадцать первое марта, 2012.
  2. ^ "Библиотека сенсея: определение безусловной жизни Бенсоном". Получено Двадцать первое марта, 2012.