Tic-Tac-Toe game with prolog

Tic-Tac-Toe game with prolog

Reference: https://www.cpp.edu/~jrfisher/www/prolog_tutorial/5_3.html

To work this ttt game with prolog and Java GUI – you may do this assignment by yourself or in a team of 2 persons. Your task is to make this tttab (Dr. Fisher’s ttt with minimax alpha-beta) game to be a bit more challenging and generalized.

You may let prolog program to do all (including ttt output and playing with two computer-players), to do away with Java program. If you are comfortable with Javascript (with HTML and/or CSS, without Java program) then this would be an option for you or your team.

Assignment3

Part1 – 40%

Part2 – 40%

Part3 – 20%

For demo, up to -10% penalty, if not done.

And there will be up to -10% penalty for any missing, incomplete, or poor documentation and/or submission.

Assignment4

Part4 – 40%

Part5 – 40%

Part6 – 20%

For demo, up to -10% penalty, if not done.

And there will be up to -10% penalty for any missing, incomplete, or poor documentation and/or submission.

Part7 – bonus 10% (or more depending on the quality of the work).

Part1. Task #1.

To make ttt 3×3 game to be computer against computer.

You may use the same prolog program to be duplicated (one for computer1 and the other for computer2 to play each other) as they both use minimax alpha-beta strategy. That is, very tough contender to each other. (The Java program calls each player to get the move one after the other.)

Note. Create a folder named: ttt1 (to place all the programs and the output file (log of program run), etc. here to be uploaded in a zip file (with other folders or files for this assignment).

Name your program: ttt1 (to run, and name the program source file name to be: ttt1.pl, ttt1ab.pl, ttt1.java, ttt1-out.txt, etc.).

Part1. Task #2.

To make ttt2 game (computer by computer) to be run M times where M would be 1, 10, 100, 1000. Also provide a timer to take each move in S seconds (a pause time for a human to observe the game play) where S can be 0.1 to 1 second. If S is 0 then it runs as fast as it can.

Note. Create a folder named: ttt2 (to place all the programs and the output file (log of program run), etc. here to be uploaded in a zip file (with other folders or files for this assignment).

Name your program: ttt2 (to run, and name the program source file name to be: ttt2.pl, ttt2ab.pl, ttt2.java, ttt2-out.txt, etc.).

Provide the summary of each game: who wins how many times (and in per cent).

Hint for Part1 #1.

Note that the Java program runs Player1 (human) and GUI where Prolog program runs Player2 (computer) being called by Java program for the next move. Essentially the Prolog program for Player1 should be same (or almost same) as the code for Player2. That is, you may simply copy the Prolog program to be Player1 to called by Java program for Player1. One thing to change is the port number so that Java starts both Player1 and Player2 prolog programs as clients to be connected to Java program (a server listening to two ports – one for Player1 and the other for Player2). Otherwise, your code will confuse the Java program on which player is which player. Also note that the prolog code has minimax alpha-beta code that you need to review and understand.

Part2. Task #1.

To make ttt game to be NxN ttt game where N is 4. A player who gets first its 3 tokens in a line (row, column, diagonal) wins the game.

Note. Create a folder named: ttt4x4 (to place all the programs and the output file (log of program run), etc. here to be uploaded in a zip file (with other folders or files for this assignment).

Name your program: ttt4x4 (to run, and name the program source file name to be: ttt4x4.pl, ttt4x4ab.pl, ttt4x4.java, ttt4x4-out.txt, etc.).

Part2. Task #2.

To make ttt game to be NxN ttt game where N is 3 to 6. A player who gets first its 3 tokens in a line (row, column, diagonal) wins the game. For GUI, please provide a button (option-button or radial-button to select the size N of ttt board) or similar to facilitate this extension.

Note. Create a folder named: tttNxN (to place all the programs and the output file (log of program run), etc. here to be uploaded in a zip file (with other folders or files for this assignment).

Name your program: tttNxN (to run, and name the program source file name to be: tttNxN.pl, tttNxNab.pl, tttNxN.java, tttNxN-out.txt, etc.).

Part3. Task #1.

To make ttt 3×3 game to be computer against computer, with a block.

The board will place a block (where you may use the “*” or “+” to mark the cell) on the board to show up on a cell, preventing one’s move for this cell for one player ready to select one’s choice of cell. This is one-time blocking and to be cleared out for next player. That is, the cell is blocked for this player for this move/time only. Then the block will be cleared for the next player and the board will select a cell to be blocked for the next player. A block will prevent the selected cell to be selected as a choice. After the move of the player, the block disappears. The board will select one cell for a block from one of the cells (or choices) of the player to get any cell which could result in three in a line for the player.

The board will find and select one of the best cells for the blocking (for example, using alpha-beta pruning). Further the board will decide to block this player or not using a fair coin (with a chance of 0.5) to block this player or not for this time.

Note. Create a folder named: ttt3 (to place all the programs and the output file (log of program run), etc. here to be uploaded in a zip file (with other folders or files for this assignment).

Name your program: ttt3 (to run, and name the program source file name to be: ttt3.pl, ttt3ab.pl, ttt3.java, ttt3-out.txt, etc.).

Part3. Task #2.

To make ttt3 game (computer by computer) to be run M times where M would be 1, 10, 100, 1000. Also provide a timer to take each move in S seconds (a pause time for a human to observe the game play) where S can be 0.1 to 1 second. If S is 0 then it runs as fast as it can.

If running more than one-time, then your output is the summary of all the runs (for example, who wins and how many times, etc.).

Note. Create a folder named: ttt3M (to place all the programs and the output file (log of program run), etc. here to be uploaded in a zip file (with other folders or files for this assignment).

Name your program: ttt3M (to run, and name the program source file name to be: ttt2M.pl, ttt3Mab.pl, ttt3M.java, ttt3M-out.txt, etc.).

Provide the summary of each game: who wins how many times (and in per cent).

Part4.

To make ttt game (computer by computer) to integrate what you have done in Part1-3.

That is, ttt can play: NxN board, M times with blocking one cell by the board (one-time block).

Provide Java GUI to have the needed buttons to select each option to be tried.

Note. Create a folder named: ttt4 (to place all the programs and the output file (log of program run), etc. here to be uploaded in a zip file (with other folders or files for this assignment).

Name your program: ttt4 (to run, and name the program source file name to be: ttt4.pl, ttt4ab.pl, ttt4.java, ttt4-out.txt, etc.).

Provide the summary of each game: who wins how many times (and in per cent).

Part5

To make ttt game (computer by computer of Part4 Task#1) to have non-zero sum game.

Each player has initially N*N*10 tokens where N is the size of the board NxN.

For each game, each player bets 10 tokens. For each move, each player adds 1 tokens to continue. At the end of the game, the winner takes all the tokens at stake for this case. One player in the middle of a game may yield (give up to declare one’s loss) to terminate a game and the other player is the winner to get all the tokens at stake for this game case.

Provide Java GUI to provide any initial setting and/or the display of game results (for example, each player’s tokens and tokens in the betting pot of the current game).

Note. Create a folder named: ttt5 (to place all the programs and the output file (log of program run), etc. here to be uploaded in a zip file (with other folders or files for this assignment).

Name your program: ttt5 (to run, and name the program source file name to be: ttt5.pl, ttt5ab.pl, ttt5.java, ttt5-out.txt, etc.).

Provide GUI (e.g., the summary of each game: who wins how many times and in per cent).

Part6. Project Documentation

Finally prepare for this game project in word document (template will be provided) to be submitted: (1) project document, (2) technical document, and (3) a zip file containing all the program related work (source code, run-log, screen-shots, etc.).

Note. Create a folder named: ttt6doc (to place all the programs and the output file (log of program run), etc. here to be uploaded in a zip file (with other folders or files for this assignment).

Bonus. Part7

To make ttt game to have X players (X more than 2) for NxN board with M times run. You may represent Player1 with “1” for a cell (and Player 2 with “2”, etc.).

Note. Create a folder named: ttt7 (to place all the programs and the output file (log of program run), etc. here to be uploaded in a zip file (with other folders or files for this assignment).

Name your program: ttt7 (to run, and name the program source file name to be: ttt7.pl, ttt7ab.pl, ttt7.java, ttt7-out.txt, etc.).

Provide GUI (e.g., the summary of each game: who wins how many times and in per cent).

Week08 Activity Lab – do the following exercise to run Tic-Tac-Toe (Prolog and Java)

Source: Prolog Tutorial by Dr. J. R. Fisher

————————————

First, run the TicTacToe.jar file (which will run the prolog prog to be communicated via socket).

    Check the pdf file (Prolog Fisher – first run jar file for ttt.pdf) first to run jar file and to set the paths.

Submit a word document that you read the program and run the ttt program.

Note. (Mac Users or) If you have some difficulty here (for the path name of swi prolog program), you select a file in the finder and press command-option-c the path name is copied. This method also puts the filename on the end of the path. (2) Or you may type the path name without “Macintosh HD” as Mac is BSD Unix (for its absolute path name to the swi prolog). A few alternatives could be: (1) to use CS OpenLab desktops with swi prolog and java installed, or (2) do the lab together with someone who can do this part. 
————————————-

    5. Search in Prolog

5.1 The A* algorithm in Prolog

5.2 The 8-puzzle

5.3 αβ search in Prolog

https://www.cpp.edu/~jrfisher/www/prolog_tutorial/contents.html#5

5.3 α&beta search in Prolog, tic tac toe example

Source:     https://www.cpp.edu/~jrfisher/www/prolog_tutorial/contents.html#5

This section adapts the α&beta search framework in The Art of Prolog, by L. Sterling and E. Shapiro (1986) for playing the game of tic tac toe (noughts and crosses). One purpose is to study that framework by testing the adaptation to the TicTacToe game. Another intended purpose is to have a Prolog tic tac toe expert agent that can play against the GUI interface developed in Section 8.4.

representing the tic tac toe board in Prolog

To represent the tictactoe board we use a Prolog list. The empty board, before play starts is

_|_|_

_|_|_ ~ [_Z1,_Z2,_Z3,_Z4,_Z5,_Z6,_Z7,_Z8,_Z9]

_|_|_ | 1st row | 2nd row | third row |

After playing two moves each, here is another board …

o|_|_

o|x|x ~ [o,_Z2,_Z3,o,x,x,_Z7,_Z8,_Z9]

_|_|_

The reason for this somewhat obscure representation is so as to avoid having to process a list representation for the board. Instead, a player marks the board by binding a free variable.

:- 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)).

For example, after this code is loaded, consider the following goal …

?- board(B),mark(o,B,X,Y).

B = [o, _G286, _G289, _G292, _G295, _G298, _G301, _G304, _G307] X = 1 Y = 1 ;

B = [_G283, o, _G289, _G292, _G295, _G298, _G301, _G304, _G307] X = 2 Y = 1 ;

B = [_G283, _G286, o, _G292, _G295, _G298, _G301, _G304, _G307] X = 3 Y = 1 ;

B = [_G283, _G286, _G289, o, _G295, _G298, _G301, _G304, _G307] X = 1 Y = 2 ;

B = [_G283, _G286, _G289, _G292, o, _G298, _G301, _G304, _G307] X = 2 Y = 2 ;

B = [_G283, _G286, _G289, _G292, _G295, o, _G301, _G304, _G307] X = 3 Y = 2 ;

B = [_G283, _G286, _G289, _G292, _G295, _G298, o, _G304, _G307] X = 1 Y = 3 ;

B = [_G283, _G286, _G289, _G292, _G295, _G298, _G301, o, _G307] X = 2 Y = 3 ;

B = [_G283, _G286, _G289, _G292, _G295, _G298, _G301, _G304, o] X = 3 Y = 3 ;

No

This illustrates that all the moves can be be generated by backtracking on the mark clauses. Now, let’s first record an xin the center and then generate all possible subsequent moves for o …

?- record(x,1,1), board(B), findall((X,Y),mark(o,B,X,Y),Moves).

B = [x, _G370, _G373, _G376, _G379, _G382, _G385, _G388, _G391]

X = _G186

Y = _G187

Moves = [ (2, 1), (3, 1), (1, 2), (2, 2), (3, 2), (1, 3), (2, 3), (3, 3)]

Yes

?- board(B).

B = [x, _G234, _G237, _G240, _G243, _G246, _G249, _G252, _G255]

Yes

Notice carefully that record does in fact record (assert) a move, but that mark simply finds all possible moves(without actually recording them).

We need an evaluation function that measures how good a board is for a player. We use the well known one that measures the difference between the open lines of play for each player,

value(Board) = (# open lines for o – # open lines for x)

Larger values favor o, smaller values favor x. Our champion is o (computer) whose algorithms below will search to maximixe a move’s value. The algoritms assume that x would search to minimize value. A winning board for o has value 100, a winning board for x has value -100.

%%%%%

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

For example,

?- value([_X,o,o,_Y,o,x,x,_Z,x],V).

V = 0

The reader should try several example boards, and also compute the value by inspection.

adapting αβ search for tic tac toe

The αβ search algorithm looks ahead in order to calculate what move will be best for a player. The algorithm maximizes the value for o, and minimizes the value for x. Here is the basic code framework …

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

To test the code from the Prolog command line, we add a few instructions …

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%% 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).

Now, consider the following interactions …

?- s. % show the board

# # #

# # #

# # #

Yes

?- h(2,1). % Human marks x at 2,1 (not best)

# x #

# # #

# # #

Yes

?- c. % computer thinks, moves to 2,2

# x #

# o #

# # #

Yes

?- h(1,1). % Human moves to 1,1

x x #

# o #

# # #

Yes

?- c. % computer’s move. SEE ANALYSIS BELOW

x x o

# o #

# # #

… etc.

… a cat’s game.

The Prolog program has been designed so that the state of the tic tac toe board is stored after each board, rather than a continuing program that alternately interacts with the players. The reason for this design choice is that we will connect the Prolog tic tac toe player up with a Java GUI in Section 8.4. The Java program will also store the state of the current board. In this way, Prolog and Java will merely have to communicate with each other by telling the other player what the move is: a pair of numbers X,Y.

Let us look at what happens when Prolog computes the last move shown in the game above. The following diagram graphically illustrates what happens for o’s choices other than the first possible (and critically best) move. All of the moves are expanded in the order generated by the program. The second possible move [x,x,_,o,o,_,_,_,_] gives x the opportunity to choose her win [x,x,x,o,o,_,_,_,_]. Our maximizer, o, will not tolerate this and searches no further. The α-cutoff is the red dashed edge from the root to the second tier choice: Notice that cuttoff is called by evaluate_and_choose, which can thus truncate the possibities! The backed-up value Alpha == 0 was obtained from the leftmost search: The best that o can be guarateed from the ist move.


Fig. 5.3

The αβ algorithm brings much more power to bear than is be actually needed to play tic tac toe.

The real advantage that αβ search brings to a more complex game derives from its ability to cutoff the search tree for search which looks ahead by many more moves. Sterling and Shapiro (1986) provide an example for the game of Kalah. The complexity of Kalah takes better advantage of αβ search, and so too can other more complicated games.

It is possible that future versions of the Prolog Tutorial will study more complex games.

The reference Principles of Artificial Intelligence by Nilsson (1980) has a nice discussion of αβ search, and uses tic tac toe as a motivating example.

Prolog Code for tic tac toe discussed in this section.
Prolog Tutorial Contents

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% Prolog TicTacToe alpha-beta expert

%% Design to play against human (Java GUI)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% The empty Tac Tac Toe board

%% Z1 Z2 Z3

%% Z4 Z5 Z6 ~ [Z1,Z2,Z3,Z4,Z5,Z6,Z7,Z8,Z9]

%% Z7 Z8 Z9

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- dynamic board/1.

init:-

retractall(board(_)),

assert(board([_Z1,_Z2,_Z3,_Z4,_Z5,_Z6,_Z7,_Z8,_Z9])).

:- init.

%%%%%

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

%%%%%

%% Move

%%%%%

move(P,(1,1),[X1|R],[P|R]) :- var(X1).

move(P,(2,1),[X1,X2|R],[X1,P|R]) :- var(X2).

move(P,(3,1),[X1,X2,X3|R],[X1,X2,P|R]) :- var(X3).

move(P,(1,2),[X1,X2,X3,X4|R],[X1,X2,X3,P|R]) :- var(X4).

move(P,(2,2),[X1,X2,X3,X4,X5|R],[X1,X2,X3,X4,P|R]) :- var(X5).

move(P,(3,2),[X1,X2,X3,X4,X5,X6|R],[X1,X2,X3,X4,X5,P|R]) :- var(X6).

move(P,(1,3),[X1,X2,X3,X4,X5,X6,X7|R],[X1,X2,X3,X4,X5,X6,P|R]) :- var(X7).

move(P,(2,3),[X1,X2,X3,X4,X5,X6,X7,X8|R],[X1,X2,X3,X4,X5,X6,X7,P|R]) :- var(X8).

move(P,(3,3),[X1,X2,X3,X4,X5,X6,X7,X8,X9|R],[X1,X2,X3,X4,X5,X6,X7,X8,P|R]) :- var(X9).

%%%%%

%% Record a move: record(+,+,+).

%%%%%

record(Player,X,Y) :-

retract(board(B)),

mark(Player,B,X,Y),

assert(board(B)).

%%%%%

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% using minimax procedure with alpha-beta cutoff.

% Computer (o) searches for best tic tac toe move,

% Human player is x.

% Adapted from L. Sterling and E. Shapiro, The Art of Prolog, MIT Press, 1986.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- assert(lookahead(2)).

:- dynamic spy/0. % debug calls to alpha_beta

:- assert(spy). % Comment out stop spy.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

search(Position,Depth,(Move,Value)) :-

alpha_beta(o,Depth,Position,-100,100,Move,Value).

alpha_beta(Player,0,Position,_Alpha,_Beta,_NoMove,Value) :-

value(Position,Value),

spy(Player,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).

spy(Player,Position,Value) :-

spy, !,

write(Player),

write(‘ ‘),

write(Position),

write(‘ ‘),

writeln(Value).

spy(_,_,_). % do nothing

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%% 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),

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%% Play tic tac toe with the Java GUI

%%% using port 54321.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

connect(Port) :-

tcp_socket(Socket),

gethostname(Host), % local host

tcp_connect(Socket,Host:Port),

tcp_open_socket(Socket,INs,OUTs),

assert(connectedReadStream(INs)),

assert(connectedWriteStream(OUTs)).

:- connect(54321). % Comment out for testing

ttt :-

connectedReadStream(IStream),

read(IStream,(X,Y)),

record(x,X,Y),

board(B),

alpha_beta(o,2,B,-200,200,(U,V),_Value),

record(o,U,V),

connectedWriteStream(OStream),

write(OStream,(U,V)),

nl(OStream), flush_output(OStream),

ttt.

:- ttt. % Comment out for testing

// Java code for GUI, Player1 (human) and to call Player2 (computer)

import java.awt.* ;

import java.awt.event.* ;

import java.io.* ;

import java.net.* ;

import javax.swing.* ;

import javax.swing.border.* ;

public class TicTacToe extends JFrame

implements ActionListener {

JButton b11,b21,b31,

b12,b22,b32,

b13,b23,b33 ;

boolean myturn ;

BufferedReader br ;

BufferedWriter bw ;

Thread connection ;

Process prologProcess ;

String prolog ;

String ttt ;

/**

* Create a tic tac toe game,

* prolog is the prolog command (e.g. “/opt/local/bin/swipl”).

* ttt is the locator for ttt.pl (e.g. “/javalib/TicTacToe/ttt.pl”).

*/

public TicTacToe(String prolog, String ttt) {

this.prolog = prolog ;

this.ttt = ttt ;

b11 = new JButton(“”) ;

b21 = new JButton(“”) ;

b31 = new JButton(“”) ;

b12 = new JButton(“”) ;

b22 = new JButton(“”) ;

b32 = new JButton(“”) ;

b13 = new JButton(“”) ;

b23 = new JButton(“”) ;

b33 = new JButton(“”) ;

b11.setActionCommand(“(1,1).”) ; // prolog reads pair term

b21.setActionCommand(“(2,1).”) ;

b31.setActionCommand(“(3,1).”) ;

b12.setActionCommand(“(1,2).”) ;

b22.setActionCommand(“(2,2).”) ;

b32.setActionCommand(“(3,2).”) ;

b13.setActionCommand(“(1,3).”) ;

b23.setActionCommand(“(2,3).”) ;

b33.setActionCommand(“(3,3).”) ;

Font f = new Font(“monospaced”,Font.PLAIN,64) ;

b11.setFont(f) ;

b21.setFont(f) ;

b31.setFont(f) ;

b12.setFont(f) ;

b22.setFont(f) ;

b32.setFont(f) ;

b13.setFont(f) ;

b23.setFont(f) ;

b33.setFont(f) ;

b11.addActionListener(this) ;

b21.addActionListener(this) ;

b31.addActionListener(this) ;

b12.addActionListener(this) ;

b22.addActionListener(this) ;

b32.addActionListener(this) ;

b13.addActionListener(this) ;

b23.addActionListener(this) ;

b33.addActionListener(this) ;

JPanel panel = new JPanel() ;

panel.setLayout(new GridLayout(3,3)) ;

panel.add(b11) ;

panel.add(b21) ;

panel.add(b31) ;

panel.add(b12) ;

panel.add(b22) ;

panel.add(b32) ;

panel.add(b13) ;

panel.add(b23) ;

panel.add(b33) ;

//this.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE) ;

this.setTitle(“Tic Tac Toe”) ;

Border panelborder = BorderFactory.createLoweredBevelBorder() ;

panel.setBorder(panelborder) ;

this.getContentPane().add(panel) ;

this.setSize(300,300) ;

this.setLocation(900,300) ;

this.myturn = true ;

Connector connector = new Connector(54321) ;

connector.start() ;

Socket sock ;

try {

sock = new Socket(“127.0.0.1”,54321) ;

br = new BufferedReader(new InputStreamReader(sock.getInputStream())) ;

bw = new BufferedWriter(new OutputStreamWriter(sock.getOutputStream())) ;

} catch(Exception x) { System.out.println(x) ; }

connection = new Thread() {

public void run() {

while(true) {

try{

String s = br.readLine() ;

computer_move(s) ;

} catch(Exception xx) { System.out.println(xx) ; }

}

}

} ;

connection.start() ;

Thread shows = new Thread() {

public void run() {

setVisible(true) ;

}

} ;

EventQueue.invokeLater(shows);

// Start the prolog player

try {

prologProcess =

Runtime.getRuntime().exec(prolog + ” -f ” + ttt) ;

} catch(Exception xx) {System.out.println(xx) ; }

// On closing, kill the prolog process first and then exit

this.addWindowListener(new WindowAdapter() {

public void windowClosing(WindowEvent w) {

if (prologProcess != null) prologProcess.destroy() ;

System.exit(0) ;

}

}) ;

}

// /opt/local/bin/swipl /javalib/TicTacToe/ttt.pl

public static void main(String[] args) {

String prolog = “/opt/local/bin/swipl” ;

String ttt = “/javalib/TicTacToe/ttt.pl” ;

boolean noargs = true ;

try {

prolog = args[0] ;

ttt = args[1] ;

noargs = false ;

}

catch (Exception xx) {

System.out.println(“usage: java TicTactoe <where prolog> <where ttt>”) ;

}

if (noargs) {

Object[] message = new Object[4] ;

message[0] = new Label(” prolog command”) ;

message[1] = new JTextField(prolog) ;

message[2] = new Label(” where ttt.pl “) ;

message[3] = new JTextField(ttt) ;

try {

int I = JOptionPane.showConfirmDialog(null,message,”Where are Prolog and ttt.pl? “,JOptionPane.OK_CANCEL_OPTION) ;

if (I == 2 | I == 1) System.exit(0) ;

System.out.println(I) ;

new TicTacToe(((JTextField)message[1]).getText().trim(),((JTextField)message[3]).getText().trim()) ;

} catch(Exception yy) {}

}

else

new TicTacToe(prolog,ttt) ;

}

void computer_move(String s) { // ” x ## y ‘

String[] c = s.split(“,”) ;

int x = Integer.parseInt(c[0].trim()),

y = Integer.parseInt(c[1].trim()) ;

//System.out.println(x+”,”+y) ;

if (x == 1) {

if (y == 1) b11.setText(“O”) ;

else if (y == 2) b12.setText(“O”) ;

else if (y == 3) b13.setText(“O”) ;

}

else if (x == 2) {

if (y == 1) b21.setText(“O”) ;

else if (y == 2) b22.setText(“O”) ;

else if (y == 3) b23.setText(“O”) ;

}

else if (x == 3) {

if (y == 1) b31.setText(“O”) ;

else if (y == 2) b32.setText(“O”) ;

else if (y == 3) b33.setText(“O”) ;

}

if (winner()) connection.stop() ;

else myturn = true ;

}

/**

* Java player

*/

public void actionPerformed(ActionEvent act) {

if (!myturn) return ; // otherwise

String s = ((JButton)act.getSource()).getText() ;

if (!s.equals(“”)) return ;

((JButton)(act.getSource())).setText(“X”) ;

try {

bw.write(act.getActionCommand() + “\n”) ;

bw.flush() ;

} catch(Exception xx) { System.out.println(xx) ; }

myturn = false ;

if (winner()) connection.stop() ;

}

/**

* Do we have a winner?

*/

boolean winner() {

return line(b11,b21,b31) ||

line(b12,b22,b32) ||

line(b13,b23,b33) ||

line(b11,b12,b13) ||

line(b21,b22,b23) ||

line(b31,b32,b33) ||

line(b11,b22,b33) ||

line(b13,b22,b31) ;

}

/**

* Are three buttons marked with same player?

* If, so color the line and return true.

*/

boolean line(JButton b, JButton c, JButton d) {

if (!b.getText().equals(“”) &&b.getText().equals(c.getText()) &&

c.getText().equals(d.getText())) {

if (b.getText().equals(“O”)) {

b.setBackground(Color.red) ;

c.setBackground(Color.red) ;

d.setBackground(Color.red) ;

}

else {

b.setBackground(Color.green) ;

c.setBackground(Color.green) ;

d.setBackground(Color.green) ;

}

return true ;

} else return false;

}

}

/*

If Java player closes GUI, then Prolog process is terminated. Java process monitors “win” status of both players, signals a win,and closes the connector and prolog player. Prolog justs plays given position. Write all of this up; it is interesting.

*/

Leave a Reply

Your email address will not be published. Required fields are marked *