Tic-tac-toe

Tic-tac-toe [1]  este un joc logic între doi adversari pe un câmp pătrat de 3 pe 3 celule sau mai mare (până la un „câmp infinit”). Unul dintre jucători joacă cu „cruci”, al doilea – cu „nu”. Jocul tradițional chinezesc ( Gomoku ) folosește pietre albe și negre.

Versiunea clasică

Regulile jocului

Jucătorii pun pe rând semne 3×3 pe celulele libere ale terenului (una este întotdeauna cruci, cealaltă este întotdeauna zerouri). Primul care își aliniază 3 piesele pe verticală, orizontală sau diagonală câștigă. Prima mutare este făcută de jucătorul care plasează cruci.

De obicei, la sfârșitul jocului, partea câștigătoare taie cu o linie cele trei caractere ale sale (zero sau cruce), care formează un rând continuu.

Analiză

Sunt cunoscuți algoritmi pentru fiecare dintre părți, care garantează un egal în orice joc al adversarului, iar dacă acesta greșește, îți permit să câștigi. Astfel, jocul este într-o stare „ mort mort ”.

Mai jos sunt câteva dintre aceste strategii. Se crede că jucătorul respectă întotdeauna două reguli care au prioritate față de toate celelalte:

Pentru cruci

Faceți prima mișcare spre centru. Mișcările rămase, dacă regulile 1-2 sunt inaplicabile, se fac la cea a colțurilor libere, care este cea mai îndepărtată de mutarea anterioară de zerouri , iar dacă acest lucru nu este posibil, la orice celulă.

     
  X  
  O  

Să demonstrăm că această strategie duce la o victorie sau la egalitate. Dacă zeroul merge în lateral, atunci poziția (până la simetrie) va fi după cum urmează:

  O  
  X  
X    

După aceea, regulile 1 și 2 vor duce la poziția:

X O O
  X  
X    

Câștigă .

Dacă zeroul intră într-un colț, poziția (până la simetrie) va fi după cum urmează:

O    
  X  
    X

În funcție de următoarea mișcare a zeroului, va apărea una dintre cele trei poziții:

O O
  X  
    X
O
  X O
    X
O O 
X
X

Crusele câștigă în primele două poziții  . În al treilea - o remiză .

Pentru zerouri

Rețineți că regulile 1-2, dacă este cazul, au prioritate față de tot ceea ce este scris mai jos.

  • Dacă crucile au făcut prima mutare spre centru, mergeți în orice colț până la sfârșitul jocului, iar dacă acest lucru nu este posibil, în orice celulă.
O
X
  • Dacă încrucișările au făcut prima mișcare la colț, răspundeți cu o mutare în centru.
X
O
   
  • La următoarea mutare, luați colțul opus primei mișcări a crucilor, iar dacă acest lucru nu este posibil, mergeți în lateral.
X
  O
 O X
  • Dacă crucile au făcut prima mișcare în lateral, răspundeți cu o mutare în centru.
  • Dacă următoarea mișcare a crucilor este la colț, luați colțul opus:
X O
  O
X  
  • Dacă următoarea mișcare a crucilor este pe partea opusă, mergeți în orice colț:
O X
O  
  X  
  • Dacă următoarea mișcare a lui X este în partea de lângă prima lor mișcare, mergeți la colțul de lângă ambii X.
O X
X O  
     

Arborele situațiilor de joc

Arborele situațiilor de joc pentru jocul tic-tac-toe, în care jucătorul pentru „tic-tac-toe” merge primul și acționează conform algoritmului de mai sus, iar jucătorul pentru „tic-toe” poate face orice dorește ( în plus, un vârf este dat pentru un act rațional și pentru un act irațional, adică oricare altul), este format din 50 de noduri.

Soluție computer

Pentru a rezolva acest tip de jocuri, un arbore de situații de joc este construit pe un computer în conformitate cu metoda minimax . Numărul total de noduri dintr-un astfel de arbore este 255168 [2] . Acest număr se obține ca suma tuturor mișcărilor posibile - 9 opțiuni la prima treaptă, 8 - pentru fiecare dintre 9 la a doua treaptă, 7 - la fiecare dintre cele 72 de opțiuni la a treia treaptă etc., minus situațiile de sfârșitul timpuriu al jocului (câștig).

Un exemplu de implementare mai simplă a găsirii jucătorului câștigător: https://github.com/evgnor86/XO_game.git

Generalizări

Rânduri mai lungi

Putem considera un joc în care câștigătorul este jucătorul care a construit primul semne identice pe un teren dreptunghiular suficient de mare pentru asta. În acest caz, puteți limita câmpul la o anumită dimensiune (începând cu ), sau să nu-l limitați deloc (în acest caz, se vorbește despre un câmp „infinit”).

A juca până la 4 semne identice pe un teren fără sfârșit nu este interesant, deoarece un începător construiește o „furcă” destul de repede și câștigă. Jocul de la este, de asemenea, neinteresant din cauza „moartei remiză”. Există strategii care împiedică inamicul să construiască vreodată linia dorită. Cu toate acestea, atunci când jocul devine mult mai semnificativ. Această opțiune are un nume special - gomoku . Gomoku a fost jucat inițial pe o tablă de 19×19, ulterior redusă la 15×15 pătrate.

Principala tactică câștigătoare atunci când se joacă pe un teren fără sfârșit este construirea de intersecții („furci”), care nu dau inamicului posibilitatea de a bloca toate modalitățile posibile de a construi un cinci. Pentru a nu pierde, este necesar să întrerupeți în timp util liniile inamicului cu o lungime de trei bucăți sau mai mult.

Practica a arătat că cu reguli egale pentru jucători, cel care face prima mutare are un avantaj care îi permite să câștige cu un joc suficient de priceput, lucru care a fost ulterior dovedit cu strictețe [3] [4] . Pentru a menține interesul pentru joc, au fost propuse diverse opțiuni de modificare a regulilor jocului.

Deci, odată cu introducerea de faulturi (mișcări interzise) pentru un jucător care începe primul - îi este interzis să construiască furci 3 × 3, 4 × 4, precum și să construiască un „rând lung” de piesele sale - un nou joc numit Sa obținut renju , cu o mare varietate de strategii de joc și șanse egale ale jucătorilor.

Modificarea câmpului

Mărirea dimensiunii câmpului a fost deja discutată mai sus. Cea mai simplă, dar cea mai tactică bogăție a jocului, este adăugarea unui pătrat de-a lungul unei laturi a tablei 3x3.

O altă opțiune este schimbarea topologiei câmpului. De exemplu, se pot considera părți opuse ale câmpului care urmează să fie lipite, formând astfel fie suprafața unui cilindru sau a unui tor , fie un plan proiectiv . De asemenea, puteți crește dimensiunea, de exemplu, jucați într-un cub 4x4x4, într-un hipercub și așa mai departe.

Schimb de pictograme

Puteți anula regula care le spune jucătorilor să pună doar propriul tip de pictograme.

De exemplu, o variantă a jocului ar putea fi: jucătorii pun o cruce sau un zero (orice vor); primul câștigă dacă construiește o linie de lungimea necesară din aceleași pictograme, al doilea câștigă dacă acest lucru nu se întâmplă înainte de completarea câmpului.

O altă opțiune: pictograma „proprie” se schimbă cu fiecare mișcare.

Condițiile de câștig se schimbă

În loc să închei jocul prin construirea primei linii de lungimea dorită, nu te poți opri acolo și continua până când câmpul este complet umplut. De exemplu, pe orice teren puteți juca pe cine va construi cei mai mulți „patru” din semnele lor.

Există și o variantă a tic-tac-toe a lui Silverman . Utilizează un teren de joc de celule 4x4. Crucile câștigă dacă există un rând de 4 pictograme identice (cruci sau zerouri), în caz contrar, zerourile câștigă.

Există și o variantă a jocului cu câmpul clasic 3×3, în care este necesar să faci două rânduri pentru a câștiga, în timp ce algoritmul advers are nevoie doar de unul. [5] [6]

Alungirea cursei

O altă opțiune pentru modificarea jocului este să pui la fiecare mișcare nu unul dintre semnele tale, ci două sau mai multe. Așa este jocul Connect6 , în care negrul face prima mișcare expunând un semn, după care jucătorii expun alternativ două semne, primul care construiește o linie de 6 sau mai multe semne ale sale câștigă.

Tic-tac-toe în cultură

Există trei melodii dedicate acestui joc.

  • Cântecul „Tic Tac Toe” al compozitorului Veniamin Basner după versurile lui Mihail Matusovsky interpretat de Taisiya Kalinchenko a devenit laureatul „Songs-74” [7] . Mai târziu a fost cântat de Eduard Khil [8]
  • Katya Lel a cântat o altă melodie cu același nume [9]
  • Al treilea cântec a fost cântat de Viktor Rybin și Natalya Senchukova [10] ca duet .

Vezi și

Note

  1. ↑ În secolul al XIX-lea, alături de denumirea de „tic-tac-toe” (vezi N. A. Leikin , „O zi de școală la o școală germană”, 1871), se mai foloseau „heriki-oniki” sau „heriki”  - conform vechiul nume al alfabetului literelor rusești „X” - „dick” și „O” - „it” ( „Dahl” în Dicționarul Dahl Arhiva copie din 14 iunie 2011 pe Wayback Machine ), „zero” ( N. P. Ghiliarov-Platonov , „Din experiență”, 1886
  2. ↑ Câte jocuri Tic-Tac-Toe (noughts and crosses)? . www.se16.info. Preluat la 16 august 2019. Arhivat din original la 15 februarie 2020.
  3. ↑ Allis, L.V. (1994). În căutarea de soluții în jocuri și inteligență artificială, Ph.D. Teză, Universitatea din Limburg, Maastricht.
  4. ↑ Allis, LV, Herik, HJ van den și Huntjens, MPH (1996). Go-Moku rezolvat prin noi tehnici de căutare. Inteligența computațională, voi. 12.
  5. ↑ De două ori încrucișează-cercuri | joc video | VideoGameGeek
  6. ↑ De două ori încrucișează cercuri: Descărcare gratuită, împrumut și transmitere în flux: Internet Archive
  7. ↑ Taisiya Kalinchenko „Tic-tac-toe” (1974) . Preluat la 17 ianuarie 2022. Arhivat din original la 17 ianuarie 2022.
  8. ↑ Eduard Khil, - Tic-tac-toe . Preluat la 17 ianuarie 2022. Arhivat din original la 17 ianuarie 2022.
  9. ↑ Katya Lel - Tic-tac-toe . Preluat la 17 ianuarie 2022. Arhivat din original la 17 ianuarie 2022.
  10. ↑ Viktor Rybin și Natalya Senchukova - Tic-Tac-Toe . Preluat la 17 ianuarie 2022. Arhivat din original la 17 ianuarie 2022.

Literatură

  • Gardner M. Tic-tac-toe. —M.: Mir, 1988. ISBN 5-03-001234-6 .