Algorytm gry Kółko i krzy\yk strona 1 dla uczniów
_____________________________________________
GRA PLANSZOWA KÓAKO 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 CZAOWIEKA. 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 CZAOWIEK 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-CZAOWIEK, 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-CZAOWIEK, 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 -
Wyszukiwarka
Podobne podstrony:
borland cpp builder cw1
borland cpp builder cw5
borland cpp builder cw10
borland cpp builder cw8
borland cpp builder cw3
borland cpp builder cw9
borland cpp builder cw2
borland cpp builder
borland cpp builder cw12
borland cpp builder cw4
borland cpp builder cw6
borland cpp builder cw7
borland cpp builder cw13
algorytm Kruskala Borland C
SQL access in Borland C Builder
więcej podobnych podstron