Для почина вот такая идея. По поводу представления позиций. Естественный способ хранения позиции - в виде матрицы. Возникла идея альтернативного представления - в виде графа, где вершины - поля, и ребра, соответственно, соединяют соседние. Что тут хорошего? Этот граф можно сократить следующим образом:
1) Две соседние вершины имеющие одинаковый цвет, стягиваются в одну.
2) Ребра между враждебно окрашенными вершинами удаляются.
3) Кратные ребра удаляются
То есть, группа в сильном смысле (общие точки дыхания) стягивается в одну вершину; у любого ребра хотя бы один из концов - свободное поле; количество точек дыхания группы равно количеству исходящих ребер.
В таком представлении группа в атари - "окрашенная" вершина, соединенная с единственным свободным полем, легко идентифицируются "защелка" и секи... Такое представление медленнее, но умнее, возможно пригодится для расчетов сэмэай и в ёсе.

Лес , придумай теперь как единообразно переменные именовать ...

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

Конечно понадобится топология и в частности теория графов . Придется изучить еще много теорий и чужих наработок ...

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

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

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

А я что-то говорил про коллективное кодирование?

>> Сначала нужно ... Применение....Конечно понадобится... Придется изучить...должно стать на долгие годы ....Меньшими усилиями - можно сделать ...
Вот кажется и все ...

Да не собираюсь я догонять MFGo! Вы же лично не планируете становиться го-профессионалом, тем не менее играете зачем-то.

Лес , прежде всего извините пожалуйста за "ты" .

>>> Для почина вот такая идея. По поводу представления позиций.

> А я что-то говорил про коллективное кодирование?

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

> Да не собираюсь я догонять MFGo!

А что Вы собираетесь делать ? Или что посоветуете делать программистам , желающим в свободное от работы время программировать Го ?

Тогда есть у меня одна интересная идея: раз уж все перед всеми уже расшаркались, давайте конкретнее, чей проект доабатываем?.. или проекта ещё нет?.. как на счёт алгоритмов (готовые есть)? и много всего другого... для начала алгоритм, который реализует правила игры (объясняет компьютеру что есть даме, пункт, камень, итд)...

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

P.S. Также необходимо включить в программe некоторую бд.

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

> есть у меня одна интересная идея

Но она составляет коммерческую тайну ?

> чей проект доабатываем?

Автора ветки

> Про стандартные функции: оценочная - китайский метод

Впервые слышу , очень интересно . Можно его описать , есть ли ссылки ?

> применнение готовых вариантов, форсированные розыгрыши - шаблоны

То же самое . Как определить , что в данной ситуации можно применить некоторый готовый вариант ? Как его найти среди других готовых вариантов ? Какой предпочесть , если подходящих вариантов нашлось много ?

Когда надо заканчивать форсированный розыгрыш ? Я не вижу достаточно четких критериев .

Неужели все это - "шаблоны" ? Стандартизовано , отлажено , доказано , растиражировано ? Ссылки - в студию !

> самообучение - уже не раз доказывали невозможность самоообучения в го...

Но так и не доказали ? Доказательства достаточно ровно одного .

> Также необходимо включить в программe некоторую бд

А разве готовые варианты - не БД ? А какая еще нужна БД ? Эвристики для игры , эвристики для генерации гипотез и т.д. - см. список выше ?

> понять зачем в этой теме идёт такой разговор очень непросто.

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



Отправка отредактированного (25/10/03 02:46)

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

Илья Ветров>>Эта идея не годится "для почина"

Я только хотел дать старт обсуждению алгоритмов. Как самоцель не годится?

Илья Ветров>>А что Вы собираетесь делать ?

Искать идеи.

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

Не слушать ничьих советов :)

Diplomat>>...Представьте себе изменения подобного графа:...

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

Diplomat>>P.S. Также необходимо включить в программe некоторую бд.

БД чего, партий, дзёсеки, форм?

Diplomat>>...или только алгоритмы составлять?

Пока - да.

Ура! Пошло более или менее детальное обсуждение.

Вопрос на засупку - в чем видны минусы существующих алгоритмов?



Невыносимый Cir (кстати, упорно двигающийся в сторону данов).

Еще более простой вопрос - какие существуют, нет, не алгоритмы - подходы к задаче программирования го?



Алексей АКА JumpingRat

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

Китайский метод подсчёта очков используют практически все программы по го. Заключается он вот в чём (для тех, кто знает кит. правила будет легко понятен) : Подсчитываются все территории вместе с границами, те с камнями, пленники ничего не дают (просто это значит, что граница у партнёра меньше -> меньше очков) выигрывает тот у кого эта сумма больше.
На счёт шаблонов. Тут такая вещь, что представить себе что-то ещё очень тяжело... А по шаблонам работают просто все программы (и MFGo тоже). Каждому шаблону даётся накоторая оценка (как называю я "сила шаблона") и применять его в зависимости от позиции ( от "сил" других мест).
База данных нужна фусеки, тк это по шаблонам уже не пойдёт (может показаться, что БД и совокупность некоторго числа шаблонов есть одно и тоже, но это не так) БД нужна очень обьёмная, не менее 10000 фусеки, 5000 джёсеки.
------
Всё это если делается обычная прога хорошо, иначе надо много творчества.

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

Это не для начала . Создание и обкатка алгоритмов - это и есть накопление лемм для итогового доказательства .

> Еще более простой вопрос - какие существуют, нет, не алгоритмы - подходы к задаче программирования го?

Хехе , Алексей , этот вопрос должен быть к тебе , а он - от тебя ...

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

Олег , в оценочную функцию входит не только предполагаемый результат при тривиальном доигрывании . В ней надо учесть силы и слабости камней и зон , перспективы атак , вторжений и захватов территорий (пока ничейных) , короче говоря ВСЮ ТАКТИКУ И СТРАТЕГИЮ игры .

=================

И давайте "для начала" обсудим , кому и насколько нужна программа , отнимающая у человека важный или даже главный стимул творчества в Го ? Может лучше ограничиться более скромными , реальными и полезными задачами ?



Отправка отредактированного (26/10/03 12:45)

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

>Хехе , Алексей , этот вопрос должен быть к тебе , а он - от тебя //

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

>Может лучше ограничиться более скромными , реальными и полезными задачами ?//

Золотые слова! Хотя если кто-либо чувствует в себе силы на большее - почему бы и нет?



Алексей АКА JumpingRat

Ну, что ж. Идеи высказаны хорошие. И замечания то же.

1. Идея LES, по применению неориентированных графов, интересна.
Ранее, я как то рассматривал ее, но упустил детали , которые подсказал LES. Спасибо ему.
2.В любом случае, придется использовать таблицы (они же матрицы).
Ну никуда без них не деться.
3.Работу с матрицей можно вести по обычным законам мат. логики.
4.Далее вся структуры программы, должна разбиваться на множество подзадач, где подзадача решает только ей поставленую цель.
После ее решения, ответ передается в "Вышестоящий орган " ))
т.е. в задачу оценки решений и выбора нужного.

Это пока в кратце.

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

Так что если у кого есть желание могу выслать по мылу.
Формат файлов pdf.

tol'ko chto link obnaruzhil... pochti v temu:

[www.koei.co.jp]

consta

мне тут тоже линки подкинули.
Вот они.

[www.inventivity.com]
[www.andromeda.com]
[cns.nyu.edu]

Немного о переборе.
Есть случаи когда перебор неизбежен. Это особенно касается "хаотических" ситуаций, когда небольшое изменение условий влечет серьезные последствия, неприменимость шаблона тут связана с зависимостью от контекста.
Варианты: поиск в ширину и поиск с альфа-бета отсечением. С первым думаю, все понятно, второй отличается тем, что умеет обрезать ветви, руководствуясь двумя принципами:
"Этот вариант для меня явно плох. Дальше его можно не просчитывать."
"Этот вариант плох для моего оппонента. Он достаточно умен, чтобы не делать такого хода."
Второй вариант сложнее, поскольку требует делать статическую оценку на каждом шагу вычислений. Какова отдача? Пример - поиск в ширину не справится с "лестницей", шичо. Последняя может быть достаточно длинной, а у поиска в ширину глубина ограничена. Альфа-бета же, сможет просчитать шичо не отвлекаясь, поскольку вариации приводят к потерям.

Да, но в данном случае альфа-бета отсечение слишком долго по времени обсчитывается ln(a/2)*n^2.
Есть конечно оптимизированые в этом случает алгоритмы сокращается время расчета.
Можно поместить расчет алгоритма в поток на пять частей время уменьшиться до ln(a)/n.

Есть еще однай идейка.
применение фрактального алгоритма построения.
С обрезкой не состоявшихся ветвей комбинаций.
В этом варианте проще составляется алгоритм ,
ресурсы маленькие, на базы объема мало надо будет.

kit писал(а):

> Есть еще однай идейка.
> применение фрактального алгоритма построения.
> С обрезкой не состоявшихся ветвей комбинаций.
> В этом варианте проще составляется алгоритм ,
> ресурсы маленькие, на базы объема мало надо будет.
>
>

Можно поподробнее о фрактальном алг. построения,
я о таком не слышал