4
$\begingroup$

There has been a question on the BoardGameGeek forums that basically boils down to this:

  1. There is a player character on a regular rectangle map at position (px,py).
  2. There is one "AI" character that moves across this map according to some function or pattern (e.g. one field per turn (t), (ax,ay) = (ax0,ay0) + t * (vx,vy)).
  3. The player needs to determine if the two characters are within (L1/Manhattan) distance D.

The question here is if there is some scheme that allows the player to calculate the distance to the AI without the game having to disclose the actual location to the player.

To me this sounds like there may be some solution to be found in the cryptography community.

The restriction here is that, this being a board game, no computer should be involved. So "complex" calculations or just storing the positions digitally is not wanted. But apart from that every utility is fair game (ie, (big) lookup tables or code books).


edit: @bmm6o is right, of course. The scheme proposed by @PaulUszak does not really take into account that somebody has to calculate $H(p_x || p_y || a_x || a_y)$ and in the case of a (solo) board game that is the player.

I derived a scheme from Pauls answer and posted that on BGG. The critique there was that I hard coded the AIs positions which reduces replayability. Once the player figures out the $ai_{hash} \rightarrow (ai_x, ai_y)$ relationship the AIs position is not hidden anymore.

With that in mind, the question becomes if there is a scheme to disclose the current distance [2] between player and AI to the player that carries out the calculation while disclosing as little information as possible about the current position of the AI.


[2] If it makes a difference the original poster on BGG was mostly interested in if the AI and the player occupy the same place ($d=0$) or if the AI is "close" (e.g. $d<3$). Distances further than that are irrelevant.

$\endgroup$
8
  • 1
    $\begingroup$ What is the cardinality of the set of map coordinates? I.e. how many possible positions are there on the map? $\endgroup$
    – Paul Uszak
    Jan 20, 2022 at 16:49
  • $\begingroup$ @PaulUszak That was not specified in the original question, but I guess we can assume a board of around 10x10 fields. $\endgroup$
    – fho
    Jan 20, 2022 at 21:57
  • $\begingroup$ @kelalaka I am not sure I understand your question, but I think you assume I am talking about a computer game? If that were the case, it would be easy to let the computer handle any hidden information and calculations. But the question was about a scheme to hide and only disclose part of information in a board game. $\endgroup$
    – fho
    Jan 20, 2022 at 22:07
  • $\begingroup$ Ok, can the user see where is the AI player? Isn't it Manhattan D is easy to calculate except the obstacles... $\endgroup$
    – kelalaka
    Jan 20, 2022 at 22:10
  • $\begingroup$ It's worth mentioning that if one is ok with some relaxations (probabilistic, and only guarantees when the player is close, meaning $\lVert \vec v-\vec v'\rVert_1 < d$, or far, meaning $> dc$ for $c > 1$), one can likely do much better than the current answer with locality-sensitive hashing. This doesn't give a cryptographic guarantee, but that doesn't seem needed. Additionally, existing LSH schemes are (close to) linear, so one could likely simply store $(h, h(ax_0, ay_0), h(v_x, v_y))$, a (relatively) tiny amount of data. The "gap" mean this may not be suitable for the application though. $\endgroup$
    – Mark Schultz-Wu
    Jan 24, 2022 at 22:58

1 Answer 1

2
$\begingroup$

Good instinct coming here. Fair warning, I don't know what this game is, but. Let the player live at $(p_x, p_y)$ and the AI lives at $(a_x, a_y)$. And we assume a grid of 10 by 10 cells.

Thus there are 100 possible positions per player, and so 10,000 possible combinations of the two players. I'm assuming that the AI can be on top of the player, otherwise you'd have 10,000 - 100 possible combinations if they can't share a cell.

For all games, pre-calculate $H(p_x||p_y||a_x||a_y)$, and also Manhattan distance $D$ between $(p_x, p_y)$ and $(a_x, a_y)$. $H$ is a cryptographic hash function. I suggest SHA-1 as the 40 character hexadecimal values are not overly long for manual searching. Sort $H$ into numeric order to further ease the search. Then publish the $(H, D)$ pairs in a thick book. At 50 hashes per page, that's ~200 pages.

When the AI or the player moves, the 'game' outputs $H$ which can be looked up in the thick book to obtain $D$. You didn't want digital storage, otherwise the game could just compute and output $D$ directly. The player will know the distance, but it is computationally infeasible to invert $H$ to obtain the AI's position without brute forcing/cheating. This technique also allows uni-lateral re-computation of $(H, D)$ pairs if necessary to audit the process and prevent cheating.

This should be doable for a 10 by 10 board, but clearly gets ridiculous for much larger ones.


Note1: Be aware the granularity of a 10 by 10 board. Since you know your own position, any $D$ creates a circle of potential locations of the AI around the player. If the distance calculation was based on the cell centres, only a few cells will exactly match $D$. So there is some positional information leakage. This weakness is not a feature exclusively of my solution, but maths and the small grid.

Note2: Inversion comment. Yes you could create a cheat code book yourself and find all $H$ preimages. That's cheating though. If there was an independent unbiased arbiter for the game, a dungeon master (???) if you will, you could adapt the hash as $H = \text{SHA-1}(p_x||p_y||a_x||a_y||pepper)$ where the pepper is only known to the arbiter. That would still facilitate audit during a dispute. Could the AI hold the pepper if you trust it to play a fair game?

Note3: It should be statistically possible to truncate $|H|$ from 40 hexadecimal characters to much less. 10,000 combinations only occupies 14 bits. If we choose a game position security level of another 10,000, we could use 28 bits for the published hashes. That would publish as seven hexadecimal characters; eight if you want pairs. And therefore less pages.

$\endgroup$
19
  • 1
    $\begingroup$ The question says Manhattan distance, so the references to Pythagoras don't apply. And if this actually needs to be a pen-and-paper calucation, I would not suggest SHA-1. $\endgroup$ Jan 20, 2022 at 23:59
  • 1
    $\begingroup$ @AmanGrewal Manhattan:sorted, thanks. The hashes are precomputed into a lookup book. I understood that code books/look up tables are allowed. $\endgroup$
    – Paul Uszak
    Jan 21, 2022 at 0:28
  • 1
    $\begingroup$ How does this step happen: "the 'game' outputs H"? $\endgroup$
    – bmm6o
    Jan 21, 2022 at 1:52
  • 1
    $\begingroup$ "it is computationally infeasible to invert $H$" --> it would take mere milliseconds to compute all 10,000 hashes yourself to build an inverted index. There are no high-entropy inputs to $H$ in your proposal, so it does not make sense to talk about the one-wayness of $H$. $\endgroup$
    – Mikero
    Jan 21, 2022 at 3:07
  • 1
    $\begingroup$ @fho $||$ is the concatenation operation. As such $0 || 1 = 01$, yet $1 || 0 = 10$. Thus the inputs to the hash function are not equal. $\endgroup$
    – Morrolan
    Jan 21, 2022 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.