Dice Chess Wiki

Dice Roll Encoding

10 min read

Дам детальный анализ алгоритма Dice Roll Encoding — один из самых инновативных частей проекта.

Отлично, теперь дам очень подробный анализ.

🎲 ОЧЕНЬ ПОДРОБНЫЙ АНАЛИЗ: DICE ROLL ENCODING

ЗАДАЧА

Что нужно решить?

У нас есть 3 кубика, каждый может выпасть одной из 6 фигур:

  • Пешка (P), Конь (N), Слон (B), Ладья (R), Ферзь (Q), Король (K)

Сырой подход: Всего 6³ = 216 различных комбинаций кубиков.

Проблема: Нам важны неупорядоченные комбинации:

  • PPB, PBP, BPP — это одна и та же комбинация
  • Нужно отобразить их в ОДИН индекс

Решение: Сжать 216 вариантов в 56 уникальных комбинаций (неупорядоченных).

Давайте проверим это число:

C(6+3-1, 3) = C(8, 3) = 56

Это звёздочки и полочки — кол-во способов распределить 3 кубика между 6 типами.

ТРЕУГОЛЬНИК ПАСКАЛЯ КАК КЛЮЧ

Что это?

consteval auto make_pascal_triangle() {
    std::array<std::array<unsigned, 9>, 9> p{};
 
    for (size_t i = 0; i < 9; ++i) {
        p[i][0] = 1;           // C(n, 0) = 1
        p[i][i] = 1;           // C(n, n) = 1
        for (size_t j = 1; j < i; ++j) {
            p[i][j] = p[i-1][j-1] + p[i-1][j];  // C(n,k) = C(n-1,k-1) + C(n-1,k)
        }
    }
    return p;
}

Результат для N=DICE_COUNT+PIECES_TYPES_COUNT-1=8:

      p[0]       p[1]       p[2]       ...
p[0]: [1]
p[1]: [1, 1]
p[2]: [1, 2, 1]
p[3]: [1, 3, 3, 1]
p[4]: [1, 4, 6, 4, 1]
p[5]: [1, 5, 10, 10, 5, 1]
p[6]: [1, 6, 15, 20, 15, 6, 1]
p[7]: [1, 7, 21, 35, 35, 21, 7, 1]
p[8]: [1, 8, 28, 56, 70, 56, 28, 8, 1]

Ключевые значения для нас:

  • p[8][3] = 56 — всего комбинаций 3 кубиков по 6 типам ✅
  • p[7][2] = 21 — комбинации 2 кубиков по 6 типам
  • p[6][1] = 6 — комбинации 1 кубика по 6 типам

ЛЕКСИКОГРАФИЧЕСКИЙ ПОРЯДОК

Идея: Перечисляем комбинации в определённом порядке:

Индекс 0:  ------  (0 кубиков)
Индекс 1:  P      (1 кубик, первый тип)
Индекс 2:  N
Индекс 3:  B
Индекс 4:  R
Индекс 5:  Q
Индекс 6:  K      (1 кубик, последний тип)
Индекс 7:  PP     (2 кубика)
Индекс 8:  PN
...
Индекс 27: KK     (последняя комбинация 2 кубиков)
Индекс 28: PPP    (3 кубика)
...
Индекс 55: KKK    (последняя комбинация 3 кубиков)

20 строк кода соответствуют 56 комбинациям!

ГЛУБОКИЙ АНАЛИЗ: ENCODE()

Формально, count[i] = количество раз, когда выпала фигура типа i.

Пример: PPB означает count = [2, 0, 1, 0, 0, 0]

Шаг 1: Подсчёт “смещения” для гуппы с sum кубиков

int sum = this->total_rolls();  // Для PPB: sum = 3
for (int i = 0; i < sum; ++i)
    ret += pascal[PIECES_TYPES_COUNT + i - 1][i];

Разбор:

  • i=0: ret += pascal[5][0] = 1
  • i=1: ret += pascal[6][1] = 6
  • i=2: ret += pascal[7][2] = 21

ret = 1 + 6 + 21 = 28

❓ Что это означает?

Это сумма всех комбинаций с <3 кубиками:

  • C(5,0) = 1 (комбинация с 0 кубиков)
  • C(6,1) = 6 (комбинации с 1 кубиком)
  • C(7,2) = 21 (комбинации с 2 кубиками)
  • Итого: 28 комбинаций до наших 3 кубиков

Шаг 2: Определение позиции внутри группы sum=3

for (size_t i = 0; i < PIECES_TYPES_COUNT; ++i) {  // i = 0..5 типов
    for (int _ = 0; _ < count[i]; ++_) {  // Для каждого кубика типа i
        int len = PIECES_TYPES_COUNT - i - 1;  // Сколько типов ПОСЛЕ этого
        ret += pascal[sum + len - 1][sum];
        sum--;
    }
}

Для PPB: count[0]=2, count[2]=1, остальное 0

Итерация 1 (i=0, первая P):

  • len = 6 - 0 - 1 = 5
  • ret += pascal[3 + 5 - 1][3] = pascal[7][3] = 35
  • ret = 28 + 35 = 63
  • sum = 2

Итерация 2 (i=0, вторая P):

  • len = 6 - 0 - 1 = 5
  • ret += pascal[2 + 5 - 1][2] = pascal[6][2] = 15
  • ret = 63 + 15 = 78
  • sum = 1

Итерация 3 (i=2, B):

  • len = 6 - 2 - 1 = 3
  • ret += pascal[1 + 3 - 1][1] = pascal[3][1] = 3
  • ret = 78 + 3 = 81
  • sum = 0

ФИНАЛЬНЫЙ РЕЗУЛЬТАТ: ret = 81 для PPB

ЧТО ПРОИСХОДИТ В ЦИКЛЕ?

Ключевое понимание:

Когда мы добавляем i-й кубик типа X, мы добавляем количество всех комбинаций, которые лексикографически МЕНЬШЕ.

Для PPB на позиции первой P:

  • Сколько есть комбинаций вида **? где на позиции первого идёт какой-то другой тип?
  • Это все комбинации: **N, **B, **R, **Q, **K где ** — оставшиеся 2 любых
  • Это C(6+2-1, 2) = C(7, 2) = 21…

Нет, погодите. На самом деле это:

  • *? где * это один оставшийся кубик, и ? это один из типов после P

Это C(5+2-1, 2) = C(6, 2) = 15…

Хм, давайте подумаем правильно…

Истинное объяснение:

pascal[7][3] = 35 означает: “сколько комбинаций из 6 оставшихся типов с 3 кубиками?”

Мы добавляем это, потому что если вместо P из типа 0 мы выберем ЧТО-ТО из типов 1-5, то получим 35 вариантов.

Потом для второй P:

  • pascal[6][2] = 15 — комбинации из типов 1-5 с 2 оставшимися кубиками

И для B:

  • pascal[3][1] = 3 — комбинации из типов 3-5 с 1 кубиком (это N, R, Q, K = 4 типа)

Стоп, pascal[3][1] = 3, а не 4…

ПРАВИЛЬНО:

После двух P нам остаётся 1 кубик, и нам нужно выбрать тип.

У нас осталось типов 6 - 2 = 4 (всё кроме P и N).

Число способов выбрать 1 из 4 = C(4, 1) = 4

Но pascal[3][1] = C(3,1) = 3…

Ахаа! Потому что len = 6 - 2 - 1 = 3, то есть это типы после B.

Типы после B это {R, Q, K} = 3 типа!

Итак, по типам: P(0), N(1), B(2), R(3), Q(4), K(5)

После B остаётся 3 типа: R, Q, K

C(3+1-1, 1) = C(3, 1) = 3 ✅

Это ответ на вопрос: “Сколько есть позиций, где вместо B я выбираю одного из типов после B?”

ГЛУБОКИЙ АНАЛИЗ: DECODE()

Теперь обратная операция: из индекса 81 восстановить PPB.

Шаг 1: Определить, сколько кубиков было выброшено

int sum = 0;
while (x >= pascal[PIECES_TYPES_COUNT + sum - 1][sum]) {
    x -= pascal[PIECES_TYPES_COUNT + sum - 1][sum];
    sum++;
}

Входные данные: x = 81

Итерация 1 (sum=0):

  • pascal[5][0] = 1
  • 81 >= 1? Да
  • x = 81 - 1 = 80
  • sum = 1

Итерация 2 (sum=1):

  • pascal[6][1] = 6
  • 80 >= 6? Да
  • x = 80 - 6 = 74
  • sum = 2

Итерация 3 (sum=2):

  • pascal[7][2] = 21
  • 74 >= 21? Да
  • x = 74 - 21 = 53
  • sum = 3

Итерация 4 (sum=3):

  • pascal[8][3] = 56
  • 53 >= 56? Нет → выход из цикла

Результат: sum = 3, x = 53 ✅

Мы правильно определили, что это комбинация 3 кубиков. И остаток x=53 — это позиция внутри группы 3-кубиков.

Шаг 2: Распределить x=53 по типам фигур

for (size_t i = 0; i < PIECES_TYPES_COUNT; ++i) {  // i = 0..5
    int len = PIECES_TYPES_COUNT - i - 1;  // Типов после i-го
    while (sum && x >= pascal[len + sum - 1][sum]) {
        ret.count[i]++;  // Добавляем кубик типа i
        x -= pascal[len + sum - 1][sum];
        sum--;
    }
}

Входные данные: x=53, sum=3, i=0 (Пешка)

Итерация 1.1 (i=0, sum=3, x=53):

  • len = 5
  • pascal[7][3] = 35
  • 53 >= 35? Да
  • ret.count[0]++ → ret.count[0] = 1
  • x = 53 - 35 = 18
  • sum = 2

Итерация 1.2 (i=0, sum=2, x=18):

  • len = 5
  • pascal[6][2] = 15
  • 18 >= 15? Да
  • ret.count[0]++ → ret.count[0] = 2 ✅
  • x = 18 - 15 = 3
  • sum = 1

Итерация 1.3 (i=0, sum=1, x=3):

  • len = 5
  • pascal[5][1] = 5
  • 3 >= 5? Нет → выход из while

Итерация 2 (i=1, sum=1, x=3, Конь):

  • len = 4
  • pascal[4][1] = 4
  • 3 >= 4? Нет → выход из while (не добавляем)

Итерация 3 (i=2, sum=1, x=3, Слон):

  • len = 3
  • pascal[3][1] = 3
  • 3 >= 3? Да
  • ret.count[2]++ → ret.count[2] = 1 ✅
  • x = 3 - 3 = 0
  • sum = 0

Итерация 4..6: sum=0, поэтому while не срабатывает

ФИНАЛЬНЫЙ РЕЗУЛЬТАТ:

ret.count[0] = 2  (P, P)
ret.count[2] = 1  (B)
Остальное = 0

✅ Декодировано: PPB

ВИЗУАЛЬНОЕ ОБЪЯСНЕНИЕ

Все 56 комбинаций с 3 кубиками в порядке:

[0]:   ---     (пусто)
[1]:   P--     (первый тип)
[2]:   N--
...
[6]:   K--     (последний тип)
[7]:   PP-     (PP*: все после PP)
[8]:   PN-
[9]:   PB-
[10]:  PR-
[11]:  PQ-
[12]:  PK-
[13]:  NN-     (NN*)
[14]:  NB-
...
[27]:  KK-     (KK* = KKK)
[28]:  PPP
[29]:  PPN
...
[81]:  PPB     ← нас интересует эта позиция
...
[55]:  KKK

лексикографический порядок гарантирует, что:

  • Сначала идут комбинации, где первый элемент = самый ранний тип
  • Затем второй элемент переступает
  • И т.д.

ОБЪЯСНЕНИЕ ЧЕРЕЗ КОМБИНАТОРИКУ: STARS AND BARS

Классическая задача: Распределить n идентичных объектов в k различных ящиков.

Ответ: C(n+k-1, k) = C(n+k-1, n)

Для нас:

  • n = 3 (кубика)
  • k = 6 (типов)

C(3+6-1, 6) = C(8, 6) = C(8, 2) = 28

Хм, это 28, но мы сказали 56. Погодите…

Правильно: C(3+6-1, 3) = C(8, 3) = 56 ✅

Это означает: “Во сколько способов можем расставить 3 кубика и 5 разделителей?”

Пример расстановки для PPB:
| P P | N | B | R | Q | K
^ это означает: 2 в первый ящик (P), 0 во второй (N), 1 в третий (B), 0,0,0 в остальные

Абстрактно: Комбинаторное число — это количество неупорядоченных выборок.

Кодирование → преобразование неупорядоченной выборки в уникальный индекс лексикографического порядка.

ПРОВЕРКА: ПОЛНЫЙ ЦИКЛ КОДИРОВАНИЯ

Давайте проверим несколько комбинаций:

Комбинацияcount[]Ожидаемый индексПроцесс
---[0,0,0,0,0,0]0sum=0, ret=0
P[1,0,0,0,0,0]1sum=1, ret=1 + 0 = 1
K[0,0,0,0,0,1]6sum=1, skip все типы, ret=1+6-1=6
PP[2,0,0,0,0,0]7sum=2, ret=1+6=7, затем 2 П подряд
PPP[3,0,0,0,0,0]28sum=3, ret=28, затем 3 П подряд
KKK[0,0,0,0,0,3]55sum=3, ret=28, все 3 к типу K

СЛОЖНОСТЬ АЛГОРИТМА

ОперацияСложностьПричина
encode()O(DICE_COUNT × PIECES_TYPES_COUNT) = O(18)Два вложенных цикла, максимум 3 × 6
decode()O(DICE_COUNT × PIECES_TYPES_COUNT) = O(18)Два вложенных цикла
Доступ к PascalO(1)Предвычислено
РезультатO(1) амортизированноКонстантные размеры

ПОЧЕМУ ПАСКАЛЬ А НЕ ЧТО-ТО ДРУГОЕ?

Альтернативы:

  1. Факториалы: O(n!) — взрыв
  2. Битовая маска: Нужна O(2⁶) = 64 позиций (неоптимально)
  3. Хеширование: O(hash time), менее предсказуемо

Паскалева треугольника:

  • ✅ Строгие комбинаторные причины
  • ✅ Гарантирует уникальность
  • ✅ Легко кодировать/декодировать
  • ✅ Предсчитывается один раз (compile-time!)

ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ

// Создание таблицы всех возможных позиций после хода
std::array<std::vector<board>, 56> moves;
 
for (int idx = 0; idx < 56; ++idx) {
    dice_roll roll = dice_roll::decode(idx);  // Быстро: O(1)
    moves[idx] = generate_moves_for_roll(roll);
}
 
// Позже, для конкретного броска:
dice_roll my_roll = {2, 0, 1, 0, 0, 0};  // PPB
int idx = my_roll.encode();  // Быстро: O(1)
std::vector<board>& possible_positions = moves[idx];

Прямая аналогия: Как индекс массива в памяти, но для комбинаторных объектов!

ИТОГОВАЯ ТАБЛИЦА: ПЕРВЫЕ 20 КОМБИНАЦИЙ

idx  | Комбинация | Интерпретация
-----|------------|------------------
0    | ---        | (пусто)
1    | P          | 1 пешка
2    | N          | 1 конь
3    | B          | 1 слон
4    | R          | 1 ладья
5    | Q          | 1 ферзь
6    | K          | 1 король
7    | PP         | 2 пешки
8    | PN         | пешка + конь
9    | PB         | пешка + слон
10   | PR         | пешка + ладья
11   | PQ         | пешка + ферзь
12   | PK         | пешка + король
13   | NN         | 2 коня
14   | NB         | конь + слон
15   | NR         | конь + ладья
16   | NQ         | конь + ферзь
17   | NK         | конь + король
18   | BB         | 2 слона
19   | BR         | слон + ладья
20   | BQ         | слон + ферзь

Закономерность: Лексикографический порядок по типам, для каждой “группы с первым типом X” перечисляются все “группы <X с первым типом Y>”, потом “группы >=Y”.

Это точно как перечисление неупорядоченных выборок в словаре!

Graph View