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

[avva]

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

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

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

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

Comments

[gaz-v-pol.livejournal.com]

Остался последний бастион, шведские шахматы (bughouse). В них компьютер ещё не скоро (никогда?) не научится играть лучше человека.

Я когда-то пробовал писать программу, которая бы в шашки "думала". Рассуждал так: сильный шашист смотрит на позицию и подсознательно вспоминает множество аналогичных. И понимает: в таких позициях принято играть так-то. Можно попробовать оценить схожесть позиций. Я брал множество бессмысленных параметров вроде суммы расстояний от шашек до разных прямых с разными весами. И надеялся, что можно как-то выделить множество позиций, где надо играть одним образом, от множества позиций, где надо играть другим образом. Ничего не вышло. Но при каком-то уровне развития вычислительной мощности уже может быть и выйдет.

[osherovmikhail.livejournal.com]

Шашечные программы уже существуют.

[mm-aa.livejournal.com]

Судя по всему последний бастион пока - бридж.

[dmitriy mandel (from livejournal.com)]

Я правильно понял, что вы построили что-то типа k-nearest neighbor algorithm на некоем многомерном пространстве? Вы тренировали программу на какой-то базе данных реальных шашечных партий или просто пытались определить сходства между позициями из теоретических соображений?

Мой опыт с подобными knn-алгоритмами подсказывает, что бывает трудно найти "правильные" метрики. Ещё труднее при ограниченных вычислительных ресурсах оптимизировать веса. А если набрать наугад слишком много метрик/измерений, то начинается curse of dimensionality. В общем, там много подводных камней.

[michk.livejournal.com]

Почему это в шведские шахматы не научится? Что в них такого? Я не вижу принципиальной разницы.

[oulenspiegel.livejournal.com]

Есть ещё и shogi, где сопоставимое число вариантов.
Для шведок, кстати, я хотел написать в своё время ai, но за это, блин, не платят) Так что отложил до пенсии))

Шведки

[fungophil.livejournal.com]

>>Остался последний бастион, шведские шахматы (bughouse). В них компьютер ещё не скоро (никогда?) не научится играть лучше человека.

Это пока так, но все потому что боты играют пока сами за себя. Боюсь, что как только найдется энтузиаст, который научит боты "видеть" обе доски, то у человека шансов будет мало. Ибо боты быстрее.

[spamsink.livejournal.com]

Осталось теперь применить этот подход к Аримаа, пока не поздно получить $10000. :)

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

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

[dmpogo.livejournal.com]

Я не думаю что в мозгу происходит параллельный расчет первого хода h2-h3 до конечной позиции, и лишь потом выбирается е2-е4

[vsopvs.livejournal.com]

мне всегда интересно, есть ли, кроме интроспекции, доказательство того, что человеческий мозг играет в Го не путем слепого бездумного перебора?

интроспекция, все-таки, не слишком надежная вещь, мне кажется.

[dmpogo.livejournal.com]

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

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

[gdt.livejournal.com]

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

[dmpogo.livejournal.com]

Да, обидно что решение приходит просто за счет "brute force".
В определенной степени, это наблюдается и в научных численных расчетах.

Ага, я вот численно подобрал такую формулу

[gaz-v-pol.livejournal.com]

путем слепого бездумного перебора

[osherovmikhail.livejournal.com]

Современные компьютеры играют в шахматы отнюдь не методом слепого бездумного перебора. Михаил Ботвинник пытался построить "Думающую" машину, в его годы шахматные компьютеры действовали простым перебором. Сейчас программы-победители не только перебирают ходы, но и частично думают. Применяются многие методы - и Бритва Оккама, чтобы машина не думала лишнего и не тратила время, стандартные эндшпили, оценки силы фигур, оценки позиции. Полностью принципы Ботвинника, в том числе неточная цель игры, оценка позиции, не применяются, но метод траекторий фигур - применяется. И т. д.

[bvlb.livejournal.com]

А мне недавно попадалась лекция, в начале которой упоминается о том, что легендарный TD-Gammon переписали с использованием линейного классификатора вместо нейронной сети, а он, зараза, играет в нарды, как и раньше, на уровне чемпионов мира. Тогда я и подумал, кстати, что ГО недолго осталось.

[beldmit.livejournal.com]

А чем легендарен TD-Gammon?

[sensemaking.livejournal.com]

Картинка в тему об уютном знанием о мире (с объяснением какие игры остаются людям :)
http://xkcd.com/1002/

[deadkittten.livejournal.com]

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

[dragon-ru.livejournal.com]

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

[melkore.livejournal.com]

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

[dmpogo.livejournal.com]

Игры не становятся лучше от того что в них начинают играть компьютеры, наоборот, игры тогда умирают. Так что да, лучше не станет :)

[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]

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

[raindog-2.livejournal.com]

Алгоритмы игры в го гораздо сложнее и интереснее алгоритмов игры в шахматы. Я там впервые встретился с N-armed bandits (http://en.wikipedia.org/wiki/Multi-armed_bandit), и считаю это одним из главных открытий для себя за последние годы. Насчет понимания - это уже к теме "умеют ли компьютеры мыслить", про это я ничего не понимаю :)
Но согласен, что стиль игры у гошных программ действительно неважный. Го - игра стратегическая и это, в некотором смысле, диалог. Ну и игра с го-программой - это примерно как диалог с Элизой. Прикольно, но и только.
Кстати, в текущее время людям, которые серьезно занимаются го, не рекомендуют играть с программами.
(Хотя, конечно, программа может помочь с тактикой, в просчете локальных задач).

К нам на работу недавно приходила Чизу Кобаяси, очень известный профессиональный го игрок из Японии. Она рассказывала, что автор программы Zen много играл со своей программой и в результате стал играть в ее нечеловеческом "стиле". Не знаю только, стал он играть от этого сильнее или нет.

[mratner.livejournal.com]

К нам на работу недавно приходила Чизу Кобаяси

Надо же, какие люди! Я помню когда она в первый раз приехала в Ленинград и учила нас - гошную молодежь - на семинаре в Клубе Шахматиста на Желябова - году в 1983-м наверно. Симпатичная страшно, мы ее называли "Кобаяшка обаяшка". Давно это было...

[raindog-2.livejournal.com]

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

Я даже долгое время подумывал организовать конкурс программ, но реально вряд ли найдутся желающие убивать время на дурака. Хотя в России есть группа людей, которая играет турниры в дурака, по-серьезноме, и очень на крупные ставки. Они кстати ввели там правило удваивания, как в нардах, что еще больше усложнило игру. Кажется, там Анатолий Карпов был то ли организатором, то ли президентом ассоциации. Может, их заинтересовало бы быть спонсором.

[grihanm.livejournal.com]

Думаю повод для оптимизма точно есть - человек может взять кувалду и раздолбать компьютер нахх! :)))

[french-man.livejournal.com]

Ничего, когда-нибудь появятся программируемые кувалды :)

[(Anonymous)]

http://xkcd.com/1002/

[Дмитрий Рождественский (from livejournal.com)]

Го - хитрая игра. Если в шахматы гроссмейстеры думают над ходом подолгу, то в го многие корейские мастера играют 3-5 секунд на ход. В шахматах важно знать дебюты, а в го говорят: чем больше дебютов ты знаешь - тем хуже играешь. Поэтому непонятно так ли плохо это, простой перебор в го.

[mratner.livejournal.com]

Корейцы играют в какое-то свое Го. Тем, кто вырос на японской версии, оно непонятно.

[oulenspiegel.livejournal.com]

Это простая игра для компьютера.
Просто те, кто пишут реализации подкидного дурака для мобильников, чаще всего не особо разбираются в разработке AI.

[noubase.livejournal.com]

http://gogameguru.com/zen-computer-go-program-beats-takemiya-masaki-4-stones/