"Computer Go: An AI Oriented Survey"

Для тех. кому интересен вопрос "почему компьютеры умеют играть в шахматы, но не умеют играть в Го"
http://www.ai.univ-paris8.fr/~cazenave/CG-AISurvey.pdf

Спасибо, очень интересная статья!

А может просто занимались не те?

Вопрос упирается в теорему о существовании "тех"

Хочу играть в Го! Давно. Даже книжку купил. Но партия длится очень долго. А когда заниматься чем-то полезным для общества и самолюбия?

Вот некоторые простые оценки сложности Го:

There is no particular evidence that an increase in computing power is sufficient to make the current programs into world class champions, almost without regard to the computing power available. Given current program skill, the programs would need to look dozens of moves ahead (let's say 30) and try all potentially remotely reasonable moves (lets say 50 moves). Standard alpha-beta routines put that at 50 ^ 15 moves tried and carefully evaluated; that's about 10 ^ 25 or 2 ^ 84. Say a modern computer can evaluate 10 moves a second; further suppose that your future supercomputer is 100 billion times faster (10 ^ 11). This means you can generate a good move in only 10 ^ 13 seconds, or only 300,000 years! Now, relatively standard pruning algorithms for selective searching will significantly cut down the number of nodes tried; to get it down to 1 day per move would require a pruning factor of about 10 ^ 8, which is probably doable. So, if Moore's Law holds for the next 55 years (doubtful), then maybe the standard techniques would produce a professional grade player; I doubt even that would produce a world champion, though. In short, we need more intelligent programming; the go programs are getting better as a result of a lot more than just faster CPUs. A professional quality program within 50 years would not really surprise me; a world champion would.

http://senseis.xmp.net/?SomePhilosophicalQuestionsAboutComputersAndGo

1. учитывает. Я бы даже сказал, что 50 - это ОЧЕНЬ мягкая оценка СНИЗУ...
2. иногда используются
3. увы, не работают... то есть работают, но их эффективность для сколь-нибудь сильной игры недостаточна...

Это понятно, что надо. Вопрос только, как в том анекдоте: "But... how?"

В шахматах - в простейшем случае - взятия можно отсортировать по стоимости съеденных фигур, по прогнозируемому размену и т.д. В Го это невозможно. Если вы сыграли хотя бы десяток партий в своей жизни, вы понимаете причину. Без счёта разумная сортировка невозможна... Без сортировки невозможен эффективный счёт. Замкнутый круг.

Теперь насчёт коэффициента. В миттельшпиле в Го возможно сделать 200-300 ходов возможных ходов. Альфа-бета даёт корень из этого числа, он будет в районе 15-18. Вот такой степени ветвистости дерево предстоит усекать. Но! Учтите, что для альфа-беты порядок рассмотрения ходов - критическая величина. А как сортировать ходы - совершенно неясно...

Вот ещё одна интересная статья по теме:
http://www.smart-games.com/knowpap.txt - "Knowledge representation in Many Faces of Go"
Правда, тринадцатилетней давности. Но классику надо знать

Вот о чём я всё время не устаю повторять. Цитата:

An accurate evaluation of a Go position must do
life and death analysis and assign a value for relative thickness and territory. Just
Determining the location of secure territory is a difficult problem. A chess
evaluation is dominated by the values of the pieces remaining on the board,
which is easy to get right. If a go program misreads a life and death fight
there would be a large error in the evaluation score. This leads to an
evaluation function for a go program that is orders of magnitude slower than
the chess evaluation function. Where a PC chess program can examine 100,000
positions each move, Many Faces examines less than 100 positions before
deciding on a move.

А как применить в Го теорию графов?
Мне всегда казалось, что она больше заточена на задачи вроде поиска оптимального пути. Для Гекса вот как раз подходит. А что представлять графом в Го?

Да, а в Го?

Set-таблицы = piece-square values?

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

С нетерпением жду работающего прототипа