Редактор Habrahabr, Geektimes
0,0
рейтинг
26 октября 2014 в 14:42

Разработка → Гарри Каспаров проиграл суперкомпьютеру Deep Blue в шахматы из-за компьютерного сбоя



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

Первая партия в игре была очень сложной и напряженной, у Каспарова было поначалу преимущество, но, начиная с 44 хода, он перестал понимать логику игры машины, и, в итоге, проиграл весь матч. Спустя некоторое время Каспаров даже обвинил инженеров IBM в «читерстве»: манипуляциях с ПО машины, которые и привели к поражению. Спустя 17 лет ситуация прояснилась — Каспаров проиграл из-за сбоя в алгоритме работы компьютера в самой первой партии всего сражения.

Что такое Deep Blue ?


На то время Deep Blue был действительно очень мощной системой. Суперкомпьютер представлял из себя систему с 32-ядерным (32-node) процессором IBM POWER2, каждый из которых был подключён к восьми специализированным шахматным процессорам VLSI, работающим на серверной платформе RS/6000. Код Deep Blue был написан на С, а в качестве операционной системы использовалась IBM AIX. Deep Blue, просчитывал 200 миллионов позиций в секунду, а его пиковая производительность составляла 11,38 гигафлопс.


Немного о Deep Blue от его создателя

Работа по созданию специализированных компьютерных систем велась в IBM, начиная с 1950 года. В 1985 году появился первый компьютер для решения узкоспециализированных шахматных задач. Его построил аспирант университета Карнеги Feng-hsiung Hsu, и эта система получила название ChipTest.

Чуть позже уже Мюррей Кемпбелл вместе с Feng-hsiung Hsu приступили к работе по созданию Deep Blue, став работниками IBM. Первая версия системы проиграла Каспарову в 1989 году. Второе поражение от человека система получила в 1996 году. И уже в 1997 все партии были выиграны машиной.

Проигрыш человека машине


На 44 ходу критической партии Deep Blue сделал, по всеобщему мнению, бессмысленный ход: переставил ладью с D5 на D1. Этот ход не давал никаких перспектив — ни позиционных ни каких-либо иных. Эту партию Каспаров выиграл, но логику компьютера понимать перестал, и последующие две партии (2-ю и 6-ю) сдал, проиграв все сражение.

image

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

Вот так обычная ошибка компьютера, баг, привела к поражению человека в эпохальном шахматном сражении «человек против машины».

По мотивам этой ошибки был снят документальный короткометражный фильм, который можно посмотреть здесь (хабрапарсер не пропускает вставку кода).
marks @marks
карма
170,2
рейтинг 0,0
Редактор Habrahabr, Geektimes
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (103)

  • +10
    Математический склад ума часто шутит со своим обладателем подобным образом. Мы отметаем простые решения, во всем подозреваем подвох и упорно продолжаем искать черную кошку там, где ее нет. Я, например, часто начинаю что-то чинить, не убедившись, что оно действительно сломалось.
    • +79
      Вы описал все что угодно но не «математический склад ума». Мнимость, «поиск черной кошки где ее нет», усложнение, ожидание подвоха и т.п. не имеют ничего общего с математическим складом ума. Это скорее ближе к первобытным инстинктам, эмоциям или характеру, в общем всему тому что является чуть ли не противоположностью «математического склада ума» и образу мышления.

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

        Бойяи, Лобачевский и другие искали именно несуществующиее (по представлениям того времени). И таки нашли, существенно расширив эти самые представления.

        Если бы голый формализм позволял делать открытия в области математики, мы бы уже давно математиков заменили программой по автоматическому выводу теорем. К счастью, доказано, что это сделать невозможно.
        • +1
          программой по автоматическому выводу теорем. К счастью, доказано, что это сделать невозможно.
          Чего? Когда это такое доказали? Мне кажется, вы чего-то путаете.
          • 0
            Теорем, очевидно, бесконечно много. Положим, мы начали искать доказательство некой теоремы A. И мы не знаем, точно ли существует её доказательство. В случае, если доказательства нет, поиск никогда не завершится. Проблема останова является неразрешимой проблемой. Т.е. автоматический вывод теоремы является алгоритмически неразрешимой задачей.

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

            Так что возможно, просто алгоритмически неразрешимо.
            • –3
              В случае, если доказательства нет, поиск никогда не завершится.
              Человек в этом случае также не найдёт доказательства, его ведь нет.

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

              Даже если искать «или доказательство, или опровержение» у нас есть проблемы с тем, что существуют ещё и вообще недоказуемые теоремы и мы не можем быть уверены, что наша не будет относиться к ним.
              И человек столкнётся с теми же проблемами.

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

                Человек также не может решать алгоритмически неразрешимые задачи.


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

                Пока что материальных ресурсов на копирование человеческого сознания вместе со всеми аберрациями у нас нет.
                • +1
                  у него есть догадка, интуиция, использование совершенно неформальных аналогий и так далее

                  Это все теоретически алгоритмизируется. Так как в любом случае сводится к вычислениям. Просто «догадка», «интуиция» и так далее — развитые эвристические механизмы для выделения одних направлений и отсеивания других. Вообще, человек за время своей эволюции выработал множество хаков для экономии вычислительных ресурсов. Правда, эти хаки нередко вызывают ошибки мышления.
                  • 0
                    С этим я не спорю, я спорю с тем, что использование голого формализима (логики первого порядка), лишенного всех этих аберраций и ошибок мышления, приводит к созданию малопродуктивных, нетворческих ИИ.

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

                      Заменить на:
                      С этим я не спорю, я спорю с тем, что использования голого формализима (логики первого порядка), лишенного всех этих аберраций и ошибок мышления, достаточно для создания полноценного ИИ.
                    • +3
                      Я прочитал ещё раз с чего начался наш спор и понял, что вы говорили про то, что нет простого формального метода для
                      открытий в математике, а не то что это в принципе невозможно с помощью компьютера, с чем я и спорил.

                      P.S. Для формализации и автоматической генерации доказательств обычно используют теорию типов, а не логику первого порядка.
          • 0
            Непосредственно следует из уже ставшей популярной теоремы Геделя о неполноте — если мы загрузим в автовыводилку аксиомы арифметики, интегралы и пределы она нам не выведет — это дополнительные понятия, которые всего лишь не противоречат аксиомам.
            • 0
              Если мы загрузим аксиомы арифметики, то из теоремы Гёделя следует, что есть такие арифметические факты (то есть формулирующиеся на языке арифметики), которые нельзя доказать в этой системе аксиом. Например есть какое-нибудь уравнение с кучей переменных, умножений и сложений, у которого нет решений в целых числах, но факт отсутствия решения нельзя доказать используя данную систему аксиом.
              • +1
                Смотрите шире, понимая под формулами — теоремы. Теорема Геделя утверждает, что всегда можно добавить в любую аксиоматику еще одно понятие так, что противоречить уже имеющейся аксиоматике оно не будет.
                Также теорема утверждает, что располагая лишь самой аксиоматикой такое пополнение сделать невозможно.

                Об эту теорему споткнулся сам Гильберт, пытаясь организовать то, о чем вы сейчас утверждаете.
                К 1922 году у Гильберта сложился значительно более обширный план обоснования всей (или хотя бы значительного, общепринятого фрагмента) математики путём её полной формализации с последующим «метаматематическим» доказательством непротиворечивости формализованной математики. Для осуществления этой программы Гильберт разработал строгую логическую теорию доказательств, продолжая работы Фреге с помощью которой непротиворечивость математики свелась бы к доказательству непротиворечивости арифметики. При этом Гильберт использовал только общепризнанные логические средства (логику первого порядка). Его программа оказалась невыполнимой, как впоследствии установил К. Гёдель, хотя послужила значительным стимулом к развитию логики.

                Точка в этом вопросе поставлена 92 года назад.
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Мне кажется тут сыграло роль именно то что вы написали: "… может быть банальная случайность (или причина вообще может лежать в другой плоскости), о чем некоторые исследователи забывают..." — мне кажется именно эта забывчивость и стала причиной.

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

          Все что я хотел сказать: у банальной ошибки может быть миллион причин (в том числе и особый склад ума), хотя чаще всего это банальная «забывчивость», «невнимательность» или что-то еще. Но почему-то всегда приходит кто-то, вешает ярлык «склад ума Х» и объясняет этим все ошибки и вообще всю судьбу человека и всех его бед и удач. Ну не нужно так делать :)
      • +3
        Я неверно выразился. Приводя пример, имел в виду программистов, а не математиков. Просто термин «программист» постеснялся применить к Каспарову. Как там у Купера? «Программисты пожертвуют простотой ради контроля. Обменяют успех на понимание. Они сосредотачиваются на исключительных ситуациях вместо того, чтобы сосредоточиться на типичных»

        Попытка найти логическое обоснование каждому событию играет иногда с нами злые шутки.
      • +1
        Это как на олимпиаде по физике дать задачку без звёздочки из старенького Рымкевича. Ух, сколько мы тогда нарешали!
  • +76
    Важно то что гроссмейстер проиграл, а не то, что ход, который заставил его нервничать был результатом ошибки.
    То что программа может делать нерациональные ходы (по ошибке или по задумке программистов — неважно) только приближает её игру к человекоподобной. Попытки оспорить результат, основанные на мифических «манипуляциях с ПО машины», на мой взгляд, не более чем махание кулаками после драки.
    • +3
      Именно. Проиграл — имей мужество это признать.
      • +11
        А разве Каспаров не признал?
    • 0
      только приближает её игру к человекоподобной
      А мне кажется машина выигрывать как раз таки нечеловеческими способностями. А возможностью просчитать миллионы комбинаций за короткое время.
      • 0
        У человека такой просчет всего лишь реализован экономичнее и «красивее». Применяются хитрые эвристики, отсечение больших кусков от перебора единомоментно и так далее.
        • 0
          Не стоит забывать и о психологии. Это важная составляющая при игре людей между собой.
    • +2
      Да странно как-то вообще ссылаться на «манипуляции с ПО».
      Если кто-то способен так манипулировать с ПО, что получается выигрышный вариант — ну, наймите этого манипулятора в разработчики! Получится «более умный вариант».
      А ещё лучше — раз человек чётко представляет, что нужно «сманипулировать», чтоб запросто обыграть чемпиона мира — дык пусть вдвоём и сыграют! Может это и есть потенциальный чемпион?
  • +5
    Такая ошибка машины лично для меня выглядела бы как чистой воды блеф. Конечно, шахматы — не моя игра, я больше по картам. И даже не столь важно, что этот блеф — результат программной ошибки. Важно, что он сработал ровно так, как полагается блефу.

    Мы строим системы так, чтобы они работали предсказуемо, но в этом случае ошибка или случайное действие привели к решению задачи. Получилось что-то сродни человеческому «озарению», механика которого ещё толком не изучена. Есть над чем задуматься для разработчиков разного рода прикладных машинных разумов.
    • +3
      Не думаю, что слово «блеф» применимо. Если в партии любой ход приведет к ухудшению положения, кроме такого бессмысленного, то сделать его вполне оправдано, пропускать ведь ход нельзя.
      Ну и тот случай сейчас уже не столь важен в смысле развития техники, все равно люди проигрывают в шахматы компьютеру. Да, вопрос первенства становиться шатким в плане чистоты, но это уже детали, на сегодняшний день представляющие чисто академический интерес.
      • +12
        Технически, «блеф» заставил оппонента думать, что есть некий план, которого на самом деле нет. Что соответствует определению.

        Но я имел в виду расширение применимости принципа с шахмат до других вариантов машинного разума. Речь о возможности создания «ошибочных» ходов, шагов и решений для того, чтобы расширить возможности системы. Там, где это допустимо, конечно. Что-то подобное уже обсуждалось на хабре, (ныне на GT: geektimes.ru/post/144144/), но в контексте процессорных ресурсов, а не искусственного разума.

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

        • +3
          В точку! Это сродни мутациям в генетике — случайный фактор, который в дальнейшем может принести пользу, или отфильтрован.
    • –3
      Шахматы — это не та игра, где блеф имеет практический смысл. Если ты сильнее противника, то обыграешь его и обычным образом. Если слабее — то противник просто воспользуется твоим неидеальным ходом. И я сильно сомневаюсь, что ошибка программы могла увеличить её шансы на победу (т. е. ошибка Каспарова была случайностью).

      И мне кажется, что Гай Ритчи любил шахматы исключительно с эстетической точки зрения: серьёзные дяди сидят с умным видом и двигают изящные фигурки (намекаю на фильм «Револьвер»).
    • +1
      Блеф применяется сознательно. Как уловка, чтобы сбить с толку или заманить в ловушку. В случае с той партией, ничего подобного не было. Это был просто ход наобум.
  • +19
    Это они спустя 17 лет логи просмотрели, что ли? Ладно Каспарову в голову не залезешь, но мотивы выбора компьюетрного хода должны бы вроде как быть известными относительно немедленно, как и какой именно сбой произошел. Отдельно доставляет термин «безопасный ход» в шахматах :). Любой ход что-то приносит, как минимум, потерю темпа, если ничего больше.
    • 0
      В данном случае он принёс выигрыш. Правильный был ход, я считаю, полезный (на счёт безопасности не скажу).
      • +14
        В данном случае он принес проигрыш. Эту партию Deep Blue проиграл.
        А в остальном — отмазки Каспарова, не более того.
    • +19
      Каспарову и незачем в голову лезть. Он подробно объяснял, почему проиграл (и это упоминается) — он настроился играть с машиной, которая делает только «выигрышные ходы». И вся его стратегия была заточена под раннее распознавание схемы, которую компьютер ДОЛЖЕН посчитать выигрышной.

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

      Так бывает. Компьютер перед боем начитался Сунь Цзы :)
    • +2
      Это они спустя 17 лет логи просмотрели, что ли?

      Хороший вопрос.
      Спустя 17 лет ситуация прояснилась

      — где прояснилась, кем прояснилась?
    • +7
      Это marks 17 лет спустя узнал, а факт в общем-то довольно известный. Даже я, далекий от шахмат, откуда-то знаю о нём как минимум пару лет.
      • НЛО прилетело и опубликовало эту надпись здесь
  • +29
    Что-то я не понял о какой ошибке речь? Якобы возник сбой и компьютер выполнил безопасный ход? Простите, но это слабо похоже на сбой. Ошибочная ситуация перехвачена и корректно обработана. Это часть алгоритма. Можно ли назвать предусмотренную ситуацию сбоем? Чистая подмена понятий.
    • +7
      Полагаю, правильнее сказать, что возник exception и его обработали. Перевести это как сбой на русский можно, а вот как ошибку уже не в любой ситуации.
    • –1
      Да мало-ли… Потерялся пакет, который шел в ответ из кластера и головная программа выдала экшепшн. Наводка, которую создала баба Галя включив микроволновку. Вспышка на солнце. Да все что угодно могло произойти…
    • +5
      Он считал-считал отведенное на ход время, внезапно обнаружилась ошибка, какая угодно, ECC не сошлось, исключение вылетело. Времени считать заново ход нет, сделал безопасный ход-заглушку. Может быть, так.
  • +8
    Хмм… Машина не побеждает человека в Starcraft? Но ведь у компьютера неограниченные возможности по микроконтролю, один Marine может убить Zealot в таком раскладе. То есть макроконтроль настолько решает?
    • +2
      Только если у Зилота нет «Рывка». Принятие решений на основе разведки, пожалуй, ключевой аспект игры, а компьютер пока что не может проанализировать имеющиеся у противника здания и войска и отреагировать соответствующим образом. Не буду говорить что это невозможно, но подобные алгоритмы никто не писал насколько я знаю. Имеющийся в игре ИИ действует по нескольким заранее предопределенным стратегиям, только исполняет их от «очень хорошо», до «практически идеально», в зависимости от уровня сложности поэтому победить его относительно несложно, если человек обладает должным уровнем навыка, АПМ в т.ч.
      • –2
        По-моему никто не писал алгоритмы (а писать их ой как дорого), потому что никто не будет платить за игру, в которой выйграть не возможно.
        Терры вообще с SCV могут выносить Тосса, если постоянно делать ротацию тех, что под ударом и тех что ремонтируют.

        • +2
          Именно так. Для большинства игр нет проблем сделать непобедимый ИИ.
          Но задача разработчика не в том, чтобы сделать непобедимый ИИ. Задача в том, чтобы сделать ИИ, который будет достаточно интересно играть. В идеале ИИ должен быть адаптивным, чтобы достаточно долго представлять интерес для игрока.
          Старкрафту конечно же не место на картинке. И не потому, что логика игры какая-то особенная, а потому что никто и не пытаеться сделать ИИ способного победить человека.
          Конечно ИИ старика все еще не способен победить топовых игроков… ведь он не развивается с момента создания.
          • 0
            В идеале ИИ должен быть адаптивным, чтобы достаточно долго представлять интерес для игрока.
            Сейчас примерно так и есть, в игре есть вариант игры против ИИ где его сложность растет в зависимости от того как сыграны предыдущие матчи против ИИ. Для человека, который только начал играть, этот режим может представлять интерес достаточно долго.

            Конечно ИИ старика все еще не способен победить топовых игроков… ведь он не развивается с момента создания.
            Не знаю есть ли изменения в коде/логике ИИ, хотя похоже что добавлены несколько стратегий развития для ИИ, но для игрока изменения есть, теперь можно более детально настраивать как будет играть ИИ, будет ли это максимально ранняя атака, тайминговая атака и какой-то иной вариант. Раньше возможности такой настройки не было.
          • +6
            Здрасте, не развивается. Ежегодных соревнований искусственного интеллекта в Starcraft Brood War — мало? Кучи кастомных скриптов AI для всех версий Старкрафта — мало?
            • 0
              Не знал. Спасибо.
        • –1
          SCV, к сожалению, не могут так быстро ремонтировать, чтобы противостоять тоссу. Даже толпа зилотов убъёт толпу постоянно ремонтируемых SCV, не говоря уже о колоссах, имморталах, ну и, тем более темпларах.
          • 0
            SCV раш и толпа зилов — как то странно звучит, правда?
            • 0
              Если ты рашишь SCV, то к моменту твоего прихода на мою базу у меня будет в два раза больше рабов. Никакое идеальное микро тебе не поможет выиграть это сражение. Учти ещё, что деньги на починку SCV у тебя очень быстро кончатся. Ну и моё микро никто не отменял. В общем страта рабочая, но только против другого компа.
              • 0
                Это, конечно, оффтоп, но такой раш я проводил не раз, пусть и не всегда успешно.
                Стратегия ва-банк и не на каждой карте, но работает даже с «корявым» человеческом микро менеджментом.
                • +1
                  Ещё раз говорю, работает такое только против компа или в бронзе. Любой маломальски опытный игрок размикрит такое запросто. Там просто перевес в два и больше раза, никакие починки не спасут.
    • +2
      Мне тоже кажется, что с совершенным микро до макро дело не дойдёт…
    • 0
      Больше всего решают тайминги.
      Для этого нужна огромная база игр и последующий их анализ.
      Необходимо просчитать все возможные варианты развития противника и выяснить точку, в которой он объективно слаб.
      Это если говорить про мидгейм, в макроигре контроль + правильный набор войск, дефболы, вот это всё.
      Проблема в том что состояние игры недетермирвано (точнее детерминировано, но с большим числом свободных переменных).
      Я как-то писал ИИ для одной похожей игры, но там умнее минимакса ничего не придумал, но пришлось писать очень сложную оценочную функцию (модуль ~25к строк), для стархрафта это будет намного сложнее.
    • +5
      Машина не побеждает человека в Starcraft?

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

      К первому Старкрафту есть API, проводятся соревнования AI. Мне, например, понравился AI, который устраивал жуткое микро с муталисками. Его натренировали искать дырки в обороне, пролезать, атаковать, а при приближении опасных юнитов быстро линять, аккуратно отмеряя время атаки. Если человек будет играть против такого AI, то компьютер и хорошего игрока может заставить попотеть, но это только при первой игре. В следующей партии человек просто воспользуется слабыми местами AI (если не опустится для классического «сыра»).

      Во втором Старкрафте прямо из коробки идут хорошие не читерящие AI (честно исследуют карту, честно добывают ресурсы). Они отлично играют, и бешеный APM позволяет им находиться сразу по всей карте. Есть несколько версий AI: один рано атакует, другой захватывает всю карту и т.п. (точнее, карту захватывают все, если позволить, тут вопрос приоритета). Возможностью бешеного микро при запредельном APM изкоробочные AI не пользуются. :)

      Скажем так, с новичками и середнячком современный старкрафтовый AI вполне нормально играет, если игроки не чизят его по-чёрному (например, не ставят оборонные здания посреди минералов на базе противника в начале партии — первые версии AI этим способом легко ломались, на данный момент почти починили). Разнообразие приоритетов плюс возможность подстраиваться под тактику игрока дают вполне вменяемые партии.
      • +1
        А «сыр» это что?
        • +2
          Cheese — нестандартная стратегия, обычно ва-банк, рассчитанная на то, что оппонент офигеет от происходящего и не сможет адекватно отреагировать. AI обычно не ожидает нестандартных стратегий, поэтому для быстрой победы над AI — самое то. Когда вышел Старкрафт 2, самой простой тактикой уничтожения AI любой сложности было поставить зерговские оборонные здания в правильные точки среди вражеских минералов — компьютеру сносило мозг, и он не мог ни атаковать, ни добывать ресурсы. Ну и окружение противника протоссовскими фотонными пушками в пять слоёв, всё такое. А вот с зерглинг рашем AI эффективно справляется.
          • 0
            О, спасибо. А где можно почитать про распространенные стратегии вообще? А то у нас завязался давний спор по поводу, какой сценарий лучше.
            Ой, там же, через main page, извините.
    • 0
      Хмм… Машина не побеждает человека в Starcraft?
      По одной простой причине — машину всерьез никто не научил побеждать, а обучаться она не умеет.
      • +1
        >> Хмм… Машина не побеждает человека в Starcraft?

        Если бы для создания AI Starcraft-а выделяли такие же бюджеты, как на шахматные движки, непобедимого компа уже бы давно создали. Задача сложной не кажется. Все билды на проф уровне формализованы и расписаны по секундам, а значит хорошо описываются алгоритмами.
        • 0
          Безусловно. Тем более в Старкрафт компьютер играет, можно сказать, на своей территории.
  • +53
    Как шахматист заинтересовался Вашей статьёй и решил найти искомую партию.

    В матче 1997 года Deep Blue выиграл у Каспарова 2 партии (и проиграл одну). Знаменитый разгром за 19 ходов в результате шаблонной дебютной жертвы коня на поле e6 в защите Каро-Канн случился в последней встрече. Явно не про эту партию речь. Может имеется ввиду вторая партия, которую компьютер выиграл на 45 ходу?

    Deep Blue — Каспаров, 1997, 2-я партия матча

    В последней партии матча своим 45-м ходом машина неожиданно для всех походила ладьёй с a8 на a6. После размена ферзей белую пешку можно остановить только ценой чёрного слона. Каспаров поверил компьютеру на слово и сдался. Между тем, врываясь ферзём в стан белых 45.… Фе3! относительно несложно достигалась ничья — белому королю не уйти от вечного шаха.

    Другой стрёмный ход ладьёй у компьютера (и это как раз было 44.… Лd5-d1) был сделан в предыдущей, 1-й партии, которую Каспаров выиграл.
    Каспаров — Deep Blue, 1997, 1-я партия матча

    Чёрные только что переместили ладью с 5-й горизонтали на 1-ю. Последовало логичное 45. g6-g7 и команда IBM тут же признала поражение — лавину белых пешек не остановить. Первый бой Каспаров выиграл, но войну в тот момент проиграл. Именно этот ход ладьёй сбил его с толку и он перестал понимать логику компьютера. Следующую партию обескураженный чемпион мира сдаёт, купившись на другой глупый ладейный ход, а в последней встрече матча вообще проигрывает так, как никому никогда не проигрывал.

    • +8
      Спасибо большое за анализ, подкорректировал статью, сославшись на ваш комментарий.
    • 0
      Т.е. можно просто сказать что гроссмейстер эпично протабанил? Странное, какое-то не гроссмейстерское, поведение…
      • +8
        Ничего странного. Все до единого чемпионы делали в матчах на первенство мира глупейшие промахи. И как ни странно именно потому, что они сильнейшие на планете. Стремясь максимально просчитать противника, вникнуть в самую суть мышления соперника, они иногда копали настолько глубоко, что приходили к фундаментально неверным выводам (при этом испытывая высочайшее нервное напряжение) и на ровном месте делали грубейшие зевки, которые бы и перворазрядник не допустил бы.

        В данном ходе Каспаров искал у компьютера исключительно тонкую логику, а между тем никакой особой логики и не было и ход был всего лишь следствием бага. В результате первой партии Каспаров пришёл к ложной уверенности, что компьютер играет исключительно хитроумно. Так и не поняв, что хотел сказать Deep Blue ходом 44.… Лd5-d1 в первой партии, Каспаров решил что и ход 45. Ла8-а6 во второй партии несёт глубочайший сакральный смысл (причём и этот ход был следствием неверного алгоритма в оценке позиции компьютером). Переиграв компьютер как гроссмейстер, Гарри, так сложились звёзды, вчистую проиграл компьютеру психологически :))) Если точнее — психологически он проиграл сам себе.
        • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            Ему явно заплатили, чтобы он проиграл. И по лицу чётко видно, что у него перед глазами стоит кадр из присланного похитителями ролика со связанными женой и дочерью.
          • +1
            куда мотать?
    • 0
      Следующую партию обескураженный чемпион мира сдаёт, купившись на другой глупый ладейный ход, а в последней встрече матча вообще проигрывает так, как никому никогда не проигрывал.

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

      А последнюю партию, как по мне, необходимо просто занести в разряд банальных ошибок, случающихся у всех — все же, не думаю, что Каспаров совершил ту элементарную ошибку, будучи обескураженным от непонятной ему компьютерной логики.
    • 0
      Позволю себе не согласиться с тем, что
      врываясь ферзём в стан белых 45.… Фе3! относительно несложно достигалась ничья — белому королю не уйти от вечного шаха.


      45… Фe3
      46 Фd7+ Крg8
      47 Ф:d6

      И белые угрожают следующим ходом взять ладью с шахом.

      Или, если черные закрываются слоном:
      46… Сe7
      47 d6

      Белые грозят 48 Фe6+ с матом через 6 ходов максимум.

      В обоих случаях черным не хватает времени, чтобы взять белого слона, а без этого не получится вечного шаха:

      47… Фf4+
      47 Крg1 Фc1+
      48 Крh2 Фf4+
      49 g3 Фd2+
      50 Сg2

      И черные больше шаховать не могут.

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

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

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

        В целом, у белых слабы все чёрные поля в их лагере, по ним и происходит вечное нападение чёрным ферзём на белого монарха. В одном из вариантов белые ходят пешкой h3-h4 (для того чтобы спрятаться королём на h3, прикрыть его от шахов пешкой g2-g3 и слоном Ce4-g2). На это чёрные отвечают h6-h5 и у чёрного ферзя помимо чернопольных клеток появляется ещё и белое поле, откуда он может согнать короля с бункера на h3 — поле g4. Как-то так… Как я уже сказал, мне дискутировать на эту тему лень.
  • 0
    А может сбой произошел от того, что это была например 200 000 001 комбинация расчета дальнейшей игры? А компьютер был запрограммирован на обязательный ход менее чем за секунду(ну чтобы не выглядеть слабым) И он просто не успел все рассчитать?
    • +2
      Комментарий про Бритву Оккама.
    • 0
      Времени на партию даётся достаточно, чтобы у игрока было хотя бы 30 секунд на ход. Насколько я понимаю, там был фишеровский контроль времени.
  • 0
    Задам вопрос не очень по теме. Если DeepBlue в 95 году на соответствующем железе оценивал 200 млн комбинаций в секунду, то какая примерно производительность у него будет при перекомпиляции под какой-нибудь i7? Хоть ориентировочно
    • +2
      Неравноценное сравнение. DeepBlue использовал специализированные шахматные процессоры, которые, работая на 25МГц, в разы обгоняли ширпотребные процессоры, работавшие на сотнях мегагерц.

      То есть это как сравнивать i7 с майнинговой фермой, сработанной на заказных чипах, способных только перебирать хэши.

      Потому и меряют его производительность не в традиционных флопсах, а в позициях в секунду.
    • +4
      Современные шахматные программы на Core2Duo анализируют порядка 5 миллонов комбинаций в секунду. На последних десктопных восьмиядерниках полагаю все равно меньше сотни миллионов в секунду будет. Но с другой стороны современные программы делают более глубокий анализ и эти <100 миллионов комбинаций на практике сильно переигрывают 200 миллионов от Deep Blue.
      • 0
        Спасибо, что-то такое я предполагал. Еще бы взглянуть на ассемблер этих процессоров. Кстати, VLSI это всего-навсего «сверхвысокая степень интеграции»
  • –8
    Позанудничаю немного:

    В таблице «Difficulty of various games for computers» на мой взгляд последняя категория, та где компьютер может никогда не переиграть человека, вообще некорректна.
    Snakes and Ladders основана целиком на вероятности. В эту игру попросту нельзя играть лучше или хуже.
    Seven minutes in heaven вообще не предполагает концепции выйгрыша или пройгрыша.
    Calvinball не имеет четких правил и предполагает физическую активность. Это как играть в футбол с роботом, только ему еще и новые правила нужно объяснять каждый раз перед игрой.
    Про МАО ничего не знаю к сожалению.
    • +2
      Так это же юмор такой был в оригинальной картинке.
    • +4
      выЙгрыша.

      Компьютеру просто не интересны «Семь минут в раю» (выигрыш там есть, хе-хе).
      • 0
        Да, с «АндроЙдом» у меня та же болезнь :) Пожалуй спасут только интервальные повторения.
  • +29
    На третьем ходу выяснилось, что гроссмейстер играет восемнадцать испанских партий. В остальных двенадцати черные применили хотя и устаревшую, но довольно верную защиту Филидора. Если б Остап узнал, что он играет такие мудреные партии и сталкивается с такой испытанной защитой, он крайне бы удивился. Дело в том, что великий комбинатор играл в шахматы второй раз в жизни.
    Сперва любители, и первый среди них — одноглазый, пришли в ужас. Коварство гроссмейстера было несомненно.
    С необычайной легкостью и безусловно ехидничая в душе над отсталыми любителями города Васюки, гроссмейстер жертвовал пешки, тяжелые и легкие фигуры направо и налево. Обхаянному на лекции брюнету он пожертвовал даже ферзя. Брюнет пришел в ужас и хотел было немедленно сдаться, но только страшным усилием воли заставил себя продолжать игру.
  • +2
    Искусственный интеллект под видом сбоя? :)
  • 0
    И уже в 1997 все партии были выиграны машиной.

    Это как? Вроде бы как Каспаров — Deep Blue +1-2=3, то есть ну никак не «все партии».
  • 0
    Еще со времен института отложилось, что возможен подобный баг в голове:
    Ситуация на экзамене. Преподаватель задает дополнительный вопрос. Вроде бы простой. Начинаешь сомневаться, в том что он без подвоха. И не верится, что препод на вытягивает на оценку выше. Думаешь: «Чертпобери! Валит *ука!». А на самом деле оказывается, что это и был простой вопрос. И уходишь с экзамена в оценкой на бал(два) ниже.
  • +1
    не баг, а фича
  • +9
    Пытаюсь понять нововведения хабра: разве это не должно быть в гиктаймс не?
  • +8
    Они научили машину блефовать.
    В момент «безопасного хода», надо чтобы на мониторе загорался «покер фэйс».
    • –7
      Знаете, что странно?
      За этот комментарий, мне кто-то слил карму…
  • +1
    Помню партии Крамника против Deep Fritz. Оказывается, по-правилам экземпляр программы предоставлялся гроссмейстеру за полгода для изучения. Поторчав с программой, Крамник находит выигрышную комбинацию, практически всегда с проходными пешками — компьютер их плохо видит, и демонстрирует потом решение на чемпионате. Достаточно всего одной-двух выигрышных партий, остальные сливаются в ничью.
    Более того, все программы снабжены базами финалов, до 6-й или 7-й фигуры. Во всех подобных чемпионатах, игра заканчивается, если партия входит в финал, и компьютер показывает результат. Однако результат верен, если человек не ошибется в финале, что даже для гроссмейстеров далеко не всегда верно.
    • 0
      Нет. «Эндшпильные таблицы Налимова» и гроссмейстеры прекрасно знают. Конечно не все алгоритмы, а просто позиции — выигрышная, ничейная или проигрышная. Ведь подавляющее большинство партий не играется до самого мата — а просто до понимания проигрышности позиции. Ну и лажануть в эндшпиле для гроссмейстера… Неужто он не сможет убежать королём от коня? Или понять что против ладьи не попрёшь (утрировано). Суть серьёзной игры в шахматы по большей части строится на выходе из дебюта в миттельшпиль (сами дебюты хорошо известны, но вот их развитие...) — дальше уже по большей части на игра идёт на автомате.
  • 0
    Забавно, если бы этот ход не помог компьютеру — читали бы мы сейчас статью: «Deep Blue проиграл Гарри Каспарову из-за компьютерного сбоя»: о)
  • 0
    Очень напомнило такой маневр :)
    ps.vk.me/c538119/u2000033263/docs/192a19aee3ee/file.gif

    • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    А я вот помню, что этот второй матч, ака матч-реванш, был совсем отличен от первого. Во-первых, компьютер обслуживался коммандой… в общем кучей людей, во-вторых, компьютеру давалось неограниченное время на обдумывание хода, в отличие от гроссмейстера. Там были еще какие-то, видимо менее запоминающиеся вещи, но факт того, что человек проиграл не совсем машине, я помню.
    • 0
      компьютеру давалось неограниченное время на обдумывание хода

      Был обычный классический контроль.
  • 0
    Пардон, но в статье слишком много, скажем так, неточностей. Во-первых, причины поражения Каспарова не могут быть объяснены компьютерным сбоем, это слишком примитивно. Тогда Каспаров высказал сомнение, что отдельные ходы могли быть сделаны машиной, а не человеком. Особенно это касалось дебютной жертвы фигуры в последней партии, и тут его понять можно, потому что в 1997 году даже суперкомпьютеры очень неохотно жертвовали материал за неочевидную (для них тогда) компенсацию. А говорить, что Каспаров проиграл из-за бага, или потому что перестал понимать логику компьютера — это смешно. Помимо всего прочего, Дип Блю играл уже вполне неплохо).
    Что означает фраза «И уже в 1997 все партии были выиграны машиной» — ? Финальный счёт был 3,5-2,5 в пользу Дип Блю.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.