Серия Машины, которые играют разбита на 7 частей. Это четвертая часть серии.

Эта серия охватывает историю искусственного интеллекта и игр (до Deep Blue) и фокусируется на машинах, которые играли в шахматы, шашки и нарды. Рассмотрены следующие темы: как построить шахматные машины, работы Шеннона по шахматам, работы Тьюринга по шахматам, Турок, Эль-Аджедресиста, MANIAC, шахматная программа Бернштейна, шашки Самуэля, Mac Hack VI, Cray Blitz, BKG, HiTech, Chinook, Deep Thought, TD-Gammon и Deep Blue.

Часть 1: Машины, которые играют (Обзор) - эта

Часть 2: Машины, которые играют (сборка шахматных машин)

Часть 3: Машины, которые играют (Chess-Before Deep Blue)

Часть 4: Машины, которые играют (Deep Blue) - эта

Часть 5: Машины, которые играют (сообщение Deep Blue)

Если вы хотите получить сводку первых 5 частей с акцентом на человеческий фактор, перейдите сюда [ссылка скоро появится].

Часть 6: Машины, которые играют (шашки)

Часть 7: Машины, которые играют (нарды)

Часть 4: Машины, которые играют (Deep Blue)

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

Быть похожим на человека, но (все же) не быть человеком

Путь (AI и шахматы) до сих пор *

* Подробную информацию см. в последнем разделе

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

Общественность должна увидеть, что шахматы - это жестокий вид спорта. Шахматы - это ментальная пытка . - Гарри Каспаров (1990-е)

Шахматы издавна считались игрой интеллекта. И многие люди утверждали, что машина, которая может успешно играть в шахматы, докажет, что мышление можно смоделировать / понять или что машины можно построить, чтобы думать. И именно поэтому люди хотели создать машину, которая могла бы следовать некоторым произвольным правилам нашей игры и стать настолько успешной в этом, что однажды она могла бы превзойти нас в этом.

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

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

Создание электронно-вычислительных машин началось в 1930-х годах. ENIAC, который считается первым электронным компьютером общего назначения, был введен в эксплуатацию в 1946 году. К концу 1940-х годов компьютеры использовались в качестве исследовательских и военных инструментов в США, Англии, Германии и бывшем СССР. Компьютерные шахматы представляют собой увлекательную и сложную инженерную задачу.

1940s — 1950s

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

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

1960s

В 1960-х пионеры искусственного интеллекта Герберт Саймон и Джон Маккарти называли шахматы «дрозофилой искусственного интеллекта», что означало, что шахматы, как и обычная плодовая мушка, представляют собой относительно простую систему, которую также можно использовать для исследования более крупных и сложных реальных объектов. -мирские явления. Компьютерные шахматы были идеальным полигоном для исследований искусственного интеллекта.

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

1970s — 1980s

В 1970–1980 годах упор делался на скорость аппаратного обеспечения. В 1950-х и 1960-х годах первопроходцы сосредоточились на шахматной эвристике (эмпирических правилах), чтобы выбрать лучшие следующие ходы. В 1970-х и 1980-х годах гораздо больше внимания уделялось усовершенствованию программного обеспечения, а также использованию более быстрого и специализированного оборудования. Настроенное аппаратное и программное обеспечение позволяло программам проводить гораздо более глубокий поиск деревьев игр (включая миллионы шахматных позиций), чего люди не могли (потому что не могли) делать.

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

1990s

В 1990-х годах шахматные программы начали бросать вызов международным мастерам по шахматам, а затем и гроссмейстерам. Эти программы гораздо больше полагались на память и грубую силу, чем на стратегическое понимание, и они начали последовательно побеждать лучших людей. Некоторые драматические моменты в компьютерных шахматах произошли в 1989 году - два широко уважаемых гроссмейстера были побеждены командами CMU Hitech и Deep Thought.

Исследователи почувствовали, что машины наконец-то могут победить чемпиона мира по шахматам. Это заинтересовало IBM, поэтому они начали работать над этой задачей в 1989 году и построили специализированную шахматную машину под названием Deep Blue. В конечном итоге он победит Гарри Каспарова, лучшего шахматиста среди людей.

Исследователи IBM будут награждены премией Фредкина, премией в 100 000 долларов за первую программу, которая победит действующего чемпиона мира по шахматам, которая оставалась невостребованной в течение 17 лет. Эта (и более поздние) победы в компьютерных шахматах разочаровали многих исследователей ИИ, потому что они были заинтересованы в создании машин, которые добивались успеха благодаря стратегиям «общего интеллекта», а не грубой силе. В этом смысле шахматы начали отделяться от исследований искусственного интеллекта.

Остальные разделы посвящены Deep Blue. Deep Blue был узкоспециализированной машиной, предназначенной для игры в шахматы:

  1. В 1993 году Deep Blue проиграл Бенту Ларсену в матче из четырех игр.
  2. В 1996 году Deep Blue проиграл Гарри Каспарову матч из шести игр (4–2): а) от 1,6 до 2 миллионов позиций в секунду на чип, б) от 50 до 100 миллионов позиций в секунду для системы.
  3. В 1997 году Deep Blue (3,5–2,5) выиграл матч из шести игр у Гарри Каспарова. Поражение Каспарова Deep Blue было его первым поражением в шахматном матче за всю его жизнь: а) улучшенная шахматная фишка с 2 до 2,5 миллионов позиций на фишку, б) 200 миллионов позиций в секунду.

Сейчас:

Ни один человек не может играть на лучших компьютерах (или даже на командах человек + компьютер) на равных. У нас (людей) было более 1000 лет, чтобы изобретать, играть и понимать шахматы - машинам было меньше 60 лет, и они намного лучше, чем мы.

Теперь Deep Blue

Были организованы шестигранные шахматные матчи между чемпионом мира Гарри Каспаровым и IBM Deep Blue. Первый матч состоялся в Филадельфии в феврале 1996 года. Матч-реванш состоялся в Нью-Йорке в мае 1997 года.

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

Popular Science спросил Дэвида Леви о матче Гарри Каспарова с Deep Blue, и Леви заявил, что:

«… Каспаров может довести матч до 6: 0, если захочет. «Я уверен, я поставил бы на это свою жизнь».

С другой стороны, Монте Ньюборн, профессор информатики в Университете Макгилла, сказал: «Я отдам компьютер 4 1/2 Каспарову 1 1/2 [Ничья дает каждому игроку пол-очка]. становится лучше, чем вы, становится явно лучше, чем вы, очень быстро. В худшем случае он получит оценку 4 1/2. "

«Когда компьютер становится лучше вас, он становится лучше вас очень быстро».

Результат был неясен. Deep Thought, предшественник Deep Blue, был турнирным гроссмейстером, а не матчевым гроссмейстером. И это был не обычный турнир, это был матч. Это был другой вызов. Почему матч-игра представляла собой другую проблему, чем турнирная игра? Потому что в матче игроки играют несколько игр друг с другом. Это дало человеческим гроссмейстерам возможность оценить слабые стороны машины и использовать их в своих интересах. По данным Сюй,

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

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

Каспаров выиграл матч 1996 года. В 1997 году в Нью-Йорке состоялся матч-реванш. На этот раз Каспаров проиграл - поражение Каспарова от Deep Blue стало его первым поражением в шахматном матче за всю его жизнь.

Так что же такого особенного было в 1997 году?

Согласно Кэмпбелл, Хоан, Сюй, На самом деле существует две различные версии Deep Blue: одна проиграла Гарри Каспарову в 1996 году, а другая победила его в 1997 году.

В следующем (-ых) разделе (-ах) мы рассмотрим некоторые факторы, которые, по словам Кэмпбелла, Хоана и Сюй, повлияли на успех Deep Blue в 1997 году:

  1. Одночиповая поисковая система по шахматам
  2. Массовая параллельная система с несколькими уровнями параллелизма
  3. Сильный упор на поисковые расширения
  4. Сложная оценочная функция, и
  5. Эффективное использование игровой базы данных Grandmaster.

Вначале было…

В 1985 году Фэн-сюн Сюй и (чуть позже) Мюррей Кэмпбелл работали над ChipTest, а затем над Deep Thought, первой шахматной машиной уровня гроссмейстера.

В 1988 году Deep Thought победила гроссмейстера Бента Ларсена (в турнирной игре) своим настроенным оборудованием: парой специально созданных процессоров, каждый из которых включал микросхему СБИС для генерации ходов. Позже экспериментальная шестипроцессорная версия Deep Thought сыграла (из двух игр) матч против Каспарова и проиграла.

В 1989 году Хсу и Кэмпбелл были наняты для работы в IBM Research; в их новую команду вошли компьютерные ученые Джо Хоан, Джерри Броуди и К. Дж. Тан. Их новый проект получил название Deep Blue, и они начали исследовать, как использовать параллельную обработку для решения сложных проблем.

Что в имени?

Deep Thought II или Deep Blue Prototype? (1991–1995)

Что в имени? Получается совсем немного.

Международная ассоциация компьютерных шахмат (ICCA) проводила чемпионат мира по компьютерным шахматам в Гонконге в 1995 году. Сюй, Кэмпбелл и команда выиграли турнир в 1989 году и не участвовали в 1992 году. ICCA обратилась к IBM с просьбой спонсировать мероприятие, и IBM согласилась, что означало, что команда должна будет участвовать.

По словам Сюй, они бы лучше подготовились к противостоянию с Гарри Каспаровым в 1996 году, но IBM сочла это отличной возможностью для рекламы.

К 1992 году команда Deep Blue начала работу над новым дизайном микросхемы. Что касается Каспарова, они планировали использовать новейшие чипы, которые они разработали, но эти чипы не были готовы до гонконгского события. Им пришлось конкурировать с Deep Thought II.

Как должна называться машина, участвующая в чемпионате мира по компьютерным шахматам: Deep Thought II или Deep Blue Prototype?

Именно тогда и произошли дебаты по именованию.

Сюй написал в своей книге За Deep Blue: создание компьютера, победившего чемпиона мира по шахматам: Джерри Презент, наш специалист по связям с общественностью в то время, хотел использовать имя Deep Blue Prototype вместо Deep Thought II. Я хотел использовать название Deep Thought II. Мои рассуждения были следующими. Deep Blue, новая машина, будет по крайней мере в 100 раз быстрее Deep Thought II по эффективной скорости поиска, и, кроме того, Deep Blue будет гораздо лучше разбираться в позиционных концепциях в шахматах. Сравнивать Deep Blue с Deep Thought II было бы похоже на сравнение солнца с луной. Ну, я немного преувеличиваю, но разница в вычислительной мощности была примерно порядка тысячи к одному, с учетом гораздо более сложных вычислений шахматной оценки, выполненных на шахматных фишках Deep Blue. Я гордился тем, что было сделано, и не хотел, чтобы что-то было связано с Deep Blue, если только он не использует новые чипы. Deep Thought II все еще использовал шахматные фишки, которые я разработал еще в 1985 году . Он продолжил ,

«Насколько я понимаю, Deep Thought II был динозавром, который вот-вот вымрет. Он не собирался узурпировать название нашего нового мегатонного солнечного бластера, даже если только частично. ”

Сюй хотел Deep Thought II, но Броуди хотел Deep Blue Prototype, потому что они хотели иметь возможность сказать, что Deep Blue был «преемником действующего чемпиона мира по компьютерным шахматам, Deep Blue Prototype, во время матча с Гарри. Каспаров ».

Броуди предполагал, что их машина, вероятно, победит. И в «маловероятном» случае, если он не выиграет чемпионат, тогда они скажут, что на самом деле это не игра Deep Blue. Проблема, по словам Сюй, заключалась в том, что они не считали проигрыш «маловероятным» событием - команда оценивала свои шансы на победу примерно 50–50.

Мы будем называть машину Deep Thought II, потому что так поступили Сюй и его команда.

В 1995 году Deep Thought II выступали в Гонконге. До этого Deep Thought II была в основном отключена как минимум за шесть месяцев до этого турнира. Соперником в первом туре Deep Thought II была Star Socrates, параллельная шахматная программа из Массачусетского технологического института, работающая на многомиллионном суперкомпьютере. По словам Хсу, его машина была примерно в сто раз дороже, чем рабочая станция, на которой работала Deep Thought II. И его скорость поиска была по крайней мере сопоставима с Deep Thought I I . Звездный Сократ был большой угрозой для Deep Thought II.

Сюй написал в своей книге Behind Deep Blue: Когда Deep Thought II играл Звездного Сократа годом ранее, я впервые увидел программу, которая фактически« опередила Deep Thought II ... Тем не менее, Deep Thought II имел легко превзошел его. Будет ли один год иметь значение? Deep Thought II не работал больше полугода, и сотрудники Массачусетского технологического института, вероятно, не сидели сложа руки ».

Deep Thought II победил Звезду Сократа.

Столкнувшись с последним противником, Фрицем, в какой-то момент игры Deep Thought II впал в состояние «паники». Deep Thought II оказался в плохой позиции, и ему нужно было сделать ход. Он нашел ход для игры, но проиграл, и ему нужно было найти лучший ход. Он вошел в состояние, в котором тратил дополнительное время, чтобы найти альтернативный ход. Пытаясь найти хорошую альтернативу, Deep Thought II искал гораздо большее дерево (поиск бурно развивался). Сюй вспомнил, что гроссмейстер Роберт Бирн остановился и прошептал им, какой ход, по его мнению, должен сыграть Deep Thought II.

Сюй и его команда ничего не могли поделать, кроме как ждать, пока Deep Thought II закончит свои массовые поиски, гадая, действительно ли Deep Thought II найдет ход, предложенный Робертом - ход, который остро необходим для улучшения своей позиции. Время вышло, и после всех этих поисков Deep Thought II сделал свой изначально задуманный ход. Лучшего хода не нашлось. Это было окончено. Deep Thought II проиграл. Фриц продолжал выигрывать чемпионат.

Deep Thought II не был похож на Deep Blue, но и не был той же машиной, что и Deep Thought. Они внесли улучшения (от Кэмпбелл, Хоан и Сюй):

  1. Среднемасштабная многопроцессорность »Deep Thought II имел 24 шахматных движка (со временем это число уменьшалось, поскольку процессоры выходили из строя и не были заменены) по сравнению с процессорами Deep Thought 2 (было несколько версий с 4 и 6 процессорами. ).
  2. Усовершенствованное оценочное оборудование. В оценочном оборудовании Deep Thought II использовалось больше оперативной памяти, и оно могло включать несколько дополнительных функций в функцию оценки.
  3. Улучшенное программное обеспечение для поиска. Программное обеспечение для поиска было полностью переписано для Deep Thought II и было разработано, чтобы лучше справляться с параллельным поиском, и в нем содержался ряд новых идей для расширения поиска. [Этот код позже станет исходной базой для поисковой программы Deep Blue.] Сюй написал в своей книге Behind Deep Blue: Официально причиной создания Deep Thought II было использование его в качестве прототипа для исследования алгоритмы параллельного поиска. Но главная причина заключалась в том, чтобы действительно создать большой разрыв между нашими компьютерными конкурентами и нами, чтобы проект мог продолжаться в течение длительного периода, пока я борюсь с дизайном новой шахматной фишки.
  4. Расширенная книга: расширенная книга позволяла Deep Thought II делать разумные шаги открытия даже при отсутствии книги открытия. [Эта функция также была унаследована Deep Blue.]

Переходим к Deep Blue - задача проекта заключалась в следующем: выиграть матч с лучшим чемпионом мира по шахматам среди людей при обычном контроле времени.

Разработка Deep Blue (1996–1997)

Согласно философии дизайна команды Deep Blue, сосредоточение внимания на уровне интеграции было самым важным:

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

Что касается скорости, они заявили, что скорость поиска будет достигнута за счет повышения уровня интеграции (увеличения количества однокристальных шахматных машин) и использования массового параллелизма.

Deep Blue (1996)

Deep Blue (1996) был основан на одночиповой поисковой системе по шахматам, разработанной в течение трех лет. Он работал на 36-узловом компьютере IBM RS / 6000 SP. В нем было 216 шахматных фишек. Большинство членов оценочной функции вычислялись непосредственно на микросхемах - для того, чтобы для выполнения тех же вычислений на компьютере общего назначения, которые выполнялись в Deep Blue 1986 года, потребовалось бы по крайней мере один триллион инструкций в секунду, , - сказал Сюй . Эти шахматные фишки оценивали шахматные позиции гораздо детальнее, чем любая другая шахматная программа до этого.

Каждая шахматная фишка могла выполнять поиск около 1,6 миллиона шахматных позиций в секунду. По словам Хсу, теоретическая максимальная скорость поиска Deep Blue (1996) составляла около 300 миллионов позиций в секунду. Наблюдаемая скорость поиска составила около 100 миллионов позиций в секунду.

Команда Deep Blue потратила более 3 лет на разработку этих чипов. Первые шахматные фишки они получили в сентябре 1995 года, но с фишками возникли проблемы. Поэтому им потребовалась обновленная версия чипов, которую они не получили до января 1996 года. Первый матч был назначен на февраль 1996 года, поэтому у них не было времени протестировать всю систему.

Полный 36-узловой Deep Blue (1996) сыграл свои первые игры в условиях турнира в реальном матче февраля 1996 года - против Гарри Каспарова.

Некоторая часть системы провела несколько подготовительных матчей, но игра, известная как Deep Blue Jr., использовала только одноузловую версию Deep Blue всего с 24 шахматными фишками. Но даже относительно ограниченный Deep Blue Jr. обыграл гроссмейстера Илью Гуревича 1.5–0.5, сыграл вничью у гроссмейстера Патрика Вола 1–1 и проиграл гроссмейстеру Джоэлу Бенджамину 0–2.

Deep Blue (1996) был намного мощнее Deep Blue Jr., на самом деле это была самая мощная шахматная машина из когда-либо созданных. Тем не менее, команда Deep Blue не знала, как она будет играть на самом деле. потому что они никогда не видели, чтобы он играл ни в одной игре. Deep Blue (1996) был всего двухнедельным ребенком, самым сильным ребенком на свете, но, тем не менее, еще ребенком. Сюй сказал:

«Может быть, младенец Геракл задушил двух змей, посланных богиней Герой? Или мы посылали беспомощного младенца в качестве дани, чтобы умиротворить морского чудовища Кита, но без помощи Персея? Мы боялись, что это будет последнее. ”

Первую игру Deep Blue против Каспарова в феврале 1996 года выиграла Deep Blue.

По словам Фредерика Фриделя, который был компьютерным консультантом Каспарова, в ночь после первой игры Каспаров отправился на ночную прогулку (в Филадельфии при отрицательных температурах). Во время прогулки он спросил:

«Фредерик, а что, если эта вещь непобедима?»

В этой первой партии матча Каспаров написал, компьютер подтолкнул пешку вперед на поле, где ее можно было легко взять. Это был замечательный и в высшей степени человечный ход. Если бы я играл белыми, я мог бы предложить эту жертву пешки ... Люди все время так поступают. Но компьютеры обычно вычисляют каждую линию игры, насколько это возможно, в отведенное время… Основной способ компьютеров оценивать шахматные позиции - это измерение материального превосходства, они, как известно, материалистичны. Если они «понимают игру, они могут действовать по-другому, но они не понимают. Так что я был ошеломлен этой жертвой пешки. Что это могло значить? Я играл на многих компьютерах, но никогда не испытывал ничего подобного. Я мог чувствовать - я мог чувствовать запах - новый вид интеллекта за столом. Пока я доигрывал оставшуюся часть игры, как мог, я заблудился; Всю оставшуюся часть пути он играл в красивые, безупречные шахматы и легко выигрывал ».

«Я чувствовал - я чувствовал запах - новый вид интеллекта за столом».

Оказалось, что пешка вовсе не жертва. Deep Blue (1996) просчитал все возможные ходы «вплоть до фактического восстановления пешки шестью ходами спустя». Затем Каспаров спросил: «Итак, вопрос ...

«… если компьютер делает тот же ход, который я сделал бы по совершенно другим причинам, сделал ли он« умный »ход? Зависит ли интеллект действия от того, кто (или что) его предпринимает? ”

Позже в своем выступлении на TED Каспаров сказал: Когда я впервые встретился с Deep Blue в 1996 году в феврале, я был чемпионом мира более 10 лет, и я сыграл 182 игры чемпионата мира и сотни игр. против других лучших игроков в других соревнованиях. Я знал, чего ожидать от соперников и чего ожидать от себя. Я привык измерять их движения и оценивать их эмоциональное состояние, наблюдая за языком их тела и глядя им в глаза. А потом я сел напротив Deep Blue за шахматную доску. Я сразу почувствовал что-то новое, что-то тревожное. Вы можете испытать подобное чувство, когда впервые едете в машине без водителя или когда ваш новый компьютерный менеджер впервые отдает приказ на работе. Но когда я сидел на той первой игре, я не мог понять, на что она способна. Технологии могут развиваться скачкообразно, и IBM вложила большие средства. Я проиграл эту игру. И я не мог не задаться вопросом, может ли он быть непобедимым? Моя любимая игра в шахматы закончилась? Это были человеческие сомнения, человеческие страхи, и единственное, что я знал наверняка, это то, что у моего оппонента Deep Blue совсем не было таких забот .

« И я не мог не задаться вопросом, может ли он быть непобедимым? Моя любимая игра в шахматы закончилась? Это были человеческие сомнения, человеческие страхи, и единственное, что я знал наверняка, это то, что у моего оппонента Deep Blue совсем не было таких забот ».

Матч 1996 года окончательно выиграл Каспаров (счет 4–2). Матч был равен 2–2 после первых четырех игр, и хотя казалось, что это была решающая победа, это был довольно близкий матч, ближе, чем обычно считалось.

Согласно Beyond Deep Blue: Chess in the Stratosphere Монти Ньюборна, В пятой игре Каспаров решил избежать своей любимой сицилийской защиты, так как не смог выиграть с ней в первой и третьей партиях. Это косвенно свидетельствовало о признании силы его оппонента и уважении к нему. Вместо этого он разыграл Дебют Четырех рыцарей. Потом вдруг на 23-м ходу он предложил ничью этому сопернику? И почему? Deep Blue посчитал, что проигрывает на три десятых пешки, и команда была удивлена ​​предложением. Правила игры позволяли команде решать, принимать ли жеребьевку или нет, - единственное решение, которое могли принять люди от имени компьютера. У Каспарова было немного времени - около 20 минут на следующие 17 ходов, около минуты на ход, в отличие от скорости игры, когда на каждый ход в среднем отводилось три минуты. Так что, возможно, он здесь перестраховался, чувствуя, что сможет победить Deep Blue в финальной игре белыми фигурами ... Команда Deep Blue собралась, чтобы обсудить предложение. Он так долго собирался, что Deep Blue сделал свой 24-й ход, фактически отклонив предложение.

В итоге Каспаров выиграл ту партию. Иначе по прошествии пяти игр, перед выходом в финальную шестую игру, матч был бы равен ничьей.

Каспаров закончил свой очерк во времени рассказом о том, почему он выиграл первый матч. Он сказал: Я могу определить его приоритеты и скорректировать свою игру. Со мной этого не могло быть. Поэтому, хотя я думаю, что действительно заметил некоторые признаки интеллекта, он странный, неэффективный, негибкий, из-за чего мне кажется, что у меня осталось несколько лет .

У него не осталось нескольких лет. В мае 1997 года он проиграет матч-реванш Deep Blue.

Темно-синий (1997)

Улучшения Deep Blue (1996 г.)

Команда Deep Blue знала, что в Deep Blue (1996) есть ряд недостатков, которые им необходимо преодолеть, например, пробелы в шахматных знаниях и скорости вычислений. Итак, Кэмпбелл, Хоан, Сюй внесли следующие изменения в Deep Blue (1997):

  1. Они разработали новую и значительно улучшенную шахматную фишку: 1) у новой шахматной фишки была полностью переработана функция оценки: «около 6400 функций до более 8000». Некоторые из этих новых функций были результатом проблем, которые они наблюдали в играх 1996 года; 2) новый чип добавил «аппаратное обнаружение повторения», которое включало ряд специализированных режимов генерации ходов (например, для генерации все ходы, атакующие фигуры противника :), 3) новый чип увеличил скорость поиска до 2 - 2,5 миллиона позиций в секунду.
  2. Они более чем удвоили количество шахматных фишек в системе и использовали компьютер SP нового поколения для поддержки более высоких требований к обработке, вызванных увеличением количества шахматных фишек.
  3. Они разработали набор программных инструментов для помощи в отладке и подготовке к сопоставлению, например, инструменты настройки оценки и визуализации.
  4. Они не сильно изменили поиск, потому что поисковая способность Deep Blue уже была «приемлемой».

Затем они разработали, протестировали и настроили новую функцию оценки.

Соответствие

Каспаров победил Deep Blue (1996).

Это был май 1997 года, и настало время для матча-реванша. Каспаров выиграл первую партию матча-реванша.

Прогнозы были в пользу Каспарова, многие эксперты предсказывали, что чемпион наберет не менее четырех баллов из шести. Каспаров превосходно выступал на турнире в Линаресе, и его рейтинг был на рекордно высоком уровне - 2820. В фильме 2003 года он вспомнил о своей ранней уверенности:

«Я побью машину, что бы ни случилось. Посмотрите на Первую игру. Это просто машина. Машины глупы ».

Команда Deep Blue была разочарована в игре 1, и Джоэл Бенджамин, гроссмейстер, который поделился с машиной своими гроссмейстерскими шахматными знаниями, был убежден, что Deep Blue (1997) может играть намного лучше, чем в игре 1. Посмертный анализ показал, что Deep Blue Blue могла бы сыграть вничью, если бы только могла глубже исследовать еще несколько слоев ...

Затем пришла игра 2 - игра настолько отличная от других, что машины, играющей в такую ​​игру, никогда раньше не видели.

Сила компьютеров заключалась в тактических шахматах; они не играли стратегически, другими словами, до тех пор компьютеры предпочитали материальные выгоды позиционным преимуществам. До тех пор.

Каспаров устроил ловушку, в которой Deep Blue получит пешку (материальный выигрыш), но проиграет позицию. Вместо взятия открытой пешки (как все ожидали) Deep Blue (1997) выбрал другой путь; он выбрал позиционное преимущество. В то время никакая машина не играла с тем, что гроссмейстеры называли стратегическим предвидением. Deep Blue только что мельком показал это.

Deep Blue (1997) играл в игру 2 как человек, а машины должны были играть иначе. Гроссмейстеры, наблюдавшие за игрой, позже сказали, что если бы они не знали, кто играет, они бы подумали, что Каспаров играет одного из величайших игроков человека, может быть, даже самого. Джоэл Бенджамин сказал, что был свидетелем красивой игры в «шахматы», а не в «компьютерные шахматы».

Эта игра потрясла Каспарова, и после этого он ни разу не выигрывал у Deep Blue. Он изменил свой стиль и перешел в оборону. Согласно (более поздней) статье Wired, гроссмейстер Ясир Сейраван сказал: Это был невероятно изысканный ход защиты впереди, чтобы исключить любой намек на встречные удары, и это вызвало у Гарри нервное возбуждение. >

Малькольм Пейн, шахматный корреспондент лондонской The Daily Telegraph, сказал: «Есть только три объяснения:

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

Сразу после игры Каспаров обвинил IBM в мошенничестве; он утверждал, что за определенным ходом стоял гроссмейстер (предположительно главный соперник). Это утверждение было повторено в документальном фильме Игра окончена: Каспаров и машина. Он утверждал, что такой ход был слишком человечным, и компьютер никак не мог выбрать такой ход.

IBM не обманывала, технически. Согласно правилам, им разрешалось в перерывах между играми вносить изменения в свою систему. Мы бы сказали, что« доработали программу во время матча», - сказал Джоэл Бенджамин, но они не внесли никаких существенных изменений. После провала Deep Blue в первой игре IBM вернулась к чертежной доске и переназначила относительные веса для различных функций игры.

Следующие три игры Каспаров не выиграл, но и Deep Blue не выиграл - три ничьи.

В преддверии финальной игры счет был 2,5–2,5.

Позже шахматное сообщество приступило к анализу партии 2 и обнаружило нечто шокирующее: Каспаров подал в отставку при ничьей.

По словам Джонатана Шаффера, Анализ является довольно глубоким и выходит за пределы горизонта поиска Deep Blue. И, судя по всему, Каспарова тоже. Перед командой Каспарова, в которую входили гроссмейстер Юрий Дохоян и Фредерик Фридель, стояла деликатная задача - сообщить новости Каспарову. На следующий день они подождали обеда, после того как он выпил бокал хорошего вина. После того, как они раскрыли скрытый ресурс для рисования, Каспаров погрузился в глубокие размышления (без каламбура) на пять минут, прежде чем признал, что пропустил ничью. Позже он утверждал, что впервые отказался от ничьей .

Последняя игра была бойкой и жестокой, всего за 19 ходов Deep Blue ошеломил мир. Deep Blue сместил Каспарова. [См. редкие кадры из последней игры.]

Итоговая оценка - 3,5–2,5. Каспаров был настолько великим игроком, что до этого не проигрывал ни одного матча - за всю свою жизнь. И он сыграл несколько величайших матчей в истории шахмат, в том числе несколько против Анатолия Карпова.

Но на этот раз все было иначе. В отчаянии Каспаров сказал: «Я потерял боевой дух». До этого он ни разу не проигрывал в матче из нескольких игр одному противнику.

После 6-й игры он сказал:

« Я был совсем не в настроении играть ... Я человек. Когда я вижу что-то, что выходит за рамки моего понимания, я боюсь. ’’

Каспаров был разочарован и признался на пресс-конференции, что ему было неловко и стыдно за свое выступление. Позже он попросил IBM посмотреть журналы игры, но IBM отказалась их показать. IBM критиковали за это, но нужно помнить, что журналы вычислений и ходов Deep Blue были понятны шахматным мастерам. Предоставление журналов Каспарову во время матча было бы равносильно разглашению стратегии Deep Blue, как сказал Дрю Макдермотт: … это было бы равносильно прослушиванию номера гостиницы, где он [Каспаров] обсуждал стратегию со своими секундантами .

Через неделю после матча Каспаров выразил восхищение игрой Deep Blue во 2-й партии: Решающей партией в матче была игра 2, которая напугала меня ... мы увидели кое-что, что прошло далеко за пределами наших самых смелых ожиданий относительно того, насколько хорошо компьютер сможет предвидеть долгосрочные позиционные последствия своих решений. чувство опасности. Я думаю, что этот момент может означать революцию в информатике, которая принесет IBM и команде Deep Blue Нобелевскую премию. Даже сегодня, недели спустя, ни одна другая шахматная программа в мире не смогла правильно оценить последствия позиции Deep Blue .

Deep Blue играл намного лучше, чем в 1996 году. По словам Джонатана Шеффера, некоторые из причин, по которым Deep Blue выиграли, были:

  • Он делал меньше ошибок, и ошибки, которые он делал, были менее серьезными.
  • Его скорость увеличилась
  • Помогли обширные настройки такими людьми, как Джоэл Бенджамин. Шеффер говорит, что помимо гроссмейстера Джоэла Бенджамина Deep Blue тестировали еще несколько гроссмейстеров. Другие исследователи из IBM, такие как Джерри Тезауро (TD-Gammon), были приглашены на помощь - он использовал свою технологию нейронной сети, чтобы настроить функцию оценки Deep Blue.
  • Каспаров плохо готовился к матчу. Каспаров писал о своей подготовке: «К сожалению, я основывал свою подготовку к этому матчу… на общепринятом мнении о том, что может быть хорошей антикомпьютерной стратегией. Принято считать - или так было до конца этого матча - избегать ранних столкновений, вести медленную игру, пытаться перехитрить машину, форсировать позиционные ошибки, а затем, когда наступает кульминация, не терять концентрацию и не совершать любые тактические ошибки… Мне не повезло, что эта стратегия отлично сработала в первой игре - но никогда больше до конца матча. К середине матча я обнаружил, что не готов к тому, что оказалось совершенно новым интеллектуальным вызовом ».
  • Каспаров сделал неверный выбор дебютов; он не играл по позициям, на которых чувствовал себя наиболее комфортно.

Гарри Каспаров попросил провести матч-реванш, но этого не произошло.

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

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

На эту тему Каспаров намекал на протяжении всего матча и продолжает обсуждать даже сейчас [выступление Каспарова на TED].

[Боковое примечание: Видео краткое изложение игры Каспарова против Deep Blue]

Инженерный темно-синий

Затем немного о том, что вошло в создание Deep Blue (1997). Большая часть этой информации поступает из следующих источников:

  1. Deep Blue Кэмпбелл, Хоан, Сюй
  2. Фишки гроссмейстеров Deep Blue Chess от IBM Автор Сюй
  3. Создание шахматного гроссмейстера с одной фишкой, ничего не зная о шахматах Сюй

Архитектура системы

Deep Blue (1997) - это массово-параллельная система, предназначенная для поиска в дереве шахматных игр. Распределенная архитектура состояла из 30-узлового (30 процессоров (по одному на узел)) компьютера IBM RS / 6000 SP, который принимал решения на высоком уровне, и 480 шахматных фишек (каждая - одночиповой шахматной поисковой машины) с 16 шахматами. чипов на процессор SP. Все узлы имели 1 ГБ ОЗУ и 4 ГБ на диске.

480 чипов работали параллельно, чтобы выполнять а) глубокий поиск, б) генерацию и упорядочивание перемещений, в) эффективную оценку положения (более 8000 функций оценки).

Каждая шахматная фишка могла выполнять поиск от 2 до 2,5 миллионов шахматных позиций в секунду, поэтому максимальная скорость системы достигала примерно 1 миллиарда шахматных позиций в секунду или 40 тера операций.

Поиск

Deep Blue (1997) объединил программное и аппаратное обеспечение для максимального эффекта и гибкости (см. Здесь и здесь). Основная стратегия высокого уровня заключалась в следующем:

  • Первые 4 слоя будут найдены на 1 узле рабочей станции.
  • 2-е 4 слоя будут искать параллельно более 30 узлов рабочих станций
  • Остальные слои будут искать аппаратно - здесь вступают в силу шахматные фишки.

Согласно документам Deep Blue Team (Сюй и Кэмпбелл, Хоан, Сюй), Deep Blue был организован в три уровня. Например, предположим, что системе необходимо выполнить 12-слойный поиск из заданной позиции. Потом,

  1. Главный узел: один из узлов рабочей станции, назначенный главным узлом для всей системы, будет искать первые четыре уровня в программном обеспечении, то есть он будет искать верхние уровни дерева шахматной игры. Теперь, после четырех ходов с текущей игровой позиции, количество позиций увеличивается примерно в тысячу раз.
  2. Рабочие узлы: на этом этапе все 30 узлов рабочих станций, 29 рабочих узлов и 1 главный узел будут искать в этих новых позициях (в программном обеспечении) еще четыре слоя, т. е. главный узел будет распределять «лист ”Позиции к рабочим узлам. Верхние уровни поиска будут выполняться в программном обеспечении и использовать таблицы транспонирования для повышения эффективности поиска. И снова количество позиций после этих 4-х слоев увеличивается еще в тысячу раз.
  3. Шахматные фишки. Наконец, на этом этапе рабочие узлы распределяют свои позиции по шахматным фишкам, которые ищут оставшиеся (в данном случае четыре) слоя. На самом деле шахматные фишки будут искать на последних нескольких уровнях дерева.

Подводя итог, можно сказать, что на каждую рабочую станцию ​​в системе приходилось 16 шахматных фишек, и главный узел рабочей станции распределял работу по шахматным фишкам и использовал MPI (интерфейс передачи сообщений) для связи через высокоскоростной коммутатор с другими рабочими узлами для выполнения распределенного и параллельного поиска. .

Согласно Кэмпбелл, Хоан, Сюй, общая скорость работы системы сильно варьировалась в зависимости от конкретных характеристик обыскиваемых позиций. Для тактических позиций, где существуют длинные последовательности форсированных движений, Deep Blue будет в среднем около 100 миллионов позиций в секунду. Для более тихих позиций типичной была скорость около 200 миллионов позиций в секунду. В ходе матча 1997 года с Каспаровым общая средняя скорость системы, наблюдаемая при поиске продолжительностью более одной минуты, составила 126 миллионов позиций в секунду.

[Примечание: если система может проверять 200 миллионов ходов в секунду, это означает, что она может проверять 50 миллиардов позиций за три минуты, отведенные на один ход в шахматной игре.]. Он может в среднем на 12,2 шага вперед за 3 минуты поиска.

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

Шахматные фишки

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

Базовая статистика чипа

  • 1,5 миллиона транзисторов
  • Время цикла микросхемы составляет от 40 до 50 наносекунд.
  • 0,6-микронная технология CMOS (комплементарный металл – оксид – полупроводник)
  • от 2 до 2,5 миллионов шахматных позиций в секунду
  • 1 вычисление шахматной позиции было примерно 40000 инструкций на универсальном процессоре
  • Эквивалентно суперкомпьютеру со скоростью 100 миллиардов инструкций в секунду
  • Сюй сказал: «… ускорение примерно до 30 миллионов позиций / с возможно с 0,35-микронным процессом и новым дизайном. Такой чип мог бы позволить победить чемпиона мира по шахматам с настольным персональным компьютером или даже ноутбуком ».
  • 4 основные части
  • Генератор движения
  • Функция оценки
  • Управление поиском
  • Стек умных ходов (далее делится на обычный стек ходов и детектор повторения)
  • Сюй: система с одной фишкой, похоже, подходит для сильного уровня гроссмейстера и, возможно, уровня супер-гроссмейстера

Сюй писал: Шахматные фишки в 0,6-микронной КМОП-матрице искали от 2 до 2,5 миллионов шахматных позиций в секунду на фишку. Недавний анализ конструкции показал, что ускорение примерно до 30 миллионов позиций / с возможно с 0,35-микронным процессом и новой конструкцией. Такой чип мог бы позволить победить чемпиона мира по шахматам с настольным персональным компьютером или даже ноутбуком. Используя 0,18-микронный процесс и, скажем, четыре шахматных процессора на чип, мы могли бы создать шахматный чип с более высокой устойчивой скоростью вычислений, чем Deep Blue 1997 года .

Позже Сюй писал: «Если вы готовы потратить деньги, вы можете построить шахматную машину более чем в сто раз быстрее, чем Deep Blue 1997 года, не прибегая к более быстрым шахматным фишкам».

Переместить генератор

Генератор ходов в чипе Deep Blue был расширением чипа генератора ходов Deep Thought, который был расширением генератора ходов машины Belle. Генератор ходов был основан на комбинаторном массиве 8 x 8, по одной ячейке на квадрат шахматной доски и соединен как шахматная доска. Фактически это была силиконовая шахматная доска, что означало, что проводка соответствовала способу движения шахматных фигур, чтобы можно было оценить позицию и найти все допустимые ходы одновременно, за одну вспышку.

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

В шахматной фишке также использовался порядок выбранных ходов, как описано в Кэмпбелле, Хоане, Сюй: 1) Взятие: фигура с низкой ценой захватывает фигуру с высокой; 2) Захват: фигура с высокой ценой захватывает фигуру с низкой ценностью, 3) взятие не выполняется.

Оценочные функции

Оценочная функция представляла собой взвешенную функцию различных« характеристик шахматной позиции» . Возможности варьировались от очень простых, таких как конкретная деталь на определенном квадрате, до очень сложных, и каждой особенности давалось значение. Вот пример оценочных характеристик: ладьи на седьмой горизонтали, ловушка для коня, ловушка для ладьи, пара слонов, пешечная структура, количество раз, когда ход был сделан, относительное количество раз, когда ход был сделан, недавность хода, результаты хода, силы игроков, которые делали ходы, и т. д. Шахматная фишка распознала около 8000 различных характеристик, и каждому было присвоено значение. Большинство функций и весов были настроены вручную.

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

Использование экспертных решений

Игра в шахматы состоит из трех фаз: начальной фазы, фазы середины игры и фазы эндшпиля. В зависимости от ситуации Deep Blue использовал другие стратегии для игры: дебютную книгу, расширенную книгу, базы данных эндшпиля.

Начальная фаза длится от 5 до 15 ходов. Компьютеры обычно обращались к большим базам данных для выбора ходов на этом этапе. Deep Blue курировал (в основном, гроссмейстером Джоэлом Бенджамином) начальную книгу из 4000 начальных позиций. Дебюты были выбраны, чтобы подчеркнуть позиции, которые Deep Blue играл хорошо. Эти дебюты включали как тактически сложные, так и более позиционные дебюты, с которыми Deep Blue хорошо справлялся на практике. Однако Deep Blue не переиграл Каспарова на этом этапе.

Компьютеры также неплохо играли в эндшпиле, но лучшие игроки на этом этапе все равно играли лучше. Но если в эндшпиле на доске было пять или меньше фигур, то компьютеры были лучше, потому что у них обычно была база данных обо всех пятифигурных эндшпилях. Deep Blue имел базу данных эндшпилей всех шахматных позиций с пятью или менее фигурами на доске, а также выбранных позиций с шестью фигурами. Каждый из 30 процессоров в системе содержал 4-компонентные и некоторые важные 5-компонентные базы данных на своем локальном диске. Остальная часть базы данных была включена в дисковые массивы RAID объемом 20 ГБ для онлайн-поиска.

Самым сложным для компьютеров было дойти до конца игры.

В середине игры вводная книга больше не дает рекомендаций, а базы данных эндшпиля еще бесполезны. Поиск взрывается также в середине игры. В типичных позициях средней игры от 30 до 40 ходов. И каждый ход может привести к 30 или 40 новым позициям, каждая из этих позиций будет иметь ходы, которые, в свою очередь, приведут к большему количеству позиций, и так далее. Это то, что подразумевается под высказыванием о том, что дерево игры растет с экспоненциальной скоростью. Компьютеры должны каким-то образом обыскивать эти массивные деревья, чтобы принимать эффективные решения о перемещении. И тут действительно помогли поисковые новинки.

Для решения этой проблемы Deep Blue использовала все основные нововведения в области поиска и была оснащена расширенной книгой из 700 000 баз данных игр Grandmaster, которую он мог использовать в случае, если вводной книги было недостаточно. Идея заключалась в том, чтобы обобщить информацию, доступную в каждой позиции этой большой игровой базы данных, а затем использовать ее, чтобы подтолкнуть Deep Blue в эффективном направлении.

Мы (наконец) закончили с резюме Deep Blue. Это должно было дать представление о том, что было сделано для создания машины, которая побеждает лучшего шахматиста. Май 1997 года был особенным событием в области искусственного интеллекта, и у людей есть мнение по этому поводу даже сейчас.

Реакция на победу Deep Blue

На пресс-конференции после 6-й игры Каспаров сказал: Думаю, Deep Blue пора доказать, что это не было единичным событием. Я лично заверяю вас, что, если он начнет соревноваться в шахматы, включите его в честное соревнование, и я лично гарантирую, что разорву его на куски. '' [См. «Редкие кадры последней партии.] Позже он появился на Larry King Live и сказал, что готов сыграть Deep Blue все или ничего, победитель получает все. Но этого не произошло. Вскоре после матча-реванша IBM решила отказаться от Deep Blue и прекратила всю работу над ним.

Джеймс Коутс из Chicago Tribune писал в октябре 1997 года: Подразделение IBM Deep Blue нуждается в увольнении, потому что его лидеры объявили 23 сентября, что они откажутся от широко раскрученного компьютера для игры в шахматы Deep Blue с единственной победой. рекорд с одним поражением вместо того, чтобы дать яркому и непредсказуемому гроссмейстеру Гарри Каспарову шанс на матч-реванш. Гениям, которые построили компьютер, который в мае победил лучшего шахматиста в мире, нужно выучить здесь в октябре первый урок, который каждый закулисный игрок в покер и стрелок в пул извлекает из мерзости. Я говорю о правиле троек. Допустим, мы играем в 9 мячей или в пинг-понг, и вы меня уничтожите. Прошу матча-реванша и еле обыграю тебя. Потом я прощаюсь, я лучший игрок, и теперь я иду домой? , - продолжил он:

« В бильярдных и карточных комнатах за меньшие деньги сломали ноги».

Deep Blue ошеломил мир. И у всех было свое мнение о матче или Deep Blue, или Каспарове, или IBM, или интеллекте, или творчестве, или грубой силе, или разуме…. Начнем с мнения Луиса Герстнера, генерального директора IBM: «У нас есть лучший шахматист мира против Гарри Каспарова».

Итак, действительно ли Deep Blue был лучшим шахматистом? Или Каспаров по-прежнему был лучшим игроком? Проблема в том, что в матче-реванше было всего шесть игр, а Каспаров отставал всего на одно очко. В матчах чемпионата обычно намного больше игр, и большинство из них заканчивается вничью. Таким образом, было трудно сказать, сказал ли матч-реванш из шести игр что-нибудь о том, кто был лучшим игроком. Многие возразят, что Каспаров по-прежнему был лучшим игроком. Но может быть, дело не в этом. Мы видели, как некоторые очень особенные люди приложили огромные усилия для создания машины, которая заставила сомневаться даже у лучших из нас. Он победил нас в одной из наших самых ценных игр и оставил нас в трепете (а некоторых - в страхе).

Чарльз Краутхаммер в Be Afraid в Weekly Standard написал: «К изумлению всех, в том числе Каспарова, в этой лишенной тактики игре Deep Blue победил. Блестяще. Творчески. По-человечески. Он играл - простите меня - с нюансами и тонкостью. "

«… Deep Blue выиграл. Блестяще. Творчески. По-человечески. Он играл - простите меня - с нюансами и тонкостью ».

Несмотря на то, что Deep Blue играл в игру, в которой, казалось, есть элементы человечности, и хотя ее победа кажется умопомрачительной, Родни Брукс (и другие) сказали, что обучение машины игре в сложную стратегическую игру - это не так. интеллект, по крайней мере, не так, как мы используем интеллект для других людей; эту точку зрения разделяли многие исследователи искусственного интеллекта. С другой стороны был Дрю Макдермотт, который сказал, что обычный аргумент, который люди привыкли считать Deep Blue неразумным, ошибочен. Он сказал: Сказать, что Deep Blue на самом деле не думает о шахматах, - все равно что сказать, что самолет на самом деле не летает, потому что не машет крыльями.

Так что же Deep Blue умен?

Может немного. Deep Blue, конечно, не был глуп, но он также не был умным, как мы говорим, что другие люди умны. То, что продемонстрировал Deep Blue, было узким типом интеллекта; вид, который демонстрирует великолепие в одной области, и это происходит потому, что люди создают лучшее оборудование, лучшее программное обеспечение, лучшие алгоритмы и лучшие представления. Но если вы попросите эти специализированные машины сделать что-нибудь еще, они потерпят неудачу. Deep Blue не справился бы со всеми другими задачами, не связанными с шахматами; он не проявлял общего интеллекта. До настоящего времени ни одна машина не продемонстрировала общего интеллекта, и, похоже, им еще предстоит пройти долгий путь, прежде чем они смогут это сделать.

Как Deep Blue сделал то, что сделал тогда? Когда Мюррея Кэмпбелла спросили о конкретном движении, сделанном компьютером, он ответил: «Система перебирает многие миллиарды возможностей, прежде чем принять решение о движении, и фактически выяснить, почему он сделал этот ход, невозможно. Это займет вечность. Вы можете посмотреть на разные строки и почерпнуть некоторые идеи, но…

«… никогда нельзя точно узнать, почему он сделал то, что сделал .

Deep Blue мог играть только в шахматы, он не мог делать ничего другого. Однако этот узкий интеллект уже был настолько сложным, что его создатели не могли проследить его индивидуальные решения. Deep Blue не делал того же хода в данной позиции, и это было слишком сложно, слишком сложно или слишком сложно понять его решения. Мы привыкли слышать об отсутствии объяснимости в наших системах сейчас, но тогда это было уже слишком сложно.

До Deep Blue люди выигрывали в шахматы. Машины действительно не могли победить лучших людей - даже близко. Но затем Deep Blue выиграл. Вскоре то же самое сделали и другие компьютеры, и с тех пор они бьют нас. И мы иногда не знаем, как они делают то, что делают. Этот массовый рост является их личностью - независимо от того, каковы наши темпы совершенствования, как только машины начинают совершенствоваться, их обучение и прогресс в конечном итоге измеряются экспоненциально. А у нас нет.

Но на самом деле это не мы против них, хотя это был Гарри Каспаров против Deep Blue. Это была игра, способ проверить, как машины могут учиться, совершенствоваться и играть. Но самая большая победа была для людей, потому что их интеллект создал Deep Blue. А что, если лучшие умы людей будут работать вместе с лучшими машинами?

«Не бойтесь интеллектуальных машин, работайте с ними»

Кажется правильным закончить выступлением Гарри Каспарова на TED и его взглядом на полученный опыт.

«На собственном опыте я узнал, что мы должны столкнуться со своими страхами, если мы хотим получить максимальную отдачу от наших технологий, и мы должны победить эти страхи, если мы хотим получить максимум от нашей человечности. Зализывая раны, я черпал вдохновение в битвах с Deep Blue. Как гласит старая русская пословица, если не можешь их победить, присоединяйся к ним. Затем я подумал, что, если бы я мог играть с компьютером - вместе с компьютером на моей стороне, объединяя наши сильные стороны, человеческую интуицию плюс машинный расчет, человеческую стратегию, машинную тактику, человеческий опыт, машинную память. Может ли это быть идеальная игра? Но в отличие от прошлого, когда машины заменили сельскохозяйственных животных и ручной труд, теперь они приходят на смену людям с высшим образованием и политическим влиянием. И как человек, который сражался с машинами и проиграл, я здесь, чтобы сказать вам, что это отличная, отличная новость. В конце концов, каждая профессия должна будет почувствовать это давление, иначе это будет означать, что человечество перестало прогрессировать. Мы не можем выбирать, когда и где остановится технический прогресс.

Мы не можем замедляться. Фактически, мы должны ускориться. Наши технологии превосходны в устранении трудностей и неопределенностей из нашей жизни, поэтому мы должны искать все более сложные и все более неопределенные проблемы. У машин есть расчеты. У нас есть понимание. У машин есть инструкции. У нас есть цель. У машин есть объективность. У нас есть страсть. Нам не следует беспокоиться о том, что наши машины могут делать сегодня. Вместо этого мы должны беспокоиться о том, что они все еще не могут сделать сегодня, потому что нам понадобится помощь новых интеллектуальных машин, чтобы воплотить наши самые грандиозные мечты в реальность. И если мы терпим неудачу, если мы терпим неудачу, это не потому, что наши машины слишком умны или недостаточно умны. Если мы потерпим неудачу, то это потому, что мы успокоились и ограничили свои амбиции. Наша человечность не определяется какими-либо навыками, такими как размахивание молотком или даже игра в шахматы. Есть одна вещь, которую может сделать только человек. Это мечта. Так что позвольте нам мечтать масштабно ».

Так давайте же мечтать масштабно.

Вот как выглядит результат 1997 года: победила машина, победило и человечество (хотя о последнем мы иногда забываем).

Немного истории (для любопытных и терпеливых умов)

Шахматы - старая игра. Считается, что он возник в Восточной Индии (280–550 гг.). Он достиг Западной Европы и России в 9 веке, а к 1000 году распространился по всей Европе. Он стал популярным, и в 15 веке начали появляться труды по теории шахмат (как играть в шахматы). На протяжении всей истории многие люди говорили много разного о шахматах.

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

Идея создания шахматной машины восходит к 18 веку. Примерно в 1769 году фон Кемпелен построил шахматный автомат под названием «Турок», который стал известен еще до того, как был разоблачен как розыгрыш. В 1912 году Леонардо Торрес-и-Кеведо построил машину под названием El Ajedrecista, которая играла эндшпиль, но была слишком ограниченной, чтобы быть полезной.

Создание электронно-вычислительных машин началось в 1930-х годах. ENIAC, который считается первым электронным компьютером общего назначения, начал работать в 1946 году. К концу 1940-х годов компьютеры использовались в качестве исследовательских и военных инструментов в США, Англии, Германии и бывшем СССР. Компьютерные шахматы представляют собой увлекательную и сложную инженерную задачу.

1940s — 1950s

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

  • В 1950 году Шеннон опубликовал основополагающую статью на тему: а) почему компьютерные шахматы, б) проблемы с компьютерными шахматами, в) возможные решения проблем, Программирование компьютера для игры в шахматы. Он писал: Шахматная машина - идеальная машина для начала, поскольку: (1) проблема четко определена как в разрешенных операциях (ходах), так и в конечной цели (мат); (2) это не так просто, чтобы быть тривиальным, и не слишком сложно для удовлетворительного решения; (3) обычно считается, что шахматы требуют «мышления для умелой игры; решение этой проблемы заставит нас либо признать возможность механизированного мышления, либо еще больше ограничить нашу концепцию мышления; (4) дискретная структура шахмат хорошо вписывается в цифровую природу современных компьютеров. ». Он показал, что если предположить среднюю шахматную партию (40 ходов), то есть 1⁰¹²⁰ возможных ходов - игра может» нельзя победить грубой силой (подход, при котором исследуются все возможности). Ходы нужно выбирать с умом, и в этом поможет отсечение вперед, то есть отсеивание плохих ходов. Это повлияло на первых программистов, которые приложили немало усилий, чтобы найти правила для определения ходов как плохих; позже (к 1970-м годам) они начали замечать, что существует слишком много исключений из этих правил и такого подхода.
  • В 1951 году Алан Тьюринг опубликовал первую шахматную компьютерную программу, которую разработал на бумаге. Он был способен сыграть полную партию в шахматы. Тьюринг рассчитывал шахматные ходы, заглядывая вперед на один ход и подсчитывая ход.
  • В 1956 году была написана шахматная программа MANIAC I. Команду, которая программировала MANIAC, возглавляли Станислав Улам (который изобрел ядерную импульсную двигательную установку и разработал водородную бомбу вместе с Эдвардом Теллером), Пол Штайн, Марк Уэллс, Джеймс Кистер, Уильям Уолден и Джон Паста. Из-за ограниченной памяти MANIAC в программе использовалась шахматная доска 6х6 без слонов. Он реализовал стратегию Шеннона типа А. Он выполнял 11 000 операций в секунду и имел 2400 электронных ламп. На поиск на глубину в четыре хода ушло 12 минут (добавление двух слонов потребовало бы трех часов для поиска на той же глубине).
  • В 1957 году Алекс Бернштейн, сотрудник IBM, создал первую программу, которая могла играть в шахматы полностью. Программа работала на IBM 704 и могла выполнять 42 000 инструкций в секунду. Это был один из последних ламповых компьютеров. Чтобы сделать ход, потребовалось около 8 минут, и была использована стратегия Шеннона типа B (выборочный поиск).
  • Поисковые инновации (1950): поиск Minimax (Шеннон, Тьюринг)
  • Нововведение в поисковой системе (1956 г.): альфа-бета-обрезка (Маккарти)

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

1960s

В 1960-х пионеры искусственного интеллекта Герберт Саймон и Джон Маккарти называли шахматы «дрозофилой искусственного интеллекта», что означало, что шахматы, как и обычная плодовая мушка, представляют собой относительно простую систему, которую также можно использовать для исследования более крупных и сложных реальных объектов. -мирские явления. Компьютерные шахматы были идеальным полигоном для исследований искусственного интеллекта.

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

  • В 1967 году Mac Hack Six Ричарда Гринблатта (представил таблицы транспонирования) стал первой программой, победившей человека в турнирной игре.
  • В 1968 году Маккарти и Митчи поспорили Дэвида Леви (международного мастера) на 1000 долларов, что компьютер победит его к 1978 году.
  • Нововведение в поиске (1966 г.): альфа-бета-обрезка (Коток, Маккарти)
  • Поисковые инновации (1967): таблицы транспонирования (MacHack)

1970s — 1980s

В 1970–1980 годах упор делался на скорость аппаратного обеспечения. В 1950-х и 1960-х годах первопроходцы сосредоточились на шахматной эвристике (эмпирических правилах), чтобы выбрать лучшие следующие ходы. Несмотря на то, что программы 1970-х и 1980-х годов также использовали эвристику, гораздо большее внимание уделялось усовершенствованию программного обеспечения, а также использованию более быстрого и специализированного оборудования. Настроенное аппаратное и программное обеспечение позволяло программам проводить гораздо более глубокий поиск деревьев игр (включая миллионы шахматных позиций), чего люди не могли (потому что не могли) делать.

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

  • В 1977 году Chess 4.6 стал первым шахматным компьютером, добившимся успеха на крупном шахматном турнире.
  • 1978: Ни одна машина не смогла победить Леви (Леви победил Шахматы 4.7 со счетом 4,5–1,5). Леви выигрывает пари, но машина выигрывает против него первую в истории игру.
  • В 1981 году Cray Blitz выиграл чемпионат штата Миссисипи с идеальным счетом 5–0 и рейтингом производительности 2258. В 4-м раунде он победил Джо Зентефа (2262), став первым компьютером, победившим мастера в турнирной игре, и первым компьютером. получить рейтинг мастера.
  • В 1982 году аппаратная шахматистка Кена Томпсона Белль получила звание мастера в США и рейтинг производительности 2250. (Примечание: Кен Томпсон является создателем операционной системы UNIX).
  • 1983, 1986: Cray Blitz (программное обеспечение Роберта Хаятта) выигрывал подряд чемпионаты мира по компьютерным шахматам.
  • В 1985 году Chiptest был построен Фэн-сюнг Су, Томасом Анантараманом и Мюрреем Кэмпбеллом. Он использовал специальный чип генератора движений СБИС и мог выполнять 50 000 движений в секунду.
  • В 1987 году построен Chiptest-M - команда Chiptest удалила ошибки в чипе. Теперь он мог выполнять 500 000 движений в секунду.
  • 1988: HiTech Ганса Берлинера из CMU победил гроссмейстера Арнольда Денкера в матче.
  • В 1988 году Deep Thought Хсу и Кэмпбелл из CMU разделили первое место с Тони Майлзом на чемпионате Software Toolworks Championship, опередив нескольких гроссмейстеров, в том числе. Он также победил гроссмейстера Бента Ларсена в турнирной игре, что сделало его первым компьютером, победившим гроссмейстера в турнире. Он мог выполнять 700 000 движений в секунду. Он получил оценку производительности 2745, наивысшую оценку, полученную компьютерным игроком. IBM взяла на себя этот проект и наняла людей, стоящих за ним.
  • В 1989 году Deep Thought проиграл Гарри Каспарову две выставочные партии.
  • Поисковые инновации (1975): Итеративное углубление (Chess 3.0+)
  • Поисковая инновация (1978): Специальное оборудование (Belle)
  • Поисковая инновация (1983): параллельный поиск (Cray Blitz)
  • Поисковые инновации (1985): параллельная оценка (HiTech)
  • Прогресс в скорости (1980-е годы): в 1980-х микрокомпьютер мог выполнять чуть более 2 миллионов инструкций в секунду.

1990s

В 1990-х годах шахматные программы начали бросать вызов международным мастерам по шахматам, а затем и гроссмейстерам. Эти программы гораздо больше полагались на память и грубую силу, чем на стратегическую проницательность, и они начали последовательно побеждать лучших людей. Некоторые драматические моменты в компьютерных шахматах произошли в 1989 году - два широко уважаемых гроссмейстера были побеждены командами CMU Hitech и Deep Thought.

Исследователи почувствовали, что машины наконец-то могут победить чемпиона мира по шахматам. Это заинтересовало IBM, поэтому они начали работать над этой задачей в 1989 году и построили специализированную шахматную машину под названием Deep Blue. В конечном итоге он победит Гарри Каспарова, лучшего шахматиста среди людей.

Исследователи IBM будут награждены премией Фредкина, премией в размере 100 000 долларов за первую программу, которая победит действующего чемпиона мира по шахматам, которая оставалась невостребованной в течение 17 лет. Эта (и более поздние) победы в компьютерных шахматах разочаровали многих исследователей ИИ, потому что они были заинтересованы в создании машин, которые добивались успеха благодаря стратегиям «общего интеллекта», а не грубой силе. В этом смысле шахматы начали отделяться от исследований искусственного интеллекта.

  • С 1991 по 1995 год IBM работала над Deep Thought II, который был ступенькой к Deep Blue. Это была система с 24 процессорами, и программное обеспечение Deep Thought было переписано для обеспечения параллелизма.
  • В 1992 году ChessMachine Gideon 3.1 (микрокомпьютер) Эда Шредера выиграл 7-й чемпионат мира по компьютерным шахматам, опередив мэйнфреймы, суперкомпьютеры и специальное оборудование.
  • С 1992 по 1998 год: Chess Genius - серия шахматных движков Ричарда Лэнга, написанных для различных архитектур процессоров. Первая версия в 1992 году была выпущена как программа для ПК, работающая под 16-битной MS-DOS. Эти программы выиграли чемпионат мира по шахматам на микрокомпьютерах в 1984, 1985, 1986, 1987, 1988, 1989, 1990, 1991 и 1993 годах.
  • В 1994 году во время цикла Гран-при Intel Chess Genius 3, управляемый Осси Вайнером, выиграл партию в быстрые шахматы (25 минут на каждую сторону) у Гарри Каспарова и сыграл вничью во второй партии, выбив Каспарова из турнира. Это был первый матч (скоростные шахматы), который Каспаров проиграл компьютеру. В следующем туре Chess Genius 3 обыграл Предрага Николича, но затем уступил Вишванатану Ананду. В отличие от Deep Blue, который работал на массово-параллельном специализированном оборудовании, ChessGenius работал на раннем ПК с процессором Pentium.
  • Прогресс в скорости (1990-е годы): к 1990-м годам компьютеры выполняли более 50 миллионов инструкций в секунду.

Этот раздел посвящен этим трем пунктам (Deep Blue был узкоспециализированной машиной, предназначенной для игры в шахматы):

  1. В 1993 году Deep Blue проиграл Бенту Ларсену в матче из четырех игр.
  2. В 1996 году Deep Blue проиграл Гарри Каспарову матч из шести игр (4–2): а) от 1,6 до 2 миллионов позиций в секунду на чип, б) от 50 до 100 миллионов позиций в секунду для системы.
  3. В 1997 году Deep Blue (3,5–2,5) выиграл матч из шести игр у Гарри Каспарова. Поражение Каспарова Deep Blue было его первым поражением в шахматном матче за всю его жизнь: а) улучшенная шахматная фишка с 2 до 2,5 миллионов позиций на фишку, б) 200 миллионов позиций в секунду.

Сейчас:

  • Ни один человек не может играть на лучших компьютерах на равных. У нас (людей) было более 1000 лет, чтобы изобретать, играть и понимать шахматы - машинам было меньше 60 лет, и они намного лучше, чем мы.
  • Ускорение прогресса (сейчас): процессоры в наших столах и телефоне могут выполнять более миллиарда инструкций в секунду.