Нейросеть нашла неожиданное решение самой сложной задаче в игре Го

_{Источник: Wikimedia ^[1]}

Нейросеть KataGo решила задачу, которая считается самой сложной в японской игре Го. Решение опубликовала ^[2] пользовательница под ником Cassandra на форуме 19х19. KataGo изменила 140-й ход 177-ходового решения, созданного немецкими исследователями, и пришла к неожиданному итогу: победа белых с перевесом в два очка вместо победы черных с перевесом в пять камней.

Алгоритм KataGo создан ученым из Гарварда Дэвидом Ву — он вдохновлялся более известным алгоритмом AlphaZero. AlphaZero — нейросеть DeepMind, основанная на обучении с подкреплением. Этот алгоритм тренировался исключительно на играх с самим собой: 5 000 тензорных процессоров первого поколения генерировали игры, 64 тензорных процессора второго поколения параллельно обучали сети. При этом у AlphaZero не было доступа к дебютным книгам и базам данных с исходом партий. По заявлениям создателей AlpaZero за 24 часа алгоритм достиг уровня выше человеческого сразу в шахматах, сёги и го.

Для поисков решения «самой сложной задачи в мире» KataGo обучалась непосредственно по материалам, этой задаче посвященным. Дело в том, что «самая сложная задача в мире» — 120-я из 183 уцелевших задач японского мастера Иноэ Досэцу Инсэки, жившего в конце XVII — начале XVIII веков. Он был главой офиса Годокоро, учрежденного правительством Иэясу Токугавы. Этот офис отвечал за церемониал, связанный с го, распределял дипломы и присуждал даны. Инсэки создал учебник с набором наиболее сложных задач в истории Го — записи пострадали в пожаре и до нас дошло лишь 183 задачи.

Задача под условным номером 120 считается наиболее сложной — решению ее одной посвящено несколько книг и даже сайт ^[3]. Семикратный чемпион Европы по Го Александр Динерштейн ^[4] в комментарии для Хабра пояснил, что в отличии от прочих задач в 120-й не до конца ясна цель. При этом в остальных цель зачастую очевидна — обычно все сводится к спасению или убийству группы камней противника. Причем из стартовой диспозиции становится ясна и сама цель, и чей ход будет первым. В приведенной же задаче цель выражена туманно и большинство игроков-профессионалов интерпретируют ее как «сыграть черными и выиграть».

_{Источник: Senseis ^[5]}

Над решением бились мастера из Японии, в том числе обладатель японского титула Кисей (Святой Го) Фудзисава Хидэюки. Ошибку в его решении, как и в других решениях мастеров прошлого нашла группа исследователей из Германии, которые называют себя «три любителя» (Three amateurs). Они же предложили свое решение в 177 ходов, при котором черные выигрывают в пять камней.

KataGo проанализировала существующие решения и предложила свое — на 140 ходу сыграть белым камнем на Е17, вместо G18, как предлагали Three amateurs. В итоге партию выигрывают белые с перевесом в два очка.

_{Источник: Иллюстрация предоставлена Александром Динерштейном}

Таким образом, KataGo:

• Решила задачу, которая была не под силу прочим нейросетям. Тот факт, что прочие нейросети были бессильны связывают с нестандартностью расстановки, которую придумал Иноэ Досэцу Инсэки.
• Нашла нестандартное решение с более сильным ходом, которое в итоге привело к победе белых, а не черных.

Динерштейн предположил, что для нейросети посильными окажутся и прочие задачи из сборника. Над 120-й лучшие мастера игры трудились практически 300 лет и не могли справится — именно это принесло ей славу «самой сложной задачи в мире».

Примечательно, что более ранней версией нейросети AlphaZero (AZ), по подобию которой создавал KataGo Дэвид Ву, была заточенная чисто под Го AlpaGo Zero (AGZ). AZ в отличие от AGZ может играть еще и в сёги с шахматами, а в ее параметрах есть несколько отличий. В AZ есть жестко заданные правила для настройки гиперпараметров поиска, а нейросеть постоянно обновляется. При этом AZ не умеет пользоваться симметрией игрового поля в Го, а AGZ умеет. В итоге, AlphaZero переиграла AlphaZero Go в соотношении 60 побед на 40 поражений, а затем превзошла самые совершенные алгоритмы для шахмат (Stockfish) и сёги (Elmo).

Автор: Leonid_R

Источник ^[6]