การซ่อน/ปิดบังข้อมูลตำแหน่งในเกมกระดาน

มีก คำถามในฟอรัม 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)$ และในกรณีของเกมกระดาน (เดี่ยว) ที่เป็นผู้เล่น

ฉันได้รับแบบแผนจากคำตอบของ Paul และโพสต์สิ่งนั้น บน BGG. คำวิจารณ์มีอยู่ว่าฉันฮาร์ดโค้ดตำแหน่ง AI ซึ่งลดความสามารถในการเล่นซ้ำ เมื่อผู้เล่นคิดออก $ai_{hash} \rightarrow (ai_x, ai_y)$ ความสัมพันธ์ตำแหน่ง AIs จะไม่ถูกซ่อนอีกต่อไป

เมื่อคำนึงถึงสิ่งนี้ คำถามจะกลายเป็นว่ามีแผนที่จะเปิดเผยระยะทางปัจจุบัน [2] ระหว่างผู้เล่นและ AI ให้กับผู้เล่นที่ดำเนินการคำนวณโดยเปิดเผยข้อมูลน้อยที่สุดเท่าที่จะเป็นไปได้เกี่ยวกับตำแหน่งปัจจุบันของ AI หรือไม่

[2] หากสร้างความแตกต่าง ผู้โพสต์ต้นฉบับบน BGG ส่วนใหญ่สนใจว่า AI และผู้เล่นอยู่ในตำแหน่งเดียวกันหรือไม่ ($d=0$) หรือถ้า AI นั้น "ใกล้" (เช่น $d<3$). ระยะทางไกลกว่านั้นไม่เกี่ยว

สัญชาตญาณที่ดีมาที่นี่ คำเตือน ฉันไม่รู้ว่าเกมนี้คืออะไร แต่ ให้ผู้เล่นอาศัยอยู่ที่ $(p_x, p_y)$ และ AI อาศัยอยู่ที่ $(a_x, a_y)$. และเราถือว่ากริด 10 คูณ 10 เซลล์

ดังนั้นจึงมี 100 ตำแหน่งที่เป็นไปได้ต่อผู้เล่นหนึ่งคน และ 10,000 ชุดที่เป็นไปได้ของผู้เล่นสองคนฉันสันนิษฐานว่า AI สามารถอยู่เหนือผู้เล่นได้ ไม่เช่นนั้นคุณจะมีชุดค่าผสมที่เป็นไปได้ 10,000 - 100 ชุดหากพวกเขาไม่สามารถแชร์เซลล์ได้

สำหรับเกมทั้งหมด ให้คำนวณล่วงหน้า $H(p_x||p_y||a_x||a_y)$และระยะทางแมนฮัตตันด้วย $D$ ระหว่าง $(p_x, p_y)$ และ $(a_x, a_y)$. $H$ เป็นฟังก์ชันแฮชการเข้ารหัส ฉันแนะนำ SHA-1 เนื่องจากค่าเลขฐานสิบหก 40 อักขระนั้นไม่นานเกินไปสำหรับการค้นหาด้วยตนเอง เรียงลำดับ $H$ ตามลำดับตัวเลขเพื่อความสะดวกในการค้นหาต่อไป แล้วเผยแพร่ $(สูง, ง)$ คู่กันในหนังสือเล่มหนา ที่ 50 แฮชต่อหน้า นั่นคือ ~ 200 หน้า

เมื่อ AI หรือผู้เล่นเคลื่อนไหว 'เกม' จะแสดงผลออกมา $H$ ซึ่งสามารถค้นหาในหนังสือเล่มหนาเพื่อขอรับ $D$. คุณไม่ต้องการที่เก็บข้อมูลดิจิทัล มิฉะนั้น เกมก็สามารถคำนวณและส่งออกได้ $D$ โดยตรง. ผู้เล่นจะรู้ระยะทาง แต่เป็นไปไม่ได้ที่จะกลับด้านด้วยการคำนวณ $H$ เพื่อให้ได้ตำแหน่งของ AI โดยไม่ต้องบังคับ/โกง เทคนิคนี้ยังช่วยให้การคำนวณซ้ำด้านเดียวของ $(สูง, ง)$ จับคู่หากจำเป็นเพื่อตรวจสอบกระบวนการและป้องกันการโกง

สิ่งนี้ควรทำได้สำหรับบอร์ดขนาด 10 คูณ 10 แต่เห็นได้ชัดว่าไร้สาระสำหรับบอร์ดที่ใหญ่กว่ามาก

หมายเหตุ 1: ระวังความละเอียดของกระดาน 10 คูณ 10 เนื่องจากคุณรู้ตำแหน่งของตัวเองแล้วก็ตาม $D$ สร้างวงกลมของตำแหน่งที่เป็นไปได้ของ AI รอบตัวผู้เล่น หากการคำนวณระยะทางขึ้นอยู่กับศูนย์กลางเซลล์ จะมีเพียงไม่กี่เซลล์เท่านั้นที่จะตรงกันทุกประการ $D$. ดังนั้นจึงมีการรั่วไหลของข้อมูลตำแหน่ง จุดอ่อนนี้ไม่ใช่คุณลักษณะเฉพาะของโซลูชันของฉัน แต่เป็นคณิตศาสตร์และกริดขนาดเล็ก

Note2: ความคิดเห็นผกผัน ใช่ คุณสามารถสร้างหนังสือรหัสโกงด้วยตัวคุณเองและค้นหาทั้งหมด $H$ พรีอิมเมจ นั่นคือการโกงแม้ว่า หากมีผู้ตัดสินอิสระที่เป็นกลางสำหรับเกม ดันเจี้ยนมาสเตอร์ (???) หากคุณต้องการ คุณสามารถปรับแฮชเป็น $H = \text{SHA-1}(p_x||p_y||a_x||a_y||พริกไทย)$ ที่พริกเป็นที่รู้กันเฉพาะผู้ชี้ขาด ที่จะยังคงอำนวยความสะดวกในการตรวจสอบในระหว่างการโต้แย้งAI สามารถจับพริกไทยได้หรือไม่หากคุณไว้วางใจให้เล่นเกมที่ยุติธรรม?

หมายเหตุ 3: ควรมีความเป็นไปได้ทางสถิติที่จะตัดทอน $|H|$ ตั้งแต่ 40 อักขระฐานสิบหกไปจนถึงน้อยกว่ามาก ชุดค่าผสม 10,000 ชุดใช้เพียง 14 บิตเท่านั้น หากเราเลือกระดับความปลอดภัยของตำแหน่งเกมอีก 10,000 เราสามารถใช้ 28 บิตสำหรับแฮชที่เผยแพร่ ที่จะเผยแพร่เป็นอักขระเลขฐานสิบหกเจ็ดตัว แปดถ้าคุณต้องการคู่ หน้าจึงน้อยลง