Ilość sposobów rozegrania gry kółko i krzyżyk – analiza z użyciem Javy

Kółko i krzyżyk to jest bardzo prosta gra, której zasad chyba nikomu nie trzeba tłumaczyć. Natomiast odpowiedzmy sobie na pytanie – na ile sposobów można rozegrać partię kółko i krzyżyk.

Ilość permutacji

Naszym pierwszym oszacowaniem będzie próba użycia kombinatoryki. No bo mamy 9 pól i te pola są po kolei zajmowane przez graczy. Więc wystarczyło by policzyć wszystkie możliwe ciągi wybierania tych 9 pól, spróbujmy więc policzyć to w ten sposób. Na pierwszy ruch (powiedzmy że jest to krzyżyk) można wykonać na dokładnie 9 sposobów i później zawsze pozostanie tylko 8 pól, więc niezależnie od tego, gdzie został postawiony krzyżyk w pierwszym ruchu to kółko w drugim może zostać postawione na jeden z 8 pozostałych sposobów. To daje nam już 72 możliwości po drugim ruchu. Następnie porusza się znowu krzyżyk i ma do wyboru już tylko 7 pól niezależnie jaka pozycja jest na planszy. Czyli 3 pierwsze posunięcia można rozegrać na 9*8*7 = 504 sposoby.

Idąc dalej tym sposobem wnioskujemy, że z każdym kolejnym ruchem ilość możliwości maleje o 1. I aby policzyć ilość możliwości rozegrania partii to trzeba przemnożyć ilość możliwości w każdym ruchu.

No i tak też się liczy ilość permutacji. Czyli n! – gdzie n to ilość elementów zbioru. My mamy 9 elementowy zbiór pól. Więc ilość możliwych ciągów przejścia przez ten zbiór to jest 9!.

Dokładniejsze obliczenia

W każdym razie 9! to jest 362 880. Jest to bardzo dużo jak na taką prostą grę, w rzeczywistości tych sposobów istnieje mniej. Za pomocą ilości permutacji przeszacowaliśmy ilość sposobów rozegrania gry kółko i krzyżyk.

Dzieje się tak dlatego że już w piątym ruchu krzyżyk może wygrać (o ile zakładamy że to właśnie krzyżyk zaczyna). Gdyż piąty ruch to właśnie 3 ruch dla krzyżyka i można tutaj ułożyć jedną z wygrywających kombinacji. No i po wygranej, gra już nie jest kontynuowana. Licząc ilość permutacji nie uwzględniliśmy, że nie zawsze gra dochodzi do 9 posunięcia.

Tak więc jak policzyć prawidłową ilość wszystkich posunięć? Wykorzystamy do tego program napisany w języku Java. Zasymilujemy grę w kółko i krzyżyk, przejdziemy przez wszystkie możliwe posunięcia i jednocześnie zliczymy ich ilość.

package pl.am.analizy.kolkokrzyzyk;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static pl.am.analizy.kolkokrzyzyk.Symbol.*;

public class Plansza {
    private Symbol[][] pola;

    public Plansza(Symbol[][] pola) {
        this.pola = pola;
    }

    public Plansza() {
        pola = new Symbol[][] {
                {BRAK, BRAK, BRAK},
                {BRAK, BRAK, BRAK},
                {BRAK, BRAK, BRAK}
        };
    }

    public boolean czyWygrana(Symbol symbol) {
        return (symbol == pola[0][0] && symbol == pola[0][1] && symbol == pola[0][2]) ||
                (symbol == pola[1][0] && symbol == pola[1][1] && symbol == pola[1][2]) ||
                (symbol == pola[2][0] && symbol == pola[2][1] && symbol == pola[2][2]) ||
                (symbol == pola[0][0] && symbol == pola[1][0] && symbol == pola[2][0]) ||
                (symbol == pola[0][1] && symbol == pola[1][1] && symbol == pola[2][1]) ||
                (symbol == pola[0][2] && symbol == pola[1][2] && symbol == pola[2][2]) ||
                (symbol == pola[0][0] && symbol == pola[1][1] && symbol == pola[2][2]) ||
                (symbol == pola[0][2] && symbol == pola[1][1] && symbol == pola[2][0]);
    }

    public boolean czyRemis() {
        return pola[0][0] != BRAK &&
                pola[0][1] != BRAK &&
                pola[0][2] != BRAK &&
                pola[1][0] != BRAK &&
                pola[1][1] != BRAK &&
                pola[1][2] != BRAK &&
                pola[2][0] != BRAK &&
                pola[2][1] != BRAK &&
                pola[2][2] != BRAK &&
                !czyWygrana(KRZYZYK) &&
                !czyWygrana(KOLKO);
    }

    public boolean czyKoniec() {
        return czyWygrana(KRZYZYK) || czyWygrana(KOLKO) || czyRemis();
    }

    public List<Plansza> wszystkieMozliwePosuniecia(Symbol symbol) {
        List<Plansza> nowePosuniecia = new ArrayList<>();
        for (int i=0; i<3; i++) {
            for (int j=0; j<3; j++) {
                if (pola[i][j] == BRAK) {
                    Symbol[][] nowePola = kopiujPola();
                    nowePola[i][j] = symbol;
                    nowePosuniecia.add(new Plansza(nowePola));
                }
            }
        }

        return nowePosuniecia;
    }

    private Symbol[][] kopiujPola() {
        Symbol[][] nowePola = new Symbol[3][3];

        for (int i=0; i<3; i++) {
            for (int j=0; j<3; j++) {
                nowePola[i][j] = pola[i][j];
            }
        }

        return nowePola;
    }

    @Override
    public String toString() {
        return "" + pola[0][0] + pola[0][1] + pola[0][2] + "\n" +
                 pola[1][0] + pola[1][1] + pola[1][2] + "\n" +
                pola[2][0] + pola[2][1] + pola[2][2] + "\n";
    }

    public static void main(String[] args) {
        Plansza plansza = new Plansza();

        List<Plansza> mozliwePosuniecia = plansza.wszystkieMozliwePosuniecia(KRZYZYK);

        for (Plansza posuniecie : mozliwePosuniecia) {
            System.out.println(posuniecie);
        }
    }
}

package pl.am.analizy.kolkokrzyzyk;

public enum Symbol {
    BRAK("-"),
    KOLKO("O"),
    KRZYZYK("X");

    private String znak;

    Symbol(String znak) {
        this.znak = znak;
    }

    @Override
    public String toString() {
        return znak;
    }
}

package pl.am.analizy.kolkokrzyzyk;

import java.util.List;

import static pl.am.analizy.kolkokrzyzyk.Symbol.KOLKO;
import static pl.am.analizy.kolkokrzyzyk.Symbol.KRZYZYK;

public class IloscMozliwosci {

    public static int iloscMozliwychRozgrywek(Plansza plansza, Symbol symbol) {
        List<Plansza> posuniecia = plansza.wszystkieMozliwePosuniecia(symbol);

        int iloscRozgrywek = 0;

        for (Plansza posuniecie : posuniecia) {
            if (posuniecie.czyKoniec()) {
                iloscRozgrywek++;
            } else {
                Symbol nowySymbol = (symbol == KRZYZYK ? KOLKO : KRZYZYK);
                iloscRozgrywek += iloscMozliwychRozgrywek(posuniecie, nowySymbol);
            }
        }

        return iloscRozgrywek;
    }

    public static void main(String[] args) {
        int iloscRozgrywek = iloscMozliwychRozgrywek(new Plansza(), KRZYZYK);

        System.out.println("iloscRozgrywek = " + iloscRozgrywek);
    }
}