Машинный разум нанёс человеку удар в го
Фора в семь камней и соперник девятого про-дана вам о чём-то говорят? Нам также. В это же время речь заходит о ветшайшей игре в мире, ведущейся на доске. И мир взбудоражен: программы смогли побороть опытных игроков самого большого уровня.
За результатом, что занимателен, казалось бы, лишь фанатам, стоит большой труд в области ИИ. Мы сдаём «кремнию»?
Китайские предания датируют рождение го началом второго тысячелетия до нэ. Эта старая игра, пожалуй, кроме того более сложна, чем шахматы. Уж для машинного интеллекта она определённо сложнее.
Тем бросче достижение компьютерщиков.
В феврале на респектабельном турнире по го Taiwan Open 2009 компьютерная программа MoGo (смотрите кроме этого эту страницу) обыграла двух специалистов в битве на гобане 19 х 19. С гандикапом в 7 камней она победила игрока девятого дана Дзюньсюнь Чжоу (Jun-Xun Zhou), а с форой в 6 камней сломила сопротивление игрока первого дана Личэнь Чиэня (Li-Chen Chien).
Девятый дан, увидим, это предел мастерства, профи высшей пробы. Учитывая фору, данную машине, возможно заявить, что она выступила на уровне если не специалиста, то самого сильного любителя.
Существует пара вариаций правил го (японские, китайские, американской ассоциации го и ряд других).
Отличаются они в подробностях, касающихся применения форы, последовательности правил, действующих на протяжении игры, и кроме этого подсчёта очков в конце сражения, а ещё – правилами определения ранга игроков.Ранги (кю и даны) воздействуют на начальные условия игры: в случае если видятся соперники различного уровня, не сильный даётся фора в виде нескольких камней, каковые тот выкладывает на доску до первого хода соперника. По большей части считается, что отличие в ранге на одну единицу компенсируется одним камнем гандикапа, но в Китае, Японии и Корее в ранжировании опытных игроков предполагается, что отличие в один дан соответствует лишь трети камня форы, другими словами уровни мастерства идут плотнее (фото с сайта collegedegrees.com).
И это впечатляющее достижение. Лет пять назад программы го имели возможность с уверенностью побеждать только у детишек, сравнительно не так давно приступивших к изучению данной умной стратегической игры. С простыми любителями те же программы играли на равных, ну а специалистам автомобили бесславно «сливали», кроме того имея гандикап в 25 камней.
И ещё год-полтора назад уровень программ оставался относительно скромным. Пара случаев побед автомобилей в отдельных партиях над суперпрофи имели место при большем (чем в 2009-м) гандикапе, или при играх на уменьшенном поле (9 х 9).
Последнее радикально снижает число вероятных вариантов развития событий по ходу сражения, что упрощает задачу для компьютера. А тут сходу пара прорывов.
Обыгравшая человека программа MoGo была запущена на суперкомпьютере Huygens в Амстердаме, а с Тайванем его связывала Сеть. Пиковая производительность данной совокупности превышает 60 терафлопов (фото с сайта huygens.supercomputer.nl).
В те же февральские дни 2009-го вторая программа го — Many Faces — на конференции-выставке Американской ассоциации продвижения науки (AAAS meeting 2009), совершённой в Чикаго обыграла одного из сильнейших (если не сильнейшего) американских игроков в го Джеймса Кервина (James Kerwin, первый дан), не смотря на то, что и опять-таки с предоставленным машине значительным гандикапом (7 камней).
Да, программы начали играться в го на пара тысяч лет позднее людей. Возможно сообщить, они сделали движение вторыми. Но у автомобилей намного выше скорость обработки информации, чем в живом мозге.
В глобальной партии разумов посчитаем это коми.
Главные правила го не столь уж сложны. Упрощённо говоря, задача игроков сводится к окружению камней соперника собственными камнями.
Но игра эта владеет громадной «глубиной» – вариантов действий в ответ на ходы соперника – огромное количество, а вариантов тактики кроме того в локальных сражениях (около одной из групп камней) – ещё больше (иллюстрация с сайта grappa.univ-lille3.fr).
Возможно констатировать: пал бастион, что продолжительное время считался одним из последних примеров превосходства живого разума над машинным. Пускай программы для игры в го (Computer Go, смотрите кроме этого computer-go.info) фактически не уступают в длительности собственной эволюции шахматным программам, многие эксперты утверждали, что в го машина ни при каких обстоятельствах не победит игрока-человека, входящего в число сильнейших в данной дисциплине на планете.
Обстоятельство в том, что особенности игры (в сравнении с теми же шахматами) разрешают человеку относительно весьма долгие последовательности вероятных ходов, выстраивая на данной базе хитроумные тактику и стратегию (а вот это уже совсем непросто). Но программа неимеетвозможности мыслить как человек, она механистична, а её выбор ответного хода — итог перебора вариантов, а не творческое решение проблемы.
Many Faces в версии 12.0 есть официальным мировым чемпионом среди программ го 2008 года. В том же чемпионате MoGo стала второй, а всего в нём сражались 13 программ.
Many Faces трудилась на кластере, содержащем 32 процессора по 3,2 гигагерца (иллюстрация с сайта smart-games.com).
И однако программы стали куда ближе к людям по способу и стилю обдумывания игры. Так как при с го буквальным перебором всех последующих позиций нельзя добиться ровным счётом ничего. Из-за чего? Перед тем как возвратиться к MoGo и Many Faces, нам легко нужен экскурс в историю.
Для начала — в историю битвы человек-машина на шахматном поле.
«Софтинки», талантливые хоть как-то играться против человека, показались весьма в далеком прошлом, но что серьёзнее — уже в конце 1990-х были созданы программы, талантливые сражаться с мировыми чемпионами а также побеждать у них. Легендарная первая игра в матче Гарри Каспарова против автомобили (Deep Blue – Kasparov 1996) тому пример.
Чемпион, потеряв эту одну игру, победил в том году целый матч, но через год усовершенствованная Deep Blue победила Каспарова уже совсем (Deep Blue – Kasparov 1997).
Интуиция, опыт, знание огромного числа игр прошлого, подкреплённые образным, чисто людской мышлением, которое так тяжело формализовать, уступили в тот раз «железке» Deep Blue, талантливой выбирать по 200 миллионов позиций в секунду.
Выбирать, но, не тупо. Так как неспециализированное число вероятных положений фигур в шахматах очень, соответственно, машине нужен был метод, разрешающий «разумно» выбирать среди множества вариантов продолжения самые перспективные.
Шахматный автомат Turk, выстроенный в первой половине 70-ых годов восемнадцатого века, был только мечтой о автомобилях, талантливых побороть человека в старой игре. Но не смотря на то, что он являлся обманом (а игрался за «турка» умело запрятанный человек), обладателям аппарата получалось морочить публике головы много-много лет (иллюстрация с сайта wikipedia.org).
Конечно, что программу компьютерщикам помогали готовить люди, досконально опытные шахматную теорию. Так что возможно заявить, что во второй половине 90-ых годов двадцатого века гроссмейстер проиграл не суперкомпьютеру, но коллективному разуму множества людей, и это некое утешение для человечества в целом. А не сильный утешением лично для Каспарова были ничейные матчи с двумя вторыми, не меньше коварными программами, совершённые в 2003-м.
По большому счету же по окончании матча 1997 года новые игры сильнейших шахматистов-людей против сильнейших программ продолжились, но уже не вызывали для того чтобы большого интереса, как раньше. В 2002 году «кремниевый шахматист» Deep Fritz сыграл с Владимиром Крамником вничью, а в 2006-м та же программа победила-таки и этого чемпиона.
Wu Qingyuan (второе наименование The Go Master), фильм-биография (Китай/Япония, 2006 г.), посвящённая самому сильному мастеру го XX века и одному из лучших игроков всех времён У Цинюаню, больше известному как Го Сэйгэн (Go Seigen). Китаец по рождению, в юности он переехал в Японию, трудолюбиво поднявшись на самые вершины го.На протяжении войны Го Сэйгэн стал перед непростым выбором между собственной первой и второй отчизной.
Появлявшись своим среди чужих и чужим среди собственных, великий профи остался верен го, сделав многое для развития теории а также философии данной игры. Имел возможность бы такую сильную личность победить ИИ? Сейчас мастеру практически 95, и чуть ли он снизойдёт до поединка с машиной. Не смотря на то, что кто знает… (иллюстрация с сайта verycd.com)
Менее известна история сражения ИИ с человеком на поле шашек.
Не представляет собой головоломки создание программы, которая игралась бы как среднестатистический человек, но побеждать у сильнейших шашистов мира — это уже задача совсем нетривиальная, не обращая внимания на относительную простоту игры.
Приблизительно на равных с сильнейшими «сапиенсами» бездушные игроки обучились выступать в 1990-м. Но позднее компьютерным гениям удалось пойти ещё дальше, чем в шахматах. В последних у человека постоянно остаётся шанс на выигрыш у автомобили.
А вот в шашках для того чтобы шанса у нас уже нет.
В 2007 году шашки были всецело «взломанными», другими словами были просчитаны на суперкомпьютере все их комбинации и возможные ходы. Именно поэтому последняя версия шашечной программы Chinook – она, кстати, и игралась в 1990-х с мировым чемпионом Мэрионом Тинсли (Marion Tinsley) – стала беспроигрышной. Другими словами ни один человек у неё не сможет победить ни при каких обстоятельствах, потому, что машина в любой позиции постоянно знает наилучший движение.
С шахматами таковой «взлом» чуть ли вероятен обозримой перспективе. Число всех вероятных позиций на шахматной доске (не противоречащих правилам, скажем, двух королей вы не имеете возможность поставить рядом) образовывает ориентировочно 1046 (в шашках порядок куда скромнее — 1020), потому лучшие суперкомпьютеры планеты сообща не переберут их всех поочерёдно кроме того за время, на многие порядки превышающее возраст Вселенной.
Сможем ли мы лет через 50 нарастить производительность суперкомпьютеров на много-много порядков либо придумать метод «взлома» шахмат в обход полного перебора?
Это громадный вопрос. Но что уж тогда сказать об игре в го? Тут волшебство солидных чисел любого, кто пробует «с линейкой» измерить глубину вероятных ходов.
Японская картина финиша XIX века «Семь дам готовят чай и играются в го» (иллюстрация с сайта castlefinearts.com).
По словам Дэвида Дошея (David Doshay) из Калифорнийского университета в Санта-Круз (UCSC), ведущего собственное изучение го и к тому же создавшего ещё одну го-программу SlugGo, число вероятных конечных позиций в партии го (на стандартном поле 19 х 19) образовывает 10171. И к ним возможно прийти одним из 101100 дорог!
Это число столь громадно (сравните — сумма всех элементарных частиц во Вселенной образовывает «всего» 1080), что прямой перебор всех вариантов игры полностью неосуществим.
Но и «минимаксное» дерево поиска, которое прекрасно зарекомендовало себя в шахматных программах, – в го трудится не хорошо.
В таковой стратегии компьютер выбирает все вероятные ходы из данной позиции, но на конечное число ходов вперёд (в лучших программах на 12, другими словами вовсе не до конца вымышленной партии, это принципиально важно). Полученные позиции оцениваются на предмет качества (выгодности).
С немногочисленными лучшими вариантами программа отыгрывает назад, опять в мыслях делает ходы, но уже ведущие как раз к отобранным позициям (и кроме этого последовательность последующих ходов на энное число шагов), опять вычисляет все варианты оказавшихся состояний и снова отбирает из них пара самых успешных. И без того по кругу.
Специфика го не разрешает разрешённому подходу давать прекрасные результаты. Дерево вероятных состояний на гобане (доске для го) ветвится через чур скоро. Так, что в отличие от шахмат скоро «забивает» свойстве всех современных компьютеров.
Как же компьютерщики нашли выход?
Историческая отчизна го – Китай. Правильное время появления данной игры неизвестно, но, так или иначе, произошло это ещё до нэ (иллюстрация с сайта 361points.com).
Создатели Many Faces, американская компания Smart Games и её фаворит Дэвид Фотланд (David Fotland), воспользовались методом Monte Carlo Tree Search, другими словами «Деревом поиска Монте-Карло», что был развит французскими экспертами по неестественному интеллекту в 2006-2007 годах. MoGo (а правильнее, многочисленная несколько компьютерщиков из нескольких лабораторий и французских университетов,разработавших эту программу) пользуется сходным же способом, не смотря на то, что и хорошим в подробностях.
Как явствует из заглавия, его возможно отнести к так называемым «способам Монте-Карло» (Monte Carlo method) — это неспециализированное наименование громадной семьи численных способов, в которых изучаемый процесс (задача) моделируется так, что решается не «в лоб», а путём просчёта конечных результатов огромного числа случайных событий.
Имеется дамэ! Отечественная точка свободы. Постигнем гармонию через рукотворный хаос.
Самый примитивный пример. Вы желаете вычислить возможность того, что подброшенная монетка упадёт решкой (предположим, вы не понимаете, какова эта возможность). Вместо законов теории и применения формул возможности, рассуждений о физике перемещения тела, вы монетку десять тысяч раз и, подсчитав число событий, обнаруживаете, что искомый ответ — ровно 50%.
На деле же различные вариации способа Монте-Карло используют для моделирования куда более сложных вещей: динамики молекулярных совокупностей, поведения квантовых частиц либо кроме того социальных процессов. А создан был данный способ (в целом) в Лос-Аламосе, на протяжении работ над ядерной бомбой.
А как он получил в го? Программы-победители, стартуя из имеющейся позиции, сперва выбирают случайным образом пара миллионов игр, каковые смогут быть сыграны из этого положения. Число громадное, но в полной мере конечное.
Причём каждую игру машина проигрывает до конца, совсем не заботясь о разумности либо выгодности ходов, как собственных, так и виртуального визави (только бы правила не нарушались).
Громаднейшей популярностью го пользуется в Корее, Китае, Тайване и Японии. В том месте же живут сильнейшие игроки мира.
Как киногерой «Мастер Го», кадр из которого вы видите (кадр с сайта allocine.fr).
Взяв запись ходов для каждой игры из этих миллионов, программа образовывает статистику – какие конкретно первые ходы скорее ведут к выигрышу. Не забывайте пример с монетой? Вы бросали её без совокупности, но, взглянуть на много результатов, установили, что возможность выпадения одной стороны равна 50%.
По преданиям, в го играются всевышние, в то время, когда решают судьбу Вселенной. Сейчас будущее Вселенной в руках автомобилей? (фото с сайта arco-iris.com)
Сообщите – ко – вы повторяетесь! Но в программах го дело обстоит схожим образом.
По статистике миллионов совсем безумных, хаотичных игр, в которых машина не «думала» над ходами, но игр просчитанных до конца, программа устанавливает, что следующий движение такой-то приведёт к выигрышу с возможностью, скажем, 3%, такой-то — 1,5%, а вот данный – 0,02% и без того потом. А ведь вероятных ходов кроме того на чистом поле го (19 х 19) – всего 361, а на частично заполненном – куда меньше.
Потом компьютер движение с громаднейшей возможностью выигрыша и контролирует ещё пара миллионов игр уже из нового положения. Это разрешает уточнить возможность победы, в конечном счёте сделав выбор – какой движение направляться произвести в настоящей игре с человеком.
Роберт Хирн (Robert Hearn), компьютерщик и математик из Дартмутского колледжа, и – сильный игрок в го, прогнозирует, что преодолеет менее 30 лет, и программы (в основном за счёт роста мощности суперкомпьютеров) начнут обыгрывать в го лучших профи кроме того без гандикапа. Арпад Риммель (Arpad Rimmel), один из авторов MoGo, оценивает данный срок и вовсе в 10 лет.
Но это не приблизит нас кразгадке того, как мыслит человек, играющий в го. Он-то не выбирает миллионы ходов.
Taiwan Open 2009: слева – игрок первого дана Личэнь Чиэнь, в центре – один из устроителей состязания Чаншин Ли (Chang-Shing Lee), справа – Арпад Риммель (кадр с сайта ireport.com).
«Удивлением, тайной для меня есть то, что эти методы трудятся», — говорит Хирн, комментируя новые успехи MoGo и Many Faces. Поясним: кроме того сами авторы этих программ замечательно знают – как они трудятся, но наряду с этим не знают – из-за чего это срабатывает.
У человека за выбор хода в го отвечает интуиция, умноженная на распознавание образов. Трудится визуальная аналогия (эта форма группы воздействует на эту часть доски, эта конфигурация страшна, и без того потом). Человек мыслит категориями судьбы, смерти и эволюции групп камней на доске. Он выясняет привычные конфигурации, даже если они только близки к когда-то виденным.
Он обучается обобщать образы (вот камни выстроены в цепочку, вот кольцо с разрывом на боку, вот ещё что-то). Образность и оказывает помощь человеку принимать решения за разумное время.
Майкл Атертон (Michael Atherton) и его коллеги из университета Миннесоты (University of Minnesota) в один раз просканировали мозги игроков в шахматы и го в ходе этих игр. Стало известно, что у игроков го особенно очень сильно активировались теменные доли, несущие ответственность за обработку восприятия пространственного положения объектов.
Сражавшиеся игроки покинули автографы на гобане. За MoGo расписался Риммель (кадр с сайта ireport.com).
Сходные японские испытания продемонстрировали кроме этого, что у игроков-профи к концу игры очень сильно активируются и регионы, несущие ответственность за восприятие положения тела и за перемещения.
Атертон всё это обобщил так: «Игроки в го упрощают дерево поиска ответов до эстетического эмоции. У них имеется чувство игры».
Потому отечественное весьма кроме того скромное число нейронов легко справляется с тем, на что компьютеру, кроме того с новым «монте-карловским» подходом, требуются тонны чипов и терафлопы производительности.
Этикет го предусматривает спокойное и сдержанное поведение на протяжении игры. Вот мы и говорим: нормально, у нас всё ещё имеется преимущество перед автомобилями.
Так случился ли прорыв? Нет, перед нами лишь фусэки. «Люди думают — как же на большом растоянии мы уже зашли, — говорит Дошей. — Но в конечном итоге мы лишь начали программировать компьютеры».
Да и по большому счету их поражающая мир поступь в значительной степени, — только иллюзия. Так как за каждой программой стоят люди, её написавшие. Соответственно, в общем матче со собственными детищами мы сохраняем сэнтэ и постоянно сможем позволить себе дать автомобилям «фору в семь камней».
[Stellaris: 1.8 Capek][Правление]Обзор на \
Темы которые будут Вам интересны:
-
За что основатель «макси-групп» судится с самым богатым человеком россии
-
Машина считала зрительный образ с мозга человека
