Компьютерные шахматы со всех точек зрения
За последние десятилетия компьютеры прочно заняли места в самых разнообразных сферах нашей жизни. Сейчас нашу цивилизацию невозможно представить без повсеместно используемых вычислительных машин. Персональные компьютеры проникли и в шахматы. Появились компьютерные шахматные программы, с ростом мощности компьютеров о таких программах заговорили как о предвестниках искусственного разума. О компьютерах в шахматах или о компьютерных шахматах речь и пойдет в этой статье.
С прошлого десятилетия компьютеры приобрели огромное значение в подготовке шахматистов. Разросшиеся до гигантских размеров базы дебютных вариантов и огромные базы партий стало уже невозможно эффективно анализировать без применения персональных компьютеров. Теперь компьютер с личной дебютной библиотекой стал непременным атрибутом шахматиста. Процесс проникновения вычислительных систем шёл постепенно, но неуклонно. Вот про Крамника говорили, что он последним из супергроссмейстеров перешёл на использование компьютеров. Когда его остальные, «более продвинутые», коллеги вовсю использовали шахматные программы, он ещё продолжал по старинке записывать варианты в тетрадочку. Но и он поддался веяньям прогресса.
С появлением игровых шахматных программ и мощных персональных компьютеров интенсивность изучения дебюта резко возросла. Дома можно поставить компьютер на длительное время анализировать без участия человека какой-нибудь вариант, потом использовать этот анализ. Сейчас очень и очень многие дебютные варианты, особенно, популярные, изучены до глубокого эндшпиля. Дебютная теория простирается на десятки ходов. Новинка на двадцатом ходу не вызывает никакого удивления, в отличие от новинки на десятом ходу, где, казалось бы, уже всё исследовано. Оказывается, пока что ещё не всё.
Многих известных шахматистов подвергают обвинениям в том, что они выигрывают партии за счёт большего количества компьютеров и, таким образом, более глубоких дебютных знаний. Дебютных новинок больше применяют и т.п. Каспаров чаще других подвергается подобным обвинениям. С одной стороны, к этому располагает его стиль игры от преимущества в дебюте. С другой стороны, он сам дал такой повод, явившись активным первопроходцем использования компьютеров в подготовке.
Но аспекты аналитической работы профессиональных шахматистов не так интересны простым шахматистам и болельщикам. Гораздо интереснее следить за противостоянием компьютерных программ и шахматистов за доской. К анализу которого мы сейчас и перейдём.
За последние несколько месяцев прошло два знаменательных матча Человек-Компьютер, они получили большую огласку и имели солидный призовой фонд. Сначала чемпион мира Владимир Крамник играл матч из восьми партий с шахматной программой Fritz — чемпионом мира среди компьютерных программ. Потом настала очередь лидера мирового рейтинг листа Каспарова сразится в матче из шести партий с шахматной программой Junior. Так же чемпионом мира, но другого года. Эти версии программ не играли официальных матчей между собой, так что, какая из них сильней, мы сможем узнать только на следующем чемпионате мира среди компьютеров. Тем не менее, известно различие стилей этих программ. Если Fritz тяготеет к позиционной игре, то Junior можно назвать атакёром. Кто-то даже сравнил стиль программы Fritz со стилем самого Крамника, а стиль Junior соответственно со стилем Каспарова. Говорилось о том, что гроссмейстеры играют со своим электронным воплощением.
Компьютерная тематика сайта обязывает меня писать об успехах клонированного электронного разума, однако, предполагается, что читатель знаком с фамилиями Каспаров, Крамник. Если нет, то в конце статьи я привёл ссылку на образное литературное описание обитателей шахматного королевства.
Принципы и алгоритмы компьютерных шахмат
Как уже было сказано, главная проблема – это слишком большое количество вариантов. А сколько это в реальности? В обычной позиции в среднем существует порядка 40 возможных ходов, и столько же ответных. Т.е. каждая пара полуходов – это 1600 позиций, две пары 1600*1600=2,5 млн. позиций, три пары – 4 млрд. позиций.
Математики оценивают количество различных шахматных партий величиной 10 в 120 степени – так называемое Число Шеннона (для сравнения – число атомов в изученной части вселенной – 10 80 ). Число различных позиций, возникающих на шахматной доске во время игры, несомненно, меньше, ведь в разных партиях могут возникать одинаковые позиции. Рассчитанное число позиций в шахматах около 10 43 , включая некоторые невозможные позиции. Условно, с учетом легальности позиций, можно считать их количество приблизительно равным 10 40 .
Если заложить абсолютно все позиции в базу данных компьютера, то игра шахматной программы станет идеальной из любой позиции и всегда будет приводить к лучшему исходу (если позицию хотя бы в каком-то варианте можно выиграть, программа обязательно найдет этот выигрыш). Однако, чтобы записать все эти позиции на носитель информации, понадобится хранилище данных, физические размеры которого сопоставимы с размером Луны.
Поэтому компьютерам остается только возможность делать анализ по ходу партии, рассчитывать ближайшие несколько ходов и оценивать позицию в перспективе.
Сколько ходов могли просчитать компьютеры? Производительность первых моделей составляла лишь 500 позиций в секунду, т.е. лишь 1.5 хода, если считать время хода – 3 минуты, а это – уровень начинающего шахматиста.
В 1958 году ученые Питтсбургского университета придумали «алгоритм альфа-бета», позволяющий отбросить большое количество вариантов без ущерба для конечного результата. Стоит отметить, что альфа-бета-поиск и его разновидности составляют ядро и современных шахматных программ. В чем суть: анализируется первый вариант, если второй вариант хуже первого – его не надо считать до конца, так как в любом случае из этих двух вариантов будет выбран первый. В результате работы данного алгоритма требуется просмотреть на порядок меньше позиций, и ЭВМ смогли просчитывать уже 5-6 полуходов, самые быстрые – даже 7. Компьютеры стали играть сильнее, но все же соревноваться с сильными игроками еще не удавалось.
Кстати, в разработку эффективных методов перебора внесли большой вклад и советские математики Брудно и Арлазаров. Известным математиком Александром Брудно, много сделавшим в области шахматного программирования, был разработан специальный алгоритм так называемого ранжирования, позволяющий компьютеру в опредленной позиции играть наилучшим образом. Это был прототип современных баз малофигурных окончаний. Правда, в те далекие времена требовались не одни сутки для расчетов 4-5 фигурных окончаний. Владимир Арлазаров — один из создателей шахматной «Каиссы», победившей на чемпионате мира среди шахматных программ в 1974 году.
При разработке вышеперечисленных алгоритмов решалась, прежде всего, математическая задача, то есть подход изначально был «компьютерным». Но есть и другой вариант: проанализировать опыт ведущих шахматистов и формализовать принципы игры, которыми пользуется человек. Такой компьютер будет играть быстрее и «по-человечески». Задача не из легких, первым за нее взялся Михаил Ботвинник. Он потратил много лет на создание собственного шахматного компьютера, но, к сожалению, не довел работу до конца, оставив лишь массу теоретических материалов.
Кто сильнее в шахматах — компьютер или человек?
Уже в самом начале компьютерной эры машины умели выполнять арифметические операции точнее и быстрее человека. На сегодняшний день разрыв в этой области просто колоссален.
Также компьютер может запомнить больше информации, а также способен быстро ее находить. Например, в многостраничном документе программа почти мгновенно найдет необходимую цитату.
Долгое время человеку удавалось побеждать компьютер в интеллектуальных играх, и это считалось доказательством превосходства человеческого интеллекта. Естественно, программисты обратили свое внимание на шахматы, ведь эта игра ассоциируется у многих с интеллектуальной дуэлью.
Первая шахматная партия между человеком и машиной была сыграна в 1957 году. Через 10 лет уровень машин, по оценкам эксперта, достиг только третьего шахматного разряда. Тогда же начали проводиться соревнования между разными шахматными программами. В 1983 году программа Belle достигла уровня мастера спорта.
Математика плюс философия
Удивительно, что алгоритм игры го до сих пор не раскрыт и даже самая мощная программа играет слабее человека (одну победу можно счесть случайностью, и рано пока говорить о победе искусственного разума над человеческим). Доска большая, изначально выигрышных дебютов нет, и достичь гармоничного развития простым перебором вариантов невозможно — их больше, чем атомов во Вселенной. Камни одинаковы, значение имеет только место, где они стоят, и форма, которую они образуют. Оценить потенциал построений, выбрать приоритеты — сложные задачи, связанные с такими разделами математики, как теория графов и распознавание образов. Здесь важна оптимальность действий, а это компьютеру пока не под силу. Быть может, игра го — ключ к искусственному разуму, и когда машина научится регулярно побеждать человека, она потянется и скажет: «Слушай, может, хватит? Я разумное существо, давай обговорим мои права».
Помимо того, в игре го много психологических, нематематических тонкостей, которые компьютер предсказать не может. Например, существует ситуация «секи», когда группы замирают на линии атаки, ибо начинающий гарантированно гибнет. Случается взаимный захват камня — «ко»: игрок может взять его только через ход, который обязан сделать в любой другой пункт доски, иначе взятиям не будет конца. Наконец, у игры в го есть и философский подтекст — он тоже влияет на стиль игры и принятие решений. Го учит пониманию, что добиться всего невозможно — надо брать, сколько можешь удержать, а остальным делиться. Рано или поздно игрок осознаёт, что теряет силы в драке за огрызки (отдельные камни). Мастерство приходит с пониманием принципов гармонии, навыков развития, оптимизации усилий, планирования и обустройства. И если шахматы воспитывают бойца, то игра го — правителя, организатора.
Выводы
Способность вырабатывать удачные стратегии в шахматах, изменять тактику приходит с опытом. Приложения, созданные для пк, служат хорошим учителем.
Сильнейшие шахматисты мира
Титул чемпиона по шахматам появился в 1886 году, когда австриец Вильгельм Стейниц обыграл прусского шахматиста Иоганна Цукерторта. В турнире играли до 10 побед, и за победу австрийский шахматист получил 1000 долларов, огромную по тем временам сумму.
История насчитывает десятки гениальных шахматистов, таких как Эмануэль Ласкер, который обыграл на тот момент четырёхкратного чемпиона мира по шахматам Вильгельма Стейница в 1894 году, русский гроссмейстер Александр Алехин, чья победа оказалась внезапной для всех, Михаил Ботвинник, Анатолий Карпов, Гарри Каспаров и многие другие.
Стоит отдельно отметить поединок между Борисом Спасским и Робертом Фишером, который состоялся в 1972 году, в разгар «холодной войны». Из-за сильного политического давления и эпатажного поведения Фишера, победа досталась американскому шахматисту.
История чемпионства по шахматам насчитывает множество интересных и экстраординарных случаев. И если первое столетие умы человечества занимали противостояния между людьми, то на заре 21-го века самыми обсуждаемыми стали поединки человека и компьютера.
Шахматный киборг
Альтерман давно перестал пытаться обыграть компьютер. «Все это похоже на попытку состязаться с машиной в легкой атлетике — люди не могут с ними играть», — говорит он. Но неужели соревновательная игра против компьютеров в результате этого умерла? Вовсе нет. Дэвид Леви указывает, что сегодня существуют так называемые «odds matches», в которых компьютер начинает, к примеру, без одной пешки, и они весьма популярны. Komodo сыграл серию с гроссмейстерами в таких условиях.
Стоит отметить, что существует даже спортивный интерес в просмотре игр компьютеров друг против друга. Любители компьютерных шахмат даже отслеживают и обсуждают баталии машин на онлайн-форумах.
Но что, если компьютер не всегда будет соперником? Что, если спроектировать его для помощи игроку-человеку, чтобы преимущества обоих типов мозга можно было использовать одновременно? Такая система — своего рода шахматные киборги — могла бы продвинуть даже новичков до небывалых высот.
Именно это произошло с двумя любителями в 2005 году. Стивен Крамтон и Захария Стивен были приятелями по шахматам, познакомившимися в местном клубе в Нью-Гемпшире в США. Несколько лет они провели, оттачивая свои навыки в игре, и Стивен, в частности, увлекался шахматным программированием.
Они приняли участие в «свободном» турнире, который в том году привлек несколько команд гроссмейстеров, которым помогали компьютеры. Турнир игрался дистанционно, онлайн, на серверах Playchess.com.
Крамтон и Стивен были любителями, ходили на ежедневную работу и были практически неизвестны в мире соревновательных шахмат. Но в рукаве у них было несколько крутых трюков. Они разработали базу данных персональных стратегий, которые показывали, какой из двух игроков обычно имеет больший успех, когда сталкивается с похожими ситуациями.
«У нас была весьма обширная база данных, над которой я работал в течение четырех или пяти лет, — вспоминает Стивен. — Стив тоже сделал в нее вклад».
У них было три ПК, которые пропускали цифры и были специально подготовлены Стивеном. Но что самое главное, любители знали, как на самом деле играть в игру киборга.
«У нас была хорошая методология, когда использовать компьютер, а когда собственное человеческое суждение, что повышало наше преимущество», — говорит Стивен.
История шахматного компьютера
К идее создания устройства для игры в шахматы ученые возвращались часто. Впервые о шахматном программировании заявил американский математик Клод Шеннон в 1951 году. Он находил создание программы, способной играть в шахматы, интересным вопросом для исследования, но ставил под сомнение практическую нужность этого изобретения. В 1957 году была создана первая полноценная программа для игры с участием всех фигур. Это был большой прорыв в области программирования, но не в шахматном спорте, так как компьютеры проигрывали человеку.
В 1994 году суперкомпьютер IBM Deep Blue обыграл действующего чемпиона Гарри Каспарова. Позже советский гений взял реванш, но о противостоянии легенды шахматного мира и суперкомпьютера говорили еще очень долго.
Скандальные события привлекли большое внимание к этому виду спорта, а на рынке появились специальные шахматные компьютеры. Эти устройства стали активно применять спортсмены для разбора партий и расчетов ходов и любители как развлечение.
Шахматный компьютер чаще всего представляет собой стандартное шахматное полотно, соединенное с дисплеем и датчиками выполнения игровых манипуляций.
В зависимости от размеров и конструкции различают три типа шахматных компьютеров:
- Настольный (включает шахматную доску с фигурами и электронный дисплей. При игре шахматист передвигает свои фигуры и фигуры «соперника»)
- Карманный (электронное устройство компактных размеров с сенсорным экраном, на который выводится игровое поле с фигурами. Ходы выполняются касанием пальца либо стилуса)
- Смешанный (по конструкции напоминает настольный шахматный компьютер, но имеет меньшие размеры).
Компьютер против Человека [ править ]
Даже в 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 был изменён между партиями для лучшего понимания машиной стиля игры Каспарова, помогая избежать ловушки в эндшпиле, в которую дважды попадал искусственный интеллект.