В конце 2015-го — начале 2016-го компьютерные программы оказались способнее людей в игре го и в скорости собирания кубика Рубика. В каких играх человек уже никогда не сможет победить у компьютера.
Игра «Отелло» стала популярной в начале 1970-х. Правила простые: два игрока свободно размещают фишки разных цветов на площадке из 64 клеток (8×8). Задача — закрыть с двух сторон сплошные ряды соперника (горизонтальные, вертикальные и диагональные) своими фишками. Как только ряд оказывается заблокированным, все фишки в нем переходят оппоненту и меняют цвет. Выигрывает тот, кто к концу партии занял большую территорию.
Во время первого поединка человека с компьютером в 1980 году уверенно победил действующий чемпион мира по «Отелло» Хироси Иноуе: из шести партий он уступил программе Moor только одну (5:1). Всего через девять лет компьютеры взяли реванш в командном турнире в Лондоне. Пять программ обыграли пятерых профессиональных игроков (трое из них входили в мировой топ-4) со скромным счетом 12:8.
Со временем в компьютеры была помещена информация обо всех возможных положениях фишек, и машины стали просчитывать игру примерно на 25 ходов вперед — по сути, появилась мощнейшая стратегия без слабых мест.
Уже в 1997 году стало ясно, что даже сильнейшим игрокам бессмысленно тягаться с компьютерами: чемпион мира Такеси Мураками проиграл [2] программе Logistello с унизительным счетом 0:6.
Компьютеры научились играть в нарды еще в 1970-е, но этого бы точно не произошло без влияния шахмат. Для разработчиков суперкомпьютеров, способных бороться с шахматными гроссмейстерами, эта игра оказалась небольшим промежуточным этапом.
Например, чемпион мира по шахматам по переписке Ханс Берлинер с помощью нард придумал алгоритм оценки ситуации на игровой доске (компьютер анализирует текущую ситуацию на доске и просматривает древо игры на несколько ходов вперед, чтобы выбрать оптимальное продолжение); позже это помогло ему написать шахматную программу HiTech, которая в 1988-м одолела гроссмейстера Арнольда Денкера.
Для нард Берлинер разработал программу BKG 9.8, в 1979-м она обыграла действующего чемпиона мира Луиджи Виллу со счетом 7:1. Победа была крайне неожиданной, даже создатель компьютера признал, что человек действовал талантливее и стабильнее — система восемь раз выбирала [3] не лучшие варианты продолжения игры.
Но, во-первых, BKG 9.8 несколько раз повезло с числами, выпавшими на костях, во-вторых, программа очень успешно делала выбор в пользу удвоения ставок (каждая игра начинается со ставкой в одно очко; при желании во время игры каждый участник может удвоить ставку — второй должен либо принять это удвоение, либо сдаться и проиграть одно очко, не рискуя двумя).
Позже метод Берлинера (анализ ситуации на игровом поле) был усовершенствован. Работа швейцарской программы Snowy и финской Jellyfish основывается на искусственных нейронных сетях, которые запоминают ходы лучших игроков и применяют их в случае необходимости. Правда, после поражения Виллы никто из чемпионов не решился сразиться с компьютером.
В тему: Развитие технологий до 2099 года - прогноз [4]
Компания IBM интересовалась шахматными системами с начала 1950-х, но из-за сложности игры разработка отнимала очень много времени. Только через 30 с небольшим лет ученые задумались о проекте мощного компьютера Deep Blue. Выставить его против действующего чемпиона мира Гарри Каспарова получилось в 1996 году.
Тот матч из шести партий Каспаров выиграл (3 победы, 2 ничьи, 1 поражение), он был уверен, что эпоха машин наступит нескоро: «Хотя я и видел некоторые признаки интеллекта, у компьютера все-таки была неэффективная и негибкая манера игры. Это позволяет мне думать, что у меня есть несколько лет в запасе», — писал [5] он в журнале Time.
Матч-реванш между Гарри Каспаровым и Deep Blue. 5 мая 1997 года. Фото: Najlah Feanny / Corbis SABA / Vida Press
Однако Каспаров ошибался. Разработчики быстро увеличили мощность системы — теперь она могла оценивать 200 миллионов позиций в секунду. В 1997-м Deep Blue победил в матче-реванше (2 победы, 3 ничьих, 1 поражение) и стал первым компьютером, одолевшим сильнейшего шахматиста мира. Отыграться Каспаров уже не смог, потому что IBM отказалась от дальнейших соревнований, посчитав миссию выполненной.
С тех пор компьютеры становились [6] только сильнее. Рейтинг Эло (метод расчета относительной силы игроков в играх для двоих) самой сильной шахматной программы Stockfish составляет 3341 пункт. Показатели людей существенно ниже [7]: у Каспарова на пике был 2851 пункт, у нынешнего лидера Магнуса Карлсена — 2850,6.
Древняя игра, придуманная в Китае более двух с половиной тысяч лет назад, казалась для компьютеров непреодолимым препятствием, пока за разработку не взялся Google. На первый взгляд, в го нет ничего особенно сложного: два игрока по очереди расставляют на площадке (19×19) белые и черные камни; побеждает тот, кто захватит большую территорию. В конце считаются камни, составляющие границу одного цвета, и свободные клетки за «стеной», куда можно беспрепятственно добавить другие камни. У кого сумма больше, тот выиграл.
Сложности в разнообразии вариантов. Например, в шахматах у каждого игрока есть 20 способов начать партию, а после первого хода на доске может быть 400 различных позиций. В го — 361 вариант стартового хода и 129 960 возможных комбинаций только после первого раунда. Это невероятно затрудняет работу систем искусственного интеллекта, которые опираются на стандартные алгоритмы и базы данных.
Поэтому система AlphaGo, разработанная под контролем Google, сочетает два подхода — так называемое «дерево вариантов» и глубокие нейронные сети, которые натренированы 30 миллионами ходов самых сильных игроков в го и тысячами партий внутри системы. Сейчас AlphaGo в 57% случаев предсказывает действия человека.
При тестировании AlphaGo уничтожила самые прогрессивные компьютерные го-системы, выиграв у них 499 партий из 500. Потом наступило время встретиться с человеком, и в октябре 2015-го AlphaGo разгромила трехкратного чемпиона Европы Фань Хуэя со счетом 5:0. Это первая победа компьютера над профессиональным игроком в го — до этого ни одна программа не поднималась выше любительского уровня.
Чтобы окончательно покорить го, AlphaGo осталось доказать силу в матче с сильнейшим игроком мира Ли Седолем. Встреча назначена [8] на март.
В январе изобретатели Джей Флэтлэнд и Пол Роуз представили робота, который может собрать кубик Рубика всего за секунду. Это космический уровень даже для компьютерных систем — раньше ни одной из них не удавалось справиться с головоломкой менее чем за 3,253 секунды. Лучший результат [9] Флэтлэнда и Роуза — 1,047 секунды.
Машина работает с немного модифицированным кубиком Рубика: на каждой грани в центре высверлены дырки, за которые держатся шаговые электродвигатели. При помощи четырех веб-камер компьютер оценивает текущую раскладку кубика и определяет оптимальную последовательность действий на основе алгоритма Коцембы (решение не более чем за 20 ходов).
Лучший результат среди людей в ноябре 2015-го показал [10] 14-летний американец Лукас Эттер — 4,904 секунды.
В тему: Мозг обманывает человека [11]
Сказочная история американца Мариона Тинсли, который проиграл соперникам в чекерс (разновидность шашек) всего пять партий, завершилась встречей с компьютером. Он был чемпионом мира на протяжении всей карьеры с 1955-го по 1991-й; с перерывом на 17 лет, когда пропускал все турниры.
Систему для игры в чикерс разработали в канадском Альбертском университете. Машина весила около 540 килограмм и за минуту могла обработать 12 миллионов различных игровых вариантов. В 1992 году Chinook заслужила встречу с Тинсли, но матч остался за человеком: 4 поражения программы, 2 победы, 33 ничьих. Интересно, что один раз программа проиграла только из-за технических проблем — компьютер просто завис [12], и разработчикам пришлось сдаться.
Уже в 1994-м состоялся матч-реванш. В первых шести партиях были сплошные ничьи, а потом Тинсли снялся из-за проблем со здоровьем — победа автоматически досталась компьютеру. Через неделю у чемпиона нашли рак; менее чем через год он умер.
Компьютеры с тех пор набрали такую силу, что люди вряд ли будут с ними соревноваться. В 2007 году в Канаде объявили о создании идеальной системы, которая вообще не может проиграть. Даже если ее соперник проведет безупречный матч, ему достанется в лучшем случае ничья. Программа проанализировала [13] все возможные варианты развития игры и знает идеальный ход в каждой ситуации.
Скрэббл, известный в России как «Эрудит», был покорен компьютером с первой попытки. В 2006 году в Торонто робот Quackle обыграл чемпиона мира Дэвида Бойса.
В двух стартовых партиях программа уступила — чтобы обыграть человека, потребовалось брать три следующие, используя необычные слова вроде «кади» (судья, рассматривающий дела на основе шариата) и «анурия» (отсутствие поступления мочи в мочевой пузырь).
Прежде чем сразиться с компьютером, Бойс в специальном турнире обошел 100 других желающих. Уступив роботу, он с расстройством отметил [14], что «по-прежнему лучше быть человеком, чем компьютером».
Quackle доступна [15] в интернете, так что вы тоже можете посоревноваться.
Компания IBM, которая разработала суперкомпьютер, обыгравший Гарри Каспарова, в 2011 году снова удивила человечество — на этот раз в интеллектуальной телевикторине Jeopardy! (российский аналог — «Своя игра»). Робот Watson не оставил никаких шансов двум рекордсменам: Кену Дженнингсу, который в свое время не проигрывал на протяжении 74 выпусков передачи, и Брэду Руттеру, получившему самый большой выигрыш в истории шоу — 4,45 миллиона долларов.
Кен Дженнингс, робот Watson и Брэд Руттер на телевикторине Jeopardy! 13 января 2011 года. Фото: Seth Wenig / AP / Scanpix
Робот распознавал речь ведущего, анализировал вопрос и искал ответ в базе данных. Компьютер не был подключен к интернету и не мог пользоваться сторонними сервисами, в его распоряжении были только 200 миллионов страниц контента по самым разным темам, в том числе полный архив википедии.
По сумме двух игр Watson правильными ответами заработал [16] 77 тысяч долларов, более чем втрое обогнав каждого соперника — 24 тысячи у Дженнингса и 21 600 — у Руттера.
В результате IBM выиграла миллион долларов. Все деньги были направлены на благотворительность.
—
Владислав Воронин, опубликовано в издании MEDUZA [17]
В тему:
Ссылки:
[1] https://argumentua.com/stati/obshchestvo/obrazovanie
[2] https://chessprogramming.wikispaces.com/Michael+Buro
[3] http://www.bkgm.com/rgb/rgb.cgi?view+782
[4] http://argumentua.com/stati/razvitie-tekhnologii-do-2099-goda-prognoz
[5] http://content.time.com/time/magazine/article/0,9171,984305,00.html#ixzz1DyffA0Dl
[6] http://www.computerchess.org.uk/ccrl/4040/
[7] http://www.2700chess.com/
[8] https://googleblog.blogspot.ru/2016/01/alphago-machine-learning-game-go.html
[9] https://www.youtube.com/watch?v=ixTddQQ2Hs4
[10] https://www.youtube.com/watch?v=EsssqCMfUMY
[11] http://argumentua.com/stati/mozg-obmanyvaet-cheloveka
[12] http://web.archive.org/web/20060829085713/http://www.math.wisc.edu/~propp/chinook.html
[13] http://news.bbc.co.uk/2/hi/science/nature/6907018.stm
[14] http://chronicle.com/blogs/wiredcampus/a-computer-program-wins-its-first-scrabble-tournament/2800
[15] http://people.csail.mit.edu/jasonkb/quackle/
[16] http://www.theatlantic.com/technology/archive/2011/02/is-it-time-to-welcome-our-new-computer-overlords/71388/
[17] https://meduza.io/feature/2016/02/07/eta-mashina-umnee-menya
[18] http://argumentua.com/stati/ivo-shlaus-bog-taki-igraet-v-kosti-ili-zhe-my-na-samom-dele-ne-znaem-znachenie-slova-igra
[19] http://argumentua.com/novosti/tsukerberg-zanyalsya-razrabotkoi-domashnego-robota
[20] http://argumentua.com/stati/tiago-forte-budushchee-budet-strannym