RICH с нуля: короткие прибыльные круги с цветовым кодированием

Урок 8 курса "Собери своего арбитражного бота". Беллман-Форд и SPFA находят любой прибыльный круг. Сегодня вы познакомитесь с идеей недавнего исследовательского алгоритма, который находит хорошие короткие круги.

Почему "любой круг" недостаточен

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

Поэтому боту нужен другой вопрос: найдите прибыльный круг не более чем с k шагами. Информатики называют это задачей поиска отрицательного цикла с k переходами. Бот сам выбирает k (часто это 3, 4 или 5).

Исследовательская статья, на которой основан этот урок, называется "RICH: Real-time Identification of negative Cycles for High-efficiency Arbitrage" (Luo, Jiang и соавторы, PVLDB volume 18, VLDB 2025). Авторы сообщают, что RICH работает до 32.7 раза быстрее прежних методов на данных о криптовалютах и валютном рынке. Их подход основан на старом приеме, который называется цветовым кодированием, и на нескольких инженерных идеях, сокращающих работу. Сегодня мы соберем основной прием и оставим за рамками инженерную часть. Упрощенная версия в этом уроке - не их код.

Прямой подход и его ограничения

Чтобы найти лучший круг не более чем с k шагами из начального узла, можно попробовать каждый путь длиной до k. При 300 валютах и 6 парах для каждой число путей длиной 4 составляет примерно 6⁴ = 1296 на начальный узел, что приемлемо. При 300 валютах, каждая из которых торгуется со 100 другими, получится 100⁴ = 100 миллионов на начальный узел, что уже неприемлемо.

Более умный способ - динамическое программирование: запоминать для каждого узла и каждого числа шагов самый дешевый путь к нему. Это в точности Беллман-Форд с числом раундов, ограниченным k. Но есть загвоздка: самый дешевый маршрут из k шагов может повторно посетить валюту. "Круг" USD, EUR, USD, EUR, USD из четырех шагов не является новой реальной возможностью: это двухшаговый круг, повторенный дважды. Нужны круги, которые посещают каждую валюту один раз; их называют простыми циклами. Требование, чтобы путь не повторял узлы, и делает задачу сложной.

Прием цветового кодирования

Вот прием, который звучит нелепо, но хорошо работает.

Назначьте каждой валюте случайный цвет из k цветов. (Если k = 3, каждая валюта случайно становится красной, зеленой или синей.)
Теперь ищите только круги, где на каждом шаге цвет отличается: один красный, один зеленый, один синий. Такой круг не может посетить одну и ту же валюту дважды, потому что повторная валюта повторила бы свой цвет.
Этот ограниченный поиск прост, потому что нужно запоминать только уже использованные цвета, а не валюты. При k цветах существует лишь 2ᵏ наборов использованных цветов. При k = 3 это 8, при k = 5 это 32.
Настоящий прибыльный круг можно пропустить, потому что две его валюты получили один цвет. Но если случайно перекрашивать валюты и повторять поиск, он будет найден. Вероятность, что один конкретный круг из k валют получит k разных цветов, равна k!/kᵏ (для k = 3: 6/27, около 22 процентов; для k = 4: 24/256, около 9 процентов). Если повторить 50 или 100 раз, вероятность пропустить его станет очень малой.

Аналогия: раскрасьте каждого человека в толпе в один из трех случайных цветов, затем ищите группу из трех человек трех разных цветов. Сделайте это снова с новыми случайными цветами, а потом еще раз. Любая группа из трех настоящих друзей рано или поздно одновременно получит три разных цвета.

Разбор маленького примера

Валюты: USD, EUR, GBP, JPY. Ищем лучший круг через USD не более чем с 3 шагами.

Предположим, в этом раунде случайные цвета такие: USD красный, EUR зеленый, GBP синий, JPY зеленый.

Поиск хранит таблицу. В каждой строке сказано: "Я нахожусь в этом узле, использовал эти цвета, самая низкая стоимость пока такая, а путь был таким".

Начало: в USD, использован {красный}, стоимость 0.
Шаг 1: из USD в EUR (зеленый, еще не использован): в EUR, использованы {красный, зеленый}, стоимость +0.1054. Из USD в GBP (синий): в GBP, использованы {красный, синий}, стоимость +0.2877 (вес 0.75).
Шаг 2: из EUR в GBP (синий, еще не использован): в GBP, использованы {красный, зеленый, синий}, стоимость 0.1054 + 0.1278 = 0.2332. Из EUR в JPY (зеленый): зеленый уже использован, пропускаем.
Замыкаем круг: из GBP обратно в USD стоимость −0.2624. Итого 0.2332 − 0.2624 = −0.0292. Итог отрицательный, значит USD, EUR, GBP, USD - прибыльный простой круг.

Если бы цвета были такими: USD красный, EUR зеленый, GBP зеленый, круг был бы пропущен в этом раунде (EUR и GBP оба зеленые), а в следующем раунде с другими цветами был бы найден.

Код

import math, random

random.seed(7)
rates = {("USD", "EUR"): 0.90, ("EUR", "GBP"): 0.88, ("GBP", "USD"): 1.30,
         ("EUR", "USD"): 1.10, ("GBP", "EUR"): 1.10, ("USD", "GBP"): 0.75,
         ("USD", "JPY"): 150.0, ("JPY", "USD"): 0.0066,
         ("EUR", "JPY"): 160.0, ("JPY", "EUR"): 0.0062}
nodes = sorted({n for edge in rates for n in edge})
w = {edge: -math.log(r) for edge, r in rates.items()}

def best_cycle_through(start, k, rounds=200):
    """Cheapest cycle through `start` with at most k steps, by colour-coding."""
    best = (math.inf, None)
    for _ in range(rounds):
        colour = {n: random.randrange(k) for n in nodes}
        # table[(node, набор использованных цветов)] = (стоимость, путь); набор - это битовая маска
        table = {(start, 1 << colour[start]): (0.0, [start])}
        for _step in range(k - 1):
            for (node, used), (cost, path) in list(table.items()):
                for (a, b), wt in w.items():
                    if a != node or b == start:
                        continue
                    bit = 1 << colour[b]
                    if used & bit:
                        continue                      # этот цвет уже использован
                    key = (b, used | bit)
                    if key not in table or cost + wt < table[key][0]:
                        table[key] = (cost + wt, path + [b])
        for (node, used), (cost, path) in table.items():
            if (node, start) in w and cost + w[(node, start)] < best[0]:
                best = (cost + w[(node, start)], path + [start])
    return best

cost, path = best_cycle_through("USD", 3)
print(path, "cost", round(cost, 4), "money x", round(math.exp(-cost), 4))

Результат:

['USD', 'EUR', 'GBP', 'USD'] cost -0.0292 money x 1.0296

Программа нашла прибыльный круг из трех шагов и его множитель 1.0296.

Чего нет в этой упрощенной версии

Во внутреннем цикле она перебирает все ребра, а это медленно. В настоящей реализации исходящие дороги хранятся для каждого узла.
Сначала она не сокращает граф. В статье описаны сокращение графа и компактное кодирование, которые и дают большую часть ускорения.
Она дает вероятностный ответ: при случайных цветах есть небольшая вероятность пропустить круг, которая уменьшается с числом раундов.
Она обрабатывает один начальный узел. Бот перебирает начальные узлы или использует одну таблицу для всех.

Воспринимайте урок как способ понять, почему цветовое кодирование делает поиск небольшим (всего 2ᵏ наборов цветов), а инженерные детали читайте в статье.

Когда это окупается?

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

Попросите ИИ-агента написать и проверить код

Расплывчатый запрос:

Реализуй RICH.

Запрос с ограничениями и проверкой:

Не реализуй всю статью о RICH. Напиши colour_cycle.py с функцией best_cycle_through(start, k, rounds), которая с помощью цветового кодирования находит самый дешевый простой цикл через начальную валюту не более чем с k шагами: случайный цвет для каждой валюты, таблица с ключом (узел, битовая маска использованных цветов), много повторов со случайными раскрасками. Используй веса минус натуральный логарифм курса. Проверка: с десятью курсами из этого урока, начальная валюта USD, k = 3, функция должна вернуть USD, EUR, GBP, USD с денежным множителем 1.0296. Проверка 2: умножь все курсы на 0.95, функция не должна вернуть отрицательную стоимость. Храни исходящие ребра для каждого узла, а не перебирай все ребра.

Затем спросите агента: "Что ты оставил за рамками по сравнению со статьей?" Хороший агент перечислит пропущенные части. Если он утверждает, что реализовал всю статью, не верьте ему.

Ваше упражнение

Запустите код. Вы должны увидеть множитель 1.0296.
Измените rounds с 200 на 3, 5 и 10, запуская каждую настройку 20 раз с разными начальными значениями генератора. Как часто круг не находится? Сравните с вероятностью k!/kᵏ = 6/27 за раунд при k = 3.
Посчитайте вручную вероятность пропустить круг из трех валют после 10 раундов: (1 − 6/27)¹⁰ ≈ 0.08.
Посчитайте вручную произведение курсов для USD, JPY, EUR, USD (150 × 0.0062 × 1.10). Оно равно 1.023, это второй прибыльный круг, меньше первого. Запустите код с k = 3 и rounds = 200 и подтвердите, что программа предпочитает первый, затем объясните почему через веса.

Что дальше

Мир 2 на этом заканчивается. Ваш этап 1 теперь может находить прибыльные круги в графе курсов. Но все эти курсы - лучшие цены из стакана, годные только для очень небольшой суммы. Мир 3 открывает стакан заявок и спрашивает, сколько денег круг на самом деле может провести. Урок 9 начинается с чтения и обхода стакана заявок.