Источник: Wikimedia
Нейросеть KataGo решила задачу, которая считается самой сложной в японской игре Го. Решение опубликовала пользовательница под ником Cassandra на форуме 19х19. KataGo изменила 140-й ход 177-ходового решения, созданного немецкими исследователями, и пришла к неожиданному итогу: победа белых с перевесом в два очка вместо победы черных с перевесом в пять камней.
Алгоритм KataGo создан ученым из Гарварда Дэвидом Ву — он вдохновлялся более известным алгоритмом AlphaZero. AlphaZero — нейросеть DeepMind, основанная на обучении с подкреплением. Этот алгоритм тренировался исключительно на играх с самим собой: 5 000 тензорных процессоров первого поколения генерировали игры, 64 тензорных процессора второго поколения параллельно обучали сети. При этом у AlphaZero не было доступа к дебютным книгам и базам данных с исходом партий. По заявлениям создателей AlpaZero за 24 часа алгоритм достиг уровня выше человеческого сразу в шахматах, сёги и го.
Для поисков решения «самой сложной задачи в мире» KataGo обучалась непосредственно по материалам, этой задаче посвященным. Дело в том, что «самая сложная задача в мире» — 120-я из 183 уцелевших задач японского мастера Иноэ Досэцу Инсэки, жившего в конце XVII — начале XVIII веков. Он был главой офиса Годокоро, учрежденного правительством Иэясу Токугавы. Этот офис отвечал за церемониал, связанный с го, распределял дипломы и присуждал даны. Инсэки создал учебник с набором наиболее сложных задач в истории Го — записи пострадали в пожаре и до нас дошло лишь 183 задачи.
Задача под условным номером 120 считается наиболее сложной — решению ее одной посвящено несколько книг и даже сайт. Семикратный чемпион Европы по Го Александр Динерштейн в комментарии для Хабра пояснил, что в отличии от прочих задач в 120-й не до конца ясна цель. При этом в остальных цель зачастую очевидна — обычно все сводится к спасению или убийству группы камней противника. Причем из стартовой диспозиции становится ясна и сама цель, и чей ход будет первым. В приведенной же задаче цель выражена туманно и большинство игроков-профессионалов интерпретируют ее как «сыграть черными и выиграть».
Источник: Senseis
Над решением бились мастера из Японии, в том числе обладатель японского титула Кисей (Святой Го) Фудзисава Хидэюки. Ошибку в его решении, как и в других решениях мастеров прошлого нашла группа исследователей из Германии, которые называют себя «три любителя» (Three amateurs). Они же предложили свое решение в 177 ходов, при котором черные выигрывают в пять камней.
KataGo проанализировала существующие решения и предложила свое — на 140 ходу сыграть белым камнем на Е17, вместо G18, как предлагали Three amateurs. В итоге партию выигрывают белые с перевесом в два очка.
Источник: Иллюстрация предоставлена Александром Динерштейном
Таким образом, KataGo:
- Решила задачу, которая была не под силу прочим нейросетям. Тот факт, что прочие нейросети были бессильны связывают с нестандартностью расстановки, которую придумал Иноэ Досэцу Инсэки.
- Нашла нестандартное решение с более сильным ходом, которое в итоге привело к победе белых, а не черных.
Динерштейн предположил, что для нейросети посильными окажутся и прочие задачи из сборника. Над 120-й лучшие мастера игры трудились практически 300 лет и не могли справиться — именно это принесло ей славу «самой сложной задачи в мире».
Примечательно, что более ранней версией нейросети AlphaZero (AZ), по подобию которой создавал KataGo Дэвид Ву, была заточенная чисто под Го AlphaGo Zero (AGZ). AZ в отличие от AGZ может играть еще и в сёги с шахматами, а в ее параметрах есть несколько отличий. В AZ есть жестко заданные правила для настройки гиперпараметров поиска, а нейросеть постоянно обновляется. При этом AZ не умеет пользоваться симметрией игрового поля в Го, а AGZ умеет. В итоге, AlphaZero переиграла AlphaZero Go в соотношении 60 побед на 40 поражений, а затем превзошла самые совершенные алгоритмы для шахмат (Stockfish) и сёги (Elmo).
Комментарии (40)
MooNDeaR
29.10.2019 12:15Кто-нибудь, дайте ссылку на перевод условий задачи. Я чёт вообще не понимаю как можно считать сложной задачу, условия которой не сформулированы :D
M_AJ
29.10.2019 12:26+1Как я понял там все нормально написано: выиграть за чёрных. Некая группа решила эту задачу, а сеть опровергла решение выиграв за белых.
egigd
29.10.2019 13:39Но автор статьи какого-то фига сказал, что нейросеть решила ещё лучше, а не опровергла…
tundrawolf_kiba
29.10.2019 14:07Я так понял, что не опровергла, а нашла, что оптимальная игра приводит к гораздо быстрой победе белых. Но в этом случае, если задача была найти более быстрый вариант победы за черных — получается, что решение было найдено, но не для того вопроса, который ставился изначально.
Am0ralist
29.10.2019 14:29Но вот в чём вопрос: а есть ли верное решение с победой черных? с учетом, что задачу придумали так давно.
tundrawolf_kiba
29.10.2019 14:36Вроде, как я понял из статьи — есть решение и нейросеть изменила в нем один ход, что и привело к победе уже белых.
mk2
Для неспециалистов можно пояснение? Как это — была задача «выиграть за чёрных», а нейросеть решила её победой за белых?
Я могу понять, если на самом деле нейросеть опровергла решение от «трёх любителей», но это не «решила».
Leonid_R Автор
Понимаете, тут сложный момент, который отразил Динерштейн — условия в 120-й сформулированы нечетко (все таки писал японец 300 лет назад) и большинство интерпретируются как начать и выиграть за черных. Три любителя действительно решили так, как большинство интерпретируют — выиграли за черных. Нейросеть же нашла более сильный ход и свой вариант исхода партии. Замечу, что за белых никто не мог выиграть до сих пор.
kahi4
Если за белых выиграть не смог никто, почему тогда есть сложности выиграть за чёрных?
kisaa
Может быть, данная расстановка такова, что обычно ведет к ничьей?
vesper-bot
Ничьих в Го вообще-то не бывает, белые имеют на пустой доске 0.5 камня форы.
kommari
не 0.5, а все таки 6.5.
joker512
Мне кажется должен быть такой расклад. Нейросеть заставили играть против самой себя в указанной позиции и выяснилось, что побеждают белые, а не чёрные, как всегда думали. Иначе правда непонятно о чем речь.
slonopotamus
Возможно в Го сложно играть? :)
Anton3
"Выиграть" в данном контексте означает проанализировать экспоненциальное число партий и найти выигрышную стратегию при условии идеальной игры противоположного игрока.
x67
Вы задаете слишком много вопросов, вы нам не подходите)
shasoft
Возможно нужно выиграть за минимальное количество ходов. Т.е., к примеру, как в шахматных задачах, указывается количество ходов, за которое нужно поставить мат. В некоторых задачах выиграть за указанный цвет проблем не составляет, проблему составляет уложиться у нужное количество ходов.
slonopotamus
Японцы 300 лет назад имели настолько неразборчивый почерк что невозможно отличить «чёрный» от «белого», а «выиграть» от «проиграть»? Или вместо «задача: выиграть чёрными» он написал хокку про сакуру и самурая и интепретируй это как можешь? Что вы имеете в виду?
На сайте куда ссылается статья чёрным по
беломузелёному написано что надо выиграть за чёрных. Правда тогда становится совсем непонятно причём тут «решение» нейросети.red_andr
Объяснить Го одним комментарием или даже в одной статье невозможно. Не говоря уже о самой сложной задачи. Давайте просто восхищаться нейросетью без лишних вопросов.
GeMir
red_andr
Да, можно и так. Жаль, конечно, что мой сарказм не оценили.
duronus
С таким же успехом можно восхищаться тем что в 30 лет разукрасил картинки в книжке для детей.
AllexIn
Плевать что там с ГО.
Какая была задача и как её решила сетка?
jaiprakash
Был известен ответ: 42. Осталось выяснить — в чём вопрос.
x67
Разве важен вопрос, если у нас есть ответ
perfect_genius
У нас есть мозг, и это ответ. Нам важно найти к нему вопрос.
Gordon01
Press F to pay respect
MatiasGray
Я немного не дотягиваю до любителя, но мне кажется, суть тут вот в чём.
В рамках "решения задач" расстановка фигур такова, что один игрок находится в "сложной ситуации", и зада состоит в том, чтобы найти неочевидную последовательность ходов для локального выигрыша. Для другого же игрока ходы легко читаются и решающий головоломку автоматически видит самый эффективный ход.
Тут же выяснилось, что у белых есть другой вариант ответа на ходы чёрного. Таким образом, решение трёх любителей опровергнуто.
agmt
А что мешает другой стороне поддаваться?
MatiasGray
Наверное стоит сказать, что суть решения задачи в том, чтобы найти её решение не выходя из рамок игры: не нарушая правил, не меняя исходную задачу, не переворачивая стол, не вступать в драку с оппонентом.
Конечно, можно решить задачу этими методами, они ни чуть не хуже традиционных, но обычно они даже не приходят в голову решающему задачу. Задачки ГО это не совсем игра, это более изощрённое времяпрепровождение, которым занимаются действительно увлекающиеся люди. А им просто не приходит в голову жульничать, им интересно на самом деле решить задачу.
agmt
Но ведь даже если 1 и ту же нейросеть по очереди сажать за разные стороны стола (наиболее честный метод, пришедший мне в голову), все равно она может быть (в теории) по разному натренирована на белую и черную ситуации и как бы будет поддаваться.
MatiasGray
Скорее, вы хотите сказать что она может работать неправильно, из-за неправильного обучения?
Этого не могло быть, так как обучали её не на этой задаче.
LoadRunner
MatiasGray
О, проглядел.
А что были за «материалы», интересно?
LoadRunner
MatiasGray
Да, я знаю что есть сайт. Мне интересно, какие данные данные могла сгенерировать задача го. Просто интересно, я не задаю вам вопрос, спасибо.
dolovar