{"id":1064,"title":"\u041f\u0440\u043e\u0439\u0434\u0438\u0442\u0435 \u044d\u0442\u043e\u0442 \u0442\u0435\u0441\u0442, \u043f\u043e\u043a\u0430 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u044e \u0438\u0437 \u0435\u0434\u044b \u043d\u0435 \u0437\u0430\u043f\u0440\u0435\u0442\u0438\u043b\u0438","url":"\/redirect?component=advertising&id=1064&url=https:\/\/tjournal.ru\/special\/kaleidofood&placeBit=1&hash=f30606208ead4bb67ee3624f20be3cd7a9b9c0ae8b2bd8a40218541848752d25","isPaidAndBannersEnabled":false}

Мат в 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, но что-то филонит.

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

0
19 комментариев
Популярные
По порядку
Написать комментарий...
Лига порвах 2.1

Орзик обещал
Быстро учится у Ширяева

Ответить
7
Развернуть ветку
Орзэмэс Мирзов

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

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

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

Ответить
1
Развернуть ветку
Kirill Grinenko

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

Ответить
1
Развернуть ветку
Ded Pihto

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

Ответить
3
Развернуть ветку
Военный меч

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

Ответить
0
Развернуть ветку
Митя Простомолотов

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

Ответить
0
Развернуть ветку
Трехтысячелетний пес

На личессе есть хороший раздел с десятками тысяч задач

Ответить
3
Развернуть ветку
Криминальный Илья

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

Ответить
0
Развернуть ветку
Криминальный Илья

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

Ответить
0
Развернуть ветку
Александр Хнычков

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

Ответить
1
Развернуть ветку
Ярослав Андриишин

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

Ответить
1
Развернуть ветку
Митя Простомолотов

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

Ответить
0
Развернуть ветку
Трехтысячелетний пес

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

Ответить
1
Развернуть ветку
Митя Простомолотов

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

Ответить
0
Развернуть ветку
Трехтысячелетний пес

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

Ответить
6
Развернуть ветку
Митя Простомолотов

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

Ответить
0
Развернуть ветку
Трехтысячелетний пес

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

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

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

Ответить
0
Развернуть ветку
Stas Zhirikov

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

Ответить
0
Развернуть ветку
Читать все 19 комментариев
null