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

[ogn_slon]

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

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

Comments

[lj_frank_bot]

Hello!
LiveJournal categorization system detected that your entry belongs to the category: IT.
If you think that this choice was wrong please reply this comment. Your feedback will help us improve system.
Frank,
LJ Team

[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

[ogn_slon]

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

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

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

[fat_yankey]

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

[ogn_slon]

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

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

[livejournal]

Hello! Your entry got to top-25 of the most popular entries of the Northern region in LiveJournal! Learn more about LiveJournal Ratings in FAQ.