Jocul lui Shannon
Jocul lui Shannon este un joc de strategie abstract pentru doi jucători, inventat simultan și independent de Claude Shannon și David Gale ; este, de fapt, cunoscut și sub numele de Gale, Bridg-It și Bird Cage.
Reguli
Jocul se joacă pe un grafic finit format din două noduri speciale, A și B. Fiecare conexiune a graficului poate fi colorată sau eliminată. Cei doi jucători se numesc Short and Cut și se mișcă alternativ. Jucătorul Cut, în timpul rândului său, poate șterge o conexiune la alegere din grafic, atâta timp cât nu este deja colorată. În acest moment jocul îi trece jucătorului Short, care în timpul rândului său poate colora orice conexiune încă prezentă pe grafic. Dacă Cut reușește să creeze un grafic în care A și B nu mai sunt conectate, el câștigă. Dacă Short reușește să creeze o cale colorată de la A la B, el câștigă.
Există, de asemenea, versiuni alternative ale acestui joc, jucate pe un grafic cu conexiuni direcționale și o matrice orientată. S-a găsit o soluție de joc pentru fiecare dintre aceste variante folosind teoria matricii, spre deosebire de alte jocuri precum Hex .
Algoritmi de victorie
Jocul se termină după un număr finit de mișcări și în mod necesar unul dintre cei doi jucători va avea victoria. Indiferent de ce jucător începeți, acest lucru va garanta întotdeauna existența unei strategii de câștig pe fiecare grafic posibil. [1]
Jocul Short and Cut este o dualitate și, în anumite privințe, au același scop: să asigure o anumită conexiune printr-o altă conexiune. De exemplu: Short încearcă să securizeze un grup de conexiuni care formează un circuit, în timp ce Cut încearcă să securizeze un grup de conexiuni care creează o pauză; ambele, alcătuite din cele mai puține conexiuni posibile pentru conectarea celor două subgrafe. [2]
Notă
- ^ (EN) Stephen M. Chase, Un algoritm de grafic implementat pentru câștigarea Jocurilor de comutare Shannon , în Communications of the ACM, vol. 15, nr. 4, 1972, pp. 253-256, DOI : 10.1145 / 361284.361293 .
- ^ Frederic Maire, Soluția jocului Shannon (arhivat) , 2004
Bibliografie
- ( EN ) Martin Gardner , Recreational Topology , în The Second Scientific American Book of Mathematical Puzzles and Diversions , 1987, pp. 78-88, ISBN 0-226-28253-8 .
- ( EN ) Martin Gardner , Bridg-it and Other Games , în New Mathematical Diversions , 1995, pp. 210-218 , ISBN 0-88385-517-8 .
Alte proiecte
-
Wikimedia Commons conține imagini sau alte fișiere despre jocul lui Shannon
linkuri externe
- Graph Game , implementarea Java a jocului lui Shannon