Проблемы формализации

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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



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

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

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

Программист-человек понял - это значит, что он формализовал.

Не словоблудствуй и не впадай в философские парадоксы. Тем более в ветке, посвящённой формализации.

Представь себе ситуацию таким образом: есть явление природы, которое мы хотим описать в математических терминах. Тщательно обдумываем то, как мы себе представляем себе это явление и быстренько записываем в виде мат. формулы.

Здесь встаёт вопрос о том, как мы представляем себе явление. Неудивительно, что разные люди представляют явление по разному. Главное понять, что могут быть разные взгляды на явление, тогда станет возможным выписать формулу, описывающую явление в наиболее общем виде. А потом уже перейти к частностям.

Тогда и доска сможет быть 13х25, и ко - не только расстановка камней, но и очерёдность хода, и номер хода, и пленники впридачу.

БОлее конструктивно, я считаю, получше обдумать первый пост Серпова, внести замечания и доплнения. Тогда общими усилиями получится чтонить дельное.

А зачем грызть горло за несовпадение в деталях? Горло не казённое.

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

> Программист-человек понял - это значит, что он формализовал

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

> Не словоблудствуй и не впадай в философские парадоксы. Тем более в ветке, посвящённой формализации.

Любовь к философским парадоксам можешь разделить с Сергеем Александровичем , у меня ориентация на простоту и логичность , не ревнуй понапрасну .

> Главное понять, что могут быть разные взгляды на явление, тогда станет возможным выписать формулу, описывающую явление в наиболее общем виде.

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

> Тогда и доска сможет быть 13х25, и ко - не только расстановка камней, но и очерёдность хода, и номер хода, и пленники впридачу.

Тогда - это когда ? Когда признаешь разнобой мнений ? Когда примиришь мнения в обобщающей формуле ? У меня для тебя СУРПРЫЗ ! Благая весть ! Все это "может быть" и есть и всегда было , без всяких условий и усилий .

Формат доски - не проблема ни для каких правил . Учет очередности хода в рациональном правиле ко сделан по-разному в разных системах , но ситуация с этим учетом или неучетом абсолютно ясная .

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

> БОлее конструктивно, я считаю, получше обдумать первый пост Серпова, внести замечания и доплнения.

Ну и кто тебе мешает ? Уж не мои ли скромные напоминания , что проект надо бы начинать с постановки задачи ?



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

Тебе надо молоко выдавать. За вредность.

Максим Подоляк писал(а):

> Тебе надо молоко выдавать. За вредность.

Нет . Мне (за мою вредность) - цикуту .

А молоко (опять же за мою вредность) - Сергею Владимировичу . Придираюсь , мешаю . Критикую проект проекта . Кричу : - Фундамент роете , а число этажей не знаете !



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

Это в форум ОФФТОПИК.

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

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



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

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



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

Опять началосььь...................((((((
Сколько можно...............

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

Давайте обсуждать только тто что предлагается, а не ваши ЛНВЫЕ КОММЕНТАРИИ!!!!

Простовы с такими коментами мешаете!

Просто праздник какой-то (с) Карабас-Барабас

Тем, кто просто хочет потрепаться, думаю, хватает места в других темах. Здесь надо как-то конструктивнее. Я свое дело сделал - давайте двигаться дальше. Иначе вообще заброшу эту ветку...



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

> В нашем случае все нюансы правил, которые так страстно обсуждались, несущественны. Главное - должен быть оператор перехода, а его внутреннее устройство - технические детали. Сути это не меняет.

Вот это круто ! Тогда исключается специфика Го ? И как итог проекта заново родится абстрактный минимакс с отсечениями ?

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

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

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



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

Сути все это не меняет. Либо мы строим мат. модель, либо продолжаем трепаться (имхо)...



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

Господа!
Не будем грызь горло друг другу. Все это происходит потому, что нет четко обозначенной цели чего мы хотим от программирования Го. Если мы ходим научить играть программу на 1 дан, то это одна цель, если -просто играть с хорошим сервизом редактирования партий, то -то это другая цель, если мы хотим иметь редактор дзесэки, фусэки, ёсэ, задач и учебных программ - то это третья цель. ОПРЕДЕЛИТЕСЬ!?
Но если цель - 1дан, то без формализации не обойтись, а вэтом случая как я уже указывал без графов и теории игр не обойтись. Однако не все так просто (трудно?). На мой взгляд изобретать велосипед вновь не надо. Существует много хороших играющих Го программ. Самое простое проанализировать их достоинства и недостатки. Достоинства (отдельные задачи, ветви графа) взять целиком , недостатки переписать. Предвижу, что многие скажут, что легче написать новую программу, чем совершеннствовать старую. Что ж дерзайте. Но всетаки многие задачи будут дублироваться. Поэтому легче целиком взять (купить) программный продукт, хорошо реализующий ту или инут подзадачу и как бы в упаковке вставить его в новую программу.
Мне видиться, что для того чтобы научить программу играть в силу 1 дана ее надо учить как ребенка, а значит не один год. Одучить правилам, дзесэки, фусэки, ёсэ тесудзи, баланс территории и влияния и так далее (а по простому надо в машину заложить всю эту базу или книги).
С уважением

Кит , нельзя программировать неизвестно что . Но тебе можно .

Нельзя программировать игру , не определяя ее цели . Тебе можно .

Нельзя бездоказательно объявлять любые возражения левыми комментариями . Ты - называй что хочешь как хочешь .

Но неужели и все здесь присутствующие желают формализовать или программировать игру без правил ?



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

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

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

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

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



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

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

Приглашаю оставшихся участников в новую ветку - про бег в мешках в подфоруме "Методология Го"



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

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

Т. е. второй пасс окрашивает вершину в цвет конечной.
Отсюда следует запрет на пасс в процессе партии. Интересно, мы кажется пришли к древнейшим из известных правил.