История развития компьютерных шахмат. Компьютерные шахматы

Компьютерные шахматы - это... Что такое Компьютерные шахматы?

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

История

Шахматный компьютер

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

Создание механических шахматных автоматов прекратилось с появлением цифровых компьютеров в середине XX века. В 1951 году Алан Тьюринг написал алгоритм, с помощью которого машина могла бы играть в шахматы, только в роли машины выступал сам изобретатель. Этот нонсенс даже получил название — «бумажная машина Тьюринга». Человеку требовалось более получаса, чтобы сделать один ход. Алгоритм был довольно условный, и сохранилась даже запись партии, где «бумажная машина» Тьюринга проиграла одному из его коллег[1]. За отсутствием доступа к компьютеру, программа ни разу не проверялась в работе.

Примерно в это же время, в 1951 году, математик Клод Шеннон написал свою первую статью о шахматном программировании. Он писал: «Хотя, возможно, это и не имеет никакого практического значения, сам вопрос представляется теоретически интересным, и будем надеяться, что решение этой задачи послужит толчком для решения других задач аналогичной природы и большего значения». Шеннон также отметил теоретическое существование лучшего хода в шахматах и практическую невозможность его найти.

Следующим шагом в развитии шахматного программирования стала разработка в ядерной лаборатории Лос-Аламоса в 1952 году на компьютере Maniac 1 (тактовая частота 11 кГц) шахматной программы для игры на доске 6x6, без участия слонов. Известно, что этот компьютер сыграл одну партию против сильного шахматиста, она продолжалась 10 часов и закончилась победой шахматиста. Ещё одна партия была сыграна против девушки, которая недавно научилась играть в шахматы. Машина победила на 23-м ходу. Сейчас это выглядит смешно, но для своего времени это было большое достижение.

В 1957 году Алексом Бернстейном была создана первая программа для игры на стандартной шахматной доске и при участии всех фигур[2].

Важное событие для компьютерных шахмат произошло в 1958 году, когда Аллен Ньюэлл, Клифф Шоу и Герберт Саймон разработали алгоритм уменьшения дерева поиска, названный Альфа-бета отсечение[2][3], на основе которого построены функции поиска всех сильных современных программ.

Первой же машиной, которая достигла уровня шахматного мастера, была Belle, законченная в 1983 г. Джо Кондоном и Кеном Томпсоном. «Belle» был первым компьютером, спроектированным только для игры в шахматы. Его официальный рейтинг Эло был 2250, таким образом, это была самая сильная шахматная машина своего времени.

В 1994 Гарри Каспаров проиграл программе Fritz 3 турнирную блиц-партию в Мюнхене. Программа также выиграла у Вишванатана Ананда, Бориса Гельфанда и Владимира Крамника. Гроссмейстер Роберт Хюбнер отказывался играть против программы и автоматически проиграл. Каспаров сыграл второй матч с Fritz и победил с 4 выигрышами и 2 ничьими.

В феврале 1996 года Гарри Каспаров победил шахматный суперкомпьютер Deep Blue со счетом 4-2. Этот матч выдающийся тем, что первую партию выиграл Deep Blue, автоматически став первым компьютером, победившим чемпиона мира по шахматам в турнирных условиях. Deep Blue вычислял 50 миллиардов позиций каждые три минуты, в то время как Каспаров 10 позиций за это же время. В Deep Blue было 200 процессоров. С тех пор шахматные энтузиасты и компьютерные инженеры создали много шахматных машин и компьютерных программ.

Шахматные компьютеры сейчас доступны по очень низкой цене. Появилось много программ с открытыми кодами, в частности Crafty, Fruit и GNU Chess, которые можно свободно загрузить из сети Интернет и которые могут победить многих профессиональных шахматистов. А лучшие коммерческие программы, например, Shredder или Fritz уже превысили уровень людей-чемпионов. Сейчас же движок Houdini находится на первом месте в таких компьютерных рейтинг-листах, как CEGT, CCRL,SCCT и CSS.

Мотивация

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

А. С. Кронрод определил роль компьютерных шахмат известной фразой: «шахматы — это дрозофила искусственного интеллекта». Аналогия лежит на поверхности: шахматы представляют собой безусловно интеллектуальную, но при этом чётко формализованную, простую по структуре и компактную задачу, то есть являются удобным объектом лабораторных исследований в искусственном интеллекте, так же как мушка-дрозофила, благодаря малым размерам, плодовитости и быстрой смене поколений является удобным лабораторным объектом для изучения наследственности. Действительно, на шахматах были апробированы многие известные методы и направления искусственного интеллекта, в том числе методики оптимизации перебора (уход от «комбинаторного взрыва» при просчёте вариантов вперёд на несколько ходов), распознавание образов, экспертные системы, логическое программирование.

Однако, к удивлению и огорчению многих, шахматы мало приблизили людей к созданию машин с человекоподобным интеллектом. Современные шахматные программы, по сути, остановились на наиболее примитивном этапе интеллектуальной деятельности: они исследуют огромное число возможных ходов обоих игроков, применяя различные методы усечения дерева перебора, в том числе относительно простую функцию оценки. В сочетании с базами данных, хранящими заранее рассчитанные готовые варианты дебютов и эндшпилей, благодаря быстродействию и объёмам памяти современных компьютеров эти методы уже обеспечивают игру компьютера в шахматы на гроссмейстерском уровне. По этим причинам компьютерные шахматы больше не имеют такого большого академического интереса. Роль «дрозофилы искусственного интеллекта» перешла к другим интеллектуальным играм, таким как, например, го. Гораздо больший, чем в шахматах, объём перебора вариантов в таких играх ограничивает возможности использования простых методов и требует от ученых применять более умозрительные подходы к игре.

Проблемы реализации

Разработчики шахматных программы должны сделать ряд решений при их написании. Они включают:

Способ изображения шахматной доски — представление цельной позиции как структуры данных.
Методы поиска — поиск возможных лучших ходов.
Листовая оценка — оценка позиции без учета дальнейших ходов.

См. также:

Структура шахматной программы

Первое исследование на тему шахматного программирования сделал в 1950 году американский математик Клод Шеннон, успешно предусмотревший два основных возможных метода поиска, которые можно использовать, и назвал их «Тип А» и «Тип B».

Программы типа А используют так называемый подход «грубой силы» (brute force), изучая каждую возможную позицию на фиксированную глубину с помощью алгоритма Минимакс. Шеннон утверждал, что этот метод будет непрактичным по двум причинам.

Во-первых, с примерно тридцатью ходами, возможными в типичной позиции, на изучение около 10 млрд узловых позиций (просчет примерно на три хода вперед для обеих сторон), надо примерно 16 минут, даже в «очень оптимистичном» случае, когда компьютер сможет оценивать миллион позиций в секунду. (Чтобы достичь этого понадобилось сорок лет.)

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

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

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

Основные алгоритмы современных программ

Примерная схема осуществления альфа-бета отсечения слабых ходов

Компьютерные шахматные программы рассматривают шахматные ходы как игровое дерево. Теоретически, они должны оценивать все позиции, которые возникнут после всех возможных ходов, затем все возможные ходы после этих ходов и т. д. Каждый ход одного игрока называется «узел». Перебор ходов продолжается, пока программа не достигает максимальной глубины поиска или определяет, что достигнута конечная позиция (например мат или пат). Уже на основании оценки позиции выбирает оптимальную стратегию. В каждой позиции количество возможных ходов игрока примерно равно 35. Для полного анализа четырёх ходов (по два хода каждого игрока) нужно исследовать около полутора миллиона возможностей, для шести — почти два миллиарда. Анализ на 3 хода вперед — очень мало для хорошей игры.

Программисты пытаются по-разному ограничить массу ходов, которые надо перебрать (обрезание дерева поиска — game tree pruning). Самым популярным является альфа-бета отсечение, в котором не рассматриваются позиции, имеющие меньшую оценку, чем уже оценённые.

Приблизительная программная реализация:

private int AlphaBeta(int color, int Depth, int alpha, int beta) { if (Depth == 0) return Evaluate(color); int bestmove; Vector moves = GenerateMoves(); for(int i = 0; i < moves.size(); i++) { makeMove(moves.get(i)); eval = -AlphaBeta(-color, Depth-1, -beta, -alpha); unmakeMove(moves.get(i)); if(eval >= beta) return beta; if(eval > alpha) { alpha = eval; if (Depth == defaultDepth) { bestmove = moves.get(i); } } } return alpha; }

Пример первого вызова:

AlphaBeta(1, 6, Integer.MIN_VALUE, Integer.MAX_VALUE);

При первом вызове метод (функция) вызывается с максимальным окном. При рекурсивных вызовах переменные alpha и beta меняются местами с инверсией знака и «сужают» массу поиска.

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

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

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

Во-первых, это оценка материала: каждая пешка — это 1 пункт, слон и конь — по 3, ладья — 5, ферзь — 9. Король иногда ценится в 200 пешек (Статья Шеннона) или 1 000 000 000 пешек (программа разработана в СССР в 1961 г.), чтобы гарантировать, что мат перевесит все другие факторы. Более развитые функции имеют точнее установленные коэффициенты ценности фигур, которые зависят от стадии партии и позиции на шахматной доске.
Во-вторых, позиционное преимущество, которое зависит от положения фигур на доске; например, заблокированная фигура ценится меньше, чем свободная; оценивается также безопасность короля, господство над центром доски и т. д.; существуют также более сложные системы оценки (некоторые даже используют знания о нейронных сетях), однако даже такая простая функция позволяет программе играть очень сильно; в шахматах главная проблема заключается не в оценке позиции, а в переборе дерева возможных ходов.

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

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

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

Компьютер против Человека

Даже в 70-80-х гг оставался открытым вопрос, когда шахматная программа сможет победить сильнейших шахматистов. В 1968 г. Международный гроссмейстер Дэвид Леви пошел на пари, что ни один компьютер не сможет обыграть его в течение ближайших десяти лет. Он выиграл пари, победив в 1978 г. программу Chess 4.7 (сильнейший в то время компьютер), но сознавал, что осталось не так уж много времени до того, когда компьютеры будут побеждать мировых чемпионов. В 1989 г. программа Deep Thought выиграла у Леви.

Но программы все еще были значительно ниже уровня Чемпиона мира, который продемонстрировал Гарри Каспаров, победив ту же Deep Thought дважды в 1991 г.

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

В мае 1997 года усовершенствованная версия Deep Blue нанесла поражение Каспарову со счетом 3,5-2,5. Позже IBM обвинили, что во время партий фирма использовала человека-шахматиста, чтобы увеличить стратегическую силу компьютера.[источник не указан 273 дня]

В 2003 году был снят документальный фильм, в котором исследовались эти упреки, который называется «Матч окончен: Каспаров и машина» (англ. Game Over: Kasparov and the machine), в котором утверждалось, что сильно раскрученная победа Deep Blue подстроена для увеличения рыночной стоимости IBM.

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

Матч Deep Blue против Каспарова 1996, первая партия.

Финальная позиция.

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

Имея все большую вычислительную мощность, шахматные программы, запущенные на персональных компьютерах, стали достигать уровня лучших шахматистов. В 1998 г. программа Rebel 10 победила Вишванатана Ананда, который тогда занимал второе место в мире. Однако не все партии игрались со стандартным временным контролем. Из восьми партий матча, четыре играли с блиц-контролем (пять минут плюс пять секунд за каждый ход), которые Rebel выиграл со счетом 3-1. Еще две игры были с полу-блиц контролем (пятнадцать минут на каждого), которые программа также выиграла (1,5-1). Наконец, две последние партии были сыграны со стандартным турнирным временным контролем (два часа на 40 ходов и час на остальные партии) и тут выиграл уже Ананд со счетом 0,5-1,5. К тому времени в быстрых партиях компьютеры играли лучше людей, но при классическом временном контроле преимущество было уже не так велико.

В 2000 г. коммерческие шахматные программы Junior и Fritz смогли свести в ничью матчи против предыдущих мировых чемпионов Гарри Каспарова и Владимира Крамника.

В октябре 2002 Владимир Крамник и Deep Fritz соревновались в матче из восьми партий в Бахрейне. Матч закончился вничью. Крамник выиграл вторую и третью партии, используя традиционную противокомпьютерную тактику — играл осторожно, имея целью долгосрочное преимущество, которое компьютер не может увидеть в своем дереве поиска. И все же Fritz выиграл пятую партию после грубой ошибки Крамника. Шестую партию много турнирных комментаторов назвали очень увлекательной. Крамник, имея лучшую позицию в начале миттельшпиля, попытался пожертвовать фигурой, чтобы создать сильную тактическую атаку (такая стратегия — очень рискованная против компьютеров). Fritz нашел сильную защиту, и эта атака значительно ухудшила позицию Крамника. Крамник сдал игру, веря, что партия проиграна. Однако последующий анализ показал, что Fritz вряд ли смог бы довести игру до своего выигрыша. Последние две партии закончились вничью.

В январе 2003 г. Гарри Каспаров играл против программы Junior в Нью-Йорке. Матч закончился со счетом 3-3.

В ноябре 2003, Гарри Каспаров играл с X3D Fritz. Матч закончился со счетом 2-2.

В 2005 г., Hydra, специальный шахматный компьютер с 64 процессорами, победил Майкла Адамса, шахматиста, который в то время был на седьмом месте в мире по рейтингу ЭЛО, в матче из шести партий со счетом 5,5-0,5 (хотя домашняя подготовка Адамса была намного ниже, чем у Каспарова в 2002 году). Некоторые комментаторы верили, что Hydra наконец получит несомненное преимущество над лучшими шахматистами.

В ноябре-декабре 2006, Владимир Крамник играл с программой Deep Fritz. Матч закончился со счетом 2-4.

Базы данных эндшпиля

Подробнее Базы данных эндшпиля

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

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

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

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

В 2002 г. были опубликованы основные форматы эндшпильных баз данных, включая Edward Tablebases, De Koning Endgame Database и Nalimov Endgame Tablebases, которые теперь поддерживают многие шахматные программы, такие как Rybka, Shredder и Fritz. Эндшпили с пятью или менее фигурами были полностью проанализированы. Эндшпили с шестью фигурами были проанализированы, за исключением позиций с пятью фигурами против одинокого короля. Марк Буржуцкий и Яков Коновал проанализировали некоторые эндшпили с семью фигурами. Во всех этих эндшпильных базах данных считается, что рокировка невозможна.

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

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

Базы эндшпиля Налимова на пять фигур, которые используют методы современной компрессии, занимают 7.05 Гб на жестком диске. Для хранения баз данных на шесть фигур надо примерно 1.2 терабайт. Оценено, что полная семифигурная база данных потребует больше места, чем будет доступно рядовым пользователям в ближайшем будущем.

Игра против программ

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

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

Шахматы и другие игры

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

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

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

Хронология компьютерных шахмат

1769, Вольфганг Кемпелен, построил шахматиста-автомата, который стал одной из величайших мистификаций этого периода.
1868, Чарльз Хупер представил автомат Ajeeb — в котором тоже был спрятан шахматист.
1912, Леонардо Торрес Квеведо построил машину, которая могла играть эндшпиле Король + Ладья против короля.
1948, книга Норберта Винера «Кибернетика» описывает, как можно создать шахматную программу, используя поиск минимакса с лимитированной глубиной и оценочной функцией.
1950, Клод Шеннон опубликовал «Программирование компьютера для игры в шахматы», одну из первых статей о компьютерных шахматах.
1951, Алан Тьюринг разработал на бумаге первую программу, способную играть в шахматы.
1952, Дитрих Принц разработал программу, которая решала шахматные задачи.
1956, г. Лос-Аламос — первая подобная шахматам игра, которую смогли играть программы, разработанная Полом Штейном и Марком Уэллсом для компьютера MANIAC I.
1956, Джон Маккарти изобрел альфа-бета алгоритм поиска.
1958, NSS стала первой программой, которая использовала альфа-бета алгоритм поиска.
1958, первыми шахматными программами, которые могли играть полные шахматные партии, стали одна, созданная Алексом Бернштайн и вторая российскими программистами.
1962, первой программой, которая играла правдоподобно стала Kotok-McCarthy.
1966—1967, первый матч между программами.
1967, Mac Hack Six, разработанная Ричардом Гринблатт стала первой программой, победившей человека при турнирном контроле времени.
1970, первый год Североамериканского Компьютерного Шахматного Чемпионата.
1974, Каисса выиграла первый Всемирный Компьютерный Шахматный Чемпионат.
1977, создана первая шахматная программа для микрокомпьютеров CHESS CHALLENGER.
1977, создание Международной Компьютерной Шахматной Ассоциации.
1977, Chess 4.6 стал первым шахматным компьютером, который добился успеха в главном шахматном турнире.
1980, первый год Всемирного микрокомпьютерного Шахматного Чемпионата.
1981, Cray Blitz выиграл Чемпионат Штата Миссисипи с 5-0 счетом и рейтингом производительности 2258.
1982, аппаратный шахматный игрок Кена Томпсона Belle зарабатывает титул мастера США.
1988, HiTech, разработанная Гансом Берлинером и Карлом Ебелингом, выигрывает матч против гроссмейстера Арнольда Денкер со счетом 3.5 — 0.5.
1988, Deep Thought делит первое место с Тони Майлзом в Чемпионате ПО Toolworks, впереди бывшего чемпиона мира Михаила Таля и нескольких гроссмейстеров, в частности Самуэля Решевского, Уолтера Брауна, Эрнста Грюнфельда и Михаила Гуревича. Программа также нанесла поражения гроссмейстер Бенту Ларсену, и стала первым компьютером, который выиграл у гроссмейстера в турнире.
1992, впервые микрокомпьютер, Chessmachine Gideon 3.1, разработанный Эдом Шредером (Ed Schröder) выигрывает VII Всемирный Компьютерный Шахматный Чемпионат впереди суперкомпьютеров.
1997, Deep Blue выиграл матч против Гарри Каспарова 2-1 = 3.
2002, Владимир Крамник свел вничью матч против Deep Fritz.
2003, Каспаров сыграл вничью матч против Deep Junior.
2003, Каспаров сыграл вничью матч против X3D Fritz.
2005, Hydra выиграла матч с Майклом Адамсом со счетом 5,5-0,5.
2005, команда компьютеров (Hydra, Deep Junior и Fritz), обыграла 8.5-3.5 команду из шахматистов (Веселин Топалов, Руслан Пономарев и Сергей Карякин), которые имели средний ЭЛО рейтинг 2681.
2006, чемпион мира, Владимир Крамник, побежден 4-2 Deep Fritz.

Теоретики компьютерных шахмат

См. также

Примечания

Ссылки

dic.academic.ru

Компьютерные шахматы | Энциклопедия шахмат

В 1957 году Алексом Бернштейном была создана первая программа для игры на стандартной шахматной доске и при участии всех фигур[2].

Важное событие для компьютерных шахмат произошло в 1958 году, когда Аллен Ньюэлл, Клифф Шоу и Герберт Саймон разработали алгоритм уменьшения дерева поиска, названный Альфа-бета-отсечение[2][3], на основе которого построены функции поиска всех сильных современных программ.

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

Шахматные компьютеры сейчас доступны по очень низкой цене. Появилось много программ с открытыми кодами, в частности Crafty, Fruit и GNU Chess, которые можно свободно загрузить из сети Интернет и которые могут победить многих профессиональных шахматистов. Лучшие коммерческие и бесплатные программы, например, Shredder, Fritz или Komodo уже превысили уровень людей-чемпионов. Движок с открытым кодом Stockfish находится на высоких местах в таких компьютерных рейтинг-листах, как CEGT, CCRL, SCCT и CSS, благодаря совместной разработке и тестированию многих людей[4].

Проблемы реализации Править

Разработчики шахматных программ должны сделать ряд решений при их написании. Они включают:

Способ изображения шахматной доски — представление цельной позиции как структуры данных.
Методы поиска — поиск возможных лучших ходов.
Листовая оценка — оценка позиции без учета дальнейших ходов.

См. также:

Шахматные компьютеры Править

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

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

В СССР с середины 1980-х годов выпускались потребительские шахматные компьютеры «Электроника ИМ-01», «Электроника ИМ-05», «Электроника ИМ-29» («Шахматный партнёр»), «Интеллект-01», «Интеллект-02», «Дебют», «Феникс», «100 лет Новосибирск» и другие.

Большинство программ основано на методе перебора ходов, существуют программы, основанные на эвристических методах. Попытка создать настоящую шахматную программу, на основе алгоритма шахматного мастера, предпринималась экс-чемпионом мира М. Ботвинником и его ассистентами-программистами — Б. Штильманом и А. Резницким.

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

Структура шахматной программы Править

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

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

Основные алгоритмы современных программ Править

Компьютерные шахматные программы рассматривают шахматные ходы как игровое дерево. Теоретически, они должны оценивать все позиции, которые возникнут после всех возможных ходов, затем все возможные ходы после этих ходов и т. д. Каждый ход одного игрока называется «узел». Перебор ходов продолжается, пока программа не достигает максимальной глубины поиска или определяет, что достигнута конечная позиция (например мат или пат). Уже на основании оценки позиции выбирает наилучшую стратегию. В каждой позиции количество возможных ходов игрока примерно равно 35. Для полного анализа четырёх ходов (по два хода каждого игрока) нужно исследовать около полутора миллиона возможностей, для шести — почти два миллиарда. Анализ на 3 хода вперёд — очень мало для хорошей игры.

Программисты пытаются по-разному ограничить количество ходов, которые надо перебрать (обрезание дерева поиска — game tree pruning). Самым популярным является альфа-бета-отсечение, в котором не рассматриваются позиции, имеющие меньшую оценку, чем уже оценённые.

Приблизительная программная реализация:

Пример первого вызова:

При первом вызове метод (функция) вызывается с максимальным окном. При рекурсивных вызовах переменные alpha и beta меняются местами с обращением знака и «сужают» массу поиска.

Вторым распространённым способом является итерационное заглубление. Сначала перебирается дерево игры до определенной глубины, после чего выделяется несколько лучших ходов. Затем программа оценивает эти ходы применительно к большей глубине, чтобы узнать больше об их последствиях. Эта операция повторяется до наилучшего с точки зрения программы хода. Такой подход позволяет быстро отбросить немалый процент неперспективных вариантов игры. Например, не имеет смысла исследовать, что произойдет, когда обменять ферзя на пешку, если в позиции есть лучшие ходы.

Во-первых, это оценка материала: каждая пешка — это 1 пункт, слон и конь — по 3, ладья — 5, ферзь — 9. Король иногда ценится в 200 пешек (Статья Шеннона) или 1 000 000 000 пешек (программа разработана в СССР в 1961 г.), чтобы гарантировать, что мат перевесит все другие факторы. Более развитые функции имеют точнее установленные коэффициенты ценности фигур, которые зависят от стадии партии и позиции на шахматной доске.
Во-вторых, позиционное преимущество, которое зависит от положения фигур на доске; например, заблокированная фигура ценится меньше, чем свободная; оценивается также безопасность короля, господство над центром доски и т. д.; существуют также более сложные системы оценки (некоторые даже используют знания о нейронных сетях), однако даже такая простая функция позволяет программе играть очень сильно; в шахматах главная проблема заключается не в оценке позиции, а в переборе дерева возможных ходов.

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

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

Компьютер против человека Править

Даже в 1970—80-х годах оставался открытым вопрос, когда шахматная программа сможет победить сильнейших шахматистов. В 1968 году международный гроссмейстер Дэвид Леви пошел на пари, что ни один компьютер не сможет обыграть его в течение ближайших десяти лет. Он выиграл пари, победив в 1978 году программу Chess 4.7 (сильнейшую в то время), но сознавал, что осталось не так уж много времени до того, когда компьютеры будут побеждать мировых чемпионов. В 1989 году программа Deep Thought выиграла у Леви.

Но программы всё ещё были значительно ниже уровня чемпиона мира, который продемонстрировал Гарри Каспаров, победив ту же Deep Thought дважды в 1991 году.

Это длилось до 1996 года, когда состоялся матч Каспарова с компьютером Deep Blue фирмы IBM, где чемпион проиграл свою первую партию. Впервые компьютерная шахматная программа обыграла чемпиона мира при стандартном часовом контроле. Однако Каспаров изменил свой стиль игры, выиграв три и сведя вничью две из оставшихся пяти партий. В мае 1997 года усовершенствованная версия Deep Blue нанесла поражение Каспарову со счетом 3,5-2,5. В 2003 году был снят документальный фильм, в котором исследовались упрёки Каспарова по поводу возможного использования IBM шахматиста, под названием «Матч окончен: Каспаров и машина» (англ. Game Over: Kasparov and the machine). В фильме утверждалось, что сильно раскрученная победа Deep Blue подстроена для увеличения рыночной стоимости IBM. Частично эти упрёки были оправданными. Правила позволяли разработчикам изменять программу между играми. Deep Blue был изменён между партиями для лучшего понимания машиной стиля игры Каспарова, помогая избежать ловушки в эндшпиле, в которую дважды попадал искусственный интеллект.

Финальная позиция.

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

Имея все большую вычислительную мощность, шахматные программы, запущенные на персональных компьютерах, стали достигать уровня лучших шахматистов. В 1998 году программа Rebel 10 победила Вишванатана Ананда, который тогда занимал второе место в мире. Однако не все партии игрались со стандартным временным контролем. Из восьми партий матча, четыре играли с блиц-контролем (пять минут плюс пять секунд за каждый ход), которые Rebel выиграл со счетом 3-1. Еще две игры были с полу-блиц контролем (пятнадцать минут на каждого), которые программа также выиграла (1,5-1). Наконец, две последние партии были сыграны со стандартным турнирным временным контролем (два часа на 40 ходов и час на остальные партии) и тут выиграл уже Ананд со счетом 0,5-1,5. К тому времени в быстрых партиях компьютеры играли лучше людей, но при классическом временном контроле преимущество компьютера над человеком было уже не так велико.

В 2000 году коммерческие шахматные программы Junior и Fritz смогли свести в ничью матчи против предыдущих мировых чемпионов Гарри Каспарова и Владимира Крамника.

В октябре 2002 года Владимир Крамник и Deep Fritz соревновались в матче из восьми партий в Бахрейне. Матч закончился вничью. Крамник выиграл вторую и третью партии, используя традиционную противокомпьютерную тактику — играл осторожно, имея целью долгосрочное преимущество, которое компьютер не может увидеть в своем дереве поиска. И всё же Fritz выиграл пятую партию после грубой ошибки Крамника. Шестую партию много турнирных комментаторов назвали очень увлекательной. Крамник, имея лучшую позицию в начале миттельшпиля, попытался пожертвовать фигуру, чтобы создать сильную тактическую атаку (такая стратегия очень рискована против компьютеров). Fritz нашел сильную защиту, и эта атака значительно ухудшила позицию Крамника. Крамник сдал игру, веря, что партия проиграна. Однако последующий анализ показал, что Fritz вряд ли смог бы довести игру до своего выигрыша. Последние две партии закончились вничью.

В январе 2003 года Гарри Каспаров играл против программы Junior в Нью-Йорке. Матч закончился со счётом 3-3.

В ноябре 2003 года Гарри Каспаров играл с X3D Fritz. Матч закончился со счётом 2-2.

В 2005 году Hydra, специальный шахматный программно-аппаратный комплекс с 64 процессорами, победил Майкла Адамса — шахматиста, который в то время был на седьмом месте в мире по рейтингу Эло — в матче из шести партий со счётом 5,5-0,5 (хотя домашняя подготовка Адамса была намного ниже, чем у Каспарова в 2002 году). Некоторые комментаторы верили, что Hydra наконец получит несомненное преимущество над лучшими шахматистами.

В ноябре-декабре 2006 года чемпион мира Владимир Крамник играл с программой Deep Fritz. Матч закончился выигрышем машины со счётом 2-4.

Базы данных эндшпиля Править

Подробнее Базы данных эндшпиля

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

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

Все 5-фигурные окончания занимают 7,03 ГБ.
Все 6-фигурные окончания занимают 1,205 ТБ.
Все 7-фигурные окончания занимают 140 ТБ.
Все 8-фигурные окончания будут занимать приблизительно 10 ПБ.

Игра против программ Править

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

Шахматы и другие игры Править

Настоящим вызовом для программистов стало го. Сложность вычисления го на несколько порядков больше, чем в шахматах. На каждом шаге возможны около 200—300 ходов, статическая же оценка жизни групп камней фактически невозможна. Одним ходом здесь можно вполне испортить всю игру, даже если остальные ходы были успешны. Поэтому алгоритмы, которые были успешны для игры в шахматы, не достаточны для игры в го на профессиональном уровне. Тем не менее, в октябре 2015 года, компьютерная программа AlphaGo, разработанная компанией Google DeepMind, впервые выиграла в го у профессионала 2 дана Фань Хуэя. А в марте 2016 года она выиграла матч с Ли Седолем, профессионалом 9 дана, со счётом 4-1.

Хронология компьютерных шахмат Править

1769 — Вольфганг Кемпелен создал шахматный автомат «Турок», который стал одной из величайших мистификаций того периода.
1868 — Чарльз Хупер представил автомат Ajeeb — в котором тоже был спрятан шахматист.
1912 — Леонардо Торрес Квеведо построил машину, которая могла играть эндшпиль Король + Ладья против короля.
1948 — вышла в свет книга Норберта Винера «Кибернетика», которая описывает как можно создать шахматную программу, используя поиск минимакса с лимитированной глубиной и оценочной функцией.
1950 — Клод Шеннон опубликовал «Программирование компьютера для игры в шахматы», одну из первых статей о компьютерных шахматах.
1951 — Алан Тьюринг разработал на бумаге первую программу, способную играть в шахматы.
1952 — Дитрих Принц разработал программу, которая решала шахматные задачи.
1956 — первая подобная шахматам игра, в которую смогла играть программа, разработанная Полом Штейном и Марком Уэллсом для компьютера MANIAC I (Лос-Аламос, США).
1956 — Джон Маккарти изобрёл альфа-бета алгоритм поиска.
1958 — NSS стала первой программой, которая использовала альфа-бета алгоритм поиска.
1958 — первыми шахматными программами, которые могли играть полные шахматные партии, стали одна, созданная Алексом Бернштейном, и вторая — советскими программистами.
1962 — первой программой, которая играла правдоподобно, стала Kotok-McCarthy.
1966—1967 — первый матч между программами. В этом матче машина М-2 из ИТЭФ победила программу Kotok-McCarthy на машине MANIAC Стенфордского университета. Матч длился 9 месяцев, связь осуществлялась по телеграфуШаблон:Нет АИ.
1967 — Mac Hack Six, разработанная Ричардом Гринблатом, стала первой программой, победившей человека при турнирном контроле времени.
1970 — первый год Североамериканского чемпионата по шахматам среди компьютерных программ.
1974 — Каисса выиграла первый Всемирный Компьютерный Шахматный Чемпионат.
1977 — создание первой шахматной программы для микрокомпьютеров CHESS CHALLENGER.
1977 — создание Международной Компьютерной Шахматной Ассоциации.
1977 — Chess 4.6 стал первым шахматным компьютером, который добился успеха в серьёзном шахматном турнире.
1980 — первый год Всемирного Чемпионата по шахматам среди микрокомпьютеров.
1981 — Cray Blitz выиграл Чемпионат по шахматам штата Миссисипи со счётом 5-0 и рейтингом перформанса 2258.
1982 — программно-аппаратный комплекс Belle, разработанный Кеном Томпсоном, зарабатывает титул мастера США.
1988 — Шаблон:Нп5, разработанная Гансом Берлинером и Шаблон:Нп5, выигрывает матч против гроссмейстера Арнольда Денкера со счётом 3.5—0.5.
1988 — Deep Thought делит первое место с Тони Майлзом в турнире Software Toolworks Open (Лос-Анжелес), впереди бывшего чемпиона мира Михаила Таля и нескольких гроссмейстеров, в частности Самуэля Решевского, Уолтера Брауна, Эрнста Грюнфельда и Михаила Гуревича. В этом турнире Deep Thought нанёс поражение гроссмейстеру Бенту Ларсену и стал первым компьютером, который выиграл у гроссмейстера в турнире.
1992 — впервые микрокомпьютер, Шаблон:Нп5, разработанный Эдом Шредером (Ed Schröder), выигрывает VII Чемпионат мира по шахматам среди компьютерных программ, опередив мейнфреймы и суперкомпьютеры.
1997 — Deep Blue выиграл матч против Гарри Каспарова (2—1=3).
2002 — Владимир Крамник свёл вничью матч против Deep Fritz.
2003 — Каспаров сыграл вничью матч против Deep Junior.
2003 — Каспаров сыграл вничью матч против X3D Fritz.
2005 — Шаблон:Нп5 выиграла матч с Майклом Адамсом со счётом 5,5-0,5.
2005 — команда компьютеров (Шаблон:Нп5, Deep Junior и Fritz), обыграла со счётом 8.5—3.5 команду шахматистов (Веселин Топалов, Руслан Пономарев и Сергей Карякин), которые имели средний рейтинг Эло 2681.
2006 — чемпион мира, Владимир Крамник, побеждён программой Deep Fritz со счётом 4—2.
2014 — американский гроссмейстер, Хикару Накамура, проиграл мини-матч программе Stockfish 5 со счётом 1-3 (+0=2-2). Две первые партии человек играл с форой в одну пешку, а две последующие без форы, но с использованием подсказок шахматной программы Rybka 3.

Теоретики компьютерных шахмат Править

Шахматы. Играйте и выигрывайте! [Текст] / Николай Калиниченко. — Москва [и др.] : Питер, 2012. — 269, [1] с. : ил.; 25 см. — ISBN 978-5-459-01609-3

ru.chess.wikia.com

Компьютерные шахматы Википедия

Начиная с 2000-х годов даже сильнейшие игроки-люди не имеют никаких шансов в противостоянии с шахматными программами[1].

История[ | код]

Создание механических шахматных автоматов прекратилось с появлением цифровых компьютеров в середине XX века. В 1951 году Алан Тьюринг написал алгоритм, с помощью которого машина могла бы играть в шахматы, только в роли машины выступал сам изобретатель. Этот нонсенс даже получил название — «бумажная машина Тьюринга». Человеку требовалось более получаса, чтобы сделать один ход. Алгоритм был довольно условный, и сохранилась даже запись партии, где «бумажная машина» Тьюринга проиграла одному из его коллег[2]. Из-за отсутствия доступа к компьютеру программа ни разу не проверялась в работе.

Следующим шагом в развитии шахматного программирования стала разработка в ядерной лаборатории Лос-Аламоса в 1952 году на компьютере MANIAC I c тактовой частотой 11 кГц шахматной программы для игры на доске 6x6, без участия слонов. Известно, что этот компьютер сыграл одну партию против сильного шахматиста, она продолжалась 10 часов и закончилась победой шахматиста. Ещё одна партия была сыграна против девушки, которая недавно научилась играть в шахматы. Машина победила на 23-м ходу. Сейчас это выглядит смешно, но для своего времени это было большое достижение.

В 1957 году Алексом Бернштейном была создана первая программа для игры на стандартной шахматной доске и при участии всех фигур[3].

Важное событие для компьютерных шахмат произошло в 1958 год, когда Аллен Ньюэлл, Клифф Шоу и Герберт Саймон разработали алгоритм уменьшения дерева поиска, названный «альфа-бета-отсечение»[3][4], на основе которого построены функции поиска всех сильных современных программ.

Первой же машиной, которая достигла уровня шахматного мастера, была Belle (англ.), законченная в 1983 году Джо Кондоном и Кеном Томпсоном. Belle был первым компьютером, спроектированным только для игры в шахматы. Его официальный рейтинг Эло был 2250, таким образом, это была самая сильная шахматная машина своего времени.

В 1994 Гарри Каспаров проиграл программе Fritz 3 (англ.) турнирную блиц-партию в Мюнхене. Программа также выиграла у Вишванатана Ананда,

ru-wiki.ru

Компьютерные шахматы – 5 лучших программ для игры

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

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

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

Шахматная программа Arena

Arena – популярная и мощная шахматная программа. Может использоваться в качестве интерфейса для многих шахматных движков, полезна в анализе шахматных партий.

» Скачать программу Arena

Преимущества Arena

Возможность игры с использованием многих шахматных движков
Возможность изменения внешнего вида шахматной доски
Русскоязычный интерфейс (доступен как отдельный файл)

Тип распространения: freewareЦена: бесплатно

Шахматный движок XBoard/WinBoard

XBoard/WinBoard – одна из самых популярных шахматных программ, используемая в качестве графического интерфейса для различных шахматных движков.

» Скачать XBoard/WinBoard

Преимущества XBoard/WinBoard

Универсальность: множество шахматных движков
Возможность игры через серверы
Возможность проведения розыгрыша
Классические шахматы, а также китайские, японские и другие

Тип распространения: freewareЦена: бесплатно

Многоязычные шахматы BabasChess

BabasChess – многоязычный сетевой клиент для проведения игр в шахматы через интернет.

» Скачать BabasChess

Преимущества BabasChess

Самый популярный интерфейс для шахматных серверов (FICS)
Гибкие возможности изменения доски
Возможность компоновки окон
Поддержка плагинов

Тип распространения: freewareЦена: бесплатно

Lucas Chess для обучения шахматам

Lucas Chess – шахматная программа с богатым набором обучающих функций и широким спектром настроек для игры в шахматы.

» Скачать Lucas Chess

Преимущества Lucas Chess

Доступна «легкая» версия для детей и неопытных игроков
Поддержка плагинов, викторины и шахматные тренировки
Система подсказок во время игр

Тип распространения: freewareЦена: бесплатно

Scid vs PC – шахматный тестер

Scid vs PC – база данных и тестер шахматных движков для заядлых любителей шахмат на компьютере.

» Скачать Scid vs PC

Преимущества Scid vs PC

Обслуживание местных соревнований и через серверы FICS
Настраиваемый интерфейс
Поисковая система базы мероприятий

Недостатки:

Отсутствие поддержки шахматных вариантов (Chess960, шахматы Фишера)

Тип распространения: freewareЦена: бесплатно

webznam.ru

Компьютерные шахматы Википедия

Создание механических шахматных автоматов прекратилось с появлением цифровых компьютеров в середине XX века. В 1951 году Алан Тьюринг написал алгоритм, с помощью которого машина могла бы играть в шахматы, только в роли машины выступал сам изобретатель. Этот нонсенс даже получил название — «бумажная машина Тьюринга». Человеку требовалось более получаса, чтобы сделать один ход. Алгоритм был довольно условный, и сохранилась даже запись партии, где «бумажная машина» Тьюринга проиграла одному из его коллег[2]. Из-за отсутствия доступа к компьютеру программа ни разу не проверялась в работе.

В 1994 Гарри Каспаров проиграл программе Fritz 3 (англ.) турнирную блиц-партию в Мюнхене. Программа также выиграла у Вишванатана Ананда, Бориса Гельфанда и Владимира Крамника. Гроссмейстер Роберт Хюбнер отказывался играть против программы и автоматически проиграл. Каспаров сыграл второй матч с Fritz и победил с 4 выигрышами и 2 ничьими.

ruwikiorg.ru

Реферат Компьютерные шахматы

Реферат на тему:

План:

1 История
2 Мотивация
3 Проблемы реализации
4 Структура шахматной программы
- 4.1 Основные алгоритмы современных программ
5 Компьютер против Человека
6 Базы данных эндшпиля
7 Игра против программ
8 Шахматы и другие игры
9 Хронология компьютерных шахмат
10 Теоретики компьютерных шахмат

Введение

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

1. История

Шахматный компьютер

Шахматные компьютеры сейчас доступны по очень низкой цене. Появилось много программ с открытыми кодами, в частности Crafty, Fruit и GNU Chess, которые можно свободно загрузить из сети Интернет и который может победить многих профессиональных шахматистов. А лучшие коммерческие программы, например, Shredder или Fritz уже превысили уровень людей-чемпионов. Сейчас же движок Rybka находится на первом месте в таких компьютерных рейтинг-листах, как CEGT,CCRL,SCCT і CSS.

2. Мотивация

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

3. Проблемы реализации

Разработчики шахматных программы должны сделать ряд решений при их написании. Они включают:

Способ изображения шахматной доске — представление цельной позиции как структуры данных.
Методы поиска — поиск возможных лучших ходов.
Листовая оценка — оценка позиции без учета дальнейших ходов.

См. также:

Минимакс
Альфа-бета отсечение
Killer эвристика
Итерационное заглубление
Эвристика нулевого хода

4. Структура шахматной программы

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

4.1. Основные алгоритмы современных программ

Примерная схема осуществления альфа-бета отсечения слабых ходов

Компьютерные шахматные программы рассматривают шахматные ходы как игровое дерево. Теоретически, они должны оценивать все позиции, которые возникнут после всех возможных ходов, затем все возможные ходы после этих ходов и т. д. Каждый ход одного игрока называется «узел». Перебор ходов продолжается, пока программа не достигает максимальной глубины поиска или определяет, что достигнута конечная позиция (например мат или пат). И уже на основании оценки позиции выбирает оптимальную стратегию. В каждой позиции количество возможных ходов игрока около 35. Для полного анализа четырех ходов (по два хода каждого игрока) нужно исследовать около полутора миллиона возможностей, для шести — почти два миллиарда. Анализ на 3 хода вперед — очень мало для хорошей игры.

Программисты пытаются по-разному ограничить массу ходов, который надо перебрать (обрезание дерева поиска — game three pruning). Самым популярным является альфа-бета отсечение, в котором не рассматриваются позиции, имеющие меньшую оценку, чем уже оцененные. Приблизительное осуществления:

Пример первого вызова:

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

Во-первых, это оценка материала — каждая пешка — это 1 пункт, слон и конь по 3, ладья — 5, ферзь — 9. Король иногда ценится в 200 пешек (Статья Шеннона) или 1 000 000 000 пешек (программа разработана в СССР в 1961 г.), чтобы гарантировать, что мат перевесит все другие факторы. Более развитые функции имеют точнее установленные коэффициенты ценности фигур, которые зависят от стадии партии и позиции на шахматной доске.
Во-вторых, позиционное преимущество, которое зависит от положения фигур на доске; например заблокированная фигура ценится меньше, чем свободная, оценивается также безопасность короля, господство над центром доски и т. д.; существуют также более сложные системы оценки (некоторые даже используют знания о нейронных сетях), однако даже такая простая функция позволяет программе играть очень сильно; в шахматах главная проблема заключается не в оценке позиции, а в переборе дерева возможных ходов.

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

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

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

5. Компьютер против Человека

Финальная позиция.

В октябре 2002 Владимир Крамник и Deep Fritz соревновались в матче из восьми партий в Бахрейне. Матч закончился вничью. Крамник выиграл вторую и третью партии, используя традиционную противокомпьютерную тактику — играл осторожно, имея целью долгосрочное преимущество, которое компьютер не может увидеть в своем дереве поиска. И все Fritz выиграл пятую партию после грубой ошибки Крамника. Шестую партию много турнирных комментаторов назвали очень увлекательной. Крамник, имея лучшую позицию в начале миттельшпиля, попытался пожертвовать фигурой, чтобы создать сильную тактическую атаку (такая стратегия — очень рискованная против компьютеров). Fritz нашел сильную защиту, и эта атака значительно ухудшила позицию Крамника. Крамник сдал игру, веря, что партия проиграна. Однако последующий анализ показал, что Fritz вряд ли смог бы довести игру до своего выигрыша. Последние две партии закончились вничью.

В январе 2003 г. Гарри Каспаров играл против программы Junior в Нью-Йорке. Матч закончился со счетом 3-3.

В ноябре 2003, Гарри Каспаров играл с X3D Fritz. Матч закончился со счетом 2-2.

В ноябре-декабре 2006, Владимир Крамник играл с программой Deep Fritz. Матч закончился со счетом 2-4.

6. Базы данных эндшпиля

Подробнее Базы данных эндшпиля

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

Базы эндшпиля Налимова на пять фигур, которые используют методы современной компрессии, занимают 7.05 Гб на жестком диске. Для хранения баз данных на шесть фигур надо примерно 1.2 терабайт. Оценено, что семифигурная база данных потребует больше места, чем будет доступно в ближайшем будущем.

7. Игра против программ

8. Шахматы и другие игры

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

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

9. Хронология компьютерных шахмат

1769, Вольфганг Кемпелен, построил шахматиста-автомата, который стал одной из величайших мистификаций этого периода.
1868, Чарльз Хупер представил автомат Ajeeb — в котором тоже был спрятан шахматист.
1912, Леонардо Торрес Квеведо построил машину, которая могла играть эндшпиле Король + Ладья против короля.
1948, книга Норберта Винера «Кибернетика» описывает, как можно создать шахматную программу, используя поиск минимакса с лимитированной глубиной и оценочной функцией.
1950, Клод Шеннон опубликовал «Программирование компьютера для игры в шахматы», одну из первых статей о компьютерных шахматах.
1951, Алан Тьюринг разработал на бумаге первую программу, способную играть в шахматы.
1952, Дитрих Принц разработал программу, которая решала шахматные задачи.
1956, г. Лос-Аламос — первая подобная шахматам игра, которую смогли играть программы, разработанная Полом Штейном и Марком Уэллсом для компьютера MANIAC I.
1956, Джон Маккарти изобрел альфа-бета алгоритм поиска.
1958, NSS стала первой программой, которая использовала альфа-бета алгоритм поиска.
1958, первыми шахматными программами, которые могли играть полные шахматные партии, стали одна, созданная Алексом Бернштайн и вторая российскими программистами.
1962, первой программой, которая играла правдоподобно стала Kotok-McCarthy.
1966—1967, первый матч между программами.
1967, Mac Hack Six, разработанная Ричардом Гринблатт стала первой программой, победившей человека при турнирном контроле времени.
1970, первый год Североамериканского Компьютерного Шахматного Чемпионата.
1974, Каисса выиграла первый Всемирный Компьютерный Шахматный Чемпионат.
1977, создана первая шахматная программа для микрокомпьютеров CHESS CHALLENGER.
1977, создание Международной Компьютерной Шахматной Ассоциации.
1977, Chess 4.6 стал первым шахматным компьютером, который добился успеха в главном шахматном турнире.
1980, первый год Всемирного микрокомпьютерного Шахматного Чемпионата.
1981, Cray Blitz выиграл Чемпионат Штата Миссисипи с 5-0 счетом и рейтингом производительности 2258.
1982, аппаратный шахматный игрок Кена Томпсона Belle зарабатывает титул мастера США.
1988, HiTech, разработанная Гансом Берлинером и Карлом Ебелингом, выигрывает матч против гроссмейстера Арнольда Денкер со счетом 3.5 — 0.5.
1988, Deep Thought делит первое место с Тони Майлзом в Чемпионате ПО Toolworks, впереди бывшего чемпионв мира Михаила Таля и нескольких гроссмейстеров, в частности Самюэля Решевського, Уолтера Брауна, Эрнста Грюнфельда и Михаила Гуревича. Программа также нанесла поражения гроссмейстер Бенту Ларсену, и стала первым компьютером, который выиграл у гроссмейстера в турнире.
1992, впервые микрокомпьютер, Chessmachine Gideon 3.1, разработанный Эдом Шредером (Ed Schröder) выигрывает VII Всемирный Компьютерный Шахматный Чемпионат впереди суперкомпьютеров.
1997, Deep Blue выиграл матч против Гарри Каспарова 2-1 = 3.
2002, Владимир Крамник свел вничью матч против Deep Fritz.
2003, Каспаров сыграл вничью матч против Deep Junior.
2003, Каспаров сыграл вничью матч против X3D Fritz.
2005, Hydra выиграла матч с Майклом Адамсом со счетом 5,5-0,5.
2005, команда компьютеров (Hydra, Deep Junior и Fritz), выиграла 8.5-3.5 команду из шахматистов (Веселин Топалов, Руслан Пономарев и Сергей Карякин), которые имели средний ЭЛО рейтинг 2681.
2006, чемпион мира, Владимир Крамник, побежден 4-2 Deep Fritz.

10. Теоретики компьютерных шахмат

Дэвид Леви
Роберт Хайатт (автор шахматной программы Crafty)
Ганс Берлинер
Клод Шеннон

Примечания

Alan Turing vs Alick Glennie - www.chessgames.com/perl/chessgame?gid=1356927 // «Turing Test», 1952
↑ 12 Early Computer Chess Programs - www.chessville.com/billwall/EarlyComputerChessPrograms.htm // Bill Wall’s Wonderful World of Chess
Computer Chess History by Bill Wall - www.geocities.com/SiliconValley/Lab/7378/comphis.htm

wreferat.baza-referat.ru

История развития компьютерных шахмат

Компьютерные шахматы Когда компьютеров еще не было, люди уже задумывались над созданием шахматного автомата. Известна история про "Турка", созданного в 18-м веке для Марии-Терезии, австрийской императрицы. Аппарат играл на удивление хорошо, но, увы, оказался фальшивкой – внутри сидел живой шахматист.

Следующий шаг был сделан после Второй Мировой войны, когда один из лучших математиков того времени Алан Тьюринг создал алгоритм для обучения машины игре в шахматы. В 1947 году он специфицировал первую шахматную программу.

Одновременно с Тьюрингом этой задачей занимался еще один математик – Клод Шеннон. В 1949-1950 годах он обозначил главную проблему: с каждым ходом число вариантов продолжений будет расти. Исследователь выделил два способа перебора вариантов: А-стратегия, с перебором всех без исключения вариантов, и B-стратегия, отбрасывающая неподходящие варианты, исходя из шахматного опыта людей.

Первый компьютер был спроектирован фон Нейманом для ведения сложных расчетов при создании ядерного оружия. В 1950 году появился первый образец, способный производить 10000 операций в секунду. Одним из первых экспериментов с аппаратом стало написание шахматной программы, правда, шахматы были нестандартные – на доске 6*6 без слонов. Через несколько лет этот компьютер ("MANIAC") сыграл с людьми: сильный шахматист одержал уверенную победу, а новичок проиграл за 23 хода.

В СССР разработкой шахматных компьютеров занялись в 1963 году. До 1980 года "Каисса" обыгрывала американские варианты, но дальше, как известно, отставание в развитии вычислительной техники не позволило добиваться новых результатов.

Принципы и алгоритмы компьютерных шахмат

Как уже было сказано, главная проблема – это слишком большое количество вариантов. А сколько это в реальности? В обычной позиции в среднем существует порядка 40 возможных ходов, и столько же ответных. Т.е. каждая пара полуходов – это 1600 позиций, две пары 1600*1600=2,5 млн. позиций, три пары – 4 млрд. позиций.

Математики оценивают количество различных шахматных партий величиной 10 в 120 степени – так называемое Число Шеннона (для сравнения – число атомов в изученной части вселенной – 1080). Число различных позиций, возникающих на шахматной доске во время игры, несомненно, меньше, ведь в разных партиях могут возникать одинаковые позиции. Рассчитанное число позиций в шахматах около 1043, включая некоторые невозможные позиции. Условно, с учетом легальности позиций, можно считать их количество приблизительно равным 1040.

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

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

Сколько ходов могли просчитать компьютеры? Производительность первых моделей составляла лишь 500 позиций в секунду, т.е. лишь 1.5 хода, если считать время хода – 3 минуты, а это – уровень начинающего шахматиста.

В 1958 году ученые Питтсбургского университета придумали "алгоритм альфа-бета", позволяющий отбросить большое количество вариантов без ущерба для конечного результата. Стоит отметить, что альфа-бета-поиск и его разновидности составляют ядро и современных шахматных программ. В чем суть: анализируется первый вариант, если второй вариант хуже первого – его не надо считать до конца, так как в любом случае из этих двух вариантов будет выбран первый. В результате работы данного алгоритма требуется просмотреть на порядок меньше позиций, и ЭВМ смогли просчитывать уже 5-6 полуходов, самые быстрые – даже 7. Компьютеры стали играть сильнее, но все же соревноваться с сильными игроками еще не удавалось.

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

При разработке вышеперечисленных алгоритмов решалась, прежде всего, математическая задача, то есть подход изначально был "компьютерным". Но есть и другой вариант: проанализировать опыт ведущих шахматистов и формализовать принципы игры, которыми пользуется человек. Такой компьютер будет играть быстрее и "по-человечески". Задача не из легких, первым за нее взялся Михаил Ботвинник. Он потратил много лет на создание собственного шахматного компьютера, но, к сожалению, не довел работу до конца, оставив лишь массу теоретических материалов.

Суперкомпьютеры

Следующим шагом было создание компьютеров специально для шахмат, позволяющих совершать большое количество операций в секунду. Первый такой компьютер был создан в лаборатории Белл Кеном Томпсоном, он производил 180000 операций в секунду (обычные компьютеры – лишь 5000) и просчитывал позицию на 8-9 полуходов, что соответствовало уровню мастера. Этот компьютер победил Всемирном шахматном турнире компьютеров, и во многих других турнирах в начале 80-х, но уступил новому гораздо более мощному Cray X_MPs. Компьютер Томпсона был усовершенствован, но так и не смог победить лидера. Далее появился Chip Test и Deep Thought, способный считать 500 000 операций в секунду. DT сыграл две партии с действующим чемпионом мира Каспаровым и проиграл обе, зато одержал победу над несколькими гроссмейстерами.

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

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

1 полуход – 200 Эло
4 полухода – 1230 Эло
9 полуходов – 2328 Эло
14 полуходов – 2800 Эло

Данное разделение глубины расчета вариантов и силы игры программы достаточно условно, т.к. важен еще и алгоритм оценки отдельно взятой позиции.

В 1996 году состоялся первый матч Deep Blue с Каспаровым, в котором чемпион мира одержал победу со счетом 4:2. Deep Blue – это 6-ти процессорный суперкомпьютер, способный просчитывать 100 млн позиций в секунду. Через год состоялся матч реванш с модернизированным 8-процессорным Deep Blue, считающим вдвое быстрее. Компьютер впервые победил лучшего шахматиста со счетом 3.5:2.5. В то время компьютер не умел оценивать позицию и строить игру на основании этой оценки. Рост силы игры достигался исключительно за счет увеличения мощности "железа". Даже алгоритм перебора все еще использовался "брутфорс", то есть перебирались все варианты, но очень быстро.

Суперкомпьютер – вещь штучная, рядовому пользователю недоступная. Дальнейшее развитие было связано с улучшением алгоритмов и снижением требований к аппаратной части, тем более, что и персональные компьютеры все это время не стояли на месте. В матче с Крамником играл Deep Fritz на двухпроцессорном сервере Compaq ProLiant DL760 на процессорах Xeon и RAM 2-16Гб. Такой компьютер, конечно, рядовому пользователю еще недоступен, но все же он выпускается серийно. Матч закончился вничью со счетом 4:4.

В 2003 году состоялся еще один матч Каспарова против компьютера – с Deep Junior, работавшем на 4х-процессорной системе с процессорами Pentium IV 1.9 ГГц и 3 Гб оперативной памяти. Junior – первая программа, демонстрирующая "человечную" игру, и способная пойти на жертву ради инициативы. Матч закончился вничью. В следующем матче Каспаров играл на виртуальной трехмерной доске в 3D-очках, делая ходы при помощи голосовых команд. Этот матч также закончился вничью.

Шахматные базы данных

Было бы странно не использовать накопленный людьми опыт. Создание дебютных баз позволило вообще не считать позицию первые 20-25 ходов, а пользоваться готовыми наработками. Но и опыт компьютеров также пригодился: начиная с 1980-х годов Кен Томпсон стал создавать базу 4-х и 5-ти фигурных эндшпильных окончаний. Теперь компьютеру не надо считать по новой – можно использовать существующие наработки. Эндшпильные базы постоянно дорабатываются и пополняются, в ход пошли уже 6-7-фигурные эндшпили.

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

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

Можно ли победить компьютер в шахматы

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

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

В 5-6, и частично в 7-фигурном эндшпиле программа заведомо будет играть идеально, без ошибок. А вот при большем количестве фигур возможности живого игрока возрастают.

При переборе позиций на некоторую глубину, компьютер их оценивает, и в конечном итоге выбирает вариант, в котором получит преимущество. Как производится оценка? По формальным факторам, выраженным в условных пешках. Оценивается непосредственно наличие фигур, их активность, расположение пешек: изолированные, сдвоенные, проходные, отсталые, контроль полей в центре и вблизи короля и т.д. Чем точнее модель оценки позиции, тем лучше программа владеет позиционной игрой, но поскольку модель жестко задана, то именно здесь компьютер легче всего "подловить" – например, программа неуверенно ведет себя в закрытых позициях. Ну и главное "оружие" человека – это нестандартность мышления. "Антикомпьютерные шахматы" повысили шансы гроссмейстеров в игре с искусственным интеллектом. Но выявление слабостей немедленно привело к работе по их устранению.

Современные шахматные программы

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

Помимо коммерческих программ стали появляться частные разработки. Первым появился движок Ruffian, который сначала потеснил Fritz и Shredder, но новые версии "гигантов" оказались сильнее. Следующим "нарушителем спокойствия" стал движок Fruit, игравший с каждой версией все лучше и лучше. Fritz’у понадобилось выпустить девятую версию, чтобы на равных вести борьбу с новичком.

А пока "старички" воевали с "новичками" появилась она – шахматная программа Рыбка. Созданная шахматистом с высоким рейтингом, побеждающая всех и вся и с каждой версией подтверждающая свое превосходство. Первая версия "рыбки" не умела играть эндшпили – но до них и не доходило дело! Впервые программа научилась хорошо вести позиционную игру. Васик Райлих отошел от традиционной оценки позиции, а вместо нее использовал таблицы готовых оценок, полученных в результате анализа большого количества партий. Рыбка-3 на двухпроцессорном компьютере имеет рейтинг 3250 Эло, что гораздо выше, чем у действующего чемпиона мира.

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

Перспективы шахматных программ

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

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

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

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

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

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

Максим Наумов, GAMBITER.RU, декабрь 2008

www.gambiter.ru