Скрытие/скрытие информации о позиции в настольной игре

Был вопрос на форумах BoardGameGeek это в основном сводится к следующему:

1. На обычной прямоугольной карте в позиции (px,py) находится персонаж игрока.
2. Существует один персонаж «ИИ», который перемещается по этой карте в соответствии с некоторой функцией или шаблоном (например, одно поле за ход (t), (ax,ay) = (ax0,ay0) + t * (vx,vy)).
3. Игроку необходимо определить, находятся ли два персонажа в пределах (L1/Манхэттен) расстояния D.

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

Для меня это звучит так, будто в криптографическом сообществе можно найти какое-то решение.

Ограничение здесь состоит в том, что это настольная игра, в которой не должен участвовать компьютер. Таким образом, «сложные» вычисления или просто хранение позиций в цифровом виде нежелательны. Но помимо этого каждая утилита является честной игрой (т. е. (большие) справочные таблицы или кодовые книги).

редактировать: @bmm6o, конечно, прав. Схема, предложенная @PaulUszak, на самом деле не учитывает, что кто-то должен вычислять $H(p_x || p_y || a_x || a_y)$ а в случае (одиночной) настольной игры это игрок.

Я получил схему из ответа Пауля и опубликовал это на БГГ. Критика заключалась в том, что я жестко запрограммировал позиции ИИ, что снижает реиграбельность. Как только игрок выяснит $ai_{хэш} \rightarrow (ai_x, ai_y)$ отношения позиция ИИ больше не скрыта.

Имея это в виду, возникает вопрос, существует ли схема раскрытия текущего расстояния [2] между игроком и ИИ для игрока, который выполняет расчет, раскрывая при этом как можно меньше информации о текущем положении ИИ.

[2] Если это имеет значение, оригинальный постер на BGG в основном интересовался тем, занимают ли ИИ и игрок одно и то же место ($д=0$) или если ИИ «близок» (например, $d<3$). Дальнейшее расстояние не имеет значения.

Хороший инстинкт приходит сюда. Честное предупреждение, я не знаю, что это за игра, но. Пусть игрок живет в $(п_х, п_у)$ а ИИ живет в $(а_х, а_у)$. И мы предполагаем сетку 10 на 10 ячеек.

Таким образом, у каждого игрока есть 100 возможных позиций и, следовательно, 10 000 возможных комбинаций двух игроков.Я предполагаю, что ИИ может быть над игроком, иначе у вас было бы 10 000-100 возможных комбинаций, если они не могут делить ячейку.

Для всех игр предварительно рассчитать $H(p_x||p_y||a_x||a_y)$, а также манхэттенское расстояние $Д$ между $(п_х, п_у)$ и $(а_х, а_у)$. $Ч$ является криптографической хеш-функцией. Я предлагаю SHA-1, так как 40-символьные шестнадцатеричные значения не слишком длинны для ручного поиска. Сортировать $Ч$ в числовом порядке для дальнейшего облегчения поиска. Затем опубликуйте $(Ч, Д)$ пар в толстой книге. При 50 хэшах на страницу это примерно 200 страниц.

Когда ИИ или игрок перемещаются, «игра» выводит $Ч$ который можно найти в толстой книге, чтобы получить $Д$. Вам не нужно было цифровое хранилище, иначе игра могла бы просто вычислять и выводить $Д$ напрямую. Игрок будет знать расстояние, но инвертировать его вычислительно невозможно. $Ч$ чтобы получить позицию ИИ без перебора/обмана. Этот метод также позволяет односторонне пересчитать $(Ч, Д)$ пары, если это необходимо для аудита процесса и предотвращения мошенничества.

Это должно быть выполнимо для доски 10 на 10, но явно становится нелепым для гораздо больших.

Примечание 1. Помните о степени детализации доски 10 на 10. Поскольку вы знаете свою позицию, любая $Д$ создает круг потенциальных локаций ИИ вокруг игрока. Если расчет расстояния был основан на центрах ячеек, только несколько ячеек точно совпадут. $Д$. Так что есть некоторая утечка позиционной информации. Эта слабость связана не только с моим решением, но и с математикой и мелкой сеткой.

Примечание 2: Инверсия комментария. Да, вы можете сами создать книгу чит-кодов и найти все $Ч$ прообразы. Хотя это обман. Если бы в игре был независимый беспристрастный арбитр, мастер подземелий (???), если хотите, вы могли бы адаптировать хэш как $H = \text{SHA-1}(p_x||p_y||a_x||a_y||перец)$ где перец известен только арбитру. Это все равно облегчило бы аудит во время спора.Сможет ли ИИ удержать перец, если вы доверите ему честную игру?

Примечание 3: должно быть статистически возможно обрезать $|Ч|$ от 40 шестнадцатеричных символов до гораздо меньшего. 10 000 комбинаций занимают всего 14 бит. Если мы выберем уровень безопасности игровой позиции еще 10 000, мы могли бы использовать 28 бит для публикуемых хэшей. Это будет опубликовано как семь шестнадцатеричных символов; восемь, если вы хотите пары. И поэтому меньше страниц.