Шахматная задача которую не может решить компьютер
Обновлено: 07.07.2024
Никто точно не скажет, когда люди стали задумываться о создании устройства, которое могло бы играть в шахматы. Но первые конкретные попытки были предприняты в 18 веке. К этому моменту история игры насчитывала более тысячи лет, а в Европе в неё играли уже семь столетий.
Считается, что первый шахматный автомат сконструировал австриец Вольфганг фон Кемпелен. В 1769 году изобретатель продемонстрировал устройство, которое назвал «Турок».
Аппарат представлял из себя восковую фигуру человека в натуральную величину, стоящую за ящиком с шахматной доской. Автомат не играл в полноценную игру, а лишь решал задачу о ходе коня. Суть задачи состоит в том, чтобы провести коня по всем клеткам доски ровно по одному разу.
Внутри ящика находился механизм, состоящий из всевозможныйх деталей и узлов. Каждые двадцать ходов оператор заводил механизм ключом, и турок начинал передвигать фигуры.
По крайней мере, так это подавалось зрителю. На самом деле, внутрь ящика был втиснут живой шахматист, а процедура завода механизма нужна была лишь для того, чтобы дать человеку время на раздумье.
Конечно, такое устройство не является шахматным компьютером, и вовсе считалось бы простым атракционом, если бы не одно важное обстоятельство. Оператор, сидящий внутри ящика, не мог непосредственно наблюдать за течением игры и делать ходы. Для решения этих задач автомат был оснащён сигнальной системой из магнитов, тросов и рычагов. Такая система формализовала процесс игры, заложив основу для теории компьютерных шахмат.
Следующие полтора столетия в компьютерных шахматах не было существенных подвижек — лишь несколько вариаций на тему «Турка».
И вот в 1912 году испанский инженер и математик Леонардо Торрес представил миру «El Ajedrecista» — «Шахматиста» (исп.) — первый автономный шахматный компьютер.
«Шахматист» всё ещё не мог вести полноценную партию. Аппарат демонстрировал игру тремя фигурами: король и ладья ставили мат королю соперника. Но, в отличие от предшественников, устройство могло играть самостоятельно, без помощи оператора.
В основе конструкции лежала металлическая сетка с электрической цепью, которая кодировала позицию фигур и передавала её на вычислительное устройство. В ответ ВУ приводило фигуры в движение с помощью зубчатой передачи и магнитов.
Взаимодействие трех фигур легко поддаётся формальному описанию, поэтому алгоритм игры оставался очень примитивным, и такие машины пока не вызывали серьезного интереса со стороны шахматной публики.
В течение нескольких следующих десятилетий активно развиваются алгоритмы и математические методы, которые затем лягут в основу компьютерных шахмат.
В 30-40-х годах немецкий инженер и пионер компьютеростроения Конрад Цузе разработал язык программирования Планкалькюль (Plankalkül), на котором начал писать программу для полноценной игры в шахматы. Однако война помешала работе Цузе, и программа так и не была реализована на «железе».
В 1948 году выдающийся математик и философ, «отец кибернетики» Норберт Винер публикует монументальный труд «Кибернетика», в котором помимо прочего освещает задачу компьютерных шахмат. Винер стремится применить к шахматам всю силу современных математических методов.
Работа Винера привлекла интерес к теме. Вслед за именитым ученым новое поколение выдающихся математиков и инженеров делает свой вклад в развитие компьютерных шахмат.
Основатель теории информации и «отец информационного века» Клод Шеннон публикует книгу «Programming a Computer for Playing Chess» («Компьютерное программирование для игры в шахматы»), которая становится самым фундаментальным трудом в этой области на тот момент.
В своей работе автор предлагает строить стратегию игры, отталкиваясь от материальной ценности фигур и позиционных факторов.
К середине 20 века шахматные программы базировались на двух принципах: оценивающая функция и перебор дерева вариантов.
Оценивающая функция, как это следует из названия, даёт оценку позиции на доске. Оценка включает в себя и материальную, и позиционную составляющую. Если одна из сторон имеет лишние фигуры, то оценка склоняется в её сторону: лишняя пешка дает «+1» к оценке, лишний слон — «+3». В то же время централизованный конь «весит» больше коня в углу доски. Это, разумеется, упрощённая схема, ведь ценность фигур меняется в зависимости от стадии игры, но для иллюстрации принципов этого достаточно.
Теперь разберёмся с деревом вариантов. Рассмотрим начальную расстановку фигур на доске — она будет корнем нашего дерева. Любой ход фигуры даёт начало новой ветви в этом дереве. С учётом того, что в начальной позиции могут ходить только пешки и кони, получается:
[8 пешек] × [пешка имеет 2 возможных хода] + [2 коня] × [конь имеет 2 возможных хода] = 20 вариантов позиций после первого хода
После первого хода в нашем дереве есть уже 20 ветвей. А после ответа чёрных каждая ветвь также получит по 20 продолжений, и ко второму ходу дерево будет включать уже 400 ветвей.
Пешка может сделать ход на одну или две клетки вперед, а коню доступно только два поляДумаю, вы уже поняли, что количество ветвей в дереве растёт очень быстро. Например, после четвёртого хода ветвей станет уже 71870.
Так вот. Допустим, вы компьютер и хотите через четыре хода иметь наилучшую для себя позицию. Для этого вам придётся вычислить функцию оценки для 71870 вариантов. Найдя позицию с наилучшей оценкой, вы делаете ход, который даёт начало ветке, ведущей к этой позиции.
В 1956 году в лаборатории Лос-Аламоса — колыбели ядерной бомбы — разрабатывают вариант игры в шахмат без слонов на доске размером 6×6 клеток. По сравнению с классическим, такой вариант игры требует меньше вычислений и отлично подходит для разработки и тестирования шахматных программ на одном из первых электронных компьютеров MANIAC I.
Пол Стейн и Марк Уэллс работают над шахматной программой на фоне MANIAC IСотрудники лаборатории Пол Стейн и Марк Уэллс разработали программу, работающую методом полного перебора .
Их компьютер работал со скростью 11 тысяч операций в секунду и просчитывал варианты на четыре хода вперёд. Лучший в этих пределах ход отыскивался в среднем за 12 минут.
Ограниченная мощность компьютеров подталкивала на поиск более оптимальных шахматных алгоритмов. Эту проблему решил информатик Джон Маккарти, который разработал алгоритм альфа-бета-отсечения. В основе алгоритма лежал всё тот же перебор. Отличие состояло в том, что новый алгоритм позволял отбросить бесперспективные ветки и сократить количество операций.
Благодаря новому алгоритму шахматные программы смогли увеличить глубину расчётов и сократить время работы. Уже через год и американские, и советские инженеры создали собственные компьютерные программы, которые могли играть в полноценные шахматы.
Шахматные программы делали большие успехи, однако сила их игры оставляла желать лучшего.
В 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½. Компьютер одолел чемпиона мира.
В новом веке противостояние продолжается, причём машина участвует в нём уже с позиции силы. В 2002 году Fritz вничью проводит матч с новым чемпионом мира — Владимиром Крамником. В 2006 году в повторном матче Крамник проигрывает со счётом 2:4.
Появляются опенсорсные компьютерные программы, наподобие Stockfish, сила игры которых уже не оставляет человеку шансов.
Несмотря на то, что живые шахматисты больше не могли конкурировать с машинами, компьютерные программы продолжили совершенствоваться.
Во всю играются чемпионаты по шахматам среди компьютерных программ, в которых одни программы соревнуются с другими.
Напоследок расскажу о недавнем событии, которое, скорее всего, станет важной отметкой не только в истории компьютерных шахмат, но и искуственного интеллекта в целом.
Обзор одной из партий между AlphaZero и StockFish. Партию называют одной из самых красивых в матчеРазработчики нейронных сетей, конечно же, не могли остаться в стороне, не попробовав своих сил в шахматах.
Долгое время программисты не могли «заставить» нейронку успешно играть в шахматы, пока в 2017 году инженеры из DeepMind Technologies, дочерней компании Google, не добились успеха.
Их программа AlphaGo одержала победу над чемпионом мира по игре в го. Эта игра долгое время время оставалось неприступной для компьютерных программ: го считается сложнее шахмат из-за большего количества игровых позиций.
Вскоре после этого гугловские инженеры представили AlphaZero — нейронку, основанную на AlphaGo, но предназначенную для игры в шахматы. Новую программу выставили против Stockfish 8 — самой сильной на тот момент не-нейронки. Из ста партий AlphaZero выиграл 28, а остальные 72 свёл в ничью.
Возможно, это выглядит как обычная шахматная задача, но она может наконец помочь учёным понять механизм, делающий человеческим ум настолько уникальным, что компьютерам, возможно, никогда за ним не угнаться.
Через 75 лет после того, как в Bletchley Park во время Второй мировой войны нашли шифровальщиков, разместив кроссворд в The Telegraph, учёные снова обращаются к читателям, чтобы найти самые лучшие умы.
Задача совпала с открытием нового Института Пенроуз. Его основатель – сэр Роджер Пэнроуз, почётный профессор Оксфордского математического института. В 1988 году он, вместе с профессором Стивеном Хокингом, получил премию Вольфа по физике – за работу о чёрных дырах и сингулярности.
Новый институт, с отделениями в Университетском колледже Лондона и в Оксфордском университете, задался целью изучить человеческое сознание с помощью физики и вывести фундаментальные отличия между искусственным и человеческим интеллектами.
Как закончится партия? Шахматная позиция, которая ставит в тупик компьютеры. Шахматная программа всегда предполагает, что чёрные выигрывают. Но для белых здесь возможна ничья и даже победа.
Если у учёных получится, результаты исследования могли бы доказать, что человеческий мозг – не просто гигантский суперкомпьютер, но и структура, которая демонстрирует квантовые эффекты, выходящие далеко за пределы представимого. Эту противоречивую теорию многие учёные считают невозможной.
Шахматная задача, представленная сэром Роджером, придумана так, что решить её могут только люди – искусственный интеллект на это неспособен. Учёные из Института Пенроуз предлагают читателям подумать, как выиграть белым, или доказать неизбежную ничью.
Команда надеется, что, исследуя мозг людей, решивших задачу, или людей в момент озарения, они могут узнать, в каких участках мозга появляется «эврика» или интуиция.
«Мы знаем, что есть вещи, с которыми человеческий разум справляется, а мощный суперкомпьютер – нет, и мы не знаем, почему так происходит. Квантовый эффект есть в биологии – в фотосинтезе, миграции птиц и т.д., и это доказано. Возможно, то же самое происходит и с мозгом. Эта гипотеза крайне противоречива. Если мы выясним, чем именно человек отличается от компьютера, социологические последствия будут несоизмеримыми. Люди боятся думать о будущем, в котором роботы или компьютеры отнимут их работы, но может выяснится, что в некоторых областях знания машины никогда не станут лучше, чем мы. В креативности, к примеру».
В 1942 году шифровальщики из Bletchley Park отпечатали похожий паззл на страницах The Telegraph. Они надеялись нанять новых работников, чтобы помочь союзникам взломать Enigma и выиграть Вторую мировую. Читателей попросили решить задачу за 12 минут.
Новая шахматная задача – одна из серии. Остальные Институт выпустит в ближайшие недели – исследователи хотят взломать код человеческой гениальности.
Джеймс Тэгг, создатель сенсорного ЖК-дисплея, возглавивший институт, говорит: «Нам интересно посмотреть, что происходит с мозгом, когда людей осеняет. У меня – это настоящая вспышка света, но остальные, возможно, видят нечто иное. Задача сконструирована, чтобы показать разницу между ИИ и ЧИ (человеческим интеллектом), выяснить природу человеческого понимания вещей. Человек, взглянув на картинку, поймет, что должны и не должны делать белые – на это у него уйдёт минимальное количество энергии. Однако для компьютера решение задачи требует немыслимого количества вычислений, немыслимого даже для современных суперкомпьютеров».
Институт, кроме того, надеется разработать новую технологию для лечения заболеваний мозга и анестезии, разработать новые телескопы, чтобы найти тёмную материю и даже разрешить парадокс Кота Шрёдингера (кот, запертый в коробке, жив и мёртв одновременно).
Решить шахматную задачу приглашают любого желающего.
Иллюстрация Penrose Institute.
Со стороны может показаться, что перед нами обыкновенная шахматная задача (смотрите заглавную иллюстрацию). Но это не совсем так. Исследователи придумали головоломку, которая поможет учёным наконец-то понять, что же делает человеческое сознание уникальным.
И вот теперь учёные вновь пригласили людей "потягаться" в головоломном конкурсе с целью отыскать сообразительного человека (очень сообразительного).
Параллельно (пока учёные ждут, кто же решит головоломку) был открыт новый Институт Пенроуза (Penrose Institute), основанный сэром Роджером Пенроузом, профессором Математического института при Оксфордском университете.
Пенроуз разделил в 1988 году премию Вольфа по физике с профессором Стивеном Хокингом за блестящее развитие общей теории относительности, в котором они показали неизбежность космологических сингулярностей и объяснили физику чёрных дыр.
Новый институт был создан выдающимся учёным для изучения человеческого сознания посредством физики и выявления основополагающей разницы между искусственным и человеческим интеллектами.
В случае успеха нынешнего шахматного начинания исследователи планируют впервые доказать, что человеческий мозг – это не просто "суперкомпьютер", но в нём также могут иметь место квантовые эффекты, выходящие за рамки сегодняшнего представления о работе главного мыслительного органа. Добавим, что это довольно спорная гипотеза, которую многие учёные считают несостоятельной.
Шахматная задача – изначально составленная сэром Пенроузом — была создана с целью "разгромить" искусственный интеллект (ИИ). Однако её могут решить люди.
Исследователи Института Пенроуза приглашают всех желающих решить, как "белые" могут победить "чёрных", а затем поделиться своими рассуждениями.
Затем специалисты планируют пригласить к себе людей, которые предложат самый быстрый вариант победы, или тех, кому придут в голову самые интересные идеи, и с помощью различных методик просканировать их мозг. Исследователи хотят понять, можно ли заметить в мозге возникновение человеческого "озарения" или "интуиции".
"Если вы предложите решить эту головоломку компьютеру, то он просто ответит, что "чёрные" выиграют из-за количества мест и позиций. Однако человеку ответ не покажется столь очевидным, он, взглянув на головоломку, поймёт, что это не так", — объясняет сэр Пенроуз.
Мы знаем, продолжает учёный, что есть задачи, которые не подвластны даже самому мощному суперкомпьютеру. "Но с ними вполне справится человеческий разум, — говорит Пенроуз. – Но причину этому мы не знаем".
Сейчас на руках учёных уже есть доказательства того, что квантовые эффекты характерны для биологии, например, они имеют место в фотосинтезе или при миграции птиц. "Нечто похожее может происходит и в мозгах. Но это довольно спорная теория", — соглашается основатель нового института.
"Если мы найдём, чем, грубо говоря, люди отличаются от компьютеров, то это может иметь серьёзные социальные последствия. Люди впадают в депрессию, когда размышляют о будущем, в котором роботы всё чаще начинают отбирать рабочие места у человека. Но, возможно, есть области, где компьютеры никогда не смогут заменить нас. Например, в творчестве", — размышляет сэр Пенроуз.
Правда, и с этим можно поспорить, если вспомнить, что интернет-бота научили писать рэп и сочинять музыку, "вдохновляясь" картинами. Роботы уже начинают конкурировать с людьми даже, казалось бы, в творческих сферах – журналистике и литературе.
Однако отчаиваться рано, уверяют специалисты. В 1942 году шифровальщики Блетчли-парка опубликовали в газете The Telegraph кроссворд в надежде привлечь новых криптографов (ниже на фото тот самый кроссворд). И сделать это в итоге удалось: "новобранцы" сыграли решающую роль в оказании помощи союзникам. Тогда читателям газеты было предложено решить головоломку за 12 минут.
Новая шахматная головоломка – одна из нескольких, которые в ближайшем будущем будут опубликованы специалистами Института Пенроуза. На этот раз учёные очень хотят "взломать код" человеческой смекалки.
Специалисты также надеются на основании собранных данных разработать новые технологии для улучшения методик лечения болезней мозга и создания обезболивающих. Кроме того, они намерены предложить новый тип телескопа, которому будет под силу обнаружить тёмную материю, и даже готовы разрешить знаменитый парадокс кота Шрёдингера.
Читайте также: