Команда из двух новых систем ИИ набрала на один балл меньше золота на глобальном математическом конкурсе для одаренных студентов
Хотя компьютеры были созданы для выполнения математических вычислений быстрее, чем человек, высший уровень формальной математики остается исключительно человеческой сферой. Однако прорыв исследователей из Google DeepMind приблизил системы ИИ к тому, чтобы превзойти лучших человеческих математиков в их собственной игре.
Две новые системы — AlphaProof и AlphaGeometry 2, работали вместе, чтобы решать задачи Международной математической олимпиады (IMO), глобального математического конкурса для школьников, который проводится с 1959 года.
Олимпиада состоит из шести крайне сложных задач, охватывающих области алгебры, геометрии и теории чисел. Золотая медаль дает победителю статус одного из лучших молодых математиков в мире.
Совместные усилия двух систем DeepMind не совсем соответствовали этому уровню. Их ответы оценивал профессор Тимоти Гауэрс — лауреат «медали Филдса» (математического эквивалента «Нобелевской премии») и обладатель золотой медали на олимпиаде, команда DeepMind набрала 28 из 42 баллов — достаточно для серебряной медали, но на один балл меньше золота.
В отличие от человеческого математика, системы либо были безупречны, либо абсолютно беспомощны. В каждой из решенных задач они набрали максимальные баллы, но по двум из шести задач не смогли даже начать работу. Более того, у DeepMind, в отличие от человеческих конкурентов, не было ограничения по времени. В то время как студенты получают девять часов на решение задач, системы DeepMind работали над одной задачей три дня без перерыва, хотя с другой справились за считанные секунды.
Системы сильно различались. AlphaProof, которая решила три задачи, использует крупную языковую модель — такую же, как в чат-ботах, — и специальный подход «обучения с подкреплением», аналогичный тому, который DeepMind использовал для игры в Го. Секрет заключается в использовании существующего подхода под названием «формальная математика», набора правил, позволяющих записать математическое доказательство как программу, которая работает только в том случае, если она верна.
«Мы пытаемся построить мост между этими двумя сферами, чтобы мы могли воспользоваться преимуществами формальной математики и данными, доступными в неформальной математике», — сказал Томас Хьюберт, руководитель проекта AlphaProof.
После обучения на большом количестве задач, записанных на английском языке, AlphaProof использовала свои знания для создания конкретных доказательств на формальном языке. Поскольку эти доказательства могут быть либо истинными, либо ложными, можно обучить систему самоулучшению. Этот подход может решать сложные задачи, но не всегда быстро: хотя он намного лучше простого метода проб и ошибок, на одну из самых сложных задач ушло три дня.
Другая система, AlphaGeometry 2, аналогично сочетает языковую модель с более математически ориентированным подходом. Но ее успех в узкой области геометрических задач был поразителен: задача была решена всего за 16 секунд. И, как отметил Гауэрс, система выбрала неожиданный путь для этого. «Существуют легендарные примеры компьютерных доказательств, которые длиннее, чем Википедия. Это не тот случай: речь идет о очень кратком, человекоподобном решении.»
Руководитель проекта AlphaGeometry 2, Тханг Луонг, описал результат как аналог знаменитого «хода 37» в исторической победе DeepMind в Го, когда ИИ сделал ход, о котором ни один человек бы не подумал, и выиграл.
Доказательство AlphaGeometry 2 включало построение окружности вокруг другой точки и использование этой окружности для доказательства общего ответа. «Сначала наш эксперт не совсем понял, зачем вообще была построена эта точка, но после изучения решения стало ясно, что оно действительно объединяет множество треугольников, и решение оказалось весьма элегантным», — сказал Луонг.
Пример одной из задач AlphaGeometry 2:
Пусть ABC — треугольник с AB < AC < BC. Пусть I — центр вписанной окружности треугольника ABC, а ω — вписанная окружность. Пусть X — точка на прямой BC, отличная от C, такая что прямая, проходящая через X параллельно AC, касается ω. Аналогично, пусть Y — точка на прямой BC, отличная от B, такая что прямая, проходящая через Y параллельно AB, касается ω. Пусть AI пересекает описанную окружность треугольника ABC снова в точке P ≠ A. Пусть K и L — середины AC и AB соответственно.
Докажите, что ∠KIL + ∠YPX = 180°.
Задача была решена за 19 секунд.
Самая сложная задача AlphaProof
Улитка по имени Турбо играет в игру на доске с 2024 рядами и 2023 столбцами. В 2022 клетках спрятаны монстры. Изначально Турбо не знает, где находятся монстры, но знает, что в каждом ряду, кроме первого и последнего, точно по одному монстру, и что в каждом столбце не больше одного монстра.
Турбо делает серию попыток пройти с первого ряда до последнего. В каждой попытке он выбирает любую клетку в первом ряду, а затем неоднократно переходит в соседнюю клетку, имеющую общую сторону. (Он может вернуться в ранее посещенную клетку.) Если он достигает клетки с монстром, его попытка заканчивается, и он возвращается в первый ряд, чтобы начать новую попытку. Монстры не двигаются, и Турбо запоминает, содержит ли каждая посещенная им клетка монстра. Если он достигает любой клетки в последнем ряду, его попытка заканчивается, и игра заканчивается.
Определите минимальное значение n, для которого у Турбо есть стратегия, гарантирующая достижение последнего ряда на n-й попытке или раньше, независимо от расположения монстров.
Эта задача осталась нерешенной.
https://deepmind.google/discover/blog/ai-solves-imo-problems-at-silver-medal-level/
Комментарии (13)
peterjohnsons
07.08.2024 08:20Я ни разу не математик, но ради интереса задал эту задачку Sonnet 3.5. Она выдала решение за 10-15 секунд. Но правильное ли, мне не известно ? Но убедительно)
Давайте разберем эту геометрическую задачу шаг за шагом:
-
Сначала обозначим ключевые элементы:
ABC - треугольник, где AB < AC < BC
I - центр вписанной окружности ω
X - точка на BC, где прямая через X || AC касается ω
Y - точка на BC, где прямая через Y || AB касается ω
P - точка пересечения AI с описанной окружностью (кроме A)
K - середина AC
L - середина AB
Ключевое наблюдение: в треугольнике ABC, AI - биссектриса угла BAC.
-
Рассмотрим ∠KIL:
KI и LI - это медианы к сторонам AC и AB соответственно
∠KIL = 1/2 ∠BAC (так как AI - биссектриса)
-
Теперь рассмотрим ∠YPX:
AP - диаметр описанной окружности (так как AI ⊥ BC в треугольнике)
∠YPX вписанный, опирается на дугу YX
∠YPX = 1/2 ∠YAX (вписанный угол равен половине центрального)
-
Ключевой момент: ∠YAX = 180° - ∠BAC
Это следует из того, что YX || BC (поскольку Y и X выбраны так, что прямые через них параллельны сторонам треугольника)
Следовательно:
∠YPX = 1/2 (180° - ∠BAC) = 90° - 1/2 ∠BACТеперь сложим углы:
∠KIL + ∠YPX = 1/2 ∠BAC + (90° - 1/2 ∠BAC) = 90°Удваиваем обе части:
2(∠KIL + ∠YPX) = 180°Следовательно:
∠KIL + ∠YPX = 180°
Что и требовалось доказать.
OlegFX
07.08.2024 08:20Как будто если в пункте 8:
2(∠KIL + ∠YPX) = 180°
То ∠KIL + ∠YPX должно быть 90°? И не имело смысла удваивать после пункта 7, где этот результат уже был получен.
То есть, не очень убедительно.
-
MainEditor0
07.08.2024 08:20Терри Тао недавно провел доклад-лекцию в Оксфорде на тему роли ИИ в математике. The Potential for AI in Science and Mathematics - Terence Tao
Deosis
Самая простая стратегия - идти вертикально вниз в каждом ряду. Она гарантированно сработает не более чем за 2023 хода. Так как есть столбец, свободный от монстров.
Более того, в любой оптимальной стратегии потребуется не более 2023 ходов, так как предыдущие ходы выяснят положение всех монстров.
Осталось либо доказать, что нельзя за меньшее число ходов гарантированно прийти к финишу, либо предложить лучшую стратегию.
Alexandroppolus
Сильно подозреваю, что можно меньше. Например, выясним номера строк для монстров в первом, центральном и последнем столбцах, пусть это значения А, В, С. Если они во всех трех оказались, то либо |A - B| != 1011, либо |B - C| != 1011. Там, где это неравенство имеет место, у нас 1012 подряд идущих столбцов, не перегороженных сплошным диагональным "забором", и можно выполнить задачу, используя только эти столбцы, итого 1015 (или 1016) попыток. Но можно продолжить этот бинарный поиск и далее, радикально уменьшив результат до чего-то, похожего на ln(n).
А вот как это наиболее хитро обыграть, да ещё и доказать оптимальность результата - совсем другая история...
novoselov
Перечитал условия 2 раза, нужно узнать минимальное количество попыток, а не ходов.
Первая попытка: выбираем 2 столбец (x=2) и двигаемся строго вниз, в итоге либо доходим до конца (n = 1), либо утыкаемся в монстра допустим на ряду под номером y.
Вторая попытка: повторяем предыдущий путь, но в ряду y-1 сдвигаемся вправо (x+1, y-1) и дальше вниз (x+1, y) и вниз (x+1, y+1). В итоге либо утыкаемся в монстра (идем на 3 попытку) либо находим пустую клетку, тогда возвращаемся в исходную колонку (x, y+1) и спокойно спускаемся вниз, так как в этой колонке монстра уже нет (n=2).
Третья попытка: повторяем предыдущий путь как и в прошлой попытке, но теперь сворачиваем влево (x-1, y-1), обходим монстра слева (x-1, y) и вниз (x-1, y+1) и возвращаемся в исходную колонку (x, y+1). Слева монстра быть не может, так как монстра мы нашли во 2 попытке, и дальше опять можно спускаться вниз (n=3).
Минимальное количество: n=3.
Alexandroppolus
А с чего вы взяли, что в клетке (x-1, y-1) не монстр?
По факту, надо найти либо столбик без монстра, либо два соседних столбика, у которых клетки с монстрами не граничат по углу (тогда делаем маневр как в вашем втором шаге). Проблема именно в непрерывных диагональных линиях с монстрами, сквозь которые не проскочить. Например, если монстры сидят в клетках (1, y-1), (2, y), (3, y+1), то нельзя ограничиться только лишь колонками 1, 2 и 3.
novoselov
Да, тоже проснувшись про это подумал. Слишком простое решение за 5 минут чтобы быть правильным :)
Там в окрестности одной точки 7 вариантов размещения монстров, 5 их них просто обходятся, 2 образуют диагональ.
Можно спуститься по средней колонке до первой точки (1012, y)
Проверить точку справа (1013, y-1), если она занята, то у нас предположительно диагональ идет вверх [/].
Будем двигаться от точки (1012, y) вправо и на клетку выше предполагаемой восходящей диагонали [//], если встретим на ней занятую клетку, значит мы нашли брешь в диагонали через которую можно зайти и спуститься вниз.
Если дошли до верха возвращаемся в исходную точку (1012, y), дальше можем пытаться проверить так же спуск влево вниз. А если встретим нисходящую диагональ [\], будем достраивать ее в обратную сторону [\\].
В лучшем случае у нас будет либо снова брешь. Либо одна сплошная диагональ [//] или две сходящиеся диагонали [\\//] без понимания что под ними :)
Дальше можно разбивать половины диагонали пополам, отсекать ненужные части и искать брешь по другому алгоритму, но вполне возможно есть более оптимальный вариант :)
P.S. главное условие победы подойти к монстру снизу
avdx
За логарифмическое количество попыток путь находится. Спускаемся по среднему столбцу, пока не уткнемся. Исходя из локальной конфигурации 3х2, на определение которой нужно не больше двух попыток, можно либо понять, что мы нашли проход, либо узнать в левой или в правой части (либо в обеих) точно есть проход, тогда задача сводится к исходной, только с шириной в два раза меньше. Таким образом путь находится бинарным поиском.
novoselov
После проверки конфигурации проход есть только в одной части и вы не знаете в какой именно. Поэтому только бинарного поиска недостаточно.
avdx
Знаем в какой именно. Допустим у нас конфигурация, что закрашена клетка слева вверху от той, куда мы уперлись. Тогда у нас есть две области: слева вверху от конфигурации 2х2 из этих двух клеток и справа внизу. Для этих областей известен проход как к линии целиком над ними, так и выход с линии целиком под ними. Т.е. вопрос только в проходе через эти области, при этом для каждой области ситуация аналогична исходной. Очевидно, что проход точно есть в той области, где число столбов больше, чем число строк. Это условие будет всегда выполняться как минимум для одной из этих двух областей. Для конфигурации, когда закрашена клетка справа сверху, ситуация просто зеркальна.
Kergan88
не пойдет. я расставлю монстров на диагонали, не заполняя крайние ряды (т.о. у меня останется 1 свободный монстр). когда вы проверите середину и решите пойти влево - я поставлю этого монстра скраю слева, и слева не будет прохода. если решите пойти вправо - я поставлю его вправо и справа не будет прохода. в итоге куда бы вы не пошли - там прохода не будет.
avdx
Область неквадратная - в ней количество столбцов больше чем количество строк, поэтому у нее нет одной диагонали, будет как минимум два варианта диагонали, каждый их которых заранее определяет, где будет проход. Можете сами проверить на примере области 4x3. Если вы поставите "монстров" на верхней диагонали (в координаты (x, y): (2, 2,), (3,1)), то правила расстановки не позволяют вам перекрыть проход справа, а если на нижней диагонали ((2,3), (3,2)), то не сможете перекрыть проход слева. Для зеркальных диагоналей то же самое.