Валерий Дмитриевич , боюсь , что речь в ДАННОМ проекте идет не об оценке позиции , а о послеигровом подсчете результата , возможно даже полуавтоматическом .



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

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

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

Пора ветвить тему...



Отправка отредактированного (17/11/03 08:07)

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

Очень удачно я попал на этот форум. Объясняю почему.
Несколько дней назад я решил переписать заново свою гошную программу.
Она конечно не играет в го, эту программу можно назвать «играющей доской», т.е. можно играть вдвоем на компьютере. На данный момент переписано пока очень мало: класс рисующий доску и проставляющий на ней камни.
Если кому либо это интересно могу скинуть исходники по мылу. Пишу на Visual C++ 6.0 с использование MFC

Буду благодарен за исходник: Sibgo[sobaka]narod.ru



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

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

Михаил , пришлите и мне пожалуйста .

ylja [gavkalka] mail.ru



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

Немного причешу и скину 17 или 18 числа вечером (по Москве)

Немного причешу и скину 17 или 18 числа вечером (по Москве)

Уважаемый Илья Ветров!
Вы писали: "Валерий Дмитриевич , боюсь , что речь в ДАННОМ проекте идет не об оценке позиции , а о послеигровом подсчете результата , возможно даже полуавтоматическом ".
В этом случае надо выражаться г-ну PuzzleMan(у) по-точнее. Задача "анализ позиции" конечно очень сложная. Сложность заключается в том, что задача очень динамична (быстро меняется огромное число параметров оценки). Оценочная матрица (граф) будет велика, а найти оптимизирующую функцию (потенциал) будет не легко (если не сказать невозможно).
Другое дело - подсчет результата партии (или баланса позиции). Задача - статическая. Все налицо. Подсчитать не трудно. Однако лучше не тратить время и взять (если возможно) готовый программый продукт (благо существует много гошных программ).
Мне кажется, что эта задача хорошо форматизируется и легко программируется.
С уважением

Валерий Дмитриевич , может быть я ошибся .

PuzzleMan :

> Сразу оговорюсь, что это не играющая программа (я вообще не совсем уверен, что такую программу надо писать)

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

То есть играть не играть , а позицию оценивать надо , как например делает сервер Кисейдо ... Сам же инициатор втихаря готовит свое ТЗ и не опровергает ни мое , ни Ваше мнение .

Дима , даешь ТЗ !!! Народ хочет обрести цели и горизонты !

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



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

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

Илья,

> То есть играть не играть , а позицию оценивать надо , как
> например делает сервер Кисейдо ...

Да, именно так и планируется...

> Сам же инициатор втихаря
> готовит свое ТЗ и не опровергает ни мое , ни Ваше мнение .

Так, может какие интересные мысли еще почерпну =)

> Дима , даешь ТЗ !!! Народ хочет обрести цели и горизонты !

Пишу... На этой неделе закончу. Только это будет еще не окончательно тз разработчикам, а скорее предварительное, которое будет описывать в основном внешнюю сторону.

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

А вот тут я не совсем уверен... Внктри моей живой группы находится мертвая группа противника, причм у нее 35 фальшивых глаз и один настоящий. Справится заливка с этим делом?

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

Секи...

Отдельная песня - симоку-магари.

(Я говорю про японские правила. В данном случае их совершенство/несовершенство в рассчет не берется)

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



С уважением,
Дмитрий Петраков aka PuzzleMan
Elite Japan Crossword

>> Эта заливка проверена и оптимизирована вусмерть .

> А вот тут я не совсем уверен... Внктри моей живой группы находится мертвая группа противника, причм у нее 35 фальшивых глаз и один настоящий. Справится заливка с этим делом?

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

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

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

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

Этого я не понял . Как у живой собаки может быть мертвый хвост ?

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

> Секи...
> Отдельная песня - симоку-магари.
> (Я говорю про японские правила. В данном случае их совершенство/несовершенство в рассчет не берется)

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

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



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

Илья,

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

Это безусловно, но хочется максимально близко к реальности.

> > Или хвост моей группы (живой) соединен с ней посредством
> бамбука... Насколько я понимаю, по японским правилам совершенно
> не обязательно тратить ход на соединение.
>
> Этого я не понял . Как у живой собаки может быть мертвый хвост
> ?

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


&nbsp________
|O&nbspOOOOOO|
|OOOOOOOO|
|XXX&nbsp&nbspXXX|
|&nbspXOOOOX&nbsp|
|XXOOOOXX|
|&nbspXOOOOX&nbsp|
|XXOO&nbspOXX|
&nbsp--------

> В любом случае полуавтоматичность и
> возможность доиграть решает все проблемы .

Безусловно, полуавтоматический режим нужен... но основная цель проекта зделать подукт максимально удобный и легкий в обращении. Когда я прошу рассчитать партию, то хочу увидеть сразу результат, а не тратить кучу телодвижений для этого. Предположим, я рассматриваю несколько вариантов последних 10 ходов йосе. Ищу способ где бы отобать нехватающие 0.5 очков для победы (естественно это во время послеигрового анализа). И для того, чтобы посмотреть, отыграл ли я эти 0.5 очков мне придется пометить 15 мертвых групп и 10 нейтралок. Грустно =( Скорее всего, игрокам начиная с ???д это и не надо, а мне бы очень пригодилось...

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

А вот и не приму! =) Какие там проблемы в рассчете результата?

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

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

> Кстати , ко тоже трактуешь по-японски ? В реализации это
> конечно попроще.

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

>Только учти , что при желании участников игра
> может зациклиться.

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

>По крайней мере отслеживай границы массива
> ходов - так делает IGS .

Программа будет не играющая... пока по крайней мере. Зачем запрещать человеку вводить бесконечную партию? Раз флажек не упадет, то память кончится или место на диске =)



С уважением,
Дмитрий Петраков aka PuzzleMan
Elite Japan Crossword

> А вот и не приму! =) Какие там проблемы в рассчете результата?

Японские правила создали себе массу проблем , в том числе при подсчете результата , кое-что даже здесь на форуме (-мах) обсуждалось .

Бывает статус групп более сложный , чем магари шимоку , из-за вечных генераторов ко-угроз .

Далеко не тривиальна формулировка "только та группа владеет территорией , которая в состоянии построить 2 глаза" . Что если может , но от этого хуже будет ? Или может при условии съедения мешающей группы , статус которой ... и т.д. см. выше .

Могу утешить только одним : в реальных партиях даже вопрос о территории в сэки на моих глазах ни разу не возникал , а бОльшие тонкости вообще можно считать теоретической экзотикой . Просто пиши в рекламе слабую отмазку - мол , результат ПРАКТИЧЕСКИ всегда вычисляется автоматически в полном соответствии с японскими правилами . И обойдись без полуавтоматики , ведь отсутствие споров (о статусе групп) важнее , чем феноменально редкие ошибки .

> память кончится или место на диске

Главное - границы массива соблюсти . Но извини за банальное напоминание - ты небось и сам не позабыл бы ...



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

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

Что буду делать я в ближайшее время? Доводить до ума SGFView. Когда оно даст мне немного свободы, сделаю версию, способную предоставлять "необычную" доску. Такая вещь, имхо, есть хороший мост между мирами Го и головоломок.

Еще у меня есть идея разработки проекта внедрения Го в ММОРПГ. Причем не просто как мини-игру, а как своего рода магию... Ну, например, чтобы открыть запертую дверь, надо решить го-проблему. Не говоря о драках с монстрами-ботами или player vs player.

Ну, я думаю вы давно поняли, что фаназии мне не занимать. :D

Насчет магии - интересно . Если тщательно подобрать и расставить задачи и разумно ограничить число попыток решения - будет хороший стимул и учебник Го . Под чужими камнями могут быть спрятаны ценности или секреты ...



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

Идея этого проекта умерла или как? А то тишина какая-то...
Может где отдельный (под)форум был создан?

Копался в поиске и "откопал". Неужели умерли все идеи создать проект с подпроектами? Хотя бы кто за жеребьвки наконец-то взялся.

Да, проясните историю проекта. А то как Роман без конца....

Здравствуй Дмитрий !

Хотелось бы откликнуться по части генерации концептуальных идей,или пользуясь твоими словами,откликнуться на следствие 3 пункта.К сожалению не владею программированием.Хотелось бы знать - всё таки это будет традиционная игра на традиционных досках?
Известный тебе по "Стратегии по правилам ГО" Олег Горчаков.Кстати
идею свою я развиваю.Сейчас занимаюсь будущим интерфейсом - а именно приспосабливаю реальные географические карты к игре ГО.Игра будет проще чем я предполагал.