Подробности

    ЦифроМахИгры и ГоловоломкиЛогика → Шахматная машина - гроссмейстер

    Шахматная машина - гроссмейстер

    шахматы играть

    В ЯНВАРЕ 1988 г. на пресс-конференции в Париже чемпиона мира по шахматам Гарри Каспарова спросили, сумеет ли компьютер выиграть у гроссмейстера до 2000 года? «Ни в коем случае, - ответил он, - и если у кого-нибудь из гроссмейстеров возникнут затруднения в игре с компьютером, я с удовольствием дам им совет».

    ЧЕМПИОН МИРА Гарри Каспаров и компьютер IBM PS/2, с помощью которого осуществляется связь с «Глубокой мыслью», перед началом матча против машины, состоявшегося в конце 1989 г. Каспаров победил, несмотря на гроссмейстерский рейтинг «Глубокой мысли».

    Спустя 10 месяцев после заявления Каспарова, на крупном турнире, состоявшемся в Лонг-Биче (шт. Калифорния), гроссмейстер БентЛарсен, в прошлом претендент на мировую корону, потерпел поражение в поединке с играющей машиной, которую мы сконструировали в качестве своего аспирантского проекта в Университете Карнеги - Меллона. Машина, представляющая собой сочетание программ и специализированной аппаратуры и названная "Deep Thought" («Глубокая мысль»), выиграла еще 5 встреч, одну проиграла и одну свела вничью, разделив с гроссмейстером Энтони Майлсом первое место на турнире. Поскольку машинам не присуждается денежная премия за победу в турнире, Майлс положил в свой карман первый приз в размере 10 тыс. долл. («Глубокая мысль» все же победила Майлса через год в показательном матче.)

    К лету 1990 г., когда трое из нас поступили на службу в корпорацию IBM, «Глубокая мысль» достигла 50%-ного успеха в 10 встречах с гроссмейстерами и 86%-ного успеха в 14 играх против мастеров международного класса. Некоторые из числа этих матчей, а также десятки других игр, сыгранных против менее именитых соперников, проходили под эгидой шахматной федерации США, которая по результатам игр определила шахматный рейтинг машины. Он оказался равным 2552. Этот рейтинг соответствует уровню нижней половины гроссмейстерского диапазона. В то же время средний турнирный игрок имеет рейтинг примерно 1500 очков). Теперь, когда компьютер достиг своей нынешней скорости анализа ситуаций на доске - 750 тыс. позиций в секунду, - рейтинг машины еще более возрос и превысил 2600.

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

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

    С другой стороны, создание компьютера, умеющего играть в шахматы, представляет собой увлекательную техническую проблему. Она была описана на страницах журнала "Scientific American" 40 лет назад Клодом Шенноном, основоположником теории информации (см.: Shannon С.Е., A Chess-Playing Machine, "Scientific American", February, 1950). Приведем выдержку из этой статьи:

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

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

    ПЕРВАЯ попытка практически реализовать идею создания играющей в шахматы машины была предпринята в 60-х годах XVIII в., когда барон Вольфганг фон Кемпелен начал демонстрировать свой шахматный автомат, разъезжая по Европе. Машину прозвали «турком», поскольку ходы на доске выполняла усатая кукла с тюрбаном на голове, которая, очевидно, приводилась в движение замысловатым механизмом, спрятанным в основании машины. Обычно машина играла довольно хорошо и однажды привела в бешенство Наполеона Бонапарта, выиграв у него за 19 ходов. Эдгар Алан По, как и многие другие, впоследствии разгадал секрет автомата: его ходы делал опытный шахматист карликового роста, скрытый в потайном отделении. Однако По неправильно аргументировал свою догадку: по его мнению, эпизодические проигрыши «турка» находились в противоречии с предполагаемым совершенством, присущим настоящему автомату.

    Алан М. Тьюринг, английский математик, пионер информатики и специалист в области криптографии, был в числе первых, кто начал рассматривать перспективу создания компьютера, играющего в шахматы. Однако ему было легче разработать свою простую программу, генерирующую ходы и оценивающую позиции на доске, при помощи карандаша и бумаги, чем прибегнуть к помощи компьютера. Аналогичные попытки совершали Конрад Цузе в Германии и другие ученые, однако основополагающая работа была выполнена Шенноном. Ему удалось развить идеи Джона фон Неймана и Оскара Моргенштерна, которые в рамках своей универсальной теории игр изобрели так называемый минимаксный алгоритм, позволяющий вычислять наилучший ход в заданной ситуации.

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

    Каждый новый слой в ветвящемся дереве анализа охватывает приблизительно в 38 раз большее количество позиций (среднее количество ходов в шахматной позиции), чем предыдущий слой, или в 6 раз большее количество позиций в случае, когда используется метод «альфа-бета-усечения» (см. диаграмму). Поэтому большинство возможных позиций находится на самых внешних частях ветвей дерева игры, «наращиваемых» до тех пор, пока не кончится игра, или время, отпущенное компьютеру, не будет исчерпано. Оценивающий функционал присваивает каждой конечной позиции определенное числовое значение, например 1 для позиции «мат» противнику, - 1 для позиции, в которой выигрывает противник, и 0 для ничейного исхода. Можно регистрировать также и менее явные преимущества и недостатки позиций. Например, компьютер может подсчитывать материальный баланс, выражаемый в количестве фигур и пешек, и вычислять оценку позиций с учетом расположения фигур на доске, положения пешек, занятия ими свободной вертикали, контроля за центральной частью доски и т.д.



  • Способности человека

    50 вопросов, не скучно и очень объемная информация: анализ и обобщение, гибкость мышления, отвлекаемость, скорость и точность восприятия, грамотность и пр

     
  • Источник: http://www.scorcher.ru