Искусство программирования от AlphaCode

[ogn_slon]

Можно надеяться, что со временем компьютеры будут соревноваться с людьми
во всех чисто интеллектуальных областях.
    - Алан Тьюринг, «Вычислительные машины и интеллект»
       (Computing Machinery and Intelligence, 1950)

В блоге DeepMind сообщается, что алгоритм AlphaCode научился решать конкурсные задачи по программированию на уровне среднего

Comments

[fat_yankey]

Мы как-то с вами беседовали по поводу вот этой статьи: http://www.cs.yale.edu/publications/techreports/tr82.pdf

Не могу оттуда не процитировать:

The purpose of the program is an informal, often unstated, criterion and the transition from informal to formal objects must forever be unformalized, lest we be caught in the paradox of assuming the formalization of an object we know only informally.

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

Для AlphaCode (и, естественно, для белковых конкурсантов) задачу формализации проделали составители задач. Они изложили эту формализацию естественным языком, но тем не менее. Ну то есть понятно, что это всё равно впечатляет - в формулировке задачи нет решения в явном виде, есть только правила и желаемый результат.

С другой стороны, то же (нет алгоритма, только правила и результат) верно и для языков высокого уровня типа SQL или Пролог.

[ogn_slon]

Не уверен, что понимаю.

Вот вполне формализованная задача: для каждого целого положительного n определить, конечно или бесконечно количество пар простых чисел вида p1, p2, таких что |p1 - p2| ≤ 2n.
Ввод: n, 0 < n < 123.
Вывод: FIN если конечно, INFIN если бесконечно.
Задача формализации уже решена, осталось (как бы, "всего-навсего") написать собственно алгоритм?

(Я помню, что у вас был пост с обсуждением статьи, содержащей цитату про формализацию, но само обсуждение выветрилось из памяти.)

[fat_yankey]

Тут нужно ещё формализовать понятия простого числа, конечного и бесконечного. Но после этого алгоритм пишется на раз. Только работать он будет бесконечное время. Но это не было граничным условием.

[ogn_slon]

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

Я не сомневаюсь, что четкие и однозначные формулировки конкурсных заданий сильно упростили конструирование и обучение AlphaCode. Но это не меняет мою оценку события на уровне "мир изменился".