Фора в семь камней и соперник девятого про-дана вам о чём-то говорят? Нам тоже. Между тем речь идёт о старейшей игре в мире, ведущейся на доске. И мир взбудоражен: программы смогли побороть профессиональных игроков самого высокого уровня. За результатом, который интересен, казалось бы, только фанатам, стоит колоссальный труд в области искусственного интеллекта. Мы сдаём "кремнию"?
Китайские легенды датируют рождение го началом второго тысячелетия до нашей эры. Эта древняя игра, пожалуй, даже более сложна, чем шахматы. Уж для машинного интеллекта она определённо сложнее. Тем ярче достижение компьютерщиков.
В феврале на престижном турнире по го Taiwan Open 2009 компьютерная программа MoGo обыграла двух профессионалов в битве на гобане 19 х 19. С гандикапом в 7 камней она победила игрока девятого дана Дзюньсюнь Чжоу (Jun-Xun Zhou), а с форой в 6 камней сломила сопротивление игрока первого дана Личэнь Чиэня (Li-Chen Chien).
Девятый дан, заметим, это предел мастерства, профи высшей пробы. Учитывая фору, данную машине, можно сказать, что она выступила на уровне если не профессионала, то самого сильного любителя.
Существует несколько вариаций правил го (японские, китайские, американской ассоциации го и ряд других). Отличаются они в деталях, касающихся применения форы, ряда правил, действующих в ходе игры, и также подсчёта очков в конце сражения, а ещё – правилами определения ранга игроков.
Ранги (кю и даны) влияют на начальные условия игры: если встречаются соперники разного уровня, слабому даётся фора в виде нескольких камней, которые тот выкладывает на доску до первого хода противника.
В основном считается, что разница в ранге на одну единицу компенсируется одним камнем гандикапа, но в Китае, Японии и Корее в ранжировании профессиональных игроков предполагается, что разница в один дан соответствует только трети камня форы, то есть уровни мастерства идут плотнее. И это впечатляющее достижение. Лет пять назад программы го могли уверенно выигрывать исключительно у детишек, недавно приступивших к изучению этой мудрой стратегической игры. С обычными любителями те же программы играли на равных, ну а профессионалам машины бесславно "сливали", даже имея гандикап в 25 камней.
И ещё год-полтора назад уровень программ оставался сравнительно скромным. Несколько случаев побед машин в отдельных партиях над суперпрофи имели место при большем (чем в 2009-м) гандикапе, либо при играх на уменьшенном поле (9 х 9).
Основные правила го не столь уж сложны. Упрощённо говоря, задача игроков сводится к окружению камней противника своими камнями. Но игра эта обладает большой "глубиной" – вариантов действий в ответ на ходы соперника – огромное количество, а вариантов тактики даже в локальных сражениях (вокруг одной из групп камней) – ещё больше. Можно констатировать: пал бастион, который долгое время считался одним из последних примеров превосходства живого разума над машинным. Пусть программы для игры в го (Computer Go, смотрите также computer-go.info) практически не уступают в длительности своей эволюции шахматным программам, многие специалисты утверждали, что в го машина никогда не победит игрока-человека, входящего в число сильнейших в данной дисциплине на планете.
Причина в том, что особенности игры (в сравнении с теми же шахматами) позволяют человеку сравнительно просто видеть очень длинные последовательности возможных ходов, выстраивая на этой основе хитроумные тактику и стратегию (а вот это уже совсем непросто). Но программа не может мыслить как человек, она механистична, а её выбор ответного хода — результат перебора вариантов, а не творческое решение проблемы.
"Софтинки", способные хоть как-то играть против человека, появились очень давно, но что важнее — уже в конце 1990-х были созданы программы, способные сражаться с чемпионами мира и даже выигрывать у них. Легендарная первая игра в матче Гарри Каспарова против машины (Deep Blue – Kasparov 1996) тому пример.
Чемпион, упустив эту одну игру, выиграл в том году весь матч, но через год усовершенствованная Deep Blue победила Каспарова уже окончательно (Deep Blue – Kasparov 1997).
Интуиция, опыт, знание огромного числа игр прошлого, подкреплённые образным, чисто человеческим мышлением, которое так трудно формализовать, уступили в тот раз "железке" Deep Blue, способной перебирать по 200 миллионов позиций в секунду.
Перебирать, впрочем, не тупо. Ведь общее число возможных положений фигур в шахматах колоссально, а значит, машине нужен был алгоритм, позволяющий "разумно" выбирать среди множества вариантов продолжения наиболее перспективные.
Шахматный автомат Turk, построенный в 1770 году, был лишь мечтой о машинах, способных побороть человека в древней игре. Но хотя он являлся обманом (а играл за "турка" ловко спрятанный человек), владельцам аппарата удавалось морочить публике головы много-много лет (иллюстрация с сайта wikipedia.org).
Естественно, что программу компьютерщикам помогали готовить люди, досконально знающие шахматную теорию. Так что можно сказать, что в 1997 году гроссмейстер проиграл не суперкомпьютеру, но коллективному разуму множества людей, и это некоторое утешение для человечества в целом. А слабым утешением лично для Каспарова оказались ничейные матчи с двумя другими, не менее коварными программами, проведённые в 2003-м.
Вообще же после матча 1997 года новые игры сильнейших шахматистов-людей против сильнейших программ продолжились, но уже не вызывали такого высокого интереса, как раньше. В 2002 году "кремниевый шахматист" Deep Fritz сыграл с Владимиром Крамником вничью, а в 2006-м та же программа победила-таки и этого чемпиона.
Примерно на равных с сильнейшими "сапиенсами" бездушные игроки научились выступать в 1990-м. Но позже компьютерным гениям удалось пойти ещё дальше, чем в шахматах. В последних у человека всегда остаётся шанс на выигрыш у машины. А вот в шашках такого шанса у нас уже нет.
В 2007 году шашки оказались полностью "взломанными", то есть были просчитаны на суперкомпьютере все их возможные ходы и комбинации. Благодаря этому последняя версия шашечной программы Chinook – она, кстати, и играла в 1990-х с чемпионом мира Мэрионом Тинсли (Marion Tinsley) – стала беспроигрышной. То есть ни один человек у неё не сможет выиграть никогда, поскольку машина в абсолютно любой позиции всегда знает самый лучший ход.
С шахматами такой "взлом" едва ли возможен в обозримом будущем. Число всех возможных позиций на шахматной доске (не противоречащих правилам, скажем, двух королей вы не можете поставить рядом) составляет ориентировочно 10^46 (в шашках порядок куда скромнее — 10^20), потому лучшие суперкомпьютеры планеты сообща не переберут их всех поочерёдно даже за время, на многие порядки превышающее возраст Вселенной.
Сможем ли мы лет через 50 нарастить производительность суперкомпьютеров на много-много порядков или придумать способ "взлома" шахмат в обход полного перебора?
Это большой вопрос. Но что уж тогда говорить об игре в го? Тут магия больших чисел просто подавляет любого, кто пытается "с линейкой" измерить глубину возможных ходов.
По словам Дэвида Дошея (David Doshay) из Калифорнийского университета в Санта-Круз (UCSC), ведущего собственное исследование го и к тому же создавшего ещё одну го-программу SlugGo, число возможных конечных позиций в партии го (на стандартном поле 19 х 19) составляет 10^171. И к ним можно прийти одним из 10^1100 путей!
Это число столь велико (сравните — сумма всех элементарных частиц во Вселенной составляет "всего" 10^80), что прямой перебор всех вариантов игры абсолютно невозможен.
Историческая родина го – Китай. Точное время появления этой игры неизвестно, но, так или иначе, случилось это ещё до нашей эры.
Наибольшей популярностью го пользуется в Корее, Китае, Тайване и Японии. Там же живут сильнейшие игроки мира. Получив запись ходов для каждой игры из этих миллионов, программа составляет статистику – какие первые ходы с большей вероятностью ведут к выигрышу.
У человека за выбор хода в го отвечает интуиция, помноженная на распознавание образов. Работает визуальная аналогия (эта форма группы влияет на эту часть доски, эта конфигурация опасна, и так далее). Человек мыслит категориями жизни, эволюции и смерти групп камней на доске. Он узнаёт знакомые конфигурации, даже если они лишь близки к когда-то виденным. Он учится обобщать образы (вот камни выстроены в цепочку, вот кольцо с разрывом на боку, вот ещё что-то). Образность и помогает человеку принимать решения за разумное время.
