Популярная шахматная задача, в которой на доске нужно расставить восемь ферзей так, чтобы они не угрожали друг другу, привлекает внимание математиков и программистов уже много лет, однако никто пока так и не смог написать компьютерную программу, которая быстро решила бы эту головоломку.
Задачу о восьми ферзях в 1848 году сформулировал немецкий шахматист Макс Беццель. Доктор Франц Наук в 1850-м опубликовал 92 решения задачи. Математик Джеймс Глэшер из Великобритании в 1874 году доказал, что эти 92 позиции исчерпывают все возможности решения головоломки.
Решить задачу очень сложно с учетом огромной силы ферзя. Игрок должен гарантировать, что каждый ферзь не угрожает никакому другому ни по диагонали, ни по вертикали, ни по горизонтали
Искусственный интеллект пока не может решить задачу о возьми ферзях в разумные сроки. Компьютерные программы берут «грубой силой», систематически перебирая все возможные позиции. Но этот подход чрезвычайно ресурсоемкий и неэффективный, занимающий много лет. Причина в «поиске с возвратом» — алгоритме, используемом в программировании, когда каждый возможный вариант рассматривается и «отбрасывается» вплоть до нахождения решения. Очевидно, что для достижения поставленной цели машина должна «думать» по другому алгоритму.
Ведущий исследователь Йен Гент из школы компьютерных наук Университета Сент-Эндрюс (Великобритания) узнал о задаче после того, как его френд в Facebook предложил ему решить эту головоломку. Сейчас Гент и его коллеги — Питер Найтингейл и Кристофер Джеферсон — борются за приз в $1 млн, предложенный Математическим институтом Клэя (США) за программу, быстро находящую решение.
Объявленный приз — это не просто вызов для компьютерщиков. Гент убежден, что софт, который эффективно обойдет существующие проблемы, будет способен решать задачи, которые считаются невозможными и приведут к разработке принципиально новых подходов, в том числе и в сфере безопасности.
«Эти задачи включают в себя создание самой большой группы друзей в Facebook, которые не знают друг друга, или такие важные вещи, как взлом кодов, которые держат в безопасности все наши онлайн-транзакции», — отмечает Гент.
Кроме того, команда, которая представит программу, отвечающую требованиям, помимо денежного вознаграждения будет первой, кто сможет вывести технологию на рынок.
