Челлендж недели: за решение <<простой>> шахматной задачи предложили миллион долларов. Хотите попробовать?

Математики из Сент-Эндрюсского университета в Шотландии обещают любому, кто справится с <<задачей о восьми ферзях>> в более общем виде, предложив для неё программное решение, миллион долларов. Программа должна расставить на доске 1000 на 1000 клеток тысячу ферзей, которые не бьют друг друга, и не потратить на это годы. Тому, у кого получится, считают исследователи, подвластна задача практически любой сложности.

Команда математиков, занимающаяся проблемами искусственного интеллекта в Сент-Эндрюсском университете, решила радикально подойти к решению одной из самых захватывающих отвлечённых задач для суперкомпьютеров. Тому, кто научит компьютер решать <<задачу восьми ферзей>> для доски в тысячу на тысячу клеток, они заплатят миллион долларов. Челлендж официально объявлен на сайте университета, а статья о задаче опубликована в Journal of Artificial Intelligence Research.

В частном виде задача, которую придумали ещё в 1850 году, звучит просто: нужно расставить на обычной шахматной доске восемь королев таким образом, чтобы ни одна из них не била другую.

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

Даже в общем виде, для доски любого размера, хоть миллион на миллион с миллионом ферзей программа не будет громоздкой. Нью-Йоркский математик Пол Батлер, например, предложил элегантное решение длиной ровно в один твит: 140 символов.

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

Интерес к шахматам в нулевые, после того как компьютеры стали регулярно и уверенно обыгрывать людей, сильно упал. В 2015 году программисты создали программу Giraffe, которая, самостоятельно обучившись, играя сама с собой в течение 72 часов, потом без труда (и без баз шахматных партий) обыгрывала гроссмейстеров.

Всё изменилось после матча между россиянином Сергеем Карякиным и норвежцем Магнусом Карлсеном за звание чемпиона мира в прошлом году. Матч, в котором на кону стоял 1 миллион евро, в прямой трансляции смотрели сотни тысяч людей по всему миру, на три недели он стал одной из главных тем в новостях. После того как Карлсен защитил титул чемпиона, в соцсетях даже люди, едва знакомые с шахматами, долго обсуждали поединок.