истории

Эта машина умнее меня В каких играх человек уже никогда не победит компьютер

Источник: Meduza

В конце 2015-го — начале 2016-го компьютерные программы оказались способнее людей в игре го и в скорости собирания кубика Рубика. По просьбе «Медузы» журналист Владислав Воронин рассказывает, в каких играх человек уже никогда не сможет выиграть у компьютера. 

Отелло (реверси)

Игра «Отелло» стала популярной в начале 1970-х. Правила простые: два игрока свободно размещают фишки разных цветов на площадке из 64 клеток (8×8). Задача — закрыть с двух сторон сплошные ряды соперника (горизонтальные, вертикальные и диагональные) своими фишками. Как только ряд оказывается заблокированным, все фишки в нем переходят оппоненту и меняют цвет. Выигрывает тот, кто к концу партии занял большую территорию.

Во время первого поединка человека с компьютером в 1980 году уверенно победил действующий чемпион мира по «Отелло» Хироси Иноуе: из шести партий он уступил программе Moor только одну (5:1). Всего через девять лет компьютеры взяли реванш в командном турнире в Лондоне. Пять программ обыграли пятерых профессиональных игроков (трое из них входили в мировой топ-4) со скромным счетом 12:8.

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

Уже в 1997 году стало ясно, что даже сильнейшим игрокам бессмысленно тягаться с компьютерами: чемпион мира Такеси Мураками проиграл программе Logistello с унизительным счетом 0:6.

Нарды

Компьютеры научились играть в нарды еще в 1970-е, но этого бы точно не произошло без влияния шахмат. Для разработчиков суперкомпьютеров, способных бороться с шахматными гроссмейстерами, эта игра оказалась небольшим промежуточным этапом. Например, чемпион мира по шахматам по переписке Ханс Берлинер с помощью нард придумал алгоритм оценки ситуации на игровой доске (компьютер анализирует текущую ситуацию на доске и просматривает древо игры на несколько ходов вперед, чтобы выбрать оптимальное продолжение); позже это помогло ему написать шахматную программу HiTech, которая в 1988-м одолела гроссмейстера Арнольда Денкера.

Для нард Берлинер разработал программу BKG 9.8, в 1979-м она обыграла действующего чемпиона мира Луиджи Виллу со счетом 7:1. Победа была крайне неожиданной, даже создатель компьютера признал, что человек действовал талантливее и стабильнее — система восемь раз выбирала не лучшие варианты продолжения игры. Но, во-первых, BKG 9.8 несколько раз повезло с числами, выпавшими на костях, во-вторых, программа очень успешно делала выбор в пользу удвоения ставок (каждая игра начинается со ставкой в одно очко; при желании во время игры каждый участник может удвоить ставку — второй должен либо принять это удвоение, либо сдаться и проиграть одно очко, не рискуя двумя).

Позже метод Берлинера (анализ ситуации на игровом поле) был усовершенствован. Работа швейцарской программы Snowy и финской Jellyfish основывается на искусственных нейронных сетях, которые запоминают ходы лучших игроков и применяют их в случае необходимости. Правда, после поражения Виллы никто из чемпионов не решился сразиться с компьютером.

Шахматы

Компания IBM интересовалась шахматными системами с начала 1950-х, но из-за сложности игры разработка отнимала очень много времени. Только через 30 с небольшим лет ученые задумались о проекте мощного компьютера Deep Blue. Выставить его против действующего чемпиона мира Гарри Каспарова получилось в 1996 году.

Тот матч из шести партий Каспаров выиграл (3 победы, 2 ничьи, 1 поражение), он был уверен, что эпоха машин наступит нескоро: «Хотя я и видел некоторые признаки интеллекта, у компьютера все-таки была неэффективная и негибкая манера игры. Это позволяет мне думать, что у меня есть несколько лет в запасе», — писал он в журнале Time. 

Однако Каспаров ошибался. Разработчики быстро увеличили мощность системы — теперь она могла оценивать 200 миллионов позиций в секунду. В 1997-м Deep Blue победил в матче-реванше (2 победы, 3 ничьих, 1 поражение) и стал первым компьютером, одолевшим сильнейшего шахматиста мира. Отыграться Каспаров уже не смог, потому что IBM отказалась от дальнейших соревнований, посчитав миссию выполненной.

С тех пор компьютеры становились только сильнее. Рейтинг Эло (метод расчета относительной силы игроков в играх для двоих) самой сильной шахматной программы Stockfish составляет 3341 пункт. Показатели людей существенно ниже: у Каспарова на пике был 2851 пункт, у нынешнего лидера Магнуса Карлсена — 2850,6. 

Го

Древняя игра, придуманная в Китае более двух с половиной тысяч лет назад, казалась для компьютеров непреодолимым препятствием, пока за разработку не взялся Google. На первый взгляд, в го нет ничего особенно сложного: два игрока по очереди расставляют на площадке (19×19) белые и черные камни; побеждает тот, кто захватит большую территорию. В конце считаются камни, составляющие границу одного цвета, и свободные клетки за «стеной», куда можно беспрепятственно добавить другие камни. У кого сумма больше, тот выиграл.

Сложности в разнообразии вариантов. Например, в шахматах у каждого игрока есть 20 способов начать партию, а после первого хода на доске может быть 400 различных позиций. В го — 361 вариант стартового хода и 129 960 возможных комбинаций только после первого раунда. Это невероятно затрудняет работу систем искусственного интеллекта, которые опираются на стандартные алгоритмы и базы данных.

Поэтому система AlphaGo, разработанная под контролем Google, сочетает два подхода — так называемое «дерево вариантов» и глубокие нейронные сети, которые натренированы 30 миллионами ходов самых сильных игроков в го и тысячами партий внутри системы. Сейчас AlphaGo в 57% случаев предсказывает действия человека.

При тестировании AlphaGo уничтожила самые прогрессивные компьютерные го-системы, выиграв у них 499 партий из 500. Потом наступило время встретиться с человеком, и в октябре 2015-го AlphaGo разгромила трехкратного чемпиона Европы Фань Хуэя со счетом 5:0. Это первая победа компьютера над профессиональным игроком в го — до этого ни одна программа не поднималась выше любительского уровня.

Чтобы окончательно покорить го, AlphaGo осталось доказать силу в матче с сильнейшим игроком мира Ли Седолем. Встреча назначена на март.

Кубик Рубика

В январе изобретатели Джей Флэтлэнд и Пол Роуз представили робота, который может собрать кубик Рубика всего за секунду. Это космический уровень даже для компьютерных систем — раньше ни одной из них не удавалось справиться с головоломкой менее чем за 3,253 секунды. Лучший результат Флэтлэнда и Роуза — 1,047 секунды.

Машина работает с немного модифицированным кубиком Рубика: на каждой грани в центре высверлены дырки, за которые держатся шаговые электродвигатели. При помощи четырех веб-камер компьютер оценивает текущую раскладку кубика и определяет оптимальную последовательность действий на основе алгоритма Коцембы (решение не более чем за 20 ходов).

Лучший результат среди людей в ноябре 2015-го показал 14-летний американец Лукас Эттер — 4,904 секунды.

Шашки

Сказочная история американца Мариона Тинсли, который проиграл соперникам в чекерс (разновидность шашек) всего пять партий, завершилась встречей с компьютером. Он был чемпионом мира на протяжении всей карьеры с 1955-го по 1991-й; с перерывом на 17 лет, когда пропускал все турниры.

Систему для игры в чекерс разработали в канадском Альбертском университете. Машина весила около 540 килограмм и за минуту могла обработать 12 миллионов различных игровых вариантов. В 1992 году Chinook заслужила встречу с Тинсли, но матч остался за человеком: 4 поражения программы, 2 победы, 33 ничьих. Интересно, что один раз программа проиграла только из-за технических проблем — компьютер просто завис, и разработчикам пришлось сдаться. 

Уже в 1994-м состоялся матч-реванш. В первых шести партиях были сплошные ничьи, а потом Тинсли снялся из-за проблем со здоровьем — победа автоматически досталась компьютеру. Через неделю у чемпиона нашли рак; менее чем через год он умер.

Компьютеры с тех пор набрали такую силу, что люди вряд ли будут с ними соревноваться. В 2007 году в Канаде объявили о создании идеальной системы, которая вообще не может проиграть. Даже если ее соперник проведет безупречный матч, ему достанется в лучшем случае ничья. Программа проанализировала все возможные варианты развития игры и знает идеальный ход в каждой ситуации. 

Скрэббл 

Скрэббл, известный в России как «Эрудит», был покорен компьютером с первой попытки. В 2006 году в Торонто робот Quackle обыграл чемпиона мира Дэвида Бойса. 

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

Прежде чем сразиться с компьютером, Бойс в специальном турнире обошел 100 других желающих. Уступив роботу, он с расстройством отметил, что «по-прежнему лучше быть человеком, чем компьютером». 

Quackle доступна в интернете, так что вы тоже можете посоревноваться. 

Телевикторина

Компания IBM, которая разработала суперкомпьютер, обыгравший Гарри Каспарова, в 2011 году снова удивила человечество — на этот раз в интеллектуальной телевикторине Jeopardy! (российский аналог — «Своя игра»). Робот Watson не оставил никаких шансов двум рекордсменам: Кену Дженнингсу, который в свое время не проигрывал на протяжении 74 выпусков передачи, и Брэду Руттеру, получившему самый большой выигрыш в истории шоу — 4,45 миллиона долларов.

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

По сумме двух игр Watson правильными ответами заработал 77 тысяч долларов, более чем втрое обогнав каждого соперника — 24 тысячи у Дженнингса и 21 600 — у Руттера.

В результате IBM выиграла миллион долларов. Все деньги были направлены на благотворительность.