Ristinolla

Tic-tac-toe [1]  on looginen peli kahden vastustajan välillä neliökentällä, jossa on 3 x 3 solua tai suurempi ("äärettömään kenttään" asti). Yksi pelaajista pelaa "risteillä", toinen - "ei". Perinteinen kiinalainen peli ( Gomoku ) käyttää mustia ja valkoisia kiviä.

Klassinen versio

Pelin säännöt

Pelaajat laittavat vuorotellen 3×3 merkkejä kentän vapaisiin soluihin (yksi on aina risti, toinen aina nolla). Ensimmäinen, joka asettaa 3 nappulaansa pystysuoraan, vaakasuoraan tai vinottain, voittaa. Ensimmäisen liikkeen tekee pelaaja, joka laittaa ristiä.

Yleensä pelin lopussa voittajapuoli ylittää viivalla sen kolme merkkiä (nolla tai risti), jotka muodostavat jatkuvan rivin.

Analyysi

Jokaiselle osapuolelle tunnetaan hyvin algoritmit, jotka takaavat tasapelin missä tahansa vastustajan pelissä, ja jos hän tekee virheen, voit voittaa. Peli on siis " kuollut kuollut " -tilassa.

Alla on joitain näistä strategioista. Uskotaan, että pelaaja kunnioittaa aina kahta sääntöä, jotka ovat etusijalla kaikkiin muihin nähden:

Risteille

Tee ensimmäinen liike keskelle. Loput siirrot, jos säännöt 1-2 eivät sovellu, tehdään vapaiden kulmien liikkeelle, joka on kauimpana edellisestä nollien siirrosta , ja jos tämä ei ole mahdollista, mihin tahansa soluun.

     
  X  
  O  

Osoittakaamme, että tämä strategia johtaa voittoon tai tasapeliin. Jos nolla menee sivulle, sijainti (symmetriaan asti) on seuraava:

  O  
  X  
X    

Sen jälkeen säännöt 1 ja 2 johtavat asemaan:

X O O
  X  
X    

Voita .

Jos nolla menee nurkkaan, sijainti (symmetriaan asti) on seuraava:

O    
  X  
    X

Seuraavasta nollan siirrosta riippuen syntyy yksi kolmesta asennosta:

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

Ristit voittaa kahdessa ensimmäisessä paikassa  . Kolmannessa - tasapeli .

Nollia varten

Muista, että säännöt 1-2 ovat soveltuvin osin ensisijaisia ​​kaikkeen alla kirjoitettuun nähden.

  • Jos ristit tekivät ensimmäisen liikkeen keskelle, siirry mihin tahansa nurkkaan pelin loppuun asti, ja jos tämä ei ole mahdollista, mihin tahansa soluun.
O
X
  • Jos ristit tekivät ensimmäisen liikkeen kulmaan, vastaa liikkeellä keskelle.
X
O
   
  • Ota seuraavalla liikkeellä ristien ensimmäistä liikettä vastapäätä oleva kulma ja jos tämä ei ole mahdollista, mene sivuun.
X
  O
 O X
  • Jos ristit tekivät ensimmäisen liikkeen sivulle, vastaa liikkeellä keskelle.
  • Jos ristien seuraava liike on kulmaan, ota vastakkainen kulma:
X O
  O
X  
  • Jos ristien seuraava liike on vastakkaisella puolella, siirry mihin tahansa kulmaan:
O X
O  
  X  
  • Jos X:n seuraava liike on heidän ensimmäisen liikkeensä viereiselle puolelle, mene molempien X:iden viereen kulmaan
O X
X O  
     

Pelitilanteiden puu

Pelitilanteiden puu pelille tic-tac-toe, jossa "tic-tac-toe" -pelin pelaaja menee ensin ja toimii yllä olevan algoritmin mukaisesti, ja "tic-toe"-pelaaja voi tehdä mitä haluaa ( lisäksi yksi kärki on annettu rationaaliselle ja irrationaaliselle aktille, eli mille tahansa muulle), koostuu 50 solmusta.

Tietokoneratkaisu

Tällaisten pelien ratkaisemiseksi tietokoneelle rakennetaan minimax -menetelmän mukaisesti pelitilanteiden puu . Solmujen kokonaismäärä tällaisessa puussa on 255168 [2] . Tämä luku saadaan kaikkien mahdollisten liikkeiden summana - 9 vaihtoehtoa ensimmäisessä vaiheessa, 8 - kullekin 9:lle toisessa vaiheessa, 7 - jokaisessa 72 vaihtoehdossa kolmannessa vaiheessa jne., josta on vähennetty tilanteet pelin alussa (voitto).

Esimerkki yksinkertaisemmasta toteutuksesta voittajan löytämiseksi: https://github.com/evgnor86/XO_game.git

Yleistykset

Pidemmät rivit

Voimme harkita peliä, jossa voittaja on pelaaja, joka ensin rakensi identtiset merkit tähän riittävän suurelle suorakaiteen muotoiselle kentälle. Tässä tapauksessa voit rajoittaa kentän johonkin kokoon (alkaen kirjaimella ) tai olla rajoittamatta sitä ollenkaan (tässä tapauksessa puhutaan "äärettömästä" kentästä).

Enintään 4 identtisen merkin pelaaminen loputtomalla kentällä ei ole mielenkiintoista, koska aloittelija rakentaa "haarukan" melko nopeasti ja voittaa. Peli osoitteessa on myös epäkiinnostava "draw death" vuoksi. On strategioita, jotka estävät vihollista rakentamasta haluttua linjaa koskaan. Kuitenkin, kun pelistä tulee paljon merkityksellisempää. Tällä valinnalla on erityinen nimi - gomoku . Gomokua pelattiin alun perin 19×19 laudalla, joka pienennettiin myöhemmin 15×15 ruutuun.

Päävoittotaktiikka loputtomalla kentällä pelatessa on risteyskohtien ("haarukoiden") rakentaminen, jotka eivät anna viholliselle mahdollisuutta estää kaikkia mahdollisia tapoja rakentaa viisi. Jotta et menetä, on välttämätöntä katkaista vihollisen linjat ajoissa vähintään kolmen kappaleen pituudella.

Käytäntö on osoittanut, että pelaajien yhtäläisillä säännöillä ensimmäisen liikkeen tekijällä on etu, jonka ansiosta hän voi voittaa riittävän taitavalla pelillä, mikä todistettiin myöhemmin tiukasti [3] [4] . Kiinnostuksen säilyttämiseksi peliä kohtaan ehdotettiin erilaisia ​​vaihtoehtoja pelin sääntöjen muokkaamiseen.

Joten, kun ensimmäisenä aloittavalle pelaajalle otettiin käyttöön virheitä (kiellettyjä liikkeitä) - hän ei saa rakentaa haarukoita 3 × 3, 4 × 4, samoin kuin rakentaa nappulastaan ​​"pitkä rivi" - uusi peli ns. Renju saatiin , jossa oli laaja valikoima pelistrategioita ja pelaajien yhtäläiset mahdollisuudet.

Kentän muutos

Kentän koon kasvattamisesta on jo keskusteltu edellä. Pelin yksinkertaisin, mutta taktisin rikkaus on lisätä yksi neliö 3x3-laudan toiselle puolelle.

Toinen vaihtoehto on muuttaa kentän topologiaa. Esimerkiksi kentän vastakkaisia ​​puolia voidaan pitää liimattavana, jolloin muodostuu joko sylinterin tai toruksen pinta tai projektiotaso . Voit myös lisätä ulottuvuutta, esimerkiksi pelata 4x4x4-kuutiossa, hyperkuutiossa ja niin edelleen.

Ikonivaihto

Voit peruuttaa säännön, joka käskee pelaajia asettamaan vain omanlaisiaan kuvakkeita.

Esimerkiksi pelin muunnelma voisi olla: pelaajat laittavat ristin tai nollan (mitä tahansa he haluavat); ensimmäinen voittaa, jos se rakentaa vaaditun pituisen rivin samoista kuvakkeista, toinen voittaa, jos näin ei tapahdu ennen kuin kenttä on täytetty.

Toinen vaihtoehto: "oma"-kuvake muuttuu jokaisen liikkeen yhteydessä.

Voittoehdot muuttuvat

Sen sijaan, että lopettaisit pelin rakentamalla ensimmäisen halutun pituisen rivin, et voi lopettaa tähän ja jatkaa, kunnes kenttä on täysin täytetty. Esimerkiksi millä tahansa kentällä voit pelata sillä, kuka rakentaa eniten "neljää" merkeistään.

Myös Silvermanin tic-tac-toe-varsiversio on olemassa . Se käyttää 4x4 solujen pelikenttää. Ristit voittavat, jos rivissä on 4 identtistä kuvaketta (ristejä tai nollia), muuten nollat ​​voittaa.

Pelistä on myös variantti klassisella 3×3-kentällä, jossa voittoon tarvitaan kaksi riviä, kun taas vastakkainen algoritmi tarvitsee vain yhden. [5] [6]

Vedon pidennys

Toinen vaihtoehto pelin muokkaamiseen on laittaa jokaiseen liikkeeseen ei yhtä merkkiäsi, vaan kaksi tai useampia. Tällainen on Connect6 - peli , jossa musta tekee ensimmäisen liikkeen paljastamalla yhden merkin, jonka jälkeen pelaajat paljastavat vuorotellen kaksi merkkiä, joista ensimmäinen, joka rakentaa 6 tai useamman merkin rivin, voittaa.

Tic-tac-toe kulttuurissa

Tälle pelille on omistettu kolme kappaletta.

  • Taisiya Kalinchenkon esittämä säveltäjä Veniamin Basnerin kappale "Tic Tac Toe" Mihail Matusovskin säkeisiin tuli "Songs-74" -palkinnon saajaksi [7] . Myöhemmin sen lauloi Eduard Khil [8]
  • Katya Lel lauloi toisen kappaleen samalla nimellä [9]
  • Kolmannen kappaleen lauloivat Viktor Rybin ja Natalya Senchukova [10] duetona .

Katso myös

Muistiinpanot

  1. ↑ 1800-luvulla käytettiin nimen "tic-tac-toe" (ks . N. A. Leikin , "Koulupäivä saksalaisessa koulussa", 1871) lisäksi myös "heriki-oniki" tai "heriki"  - mukaan venäläisten kirjainten vanha nimi "X" - "dick" ja "O" - "it" ( "Dahl" Dictionary of Dahl Archival -kopiossa 14. kesäkuuta 2011 Wayback Machinessa ), "nollat" ( N. P. Giljarov-Platonov , "Kokemuksesta", 1886
  2. ↑ Kuinka monta Tic-Tac-Toe (noughts and cross) peliä? . www.se16.info. Haettu 16. elokuuta 2019. Arkistoitu alkuperäisestä 15. helmikuuta 2020.
  3. ↑ Allis, L.V. (1994). Ratkaisujen etsiminen peleissä ja tekoälyssä, Ph.D. Väitöskirja, Limburgin yliopisto, Maastricht.
  4. ↑ Allis, LV, Herik, HJ van den ja Huntjens, MPH (1996). Go-Moku ratkaistu uusilla hakutekniikoilla. Computational Intelligence, Voi. 12.
  5. ↑ Kaksi kertaa ristiä-ympyröitä | videopeli | VideoGameGeek
  6. ↑ Kaksi kertaa ristiin-ympyrät : ilmainen lataus, lainaus ja suoratoisto : Internet-arkisto
  7. ↑ Taisiya Kalinchenko "Tic-tac-toe" (1974) . Haettu 17. tammikuuta 2022. Arkistoitu alkuperäisestä 17. tammikuuta 2022.
  8. ↑ Eduard Khil, - Tic-tac-toe . Haettu 17. tammikuuta 2022. Arkistoitu alkuperäisestä 17. tammikuuta 2022.
  9. ↑ Katya Lel - Tic-tac-toe . Haettu 17. tammikuuta 2022. Arkistoitu alkuperäisestä 17. tammikuuta 2022.
  10. ↑ Viktor Rybin ja Natalya Senchukova - Tic-Tac-Toe . Haettu 17. tammikuuta 2022. Arkistoitu alkuperäisestä 17. tammikuuta 2022.

Kirjallisuus

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