Искусственный интеллект поборется за миллион долларов

09.02.2018

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

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

Задачу о восьми ферзях в 1848 году сформулировал немецкий шахматист Макс Беццель. Доктор Франц Наук в 1850-м опубликовал 92 решения задачи. Математик Джеймс Глэшер из Великобритании в 1874 году доказал, что эти 92 позиции исчерпывают все возможности решения головоломки.

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

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

Ведущий исследователь Йен Гент из школы компьютерных наук Университета Сент-Эндрюс (Великобритания) узнал о задаче после того, как его френд в Facebook предложил ему решить эту головоломку. Сейчас Гент и его коллеги — Питер Найтингейл и Кристофер Джеферсон — борются за приз в $1 млн, предложенный Математическим институтом Клэя (США) за программу, быстро находящую решение.

Йен Гент (слева) и Питер Найтингейл
Йен Гент (слева) и Питер Найтингейл

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

«Эти задачи включают в себя создание самой большой группы друзей в Facebook, которые не знают друг друга, или такие важные вещи, как взлом кодов, которые держат в безопасности все наши онлайн-транзакции», — отмечает Гент.

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

Techdiver.ru