Секрет древней игры го. почему компьютер до сих пор не обыграл человека?

Автор: ·

Секрет древней игры го. почему компьютер до сих пор не обыграл человека?

В первой половине 90-ых годов двадцатого века компьютер обыграл мирового чемпиона по шашкам, во второй половине 90-ых годов двадцатого века — по шахматам. Сейчас компьютеры превосходят людей полностью во всех играх с полной информацией, не считая одной — го.

У хорошей игры с 2500-летней историей весьма простые правила, но компьютерные программы кроме того близко не смогут подобраться к победе над лучшими гроссмейстерами, пишет Wired.

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

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

В том месте гениальных детей забирают из дома для обучения в академии го приблизительно с 9 лет.

Продвинутые любители практически в любое время застревают на определённом уровне игры и не смогут улучшить итог: «Требуется некоторый ментальный прыжок, дабы снять эту блокировку, и в разработке программ та же неприятность, — растолковывает Дэвид Фотлэнд (David Fotland), основной разработчик процессора PA-RISC в компании Hewlett Packard в 70-е годы. Он тестировал программу го на процессоре собственной разработки. — Вопрос в том, как оценивать всю доску, а не отдельные фрагменты».

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

Компьютерные программы для го разрабатывают уже 45 лет, данной проблеме уделяли практически столько же внимания, сколько и шахматным программам. Первую написал гений теории игр Альфред Зобрист во второй половине 60-ых годов XX века. Она имела возможность обыграть безотносительного новичка, что только что познакомился с правилами (запись первой игры человек-компьютер). Начало казалось оптимистичным.

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

Обстоятельство можно понять, в случае если сравнить го с шахматами. В начале шахматной партии у белых имеется 20 вероятных ходов, а у тёмных — 20 вероятных вариантов ответа. По окончании первого хода на доске возможно 400 разных позиций. А сейчас сравните цифры в го: на доске 19х19 у тёмных имеется 361 вероятных начальных ходов, а у белых 360 вариантов ответа.

Это указывает 129 960 вероятных комбинаций лишь по окончании первого раунда.

Так называемый «фактор ветвления» — среднее количество ходов, дешёвых в каждом раунде — в шахматах образовывает 35, в го — 250. Игры с сильным ветвлением затрудняют работу стандартных методов, применяющих правило минимакса для дерева вероятных комбинаций. Кроме того с учётом анализа не всех, а лишь перспективных ветвлений для более глубокого анализа.

То, что трудится в шахматах и шашках, не работает в го. Выбор перспективных ветвлений в дереве вероятных комбинаций го — довольно часто совсем загадочный процесс. Кроме того игроки не знают, как они это делают: «Легко наблюдаешь на доску и знаешь», говорят они.

Снова же, в шахматах практически в любое время можно понять, кто побеждает, хотя бы по числу фигур. В го обстановку смогут толковать лишь специалисты.

Среднее количество ходов в игре: в шахматах — около 40, в го — 200. Учитывая фактор ветвления и эту статистику, делается понятным бессилие компьютеров.

Гениальный французский программист Реми Кулом (Remi Coulom) добился первого успеха с программой Crazy Stone в 2006 году, в то время, когда додумался совместить метод и минимакс Монте-Карло. Новый метод расчёта дерева ветвлений он назвал Monte Carlo Tree Search либо MCTS. Француз победил чемпионат среди компьютерных программ UEC Cup в 2007 и 2008 годах, но это так и не принесло ему известности, и Реми закинул разработку.

Но в 2010 году он взял предложение от японского игрового разработчика Unbalance — и в 2011 году вышла первая коммерческая версия Crazy Stone. В 2013 году Реми победно возвратился на чемпионат.

Но, в 2014 году произошла неудача. В финальном противостоянии против программы Zen зрители осознали, что творится что-то необычное уже по окончании третьего хода. Программа Zen, по окончании стандартной постановки двух камней по углам внезапно поставила третий камень около центра.

Так никто не игрался, это было очевидно «нечеловеческое» ответ. Скоро уровень победных ожиданий у Crazy Stone вырос до неприлично высоких значений, более 60%. "Наверное," программа вычисляла надёжной группу камней в правом верхнем углу, не смотря на то, что она не была надёжной.

Потому, что успешная стратегия зависит от верной оценки доски, зрители начали шептаться о вероятном поражении Crazy Stone. Так оно и вышло: на 186 ходу Crazy Stone признала поражение, а Zen стал новым чемпионом UEC Cup.

Но, у Кулома осталась возможность реванша. Как финалист, он взял право играться против настоящего гроссмейстера-человека с форой в четыре камня. В текущем году на турнир приехал Норимото Ёда. Японский гроссмейстер сел за стол в классическом зелёном кимоно.

Реми Кулом — в очках без оправы и светло синий свитере, в которых был и на прошлом чемпионате.

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

Обидное поражение Crazy Stone потерпела в самой концовке. Побеждая 11 камней, любой человек сделал бы пара очевидных защитных ходов, дабы не разрешить противнику отыграться и сохранить преимущество. Но Crazy Stone была запрограммирована лишь на победу. Исходя из этого её метод был в том, чтобы в ситуации выигрыша делать тщетные ходы в собственной территории, ожидая, в то время, когда соперник признает поражение.

Но тут таковой фокус не прошёл — и Ёда сумел отыграться. Во втором матче против Zen он уже смотрелся получше и победил у программы четыре камня.

Реми Кулэм всё равняется был радостен — и дал обещание к следующему чемпионату доработать метод действий в концовке.

"Наверное," не так долго осталось ждать компьютер победит в последнюю игру с полной информацией, которая до тех пор пока остаётся за человеком. По оценке Кулома, программа победит без форы в течение 10 лет. Специалисты, опытные силу лучших игроков, не так уверены. Дело в том, что на наибольших уровнях игра выходит на как следует другой уровень, ходы перестают быть предсказуемыми.

Одновременно с этим уровень качества игры программ до сих пор надеется не столько на вычислительную мощь, сколько на уровень качества кода: к примеру, те же Crazy Stone и Zen на 64-ядерных стандартных серверах легко побеждали 2048-ядерные кластеры соперников. Другими словами программы смогут опять уткнуться в стенке.

Но кроме того в случае если компьютеры и победят в го, нельзя говорить о «падении последнего интеллектуального бастиона», где господствует человек, как это писали газеты по окончании победы Deep Blue в шахматах. Программы для го — это легко узкоспециализированные инструменты для ответа конкретных задач. Они очень далеки от людской разума и не пробуют эмулировать работу мозга. «Для меня это легко развлечение, — говорит Кулом, — не более того».

habrahabr

Случайная запись:

10 СЕКРЕТНЫХ УРОВНЕЙ В ИГРАХ, КОТОРЫЕ ГЕЙМЕРЫ НЕ МОГЛИ НАЙТИ


Статьи по теме:

Метки: