Algorytm gry Kółko i krzy\
yk  strona 1  dla uczniów
_____________________________________________
GRA PLANSZOWA  KÓA
KO I KRZYśYK
ALGORYTM
Zało\
enia:
- Plansza 3 x 3 (Liczba pól na planszy: 9)
- Pola numerowane są od 0 do 8 (dla języka C++), albo od 1 do 9 (dla języka Pascal).
- Pierwszy ruch nale\
y do człowieka.
- Cel algorytmu: Algorytm (komputer) nie mo\
e przegrać z człowiekiem,
mo\
e wygrać bądz
zremisować.
Algorytm 1:
Krok 1. Wybór pola przez CZA
OWIEKA. Zapamiętanie nr pola w zmiennej nr_pola.
Krok 2. Zaznacz na planszy pole o numerze nr_pola (na którym człowiek stawia kółeczko).
Krok 3. Sprawdz
czy ze stanu planszy wynika, \
e CZA
OWIEK wygrał  algorytm nr 2  jeśli
tak to wyświetl odpowiedni komunikat i zakończ algorytm.
Krok 4. Sprawdz
czy ze stanu planszy wynika, \
e jest REMIS  algorytm nr 3  jeśli tak to
wyświetl odpowiedni komunikat i zakończ algorytm.
Krok 5. Wyznacz ruch dla KOMPUTERA (zmienna nr_pola)  algorytm nr 4  zaznacz na
planszy pole o numerze nr_pola.
Krok 6. Sprawdz
czy ze stanu planszy wynika, \
e KOMPUTER wygrał  algorytm nr 2  jeśli
tak to wyświetl odpowiedni komunikat i zakończ algorytm.
Krok 7. Sprawdz
czy ze stanu planszy wynika, \
e jest REMIS  algorytm nr 3  jeśli tak to
wyświetl odpowiedni komunikat i zakończ algorytm.
Krok 8. Wyświetl stan planszy.
Krok 9. Przejdz
do kroku 1.
Algorytm 2  WYGRANA(t, g) - (zapisany w notacji języka Pascal):
Dane : t  tablica o rozmiarach 3x3 przechowująca planszę, g  gracz (0-CZA
OWIEK, 1 
KOMPUTER, 2  pole puste)
Wynik: wygrana  typ boolean; true , jeśli wygrywa gracz g.
function wygrana(var t:Tplansza; g:integer):boolean;
var
test: boolean;
i: integer;
begin
test:= false; { Zmienna przyjmuje true, jeśli zawodnik ma trzy figury w
wierszu,
kolumnie lub na przekątnych }
{ Sprawdzamy wiersze }
i:= 1;
while i <= 7 do begin
test:=test or ((t[i]=g) and (t[i+1]=g) and (t[i+2]=g));
i:=i+3;
end;
- 1 -
Algorytm gry Kółko i krzy\
yk  strona 2  dla uczniów
_____________________________________________
{ Sprawdzamy kolumny }
i:=1;
while i <= 3 do begin
test := test or ((t[i]=g) and (t[i+3]=g) and (t[i+6]=g));
i:=i+1;
end;
{ Sprawdzamy przekątną 1-5-9 }
test := test or ((t[1]=g) and (t[5]=g) and (t[9]=g));
{ Sprawdzamy przekątną 3-5-7 }
test:= test or ((t[3]=g) and (t[5]=g) and (t[7]=g));
wygrana:=test;
end;
Algorytm 3  REMIS(t, g) - (zapisany w notacji języka Pascal):
Dane : t  tablica o rozmiarach 3x3 przechowująca planszę
Wynik: remis  typ boolean; true , jeśli jest remis.
function remis(var t:Tplansza):boolean;
var i:integer;
begin
{ Jeśli napotkamy spację, to plansza posiada wolne pola - zwracamy false }
for i:= 1 to 9 do if t[i] = ' ' then begin
remis:=false;
exit;
end;
{ Jesli pętla for zakończyła się normalnie, to na \
adnym polu planszy nie
było spacji.
Mamy do czynienia z remisem - zwracamy true }
remis:=true;
end;
Algorytm 4  KOMPUTER(t) - (zapisany w notacji języka Pascal):
Dane : t  tablica o rozmiarach 3x3 przechowująca planszę
Wynik: komputer  typ integer; nr pola na którym komputer stawia krzy\
yk.
function komputer(var t:Tplansza):integer;
var
ruch, i, m, mmx:integer;
begin
mmx:= -10;
for i:= 1 to 9 do
if t[i]=' ' then begin
t[i]:=KOMPUTER;
m:= minimax(t,KOMPUTER);
t[i]:= ' ';
if m > mmx then begin
mmx:= m;
ruch:= i;
end;
end;
komputer:=ruch;
end;
- 2 -
Algorytm gry Kółko i krzy\
yk  strona 3  dla uczniów
_____________________________________________
Algorytm MINIMAX(t,g) - (zapisany w notacji języka Pascal):
Algorytm rekurencyjny
Dane : t  tablica o rozmiarach 3x3 przechowująca planszę, g  gracz (0-CZA
OWIEK, 1 
KOMPUTER)
Wynik: minimax  typ integer;
function minimax(var t:Tplansza; g:integer):integer;
var
m, mmx:integer;
begin
{ Najpierw sprawdzamy, czy bie\
ący gracz wygrywa na planszy.
Jeśli tak, to zwracamy jego maksymalny wynik }
if wygrana(t,g) then begin
if gracz='X' then minimax:=1 else minimax:=-1;
exit;
end;
{ Następnie sprawdzamy, czy nie ma remisu. Jeśli jest, zwracamy wynik 0 }
if remis(t) then begin
minimax:=0;
exit;
end;
{ Będziemy analizować mo\
liwe posunięcia przeciwnika.
Zmieniamy zatem bie\
ącego gracza na jego przeciwnika }
if g=KOMPUTER then gracz:=CZLOWIEK' else gracz:=KOMPUTER;
{
Algorytm MINIMAX w kolejnych wywołaniach rekurencyjnych naprzemiennie
analizuje
grę gracza oraz jego przeciwnika. Dla gracza oblicza maksimum wyniku gry,
a dla
przeciwnika oblicza minimum. Wartość mmx ustawiamy w zale\
ności od tego,
czyje
ruchy analizujemy:
X - liczymy max, zatem mmx <- -10
O - liczymy min, zatem mmx <- 10
}
if g=CZLOWIEK then mmx:=10 else mmx:=-10;
{
Przeglądamy planszę szukając wolnych pół na ruch gracza. Na wolnym polu
ustawiamy
literkę gracza i wyznaczamy wartość tego ruchu rekurencyjnym wywołaniem
algorytmu MINIMAX. Planszę przywracamy i w zale\
ności kto gra:
X - wyznaczamy maximum
O - wyznaczamy minimum
}
- 3 -
Algorytm gry Kółko i krzy\
yk  strona 4  dla uczniów
_____________________________________________
for i:= 1 to 9 do
if t[i]= ' ' then begin
t[i]:= g;
m:= minimax(t,g);
t[i]:= ' ';
if (((gracz=CZLOWIEK) and (m(m>mmx)))
then mmx:= m;
end;
minimax:=mmx;
end;
- 4 -