Luffarschack

Tic-tac-toe [1]  är ett logiskt spel mellan två motståndare på ett kvadratiskt fält med 3 gånger 3 celler eller större (upp till ett "oändligt fält"). En av spelarna spelar med "kryss", den andra - med "noes". Det traditionella kinesiska spelet ( Gomoku ) använder svarta och vita stenar.

Den klassiska versionen

Spelregler

Spelare turas om att sätta 3×3-tecken på fältets fria celler (en är alltid kryss, den andra är alltid nollor). Den första att rada upp 3 av sina pjäser vertikalt, horisontellt eller diagonalt vinner. Det första draget görs genom att spelaren sätter kryss.

Vanligtvis, i slutet av spelet, stryker den vinnande sidan ut med en linje dess tre tecken (nolla eller kryss), som utgör en sammanhängande rad.

Analys

Algoritmer är välkända för var och en av parterna, som garanterar oavgjort i vilket spel som helst av motståndaren, och om han gör ett misstag låter de dig vinna. Således är spelet i ett " död död " tillstånd.

Nedan finns några av dessa strategier. Man tror att spelaren alltid respekterar två regler som har företräde framför alla andra:

För kryss

Gör det första steget till mitten. De återstående dragen, om reglerna 1-2 inte är tillämpliga, görs på de fria hörnen, som är längst bort från föregående drag av nollor , och om detta inte är möjligt, till någon cell.

     
  X  
  O  

Låt oss bevisa att denna strategi leder till vinst eller oavgjort. Om nollan går åt sidan blir positionen (upp till symmetri) som följer:

  O  
  X  
X    

Därefter kommer reglerna 1 och 2 att leda till positionen:

X O O
  X  
X    

Vinn .

Om nollan går in i ett hörn blir positionen (upp till symmetri) som följer:

O    
  X  
    X

Beroende på nästa drag av nollan kommer en av tre positioner att uppstå:

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

Kryss vinner i de två första positionerna  . I den tredje - oavgjort .

För nollor

Kom ihåg att regler 1-2, om tillämpligt, har företräde framför allt som skrivs nedan.

  • Om kryssen gjorde det första draget till mitten, gå till valfritt hörn fram till slutet av spelet, och om detta inte är möjligt, till valfri cell.
O
X
  • Om kryssen gjorde det första draget till hörnet, svara med ett drag till mitten.
X
O
   
  • Vid nästa drag, ta hörnet mitt emot det första draget av kryssen, och om detta inte är möjligt, gå åt sidan.
X
  O
 O X
  • Om kryssen gjorde det första draget åt sidan, svara med ett drag till mitten.
  • Om nästa drag av kryssen är till hörnet, ta det motsatta hörnet:
X O
  O
X  
  • Om nästa drag av kryssen är på motsatt sida, gå till valfritt hörn:
O X
O  
  X  
  • Om nästa drag av X:en är vid sidan av deras första drag, gå till hörnet bredvid båda X:en
O X
X O  
     

Träd för spelsituationer

Trädet av spelsituationer för spelet tic-tac-toe, där spelaren för "tic-tac-toe" går först och agerar enligt ovanstående algoritm, och spelaren för "tic-tac-toe" kan göra vad han vill ( dessutom ges en vertex för en rationell och för en irrationell handling, det vill säga vilken annan som helst), består av 50 noder.

Datorlösning

För att lösa den här typen av spel byggs ett träd av spelsituationer på en dator i enlighet med minimaxmetoden . Det totala antalet noder i ett sådant träd är 255168 [2] . Detta antal erhålls som summan av alla möjliga drag - 9 alternativ på det första steget, 8 - för vart och ett av 9 på det andra steget, 7 - på vart och ett av de 72 alternativen på det tredje steget, etc., minus situationerna med tidigt slut av spelet (vinst).

Ett exempel på en enklare implementering för att hitta den vinnande spelaren: https://github.com/evgnor86/XO_game.git

Generaliseringar

Längre rader

Vi kan överväga ett spel där vinnaren är den spelare som först byggde identiska skyltar på ett rektangulärt fält som är tillräckligt stort för detta. I det här fallet kan du begränsa fältet till en viss storlek (som börjar med ), eller inte begränsa det alls (i det här fallet talar de om ett "oändligt" fält)

Att spela upp till 4 identiska tecken på ett oändligt fält är inte intressant, eftersom en nybörjare bygger en "gaffel" ganska snabbt och vinner. Spelet på är också ointressant på grund av "draw death". Det finns strategier som hindrar fienden från att någonsin bygga den önskade linjen. Men när spelet blir mycket mer meningsfullt. Det här alternativet har ett speciellt namn - gomoku . Gomoku spelades ursprungligen på en 19×19-bräda, senare reducerad till 15×15 rutor.

Den främsta vinnande taktiken när man spelar på ett oändligt fält är konstruktionen av korsningar ("gafflar"), som inte ger fienden möjligheten att blockera alla möjliga sätt att bygga en femma. För att inte förlora är det nödvändigt att i tid avbryta fiendens linjer med en längd på tre stycken eller mer.

Övning har visat att med lika regler för spelarna har den som gör det första draget en fördel som gör att han kan vinna med ett tillräckligt skickligt spel, vilket sedan bevisades strikt [3] [4] . För att behålla intresset för spelet föreslogs olika alternativ för att ändra spelets regler.

Så, med införandet av fouls (förbjudna drag) för en spelare som börjar först - han är förbjuden att bygga gafflar 3 × 3, 4 × 4, samt att bygga en "lång rad" av sina pjäser - ett nytt spel som heter renju erhölls , med ett brett utbud av spelstrategier och lika chanser för spelarna.

Fältändring

Att öka fältstorleken har redan diskuterats ovan. Den enklaste, men mest taktiska rikedomen i spelet, är att lägga till en ruta längs ena sidan av 3x3-brädet.

Ett annat alternativ är att ändra fältets topologi. Till exempel kan man överväga att motsatta sidor av fältet ska limmas och på så sätt bilda antingen ytan av en cylinder eller torus eller ett projektivt plan . Du kan också öka dimensionen, till exempel spela i en 4x4x4 kub, i en hyperkub och så vidare.

Ikonutbyte

Du kan avbryta regeln som säger till spelare att bara sätta sin egen typ av ikoner.

Till exempel kan en variant av spelet vara: spelare sätter ett kryss eller en nolla (vad de vill); den första vinner om den bygger en rad med önskad längd från samma ikoner, den andra vinner om detta inte händer innan fältet är ifyllt.

Ett annat alternativ: "egen" ikon ändras med varje drag.

Vinstvillkor ändras

Istället för att avsluta spelet genom att bygga den första raden av önskad längd, kan du inte stanna där och fortsätta tills fältet är helt fyllt. Till exempel, på vilken plan som helst kan du spela på vem som bygger flest "fyror" från sina skyltar.

En variant av Silvermans tic-tac-toe finns också . Den använder en spelplan med 4x4 celler. Kryssen vinner om det finns en rad med 4 identiska ikoner (kors eller nollor), annars vinner nollorna.

Det finns också en variant av spelet med det klassiska 3×3-fältet, där det är nödvändigt att göra två rader för att vinna, medan den motsatta algoritmen bara behöver en. [5] [6]

Stroke förlängning

Ett annat alternativ för att modifiera spelet är att sätta på varje drag inte ett av dina tecken, utan två eller fler. Sådan är Connect6 -spelet , där svart gör det första draget genom att exponera ett tecken, varefter spelarna växelvis exponerar två tecken, den första som bygger en rad med 6 eller fler av sina tecken vinner.

Tic-tac-toe i kulturen

Det finns tre låtar dedikerade till detta spel.

  • Låten "Tic Tac Toe" av kompositören Veniamin Basner till verserna av Mikhail Matusovsky framförd av Taisiya Kalinchenko blev pristagaren av "Songs-74" [7] . Senare sjöngs den av Eduard Khil [8]
  • Katya Lel sjöng en annan låt med samma namn [9]
  • Den tredje låten sjöngs av Viktor Rybin och Natalya Senchukova [10] som en duett .

Se även

Anteckningar

  1. ↑ På 1800-talet användes tillsammans med namnet ”tic-tac-toe” (se N. A. Leikin , ”En skoldag i en tysk skola”, 1871), även ”heriki-oniki” eller ”heriki”  - enl. det gamla namnet på de ryska bokstäverna alfabetet "X" - "dick" och "O" - "it" ( "Dahl" i Dictionary of Dahls arkivkopia daterad 14 juni 2011 på Wayback Machine ), "nollor" ( N. P. Gilyarov-Platonov , "Från erfarenheten", 1886
  2. ↑ Hur många Tic-Tac-Toe-spel? . www.se16.info. Hämtad 16 augusti 2019. Arkiverad från originalet 15 februari 2020.
  3. ↑ Allis, L.V. (1994). Söker efter lösningar inom spel och artificiell intelligens, Ph.D. Avhandling, University of Limburg, Maastricht.
  4. ↑ Allis, LV, Herik, HJ van den och Huntjens, MPH (1996). Go-Moku löst med nya söktekniker. Computational Intelligence, vol. 12.
  5. ↑ Två gånger korsar cirklar | videospel | VideoGameGeek
  6. ↑ Två gånger korsar cirklar: Gratis nedladdning, lån och strömning: Internetarkiv
  7. ↑ Taisiya Kalinchenko "Tic-tac-toe" (1974) . Hämtad 17 januari 2022. Arkiverad från originalet 17 januari 2022.
  8. ↑ Eduard Khil, - Tic-tac-toe . Hämtad 17 januari 2022. Arkiverad från originalet 17 januari 2022.
  9. ↑ Katya Lel - Tic-tac-toe . Hämtad 17 januari 2022. Arkiverad från originalet 17 januari 2022.
  10. ↑ Viktor Rybin och Natalya Senchukova - Tic-Tac-Toe . Hämtad 17 januari 2022. Arkiverad från originalet 17 januari 2022.

Litteratur

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