[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.

3 komentarzy

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.