Абстрактный алгоритм Го

Есть много программ для Го, но ни одна пока не сыграла на 5 кю.

Рассчитать всё неквантовый компьютер не в сотоянии, да и не нужно - ведь мастер не считает

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

Разумеется, для того, чтобы потом можно было бы это реализовать. Вот я предлагаю пример:
АЛГОРИТМ УЗНАВАЕМЫХ ПУТЕЙ
Человек ищет такие ходы, которые ведут к позиции с узнаваемыми преимуществами Т.е. и компьютеру понятно, что больше территории - лучше. А вот в неопределённых позициях ход не даёт территории, к чему же стремится человек? Машина "занимает" полезные точки, но потом эти камни окружены.
А человек - он говорит себе: вот такая позиция похожа на позиции из кот. большинство было выиграно. Человек ориентируется на своеобразную базу данных в голове, что делает для него неопределённые позиции более определёнными

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

Замечу - "гоплюсплюс" лучше всего играет в начале, для которого у неё есть "база

вот другой пример
АЛГОРИТМ ...

подожду я с другим примером, может первый никому неинтересен

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

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

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



Отправка отредактированного (10/07/07 12:16)

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

Цитата:

Что касается алгоритма, то я его не увидел.

Сказано же, что алгоритм абстрактный, т.е. на самом деле он может состоять из одного правила выраженного в словесной форме
ПРАВИЛО искать знакомые элементы в возможных позициях и отбирать те, которые больше схожи с завдомо выигрышными

т.е. как раз именно обращение к базе данных

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

Цитата:

Го плохо алгоритмизируется. Для решения таких задач обычно создают экспертные системы на основе базы знаний.

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

Цитата:

К тому же объединить базу правил с нейронной сетью та ещё задача. На уровне объединения левого полушария мозга с правым

Не делает ли это столь же слабо и человек?

>Сказано же, что алгоритм абстрактный, т.е. на самом деле он может состоять из одного правила выраженного в словесной форме
Я тогда, пожалуй, предложу еще лучший "абстрактный алгоритм"
ПРАВИЛО: выбираем лучший ход.

Что касается нейронных сетей, то, как правильно заметил Antarex, если делать "влоб" - 361 вход, да пара полносвязных слоев (что, вполне возможно, окажется маловато) - это очень много. Плюс, такая сеть, скорее всего, сможет лишь нащупать "ключевые точки" - и перебор полностью исключить не оплучится.
Теперь обучение. Обучать на партиях профи - оно, конечно хорошо. Но. Для обучения нужны не только знание "хороших", но и "плохих" ходов. А их в партии профи нет. Вернее, мы не будем знать, какие из несделаных ходов чуть-чуть хуже, а какие - полностью неприемлемы.
Ведь уровень игры - это даже не уменее делать хорошие ходы - а уменее не делать плохих (на том уровне игры, к которому стремятся разработчики го-программ).



Отправка отредактированного (10/07/07 21:52)

chess-player, искать _похожие_ элементы - задача нетривиальная даже для человека. Особенно в Го, когда сдвиг одного камня на позицию может коренным образом изменить баланс сил. Принципиально неустойчивая задача. Так что база данных - тупиковый путь. Слишком много вариантов, слишком длинные последовательности ходов, неочевидных, приводящие тем не менее к результату. Рассчёт на силу противника и его возможные ошибки... как это формализовать?

Скорость работы экспертной системы зависит во многом от железа, во многом от алгоритма вывода и организации знаний. И с чего бы экспертной системе не быть игровой программой?..

Мастера, эксперты своего дела, никогда не пользуются алгоритмическим мышлением. Это одна из основных и давно известных проблем инженерии знаний. Извлечь знания из эксперта очень сложно. Чем выше уровень мастерства, тем туманнее объяснения. Либо, если начать копать, на любой случай будет столько вариантов, что описать их системой правил будет нереально.

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

в-общем, работа для НИИ или для гения :)

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

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

понятно?
Б - предполаагет неслабую эвристику

Назовём алгоритм из предыдущего сообщения
АЛГОРИТМ СВЕДЕНИЯ К УЗНАВАЕМЫМ ПУТЯМ
вместо
АЛГОРИТМА УЗНАВАЕМЫХ ПУТЕЙ

Господа-товарищи, а что Вы ЛЮДИ Разве не используете свою Накопленную базу знаний?
А относительности плохой алгоритмизации игры, чушь!
Внимательнее нужно быть, да ипросто смотреть варианты, и не стандартные, которые впихивают аж со школьной скамьи.
**** АЛГОРИТМА УЗНАВАЕМЫХ ПУТЕЙ ****
Так это почти Бинарное Дерево с равновесными путями.

Да-да, именно потому что го хорошо алгоритмизуются, программы играют так сильно.

По-моему, начинать лучше с постановки задачи несколько более математической и формальной, чем "найти лучший ход".

А что такое "лучший ход"?

Re: Абстрактный алгоритм Го новое
Пользователь: Antarex
Дата: 09, November, 2007 13:54

А что такое "лучший ход"?

Это же " Элементарно, Ватсон!"
"Лучший ход" - ход ведущий к победе, в локальной ситуации или же во всей игре.

По-моему, начинать лучше с постановки задачи несколько более математической и формальной, чем "найти лучший ход".

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

kit144, что же делать, когда лучшего хода нет? И что важнее, лучший ход в локальной ситуации, или во всей игре? И если в локальной, то в какой именно из множества имеющихся?

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

Может быть, это как-то поможет?

Относительно лучшего хода - Он всегда есть!
только мы не всегда его можем увидеть или правильно распознать.
С Мишей согласен. Достаточно часто встречается в партиях - локальные позиции очень сильные а в целом на поле проигрышь.

Для программирования игры лучше всего использовать функциональные языки программирования общего назначение такие как :
HASKEL 98 и его улучшенная реализация curry 99
или же FSharp.
В этих языках достаточно хорошо можно описать нужные дейтвия не заморачивая себе голову умудренными мат. функциями.

пример на языке Fsharp - игра "Китайские шахматы" вместе с исходниками.
архив.
[strangelights.com]

[qoute]
"Лучший ход" - ход ведущий к победе, в локальной ситуации или же во всей игре.
[/quote]
[quote]
Относительно лучшего хода - Он всегда есть!
[/quote]
Одно из вышеперечисленных утверждений - ложно (в смысле математической логики). Провести пример или не нужно?

[qoute]
Для программирования игры лучше всего использовать функциональные языки программирования общего назначение такие как :
HASKEL 98 и его улучшенная реализация curry 99
или же FSharp.
[/quote]

Как человек, профессионально занимающийся программирование на ФП языках (Haskell, Erlang), скажу, что если не можешь написать алгоритм на бумажке в понятных человеку словах (вплоть до деталей), то и на любом языке программирования сформулировать программу не сможешь.
В какую силу играет прогрмма в "Китайские шахматы"?

kit144 Написал:
-------------------------------------------------------

> А что такое "лучший ход"?
> Это же " Элементарно, Ватсон!" "Лучший ход" - ход ведущий к победе,
> в локальной ситуации или же во всей игре.

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

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

звучит красиво, и хоть какой-то пример определения такого коэффициента?