Jocul de bridge ca problemă de complexitatea comunicării

În informatica teoretică, complexitatea comunicării studiază cantitatea de comunicare necesară pentru a rezolva o problemă atunci când intrarea în problemă este distribuită între două sau mai multe părți. Studiul complexității comunicărilor a fost introdus pentru prima dată de Andrew Yao în 1979, în timp ce studia problema calculului distribuit între mai multe mașini. Problema este de obicei enunțată după cum urmează: două părți (numite în mod tradițional Alice și Bob) primesc fiecare câte un și (potențial diferit) de n biți, x și y. Scopul este ca Alice să calculeze valoarea unei anumite funcții, f(x,y), care depinde atât de x cât și de y, cu o cantitate minimă de comunicare între ei.

Licitația în bridge poate fi privită ca o problemă de complexitate a comunicării (PCC). Fie H_N, H_E, H_S și H_W să desemneze mâinile jucătorilor. Există un contract optim pentru W și E care este o funcție a tuturor mâinilor f (H_N, H_E, H_S, H_W). Scopul partenerilor este de a numi contractul optim: cu alte cuvinte, găsiți valoarea lui f, cu cât mai puțină comunicare. Există unele constrângeri locale suplimentare care fac problema mai dificilă: (i) cantitatea de comunicare pe care jucătorii au voie să o schimbe depinde de valoarea lui f și de strategia adversarilor lor, (ii) funcția f poate fi greu de calculat chiar dacă toate mâinile sunt cunoscute, (iii) este dificil să compari strategiile cuantice și clasice, deoarece, în majoritatea cazurilor, este greu să găsești strategiile clasice optime. Cu toate acestea, atunci când ne limităm să luăm în considerare o singură convenție, situația devine mai simplă. Convenția Roman Key Blackwood, de ex., poate fi considerată ca o anumită PCC, formulată în felul următor: Alice are un șir aleatoriu de doi biți a₀ și a₁, în timp ce Bob face alegerea independentă cu privire la pe care dintre cei doi biți vrea să îi învețe; adică fixează b = 0, 1, pentru a învăța a_b (vezi fig. 1). Dar, Alice are voie să trimită un mesaj pe un singur bit m către Bob (m = 0 sub formă de 5♣ sau m = 1 ca 5♦), în timp ce nu îi este permis să trimită nicio informație.

Pentru astfel de PCC, cineva este de obicei interesat de probabilitatea de succes în cel mai rău caz sau probabilitatea medie (succesul este atunci când Bob învață valoarea corectă a lui a₀ sau a₁). Se presupun de obicei intrări distribuite uniform. Cu toate acestea, natura jocului de bridge este de așa natură încât această ipoteză nu este satisfăcută. Astfel, trebuie să introducem următoarea cifră de merit I, care este probabilitatea medie ca Bob, după ce a primit mesajul m, să ghicească corect bitul de la Alice pe care vrea să-l cunoască:

(1)   I = Σ_i,j,kp(a₀ = i, a₁ = j, b = k) × P(R = a_b|a₀ = i, a₁ = j, b = k, m)

unde R este valoarea pe care Bob o ghicește pentru a_b, după ce a primit m, iar p(a₀,a₁,b) este distribuția de probabilitate pentru a₀, a₁ și b.

Fig. 1. Protocolul cuantic al PCC la bridge. Alice (jucând la Est) deține doi biți de informații a_i cu i = 0, 1 (definit de mâna ei). Bob (jucând la West) alege între b = 0 sau 1, ceea ce indică de ce bit de la Alice este interesat. Alice își alege setarea de măsurare să fie a = a₀ⴲa₁. Bob își stabilește măsurarea în funcție de alegerea sa a lui b. După ce a citit rezultatul A (care este codificat ca valoare de bit), Alice îi trimite lui Bob un mesaj de un bit, valoarea m = Aⴲa₀. Bob calculează estimarea lui R pentru valoarea bitului pe care dorește să-l cunoască adăugând mesajul la rezultatul de măsurare locală B (codificat și ca valoare de un bit), adică R = Bⴲm.

Pentru a găsi valoarea maximă a lui I care poate fi atinsă cu resursele clasice, ca în cazul oricărei PCC clasic, este suficient să verificați toate codificările deterministe ale a₀ și a₁ într-un mesaj pe un bit m(a₀,a₁). Am enumerat toate cele 256 combinații posibile de strategii de codare/decodare și am constatat că strategia deterministă optimă, care atinge valoarea maximă a lui I_C, corespunde lui Alice în fiecare rulare trimițând a₀ (sau a₁) ca mesaj m. Dacă Bob este interesat de a₀ (alternativ, a₁), el obține valoarea corectă. Cu toate acestea, dacă el, într-o anumită rundă, este interesat de a₁ (alternativ, a₀), ipoteza lui este valoarea mai probabilă, pe care o deduce din distribuțiile marginale cunoscute p(a₀) și p(a₁). Astfel, avem

(2)   I_C = max{p(b = 0) + p(b = 1)max_i{p(a₁ = i|b = 1)}, p(b = 1) + p(b = 0)max_i{p(a₀ = i|b = 0)}}

În jocul de bridge duplicat, a câștiga nu înseamnă a obține mai multe puncte decât adversarii tăi. Înseamnă să obții mai multe puncte decât alte perechi care joacă cu aceleași cărți. Deoarece găsirea sumei licitate optime crește în mod dramatic cantitatea de puncte acordate, aceasta este condiția necesară pentru câștig. Dacă jucătorii se află în situația descrisă, ei știu că orice alt parteneriat care joacă cu aceleași cărți se va confrunta cu aceeași problemă: dacă să liciteze sau nu pentru slam. Presupunând că toți vor juca mâna în mod optim, cei care licitează corect vor câștiga. Prin urmare, probabilitatea de a ghici ab este probabilitatea de a câștiga.

Sursa: Sadiq Muhammad, Armin Tavakoli, Maciej Kurant, Marcin Pawłowski, Marek Żukowski, Mohamed Bourennane. (2014) Quantum Bidding in Bridge, în PHYSICAL REVIEW X 4, 021047. Licența CC BY 3.0. Traducere și adaptare Nicolae Sfetcu