m , n , k -spel
Ett m , n , k -spel är ett abstrakt brädspel där två spelare turas om att placera en sten i sin färg på en m -by- n bräda, vinnaren är den spelare som först får k stenar i sin egen färg i en rad, horisontellt, vertikalt eller diagonalt. Alltså, tic-tac-toe är 3,3,3-spelet och freestyle- gomoku är 15,15,5-spelet. Ett m , n , k -spel kallas även ett k -i-rad- spel på en m -by- n- bräda.
M , n , k -spelen är huvudsakligen av matematiskt intresse . Man söker hitta det spelteoretiska värdet, resultatet av spelet med perfekt spel . Detta är känt som att lösa spelet.
Strategistöldargument
Ett standardstrategistöldargument från kombinatorisk spelteori visar att det inte i något m , n , k - spel kan finnas en strategi som säkerställer att den andra spelaren vinner (en andra spelares vinnande strategi ). Detta beror på att en extra sten som ges till någon av spelarna i valfri position bara kan förbättra spelarens chanser. Strategistöldargumentet antar att den andra spelaren har en vinnande strategi och visar en vinnande strategi för den första spelaren. Den första spelaren gör ett godtyckligt drag till att börja med. Efter det låtsas spelaren att de är den andra spelaren och antar den andra spelarens vinnande strategi. De kan göra detta så länge som strategin inte kräver att en sten placeras på den "godtyckliga" torget som redan är upptagen. Om detta händer kan de dock återigen spela ett godtyckligt drag och fortsätta som tidigare med den andra spelarens vinnande strategi. Eftersom en extra sten inte kan skada dem, är detta en vinnande strategi för den första spelaren. Motsägelsen innebär att det ursprungliga antagandet är falskt och att den andra spelaren inte kan ha en vinnande strategi .
Detta argument säger ingenting om huruvida ett visst spel är oavgjort eller vinst för den första spelaren. Dessutom ger det faktiskt ingen strategi för den första spelaren.
Applicera resultat på olika brädstorlekar
Ett användbart begrepp är ett "svagt ( m , n , k ) spel", där k -i-rad av den andra spelaren inte avslutar spelet med en andra spelares vinst.
Om svag ( m , n , k ) är oavgjort, kommer en minskning av m eller n , eller ökning av k också att resultera i ett oavgjort spel.
Omvänt, om svag eller normal ( m , n , k ) är en vinst, så är varje större svag ( m , n , k ) en vinst.
Observera att bevis på drag med hjälp av parningsstrategier också bevisar oavgjort för den svaga versionen och därmed för alla mindre versioner.
Allmänna resultat
Följande uttalanden hänvisar till den första spelaren i det svaga spelet, förutsatt att båda spelarna använder en optimal strategi.
- 000000000000000000 Om en viss ( m , n , k ) är oavgjort, så är ( m , n , k ) med k ≥ k oavgjort, och ( m , n , k ) med m ≤ m och n ≤ n är oavgjort. På samma sätt, om ( m , n , k ) är en vinst, så är ( m , n , k ) med k ≤ k en vinst, och ( m , n , k ) med m ≥ m och n ≥ n är en vinst.
- k ≥ 9 är oavgjort: när k = 9 och brädan är oändlig kan den andra spelaren dra via en "parningsstrategi". Oavgjort på en oändlig bräda betyder att spelet kommer att fortsätta för evigt med perfekt spel. En parningsstrategi innebär att dela upp alla rutor på brädet i par på ett sådant sätt att genom att alltid spela på paret i den första spelarens ruta, säkerställs den andra spelaren att den första spelaren inte kan få k på en rad . En parningsstrategi på en oändlig bräda kan också tillämpas på vilken ändlig bräda som helst – om strategin kräver ett drag utanför brädet, gör den andra spelaren ett godtyckligt drag inuti brädet.
- k ≥ 8 är ett drag på en oändlig bräda. Det är inte klart om denna strategi gäller för några ändliga brädstorlekar. Det är inte känt om den andra spelaren kan tvinga fram oavgjort när k är 6 eller 7 på en oändlig bräda.
- k ≥ 3 och antingen k > m eller k > n är oavgjort, också genom en parningsstrategi i dimensionen inte mindre än k (eller trivialt omöjligt att vinna om båda är mindre)
Specifika resultat
- k = 1 och k = 2 är triviala vinster, förutom (1,1,2) och (2,1,2)
- (3,3,3) är oavgjort (se Tic-tac-toe ), och ( m , n ,3) är oavgjort om m < 3 eller n < 3. ( m , n ,3) är vinst om m ≥ 3 och n ≥ 4 eller m ≥ 4 och n ≥ 3.
- (5,5,4) är oavgjort, vilket betyder att ( m , n ,4) är oavgjort för m ≤ 5 och n ≤ 5, och (6,5,4) är vinst, vilket betyder att ( m , n ,4) är vinst för m ≥ 6 och n ≥ 5 eller m ≥ 5 och n ≥ 6. ( m ,4,4) är vinst för m ≥ 30 (Lustenberger, 1967) och oavgjort för m ≤ 8. Det är okänt om ( m ,4,4) är en vinst eller oavgjort för 9 ≤ m ≤ 29.
- Datorsökning av Wei-Yuan Hsu och Chu-Ling Ko har visat att både (7,7,5) och (8,8,5) är drag, vilket betyder att ( m , n ,5) är drag för m ≤ 8 och n ≤ 8. Datorsökning av L. Victor Allis har visat att (15,15,5) är en vinst, även med en av Gomokus restriktiva regler .
- (9,6,6) och (7,7,6) är båda oavgjorda via par.
Flerdimensionell variant
Det är möjligt att överväga varianter som spelas på en flerdimensionell bräda istället för en tvådimensionell bräda.
För fallet med k -i-rad där brädan är en n -dimensionell hyperkub med alla kanter med längden k , bevisade Hales och Jewett att spelet är oavgjort om k är udda och
- k ≥ 3 n − 1
eller om k är jämnt och
- k ≥ 2 n +1 − 2.
De antar att spelet är oavgjort även när antalet celler är minst dubbelt så många linjer, vilket händer om och bara om
- 2 k n ≥ ( k + 2) n .
Se även
| Varianter |  |
|
|---|---|---|
| Relaterade begrepp | ||
| Liknande spel | ||