Kółko i krzyżyk pod lupą

Wstęp

Kółko i krzyżyk to gra do której niewiele trzeba: coś do pisania i kawałek kartki papieru. Po długim istnieniu gry powstały strategie, które gwarantują, że nie można przegrać. Jednak kiedy gra dwóch graczy strategią nie do pokonanie gra zawsze kończy się remisem. Oczywiście pod warunkiem, że wszystkie ruchy zostaną wykonane poprawnie. Jednak zadałem sobie pytanie czy gracze mają równe szanse na zwycięstwo.

Wyniki

Dane na podstawie których opracowałem ten artykuł dotyczą wszystkich możliwych rozgrywek. Ze względu na ograniczoną ilość ruchów liczba możliwych scenariuszy wynosi maksymalnie 268668. Oczywiście, gdyby gra nie mogła się skończyć przed wszystkimi możliwymi ruchami rozgrywek byłoby więcej, a dokładnie 9! = 362880. Rezultaty przedstawia poniższa tabelka:

Dane w tabelce przedstawiają ile gier wygrywa, który z graczy po którym ruchu. Gry nierozstrzygnięte w ostatnim wierszu oznaczają liczbę remisów. W poprzednich wierszach gry nierozstrzygnięte należy traktować jako gry, które trwają i następny gracz ma możliwy ruch. Na podstawie danych można określić procentową szansę na remis i zwycięstwo każdego z graczy:

Wygrane Gracz 1	Wygrane Gracz 2	Remis	Wykres
0,00%	0,00%	100,00%
0,00%	0,00%	100,00%
0,00%	0,00%	100,00%
0,00%	0,00%	100,00%
8,33%	0,00%	91,67%
2,22%	8,13%	89,65%
27,44%	2,91%	69,65%
16,17%	24,44%	59,39%
45,44%	24,44%	30,12%

Na wykresie można odczytać, że szansę zwycięstwa pierwsze gracza są bardzo duże. Krótka analiza tabelki to potwierdza: gracz rozpoczynający grę w 7 ruchu ma prawie 10 razy większą szansę od drugiego gracza. Wyniki pokrywają się ze typowymi strategiami. Jednak miażdżąca okazuje się tutaj konkluzja końcowa. Ponad 45% gier kończy się zwycięstwem gracza pierwszego to dwa razy więcej niż ma gracz drugi. Zaskakujące okazuje się 30% szansy na remis - w przypadku gier osób, które potrafią grać wynosi on aż 100%. (Oczywiście jest to spowodowane sprawdzaniem wszystkich możliwych przypadków.)

Skąd te dane?

Wszystkie wyniki jakie znajdują się na stronie nie są wzięte z sufitu, ani wyliczone matematycznie. Wystarczył niewielki program, który wszystko policzył. Metoda sprawdzania to brute force, czyli program przejrzał wszystkie możliwe przypadki rozgrywki. Przy tym nie trzymał się żadnej strategii. Plansza była reprezentowana przez tablicę 3x3, a przechowywany typ danych to char. Wolne pola były oznaczone przez spację ' ', kółka przez 'o', a krzyżyki 'x'. Pierwszą funkcją, która była potrzebna w programie była funkcja getBoard(), która umożliwia stworzenie kwadratowej tablicy n x n:

1. char** getBoard(int n){
2.   char** board = new char*[n];
3.   for(int i = 0; i < n; i++){
4.     board[i] = new char[n];
5.     for(int j = 0; j < n; j++){
6.       board[i][j] = ' ';
7.     }
8.   }
9.   return board;
10. }

Następnie w celu uproszczenia kodu zadeklarowałem trzy zmienne globalne, których zadaniem było przetrzymywania wyników. Zadeklarowanie ich jako globalne pozwoliła na nieprzekazywania ich w funkcji, jak również ominięcie deklarowania specjalnej struktury do przechowywania trzech liczb:

1. int wino = 0, winx = 0, tie = 0;

Teraz przyszedł czas na funkcję, która będzie wykonywać ruchy. Jej działanie zbiega się do stwierdzenia czy są wolne pola. Jeśli tak to dla każdego pola generuje nową tablicę z nowo ustawionym symbolem w odpowiednim miejscu. Dalsza część algorytmu zależy od tego czy ruch dał graczowi zwycięstwo. Jeśli tak to należy zwiększyć liczbę zwycięstw gracza i wrócić do poprzedniego stanu tablicy. Jednak jeśli nie to funkcja powinna sprawdzić dalsze możliwe ruchy na podstawie nowej tablicy:

1. void check(char** board, int n, int player = 0){
2.   char p = (player == 0) ? 'o' : 'x';
3.   if(n > 0){
4.     for(int x = 0; x < 3; x++){
5.       for(int y = 0; y < 3; y++){
6.         if(board[x][y] == ' '){
7.           board[x][y] = p;
8.           if(checkWin(board, x, y, p)){
9.             if(player == 0) wino++; else winx++;
10.           } else {
11.             check(board, n-1, (player+1)%2);
12.           }
13.           board[x][y] = ' ';
14.         }
15.       }
16.     }
17.   } else {
18.     tie++;
19.   }
20. }

(1.) Procedura check() przyjmuje board** stan planszy, n ile ruchów można jeszcze wykonać oraz player - określa gracza, który aktualnie wykonuje (0 - gracz pierwsza, 1 - gracz drugi). (2.) Określenie znaku gracza. (3.) Jeśli n = 0 oznacza to, że już nie ma poprawnych ruchów, dlatego (18.) wystarczy zwiększyć liczbę remisów. Jednak kiedy są dostępne ruchy to (4.) dla każdego wiersza, (5.) dla każdego pola o ile (6.) jest wolne: (7.) należy wpisać symbol i (8.) sprawdzić zwycięstwo. (9.) Jeśli gracz zwyciężył to wystarczy zwiększyć licznik zwycięstw odpowiedniego gracza. Jednak w przypadku, gdy nie to (11.) należy wywołać funkcję check() z nowym stanem na planszy. Po zakończeniu badania dalszych ruchów należy (13.) pole ustawić ponownie na wolne. Jest to bardzo ważne, ponieważ nie wykonujemy kopii dla każdej kolejnej iteracji - program wciąż pracuje na tej samej tablicy przez cały czas.

Funkcja, która określa czy gracz wygrał ma do dyspozycji: board - planszę gry, pozycje ostatniego ruchu x, y oraz symbol gracza p.

1. bool checkWin(char** board, int x, int y, char p){
2.   return ((board[x][0]==p && board[x][1]==p && board[x][2]==p) ||
3.     (board[0][y]==p && board[1][y]==p && board[2][y]==p) ||
4.     (x == y && board[0][0]==p && board[1][1]==p && board[2][2]==p) ||
5.     (x == 3 - y && board[0][2]==p && board[1][1]==p && board[2][0]==p));
6. }

Zwycięstwo może być wtedy, gdy: (2.) wszystkie w linii poziomo są identyczne lub (3.) pionowo. Jednak jeśli zmieniony został element na diagonali to trzeba sprawdzić (4. - 5.) jedną z nich lub obydwie dla punktu (1, 1).

Na samo koniec zostało tylko wywołać funkcję tak, aby wypisała na ekran ile gier zakończyło się zwycięstwem każdego gracza lub remisem po n ruchach:

1. int main () {
2.   char** board = getBoard(3);
3.   check(board, 9);
4.   cout << "Rozegranych gier: \t" << (wino+winx+tie) << endl;
5.   cout << "- wygranych gracz 1: \t" << wino << endl;
6.   cout << "- wygranych gracz 2: \t" << winx << endl;
7.   cout << "- brak zwyciezcy: \t" << tie << endl << endl;
8.   system("pause");
9.   return 0;
10. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Używając zamieszczonego kodu źródłowego uzyskaj dane, które pokażą ile gier się skończyło zwycięstwem lub remisem dokładnie w i-tym ruchu tj. bez uwzględniania zwycięstw z ruchów poprzednich.

• Kod źródłowy Zadanie 1