Что произойдет, если две идентичные шахматные программы сойдутся в поединке? Будут ли все партии заканчиваться вничью, или у белых, благодаря первому ходу, будет стратегическое преимущество? И существует ли универсальная выигрышная стратегия, которая позволила бы новичку одержать верх над гроссмейстером? Эти вопросы долгое время волновали умы исследователей.
В этой статье мы углубимся в историю противостояния человека и машины за шахматной доской. Хотя строгой математики здесь будет немного, мы затронем колоссальные числа, описывающие сложность игры. Шахматы стали для теории игр и искусственного интеллекта тем же, чем двигатель для самолета — фундаментальной движущей силой и испытательным полигоном.
Несравнимая сложность: шашки против шахмат
На фоне шахмат даже сложные шашки кажутся простой задачей. Напомним, что для английских шашек общее количество возможных партий составляет 5×10^20. Полный перебор всех вариантов, осуществленный специальной программой, занял 18 лет непрерывных вычислений.
*Важно отметить, что компьютер научился обыгрывать человека в шашки гораздо раньше. Главной целью того проекта был не просто выигрыш, а построение полного «дерева решений» — исчерпывающего знания последствий любого хода до конца игры.
Здесь возникает закономерный вопрос: раз с шашками справились, почему бы не проделать то же самое с шахматами? Подождем еще лет двадцать, и, возможно, в 2040 году, листая новости, мы увидим сообщение о полном решении шахмат. К сожалению, на сегодняшний день это чистая утопия.
Число Шеннона: астрономическая сложность игры
Проблема заключается в фантастической сложности самой игры. Количество возможных позиций фигур на доске оценивается примерно в 10^46, а число уникальных партий (так называемое «число Шеннона») превышает 10^120.
Десять в сто двадцатой степени — это число, не имеющее аналогов в наблюдаемой Вселенной. Для сравнения: количество атомов в видимой части космоса оценивается в 10^80. Таким образом, число возможных шахматных партий больше этого значения в 10^40 раз! Сложность нарастает лавинообразно: после первого хода белых существует 20 вариантов, после ответа черных — уже 400 возможных позиций. После второго хода с каждой стороны это число вырастает до 72 084, после третьего — превышает 9 миллионов, а после четвертого — переваливает за 288 миллиардов, что сопоставимо с количеством звезд в нашей галактике. И это лишь самое начало партии.
Шахматы как двигатель прогресса
Не зря шахматы называют «двигателем» теории игр. Еще на заре компьютерной эры, после Второй мировой войны, они стали ключевым испытательным стендом для алгоритмов и идей в области искусственного интеллекта. Клод Шеннон (в честь которого и названо то самое гигантское число), один из пионеров этой науки, отмечал, что хотя практическая ценность полного перебора всех партий сомнительна, сама эта цель служит мощным стимулом для технологического развития.
Первая в истории шахматная программа была создана Дитрихом Принцем, коллегой Алана Тьюринга, в 1952 году для компьютера Ferranti Mark. Возможности машины были крайне ограничены: объема ее памяти хватало лишь на алгоритм поиска «мата в два хода», работавший только на финальной стадии игры.
Обратите внимание: "ПромСтройКомплект" и услуги, которые предоставляет компания.
Несмотря на скромность, это было историческое начало.
В 1956 году компьютер MANIAC-1 сыграл три партии в упрощенные шахматы (на доске 6×6 и без слонов). Он проиграл опытному игроку (даже тому, кто начал партию без ферзя), но одержал победу над новичком. Это событие вошло в историю как первая победа машины над человеком в шахматах.
Восхождение машин: от микропроцессоров к чемпионским титулам
С изобретением микропроцессора в 1971 году вычислительная мощь компьютеров резко возросла. Это позволило хранить в памяти огромные базы дебютов и эндшпилей. В 1974 году прошел первый чемпионат мира среди шахматных программ. Уже в 1978 году машина впервые обыграла международного мастера, а в 1981-м программа Cray Blitz первой среди компьютеров получила рейтинг мастера.
Однако долгое время алгоритмы оставались относительно простыми и основывались на методе «минимакса» с отсечениями (альфа-бета-отсечение), по сути, представляя собой усложненный перебор вариантов. Преимущество одной программы над другой определялось в основном мощностью «железа» и объемом загруженных в нее партий гроссмейстеров. Ярким примером такого подхода был суперкомпьютер Deep Blue от IBM.
Переломный момент: Deep Blue против Каспарова
Легендарным Deep Blue стал 11 мая 1997 года, выиграв матч из шести партий у действующего чемпиона мира Гарри Каспарова. Интересно, что за восемь лет до этого Каспаров с легкостью победил его предшественника, Deep Thought. Тогда гроссмейстер заявил, что не верит в возможность создания машины, которая превзойдет лучшего из людей, и пообещал защитить честь человечества. События 1997 года заставили его пересмотреть эту точку зрения.
Deep Blue
Окончательную точку в противостоянии поставил 2005 год — последний раз, когда человеку удалось выиграть партию у топовой шахматной программы в официальном матче. Сегодня разрыв в рейтинге стал непреодолимым: на начало сентября 2022 года наивысший рейтинг человека (Магнус Карлсен) составлял 2861, в то время как лучшие программы, такие как Stockfish, имеют рейтинг около 3535.
Неразрешенная задача и будущее
Несмотря на абсолютное превосходство компьютеров над людьми, шахматы как математическая задача остаются нерешенными. Мы до сих пор не знаем, к какому результату (победа белых, ничья, победа черных) приведет идеально сыгранная с обеих сторон партия. Ученые склоняются к гипотезе, что у белых есть небольшое преимущество первого хода, но доказать это пока не могут. Надежду дает развитие квантовых вычислений, способных анализировать множество вариантов одновременно, однако революционного алгоритма для полного решения игры пока не создано. Универсальной выигрышной стратегии для «чайника» не существует.
Хотя шахматы как испытательный полигон для ИИ уступили место более сложным играм вроде Go и StarCraft, подходы, отработанные на шахматной доске, легли в основу современных методов машинного обучения. И сама мысль о том, что решение существует в принципе, и мы движемся к нему, пусть и не имея пока достаточных ресурсов, продолжает вдохновлять ученых и инженеров.
Автор - Александр Грибоедов
Ещё нас можно читать в ВК, телеге и Дзене
Больше интересных статей здесь: Производство.
Источник статьи: Компьютеры, которые играют в игры.