Мат в N ходов

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

В закладки
Аудио

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

«Турок»

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

Первый шахматный компьютер (ну почти) hackernoon.com

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

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

Пример решения задачи о ходе коня для доски 5×5
wikipedia.org

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

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

Испанский «Шахматист»

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

Торрес (второй слева) демонстрирует своё изобретение
torresquevedo.org

И вот в 1912 году испанский инженер и математик Леонардо Торрес представил миру «El Ajedrecista» — «Шахматиста» (исп.) — первый автономный шахматный компьютер.

«Шахматист» всё ещё не мог вести полноценную партию. Аппарат демонстрировал игру тремя фигурами: король и ладья ставили мат королю соперника. Но, в отличие от предшественников, устройство могло играть самостоятельно, без помощи оператора.

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

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

1010011010

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

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

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

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

Основатель теории информации и «отец информационного века» Клод Шеннон публикует книгу «Programming a Computer for Playing Chess» («Компьютерное программирование для игры в шахматы»), которая становится самым фундаментальным трудом в этой области на тот момент.

Клод Шеннон и 11-й чемпион мира Роберт Фишер работают над прототипом шахматного компьютера
computerhistory.org

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

Полный перебор

К середине 20 века шахматные программы базировались на двух принципах: оценивающая функция и перебор дерева вариантов.

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

Ценность фигур, приведённая в одном из шахматных учебников
chesshistory.com

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

[8 пешек] × [пешка имеет 2 возможных хода] + [2 коня] × [конь имеет 2 возможных хода] = 20 вариантов позиций после первого хода

После первого хода в нашем дереве есть уже 20 ветвей. А после ответа чёрных каждая ветвь также получит по 20 продолжений, и ко второму ходу дерево будет включать уже 400 ветвей.

Пешка может сделать ход на одну или две клетки вперед, а коню доступно только два поля

Думаю, вы уже поняли, что количество ветвей в дереве растёт очень быстро. Например, после четвёртого хода ветвей станет уже 71870.

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

Настоящий компьютер

В 1956 году в лаборатории Лос-Аламоса — колыбели ядерной бомбы — разрабатывают вариант игры в шахмат без слонов на доске размером 6×6 клеток. По сравнению с классическим, такой вариант игры требует меньше вычислений и отлично подходит для разработки и тестирования шахматных программ на одном из первых электронных компьютеров MANIAC I.

Пол Стейн и Марк Уэллс работают над шахматной программой на фоне MANIAC I

Сотрудники лаборатории Пол Стейн и Марк Уэллс разработали программу, работающую методом полного перебора .

Их компьютер работал со скростью 11 тысяч операций в секунду и просчитывал варианты на четыре хода вперёд. Лучший в этих пределах ход отыскивался в среднем за 12 минут.

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

Компьютер серии БЭСМ, на котором работала первая советская шахматная программа nautil.us

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

«Давид против Голиафа»

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

В 1963 году выдающийся советский шахматист и энтузиаст компьютерных шахмат Давид Бронштейн сыграл партию с самой сильной на тот момент шахматной программой, работающей на компьютере «Минск-22». Несмотря на то, что компьютер проводил 20 тысяч операций в секунду, гроссмейстер одержал убедительную победу над машиной.

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

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

Но переломный момент наступает на рубеже 80-х и 90-х.

Тёмно-синий

Скорее всего, вы что-то слышали про Deep Blue и его матчах с Каспаровым. Но прежде чем рассказать об их противостоянии, стоит упомянуть предшественников.

В 1988 году инженеры IBM создали Deep Thought. В этом же году машина приняла участие в шахматном турнире в Лонг-Бич, где поделила первое место с британским гроссмейстером Энтони Майлзом, обойдя при этом экс-чемпиона мира Михаила Таля.

На этом удача Deep Thought заканчивается. В 1989 году машина уступает в матче с Каспаровым со счётом 0:2, а в следующем году — Карпову со счётом 0:1.

Матч Каспарова против Deep Blue в 1997 году
scroll.in

IBM принимает решение развивать проект дальше, и вскоре на свет появляются Deep Thought ||, а за ним Deep Blue. В феврале 1996 последний пробует свои силы в матче с Каспаровым и вновь терпит поражение со счетом 2:4.

Инженеры вносят значитильные изменения прямиком в шахматный процессор машины и в мае 1997 Deep Blue II берет реванш.

Матч протекает с большой интригой. Первую партию выигрывает Каспаров, вторую — Deep Blue. Третья и четвёртая завершаются вничью. В пятой партии у Каспарова выигранная позиция, однако машина выкручивается и добивается ничьи посредством вечного шаха. Таким образом, накануне последней партии счет равный — 2½ на 2½. В заключительной партии Каспаров неудачно разыгрывает дебют, и, получив безнадёжную для себя позицию, сдаётся всего через 19 ходов.

Окончательный счет матча — 3½ на 2½. Компьютер одолел чемпиона мира.

Fritz противостоит Крамнику в 2002 году chessbase.com

В новом веке противостояние продолжается, причём машина участвует в нём уже с позиции силы. В 2002 году Fritz вничью проводит матч с новым чемпионом мира — Владимиром Крамником. В 2006 году в повторном матче Крамник проигрывает со счётом 2:4.

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

Нейронные сети

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

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

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

Обзор одной из партий между AlphaZero и StockFish. Партию называют одной из самых красивых в матче

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

Долгое время программисты не могли «заставить» нейронку успешно играть в шахматы, пока в 2017 году инженеры из DeepMind Technologies, дочерней компании Google, не добились успеха.

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

Вскоре после этого гугловские инженеры представили AlphaZero — нейронку, основанную на AlphaGo, но предназначенную для игры в шахматы. Новую программу выставили против Stockfish 8 — самой сильной на тот момент не-нейронки. Из ста партий AlphaZero выиграл 28, а остальные 72 свёл в ничью.

– Cheating bitch!

Компьютеры-компьютерами, а мы давайте тоже играть, ведь это интересно и весело.

Орзик, помнится, обещал устраивать регулярные турниры среди читателей TJ, но что-то филонит.

Вот предыдущий пост о том, как начать играть.

Материал дополнен редакцией

Материал опубликован пользователем.
Нажмите кнопку «Написать», чтобы рассказать свою историю.

Написать
{ "author_name": "Трехтысячелетний пес", "author_type": "self", "tags": ["\u0448\u0430\u0445\u043c\u0430\u0442\u044b","\u043d\u0435\u0439\u0440\u043e\u0441\u0435\u0442\u0438"], "comments": 19, "likes": 69, "favorites": 40, "is_advertisement": false, "subsite_label": "science", "id": 83087, "is_wide": false, "is_ugc": true, "date": "Mon, 14 Jan 2019 10:55:53 +0300", "is_special": false }
0
{ "id": 83087, "author_id": 130988, "diff_limit": 1000, "urls": {"diff":"\/comments\/83087\/get","add":"\/comments\/83087\/add","edit":"\/comments\/edit","remove":"\/admin\/comments\/remove","pin":"\/admin\/comments\/pin","get4edit":"\/comments\/get4edit","complain":"\/comments\/complain","load_more":"\/comments\/loading\/83087"}, "attach_limit": 2, "max_comment_text_length": 5000, "subsite_id": 214346, "last_count_and_date": null }
19 комментариев
Популярные
По порядку
Написать комментарий...
7

Орзик обещал

Быстро учится у Ширяева

Ответить
1

Орзик хочет, но Орзик ищет оправдания. Нет мне прощения.

На деле же, любой может создать турнир, ничего сложного в этом нет.

Я же хочу внести фичу на тж, для уведомления о новых постах с определенного подсайта. А то по другому собрать много народу проблематично

Ответить
1

Как вы умудрились даже не упомянуть Ботвинника и его незаменимый вклад в становление и развитие современных шахматных компьютеров?
И неужели между Fritz и Stockfish ни одного нашумевшего движка не было?
Поскакали вы по верхам во второй половине, нельзя так делать.
Да и вроде я как-то об одном древнем хардварном "не-турке" читал. Поищу завтра, скину.

Ответить
3

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

Ответить
0

Ну хоть искусственным интеллектом не называют.

Ответить
0

Очень интересно! И написано хорошо. Посоветуй ресурс с классными шахматными задачами.

Ответить
0

Комментарий удален по просьбе пользователя

Ответить
0

Комментарий удален по просьбе пользователя

Ответить
1

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

Ответить
1

Для справедливости, всё таки самым сильным на тот момент уже был stockfish 10. И партий, по-моему было 1000, просто разработчики показали только 100.

Ответить
0

Интересно, смогут ли люди подтянуться и таки снова побить компьютер.

Ответить
1

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

Ответить
0

Как зачем? Чтобы игра с компьютером заведомо не означала поражение. Оставляло шанс на победу.

Ответить
6

Ну это как «чтобы бег наперегонки с автомобилем заведомо не означал поражение»)

Ответить
0

Скорее как соревнование между обычным велосипедистом и электрическим велосипедом

Ответить
0

Черт с ними с аналогиями. Я просто хотел сказать, что человек-то создает все эти штуки не чтоб потом с ними соревноваться, а чтоб упростить себе жизнь.

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

А то так можно долго задваться вопросами из серии «может ли человек отрастить себе такую шерсть, чтобы мороз –40°C заведомо не означал поражение» и так далее в том же духе)

Ответить
0

Вот так я и узнал что на личесе провдятся турниры )

Ответить
Обсуждаемое
Новости
В США мужчина преодолел 564 километра ради секса с несовершеннолетней, но она оказалась полицейским под прикрытием
Теперь ему грозит до 10 лет тюрьмы.
Путешествия
Я нашел лодки из клипа Аллы Борисовны 1978 года
Это короткая заметка о том, как ради клипа «Сонет Шекспира» я отправился в путешествие в другой город.
Новости
Фото: Торжественное открытие школьного сквера с поролоновыми русалками и тканевым прудом в Сахалинской области
Это обошлось бюджету региона в 500 тысяч рублей.
Популярное за три дня
Новости
«Суки, сколько „за“, сколько „против“ и сколько воздержались?»: глава Мосгордумы на заседании поторопил подсчёт голосов
В итоге проект бюджета Москвы на три года рекомендовали для рассмотрения.
Новости
Илон Маск выступил на краснодарском форуме по видеосвязи
Он заявил, что «когда-нибудь в будущем» может открыть в России производство Tesla.
Интернет и мемы
!

Прямой эфир

[ { "id": 1, "label": "100%×150_Branding_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox_method": "createAdaptive", "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "cndo", "p2": "ezfl" } } }, { "id": 2, "label": "1200х400", "provider": "adfox", "adaptive": [ "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "cndo", "p2": "ezfn" } } }, { "id": 3, "label": "240х200 _ТГБ_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "i", "ps": "cndo", "p2": "fizc" } } }, { "id": 4, "label": "Article Branding", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "p1": "cfovy", "p2": "glug" } } }, { "id": 5, "label": "300x500_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "cndo", "p2": "ezfk" } } }, { "id": 6, "disable": true, "label": "1180х250_Interpool_баннер над комментариями_Desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "h", "ps": "clmf", "p2": "ffyh" } } }, { "id": 7, "label": "Article Footer 100%_desktop_mobile", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "p1": "byswn", "p2": "fjxb" } } }, { "id": 8, "label": "Fullscreen Desktop", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "cndo", "p2": "fjoh" } } }, { "id": 9, "label": "Fullscreen Mobile", "provider": "adfox", "adaptive": [ "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "cndo", "p2": "fjog" } } }, { "id": 10, "disable": true, "label": "Native Partner Desktop", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fmyb" } } }, { "id": 11, "disable": true, "label": "Native Partner Mobile", "provider": "adfox", "adaptive": [ "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fmyc" } } }, { "id": 12, "label": "Кнопка в шапке", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "cndo", "p2": "fdhx" } } }, { "id": 13, "label": "DM InPage Video PartnerCode", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox_method": "createAdaptive", "adfox": { "ownerId": 228129, "params": { "pp": "h", "ps": "cndo", "p2": "flvn" } } }, { "id": 14, "label": "Yandex context video banner", "provider": "yandex", "yandex": { "block_id": "VI-223677-0", "render_to": "inpage_VI-223677-0-130073047", "adfox_url": "//ads.adfox.ru/228129/getCode?pp=h&ps=cndo&p2=fpjw&puid1=&puid2=&puid3=&puid4=&puid8=&puid9=&puid10=&puid21=&puid22=&puid31=&puid32=&puid33=&fmt=1&dl={REFERER}&pr=" } }, { "id": 15, "label": "Баннер в ленте на главной", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "p1": "byudv", "p2": "ftjf" } } }, { "id": 16, "label": "Кнопка в шапке мобайл", "provider": "adfox", "adaptive": [ "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "p1": "ccydt", "p2": "ftwx" } } }, { "id": 17, "label": "Stratum Desktop", "provider": "adfox", "adaptive": [ "desktop" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "cndo", "p2": "fzvb" } } }, { "id": 18, "label": "Stratum Mobile", "provider": "adfox", "adaptive": [ "tablet", "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "cndo", "p2": "fzvc" } } }, { "id": 20, "label": "Кнопка в сайдбаре", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "p1": "chfbk", "p2": "gnwc" } } } ]