Spiiin's blog

1 - (2009) Python in imaginary world
2 - (2015) Scala in imaginary world
3 - (2021) Nim in imaginary world
4 - (2022) daScript in imaginary world
5 - (2023) AI in imaginary world
6 - (2024) F# in imaginary world
7 - (2025) C++ in imaginary world
8 - (2025) IDA* in imaginary world

Моя Римская империя — это маленькая задачка-пазл из игры James Bond Jr на NES. Я возвращаюсь к ней иногда, когда учу новые языки, или хочу попробовать что-нибудь из алгоритмов.

В последний раз я решал её на C++ с целью посмотреть, насколько можно разогнать её относительно других языков (и попробовать разные хеш-таблицы и алгоритмы), а затем просто изучал алгоритмически на Python, насколько можно разогнать части алгоритма.

На С++ я дошёл до того, чтобы решить её за 750 микросекунд, если взять ska::flat_hash_map, настроить хеширование на минимум коллизий и максимум скорости, а также запустить поиск решения двух сторон. На этом я остановился, снизить время еще на порядок не получилось.

Следующий подходом я вернулся к старой версии решения на Python, и полез ковыряться с самим алгоритмом поиска пути. Если правильно оценить количество ходов сверху, то благодаря этой оценке можно перейти от DFS/BFS к IDA* и быстрее добираться до решения за счёт сортировки ходов. Ещё один способ ускорения — убрать лишние ходы на стадии раскрытия вершин — из-за особенностей головоломки можно не рассматривать обратные ходы.

Микрооптимизации с ИИ#

Я решил посмотреть, получится ли у GPT-6 разогнать решение ещё дальше. Я скормил ему свои же статьи и попросил перевести последние улучшения алгоритма с Python на C++ версию. Он подумал немного, и прибавил еще пару улучшений:

• несимметричный поиск с двух концов. Вместо двух растущих BFS строится небольшой BFS до глубины 4 от начала, затем выполняется поиск от цели с последовательным увеличением глубины. Это сокращает затраты на хранение и обработку второго фронта.
• Отсекаются эквивалентные последовательности ходов - кроме моих отсечений добавил дополнительно правило — если начало симметрично относительно вертикальной оси, состояние и его зеркальное отражение объединяются в одну запись. Каждая пара разных зеркальных состояний занимает одну запись вместо двух
• Специализированная хеш-таблица с AVX2 - вместо общего flat_hash_map используются группы по восемь 32-битных ключей. Одна SIMD-операция сравнивает искомое состояние сразу с восемью записями
• Меньше данных для восстановления пути. Пути хранятся только для внутренних слоёв BFS. Во внешнем слое сохраняется лишь состояние; недостающий последний шаг восстанавливается после встречи
• DFS специализирован по глубине. Шаблонные функции позволяют компилятору заранее знать оставшуюся глубину и убрать часть проверок из часто исполняемого кода.

Всё это позволило разогнать решение в 2.5 раза, до 288 микросекунд

Круто, но пока не на порядок.

Интересно наблюдать, как при наведении “микроскопа ускорения” меняется код — нечастно можно встретить такой код, пока вы не захотите поймать лишние сотни микросекунд.
https://github.com/spiiin/james_bond_jr_problem/blob/main/james_bond_cpp_ai/fast_solver.hpp

U get(U key) const {
    if (!key)
      return 0;
    U original = key;
    key = canonical(key);
    size_t i = hash(key);
    auto needle = _mm256_set1_epi32(key), zero = _mm256_setzero_si256();
    for (;;) {
      auto bucket =
          _mm256_loadu_si256(reinterpret_cast<const __m256i *>(&tab[i]));
      unsigned eq = _mm256_movemask_ps(
          _mm256_castsi256_ps(_mm256_cmpeq_epi32(bucket, needle)));
      if (eq)
        return original;
      unsigned empty = _mm256_movemask_ps(
          _mm256_castsi256_ps(_mm256_cmpeq_epi32(bucket, zero)));
      if (empty)
        return 0;
      i = (i + 8) & mask;
    }
  }

Additive Pattern Database Heuristics#

Каждая следующая модель ИИ справляется с этой оптимизацией всё лучше, и GPT-6 накопал и реализовал такую вещь, как pattern databases. Идея достаточно простая и интересная.

При оценке позиции можно просто закрыть пару цветов и решить упрощенную задачу. Мы можем записать все оценки для этой упрощенной задачи — они будут гарантированно лучше чем для исходной задачи (мы же просто не учитываем позиции пары цветов). Так что эту оценку можно использовать как хорошую и быструю эвристику для исходной задачи.

Начало                 Цель
1 2 2 1                4 3 4 2
3 4 4 3                3 1 2 4
3 4 4 3                4 2 4 3
2 4 4 2                2 4 3 1

Упрощённое начало      Упрощённая цель
1 · · 1                4 · 4 ·
· 4 4 ·                · 1 · 4
· 4 4 ·                4 · 4 ·
· 4 4 ·                · 4 · 1

Я сначала не понял всю мощь и красоту этой идеи — на первый взгляд она не выглядит как что-то, что может серьёзно помощь в уже ускоренном поиске, как может дополнительное построение еще одной таблице помочь решению задачи? Однако это именно способ посмотреть через призму на основную задачу. Можно построить несколько таких таблиц, закрыв разные пары цветов — и если хотя бы один из фильтров подскажет, что текущее состояние “негодное”, его можно быстро отбросить.

Три разных pattern database на разных парах цветов чудовищно срезают количество необходимых раскрытий вершин.

Python-версия - https://github.com/spiiin/james_bond_jr_problem/tree/main/james_bond_python_pdb_final

За счет таких фильтраций с помощью паттернов практически сразу видна оценка позиции, если хоть один фильтр признает позицию плохой, то её можно отбросить — в итоге требуется на 2 порядка меньше необходимых для изучения вершин. Python-версия ускорилась в 100 раз. Само построение таких таблиц тоже быстрое, так как упрощенные задачи намного проще — около 300 мсек на 3 таблицы паттернов.

В итоге таблицы паттернов:

• позволяют быстро решить упрощенную версию задачи
• позволяют использовать несколько упрощенных решений совместно, чтобы посмотреть на исходную задачу с разных сторон и упростить её решение
  Три таблицы паттернов в сумме упрощают исходную задачу на пару порядков — в итоге нужно просматривать в 100-500 раз меньше вершин

После python версии я перенес это решение и на C++ версию

C++ версия, время включает поиск и восстановление пути, но не подготовку PDB. Все варианты нашли путь из 8 ходов в обоих направлениях.
https://github.com/spiiin/james_bond_jr_problem/tree/main/james_bond_cpp_pdb

“обратный” в таблице - это просто тест, если запускать поиск не от исходной позиции к цели, а наоборот. Это не относится к времени решения основной задачи

7.6 микросекунд с прогретым кешем. Да, это частично compile-time решение (сами таблицы строятся заранее), но красивое.

The Bitter Lesson — интересная статья о том, что глупые методы, которые хорошо масштабируются, в итоге побеждают умные. Люди пытаются применить какие-то знания в предметной области для ускорения, но в итоге побеждает закон Мура.

Когда-то казалось диким просто перебирать все варианты ходов в шахматах или го (это всё тот же поиск пути, как и в этой моей задаче), и долго искали, как именно люди играют в шахматы. В итоге поиск победил. В ии долго пытались строить хитрые базы знаний, но в итоге тоже победило простое перемножение матриц. Победило настолько, что теперь ИИ объясняет людям, как ускорять поиск.

Так было с разпознаванием речи и компьютерным зрением, везде попытки перевести в алгоритмы наши знания о том, как мы это делаем, проиграли грубой силе. Мы должны усвоить урок: внедрение нашего собственного образа мышления в наши системы не работает в долгосрочной перспективе. Универсальные методы, которые продолжают масштабироваться с увеличением вычислительных мощностей, побеждают, хотя и кажутся расточительными и неэффективными. Два метода, которые, похже, масштабируются произвольно таким образом, — это поиск и обучение.

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