สัญชาตญาณที่ดีมาที่นี่ คำเตือน ฉันไม่รู้ว่าเกมนี้คืออะไร แต่ ให้ผู้เล่นอาศัยอยู่ที่ $(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 บิตสำหรับแฮชที่เผยแพร่ ที่จะเผยแพร่เป็นอักขระเลขฐานสิบหกเจ็ดตัว แปดถ้าคุณต้องการคู่ หน้าจึงน้อยลง