Hex (joc de societate) - Hex (board game)

Acest articol este despre jocul de strategie abstractă. Pentru alte utilizări, consultați Joc hexagonal (dezambiguizare) .

Hex
Hex-board-11x11- (2) .jpg
11 × 11 Hexboard care prezintă o configurație câștigătoare pentru Blue
ani activi 1942 – prezent
genuri Joc de
masă Joc de strategie abstract Joc de
conexiune
Jucători 2
Timp de configurare Nici unul
Timp de joc 30 minute - 2 ore (bord 11 × 11)
Șansă aleatorie Nici unul
Abilitati cerute Strategie , tactică

Hex este un jucător de două strategie abstractă joc de masă în care jucătorii încearcă să se conecteze laturile opuse ale unui bord hexagonală . Hex a fost inventat de matematicianul și poetul Piet Hein în 1942 și independent de John Nash în 1948.

Se joacă în mod tradițional pe o placă de romb de 11 × 11 , deși plăcile de 13 × 13 și 19 × 19 sunt, de asemenea, populare. Fiecărui jucător i se atribuie o pereche de laturi opuse ale planșei pe care trebuie să încerce să le conecteze, luând pe rând o piatră de culoarea lor pe orice spațiu gol. Odată plasate, pietrele nu pot fi mutate sau îndepărtate. Un jucător câștigă atunci când își conectează părțile împreună cu succes printr-un lanț de pietre adiacente. Extragerile sunt imposibile în Hex datorită topologiei tabloului de joc.

Jocul are o strategie profundă, tactici clare și un fundament matematic profund legat de teorema punctului fix Brouwer . Jocul a fost comercializat pentru prima dată ca joc de societate în Danemarca sub numele de Con-tac-tix , iar Parker Brothers a comercializat o versiune a acestuia în 1952 numită Hex ; nu mai sunt în producție. Hex-ul poate fi jucat și cu hârtie și creion pe hârtie milimetrică reglată hexagonal.

Cercetările legate de Hex sunt actuale în domeniile topologiei, teoriei graficelor și matroidelor , combinatoriei, teoriei jocurilor combinatorii și a inteligenței artificiale.

Tip de joc

Hex este un joc de conexiune și poate fi clasificat ca joc Maker-Breaker , un anumit tip de joc pozițional . Jocul nu se poate termina niciodată într-o remiză (egalitate) , cu alte cuvinte, Hex este, de asemenea, un „ joc determinat ”.

Hex este un joc de informații finit, perfect și un joc de strategie abstract care aparține categoriei generale a jocurilor de conexiune . Hex este un caz special al versiunii „nod” a jocului de comutare Shannon .

Ca produs, Hex este un joc de societate ; se poate juca și cu hârtie și creion .

Istorie

Invenţie

Jocul a fost inventat de matematicianul danez Piet Hein , care l-a introdus în 1942 la Institutul Niels Bohr . Deși mai târziu Hein l-a redenumit Con-tac-tix, a devenit cunoscut în Danemarca sub numele de Polygon datorită unui articol al lui Hein din ediția din 26 decembrie 1942 a ziarului danez Politiken , prima descriere publicată a jocului, în care a folosit acest nume. Jocul a fost reinventat independent în 1948 de matematicianul John Nash de la Universitatea Princeton . Potrivit lui Martin Gardner , care a prezentat Hex în coloana sa din Jocuri matematice din iulie 1957 , colegii lui Nash au numit jocul fie Nash, fie John, denumirea din urmă făcând referire la faptul că jocul putea fi jucat pe gresie hexagonală de baie. Hein i-a scris lui Gardner în 1957 exprimând îndoiala că Nash a descoperit Hex independent, dar Nash insistă asupra faptului că a reinventat jocul înainte de a fi expus la munca lui Hein. Gardner nu a putut să verifice sau să respingă în mod independent cererea lui Nash.

Jocuri publicate

O ediție a jocului Parker Brothers

În 1952, Parker Brothers a comercializat o versiune. Ei și-au numit versiunea „Hex” și numele a rămas. De asemenea, Parker Brothers a vândut o versiune sub numele „Con-tac-tix” în 1968. Hex a fost, de asemenea, lansat ca unul dintre jocurile din seria 3M Paper Games din 1974; jocul conținea un 5+1 ⁄ 2 -la- 8+1 ⁄ 2- inch (140 mm × 220 mm) tampon de 50 de coli de grile hexagonale rigulate. Hex este publicat în prezent de Nestorgames într-o dimensiune de 11x11 și o dimensiune de 14x14.

Mașina Hex a lui Shannon

În jurul anului 1950, matematicianul și inginerul electric Claude Shannon și EF Moore au construit o mașină de joc analogică Hex, care era în esență o rețea de rezistență cu rezistențe pentru margini și becuri pentru vârfuri. Miscarea care a fost făcută a corespuns unui anumit punct de șa specificat din rețea. Mașina a jucat un joc destul de bun de Hex. Mai târziu, cercetătorii care au încercat să rezolve jocul și să dezvolte algoritmi de calcul Hex-playing au emulat rețeaua lui Shannon pentru a produce automate puternice.

Cronologia cercetării

În 1952, John Nash a expus o dovadă a existenței că pe tablele simetrice, primul jucător are o strategie câștigătoare.

În 1964, matematicianul Alfred Lehman a arătat că Hex nu poate fi reprezentat ca un matroid binar , așa că o strategie câștigătoare determinată ca cea a jocului de comutare Shannon pe o rețea dreptunghiulară regulată nu era disponibilă. Jocul s-a dovedit ulterior a fi complet PSPACE.

În 2002, a fost descrisă prima strategie câștigătoare explicită (o strategie de tip reducere) pe o placă 7 × 7.

În anii 2000, prin utilizarea algoritmilor computerului de căutare a forței brute , plăcile Hex până la dimensiunea 9 × 9 (începând cu 2016) au fost complet rezolvate.

Până în 2019, oamenii au rămas mai buni decât computerele cel puțin pe tablele mari, cum ar fi 19x19, dar pe 30 octombrie 2019 programul Mootwo a câștigat împotriva jucătorului uman cu cel mai bun rang ELO de pe LittleGolem, de asemenea câștigător al diferitelor turnee (jocul este disponibil aici ). Acest program s-a bazat pe Polygames (un proiect open-source, inițial dezvoltat de Facebook Artificial Intelligence Research și mai multe universități) folosind un mix de:

  • zero-learning ca în AlphaZero
  • invarianță a dimensiunii plăcilor datorită rețelelor neuronale complet convoluționale (ca în U-Net ) și pooling
  • și arhitecturi în creștere (programul poate învăța pe o tablă mică și apoi poate extrapola pe o tablă mare, spre deosebire de afirmațiile populare justificate despre metodele de inteligență artificială anterioare, cum ar fi AlphaGo original).

Automate

La începutul anilor 1980, Dolphin Microware a publicat Hexmaster , o implementare pentru computerele Atari pe 8 biți . Diferite paradigme rezultate din cercetarea jocului au fost folosite pentru a crea automatele de joc Hex de la computerul digital începând cu anul 2000. Primele implementări au folosit funcții de evaluare care imitau modelul circuitului electric al lui Shannon și Moore încorporat într-un cadru de căutare alfa-beta cu cunoștințe lucrate manual - tipare bazate pe. Începând din 2006, au fost introduse metodele de căutare a copacilor Monte Carlo împrumutate de la implementările de succes ale computerului Go și au dominat în curând domeniul. Mai târziu, modelele realizate manual au fost completate de metode de învățare automată pentru descoperirea modelelor. Aceste programe sunt acum competitive împotriva jucătorilor umani calificați. Evaluările bazate pe Elo au fost atribuite diferitelor programe și pot fi folosite pentru a măsura progresul tehnic, precum și pentru a evalua puterea jocului împotriva oamenilor cu rating Elo. Cercetările actuale sunt adesea publicate fie în jurnalul trimestrial ICGA, fie în seria anuală Advances in Computer Games (van den Herik et al. Eds.).

Joc

Negru vs alb pe o placă hexagonală

Fiecare jucător are o culoare alocată, în mod convențional Roșu și Albastru sau Alb și Negru. Jucătorii rând pe rând plasează o piatră de culoarea lor pe o singură celulă din tabloul general de joc. Odată plasate, pietrele nu sunt mutate, capturate, înlocuite sau scoase de pe tablă. Scopul fiecărui jucător este de a forma o cale conectată din propriile pietre care leagă laturile opuse ale tablei marcate de culorile lor, înainte ca adversarul să își conecteze laturile într-un mod similar. Primul jucător care își completează conexiunea câștigă jocul. Hexagonele de pe fiecare dintre cele patru colțuri aparțin ambelor părți adiacente.

Nu este necesar să construiți un lanț complet între părți sau să umpleți întreaga tablă înainte de a decide jocul (dar dacă se face prin construcție, jucătorul care plasează ultima piatră va câștiga); de obicei, doar 1/3 până la 40% din tablă este umplut înainte de a deveni evident că un jucător sau celălalt poate forța o victorie. Acest lucru este oarecum analog jocurilor de șah care se încheie cu mult înainte de mat - jocul se termină de obicei cu un jucător sau celălalt demisionând.

Deoarece primul jucător care se mută în Hex are un avantaj distinct, regula plăcii este în general implementată pentru corectitudine. Această regulă permite celui de-al doilea jucător să aleagă dacă va schimba pozițiile cu primul jucător după ce primul jucător face prima mișcare.

Strategie

Din dovada unei strategii câștigătoare pentru primul jucător, se știe că placa Hex trebuie să aibă un tip complex de conectivitate care nu a fost niciodată rezolvat. Jocul constă în crearea unor modele mici, care au un tip de conectivitate mai simplu numit „conectat în siguranță” și unirea lor în secvențe care formează o „cale”. În cele din urmă, unul dintre jucători va reuși să formeze o cale conectată în siguranță de pietre și spații între laturile sale de bord și să câștige. Etapa finală a jocului, dacă este necesar, constă în completarea spațiilor goale din cale.

Diagrama 1: pod (A <--> C), un model conectat în siguranță

Un tipar „conectat în siguranță” este compus din pietre de culoarea jucătorului și spații deschise care pot fi unite într-un lanț, o secvență neîntreruptă de pietre adiacente din punct de vedere al marginii, indiferent de modul în care joacă adversarul. Unul dintre cele mai simple astfel de modele este podul (vezi diagrama 1), care constă din două pietre de aceeași culoare (A și C) și o pereche de spații deschise (B și D). Dacă adversarul joacă în oricare dintre spații, jucătorul joacă în celălalt, creând un lanț contiguu. Există, de asemenea, modele conectate în siguranță, care leagă pietrele de margini. Există multe modele mai conectate în siguranță, unele destul de complexe, construite din altele mai simple precum cele prezentate. Modelele și căile pot fi întrerupte de adversar înainte ca acestea să fie complete, astfel încât configurația plăcii în timpul unui joc real pare de multe ori mai degrabă mai degrabă decât un patchwork decât ceva planificat sau proiectat.

Există tipuri de conectivitate mai slabe decât „conectate în siguranță”, care există între pietre sau între modele conectate în siguranță, care au spații multiple între ele. Partea de mijloc a jocului constă în crearea unei rețele de astfel de pietre și modele slab conectate care, sperăm, îi va permite jucătorului, prin completarea verigilor slabe, să construiască doar o cale conectată în siguranță între părți pe măsură ce jocul progresează.

Succesul la Hex necesită o abilitate specială de a vizualiza sinteza tiparelor complexe într-un mod euristic și estimarea dacă astfel de tipare sunt „suficient de puternice” conectate pentru a permite o eventuală victorie. Abilitatea este oarecum similară cu vizualizarea modelelor, secvențierea mișcărilor și evaluarea pozițiilor în șah.

Teoria matematică

Determinarea

John Nash a fost primul care a demonstrat (c. 1949) că Hex nu se poate termina într-o remiză, un rezultat non-banal numit în mod colocvial „teorema Hex”, despre care știm acum că este echivalent cu teorema punctului fix Brouwer. Se pare că nu a publicat dovada. Prima expunere a acestuia apare într-un raport tehnic intern din 1952, în care afirmă că „conectarea și blocarea oponentului sunt acte echivalente”. Prima dovadă riguroasă a fost publicată de John R. Pierce în cartea sa din 1961 Simboluri, semnale și zgomot . În 1979, David Gale a publicat o dovadă care a arătat, de asemenea, că poate fi utilizată pentru a dovedi teorema bidimensională a punctului fix Brouwer și că determinarea variantelor cu dimensiuni superioare demonstrează teorema punctului fix în general. O scurtă schiță a cerinței de finalizare a extragerii fără extragere a Hex din acea lucrare este prezentată mai jos:

  1. Începeți cu o tablă Hex completată cu hexagone marcate fie cu X, fie cu O (indicând ce jucător a jucat pe acel hexagon).
  2. Începând de la un vârf hexagonal la colțul plăcii unde se întâlnesc laturile X și laturile O, desenați o cale de-a lungul marginilor dintre hexagoane cu diferite marcaje X / O.
  3. Deoarece fiecare vârf al căii este înconjurat de trei hexagoane, calea nu se poate intersecta sau bucla, deoarece porțiunea de intersecție a căii ar trebui să se apropie între două hexagoane cu același marcaj. Deci, calea trebuie să se termine.
  4. Calea nu se poate termina în mijlocul plăcii, deoarece fiecare margine a căii se termină într-un nod înconjurat de trei hexagoane - dintre care două trebuie marcate diferit prin construcție. Al treilea hexagon trebuie să fie marcat diferit de cele două adiacente cărării, astfel încât calea să poată continua într-o parte sau alta a celui de-al treilea hexagon.
  5. În mod similar, dacă părțile laterale ale plăcii sunt considerate a fi un perete solid de hexagoane X sau O, în funcție de jucătorul care încearcă să se conecteze acolo, atunci calea nu se poate termina pe laturi.
  6. Astfel calea se poate termina doar într-un alt colț.
  7. Hexagonele de pe ambele părți ale liniei formează un lanț neîntrerupt de X hexagoane pe o parte și hexagone O pe cealaltă prin construcție.
  8. Calea nu se poate termina în colțul opus, deoarece marcajele X și O ar fi inversate la acel colț, încălcând regula de construcție a căii.
  9. Deoarece calea conectează colțurile adiacente, latura plăcii dintre cele două colțuri (să zicem, o parte X) este tăiată de restul plăcii printr-un lanț neîntrerupt al marcajelor opuse (O în acest caz). Acest lanț neîntrerupt leagă în mod necesar celelalte două părți adiacente colțurilor.
  10. Astfel, placa Hex complet completă trebuie să aibă un câștigător.

Există o dovadă a existenței reductio ad absurdum atribuită lui John Nash c. 1949 că primul jucător din Hex pe o tablă de orice dimensiune are o strategie câștigătoare . O astfel de dovadă nu oferă nicio indicație a unei strategii corecte de joc. Dovada este comună pentru o serie de jocuri, inclusiv Hex, și a ajuns să fie numită argumentul furtului de strategie . Iată o declarație informală extrem de condensată a dovezii:

  1. Este imposibil ca jocul să se încheie la egalitate (a se vedea mai sus), prin urmare trebuie să câștige primul sau al doilea jucător.
  2. Deoarece Hex este un joc de informare perfect , trebuie să existe o strategie câștigătoare pentru primul sau pentru al doilea jucător.
  3. Să presupunem că al doilea jucător are o strategie câștigătoare.
  4. Primul jucător poate adopta acum următoarea apărare. Face o mișcare arbitrară. Ulterior, el joacă strategia câștigătoare a celui de-al doilea jucător asumată mai sus. Dacă, jucând această strategie, i se cere să joace pe celula unde a fost făcută o mișcare arbitrară, el face o altă mișcare arbitrară. În acest fel, joacă strategia câștigătoare cu o singură piesă suplimentară întotdeauna pe tablă.
  5. Această piesă suplimentară nu poate interfera cu imitarea de către primul jucător a strategiei câștigătoare, deoarece o piesă suplimentară este întotdeauna un atu și niciodată un handicap. Prin urmare, primul jucător poate câștiga.
  6. Deoarece acum ne-am contrazis presupunerea că există o strategie câștigătoare pentru al doilea jucător, suntem obligați să renunțăm la această presupunere.
  7. În consecință, trebuie să existe o strategie câștigătoare pentru primul jucător.

Complexitatea computațională a generalizărilor

În 1976, Shimon Even și Robert Tarjan au demonstrat că determinarea dacă o poziție într-un joc de Hex generalizat jucat pe grafice arbitrare este o poziție câștigătoare este PSPACE-completă . O întărire a acestui rezultat a fost dovedită de Reisch prin reducerea formulei booleene cuantificate în formă normală conjunctivă la Hex jucat pe grafuri plane arbitrare . În teoria complexității de calcul , se presupune că problemele complete PSPACE nu pot fi rezolvate cu algoritmi eficienți (timp polinomial). Acest rezultat limitează eficiența celor mai buni algoritmi posibili atunci când se iau în considerare poziții arbitrare pe plăci de dimensiuni nelimitate, dar nu exclude posibilitatea unei strategii simple de câștig pentru poziția inițială (pe placi de dimensiune nelimitată) sau o simplă câștigare strategie pentru toate pozițiile de pe o tablă de o anumită dimensiune.

Arborele de joc de 11 de 11 Hex

În 11 × 11 Hex, există aproximativ 2,4 × 10 56 poziții juridice posibile; acest lucru se compară cu 4,6 × 10 46 poziții juridice în șah.

O estimare aproximativă a numărului de noduri din arborele jocului poate fi obținută ca o funcție exponențială a factorului mediu de ramificare și a numărului mediu de straturi într-un joc astfel: b d unde d este adâncimea stratului și b este factorul de ramificare. În Hex, factorul mediu de ramificare este o funcție a adâncimii stratului. S-a afirmat că factorul mediu de ramificare este de aproximativ 100; asta implică o adâncime medie a stratului de 43 (vor exista 121 de spații deschise pe tablă atunci când primul jucător va face prima sa mișcare și 79 când va efectua a 22-a mutare, a 43-a strat - numărul mediu de spații deschise , adică factorul de ramificare, în timpul jocului este (121 + 120 + ... + 79) / 43 = 100). Prin urmare, dimensiunea arborelui de joc are o limită superioară de aproximativ 100 43 = 10 86 . Limita include un anumit număr de poziții ilegale datorate jocului atunci când există un lanț complet pentru un jucător sau altul, precum și exclude pozițiile legale pentru jocurile mai lungi de 43 de straturi. Un alt cercetător a obținut o estimare a spațiului de stare de 10 57 și o dimensiune a arborelui de joc de 10 98 folosind o limită superioară de 50 de straturi pentru joc. Aceasta se compară cu 10 123 nodul dimensiunii arborelui jocului de șah.

Reduceri interesante ale arborelui de joc sunt disponibile observând că placa are simetrie bilaterală duală, precum și simetrie de rotație la 180 °: pentru fiecare poziție, se obține o poziție topologic identică prin răsucirea plăcii stânga-dreapta, sus-jos sau rotirea acesteia cu 180 ° .

Strategii computerizate pentru placi mai mici

În 2002, Jing Yang, Simon Liao și Mirek Pawlak au găsit o strategie de câștigare explicită pentru primul jucător pe tablele Hex de dimensiunea 7 × 7 folosind o metodă de descompunere cu un set de modele locale reutilizabile. Au extins metoda pentru a rezolva slab perechea centrală de deschideri topologice congruente pe plăci 8 × 8 în 2002 și deschiderea centrală pe plăci 9 × 9 în 2003. În 2009, Philip Henderson, Broderick Arneson și Ryan B. Hayward au finalizat analiza placa 8 × 8 cu o căutare pe computer, rezolvând toate deschiderile posibile. În 2013, Jakub Pawlewicz și Ryan B. Hayward au rezolvat toate deschiderile pentru plăcile 9 × 9 și o mișcare de deschidere (cea mai centrală) pe placa 10 × 10. Pentru fiecare N≤10, o primă mișcare câștigătoare în N × N Hex este cea mai centrală, sugerând presupunerea că acest lucru este adevărat pentru fiecare N≥1.

Variante

Alte jocuri de conexiune cu obiective similare, dar structuri diferite includ jocul de comutare Shannon și TwixT . Ambele au un anumit grad de asemănare cu vechiul joc asiatic Go .

Grile dreptunghiulare și hârtie și creion

Jocul poate fi jucat pe o rețea dreptunghiulară, cum ar fi un șah, un tablou sau o tablă go, considerând că spațiile (intersecțiile în cazul go) sunt conectate într-o direcție diagonală, dar nu în cealaltă. Jocul poate fi jucat cu hârtie și creion pe o matrice dreptunghiulară de puncte sau hârtie milimetrică în același mod, folosind două creioane colorate diferite.

Dimensiunile plăcilor

Dimensiunile populare, altele decât cele standard 11x11, sunt 13 × 13 și 19 × 19 ca urmare a relației jocului cu jocul mai vechi Go . Conform cărții O minte frumoasă , John Nash (unul dintre inventatorii jocului) a susținut 14 × 14 ca dimensiune optimă.

Rex (Reverse Hex)

Varianta misère a lui Hex. Fiecare jucător încearcă să-și forțeze adversarul să facă un lanț. Rex este mai lent decât Hex, deoarece, pe orice tablă goală cu dimensiuni egale, jocul care pierde poate întârzia o pierdere până când întreaga placă este plină. Pe tablele cu dimensiuni inegale, jucătorul ale cărui laturi sunt mai depărtate pot câștiga indiferent de cine joacă primul. Pe tablele cu dimensiuni egale, primul jucător poate câștiga pe o tablă cu un număr par de celule pe fiecare parte, iar al doilea jucător poate câștiga pe o tablă cu un număr impar. Pe tablele cu un număr par, una dintre mișcările câștigătoare ale primului jucător este întotdeauna să așezi o piatră în colțul acut.

Blockbusters

Hex a avut o încarnare ca tablou de întrebări din show- ul de televiziune Blockbusters . Pentru a juca o „mișcare”, concurenții au trebuit să răspundă corect la o întrebare. Placa avea 5 coloane alternante de 4 hexagone; jucătorul solo s-ar putea conecta de sus în jos în 4 mișcări, în timp ce echipa de doi ar putea conecta de la stânga la dreapta în 5 mișcări.

Da

Jocul de Y este Hex jucat pe o grilă triunghiulară de hexagoane; obiectul este ca oricare jucător să conecteze toate cele trei laturi ale triunghiului. Y este o generalizare a Hex în măsura în care orice poziție pe o placă Hex poate fi reprezentată ca o poziție echivalentă pe o placă Y mai mare.

Havannah

Havannah este un joc bazat pe Hex. Se diferențiază de Hex prin faptul că se joacă pe o grilă hexagonală de hexagoane și se câștigă prin formarea unuia dintre cele trei tipare.

Projex

Projex este o variantă a lui Hex jucat pe un plan proiectiv real , în care jucătorii au scopul de a crea o buclă necontractabilă . La fel ca în Hex, nu există legături și nu există nicio poziție în care ambii jucători să aibă o legătură câștigătoare.

Competiție

Începând din 2016, au fost raportate turnee over-the-board din Brazilia, Republica Cehă, Danemarca, Franța, Germania, Italia, Olanda, Norvegia, Polonia, Portugalia, Spania, Marea Britanie și SUA.

Unul dintre cele mai mari turnee Hex este organizat de Comitetul Internațional al Jocurilor Matematice din Paris, Franța, care se desfășoară anual din 2013.

Hex face, de asemenea, parte din olimpiada computerului .

Vezi si

Referințe

Lecturi suplimentare

  • Strategia hexagonală: realizarea conexiunilor corecte , Browne C. (2000), AK Peters Ltd. Natick, MA. ISBN  1-56881-117-9 (broșură comercială, 363pgs)
  • HEX: The Full Story , Hayward R. cu Toft B. (2019), CRC Press Boca Raton, FL. ISBN  978-0-367-14422-7 (copertă broșată)

linkuri externe