Генерация набора псевдослучайных чисел, удовлетворяющих следующему свойству xor?

Question

Учитывая генератор псевдослучайных чисел int64 rand64(), я хотел бы построить набор псевдослучайных чисел. Этот набор должен обладать тем свойством, что комбинации XOR каждого подмножества не должны приводить к значению 0.

Я думаю о следующем алгоритме:

count = 0
set = {}
while (count < desiredSetSize)
    set[count] = rand64()
    if propertyIsNotFullfilled(set[0] to set[count])
        continue
    count = count + 1

Вопрос: как можно реализовать propertyIsNotFullfilled?

Примечания: Причина, по которой мне нравится создавать такой набор, заключается в следующем: у меня есть хеш-таблица, в которой значения хеш-функции генерируются с помощью хеширования Zobrist . Вместо того, чтобы хранить логическое значение для каждой записи в хэш-таблице, указывающее, заполнена ли запись, я подумал, что хэш-значение - которое сохраняется с каждой записью - достаточно для этой информации (0 ... пусто,! = 0 ... установлено ). Есть еще одна причина для переноса этой информации в качестве значения часового в таблице хеш-ключей. Я пытаюсь переключиться с AoS (Array of Structure) на SoA (Structure of Array) макет памяти. Я пытаюсь это избежать заполнения и проверить, если есть меньше промахов кэша. Я надеюсь, что в большинстве случаев достаточно доступа к таблице хеш-ключей (подразумевается, что значение хеша предоставляет информацию, если запись пуста или нет).
Я также подумал о том, чтобы зарезервировать наиболее значимый бит значений хеш-функции для этой информации, но это уменьшит область возможных значений хеш-функции больше, чем это необходимо. Теоретически площадь будет уменьшена с 2 ⁶⁴ (минус 0-значное старческое значение) до 2 ⁶³ .
Можно прочесть вопрос по-другому: учитывая набор из 84 псевдослучайных чисел, есть ли какое-либо число, которое не может быть сгенерировано XORing любого подмножества этого набора, и как его получить? Этот номер может быть использован в качестве дозорного значения.
Теперь, для чего мне это нужно: я разработал игровой движок Connect Four. Для игрока A, а также для игрока B возможно 6 x 7 ходов. Таким образом, существует 84 возможных хода (следовательно, необходимо 84 случайных значения). Хэш-значение состояния платы генерируется предварительно рассчитанными случайными значениями следующим образом: hash(board) = randomset[move1] XOR randomset[move2] XOR randomset[move3] ...

Answer 1

Этот набор должен обладать тем свойством, что комбинации XOR каждого подмножества не должны приводить к значению 0.

ИМХО, это ограничило бы максимальное количество подмножеств до 64 (принцип Пиджона); для> 64 подмножеств всегда будет ( непустое ) подмножество, которое XOR обнуляется. Для небольших подмножеств свойство может быть выполнено.

Чтобы проиллюстрировать мою мысль: рассмотрим систему из 64 уравнений над 64 неизвестными переменными. Затем добавьте еще одно уравнение. Тот факт, что уравнения и переменные являются логическими значениями, не делает проблему другой.

- EDIT / UPDATE--: поскольку приложение выглядит как игра "connect-four", вы можете вместо этого перечислить все возможные конфигурации. Невозможность кодирования невозможных конфигураций платы сэкономит достаточно места для кодирования, чтобы вместить любую допустимую позицию платы в 64 бита:

Кодирование цветных камней как {A, B}, а не как {X}, конфигурации (hight = 6) столбца может быть одним из:

                   X
                X  X
             X  X  X
          X  X  X  X
       X  X  X  X  X
_   A  A  A  A  A  A   <<-- possible configurations for one pile
--+--+--+--+--+--+--+ 
1   1  2  4  8 16 32   <<-- number of combinations of the Xs
               -2 -5   <<-- number of impossible Xs

(и аналогично для B вместо A). Числа под кучами - это число возможных вариантов для X наверху, отрицательные числа - количество запрещенных / невозможных конфигураций. Для столбца с одним A и 4 X, каждое значение для X является действительным, * кроме 3 * A (игра уже закончилась бы). То же самое для самой правой стопки: нижние 3X не могут быть всеми A, а X не может быть B для всех X.

Это приводит к 1 + 2 * (63-7): = 113. (1 для пустой доски, 2 для количества цветов). Итак: 113 - это число конфигураций для одного столбца, хорошо вписывающихся в 7 бит. Для 7 столбцов нам понадобится 7 * 7: = 49 бит. (мы могли бы сохранить один бит для зеркальной симметрии L / R, возможно даже один для цветовой симметрии, но это только усложнит ситуацию, ИМХО).

Там еще много места для кодирования потрачено впустую (столбцы не независимы, число As на плате равно количеству B, или еще один, и т. Д.), Но я не Не думаю, что их будет легко избежать. К счастью, в этом нет необходимости.

Answer 2

Для усиления wildplasser: каждые хеш-функции, которые используются для различения каждой n-битной строки от любой другой n-битной строки, не могут иметь выходной сигнал короче, чем n бит.Более короткие хеш-функции можно использовать, потому что нам нужно только избегать коллизий в поступающих строках, но мы не можем надеяться сделать разумный выбор в автономном режиме.Просто используйте криптографически безопасный RNG, и произойдет одно из двух: (i) ваш код будет работать так, как если бы RNG был действительно случайным, или (ii, маловероятно) ваш код сломается и (если он не прослушивается) будет действовать какразличие между крипто-ГСЧ и истинной случайностью, приносящее вам славу и известность.

Answer 3

Немного больше усиливая ответ с помощью wildplasser, вот идея, как реализовать propertyIsNotFullfilled.

Представить набор псевдослучайных чисел в виде {0,1} -матрицы.Выполните Гауссово исключение (используйте XOR вместо обычных операций умножения / вычитания).Если вы получите матрицу, где последняя строка равна нулю, верните true, в противном случае false.

Определенно, эта функция очень часто будет возвращать true, когда размер набора близок к 64. Поэтому алгоритмв OP эффективен только для относительно небольших размеров.

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