В чем сила компьютера, брат?

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

Поводом для настоящего сообщения стал очередной успех исследователей. Им удалось доказать, что в популярной игре судоку - знаете, там где нужно вычислить все цифры в квадрате 9x9 по сравнительно небольшому числу известных, при условии, что в каждой строке, каждом столбце и квадрате 3х3 они не повторяются - для однозначного решения подсказок (известных цифр) должно быть не меньше 17 (обычно их, конечно, больше, иначе слишком сложно). Т.е. 16 в любом случае дают несколько возможных решений.

Не берусь сказать, какая от этого открытия польза народному хозяйству, возможно, задача имеет какие-то выходы на криптографию. Но машинного времени исследователи убили изрядно - 7.1 млн "ядерных" часов (т.е. это совокупное время работы всех задействованных вычислительных ядер). Ядер, правда, тоже было немало. Использовался ирландский суперкомпьютер Stokes из 320 узлов с двумя 6-ядерными Xeon каждый. На все про все ушел весь 2011 год (были какие-то перерывы, т.к. задания выдавались блоками).

Что же все это время делал Stokes? Да, именно перебирал варианты. Всего таких квадратов порядка 10^21 (здесь и дальше мантиссы просто опускаю), но большая часть эквивалентны друг другу, поэтому было достаточно исследовать всего лишь порядка 5 млрд, ну и для каждого - различные наборы из 16-и подсказок. В общем, было чем заняться, и справился Stokes, как мы уже знаем, с честью.

Примечательно, что работа по ссылке помечена 1 января 2012 г. Но едва ли это заслуживает пафосных речей о "новой эре". Подобные открытия случались и раньше. Если не ошибаюсь, около 5 лет назад, компьютеры по сути убили русские (64-клеточные) шашки. Тупо за несколько лет (!) перебрали все 10^20 партий. Почему убили? Потому что таким образом было доказано существование беспроигрышной стратегии и за белых, и за черных. Конечно, алгоритма построения правильной игры нет, но для самых популярных дебютов ее можно рассчитать и запомнить на достаточную глубину, а после (когда шашек на доске станет поменьше) человек и сам разберется. Дошло до того, что в некоторых турнирах участники вынуждены разыгрывать одни и те же случайным образом выбранные дебюты.

На самом деле сегодня большинство логических игр компьютеру уже "неинтересны". Насколько я понимаю, держатся еще те, где перебор составляет порядка 10^40 и выше. Например, шахматы. Хотя все, наверное, знают, что компьютеры и их перевели в иную плоскость. Владимир Крамник, довольно красиво проиграв компьютеру одну из партий (весь матч, впрочем, тоже), сказал, что это была "нечеловеческая игра" - т.е. человек так бы не сыграл. Не смог бы просчитать такой вариант. Да, пожалуй, и не стал бы его рассматривать, положившись на общепризнанные тактические принципы. Компьютер же (опять же, благодаря использованию перебора) подобных предрассудков лишен.

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

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

Между прочим, облачные вычисления вполне могут дать этому процессу дополнительный толчок. Amazon недавно подала пример. И кстати, решение задачи судоку на их виртуальном суперкомпьютере было бы не таким уж и дорогим, всего-то 1.5 млн долл без учета возможных скидок :)