Интересуюсь искусственным интеллектом — своего недостает!
Tags: программирование
Первый шахматный компьютер.
В 1769 году венгерский инженер Барон Вольфганг фон Кемпелен дабы развлечь Австрийскую Королеву Марию Терезу построил машину, которая умела играть в шахматы. Это механическое устройство своим внешним видом напоминало турка. Однако выдающееся умение автомата играть в шахматы, в действительности, было делом рук шахматного мастера, хитроумно спрятанного внутри машины. Этот «автомат» был ненастоящим.
Идея Тьюринга.
Удивительно, что первая шахматная программа была написана еще до изобретения первого компьютера. Это программа была придумана одним провидцем, совершенно точно предугадавшим изобретение программируемых компьютеров, способных играть в шахматы. Этим человеком был Алан Тьюринг, один из величайших математиков всех времен.
Тьюринг возглавлял группу ученых, взломавших немецкий код “Enigma”, что в определенной мере предрешило исход Второй Мировой войны. Он очень любил шахматы, но несмотря на все свои невероятные усилия, имея гигантский интеллект, Тьюринг все равно оставался довольно посредственным шахматистом.
Вскоре после окончания войны, он написал алгоритм, с помощью которого можно было бы обучить машину играть в шахматы. Но поскольку на тот момент еще не существовало компьютера, который был бы способен выполнять подобные алгоритмы, то он решил сам выступить в этой роли. Следуя своим же инструкциям, Тьюринг действовал как «человек-компьютер», и у него уходило более получаса на то, чтобы совершить один ход. Одна такая партия, в которой «Бумажная машина» Тьюринга проиграла одному из его коллег, была записана.
Вот как проходила эта историческая партия:
«Бумажная машина» Тьюринга — Алик Гленни. ,
Манчестер 1952 год
1.e4 e5 2.Kc3 Kf6 3.d4 Cb4 4.Kf3 d6 5.Cd2 Kc6 6.d5 Kd4 7.h4 Cg4 8.a4 K:f3+ 9.g:f3 Ch5 10.Cb5+ c6 11.d:c6 0-0 12.c:b7 Лb8 13.Ca6 Фa5 14.Фe2 Kd7 15.Лg1 Kc5 16.Лg5 Cg6 17.Cb5 K:b7 18.0-0-0 Kc5 19.Cc6 Лfc8 20.Cd5 C:c3 21.C:c3 Ф:a4 22. Kpd2? [22.h5! — и слон в ловушке] 22…Кe6 23.Лg4 Kd4? [23… Л:b2! 24.C:b2 Л:c2+] 24.Фd3 Kb5 25.Cb3 Фa6 26.Cc4 Ch5 27.Лg3 Фa4 28.C:b5 Ф:b5 29.Ф:d6 Лd8 0-1
Стратегии Шеннона
Примерно в то же время другой великий математик, Клод Шеннон из лаборатории Белл, заинтересовался вопросом обучения компьютера игре в шахматы. Он понял, что основная проблема будет заключается в огромном количестве продолжений, поэтому он придумал два различных сапособа обработки информации: «А-Стратегия» изучала все возможные продолжения, а «В-Стратегия» отбрасывала ненужные варианты. На сегодняшний день мы знаем два основных типа шахматных программ: программы «грубой силы» и «отборочные». Но, в принципе, все современные сильные программы, скорее, принадлежат к первому типу.
Шахматы вместо атомных бомб. Во время войны США построили гигантскую лабораторию в Лос-Аламосе, в пустыне Нью-Мексико, с целью создания атомного оружия. Разработка правильной формы зарядов и детонаторов, которая повлекла бы цепную реакцию, требовала большого количества вычислений.
В 1946 году венгро-американский математик по имени Джон фон Нейман получил задание построить мощную вычислительную машину, которая позволила бы ускорить расчеты. В 1950 году он представил компьютер гигантских размеров под названием MANIAC 1. Машина состояла из тысяч вакуумных трубок и переключателей. Она могла выполнять до 10.000 операций в секунду. К тому же, компьютер был программируемым.
Вместо того, чтобы немедленно приступить к работе над бомбами, ученые начали проводить с компьютером различные эксперименты. И одной из первых была написана именно шахматная программа. Это были уменьшенные шахматы, 6х6 (без слонов). Несмотря на это, этой программе требовалось 12 минут на то, чтобы продумать следующие 4 полухода ; со слонами та же самая операция заняла бы три часа.
В середине пятидесятых этот компьютер провел три партии. Первую партию он сыграл сам с собой, и белые выиграли, во второй партии против компьютера играл сильный шахматист. Эта партия продолжалась 10 часов и закончилась победой шахматиста. Последнюю партию компьютер сыграл с молодой девушкой, научившейся играть в шахматы всего за неделю до этого. Компьютер победил на 23-ем ходу.
Первый раз за всю историю машина превзошла человека в интеллектуальной игре.
Ниже приведен текст второй, вошедшей в историю шахматной партии этого компьютера (ограничения: доска 6х6, без слонов, не допускается ходы пешек на 2 клетки в первоначальной позиции, без рокировок).
MANIAC 1 — Человек,
Лос Аламос, 1956:
1.d3 b4 2.Kf3 d4 3.b3 e4 4.Ke1 a4 5.b:a4? [5.Kd2 и 6.Kd2-c4+ Kbc:c4 7.b3:c4 с хорошей игрой] 5…K:a4 6.Kp2? Kc3 7.K:c3 b:c3+ 8.Kpd1 f4 9.a3 Лb6 10.a4 Лa6 11.a5 Kpd5 12.Фa3 Фb5 13.Фа2+ Кре5 14.Лb1 Л:a5 15.Л:b5 Л:а2 16.Лb1 [с целью предотвратить мат: 16…Ла1] 16…Ла5 17.f3 Ла4 18.f:e4 c4 19.Kf3+ Kpd6 20.e5+ Kpd5 21.e:f6Ф Kc5 22.Фf6:d4+ Kpc6 23.Kf3 e5 мат.
Шахматы и математика.
Основной проблемой при создании шахматных программ является очень большое число возникающих продолжений. В обычной позиции возможно около 40 легальных ходов, а если посчитать каждый ответный ход, то получается 40х40 = 1600 возможных позиций. Это означает, что после каждых двух полуходов возникает 1600 вариантов возможных продолжений. После двух ходов — 2.5 млн., после трех — 4.1 млрд.
В среднем за одну партии производится около 40 ходов. Это означает, что количество возможных ходов равно 10 128. Это число значительно больше числа атомов в изученной нами части вселенной (всего лишь жалкие 10 80).
Очевидно, что при таком уровне развития техники, ни компьютер, ни любая другая машина не в состоянии вести партию путем вычисления всех возможных последующих ходов. Однако и люди не являются идеальными игроками. Вопрос состоит в том, достаточно ли велики ресурсы компьютера для того, чтобы победить стратегический гений человека.
Первые компьютеры рассчитывали до 500 позиций в секунду, т.е. 90.000 за 3 минуты – время, отпускаемое на соревнованиях для одного хода. Это означает, что за это время они могли продумать только 1.5 хода, что соответствует очень слабой игре — уровень начинающего шахматиста.
Для того чтобы просчитывать на полуход больше, необходимо было продумывать 15.000 позиций в секунду, то есть в 30 раз больше, чем осуществляли те первые компьютеры. Но даже два хода – это очень немного. Так, что тогда казалось нереальным, что компьютеры когда-нибудь смогут играть на уровне гроссмейстеров высокого класса.
Альфа-Бета.
Первый прорыв в этом направлении был осуществлен в 1958 году тремя учеными (Ньюэл, Шоу и Саймон) из Университета Карнеги-Меллон в Питтсбурге. Именно они сделали важное открытие. Они утверждали, что если отбросить довольно большую часть поиска возможных вариантов, то это не повлияет на конечный результат. Они назвали это алгоритмом Альфа-Бета. Важно заметить, что в данном случае использовалась только математика и каких-либо специальных знаний в области шахмат не требовалось.
Рассмотрим как работает этот алгоритм в общем виде: компьютер, проанализировав один из возможных ходов, переходит к работе над другим. Если последующий вариант оказывается хуже предыдущего, то мы можем прекратить исследование продолжений второго хода. При этом не важно, насколько хуже он был. Программа все равно предпочтет первый ход.
Для того, чтобы прийти к такому же результату, что и программы с полномасштабным поиском, Альфа-Бета просматривает на порядок меньше комбинаций. И теперь ЭВМ могли просчитывать игру уже на 5-6 полуходов вперед. В середине 70-х самые быстрые компьютеры (например, серии CDC Cyber) могли просчитывать на 7 полуходов вперед, при такой мощности они уже пользовались славой достойных соперников. Но даже на Альфа — Бете для того, чтобы подняться на один полуход выше, необходимо увеличить скорость в пять раз. На пути опять встало непомерно большое количество расчетов.
Компьютер «Belle».
Компьютерный ученый Кен Томпсон не мог дожидаться того момента, когда суперкомпьютеры стоимостью в миллион долларов станут в пять или двадцать пять раз быстрее, а следовательно, станут лучше играть в шахматы.
Он и его коллега из лаборатории Белл решили создать специальный компьютер, начиненный сотнями чипов, стоимостью около 20.000$. Они назвали его «Belle», и он был предназначен только для игры в шахматы.
Этот компьютер мог совершать до 180.000 операций в секунду, тогда как суперкомпьютеры того времени исследовали лишь 5.000 позиций за то же время. «Belle» мог продумывать позицию на 8-9 полуходов вперед, что ставило его на уровень шахматиста мастер класса. Он победил на Всемирном шахматном турнире среди компьютеров, а так же на многих других шахматных турнирах, в период с 1980 по 1983 год, но вскоре после этого он был вытеснен другим шахматным компьютером под названием «Cray X-MPs», стоимость которого в тысячу раз превышала стоимость «Belle».
Шахматные чипы.
В середине 80-х профессор Ганс Берлинер, компьютерный ученый Университета Карнеги — Меллон, придумал, как усовершенствовать компьютер Кена Томпсона. Берлинер, который, кроме того, был чемпионом мира в шахматах по переписке, создал шахматный компьютер HiTech.
Вместе со своим аспирантом Карлом Эбелингом, он создал компьютерный чип нового поколения. Однако HiTech с параллельно действовавшими 64-мя чипами, хоть и с небольшим отставанием, но все же проиграл Cray X-MPs на всемирном чемпионате среди компьютеров в 1986 году.
Вскоре после этого другие студенты Берлинга (Фенг-хсиунг Хсу, Мюррей Кемпбелл и другие) разработали свой собственный компьютер ChipTest , а позже и Deep Thought. Он стоил около 5.000$ и мог продумывать до 500.000 позиций в секунду. Позже Хсу и Кемпбелл расстались со своим учителем и присоединились к IBM. Совместно в Джо Хоан они построили нынешний IBM-компьютер Deep Blue.
Deep Blue
Компьютер, против которого в Филадельфии и Нью-Йорке играл Гарри Каспаров, представлял собой сервер IBM SP/2, оборудованный большим количеством специально разработанных чипов, производящих мгновенные вычисления. Каждый чип осуществляет 2-3 млн. операций в секунду. При использовании около 200 таких чипов общая скорость работы программы может достичь 200 млн. операций в секунду.
Глубина расчетов против игровой силы.
Что же такое 200 млн. операций в секунду для шахматной программы? Кен Томпсон, основатель «Belle», Unix и компьютерного языка «С», в 80-х поставил несколько интересных экспериментов, целью которых было установить связь между операционной скоростью компьютера и его игровым потенциалом.
Томпсон заставил Белл играть с самим собой, придав одной из сторон больший игровой потенциал. В среднем, компьютер, способный продумывать вперед на один полуход, имеет игровой потенциал равный приблизительно 200 ЭЛО. Продумывая вперед на четыре полухода, Белл играл на уровне 1230 ЭЛО, на девять полуходов — 2328 ЭЛО.
Если продолжить данную кривую, которая выравнивается по мере приближения к максимальному значению, можно вычислить, что, продумывая вперед на 14 полуходов, компьютер достигнет уровня чемпиона мира (2800 ЭЛО).
Заключение экспертов выглядит следующим образом: если вы хотите соревноваться с чемпионом мира за обладание титула, необходимо создать компьютер, который бы выполнял до 1 миллиарда операций в секунду (и продумывал последующие 14 полуходов). Deep Blue очень близок к этому, но все же его мощность пока еще не так высока.
Micros
Естественно, качество программного обеспечения имеет большое значение. Ведущие на сегодняшний день компьютерные программы типа Fritz и Junior, используя самые быстрые компьютеры, исследуют до 600.000 позиций в секунду. Реально они рассчитаны на состязания с игроками, чей игровой потенциал свыше 2600, т.е. могут соревноваться со всеми кроме 100 ведущих игроков мира. В соревнованиях по быстрым шахматам с ними может соревноваться лишь приблизительно десять ведущих шахматистов, а в блиц турнирах только 2-3 шахматиста смогут составить достойную конкуренцию.
Атака на два фронта.
Важно отметить, что многочисленные книги по теории дебютов играют огромную роль в формировании игрового потенциала компьютеров. Обобщенные знания и опыт многих поколений шахматистов могут спокойно уместиться на жестком диске и использоваться компьютером на первой стадии игры, т.е. в дебюте. Компьютерные программы знают десятки миллионов дебютных позиций и имеют доступ к информации по каждой из них (какие ходы были сделаны, какие из них результативные, какого ранга игрок и т.д.). Зачастую программа делает 15-20 первоначальных ходов прежде, чем начинает по-настоящему соревноваться. Без преимущества от накопленных человеком знаний дебютной теории, программы были бы значительно слабее.
Помимо тех существенных преимуществ, которые приобретают компьютеры, используя накопленные за всю историю шахмат дебютные знания, они также обладают преимуществом в эндшпиле.
Эндшпильные базы данных.
И снова, пионером этой программы, был вездесущий Кен Томпсон. В 80-х он начал создание базы данных всех возможных эндшпильных позиций с 4 или 5 фигурами на доске. В типичном пятифигурном окончании, например, король и два слона с одной стороны против короля и коня — с другой, содержится 121 миллион возможных позиций.
А с пешкой, которая двигается несимметрично, это число возрастает до 335 миллионов. Томпсон написал программы, которые генерировали все возможные позиции и прорабатывали все силовые линии в каждом эндшпиле. Он также сжал полученную в результате базу до такой степени, что на однин стандартный CD-ROM помещалась информация о 20 эндшпилях. Используя эти базы данных, компьютер может идеально играть в любом окончании («как Бог»). В любой позиции при данной расстановке фигур, компьютер моментально вычисляет, будет ли партия выигрышной, ничейной или проигрышной и за сколько ходов что может произойти.
Зачастую, он предсказывает победу или мат более чем за 50 ходов. В случае проигрышной позиции он выстраивает оптимальную защиту.
Эндшпильные базы данных, разработанные Томпсоном, использует Deep Blue, и даже компьютерные программы Fritz теперь применяют их при разработке различных вариантов продолжений. Вопрос о том, как это повлияет на их игровой потенциал, пока остается открытым.
В некоторых из пятифигурных эндшпилей человеку очень трудно или порой невозможно добиться компьютерного мастерства. Например, ни один человек не сможет переиграть компьютер в ситуации: королева и пешка c одной стороны, против королевы с другой. Однако эти пятифигурные эндшпили еще «цветочки» по сравнению с шестифигурными, которые в настоящее время разрабатывает Томпсон. В некоторых шестифигурных эндшпилях для победы необходимо проделать более 200 хорошо просчитанных ходов. Однако, даже сильнейшие игроки мира порой не в состоянии определить как изменилась ситуация после 100 ходов, которые были совершенно необходимы по мнению компьютера.
Естественно, развитие такого компьютерного обеспечения идет на пользу компьютерам вообще. Шестифигурные эндшпили Томпсона, которые содержат от 8 до 20 миллиардов возможных ходов каждый, могут быть уменьшены до размеров, подходящих для DVD. К счастью, семифигурные эндшпили, содержащие 1/2 триллиона возможных ходов каждый, пока еще очень далеки.
И, скорее всего, эти два направления развития анализа — дебютные и эндшпильные базы данных — никогда не пересекутся. Кажется маловероятным, что кто-либо когда-нибудь увидит компьютер, который сыграет 1.е4 и поставит мат в 40 ходов. Но с уверенностью можно сказать, что уже через нескольких лет или десятилетий компьютер будет обыгрывать в шахматы чемпиона мира, это лишь вопрос времени.
Когда это произойдет?
Когда точно это произойдет? Когда компьютер победит чемпиона мира в обычном матче? Вот прогнозы некоторых ведущих экспертов, сделанные в период с 1991 по 1994гг.:
1992 Профессор Монти Ньюборн
1993 Джон МакКарти
1994 Ганс Берлинер, Фенг-Сиунг Хсу
1995 Мюррей Кэмбелл, Дональд Мичи, Майк Валов
1999 Клод Шэннон, Фредерик Фридель
2001 Джон Нанн
2010 Гарри Каспаров
2018 Кен Томпсон
По вполне понятным причинам (журнал-то немецкий!) позабыли упомянуть советскую «Каиссу»! Да и «эндшпильные базы, разработанные Томпсоном», почему-то больше известны как таблицы Налимова.
Источник: chesslover.livejournal.com
К какому игровому жанру относятся компьютерные шахматы?
Мне кажется, что верного ответа тут нет. Шахматы, пусть даже и компьютерные — это жанр логических игр, на соображалку. Именно в логических играх шахматы встречаются на разных сборниках игр, а так же в категориях онлайн-игр и на сайтах.
Но так как в шахматах (тем более, в компьютерных) игрок управляет несколькими юнитами (читай: фигурами), каждый из которых обладает своими уникальными особенностями (фактически, это армия, а сам человек — это главнокомандующий этой армией), и при этом игрок должен следить за действиями оппонента, то я предположу, что в данном случае правильный ответ — это стратегия.
Но это с некоторой натяжкой, хотя стратегия и тактика в шахматах — ключевой момент для достижения победы.
Источник: www.bolshoyvopros.ru
История развития компьютерных шахмат
Когда компьютеров еще не было, люди уже задумывались над созданием шахматного автомата. Известна история про «Турка», созданного в 18-м веке для Марии-Терезии, австрийской императрицы. Аппарат играл на удивление хорошо, но, увы, оказался фальшивкой – внутри сидел живой шахматист.
Следующий шаг был сделан после Второй Мировой войны, когда один из лучших математиков того времени Алан Тьюринг создал алгоритм для обучения машины игре в шахматы. В 1947 году он специфицировал первую шахматную программу.
Одновременно с Тьюрингом этой задачей занимался еще один математик – Клод Шеннон. В 1949-1950 годах он обозначил главную проблему: с каждым ходом число вариантов продолжений будет расти. Исследователь выделил два способа перебора вариантов: А-стратегия, с перебором всех без исключения вариантов, и B-стратегия, отбрасывающая неподходящие варианты, исходя из шахматного опыта людей.
Первый компьютер был спроектирован фон Нейманом для ведения сложных расчетов при создании ядерного оружия. В 1950 году появился первый образец, способный производить 10000 операций в секунду. Одним из первых экспериментов с аппаратом стало написание шахматной программы, правда, шахматы были нестандартные – на доске 6*6 без слонов. Через несколько лет этот компьютер («MANIAC») сыграл с людьми: сильный шахматист одержал уверенную победу, а новичок проиграл за 23 хода.
В СССР разработкой шахматных компьютеров занялись в 1963 году. До 1980 года «Каисса» обыгрывала американские варианты, но дальше, как известно, отставание в развитии вычислительной техники не позволило добиваться новых результатов.
Принципы и алгоритмы компьютерных шахмат
Как уже было сказано, главная проблема – это слишком большое количество вариантов. А сколько это в реальности? В обычной позиции в среднем существует порядка 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 году.
При разработке вышеперечисленных алгоритмов решалась, прежде всего, математическая задача, то есть подход изначально был «компьютерным». Но есть и другой вариант: проанализировать опыт ведущих шахматистов и формализовать принципы игры, которыми пользуется человек. Такой компьютер будет играть быстрее и «по-человечески». Задача не из легких, первым за нее взялся Михаил Ботвинник. Он потратил много лет на создание собственного шахматного компьютера, но, к сожалению, не довел работу до конца, оставив лишь массу теоретических материалов.
Суперкомпьютеры
Следующим шагом было создание компьютеров специально для шахмат, позволяющих совершать большое количество операций в секунду. Первый такой компьютер был создан в лаборатории Белл Кеном Томпсоном, он производил 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
Источник: xn--80aaa5asd7agcy5a.xn--p1ai