Алгоритм Бенсона (Go) - Bensons algorithm (Go)
| Часть серии по |
| Идти |
|---|
 |
| Особенности игры |
|
| История и культура |
| Игроки и организации |
| Компьютеры и математика |
В игре Идти, Алгоритм Бенсона (названный в честь Дэвид Б. Бенсон ) можно использовать для определения камней, которые не могут быть захвачены независимо от того, сколько ходов подряд получает противник, т.е. безусловно жив.[1]
Алгоритм
Не теряя общий смысл, мы описываем алгоритм Бенсона для черного игрока.
Позволять Икс быть набором всех черных цепей и р быть набором всех черных областей Икс. Затем алгоритм Бенсона требует итеративного применения следующих двух шагов до тех пор, пока ни один из них не сможет удалить больше цепочек или регионов:
- Удалить из Икс все черные цепи с менее чем двумя важными закрытыми черными регионами в р, где закрашенная черным область жизненно важный к черной цепи в Икс если все его пустые пересечения также являются свободами цепи.
- Удалить из р все области, окруженные черным, с окружающим их камнем в цепочке не в Икс.
Последний набор X - это набор всех безусловно живых Чёрных цепей.[2]
Смотрите также
- Computer Go - Область искусственного интеллекта, посвященная созданию компьютерной программы, играющей в го
- Стратегия и тактика игры
Рекомендации
- ^ Тапани Райко (5 мая 2005 г.). «Алгоритм Бенсона». Получено Двадцать первое марта, 2012.
- ^ "Библиотека сенсея: определение безусловной жизни Бенсоном". Получено Двадцать первое марта, 2012.
- Дэвид Б. Бенсон (1976). «Жизнь в игре го» (pdf). Информационные науки. Эльзевир. 10 (2): 17–29. Дои:10.1016 / s0020-0255 (76) 90554-5. Получено Двадцать первое марта, 2012.