Алгоритмизация

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

Ввиду того, что в нескольких постингах прозвучало недоумение по поводу предлагаемых ниже определений - мол, зачем все это в правила? - поясняю: данная тема не столько о формулировке правил, сколько о следствиях, таких как понятия: "глаз", "точка дыхания", "группа" и т.д.



Отправка отредактированного (14/11/03 09:51)

Смотри в корень

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

Для пояснения понятия "позиция" нужно формализовать описание процесса игры. Для этого введем понятие начальной позиции как некоторого распределения камней на доске, с которого начинается весь процесс. Формально такое распределение задается с помощью целочисленной матрицы (9х9, 13х13, 19х19 или, в общем случае, NxM), в которой элементы принимают значения, скажем, 0 - для пустых пунктов, 1 - для занятых черными камнями, 2 - для занятых белыми камнями. Возможны и другие способы формального описания расстановки камней на доске го, но предпочтительнее матричная форма, аналогичная предложенной. Кроме расстановки камней нужно для определения начальной позиции указать очередь хода, т.е. какая сторона (белые или черные) могут изменять начальное распределение и таким образом совершать ход.

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

Следует отметить, что для учета правила "ко" необходимо элементу матрицы, соответствующему недоступному, но свободному пункту, приписывать значение, отличное от уже использованных. Например, значение -1.

Соседний пункт - это пункт, соответствующий соседнему элементу матрицы распределения камней по вертикали или горизонтали. У соседних элементов матрицы в традиционном индексном представлении [aij] один индекс совпадает, а другой отличается ровно на единицу.

ОПРЕДЕЛЕНИЯ:

1. Определение пути (по индукции):
1.1. Один пункт образует путь.
1.2. Если к пути добавить пункт, соседний с одним из пунктов пути, то получим путь, если при этом у каждого пункта пути оказывается не более двух соседних пунктов, принадлежащих этому пути.
1.3. Если два пункта принадлежат одному пути, то говорим, что данный путь соединяет эти пункты.

2. Множество пунктов доски связно, если для любых двух элементов этого множества можно указать путь, их соединяющий, полностью лежащий в данном множестве (т.е. являющийся подмножеством данного множества).
Комментарий: связные множества пунктов - это множества, представимые в виде объединения путей.

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

4. Рассмотрим какое-либо множество пунктов и множество всех соседних пунктов для всех пунктов этого множества. Затем возьмем теоретико-множественную разность этих множеств, т.е. дополнение одного множества относительно другого. Полученное множество назовем границей рассматриваемого множества пунктов.

Комментарии.

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

Поэтому я поступаю последовательно. Путь - обычная вещь в геометрии, "параметризованная кривая". Я беру аналог для дискретного пространства игровых пунктов. В классическом определении связности в геометрии (не в топологии!) используется понятие пути. Достаточно проверить, что можно проложить путь между любыми двумя пунктами - и ясно, что множество связно.

Далее, от понятия связности переходим к понятию цепи (не группы! - это потом). Именно так уже рассматривались "непрерывные группы камней" (не вспомню сейчас, кто первым ввел понятие цепи). Причем я ввожу связность для множеств пунктов, а потом множества камней можно идентифицировать по множеству пунктов, которое эти камни занимают - так правильнее методически.

А теперь можно попробовать построить формальное определение группы, группы с двумя глазами, территории - все эти понятия так или иначе связаны с понятием "связность". Так, территория образуется из связных множеств пунктов, граница которых заставлена камнями одного цвета.

Может это все и кажется туманным для нематематиков, но зато это строго формальные определения, позволяющие корректно переходить к алгоритмам и программированию элементов игры го.



Отправка отредактированного (14/11/03 09:56)

Смотри в корень

Сергей, в определении, которое ты дал, нет места понятию "повтор позиции".

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



Отправка отредактированного (12/11/03 09:03)

Смотри в корень

Определения.

1. Свободный пункт, принадлежащий границе цепи, называется точкой дыхания.

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

3. (См. новую редакцию пунктов 3-5 в ДОПОЛНЕНИЯх) Старая редакция: "Точка дыхания называется глазом, если ее граница полностью занята камнями, принадлежащими одной цепи. 4. Две точки дыхания, не образующие связное множество, называются глазами, если они являются общими точками дыхания двух или трех группирующихся цепей одновременно и их граница полностью занята камнями, принадлежащими этим цепям. 5. Большим глазом называется, по аналогии с предыдущим, любое связное множество из более чем одного свободного пункта, если граница "глаза" полностью занята камнями, принадлежащими одной цепи. Аналогично обобщается определение 4."

6. Группой называется цепь либо множество группирующихся цепей.

Комментарий. Ясно, что эти определения несовершенны в чем-то и недостаточны для программирования го. Приглашаю к обсуждению.

ДОПОЛНЕНИЯ

Здесь будут помещаться те дополнения, которые возникнут в ходе обсуждения.

2.1. Любое количество цепей будем называть группирующимися цепями, если их можно представить в виде объединения последовательной цепочки группирующихся пар цепей так, что в каждой паре одна из цепей входит в предыдущую пару, а другая - в следующую.

3. Термин "глаз" будет употребляться, возможно с различными прилагательными, для обозначения связного множества пунктов, все граничные пункты которого заняты камнями одного цвета, а внутри самого множества могут находиться только камни соперника, в соответствии с правилами игры не являющиеся живыми.

4. Все глаза можно разбить на три категории:
- глаз внутренний (ограничен одной цепью);
- глаз межцепной, формируемый более чем одной цепью и содержащий хотя бы один пункт, являющийся граничным более чем для одного камня какой-либо из этих цепей;
- глаз типа полюс, его граница формируется 2-4 цепями совместно, причем каждая цепь имеет только один камень, для которого данный глаз является точкой дыхания.

5. Глаз называется ложным, если он не является внутренним и не выполняются оба следующих условия:
- каждая из ограничивающих его цепей ограничивает также внутренний глаз или другой глаз совместно с одной из тех же цепей, которые участвуют в ограничении данного глаза;
- расстановка камней может быть приведена к ситуации, описанной в предыдущем случае, путем занятия каких-либо других глаз.

В дальнейшем под термином "глаз" будем понимать только не ложные глаза, если не оговорено иное.



Отправка отредактированного (13/11/03 10:15)

Смотри в корень

Сергей, определение глаза мне не нравится. В позиции - черные: А1, А2, B2, C1, D2, E2, E1; белые: C2, C3; пункты B1 и D1 - могут быть глазами, если черные камни соединить снаружи вокруг белой группы.

Другой пример. Черные стоят по первым линиям кроме угловых пунктов. Угловые пункты, безусловно обеспечивают жизнь всех черных камней, но в твоем определении это не глаза.

Сергей , я все-таки хочу понять , что значит формализация . Вот Ваши определения - как бы формализованы , да ? Ну и в чем это проявляется ? Чем например Ваши определения формальнее моих ?

И мои , и Ваши рассуждения записаны на естественном языке - значит они не формальны в самом прямом смысле . Цель и тех и других - задать логические связи между игровыми понятиями (точка , камень , группа , съедение) .

Я не спрашиваю , чем Ваши определения лучше - это слишком многосмысленный вопрос , но чем они формальнее ? Большей трудностью для восприятия ? Упоминанием теории графов ? Большим числом вспомогательных понятий ? Предложениями по алгоритмизации ? Большей логической строгостью ?

Следующий вопрос - зачем нужна эта формализация . Из моих вышеперечисленных гипотез некоторую ценность имеют 2 последние - помощь в алгоритмизации и логическая строгость .

Вы представляете себе , что значит проверить связность , пользуясь понятием "путь" , прокладывая эти пути для каждой пары камней , обходя чужаков и пустоты ? Каждый , кто будет программировать Го , в первую очередь докажет , что проверка связности не требует путей , а сводится к учету имеющихся камней и групп , после чего рассмотрение очередного камня требует присоединения его к одному из существующих объектов , объединения объектов или создания нового объекта .

> Соседний пункт - это пункт, соответствующий соседнему элементу матрицы распределения камней по вертикали или горизонтали. У соседних элементов матрицы в традиционном индексном представлении [aij] один индекс совпадает, а другой отличается ровно на единицу.

Вот насчет индексов - да , так можно . Насколько полезен такой совет - другой вопрос .

Короче говоря , я не вижу помощи для программирования .

Логическая строгость - это полнота и непротиворечивость . Да , в Ваших определениях она есть . Но Ваше твердое молчание (в ответ на мои просьбы найти логический дефект в моих определениях и правилах) означает , что Вы также признаете логическую строгость моей системы .

Вопросы закончены . Их три - что такое формализация , зачем она нужна и есть ли она в моих , Ваших и Максовых правилах .

Теперь мое мнение о Вашем проекте . По-моему , Вы пытаетесь уточнить японскую систему правил , придать этой системе строгую , полную и непротиворечивую формулировку . Это чертовски трудная и возможно невыполнимая задача . Если Вы ее решите - это будет действительно великое достижение . Но сугубо теоретическое . Нельзя переформулировать Ваши правила достаточно просто и последовательно для обучения игре и для турнирной практики . А что пользы ученику от того , что все те же отговорки при обучении Го по японским правилам можно дополнить еще одной отговоркой - мол , теоретически правила хороши ?

P.S: Я начал этот постинг в 11:22 , извините если что-то пропустил .



Наш рот всегда открыт для диалога (c) Владимир ВишневскийOkruzhor (экс-Игозавр)

Илья, мне кажется мы говорим все время о разных вещах. Я вообще не обсуждаю формулировку правил для методички или что-то подобное. В науке сложилась определенная система изложения, когда обычным вроде бы языком излагаются формальные вещи. Я стараюсь придерживаться этой системы. Главное в таком изложении - формальная строгость, когда из начальных аксиом, с помощью введения новых понятий, можно выводить строго логически новые утверждения-теоремы и т.д. Прежде чем что-либо программировать, нужно убедиться в корректности того, что программируется. Например, алгоритм заливки, как Вы его назвали, должен быть доказан. И т.д. Если в моем подходе что-то не годится сразу как алгоритм, то это не декларировалось и не обещалось. Только в помощь, в идейном плане в первую очередь. Если мы не поймем, как описать понятие "группа" с помощью формальных структур, то вряд ли сможем написать хорошую программу игры в го (я лично не собираюсь писать такую программу).
Если то, что я предложил, никому не нужно - хорошо, не буду развивать эту ветку...



Смотри в корень

Да, это не глаза, так как здесь три, а не две цепи формируют границы "двух псевдоглаз". При соединении двух цепей в одну, как ты и предложил, получается два глаза, в полном соответствии с определением.

Да, я и отмечал, что определения не совершенны. Надо дополнить. Думаю. Ты тоже подумай.

Может быть дополнить так: две точки дыхания называются глазами, если ситуация сводится к пункту 4 путем затыкания некоторых общих для нескольких группирующихся цепей граничных пунктов (отличных от выделенных двух пунктов) , также претендующих называться глазами (т.е. граница которых полностью заставлена камнями группирующихся цепей).



Отправка отредактированного (12/11/03 14:53)

Смотри в корень

---- 3. Точка дыхания называется глазом, если ее граница полностью занята камнями, принадлежащими одной цепи.

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


Кажется, здесь полное и достаточное описание глаз.
Так что споры по поводу не достаточности этих определений не верны.

Кто не понял, прошу еще раз очень внимательно прочитать, пока станет понятно........

Уважаемый kit! Пример Сергея Межова с опоясывающей доску группой без угловых камней показал дефект определения. Я уже внес дополнение в постинг "Точки дыхания...".

Сергей, предложение в варианте тоже не проходит. Если немного расширить мой первый пример, легко получить три цепи, каждая из которых замыкается на два несвязных пустых пункта, например, на противоположных сторонах доски.

Надо в определении вместо "двух и только двух" написать "двух или трех". Четыре без самопересечения не может быть, либо сводится к рассмотренным случаям.



Отправка отредактированного (12/11/03 15:38)

Смотри в корень

Мне кажется, что введение понятий "глаз" и "глаза" вообще не требуется в правилах.

Эта тема не про правила, а про следствия, в основном :).

Г-н Серпов, не обижайтесь, пожалуйста!!!!!
Очень интересная ветка. Не надо её закрывать!!!

Илье: действительно, и я, и ты и Серпов используем одни и те же слова, но результат разный.

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

Я хотел сделать то же самое, но более доступным языком, в надежде, что ты заметишь разницу в подходе к изложению. Ты не заметил.
Удивительно то, что ты не заметил качественного иного взгляда на формулирование правил и в текстах Серпова. Для меня же разница очевидна.