borland_cpp_builder_cw11_algorytm.pdf

Algorytm gry Kółko i krzyŜyk – strona 1 – dla uczniów

_____________________________________________

GRA PLANSZOWA – KÓŁ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ądź zremisować.

Algorytm 1:

Krok 1. Wybór pola przez CZŁ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. Sprawdź czy ze stanu planszy wynika, Ŝe CZŁOWIEK wygrał – algorytm nr 2 – jeśli

tak to wyświetl odpowiedni komunikat i zakończ algorytm.

Krok 4. Sprawdź 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. Sprawdź 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. Sprawdź 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. Przejdź 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-CZŁ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;

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-CZŁ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<mmx)) or ((gracz=KOMPUTER) and

(m>mmx)))

then mmx:= m;

end;

minimax:=mmx;

end;

- 4 -

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: