Модель игры

В связи с успешным засорением темы философскими изысками на тему... пришлось поступить радикально, что буду делать и в дальшейшем, при необходимости.

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

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

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

3. Из разделов математики наиболее нам подходит теория графов: как правило, теория игр изучается в рамках инструментария этой теории. Тогда надо описать игру го в терминах теории графов.

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

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

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

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

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

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

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

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



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

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

Сергей!
С теорией графовь знаком не по наслышке, пробовал применять ее
но толку было мало....((( может шел не в верном направлении.

Сейчас прорабатываю идею LES'а изменени связей. В графическом представлении....
но она может применяться только для середины партии, когда есть готовые группы.

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


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

С уважением Кит.

Определим на множестве пунктов P бинарное симметричное отношение "соседние" R(p1,p2).
Назовем гобаном G множество пунктов.
Позиция s = {G,f} - гобан, плюс функция f, сопоставляющая каждому из пунктов значение "свободно"(N), "белый"(W), "черный"(B).

Определим
Enemy(W) = B;
Enemy(B) = W;
Enemy(N) = void;

Определим над множеством пунктов предикат "может дышать" D.
All p in G
{
f(p) = N => D(p) = void
f(p) = x, Exist p1 { R(p,p1), f(p1) = N } => D(p) = true
f(p) = x, Exist p1 { R(p,p1), f(p1) = x, D(p1) } => D(p) = true
(иначе) => D(p) = false
}

Назовем позицию s валидной, если
All p in G { D(p)=/=false }

Определим над множеством позиций функции удаления бездыханных камней каждого цвета DEL_w(s), DEL_b(s)

DEL_х( {G, f} ) = {G, f1}
где All p in G
{
f(p) = x, D(p) = false => f1(p) = N
(иначе) => f1(p) = f(p)
}

Будем говорить, что из позиции s={G,f} можно перейти в позицию s1={G,f1} ходом цвета х, если
s1 = s (пасс)
или

Exist s2={G,f2}
{
Exist p in G,
{
f(p) = N, f2(p) = x // этим камнем ходим
All pp =/= p f2(pp)=f(pp) // остальные пока на месте
}
}
, s1 = DEL_x(s2), s1 - валидная.

ВСЁ
Здесь не учтено ко

А как же начальные ходы учитывать?

Уважаемый Les! Для кого Вы это пишите? Если хотите формализовать, то начинайте с самого начала, а то Вас никто не поймет. Определите язык формул и терминов, которым Вы собираетесь пользоваться и т.д.

Даже мне не хочется разбираться в такой формализации.



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

Ссылка на сайт по нечеткой логике (прислал Владимир)
[fuzzyfly.chat.ru]

Вообще-то, именно такие заклинания я рисовал в аспирантуре... правда так и не защитился :.(

Я закончил восстанавливать свою программу «играющей доски». На данный момент она съедает камни, не дает делать самоубийственные ходы и запрещает простое ко. Сейчас я тестирую ее и если кого либо интересуют исходники (на С++ с использованием MFC) могу послать по e-mail.
Теперь немного о том как в программе хранятся данные. Иерархия классов (начиная с самого нижнего) такова:
1. Класс CpointArray – массив точек.
2. Класс CСhain – используется для хранения информации о цепочке камней и содержит следующие члены:
CPointArray m_StonesArray - массив камней цепочки
int m_NumChain - номер цепочки камней
int m_NumLib - число свобод цепочки
3. Класс CGroup – используется для хранения информации о группе камней (под группой камней я понимаю совокупность цепочек, имеющих общие точки свободы) и представляет из себя просто список элементов типа CСhain.
4. Класс CGoDoc – верхний класс иерархии, используется для хранений всей информации о позиции на доске и содержит следующие члены:
int m_Col - цвет очередного хода
int m_NumOfChain - номер последней цепочки на доске
int m_iSZ - размер доски
int** m_Stones - массив камней
CMyRect m_DeckRegion - прямоугольник описывающий участок доски
CList <CGroup, CGroup&> m_MasGroup - список всех групп расположенных на доске

Теперь некоторые пояснения.
1. Вся описанная структура данных обновляется динамически после каждого сделанного хода, т.е. отслеживается объединение цепочек камней, объединение групп камней, разрезание группы камней.
2. Массив m_Stones представляет из себя двумерный массив в котором хранится информация о расположенных на доске камнях. Он используется для двух целей:
1. На его основании рисуются камни на доске.
2. Он используется для заполнения структуры данных описанной выше, т.к. с его помощью проще производить операции связанные с координатами камней, чем с использованием списка групп.

Есть и другие классы, которые могут быть полезны, например класс CGroupLinkInfo – хранящий матрицу смежности для массива цепочек камней.
Предлагаю всем желающим использовать данное представление как базовый движок программы.

Михаил

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



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

Вот тут думаю над еще одной идеей -
Так существует определенное и ограниченное число базовых и фундаментальных фигур и их связок - так легче будет "плясать" от них.
Запрограммировать такую фигуру, гораздо легче, чем описывать рисунок игры. Тем более что получиться чисто векторный вариант программирования направления построения законченной фигуры. Что является , само по себе, классическим вариантом ОрГрафов.

как рассматривается эта идея, с точки зрения программистов? и не только...........?



Ну что это за Жизнь... без примеси сумасшествия совсем не интересно......
[www2.psy.uq.edu.au]
[www.mercury.csse.unimelb.edu.au] - Крутой Меркурий
[habrahabr.ru]
[shogi.by] - Shuogi

Как игрок, я думаю, что эта идея интересна и соответствует интуитивному подходу игрока к оценке статуса групп. В программировании тоже может оказаться продуктивной...



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

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

Может продуктивна идея класса? Каждая форма имеет цепочку состояний: от минимальной и далее, в зависисмости от контекста, окружения, развивается до максисмальной с полностью оформленными границами (или почти полностью?). Что-то размытое получается, однако...



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

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

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



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

А, то есть имелось в виду отношение не между стадиями жизни группы, а идея классифицировать группы по форме (косуми, кейма-симари,...) или статусу:

.......
.*.*.*. -> "стенка"
.......

.......
******* -> "стенка"
0000000

.****
*.*.* -> "живая"
****

Классификация по форме может быть частью распознавалки, а по статусу - использоваться для окончательной оценки.

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

Вообще, чтобы была тема обсуждения, надо уточнить принципы классификации.

Все правильно - Имелось ввиду базисный набор в отрыве от контекста.

Лес! Что имелось ввиду -
надо уточнить принципы классификации ---

?



Ну что это за Жизнь... без примеси сумасшествия совсем не интересно......
[www2.psy.uq.edu.au]
[www.mercury.csse.unimelb.edu.au] - Крутой Меркурий
[habrahabr.ru]
[shogi.by] - Shuogi

Мужики!
Вы скоро меня раскачаете на написание программы?!
Но, чур! Я не лечу в программирование. Я делаю общую концепцию программы, как минимум на 1 дан. Я выдаю кусок задания, а программист сам должен его реализовывать. Надо приготовиться к 2-3 годам работы.
Неплохо бы сотрудничать с Китом или другим сильным программистом.
Жду предложений! Про миллион не забудьте.
С уважением

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

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



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

Все очень просто, берем кредит в банке на 3-5 лет под разработку этой задачи :)