Генерация расклада для карточных игр

в 8:49, , рубрики: Алгоритмы, игры, карточные игры, метки: ,

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

Алгоритм для простоты описан для трех человек, но лекго расширяется на любое N>=3.

Каждый игрок генерирует три случайных перестановки: A1..3. Произведение A=A3*A2*A1 — это расклад игры. Теперь, если необходимо вскрыть карту с номером i, первый игрок передает второму A1(i), второй передает третьему A2(A1(i)) = A2*A1(i), третий публикует A(i)=A3*A2*A1(i). Если карту необходимо вскрыть только для третьего игрока — A(i) он не публикует.

Третий игрок генерирует случайную перестановку C3 и передает ее первому игроку, а второму игроку передает D3=(С3^(-1))*A3. Теперь, если необходимо вскрыть карту только для второго игрока, первый игрок передает второму A1(i), второй передает первому обратно D3*A2*A1(i) и первый вычисляет С3*D3*A2*A1(i) = A(i).

Далее, третий игрок генерирует случайную перестановку F3 и передает ее второму игроку, первому игроку он передает G3=A3*F3^(-1). Теперь, если необходимо вскрыть карту только для первого игрока, он передает второму A1(i), второй передает ему обратно F3*A2*A1(i) и первый вычисляет G3*F3*A2*A1(i)=A(i).

Перед началом игры каждый игрок публикует для каждой случайной перестановки X хэш числа X+k*n, где 0<x<=N!-1 — порядковый номер перестановки, n=N! — количество перестановок, k — случайное большое число, “соль” хэша. По окончанию игры игроки публикуют свои перестановки и k в открытую и проверяют хэши других игроков.

Ограничения алгоритма:
— данные, которыми обмениваются два пира, передаются по шифрованному каналу, сертификаты участников заранее всем известны.
— возможность сговора двух участников должна быть исключена.

Автор: zikher

* - обязательные к заполнению поля