[Prolog] Algorytm do kółko i krzyżyk
Garar
Ta wskazowka dotyczy implementacji algorytmu grajacego w znana wszystkim gre kolko i krzyzyk. Oparlem ten algorytm o przeszukiwanie przestrzeni stanow rozgrywki. Przegladane jest cale drzewo gry. Nie dodalem algorytmu ani min-max ani alpha-beta.
Zostalem zainspirowany artykulem Przemyslawa Kobylanskiego "teoria gier".
Ten algroytm jest nie do pokonania:) a i jest to sam algorytm bez interfejsu graficznego badz tekstowego.
Wywolania:
6 ?- primus(p(e, e, e, x, e, e, o, e, e), Ruch).
Ruch = 3 ;
Ruch = 5 ;
Ruch = 8 ;
Ruch = 9 ;
No
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Author: Krystian Kichewko ([email protected])
% Date: 04-06-04
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% plansza oznaczana jest jako 9-cio argumentowy term o funktorze 'p', gdzie
% kolejny argument oznacza kolejne pole: p(1, 2, 3, 4, 5, 6, 7, 8, 9), wyglada
% to na planszy nastepujaco:
% 1|2|3
% -----
% 4|5|6
% -----
% 7|8|9
% Poszczegolne pola moga przyjmowac nastepujace wartosci:
% e - puste pole
% x - krzyzyk (pierwszy gracz[primus])
% o - kolko (drugi gracz[secundus])
% UWAGA: jako ze w tej grze istnieje remis za stan wygrywajacy dla primusa
% przyjalem jego zwyciestwo lub remis, a za stan przegrywajacy dla primusa i
% wygrywajacy dla secundusa przyjalem zwyciestwo secundusa. Jezeli uznasz ze
% remis to tez porazka primusa to nalezy wykomentowac odpowiednie linijki z
% predykatow primus/2 i secundus/2. Zostaly one zaznaczone ponizej.
% Jednakze takie wywolanie w ktorym za stan przegrywajacy dla primusa
% przyjmujemy remis zawsze zawodzi bo kolko i krzyzyk jest gra w ktora z
% odpowiednio grajacym przeciwnikiem NIE DA SIE WYGRAC.
% narysuj_plansze(Plansza) - predykat rysujacy plansze.
narysuj_plansze(p(A, B, C, D, E, F, G, H, I)) :-
writef('\\n\\t%q|%q|%q\\n', [A, B, C]),
writef('\\t-----\\n',[]),
writef('\\t%q|%q|%q\\n', [D, E, F]),
writef('\\t-----\\n',[]),
writef('\\t%q|%q|%q\\n', [G, H, I]).
% linia(Plansza, Pole_1, Pole_2, Pole_3) - predykat ukonkretniajacy
% zmienne Pole_i poprzez wartosci kolejnych linii.
linia(p(A, _, _, B, _, _, C, _, _), A, B, C).
linia(p(_, A, _, _, B, _, _, C, _), A, B, C).
linia(p(_, _, A, _, _, B, _, _, C), A, B, C).
linia(p(A, B, C, _, _, _, _, _, _), A, B, C).
linia(p(_, _, _, A, B, C, _, _, _), A, B, C).
linia(p(_, _, _, _, _, _, A, B, C), A, B, C).
linia(p(A, _, _, _, B, _, _, _, C), A, B, C).
linia(p(_, _, A, _, B, _, C, _, _), A, B, C).
% prim(Plansza) - predykat opisujacy stan wygrywajacy dla gracza pierwszego.
prim(P) :-
linia(P, x, x, x).
% sec(Plansza) - predykat opisujacy stan wygrywajacy dla gracza drugiego.
sec(P) :-
linia(P, o, o, o).
% fin(Plansza) - predykat opisujacy stan koncowy.
fin(P) :-
linia(P, x, x, x),
linia(P, o, o, o).
fin(P) :-
\\+ (linia(P, A, B, C),
pusty(A, B, C)).
% pusty(A, B, C) - predykat sprawdzajacy czy choc jedna zmienna reprezentuje
% puste pole.
pusty(e, _, _).
pusty(_, e, _).
pusty(_, _, e).
% draw(Plansza) - predykat opisujacy remis.
draw(P) :-
\\+ (linia(P, A, B, C),
pusty(A, B, C)),
\\+ prim(P),
\\+ sec(P).
% move(Ruch, Plansza, Nowa_plansza, Zawodnik) - predykat generujacy ruch Ruch
% przy aktualnym stanie planszy Plansza jednoczesnie plansza przechodzi w nowy
% stan Nowa_plansza. Zawodnik opisuje figure jaka gra zawodnik
% (kolko albo krzyzyk).
move(R, S, N, Z) :-
S =.. [F|L],
nth1(R, L, e),
zmien_liste(L, R, Z, L1),
N =.. [F|L1].
% zmien_liste(Lista_1, Indeks, War, Lista_2) - predykat zmieniajacy element o
% indeksie Indeks listy Lista_1 na nowa wartosci War i zwracajacy nowa liste
% w liscie Lista_2.
zmien_liste([_|T], 1, War, [War|T]) :- !.
zmien_liste([X|T], Arg, War, [X|Nowa]) :-
Arg > 1,
Arg1 is Arg-1,
zmien_liste(T, Arg1, War, Nowa).
% primus(Plansza, Ruch) - predykat zwracjacy okreslony Ruch w stanie okreslonym
% Plansza pozwalajacy osiagnac zamierzony efekt. none - oznacza ze nei trzeba
% juz wykonywac ruchu, a ruch jest oznaczony cyfra od 1 do 9 oznaczajaca pole,
% na ktorym nalezy postawic figure. Dla primusa figura ta jest krzyzyk, a dla
% secundusa jest to kolko.
primus(Stan, none) :-
fin(Stan),
!,
% prim(Stan). % linijki do wykomentowania
(prim(Stan) ; draw(Stan)). % patrz UWAGA.
primus(Stan, Ruch) :-
move(Ruch, Stan, Nowy, x),
% narysuj_plansze(Nowy),
\\+ secundus(Nowy, _).
% secundus(Plansza, Ruch) - predykat taki sam jak primus/2, ale dla secundusa
secundus(Stan, none) :-
fin(Stan),
!,
% (sec(Stan) ; draw(Stan)). % linijki do wykomentowania
sec(Stan). % patrz UWAGA.
secundus(Stan, Ruch) :-
move(Ruch, Stan, Nowy, o),
% narysuj_plansze(Nowy),
\\+ primus(Nowy, _).
Niestety nie ma formatowania dla prologu.
Prosze o konstruktywna krytyke.
;d no nie
Wszystko fajnie, ale po raz kolejny muszę przypominać, że w artykułach przestrzegamy używania polskich znaków diakrytycznych.
Troche sie rozjechalo ale robilem to na wieksza szerokosc.