Ẩn/Che khuất thông tin vị trí trong board game

đã có một câu hỏi trên diễn đàn BoardGameGeek về cơ bản hiểu rõ điều này:

1. Có một nhân vật người chơi trên bản đồ hình chữ nhật thông thường ở vị trí (px, py).
2. Có một ký tự "AI" di chuyển trên bản đồ này theo một số chức năng hoặc mẫu (ví dụ: một trường mỗi lượt (t), (ax,ay) = (ax0,ay0) + t * (vx,vy)).
3. Người chơi cần xác định xem hai nhân vật có ở trong khoảng cách (L1/Manhattan) D hay không.

Câu hỏi đặt ra ở đây là liệu có một kế hoạch nào đó cho phép người chơi tính toán khoảng cách đến AI mà trò chơi không cần phải tiết lộ vị trí thực tế cho người chơi hay không.

Đối với tôi, điều này nghe có vẻ như có thể tìm thấy một số giải pháp trong cộng đồng mật mã.

Hạn chế ở đây là, đây là một trò chơi cờ, không nên tham gia vào máy tính. Vì vậy, không muốn tính toán "phức tạp" hoặc chỉ lưu trữ các vị trí kỹ thuật số. Nhưng ngoài ra, mọi tiện ích đều là trò chơi công bằng (nghĩa là bảng tra cứu (lớn) hoặc sách mã).

chỉnh sửa: Tất nhiên, @ bmm6o đúng. Kế hoạch do @PaulUszak đề xuất không thực sự tính đến việc ai đó phải tính toán $H(p_x || p_y || a_x || a_y)$ và trong trường hợp trò chơi cờ (một mình) là người chơi.

Tôi rút ra một kế hoạch từ câu trả lời của Pauls và đăng rằng trên BGG. Lời phê bình là tôi đã mã hóa cứng các vị trí của AI làm giảm khả năng chơi lại. Một khi người chơi tìm ra $ai_{hash} \rightarrow (ai_x, ai_y)$ mối quan hệ, vị trí của AI không bị ẩn nữa.

Với suy nghĩ đó, câu hỏi đặt ra là liệu có một kế hoạch tiết lộ khoảng cách hiện tại [2] giữa người chơi và AI cho người chơi thực hiện phép tính trong khi tiết lộ càng ít thông tin càng tốt về vị trí hiện tại của AI hay không.

[2] Nếu điều đó tạo ra sự khác biệt thì người đăng ban đầu trên BGG chủ yếu quan tâm đến việc liệu AI và người chơi có ở cùng một vị trí hay không ($d=0$) hoặc nếu AI "đóng" (ví dụ: $d<3$). Khoảng cách xa hơn là không liên quan.

Bản năng tốt đến đây. Cảnh báo công bằng, tôi không biết trò chơi này là gì, nhưng. Hãy để người chơi sống tại $(p_x, p_y)$ và AI sống ở $(a_x, a_y)$. Và chúng tôi giả sử một lưới 10 x 10 ô.

Do đó, có 100 vị trí có thể có cho mỗi người chơi và do đó có 10.000 kết hợp có thể có của hai người chơi.Tôi cho rằng AI có thể đứng đầu trình phát, nếu không, bạn sẽ có 10.000 - 100 kết hợp khả thi nếu chúng không thể chia sẻ một ô.

Đối với tất cả các trò chơi, tính toán trước $H(p_x||p_y||a_x||a_y)$, và cả khoảng cách Manhattan $D$ ở giữa $(p_x, p_y)$ và $(a_x, a_y)$. $H$ là một hàm băm mật mã. Tôi đề xuất SHA-1 vì các giá trị thập lục phân 40 ký tự không quá dài để tìm kiếm thủ công. Loại $H$ theo thứ tự số để dễ dàng tìm kiếm hơn. Sau đó xuất bản $(H, Đ)$ cặp trong một cuốn sách dày. Với 50 giá trị băm trên mỗi trang, đó là ~ 200 trang.

Khi AI hoặc người chơi di chuyển, 'trò chơi' xuất ra $H$ mà có thể được tra cứu trong cuốn sách dày để có được $D$. Bạn không muốn lưu trữ kỹ thuật số, nếu không thì trò chơi chỉ có thể tính toán và xuất ra $D$ trực tiếp. Người chơi sẽ biết khoảng cách, nhưng không thể đảo ngược về mặt tính toán $H$ để có được vị trí của AI mà không bị ép buộc/gian lận. Kỹ thuật này cũng cho phép tính toán lại một phía của $(H, Đ)$ cặp nếu cần thiết để kiểm tra quá trình và ngăn chặn gian lận.

Điều này có thể thực hiện được đối với bảng 10 nhân 10, nhưng rõ ràng trở nên vô lý đối với bảng lớn hơn nhiều.

Lưu ý1: Hãy lưu ý mức độ chi tiết của bảng 10 x 10. Vì bạn biết vị trí của chính mình, bất kỳ $D$ tạo ra một vòng tròn các vị trí tiềm năng của AI xung quanh người chơi. Nếu phép tính khoảng cách dựa trên tâm ô, thì chỉ một số ô sẽ khớp chính xác $D$. Vì vậy, có một số rò rỉ thông tin vị trí. Điểm yếu này không phải là một tính năng dành riêng cho giải pháp của tôi, mà là toán học và lưới nhỏ.

Lưu ý2: Nhận xét đảo ngược. Có, bạn có thể tự tạo một cuốn sách mã gian lận và tìm tất cả $H$ tiền hình ảnh. Đó là gian lận mặc dù. Nếu có một trọng tài độc lập không thiên vị cho trò chơi, một chủ ngục tối (???), nếu bạn muốn, bạn có thể điều chỉnh hàm băm như $H = \text{SHA-1}(p_x||p_y||a_x||a_y||pepper)$ nơi hạt tiêu chỉ được biết đến với trọng tài. Điều đó vẫn sẽ tạo điều kiện thuận lợi cho việc kiểm toán trong quá trình tranh chấp.AI có thể giữ hạt tiêu nếu bạn tin tưởng nó sẽ chơi một trò chơi công bằng không?

Lưu ý3: Có thể cắt ngắn theo thống kê $|H|$ từ 40 ký tự thập lục phân đến ít hơn nhiều. 10.000 tổ hợp chỉ chiếm 14 bit. Nếu chúng tôi chọn mức bảo mật vị trí trò chơi là 10.000 khác, chúng tôi có thể sử dụng 28 bit cho các giá trị băm đã xuất bản. Điều đó sẽ xuất bản dưới dạng bảy ký tự thập lục phân; tám nếu bạn muốn cặp. Và do đó ít trang hơn.