Puncte:4

Ascunderea/Ocultarea informațiilor despre poziție într-un joc de societate

drapel jp
fho

A existat o întrebare pe forumurile BoardGameGeek practic se rezumă la asta:

  1. Există un personaj jucător pe o hartă dreptunghi obișnuită la poziție (px,py).
  2. Există un caracter „AI” care se deplasează pe această hartă în funcție de o funcție sau model (de exemplu, un câmp pe tură (t), (ax,ay) = (ax0,ay0) + t * (vx,vy)).
  3. Jucătorul trebuie să determine dacă cele două personaje se află la distanța (L1/Manhattan) D.

Întrebarea aici este dacă există o schemă care permite jucătorului să calculeze distanța până la AI fără ca jocul să fie nevoit să dezvăluie locația reală jucătorului.

Pentru mine, acest lucru sună de parcă ar putea fi găsită o soluție în comunitatea criptografiei.

Restricția aici este că, acesta fiind un joc de societate, nu ar trebui să fie implicat niciun computer. Deci nu se dorește calcule „complexe” sau doar stocarea digitală a pozițiilor. Dar în afară de asta, fiecare utilitar este un joc corect (adică, tabele de căutare (mari) sau cărți de coduri).


Editați | ×: @bmm6o are dreptate, desigur. Schema propusă de @PaulUszak nu prea ține cont de faptul că cineva trebuie să calculeze $H(p_x || p_y || a_x || a_y)$ iar în cazul unui joc de societate (solo) acesta este jucătorul.

Am derivat o schemă din răspunsul lui Paul și am postat asta pe BGG. Critica de acolo a fost că am codificat greu pozițiile AI, ceea ce reduce rejucabilitatea. Odată ce jucătorul își dă seama $ai_{hash} \rightarrow (ai_x, ai_y)$ relație poziția AI nu mai este ascunsă.

Având în vedere acest lucru, întrebarea devine dacă există o schemă care să dezvăluie distanța curentă [2] dintre jucător și AI jucătorului care efectuează calculul, dezvăluind cât mai puține informații despre poziția actuală a AI.


[2] Dacă face o diferență, afișul original de pe BGG a fost cel mai interesat dacă AI și jucătorul ocupă același loc ($d=0$) sau dacă AI este „aproape” (de ex. $d<3$). Distanțele mai mari decât atât sunt irelevante.

Paul Uszak avatar
drapel cn
Care este cardinalitatea setului de coordonate ale hărții? i.e. câte poziții posibile există pe hartă?
drapel jp
fho
@PaulUszak Asta nu a fost specificat în întrebarea inițială, dar cred că putem presupune o tablă de aproximativ 10x10 câmpuri.
drapel jp
fho
@kelalaka Nu sunt sigur că am înțeles întrebarea ta, dar cred că presupui că vorbesc despre un joc pe computer? Dacă ar fi așa, ar fi ușor să lăsați computerul să gestioneze orice informații și calcule ascunse.Dar întrebarea era despre o schemă de a ascunde și dezvălui doar o parte a informațiilor dintr-un joc de societate.
kelalaka avatar
drapel in
Ok, utilizatorul poate vedea unde este playerul AI? Nu Manhattan D este ușor de calculat, cu excepția obstacolelor...
Mark avatar
drapel ng
Merită menționat că, dacă cineva este de acord cu unele relaxări (probabilistice și garantează doar când jucătorul este aproape, adică $\lVert \vec v-\vec v'\rVert_1 dc$ pentru $c > 1$), probabil că se poate face *mult* mai bine decât răspunsul curent cu hashing sensibil la localitate. Acest lucru nu oferă o garanție criptografică, dar nu pare necesar. În plus, schemele LSH existente sunt (aproape de) liniare, așa că probabil s-ar putea stoca pur și simplu $(h, h(ax_0, ay_0), h(v_x, v_y))$, o cantitate (relativ) mică de date. „Gapul” înseamnă că acest lucru ar putea să nu fie potrivit pentru aplicație.
drapel jp
fho
@Mark Ce „decalaj”?
Mark avatar
drapel ng
$c > 1$. Concret, se poate garanta că LSH va funcționa pentru „închidere” ($cd$), dar nu are garanții pentru distanțe „medii” ($\in (d, cd)$).
drapel jp
fho
Întrebare ulterioară aici: https://crypto.stackexchange.com/questions/98313/hiding-obscuring-position-information-in-a-board-game-part-2
Puncte:2
drapel cn

Bun instinct venind aici. Avertisment corect, nu știu ce este acest joc, dar. Lăsați jucătorul să trăiască la $(p_x, p_y)$ iar AI trăiește la $(a_x, a_y)$. Și presupunem o grilă de 10 pe 10 celule.

Astfel, există 100 de poziții posibile per jucător, și deci 10.000 de combinații posibile ale celor doi jucători.Presupun că AI poate fi deasupra jucătorului, altfel ai avea 10.000 - 100 de combinații posibile dacă nu pot partaja o celulă.

Pentru toate jocurile, precalculați $H(p_x||p_y||a_x||a_y)$, și, de asemenea, distanța Manhattan $D$ între $(p_x, p_y)$ și $(a_x, a_y)$. $H$ este o funcție hash criptografică. Sugerez SHA-1 deoarece valorile hexazecimale de 40 de caractere nu sunt prea lungi pentru căutarea manuală. Fel $H$ în ordine numerică pentru a ușura și mai mult căutarea. Apoi publicați $(H, D)$ perechi într-o carte groasă. Cu 50 de hasheuri pe pagină, înseamnă ~200 de pagini.

Când AI sau jucătorul se mișcă, „jocul” iese $H$ care poate fi căutat în cartea groasă pentru a obţine $D$. Nu ai vrut stocare digitală, altfel jocul ar putea doar să calculeze și să iasă $D$ direct. Jucătorul va ști distanța, dar inversarea este imposibil din punct de vedere computațional $H$ pentru a obține poziția AI fără forțare/trișare brută. Această tehnică permite, de asemenea, recalcularea unilaterală a $(H, D)$ perechi dacă este necesar pentru a audita procesul și a preveni înșelăciunea.

Acest lucru ar trebui să fie realizabil pentru o placă de 10 pe 10, dar în mod clar devine ridicol pentru cele mult mai mari.


Notă 1: Fiți conștienți de granularitatea unei plăci de 10 pe 10. Din moment ce vă cunoașteți propria poziție, oricare $D$ creează un cerc de locații potențiale ale AI în jurul jucătorului. Dacă calculul distanței s-a bazat pe centrele celulelor, doar câteva celule se vor potrivi exact $D$. Deci, există o scurgere de informații poziționale. Această slăbiciune nu este o caracteristică exclusivă a soluției mele, ci matematica și grila mică.

Nota 2: Comentariu de inversare. Da, ați putea să vă creați o carte de coduri și să le găsiți pe toate $H$ preimagini. Asta e insa inselat. Dacă a existat un arbitru independent imparțial pentru joc, un dungeon master (???) dacă vrei, ai putea adapta hash-ul ca $H = \text{SHA-1}(p_x||p_y||a_x||a_y||piper)$ unde ardeiul este cunoscut doar de arbitru. Acest lucru ar facilita totuși auditul în timpul unei dispute.Ar putea AI să țină ardeiul dacă ai încredere în el pentru a juca un joc corect?

Nota 3: Ar trebui să fie posibilă statistic trunchierea $|H|$ de la 40 de caractere hexazecimale la mult mai puțin. 10.000 de combinații ocupă doar 14 biți. Dacă alegem un nivel de securitate al poziției de joc de încă 10.000, am putea folosi 28 de biți pentru hashurile publicate. Aceasta ar fi publicată ca șapte caractere hexazecimale; opt dacă vrei perechi. Și, prin urmare, mai puține pagini.

Aman Grewal avatar
drapel gb
Întrebarea spune distanța din Manhattan, deci referințele la Pitagora nu se aplică. Și dacă aceasta trebuie să fie de fapt un calcul pe hârtie, nu aș sugera SHA-1.
Paul Uszak avatar
drapel cn
@AmanGrewal Manhattan: sortat, mulțumesc. Hashurile sunt precalculate într-o carte de căutare.Am înțeles că sunt permise cărțile de coduri/tabelele de căutare.
drapel ph
Cum se întâmplă acest pas: „„jocul” iese H”?
drapel us
„este imposibil din punct de vedere computațional să inversezi $H$” --> ar dura doar câteva milisecunde pentru a calcula singuri toate cele 10.000 de hashe-uri pentru a construi un index inversat. Nu există intrări cu entropie mare pentru $H$ în propunerea dvs., așa că nu are sens să vorbim despre unilateralitatea $H$.
drapel jp
fho
Super răspuns! Nu sunt prea îngrijorat de infezabilitatea de a inversa $H$, dacă jucătorii vor să întrerupă jocul, o vor face. Iti merge asta? De exemplu doar calculând $a_x || a_y$ pentru primele câmpuri va produce [[0,1],[1,1]] și privind rezultatul unui câmp 10x10 are o mulțime de numere care se repetă.
drapel jp
fho
Continuând acest gând: cred că ar putea fi evitat prin identificarea unică a fiecărui domeniu individual. Nu se calculează $H(a_x || a_y || p_x || p_y)$ ci $H( (a_x + 10 * a_y) || (p_x + 10 * p_y))$ (pentru un teren de joc de 10x10).
drapel jp
fho
(Cred că trebuie să facem același „truc” de două ori, altfel avem același câștig de problemă... deci ar fi $H((a_x + 10 * a_y) + (p_x + 10 * p_y) * 100) $. Întrebarea devine acum dacă mai este nevoie de vreo funcție hash (cu excepția posibilă a obscurării rezultatelor).
drapel jp
fho
@PaulUszak Ați putea vă rog să comentați la $p_x || p_y$ fiind același pentru mai multe combinații de $p_x$ și $p_y$ (de exemplu, $p_x = 1, p_y = 0$ și $p_y = 0, p_y = 1$)?
Morrolan avatar
drapel ng
@fho $||$ este operația de concatenare.Ca atare $0 || 1 = 01$, totuși $1 || 0 = 10$. Astfel, intrările în funcția hash nu sunt egale.
drapel jp
fho
@Morrolan Asta are mai mult sens. Nu eram familiarizat cu acea notație și am presupus că trebuie să fie un OR sau XOR.
Paul Uszak avatar
drapel cn
@fho Doamne, îmi pare rău. Este concatenare. Ceea ce este ușor ambiguu - vezi https://crypto.stackexchange.com/a/71784/23115
drapel jp
fho
@PaulUszak Mulțumesc pentru răspuns! Mă voi juca puțin cu asta. Bănuiesc că ar fi destul de ușor să „pre-scramblezi” pozițiile de pe placă (doar pentru a ofusca lucrurile) și să nu folosești nicio funcție hash (intensive de calcul). Apoi este doar $p_{fid} + a_{fid} * 100$ ($x_{fid}$ reprezintă identificatorul de câmp) pentru a obține un număr (oarecum) aleatoriu de căutat în broșură. Adică, dacă nu aveți o funcție hash în minte, ar fi banal să o calculați de mai multe ori manual.
drapel ph
Chiar nu înțeleg cum rezolvă asta problema. Cine calculează acest hash și de ce nu efectuează doar calculul distanței pe intrări?
drapel jp
fho
@bmm6o Scopul este de a întuneca poziția reală a AI pe tabla de joc. Deci nu există nicio figură/marker pe hartă care să o reprezinte. Hash-ul ar trebui să fie calculat atunci când jocul este produs pentru a completa o carte de coduri cu (hash (player, ai), distanță) tuplets. Apoi de către jucător pentru a verifica dacă este aproape de AI. Folosind Manuel Blums HCMU, acest lucru ar putea fi de fapt fezabil.
drapel ph
Am înțeles că cartea va fi produsă din timp. Cine produce hash-ul de căutat în timpul jocului?
drapel jp
fho
@bmm6o În mod ideal, jucătorul (jucătorii). Puteți reduce calculele la o singură adăugare și aplicarea funcției hash. HCMU este de fapt destul de simplu de calculat, mai ales dacă intrarea este scurtă.
drapel ph
Dacă crezi că asta îți rezolvă problema, nu mă voi certa cu tine. Dar acest răspuns nu clarifică modul în care jucătorii vor calcula o funcție a cărei intrare include poziția adversarului, fără ca aceștia să cunoască poziția adversarului. Nu este procedura pe care o are cineva pentru a calcula $H(p_x||p_y||a_x||a_y)$ la fiecare tură?
drapel jp
fho
Să [continuăm această discuție în chat](https://chat.stackexchange.com/rooms/133414/discussion-between-fho-and-bmm6o).
drapel jp
fho
@PaulUszak Îmi pare rău că nu am acceptat răspunsul dvs. Eram convins că ar trebui să-mi clarific întrebarea în loc să deschid una nouă.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.