Оценочная функция

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

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

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



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

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

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

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



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

Наверное , все таки нужно определить некторые вещи:

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

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

4)Далее использовать метод предельного упрощения ( см. ссылку [lii.newmail.ru])

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

vможет быть будет интересна и эта статья
[lii.newmail.ru]

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

--- Могу привести, если интересно, конкретный пример, когда розыгрыш двух стандартных джосеки приводит к мнговенному поражению одного из партнеров. Могу привести другой пример. Позицию, в которой отклонение от джосеки, вообще не рассматривоемое в справочниках, сразу приводит к победе.---

Согласен. Но до этого пока еще рановато идти. А метод глубокого перебора все таки нужен, хотя бы для расчета позиции на " жизнь и смерть" .
А если рассматривать метод весовых коэффициентов для выбора того или иного хода, то ведь он то же будет зависить от человека (программиста) и не всегда этот выбор будет правильным. даже в реальных партиях этот выбор не всегда верен бывает и среди профессионалов.

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

Сергей Межов писал(а):

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

Сергей! Приведите, плз, если не сложно!
Только мб не этом форуме, а в том :)

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

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

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

Или джосэки - это "равный розыгрыш" в каком-то более сильном смысле ?



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

Илья, ты правильно понимаешь. А расстояние, если по диагонале, может быть и противоположный угол.

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

Хотел бы заметить что использование процедуры альфа-бета отсечения для Го имхо практически невозможно, б.м. только на 2-3 хода
Делаем простой расчет. Пусть в среднем в конкретной позиции доступно 150 различных ходов. Для расчета на 2 хода вперед получаем 22500 различных позиций. Причем эти позиции еще нужно оценить. Если вспомнить сколько времени обсчитывает одну позицию скажем GnuGo то становится очевидно что в такой грубой реализации метод абсолютно неприменим. соответсвенно нужно отобрать 15-20 ходов, для которых уже нужно применять процедуру. Не знаю как в других программах, но в том же gnuGo афэйк для этой цели используется библиотека паттернов, а применение процедуры альфа-бета отсечения стоит одной из целей в To Do листе (функции которые неплохо бы реализовать).

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

Цитата:
====================================================
Определить, как рассчитывать позиции на доске - т.е. разбить доску на несколько частей, скажем по квадратам 6х6, и рассчитывать позиции для этих квадратов, в дальнейшем объединяя рассчитаные позиции в группы ( два квадрата объенияться с третьим и получается один квадрат, или другими словами подгруппа, и т.д. - Метод группового учета аргументов ).
====================================================

Делая такое разбиение мы уклоняемся от исходных данных и вводим новые синтетические переменные (зато конечно здорово сокащаем количество переменных с 361 до 9). При этом далеко не факт что эти переменные будут нормально отражать ситуацию на всей доске. Первое что приходит в голову - оценка позиции на симметричных и повернутых под разными углами участках доски будет одинаковой. А теперь возьмем готовую партию разрежем доску на 9 кусков и каждый из кусков повернем на произвольный угол. Сомневаюсь что то что получим результат как на исходной доске :). Т.е. даже в таком случае оценка на каждом фрагменте должна зафисеть от ситуации на других фрагментах, а один из принципов МГУА - использование как можно менее зависимых переменных...

Кроме того для применения МГУА как и большинства других методов РО требуется длительная процедура обучения на большой обучающей выборке

------ Делая такое разбиение мы уклоняемся от исходных данных и вводим новые синтетические переменные (зато конечно здорово сокащаем количество переменных с 361 до 9). При этом далеко не факт что эти переменные будут нормально отражать ситуацию на всей доске. Первое что приходит в голову - оценка позиции на симметричных и повернутых под разными углами участках доски будет одинаковой. А теперь возьмем готовую партию разрежем доску на 9 кусков и каждый из кусков повернем на произвольный угол. Сомневаюсь что то что получим результат как на исходной доске :). Т.е. даже в таком случае оценка на каждом фрагменте должна зафисеть от ситуации на других фрагментах, а один из принципов МГУА - использование как можно менее зависимых переменных...
-----

Вполне резонное замечание.........

Можно попыпаться применить функцию построения квадрата, тригонометрическу, {cos(x) + sin(y)}.
отсчет применять от центра доски.
Тогда можно получить график расположения камней на доске.
правда нужно более детально и глубже исследовать применение этой функции для двух разных систем ( белых и черных камней).
А рассчитать коэффициенты для точек пересечения для всей доски не сложно. И в полне возможно, что можно будет использовать данные коэффициенты для анализа ситуации.
Хотя , еще раз повторяю, это надо проработать и проверить, пока что на бумаге........

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

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

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



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

>>Объекты в Го - топологические , геометрическое расстояние и разбиение доски имеет смысл лишь если доска почти пуста , и только для удобства человеческого восприятия позиции .

Если я все правильно понимаю, на гобане есть некий аналог скорости света. То есть, на камень в точке (х,у) наличие камня в точке (х+а, у+б) непосредственно отразится лишь через а+б ходов.
Это утверждение следует понимать так, что для того, чтобы определить наличие шанса на выживание камня в течении С ходов, мне достаточно осмотреть ромб с центром в данном камне, и радиусом С.
Ограничение - если нет цепей, которые "съедят" расстояние.
Зато, если стянуть в точку цепи с помощью описанной мною ранее процедуры, и рассматривать топологическое расстояние, ограничение снимается.

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

> Ограничение - если нет цепей, которые "съедят" расстояние.

О том и речь

> Зато, если стянуть в точку цепи с помощью описанной мною ранее процедуры, и рассматривать топологическое расстояние, ограничение снимается.

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



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

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

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

А что.... мысль хорошая!!!

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

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