|
|
pl:prolog:pllib:tictactoe [2019/06/27 15:50] |
pl:prolog:pllib:tictactoe [2019/06/27 15:50] (aktualna) |
| ====== Tictactoe ====== |
| {{tag>game}} |
| ===== Description ===== |
| The TicTacToe game |
| |
| **Source**: PrologTutorial (on-line tutorial) |
| ===== Download ===== |
| Program source code: {{tictactoe.pl}} |
| ===== Listing ===== |
| <code prolog> |
| |
| |
| :- dynamic board/1. |
| :- retractall(board(_)). |
| :- assert(board([_Z1,_Z2,_Z3,_Z4,_Z5,_Z6,_Z7,_Z8,_Z9])). |
| |
| %%%%% |
| %% Generate possible marks on a free spot on the board. |
| %% Use mark(+,+,-X,-Y) to query/generate possible moves (X,Y). |
| %%%%% |
| mark(Player, [X|_],1,1) :- var(X), X=Player. |
| mark(Player, [_,X|_],2,1) :- var(X), X=Player. |
| mark(Player, [_,_,X|_],3,1) :- var(X), X=Player. |
| mark(Player, [_,_,_,X|_],1,2) :- var(X), X=Player. |
| mark(Player, [_,_,_,_,X|_],2,2) :- var(X), X=Player. |
| mark(Player, [_,_,_,_,_,X|_],3,2) :- var(X), X=Player. |
| mark(Player, [_,_,_,_,_,_,X|_],1,3) :- var(X), X=Player. |
| mark(Player, [_,_,_,_,_,_,_,X|_],2,3) :- var(X), X=Player. |
| mark(Player, [_,_,_,_,_,_,_,_,X|_],3,3) :- var(X), X=Player. |
| |
| %%%%% |
| %% Record a move: record(+,+,+). |
| %%%%% |
| record(Player,X,Y) :- |
| retract(board(B)), |
| mark(Player,B,X,Y), |
| assert(board(B)). |
| |
| |
| %%%%% |
| %% Calculate the value of a position, o maximizes, x minimizes. |
| %%%%% |
| value(Board,100) :- win(Board,o), !. |
| value(Board,-100) :- win(Board,x), !. |
| value(Board,E) :- |
| findall(o,open(Board,o),MAX), |
| length(MAX,Emax), % # lines open to o |
| findall(x,open(Board,x),MIN), |
| length(MIN,Emin), % # lines open to x |
| E is Emax - Emin. |
| |
| |
| %%%%% |
| %% A winning line is ALREADY bound to Player. |
| %% win(+Board,+Player) is true or fail. |
| %% e.g., win([P,P,P|_],P). is NOT correct, because could bind |
| %%%%% |
| win([Z1,Z2,Z3|_],P) :- Z1==P, Z2==P, Z3==P. |
| win([_,_,_,Z1,Z2,Z3|_],P) :- Z1==P, Z2==P, Z3==P. |
| win([_,_,_,_,_,_,Z1,Z2,Z3],P) :- Z1==P, Z2==P, Z3==P. |
| win([Z1,_,_,Z2,_,_,Z3,_,_],P) :- Z1==P, Z2==P, Z3==P. |
| win([_,Z1,_,_,Z2,_,_,Z3,_],P) :- Z1==P, Z2==P, Z3==P. |
| win([_,_,Z1,_,_,Z2,_,_,Z3],P) :- Z1==P, Z2==P, Z3==P. |
| win([Z1,_,_,_,Z2,_,_,_,Z3],P) :- Z1==P, Z2==P, Z3==P. |
| win([_,_,Z1,_,Z2,_,Z3,_,_],P) :- Z1==P, Z2==P, Z3==P. |
| |
| %%%%% |
| %% A line is open if each position is either free or equals the Player |
| %%%%% |
| open([Z1,Z2,Z3|_],Player) :- (var(Z1) | Z1 == Player),(var(Z2) | Z2 == Player), (var(Z3) | Z3 == Player). |
| open([_,_,_,Z1,Z2,Z3|_],Player) :- (var(Z1) | Z1 == Player),(var(Z2) | Z2 == Player), (var(Z3) | Z3 == Player). |
| open([_,_,_,_,_,_,Z1,Z2,Z3],Player) :- (var(Z1) | Z1 == Player),(var(Z2) | Z2 == Player), (var(Z3) | Z3 == Player). |
| open([Z1,_,_,Z2,_,_,Z3,_,_],Player) :- (var(Z1) | Z1 == Player),(var(Z2) | Z2 == Player), (var(Z3) | Z3 == Player). |
| open([_,Z1,_,_,Z2,_,_,Z3,_],Player) :- (var(Z1) | Z1 == Player),(var(Z2) | Z2 == Player), (var(Z3) | Z3 == Player). |
| open([_,_,Z1,_,_,Z2,_,_,Z3],Player) :- (var(Z1) | Z1 == Player),(var(Z2) | Z2 == Player), (var(Z3) | Z3 == Player). |
| open([Z1,_,_,_,Z2,_,_,_,Z3],Player) :- (var(Z1) | Z1 == Player),(var(Z2) | Z2 == Player), (var(Z3) | Z3 == Player). |
| open([_,_,Z1,_,Z2,_,Z3,_,_],Player) :- (var(Z1) | Z1 == Player),(var(Z2) | Z2 == Player), (var(Z3) | Z3 == Player). |
| |
| %%%%% |
| %% Calculate the value of a position, o maximizes, x minimizes. |
| %%%%% |
| value(Board,100) :- win(Board,o), !. |
| value(Board,-100) :- win(Board,x), !. |
| value(Board,E) :- |
| findall(o,open(Board,o),MAX), |
| length(MAX,Emax), % # lines open to o |
| findall(x,open(Board,x),MIN), |
| length(MIN,Emin), % # lines open to x |
| E is Emax - Emin. |
| |
| |
| alpha_beta(Player,0,Position,_Alpha,_Beta,_NoMove,Value) :- |
| value(Position,Value). |
| |
| alpha_beta(Player,D,Position,Alpha,Beta,Move,Value) :- |
| D > 0, |
| findall((X,Y),mark(Player,Position,X,Y),Moves), |
| Alpha1 is -Beta, % max/min |
| Beta1 is -Alpha, |
| D1 is D-1, |
| evaluate_and_choose(Player,Moves,Position,D1,Alpha1,Beta1,nil,(Move,Value)). |
| |
| evaluate_and_choose(Player,[Move|Moves],Position,D,Alpha,Beta,Record,BestMove) :- |
| move(Player,Move,Position,Position1), |
| other_player(Player,OtherPlayer), |
| alpha_beta(OtherPlayer,D,Position1,Alpha,Beta,_OtherMove,Value), |
| Value1 is -Value, |
| cutoff(Player,Move,Value1,D,Alpha,Beta,Moves,Position,Record,BestMove). |
| evaluate_and_choose(_Player,[],_Position,_D,Alpha,_Beta,Move,(Move,Alpha)). |
| |
| cutoff(_Player,Move,Value,_D,_Alpha,Beta,_Moves,_Position,_Record,(Move,Value)) :- |
| Value >= Beta, !. |
| cutoff(Player,Move,Value,D,Alpha,Beta,Moves,Position,_Record,BestMove) :- |
| Alpha < Value, Value < Beta, !, |
| evaluate_and_choose(Player,Moves,Position,D,Value,Beta,Move,BestMove). |
| cutoff(Player,_Move,Value,D,Alpha,Beta,Moves,Position,Record,BestMove) :- |
| Value =< Alpha, !, |
| evaluate_and_choose(Player,Moves,Position,D,Alpha,Beta,Record,BestMove). |
| |
| other_player(o,x). |
| other_player(x,o). |
| |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| %%% For testing, use h(+,+) to record human move, |
| %%% supply coordinates. Then call c (computer plays). |
| %%% Use s to show board. |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| h(X,Y) :- record(x,X,Y), showBoard. |
| |
| c :- |
| board(B), |
| alpha_beta(o,2,B,-200,200,(X,Y),_Value), % <=== NOTE |
| record(o,X,Y), showBoard. |
| |
| showBoard :- |
| board([Z1,Z2,Z3,Z4,Z5,Z6,Z7,Z8,Z9]), |
| write(' '),mark(Z1),write(' '),mark(Z2),write(' '),mark(Z3),nl, |
| write(' '),mark(Z4),write(' '),mark(Z5),write(' '),mark(Z6),nl, |
| write(' '),mark(Z7),write(' '),mark(Z8),write(' '),mark(Z9),nl. |
| s :- showBoard. |
| |
| mark(X) :- var(X), write('#'). |
| mark(X) :- \+var(X),write(X). |
| </code> |
| ===== Comments ===== |
| |