Шах и код: история компьютеров-шахматистов и шахматистов-компьютеров

5 832 просмотра
Об авторе

Шахматы

Компьютеры произвели революцию в области шахмат — и лучшие шахматные программы практически невозможно обыграть. Но может ли игрок, состоящий отчасти из человека и отчасти из компьютера, быть еще сильнее? Все началось в 1968 году с простого спора. 23-летний шотландский чемпион мира по шахматам Дэвид Леви был на вечеринке. Коктейлями угощал Дональд Мичи, основатель отделения машинного интеллекта и восприятия Эдинбургского университета. Рядом с Леви на диванчике сидел Джон Маккарти, американец, который в 1955 году придумал термин «искусственный интеллект».

Они мило беседовали, и ради забавы Маккарти предложил Леви сыграть партию в шахматы прямо здесь и сейчас. Леви обыграл его довольно просто. Маккарти, впрочем, предложил заключить пари. Компьютеры смогут обыграть чемпиона вроде Леви через 10 лет, сказал он. Леви отшучивался, но Маккарти стоял на своем. Поэтому Леви принял пари и поставил 500 фунтов стерлингов — в современном эквиваленте порядка 12 000 долларов — которые отошли бы Маккарти, если бы компьютер обыграл Леви до 1979 года.

«Тогда я получал 895 фунтов стерлингов в год, — вспоминает сейчас Леви. — Но я был так уверен».

Шахматы

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

Леви сделал ставку во времена, когда темпы улучшения вычислений были высокими. Несмотря на его уверенность в обратном, было множество людей вроде Маккарти, которые думали, что машина сможет его победить.

В 1978 году Леви оказался в Торонто, играя с компьютерным соперником в матче, который стал важной вехой в истории шахматного программирования. Он сыграл пять игр против оппонента. Первая окончилась вничью, но вторую и третью он выиграл. И затем проиграл четвертую. Если бы компьютер выиграл последнюю партию, серия закончилась бы вничью, но Леви упорствовал — и победил.

И продолжал побеждать. С момента согласования первоначальной ставки с Маккарти, его не могли победить компьютеры в выставочных матчах в течение 21 года. И только в 1989 году, во время матча, организованного Британским компьютерным сообществом в Лондоне, Леви был, наконец, свергнут программой под названием Deep Thought. Меньше чем через 10 лет, в 1997 году, суперкомпьютер IBM Deep Blue первым в истории одолел действующего чемпиона мира — Гарри Каспарова — в турнирной игре. Скоро об этом достижении узнал весь мир.

Но даже к 1989 году компьютеры уже преуспевали в играх против гроссмейстеров, и Леви знал, что его непобедимая полоса не продлится вечно. За все годы своей практики он разработал несколько «противокомпьютерных тактик», которые ему помогали. Они не предоставляли никаких преимуществ в игре против человек, но могли дать игроку перевес против компьютерного соперника.

Гарри Каспаров

«Я называл это «делай ничего, но делай это хорошо», — вспоминает он. — Я словно сидел на месте, делая движения, которые понемногу улучшали мою позицию. Компьютер не мог понять, каким был мой план в долгосрочной перспективе.

«Прорвись и раздави»

В те дни шахматные компьютерные программы могли продумывать лишь ограниченное количество ходов наперед, пять или шесть. Леви тянул свое время и искал возможности, которые могли бы позволить ему взять инициативу на себя.

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

И все же противокомпьютерные тактики не стали неактуальными после 1989 или даже после 1997 года. Борис Альтерман, израильский гроссмейстер, прославился после серии матчей против компьютеров в 90-х и начале 2000-х, подобной стратегией «Стены Альтермана». Он играл от обороны, прячась за рядом пешек, зная, что чем больше фигур на доске, тем сложнее компьютеру рассчитать преимущество из-за большого количества возможных ходов, которые нужно рассмотреть.

«Я бы сказал, что это одна из лучших тактик, которую я использовал в знаменитых матчах после компьютеров», — говорит Альтерман.

Шей Бушинский, шахматный программист, разработавший программу Junior вместе с Амиром Баном, давний друг Альтермана. Он вспоминает, как работал с ним над Junior в начале 2000-х, когда еще оставались важные направления игры, в которых люди могли бы преуспеть против машины.

Шахматы

Возьмем вот этот пример, в котором Junior (играя белыми) побеждается по большей части оборонительной стратегией гроссмейстера Йеруна Пикета (играющего черными). Один из комментаторов пишет: «Прекрасные противокомпьютерные шахматы! Просто посмотрите на игру Джуниора после 12 хода — он ничего не совершает и просто переставляет фигуры, пока Пикет (sic) выстраивает сокрушительное нападение».

Были и люди, которые поняли, что шахматные программы не всегда имеют хороший код. Саймон Уотерс, британский шахматный энтузиаст, обнаружил несколько ошибок программирования в популярной бесплатной программе GNU Chess.

«Была проблема с хронометражем, так что в некоторых моментах она не оставляла себе времени подумать, даже если имела время на часах», — приводит он один из примеров.

Слишком мощный

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

Шахматные программисты пользовались идеями людей вроде Дэвида Леви и Бориса Альтермана с тех пор, как в 1968 году была заключена знаменитая сделка. По сути, шахматные программы в наши дни настолько мощные, что даже у лучшего игрока в мире (сейчас это 24-летний норвежец Магнус Карлсен) нет шансов победить в турнирном матче.

Почему?

«За последние 10 лет произошло множество улучшений в плане как поиска, так и оценки, — говорит Марк Лефлер, программист, который работает над мощной шахматной программой Komodo. — Сейчас поиск высоко избирательный, и они отрубают части дерева (или возможные ходы) или значительно уменьшают их, если программа считает ход не особенно хорошим, — говорит он. — Критические линии могут быть обнаружены гораздо, гораздо глубже».

Шахматы

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

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

Ночью шесть компьютеров Лефлера играют порядка 14 000 игр за восьмичасовой период. «Шесть машин умножить на 14 000 игр — это много игр, — говорит он. — И с каждой сыгранной игрой база данных становится глубже и богаче».

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

Эло Магнуса Карлсена сейчас составляет 2850, тогда как Komodo удобно чувствует себя повыше — на 3350. Эти рейтинги меняются с течением времени на основе выигранных, проигранных и сыгранных вничью игр против оппонентов, принимая во внимание собственный Эло оппонента. К примеру, игрок с Эло в 1400 получит больше очков, сыграв вничью против Карлсена, чем кто-то — и компьютер — с сопоставимым Эло, сыграв вничью с чемпионом мира, достигнувшим того же результата.

Шахматный киборг

Альтерман давно перестал пытаться обыграть компьютер. «Все это похоже на попытку состязаться с машиной в легкой атлетике — люди не могут с ними играть», — говорит он. Но неужели соревновательная игра против компьютеров в результате этого умерла? Вовсе нет. Дэвид Леви указывает, что сегодня существуют так называемые «odds matches», в которых компьютер начинает, к примеру, без одной пешки, и они весьма популярны. Komodo сыграл серию с гроссмейстерами в таких условиях.

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

Шахматы

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

Именно это произошло с двумя любителями в 2005 году. Стивен Крамтон и Захария Стивен были приятелями по шахматам, познакомившимися в местном клубе в Нью-Гемпшире в США. Несколько лет они провели, оттачивая свои навыки в игре, и Стивен, в частности, увлекался шахматным программированием.

Они приняли участие в «свободном» турнире, который в том году привлек несколько команд гроссмейстеров, которым помогали компьютеры. Турнир игрался дистанционно, онлайн, на серверах Playchess.com.

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

«У нас была весьма обширная база данных, над которой я работал в течение четырех или пяти лет, — вспоминает Стивен. — Стив тоже сделал в нее вклад».

У них было три ПК, которые пропускали цифры и были специально подготовлены Стивеном. Но что самое главное, любители знали, как на самом деле играть в игру киборга.

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

Устав читеров

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

Этот факт спасает человечество, и слава богу, от позора быть запросто обыгранными компьютерами в игре, в которую мы играли тысячи лет. Справедливо также отметить, что компьютеры, наверное, безнадежно и навсегда изменили процесс игры в шахматы. В последние годы наблюдается тревожный рост читинга на турнирах, чаще всего с участием компьютеров. В апреле этого года одного гроссмейстера поймали за использованием компьютера, когда он решил посетить туалет во время матча. Руководители говорят, что обнаружили iPod Touch с шахматным приложением, с которым консультировались во время перерывов. В сентябре итальянца застали за использованием хитроумной системы с камерой, кодом Морзе и пособника, вооруженного шахматной программой, во время игры.

Шахматы всегда были и будут жестко соревновательной игрой. Возможно, компьютеры действительно слишком сильны, чтобы мы могли их обыграть. Но Бушинский высказал интересную мысль. Поскольку юные игроки даже и не думают бросать вызов машинам, эпоха их улучшения для соперничества с человеком может подойти к концу. Тот факт, что мы боимся с ними играть, может быть прекрасным ходом сам по себе.

По материалам BBC

Шах и код: история компьютеров-шахматистов и шахматистов-компьютеров

Приложение
Hi-News.ru

Новости высоких технологий в приложении для iOS и Android.

6 комментариев

  1. matva

    Хорошая статья...
    Но вот эта фраза убила )))
    "Они не предоставляли никаких преимуществ в игре против человек, но могли дать игроку перевес против компьютерного соперника."
    Попахивает авто переводом ))) (отправлено из iOS приложения Hi-News.ru)

  2. erl

    Да вы что? Какой Леви чемпион мира? Он даже не гроссмейстер!

  3. matva

    Ты подумал ,что сказал? ))) он шахматист! Он думает на десяток ходов вперёд! И в жизни тоже! Это стиль мышления такой. И потому он уже давно просчитал все для себя. (отправлено из iOS приложения Hi-News.ru)

  4. vit555

    Какой аватар-такой и комментарий...

  5. Naktopoleon

    Эмм...На этом сайте нет аватаров...

  6. Naktopoleon

    и аватарок))

Новый комментарий

Для отправки комментария вы должны авторизоваться или зарегистрироваться.