Comments 16
Parallel bit deposit and extract — то что надо?
Могу попробовать помочь с оптимизацией под x86.
Проверять все 192 автоморфизма не нужно. Достаточно после каждого хода преобразовывать поле к каноничному виду — выбирать автоморфизм, который бы имел, например, минимальный индекс.
Вычисление и перебор всех 192 значений — задача действительно вычислительно сложная. Но эту задачу можно значительно упростить, если изменить порядок нумерации бит в кубе: сначала идут 8 вершин куба (XA), затем 8 вершин центральной части 2х2х2 (XB), затем остальные 48 ячеек (XC). То есть конфигурация поля кодируется как [XA8 XB8 XC48] [OA8 OB8 OC48] [F]. Пока рассматривается только отражение и перестановка координат.
При автоморфизмах (перестановка координат, отражение) биты остаются в вершинах куба, отсюда следует, что перестановка бит будет осуществляться в пределах XA8, XB8 и XC48, не влияя друг на друга. Причём таблицы преобразования для XA8 и XB8 будут одинаковы. Аналогично можно и XC48 перегруппировать, если есть желание.
Ну а дальше дело техники. Если нам нужно найти минимальный автоморфизм, то делаем так: создаём таблицу, которая для каждого префикса XA8 выдаёт список автоморфизмов, имеющих префикс, совпадающий с префиксом каноничного автоморфизма. Список будет совсем небольшой. Далее делаем перебор для XB8, выбирая минимальный префикс. Если остаётся более 1 варианта, то делаем перебор по XC48. Случаи XA8 = 0 и XA8 = 255 рассматриваются отдельно.
Таким образом, вместо вычисления 192 автоморфизмов, на каждом шаге их будет около десятка, что должно сильно ускорить вычисления.
Условных переходов будет мало. Во-первых, условные переходы для XA8 = 0 и XA8 = 255 будут прекрасно обрабратываться предсказателем переходов. Во-вторых, список возможных автоморфизмом можно сделать фиксированного размера, просто дополнив его повторящимися автоморфизмами.
Хмм...
А что такое канонический вид?
Вот в процессе работы получилось какое-то игровое поле.
Прежде, чем считать его, я хочу проверить, может быть оно уже было просчитано.
Для этого я проверяю, есть ли оно в кэше. Если нет, я проверяю все возможные преобразования — существуют ли они.
При этом неизвестно, какое из них "каноническое".
Предлагается выделить какое-то одно состояние из изоморфных, скажем минимальное если интерпретировать как число, и сразу приводить к нему, и уже его сохранять в кеш и соответственно проверять только его.
И я предлагаю способ относительно быстрого его нахождения.
А что такое автоморфизм с наименьшим индексом ?
Если следовать предложенной методике, то необходимо иметь таблицу на 256 входов для XA8, затем таблицу на 256 входов для каждой из предыдущих таблиц для XB8, а затем таблицу на 2 в степени 48 входов для каждой предыдущей таблицы. То есть в итоге иметь таблицу размером 2 в степени 64 .
Каким таким хитрым образом обходы в ширину и в глубину могут применяться для решения игр на графе?
Однако, у кубика есть еще два внутренних автоморфизма. Один переставляет координаты полей в первой и второй паре в каждой линии,
а второй оставляет первое и последнее поле на месте, а переставляет только координаты для второго и третьего поля.
Не понял что это за хитрые автоморфизмы. Не могли бы вы пояснить их картинкой?
Вот описание из википедии:
The group of automorphisms of the game contains 192 automorphisms. It is made up of combinations of the usual rotations and reflections that reorient or reflect the cube, plus two that scramble the order of cells on each line. If a line comprises cells A, B, C and D in that order, one of these exchanges inner cells for outer ones (such as B, A, D, C) for all lines of the cube, and the other exchanges cells of either the inner or the outer cells ( A, C, B, D or equivalently D, B, C, A) for all lines of the cube.
Под поиском в ширину я понимаю следующее:
производятся итерации со все возрастающей глубиной — сначала 4, потом 6, потом 8 и т.д.
На каждой такой итерации производится исследование всего дерева соответствующей глубины.
Почти оптимальное решение трёхмерных 4x4x4 крестиков-ноликов