Продолжаем попытку обсуждения формализации алгоритма игры...

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

Формализация:
1. Определить лучшую комбинацию начала игры в углу размером 4х4, для выживания группы и захвата наибольшей территории угла.

Дальше Ваши предложения.

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

Что такое ход? Территория? Лучший ход? начало партии? Середина? Конец?
Что такое очки? Влияние?
Что такое дистанция? Количество шагов связей? Выживание? Разрозненные камни? Живущая группа?

Без ответа на эти вопросы не может быть ответов и на вопросы, поставленые Вами.

>За эти, почти четыре года, так никто и не вывел формальную постановку задачи.
Тут просто. Максимизировать F(A(X,Y),B(X,Y)) где F - цена игры т.е очки. A,B - два игрока. X,Y множество ходов.

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

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

Вопервых задания не коректные.

1. Ход 3-3 не является самым лучшим. Самым лучшим является критический ход который мы пока еще не вывели.
Насчет хода 3-3 его ценность меняется с течением игры. Если первый ход еще возможен, то в последствии это может оказаться не лучшим ходом. Возможно что если туда походить в середине или конце игры, то камень и не выжевет. Так же этот ход может оказаться хорошим для ёссе.

2. Еще раз. Еще не доказанно что это лучший ход.

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

>Формализация:
>1. Определить лучшую комбинацию начала игры в углу размером 4х4, для выживания группы и захвата наибольшей территории угла.
Группа живет в любом случии, та как камни могут убежать, доска ведь пуста.
Я бы не стал обощать. Ход в углу может приносить очки как в углу так и на стороне так и в центре.

Теперь об оценки. Сколько очков приносит камен. В начале выставим 1 очко. Практика показывает что выши 3 линии подниматься опасно. 3*3=9 А также то что джосека делит угол пополам поэтому получаем что угол дает 5 (3х3)очков. Можно даьше продолжать думать. Но это скучно. Дальше надо просто составить алгоритм который будет делать ходы влотную.И посмотреть все возможные варианты с оценкой теретории на данной момент. Так можно оценить тереторию. И узнать лучший ход. Вопрос в том что при таком раскладе мы не учитываем сколько принесет данный ход в будущем. Вопрос в том как его можно будет потом развивать. Для этого надо учесть разброс камней можно перебирать или несколько случайных комбинаций разброса. И сделать оценочную функцию возможной теретории.
То что у тебя это задача. А теперь формулизация. Max=T(x,y)+T'(x,y)
T - теретория
T' - то что может стать тереторией.

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

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

Интересные мысли. Спасибо, Pavia.

Есть такая версия, что лучшей постановки нет. "В Го каждая постановка - это ошибка". Не знаю, насколько эта версия близка или далека от истины. Я о ней только слышал.

Писал в прошлой теме, повторюсь тут... Го - принципиально неустойчивая система. Единственный ход может кардинально изменить баланс сил. Принципиально Лучший ход во многих позициях просто отсутствует. Так что только ИскИн, умеющий пользоваться и пополнять экспертную систему по Го, работающий на эвристиках в общем, и считающий варианты локально, использующий базы данных по играм. К тому же он должен адекватно реагировать на нестандартные ситуации... И обучаться игре у Мастера.

>Тут просто. Максимизировать F(A(X,Y),B(X,Y)) где F - цена игры т.е очки. A,B - два игрока. X,Y множество ходов.

Определите (дайте определение) F. Определите X и Y. A и B.

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

Определите ход. Прибыль хода. "Наилучший".

>3. Ответ очень прост такой дистанции нет. Если дистанция ноль то камни сойденены. Если дистанция одна пусая ячейка. То камни можно разрезать так же и сойденить. При большей растоянии тоже самое. На самом деле все зависит от обстановки. Еще надо отметить нужно ли сойденять камни сейчас или нет.

Что такое дистанция?

**Ну вы-то в первую очередь и не хотите делиться результатами.**
Конечно. Пока не буду уверен в них окончательно, мне о них говорить рано. Это как в науке - не уверен не публикуй...)))

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

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

Для начала - выбор оптимального пути для соединения своих "разрозненых" камней. Так как фигура, которую образуют два разрозненых камня, является прямоугольник. То задача сводится к поиску множества путей, которыми можно соединить два камня. (группу камней можно считать также как один камень). Далее выбирается самый оптимальный путь. Коэффициент высчитывается так:
Отрезок между двумя соседними точками равен 1(единице).
Если соединение происходит не по прямой линии, а по треугольнику, она же"диагональ", ( типа косуми), то производиться следующий расчет по правилу треугольника -
SQR(A^2+B^2)=C ==> C=SQR(2). Далее, если идет по прямой, то просто складывается.

ПРИМЕР:

A B C D E F
1 | - - - -
2 x - - - -
3 | - - - -
4 | - - - -
5 | - - x -
6 | - - - -

В2 соединяем с Е5 , количество путей соединения >11
считаем В2+С2+D2=3, E3+E4+E5=3, SQR((D2)^2+(E2)^2)=SQR(2)
итого 3+3+SQR(2)~=7,41 с таким коэффициентом два пути.
У остальныйх путей коэффициенты будут больше. Поэтому путь с наименьшим коэффициентом будет самым оптимальным.

Далее продолжаю...)
для тех кто хочет всё таки создатьигру, предлагаю изучить язык программирования HASKEL98. Он отвечает всем, на сегодняшний день, характеристикам языков программирования как ИИ так и формального, процедурного и логического. Для тех, кто хочет объединится в команду программеров - прошу писать на мыло kit144@rbcmail.ru

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

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

Вот какая статья - "Машинный разум нанёс человеку удар в го". Далее позволю себе процитировать некоторые детали:

В феврале на престижном турнире по го Taiwan Open 2009 компьютерная программа MoGo (смотрите также эту страницу) обыграла двух профессионалов в битве на гобане 19 х 19. С гандикапом в 7 камней она победила игрока девятого дана Дзюньсюнь Чжоу (Jun-Xun Zhou), а с форой в 6 камней сломила сопротивление игрока первого дана Личэнь Чиэня (Li-Chen Chien).

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

"Удивлением, загадкой для меня является то, что эти алгоритмы работают", — говорит Хирн, комментируя новые достижения MoGo и Many Faces. Поясним: даже сами авторы этих программ прекрасно знают – как они работают, но при этом не знают – почему это срабатывает.

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

....
Атертон всё это обобщил так: "Игроки в го упрощают дерево поиска решений до эстетического чувства. У них есть чувство игры".

-------------
Целая статья можете прочитать здесь:
[www.membrana.ru]

Ну а на равных первый дан программой обыгран?

Забыл вставить ссылку:

[www.membrana.ru]

И еще один цитат в ответ на Alone: :)

Роберт Хирн (Robert Hearn), математик и компьютерщик из Дартмутского колледжа, а также – сильный игрок в го [почему же пишут "го", а не "Го"? - замечание мое], прогнозирует, что пройдёт менее 30 лет, и программы (главным образом за счёт роста мощности суперкомпьютеров) начнут обыгрывать в го лучших профи даже без гандикапа. Арпад Риммель (Arpad Rimmel), один из авторов MoGo, оценивает этот срок и вовсе в 10 лет.

Но это не приблизит нас к разгадке того, как мыслит человек, играющий в го. Он-то не перебирает миллионы ходов.

----------

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

Интересный заход

Если рассмотреть Го как способ общения на высоком абстрактом уровне, то что же нас ожидает в будущем? :)
Общение с компьютером и искусственный интеллект? Или борьба с "электро-дауном", который умеет очень быстро делать сложение, вычитание и сравнение в определенной последовательности?

Лично мне второе не интересно...

Если даже соревновательное Го умрет под пятой электродауна, то Го. как общение и практика - останется :)

- - - - - - - - - - - - - - - - - - - - - - - - -
- Не обижайся: способность понять зависит от личного опыта, а не от умственных усилий… (Сэр Джуффин Халли)
Гостинная Шк. "Стожар": [100jar.blogspot.com]
Библиотека Шк. "Стожар": [librarystozhar.blogspot.com]

Компьютеры и сейчас выигрывают у людей и многие в сети уже пользуются их помощью.
Уже сейчас только очень сильные игроки могут выиграть у компьютера.
Я видел игрока-робота на kgs и нужно приложить всё внимание и умение, чтобы его обыграть.
Я играл с ним много раз на доске 9х9 и ни разу не выиграл!

Правильнее следовать настоящей, а не воображаемой правде вещей... (с)

shadowjack Написал:
-------------------------------------------------------
> Ну вы-то в первую очередь и не хотите делиться
> результатами. У остальных их вообще нет.
> Сначала нужно понять, что есть го как игра, а
> потом уже пытаться что-то сформулировать.
>
> Что такое ход? Территория? Лучший ход? начало
> партии? Середина? Конец?
> Что такое очки? Влияние?
> Что такое дистанция? Количество шагов связей?
> Выживание? Разрозненные камни? Живущая группа?
>
> Без ответа на эти вопросы не может быть ответов и
> на вопросы, поставленые Вами.


Удовольствие в поиске решения - вполне себе в духе Го принцип.
Иначе в Го бы играли целыми командами