Геймер k1no 21
Машинный разум нанёс человеку удар в го
Китайские легенды датируют рождение го началом второго тысячелетия до нашей эры. Эта древняя игра, пожалуй, даже более сложна, чем шахматы. Уж для машинного интеллекта она определённо сложнее. Тем ярче достижение компьютерщиков.
В феврале на престижном турнире по го Taiwan Open 2009 компьютерная программа MoGo обыграла двух профессионалов в битве на гобане 19 х 19. С гандикапом в 7 камней она победила игрока девятого дана Дзюньсюнь Чжоу (Jun-Xun Zhou), а с форой в 6 камней сломила сопротивление игрока первого дана Личэнь Чиэня (Li-Chen Chien).
Девятый дан, заметим, это предел мастерства, профи высшей пробы. Учитывая фору, данную машине, можно сказать, что она выступила на уровне если не профессионала, то самого сильного любителя.
Машинный разум нанёс человеку удар в гоИ ещё год-полтора назад уровень программ оставался сравнительно скромным. Несколько случаев побед машин в отдельных партиях над суперпрофи имели место при большем (чем в 2009-м) гандикапе, либо при играх на уменьшенном поле (9 х 9).
Последнее радикально снижает число возможных вариантов развития событий по ходу сражения, что упрощает задачу для компьютера. А тут сразу несколько прорывов.
Машинный разум нанёс человеку удар в гоОбыгравшая человека программа MoGo была запущена на суперкомпьютере Huygens в Амстердаме, а с Тайванем его связывала Сеть. Пиковая производительность этой системы превышает 60 терафлопов.
В те же февральские дни 2009-го другая программа го — Many Faces — на конференции-выставке Американской ассоциации продвижения науки (AAAS meeting 2009), проведённой в Чикаго обыграла одного из сильнейших (если не сильнейшего) американских игроков в го Джеймса Кервина (James Kerwin, первый дан), хотя и опять-таки с предоставленным машине существенным гандикапом (7 камней).
Да, программы начали играть в го на несколько тысяч лет позже людей. Можно сказать, они сделали ход вторыми. Но зато у машин намного выше скорость обработки информации, чем в живом мозге. В глобальной партии разумов посчитаем это коми.
Машинный разум нанёс человеку удар в гоОсновные правила го не столь уж сложны. Упрощённо говоря, задача игроков сводится к окружению камней противника своими камнями. Но игра эта обладает большой "глубиной" – вариантов действий в ответ на ходы соперника – огромное количество, а вариантов тактики даже в локальных сражениях (вокруг одной из групп камней) – ещё больше.
Можно констатировать: пал бастион, который долгое время считался одним из последних примеров превосходства живого разума над машинным. Пусть программы для игры в го практически не уступают в длительности своей эволюции шахматным программам, многие специалисты утверждали, что в го машина никогда не победит игрока-человека, входящего в число сильнейших в данной дисциплине на планете.
Причина в том, что особенности игры (в сравнении с теми же шахматами) позволяют человеку сравнительно просто видеть очень длинные последовательности возможных ходов, выстраивая на этой основе хитроумные тактику и стратегию (а вот это уже совсем непросто). Но программа не может мыслить как человек, она механистична, а её выбор ответного хода — результат перебора вариантов, а не творческое решение проблемы.
Машинный разум нанёс человеку удар в гоMany Faces в версии 12.0 является официальным чемпионом мира среди программ го 2008 года. В том же чемпионате MoGo заняла второе место, а всего в нём сражались 13 программ. Many Faces работала на кластере, содержащем 32 процессора по 3,2 гигагерца.
И всё же программы стали куда ближе к людям по стилю и способу обдумывания игры. Ведь в случае с го буквальным перебором всех последующих позиций нельзя добиться ровным счётом ничего. Почему? Прежде чем вернуться к MoGo и Many Faces, нам просто необходим экскурс в историю. Для начала — в историю битвы человек-машина на шахматном поле.
"Софтинки", способные хоть как-то играть против человека, появились очень давно, но что важнее — уже в конце 1990-х были созданы программы, способные сражаться с чемпионами мира и даже выигрывать у них. Легендарная первая игра в матче Гарри Каспарова против машины (Deep Blue – Kasparov 1996) тому пример.
Чемпион, упустив эту одну игру, выиграл в том году весь матч, но через год усовершенствованная Deep Blue победила Каспарова уже окончательно (Deep Blue – Kasparov 1997).
Интуиция, опыт, знание огромного числа игр прошлого, подкреплённые образным, чисто человеческим мышлением, которое так трудно формализовать, уступили в тот раз "железке" Deep Blue, способной перебирать по 200 миллионов позиций в секунду.
Перебирать, впрочем, не тупо. Ведь общее число возможных положений фигур в шахматах колоссально, а значит, машине нужен был алгоритм, позволяющий "разумно" выбирать среди множества вариантов продолжения наиболее перспективные.
Машинный разум нанёс человеку удар в гоШахматный автомат Turk, построенный в 1770 году, был лишь мечтой о машинах, способных побороть человека в древней игре. Но хотя он являлся обманом (а играл за "турка" ловко спрятанный человек), владельцам аппарата удавалось морочить публике головы много-много лет.
Естественно, что программу компьютерщикам помогали готовить люди, досконально знающие шахматную теорию. Так что можно сказать, что в 1997 году гроссмейстер проиграл не суперкомпьютеру, но коллективному разуму множества людей, и это некоторое утешение для человечества в целом. А слабым утешением лично для Каспарова оказались ничейные матчи с двумя другими, не менее коварными программами, проведённые в 2003-м.
Вообще же после матча 1997 года новые игры сильнейших шахматистов-людей против сильнейших программ продолжились, но уже не вызывали такого высокого интереса, как раньше. В 2002 году "кремниевый шахматист" Deep Fritz сыграл с Владимиром Крамником вничью, а в 2006-м та же программа победила-таки и этого чемпиона.
Машинный разум нанёс человеку удар в гоНе представляет собой головоломки создание программы, которая играла бы как среднестатистический человек, но выигрывать у сильнейших шашистов мира — это уже задача совсем нетривиальная, несмотря на относительную простоту игры.
Примерно на равных с сильнейшими "сапиенсами" бездушные игроки научились выступать в 1990-м. Но позже компьютерным гениям удалось пойти ещё дальше, чем в шахматах. В последних у человека всегда остаётся шанс на выигрыш у машины. А вот в шашках такого шанса у нас уже нет.
В 2007 году шашки оказались полностью "взломанными", то есть были просчитаны на суперкомпьютере все их возможные ходы и комбинации. Благодаря этому последняя версия шашечной программы Chinook – она, кстати, и играла в 1990-х с чемпионом мира Мэрионом Тинсли (Marion Tinsley) – стала беспроигрышной. То есть ни один человек у неё не сможет выиграть никогда, поскольку машина в абсолютно любой позиции всегда знает самый лучший ход.
С шахматами такой "взлом" едва ли возможен в обозримом будущем. Число всех возможных позиций на шахматной доске (не противоречащих правилам, скажем, двух королей вы не можете поставить рядом) составляет ориентировочно 10^46 (в шашках порядок куда скромнее — 10^20), потому лучшие суперкомпьютеры планеты сообща не переберут их всех поочерёдно даже за время, на многие порядки превышающее возраст Вселенной.
Сможем ли мы лет через 50 нарастить производительность суперкомпьютеров на много-много порядков или придумать способ "взлома" шахмат в обход полного перебора?
Это большой вопрос. Но что уж тогда говорить об игре в го? Тут магия больших чисел просто подавляет любого, кто пытается "с линейкой" измерить глубину возможных ходов.
Машинный разум нанёс человеку удар в гоЯпонская гравюра конца XIX века "Семь дам готовят чай и играют в го".
По словам Дэвида Дошея (David Doshay) из Калифорнийского университета в Санта-Круз (UCSC), ведущего собственное исследование го и к тому же создавшего ещё одну го-программу SlugGo, число возможных конечных позиций в партии го (на стандартном поле 19 х 19) составляет 10^171. И к ним можно прийти одним из 10^1100 путей!
Это число столь велико (сравните — сумма всех элементарных частиц во Вселенной составляет "всего" 10^80), что прямой перебор всех вариантов игры абсолютно невозможен.
Но и "минимаксное" дерево поиска, которое хорошо зарекомендовало себя в шахматных программах, – в го работает плохо.
В такой стратегии компьютер перебирает все возможные ходы из данной позиции, но на конечное число ходов вперёд (в лучших программах на 12, то есть вовсе не до конца вымышленной партии, это важно). Полученные позиции оцениваются на предмет качества (выгодности).
С немногочисленными лучшими вариантами программа отыгрывает назад, снова мысленно делает ходы, но уже ведущие именно к отобранным позициям (и также ряд последующих ходов на энное число шагов), снова вычисляет все варианты получившихся состояний и опять отбирает из них несколько самых удачных. И так по кругу.
Специфика го не позволяет данному подходу давать хорошие результаты. Дерево возможных состояний на гобане (доске для го) ветвится слишком быстро. Настолько, что в отличие от шахмат быстро "забивает" способности всех современных компьютеров.
Машинный разум нанёс человеку удар в гоИсторическая родина го – Китай. Точное время появления этой игры неизвестно, но, так или иначе, случилось это ещё до нашей эры.
Как же компьютерщики нашли выход?
Создатели Many Faces, американская компания Smart Games и её лидер Дэвид Фотланд (David Fotland), воспользовались алгоритмом Monte Carlo Tree Search, то есть "Деревом поиска Монте-Карло", который был развит французскими специалистами по искусственному интеллекту в 2006-2007 годах. MoGo (а точнее, большая группа компьютерщиков из нескольких французских университетов и лабораторий, написавших эту программу) пользуется сходным же методом, хотя и отличным в деталях.
Как явствует из названия, его можно отнести к так называемым "методам Монте-Карло" (Monte Carlo method) — это общее наименование большой семьи численных методов, в которых изучаемый процесс (задача) моделируется таким образом, что решается не "в лоб", а путём просчёта конечных результатов огромного числа случайных событий.
Есть дамэ! Наша точка свободы. Постигнем гармонию через рукотворный хаос.
Самый примитивный пример. Вы хотите вычислить вероятность того, что подброшенная монетка упадёт решкой (предположим, вы не знаете, какова эта вероятность). Вместо применения формул и законов теории вероятности, рассуждений о физике движения тела, вы просто бросаете монетку десять тысяч раз и, подсчитав число событий, обнаруживаете, что искомый ответ — ровно 50%.
На деле же самые разнообразные вариации метода Монте-Карло применяют для моделирования куда более сложных вещей: динамики молекулярных систем, поведения квантовых частиц или даже социальных процессов. А разработан был этот метод (в целом) в Лос-Аламосе, в ходе работ над атомной бомбой.
А как он заработал в го? Программы-победители, стартуя из имеющейся позиции, сначала перебирают случайным образом несколько миллионов игр, которые могут быть сыграны из этого положения. Число большое, но вполне конечное. Причём каждую игру машина проигрывает до конца, совершенно не заботясь о разумности или выгодности ходов, как своих, так и виртуального визави (лишь бы правила не нарушались).
Машинный разум нанёс человеку удар в гоНаибольшей популярностью го пользуется в Корее, Китае, Тайване и Японии. Там же живут сильнейшие игроки мира. Как герой фильма "Мастер Го", кадр из которого вы видите.
Получив запись ходов для каждой игры из этих миллионов, программа составляет статистику – какие первые ходы с большей вероятностью ведут к выигрышу. Помните пример с монетой? Вы бросали её без системы, но, посмотрев на большое число результатов, установили, что вероятность выпадения одной стороны равна 50%.
Скажете – ко – вы повторяетесь! Но в программах го дело обстоит схожим образом.
По статистике миллионов совершенно безумных, хаотичных игр, в которых машина не "думала" над ходами, но игр просчитанных до конца, программа устанавливает, что следующий ход такой-то приведёт к выигрышу с вероятностью, скажем, 3%, такой-то — 1,5%, а вот этот – 0,02% и так далее. А ведь возможных ходов даже на чистом поле го (19 х 19) – всего 361, а на частично заполненном – куда меньше.
Далее компьютер просто выбирает ход с наибольшей вероятностью выигрыша и проверяет ещё несколько миллионов игр уже из нового положения. Это позволяет уточнить вероятность победы, в конечном счёте сделав выбор – какой ход следует произвести в реальной игре с человеком.
Роберт Хирн (Robert Hearn), математик и компьютерщик из Дартмутского колледжа, а также – сильный игрок в го, прогнозирует, что пройдёт менее 30 лет, и программы (главным образом за счёт роста мощности суперкомпьютеров) начнут обыгрывать в го лучших профи даже без гандикапа. Арпад Риммель (Arpad Rimmel), один из авторов MoGo, оценивает этот срок и вовсе в 10 лет.
Но это не приблизит нас к разгадке того, как мыслит человек, играющий в го. Он-то не перебирает миллионы ходов.
Машинный разум нанёс человеку удар в гоTaiwan Open 2009: слева – игрок первого дана Личэнь Чиэнь, в центре – один из устроителей состязания Чаншин Ли (Chang-Shing Lee), справа – Арпад Риммель.
"Удивлением, загадкой для меня является то, что эти алгоритмы работают", — говорит Хирн, комментируя новые достижения MoGo и Many Faces. Поясним: даже сами авторы этих программ прекрасно знают – как они работают, но при этом не знают – почему это срабатывает.
У человека за выбор хода в го отвечает интуиция, помноженная на распознавание образов. Работает визуальная аналогия (эта форма группы влияет на эту часть доски, эта конфигурация опасна, и так далее). Человек мыслит категориями жизни, эволюции и смерти групп камней на доске. Он узнаёт знакомые конфигурации, даже если они лишь близки к когда-то виденным. Он учится обобщать образы (вот камни выстроены в цепочку, вот кольцо с разрывом на боку, вот ещё что-то). Образность и помогает человеку принимать решения за разумное время.
Майкл Атертон (Michael Atherton) и его коллеги из университета Миннесоты (University of Minnesota) однажды просканировали мозги игроков в шахматы и го в процессе этих игр. Выяснилось, что у игроков го особенно сильно активировались теменные доли, отвечающие за обработку восприятия пространственного положения объектов.
Сходные японские опыты показали также, что у игроков-профи к концу игры сильно активируются и регионы, отвечающие за восприятие положения тела и за движения.
Атертон всё это обобщил так: "Игроки в го упрощают дерево поиска решений до эстетического чувства. У них есть чувство игры".
Потому наше очень даже скромное число нейронов легко справляется с тем, на что компьютеру, даже с новым "монте-карловским" подходом, требуются тонны чипов и терафлопы производительности.
Этикет го предусматривает спокойное и сдержанное поведение во время игры. Вот мы и говорим: спокойно, у нас всё ещё есть преимущество перед машинами.
Так произошёл ли прорыв? Нет, перед нами только фусэки. "Люди думают — как же далеко мы уже зашли, — говорит Дошей. — Но в действительности мы только начали программировать компьютеры".
Да и вообще их поражающая мир поступь в значительной мере, — лишь иллюзия. Ведь за каждой программой стоят люди, её написавшие. А значит, в общем матче со своими детищами мы сохраняем сэнтэ и всегда сможем позволить себе дать машинам "фору в семь камней".
