在棋盘游戏中隐藏/隐藏位置信息

Question

有一个关于BoardGameGeek论坛的问题基本上可以归结为：

1. 在固定位置的矩形地图(px，py)上有一个播放器字符。
2. 有一个"AI“字符根据某种函数或模式在此地图上移动(例如，每次转一个字段(t)，(ax，ay) = (ax0，ay0) +t* (vx，vy))。
3. 玩家需要确定这两个字符是否在(L1/曼哈顿)距离D内。

这里的问题是，是否有某种方案，允许玩家计算距离的AI，而不必透露游戏的实际位置给玩家。

对我来说，这听起来像是在密码界找到了一些解决方案。

这里的限制是，这是一个棋盘游戏，不应该涉及电脑。因此，“复杂”的计算或者只是数字存储位置是不需要的。但除此之外，每个实用程序都是公平的游戏(即(大型)查找表或代码簿)。

编辑：@bmm6o当然是对的。由@PaulUszak提出的方案并没有真正考虑到必须有人计算H(p_x || p_y || a_x || a_y)，如果是(单人)棋盘游戏，即玩家。

我从保尔的答案中得到了一个方案，并发布了那个论BGG。那里的批评是，我硬编码认可机构的位置，这降低了可重放性。一旦玩家确定了ai_{hash} \rightarrow (ai_x, ai_y)的关系，认可的位置就不再隐藏了。

考虑到这一点，问题是是否有一种方案来向执行计算的玩家披露当前玩家与AI之间的距离( 2 )，同时尽可能少地披露有关AI当前位置的信息。

2，如果有区别，BGG上的原始海报主要是关注AI和玩家是否占据了相同的位置(d=0)，或者AI是否“接近”(例如d<3)。比这更远的距离是无关紧要的。

Answer 1

很好的直觉来了。公平的警告我不知道这个游戏是什么但是。让玩家住在(p_x, p_y)，AI住在(a_x, a_y)。我们假设一个由10个细胞组成的网格。

因此，每个球员有100个可能的位置，所以两个球员的组合可能有10,000个。我假设AI可以在玩家的上面，否则如果他们不能共享一个单元，就会有10,000到100种可能的组合。

对于所有游戏，预先计算H(p_x||p_y||a_x||a_y)，以及(p_x, p_y)和(a_x, a_y)之间的曼哈顿距离D。H是一个加密散列函数。我建议SHA-1作为40个字符的十六进制值不是太长的手动搜索。将H排序为数字顺序，以进一步简化搜索。然后将(H, D)对发表在一本厚厚的书中。每页50散列，大约200页。

当AI或玩家移动时，“游戏”输出H，可以在厚厚的书中查找以获得D。你不想要数字存储，否则游戏可以直接计算和输出D。玩家将知道距离，但在计算上不可能通过倒转H来获得AI的位置，而不使用蛮力强迫/欺骗。该技术还允许在必要时对(H, D)对进行单向重计算，以审核过程并防止欺骗。

对于10×10的董事会来说，这应该是可行的，但对于大得多的董事会来说，这显然是荒谬的。

Note1:要注意10×10板的粒度。因为你知道你自己的位置，任何D都会在玩家周围创建一个潜在的人工智能位置的圆圈。如果距离计算是基于单元中心，那么只有少数单元将与D完全匹配。因此有一些位置信息泄漏。这个弱点不仅仅是我的解决方案的一个特点，而是数学和小网格。

Note2:倒置评论。是的，您可以自己创建一个欺骗代码簿，并找到所有的H预映像。不过这是作弊。如果有一个独立的、公正的游戏仲裁者，一个地牢的主人(？)如果愿意，您可以将散列调整为H = \text{SHA-1}(p_x||p_y||a_x||a_y||pepper)，其中只有仲裁者才知道胡椒。这仍将有助于在争端期间进行审计。如果你相信AI能玩一场公平的比赛，它能控制住它吗？

Note3:统计上应该可以将|H|从40个十六进制字符截断到更少的字符。10,000个组合只占14位。如果我们选择另一个10,000的游戏位置安全级别，我们可以使用28位用于已发布的散列。它将发布为七个十六进制字符；如果您想要对，则为八个。因此减少了页数。