Искусственный интеллект научился «решать» задачи по соревновательному программированию

Об этом в начале декабря прошлого года нам сообщила компания DeepMind.

При первом рассмотрении достижение очень впечатляет. Особенно если посмотреть на примеры задач, с которым справился искусственный интеллект. Также поражает, что в сравнении с людьми, решавшими те же задачи, он вошел в top 54%.

При втором рассмотрении достижение по-прежнему впечатляет, но уже без вау-эффекта. Почему?

Есть нюансы.

Исходя из своего опыта соревновательного программирования, могу сказать следующее:

1. хоть авторы статьи и утверждают, что задачи с соревнований всегда разные и никогда не повторяются, в действительности это не так. Я бы сказал, что часто одни и те же задачи по-разному «упаковываются». То есть одна и та же задача может звучать в куче разных формулировок. Особенно это относится к простым задачам, именно тем, которые и научился «решать» искусственный интеллект

2. соревновательное программирование, по большей части, построено на шаблонах решений, которых ограниченное количество. Особенно это относится, опять же, к простым задачам, для решения которых достаточно применить один простой шаблон. Видимо, модель научилась распознавать этот шаблон по условию задачи (как я уже сказал в предыдущем пункте, один и тот же шаблон «упаковывается» во множество разных оберток). По крайне мере, это было бы ожидаемо. Если решение шаблонное, то и разные формулировки задачи тоже должны, в итоге, следовать общему шаблону. Люди к соревновательным задачам — да и вообще к любым — чаще всего подходят так же: пытаются узнать в незнакомой формулировке уже знакомую задачу. Наиболее сложные задачи могут требовать креативных новых подходов либо комбинирования нескольких довольно сложных шаблонов. Но это топ-уровень. Туда искусственный интеллект (пока?) не пришёл

3. решить задачу на соревнованиях часто не то же самое, что «действительно её решить». На соревнованиях решение засчитывается, если программа проходит все автоматизированные тесты. Программа, которая не решает задачу полностью — то есть для любых допустимых входных данных и в пределах заданных ресурсных ограничений — по-прежнему может пройти все тесты. Такие случаи известны даже для соревнований высокого уровня. Признаюсь, что сам иногда умудрялся получать за задачу полный балл, в действительности не имея полного решения

4. по-хорошему, в «реальном мире» (то есть для задач, которые возникли в боевых условиях и не были заранее подготовлены для соревновательных целей) решить задачу — это не просто написать программу, но ещё и показать, что она действительно решает задачу. В частности, задача, которая приводится в блоге DeepMind в качестве примера, имеет тривиальное решение, но! Обоснование этого решения требует одного нетривиального логического хода. Необходимо показать корректность жадного алгоритма, а именно, что если на концах обеих строк оказалась одна и та же буква, то эту букву можно «зачесть» и перейти к мэтчингу следующей буквы. Я допускаю, что некоторые люди, получившие за эту задачу полный балл, не смогли бы обосновать свое решение. Опираясь на «чуйку» и на оценку сложности задачи в сравнении с другими задачами из того же раунда, и поигравшись с примерами, они могли бы, не придя к полному обоснованию, заключить, что решение будет, скорее всего, корректным. Такое поведение вполне допустимо в условиях соревнований. Во-первых, из-за уже перечисленных соображений. Во-вторых, лучше попробовать хоть какой-то вариант, чем не попробовать никакой. Во-третьих, для сложных задач опытные игроки могут только наметить обоснование у себя в голове, понимая, что при желании, его можно довести до конца. Ведь они знают, что задача обязательно имеет решение, реализуемое в обозначенные условиями соревнований сроки, поэтому каких-то серьезных «подстав» можно не ожидать. В «реальном мире» всё иначе. Часто про сложность задачи ничего не известно либо уже заранее известно, что эффективного решения для неё не существует. В боевых условиях очень важно уметь доказывать корректность алгоритма. А с этим у искусственного интеллекта пока что вообще никак. Он может что-то сгенерировать, что проходит какие-то тесты. А вот поди докажи корректность решения…

Но даже при всём при этом, результат, полученный компанией DeepMind, конечно же, впечатляет.