Проблемы формализации
Игра го, по типу используемой для ее формализации математической модели, относится к так называемым "играм двух лиц с полной информацией". Для таких игр понятие позиции принято рассматривать в терминах теории графов, ставя в соответствие каждой позиции - вершины некоторого ориентированного графа, каждому ходу - ребра, соединяющие вершины. Вот в этом ключе и будем строить математическую модель игры го и сформулируем для начала основные тезисы:
1. Для алгоритмизации и программирования нужно формализовать правила игры го, включая понятие начальной позиции, правила совершения хода (оператор перехода) как способ, алгоритм, процедуру получения новых позиции (пока понимаем как расстановку камней), само понятие "позиция".
2. Работа должна проводиться в формальном терминологическом поле математики и ее разделов (других инструментов у нас пока нет, разве что какие аналоговые устройства физики предложат, или не абстрактные, а натуральные нейро-сети - биоматематики), с использованием всего наличиствующего мат. аппарата.
3. Из разделов математики наиболее нам подходит теория графов: как правило, теория игр изучается в рамках инструментария этой теории. Тогда надо описать игру го в терминах теории графов.
4. Понятие графа - первично и не подлежит обсуждению. Граф игры - это направленный граф, т.е. совокупность вершин и ребер (известные множества, могут быть большими и необозримыми), и между этими множествами установлены определенные взаимосвязи (в математической терминологии - "отношения", т.е. подмножества прямых произведений множеств): все ребра соединяют какие-то вершины и указано направление на каждом ребре, т.е. из какой вершины можно в какую перейти, и есть несколько вершин (корневых), из которых выходят ребра, но в которые не входит ни одного ребра. Есть концевые вершины, из которых, наоборот, не выходит ни одного ребра. Этот направленный граф может иметь или не иметь циклов (кольцевых последовательностей вершин и ребр). Если нет циклов и корневая вершина - одна, то граф называется деревом.
5. Для описания го в указанных рамках (построение математической модели игры) нужно сопоставить ее "неформальное", содержательное описание с формальной конструкцией - направленным графом, как он описан выше. Т.е. необходимо построить отображение материала, правил игры и других атрибутов го в множество направленных графов. При этом, следуя логике применения теории графов в теории игр, каждую вершину этого образа игры - графа игры - будем называть позицией, и как мы определим отображение в множество вершин, так у нас и сформируется понятие "позиция" в содержательном смысле игры го. Ребра графа определяются по описанию правил совершения хода и в зависимости от очереди хода в той или иной позиции-вершине считаем соответствующую вершину и все выходящие из нее ребра окрашенными в белый или черный цвет. Кстати, в соответствии с правилом о пасе, для каждой вершины есть следующая вершина (т.е. в которую из данной идет ребро) с той же самой расстановкой камней, но окрашенная в противоположный цвет. Конечные вершины - это позиции, в которых (не по сдаче или судейскому решению) однозначно определен результат партии. Такие вершины называются иногда "листьями".
Вот и давайте последовательно определять элементы модели: начальные вершины, правила перехода (ребра), множество всех вершин, листья. Первый шаг: начальные вершины - одна в каждой из нескольких моделей игры при различной форе (от 0 до ... камней), или же считать все модели одной, когда в начальной позиции (пустая доска, ход черных) белые начинают делать пасы...
Другой аспект, о котором надо договориться - конечные позиции. Для упрощения и устранения возможных неоднозначностей предлагаю строить полностью абстрактную, независящую от коми и других аналогичных условностей, модель. Тогда конечные вершины-позиции - это те, в которых действительно теоретически определен результат партии в очках (раздел территории осуществлен полностью, пленные подсчитаны, коми не учитываем).
А сейчас мы уже готовы взяться за понятие вершины графа (т.е. определеить, что же такое будет у нас называться позицией). Из всего вышеизложенного следует, что позиция это (по индукции):
- начальная позиция;
- позиция, получающаяся из известной, уже определенной позиции с помощью оператора перехода. На графе игры изображаем сей факт ребром, ведущим из известной позиции в новую.
Так как начальная вершина-позиция определена, то нужно определить оператор перехода. Считаем, что новая вершина-позиция получена из известной ходом черных, если расстановка камней отличается добавлением одного камня ... и т.д. Правило ко надо трактовать как запрет повторения расстановки камней (неважно, сколько пленных лежит в чашах) при одной и той же очереди хода.
Отправка отредактированного (21/11/03 14:54)
Смотри в корень