ГоБиблиотека: ГоНаПК/ПроГо/Термит

Го-термит – специальное насекомое для статического анализа. Основывается на «тьюрмите» – машине Тьюринга, работающей не на ленте а на плоскости (двумерной). Поправка: поразмыслив решил, что аналогия с тьюрмитом неудачная, вообще-то, это больше похоже на клеточный автомат...

• Работает так:
  
  • начинает на доске, где каждое поле имеет начальное состояние Х (черный камень), О (белый камень), . (свободно)
  • каждую секунду клетки меняют свое состояния в зависимости от состояния себя и непосредственных соседей.

Карта корневого раздела — ГоНаПКдерево?

/Автор/АлексейБирюков

Оглавление документа

Распознавание большого глаза

Распознавание цепи

Распознавание бамбука

Комментарии

Распознавание большого глаза

Первый шаг – распознавание «хвостиков»
(.)(N * X + .) -> X_hvost где N in {1,2,3}
т.е. Если пустое поле окружено несколькими черными камнями и пустым, то это хвост.

Хвост

(.)( N * X_hvost + M * X ) -> X_bigEye где N > 1
т.е., если свободное поле окружено по крайней мере двумя хвостами одного цвета и камнями того же цвета, то это большой глаз
Связность окружения глаза пока не рассматривается %)

данный термит может распознать такие ситуации:

Диаграмма1

Диаграмма2

Диаграмма3

---

Распознавание цепи

Каждому полю назначается свой id. Ищем id цепи (id_main), изначально это id поля

(X,id_main)( id1, id2, id3, id4 )
Если id_main<max(idN),
то id_main = max(idN) НЕ STOP
иначе STOP

повторять, пока все поля не будут в состоянии STOP

(Это обычный алгоритм раскрашивания замкнутой области)

---

Распознавание бамбука

(.)( X_id_main_1, X_id_main_2 ) -> X_banboo_candidate_id_main_1_id_main_2
т.е. если у пустого поля два соседа одного цвета, принадлежащие двум цепям, то это – кандидат в бамбуки.

Диаграмма1

(X_banboo_candidate_id_main_1_id_main_2)( X_banboo_candidate_id_main_1_id_main_2 ) -> banboo
т.е. если у кандидата сосед – кандидат, то бамбук

Диаграмма1

---

Комментарии