компьютеры и го

[avva]

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

Новая программа Zen19 играет на уровне 5-го любительского дана; статья объясняет, что это примерно 100-е место среди всех игроков в Америке. И это во много раз лучше того, как программы играли еще лет 5 назад.

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

Было бы намного интереснее, если бы компьютеры учились лучше играть в Го путем "понимания" хотя бы в некотором смысле, путем, похожим на человеческое мышление об этой игре. К сожалению, не похоже, чтобы нынешний чемпион Zen19 включал в себя "глубокие" знания об игре (его исходники недоступны, так что в точности неизвестно). Более того, подход Монте-Карло очень удобно разбивать на параллельные потоки. Это значит, что с ростом вычислительной мощности сила Zen19 скорее всего будет еще расти и расти. И возможно, именно такой подход в итоге победит всех игроков-людей, как это уже произошло в шахматах.

Comments

[oulenspiegel.livejournal.com]

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


Это всё заблуждения :) Скажу, как ведущий российский шахматный программист :)

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

1 20
2 400
3 8902
4 197281
5 4865609
6 119060324
7 3195901860
8 84998978956
9 2439530234167
10 69352859712417
11 2097651003696806

Современная типовая персоналка в состоянии просматривать примерно 1
миллион позиций в секунду. Значит, для перебора на 11 полуходов из
стартовой позиции потребуется 2097651004 секунды. То есть почти 67
лет. И это стартовая позиция, в которой ветвление сравнительно
небольшое.
Программа, думающая над ходом по 2 минуты, сможет в практической игре
просматривать варианты всего на 5—6 полуходов. Много это или мало? Это
значит, что такая программа сможет решить не любую задачку-трёходовку,
что под силу почти любому рядовому шахматисту. Гроссмейстер же в
практической игре просматривает некоторые варианты на 12—16 полуходов,
что абсолютно недостижимо путём перебора «в лоб».
По этой же причине, увеличение скорости компьютеров не приводит к
существенному выигрышу. Задача полного перебора на 16 полуходов как
была возможной 20 лет назад, так и останется ей очень и очень надолго,
если не навсегда.
Поэтому точка зрения, что компьютер обыгрывает человека за счёт того,
что может быстро перебрать все варианты — ошибочная.
Скажем так, если программу чемпиона мира 15-летней давности запустить
на современном «железе», то её рейтинг вряд ли превысит 2400 пунктов.
То есть прогресс в почти 1000 пунктов произошёл отнюдь не за счёт
ускорения железа, но за счёт совершенствования алгоритмов.

В типичной современной шахматной программе есть:
1. Переборный механизм — но это не тупой перебор в лоб, а довольно
сложная процедура, варьирующая глубину просмотра разных вариантов в
зависимости от самых различных факторов. Скажем, моя программа в
типичном миттельшпиле просматривает варианты на глубину от 5—6 до 50
полуходов. То есть есть варианты, которые будут брошены за
бесперспективностью очень рано, а есть варианты — которые будут
просчитаны чуть ли не до конца игры.
2. Оценочная функция — тоже очень сложный механизм, построенный на
основе статистического анализа. Это функция, которая позволяет оценить
позицию без просмотра вариантов, на основе различных компонентов
позиции и их сочетания. Такая функция учитывает огромное количество
самых разных вещей — соотношение материала, пешечную структуру,
мобильность фигур, атаку на короля и т.д. и т.п. Причём отдельные
позиционные компоненты могут легко перевешивать соотношение материала.

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

[bvlb.livejournal.com]

О, давно хотел спросить. Вот эти оценочные функции - это аналитические функции, в которых руками подкручены параметры, или это таки классификаторы, которые вы классически тренируете? Или - ни то, ни другое?

[oulenspiegel.livejournal.com]

До середины 2000-х подавляющее большинство программ использовало по большей мере компоненты оценки выставленные «на глазок». Хотя работы по автоматической подстройке параметров велись. В первую очередь, велись работы по построению статистически обоснованной модели оценки сочетания материала на доске, а также подстройки т.н. piece-square tables и оценок проходных пешек.
Проблема в том, что современные оценочные функции шахматных программ содержат очень много параметров, что затрудняет эффективную подстройку — у функции очень много локальных максимумов, а такой критерий как % выигранных партий против какого-то набора оппонентов (пусть даже в «молниеносные» шахматы) имеет очень и очень плохую сходимость. То есть подстроить параметры «грубо» таким образом можно, но такие оценки оказываются не особо лучше выставленных экспертом.
Тем не менее со второй половины 2000-х наметились явные успехи в этом направлении, связанные с применением генетических алгоритмов (подборка публикаций: http://chessprogramming.wikispaces.com/Automated+Tuning). Большим прорывом стало параллельное создание несколькими разработчиками статистически обоснованных моделей дисбаланса материала на доске (прежде всего, речь идет о программе Rybka Васика Райлиха).

[oulenspiegel.livejournal.com]

Вот, кстати, последняя «бомба» :)
http://remi.coulom.free.fr/CLOP/

И моя косноязычная болтовня на тему: http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=431783&t=40964

[oulenspiegel.livejournal.com]

А, да, забыл про общую структуру оценочной функции.
Так уж повелось, что оценку позиции дают в 1/100 долях условной пешки. Через логистическую функцию эта величина связана с вероятностью победы.
Оценочная функция по своей структуре представляет собой полином, грубо говоря. Только если в первых шахматных программах это была просто сумма независимых факторов, то в современной программе учитывается множество взаимных зависимостей параметров.
Ну, скажем, факт наличия проходная белой пешки на e7 в начале игры стоит 0.9 пешки, а в глубоком эндшпиле, ну, скажем, 2.7 пешки. Есть оценка «стадии» игры (от 0 — начало игры до 256 — конец игры).

eval += ((passed_pawn_value_endgame[square] * stage) + (passed_pawn_value_opening[square] * (255 - stage))) / 256;

И т.п.

[bvlb.livejournal.com]

а предыдущий комент Ваш про историю развитися оценочной функции пропал куда-то

[oulenspiegel.livejournal.com]

Он заскринен, видимо, т.к. содержит ссылки.
Подождём автора журнала.

[winpooh.livejournal.com]

Как там проект SmarThink поживает, будут ли новые версии?

[oulenspiegel.livejournal.com]

У меня есть версия, которая играет заметно сильнее прошлой, но, к сожалению, никак не доделаю многопроцессорный вариант, а пока не доделаю — выпускать не хочу.
Зато скоро выйдет версия под Windows Phone :)

[nikolenko.livejournal.com]

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

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

[oulenspiegel.livejournal.com]

В шахматах ProbCut плохо работает из-за тактики.

[winpooh.livejournal.com]

Ну для чистой альфа-беты (без эвристик) из второго столбика стоит все-таки извлечь корень квадратный :)

[oulenspiegel.livejournal.com]

Корень квадратный, это, если я не туплю поутру, теоретический предел альфа-беты при идеальном упорядочивании ходов в узле, то есть всё-таки не без эвристик. То есть в узлах fail high мы просмотрим 1 ход, а в fail low всё равно все. При отсутствии упорядочивания мы будем просматривать в fail high половину ходов в среднем, поэтому всё-таки не квадратный корень.
Что интересно, если P != NP, идеальный упорядочиватель для альфа-беты, работающий за полиномиальное время, невозможен :)

[gaz-v-pol.livejournal.com]

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

[oulenspiegel.livejournal.com]

В шахматах сейчас посчитаны все семифигурные окончания. Соответственно для позиции, в которой у дерева перебора все его терминальные узлы будут иметь однозначно определённую оценку (т.е. либо мат, либо пат, либо 7 фигур на доске, либо повторение позиции, либо ничья по правилу 50 ходов) можно получить точную оценку. В принципе, именно так Шеффер и его команда решили шашки.

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

С многопешечными окончаниями проблема такая, что действительно, есть позиции, где любое взятие или движение пешки приводит к позициям с весьма определённой оценкой, но основные линии перебора достаточно длинные и включают в себя длительное маневрирование королями. В современных программах нет специальных алгоритмов для таких ситуаций (хотя я какое-то время довольно много экспериментировал с пешечными эндшпилями и до сих пор в SmarThink очень много оригинальных эвристик для пешечных окончаний и ладейников), т.к. во многом спасает хэш-таблица (transposition/refutation table), в которой хранятся результаты перебора для просмотренных ранее позиций. В эндшпилях одни и те же позиции чаще возникают в результате перестановок ходов, поэтому хэш-таблица в определённой мере эмулирует поведение ретроаналитических алгоритмов.

[gaz-v-pol.livejournal.com]

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

Мы когда-то полностью просчитали 4-фигурные окончания в русских шашках и поддавках, и это казалось невероятно крутым. А теперь вот до чего наука дошла.

Про Шеффера я слышал, но там история такая, что полностью просчитаны не шашки, а draughts (слово ошибочно переводимое в словарях как "шашки"). Фишки те же, доска та же, правила ходов другие.

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

[oulenspiegel.livejournal.com]

> О как, все семифигурные шахматные окончания
> просчитаны, надо же! А как это устроено -- есть
> какая-то программа, которой можно задать позицию
> и она показывает кто выигрывает и во сколько ходов?

Семифигурных нет в онлайне, есть несколько интерфейсов для шестифигурных. Например: http://www.shredderchess.com/online-chess/online-databases/endgame-database.html (вот тут больше ссылок про эндшпильные ретроаналитические таблицы: http://kirill-kryukov.com/chess/tablebases-online/)

> Про Шеффера я слышал, но там история такая,
> что полностью просчитаны не шашки, а draughts
> (слово ошибочно переводимое в словарях как
> "шашки"). Фишки те же, доска та же, правила
> ходов другие.

Не совсем так. Шеффер решил как раз Checkers (English draughts), которые распространены во всем мире.
В России же обычно играют в русские шашки, которые Шеффер не решал, ясное дело :) С точки зрения комбинаторной сложности они не отличаются. В русских шашках дамки ходят на любое число полей + обычным шашкам можно бить назад.

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

Вот именно поэтому и нельзя. Когда пару пешек превратятся в ферзей вы получите окончание, которое не считается.
А вам для ретроанализа надо, чтобы все терминальные позиции были посчитаны.