CSCE 625 Homework Assignment #9 due: Tues, 12/1/09 Implement a tic-tac-toe playing algorithm in Prolog. Rules: The board consists of a 3x3 grid. There are two players, call them 0 and 1 (instead of the usual X and O), who alternative turns. A player wins by getting three of their pieces in a row, column, or diagonal. If neither player wins by the time all 9 positions are filled, the game is declared a draw. Here is some sample code to get you started. It represents a board using a list of 3 lists, with the symbols 0, 1, and '-' for empty. The coordinate system X,Y is assumed to be rowXcol, where row and col range over {1,2,3}, with <1,1> representing the upper-left corner. % get(Board,X,Y,Piece) % tells you what piece is in a given position in a given board get(X,1,1,A) :- X = [[A,_,_],[_,_,_],[_,_,_]]. get(X,1,2,B) :- X = [[_,B,_],[_,_,_],[_,_,_]]. get(X,1,3,C) :- X = [[_,_,C],[_,_,_],[_,_,_]]. get(X,2,1,D) :- X = [[_,_,_],[D,_,_],[_,_,_]]. get(X,2,2,E) :- X = [[_,_,_],[_,E,_],[_,_,_]]. get(X,2,3,F) :- X = [[_,_,_],[_,_,F],[_,_,_]]. get(X,3,1,G) :- X = [[_,_,_],[_,_,_],[G,_,_]]. get(X,3,2,H) :- X = [[_,_,_],[_,_,_],[_,H,_]]. get(X,3,3,I) :- X = [[_,_,_],[_,_,_],[_,_,I]]. % update(BoardIn,Piece,X,Y,BoardOut) % computes the result of placing a new piece on the board, i.e. a new board update([[A,B,C],[D,E,F],[G,H,I]],P,1,1,[[P,B,C],[D,E,F],[G,H,I]]) :- A='-'. update([[A,B,C],[D,E,F],[G,H,I]],P,1,2,[[A,P,C],[D,E,F],[G,H,I]]) :- B='-'. update([[A,B,C],[D,E,F],[G,H,I]],P,1,3,[[A,B,P],[D,E,F],[G,H,I]]) :- C='-'. update([[A,B,C],[D,E,F],[G,H,I]],P,2,1,[[A,B,C],[P,E,F],[G,H,I]]) :- D='-'. update([[A,B,C],[D,E,F],[G,H,I]],P,2,2,[[A,B,C],[D,P,F],[G,H,I]]) :- E='-'. update([[A,B,C],[D,E,F],[G,H,I]],P,2,3,[[A,B,C],[D,E,P],[G,H,I]]) :- F='-'. update([[A,B,C],[D,E,F],[G,H,I]],P,3,1,[[A,B,C],[D,E,F],[P,H,I]]) :- G='-'. update([[A,B,C],[D,E,F],[G,H,I]],P,3,2,[[A,B,C],[D,E,F],[G,P,I]]) :- H='-'. update([[A,B,C],[D,E,F],[G,H,I]],P,3,3,[[A,B,C],[D,E,F],[G,H,P]]) :- I='-'. reset :- retractall(board(_)),assert(board([[-,-,-],[-,-,-],[-,-,-]])). show :- board([[A,B,C],[D,E,F],[G,H,I]]), format('~a ~a ~a\n',[A,B,C]), format('~a ~a ~a\n',[D,E,F]), format('~a ~a ~a\n',[G,H,I]). % updates the current state % use 1 or 0 for Piece; use 1-3 for Row and Col; (1,1) is upper-left put(Piece,Row,Col) :- member(Piece,[0,1]),member(Row,[1,2,3]),member(Col,[1,2,3]),board(X), update(X,Piece,Row,Col,Y),retractall(board(_)),assert(board(Y)),show. % calls the user's "move" function to decide what to do make_move(P) :- board(B),move(B,P,X,Y),put(P,X,Y). get() and update() are key utility functions for telling you what piece is in a location or placing a new piece, generating a new board representation. The other functions use assert and retract to manipulate the current state of the game via the predicate board(). 'reset' will set set it to the empty state. 'show' will print it out. put(P,X,Y) will place a new piece on the board, that is, physically update the fact board(). Finally, make_move(P) call's the user's implementation of a predicate "move" to decide what to do, and does it. The user must fill in rules for the "move" predicate, as the decision-making component. Given a board and a piece identifier, move should return the best choice of position for the designated player. The "move" predicate will probably require defining some additional predicates for things like identifying winning boards, good moves, blocking moves, etc. In the end, the additional rules will encode a rule-based "strategy" for tic-tac-toe. (Regardless of who goes first or what position is chosen, it should always be possible to force a draw). Here is an example transcript, where I (1) am playing against the computer (0). That is, I am making my own human decisions about where to place my pieces, using put(1,X,Y), and the computer is using the move(B,P,X,Y) (called during make_move) to decide where to place the 0 pieces. ?- reset. ?- show. - - - - - - - - - ?- put(1,1,2). ?- show. - 1 - - - - - - - ?- make_move(0). - 1 - - 0 - - - - ?- put(1,1,1). ?- show. 1 1 - - 0 - - - - ?- make_move(0). 1 1 0 - 0 - - - - ?- put(1,3,1). ?- show. 1 1 0 - 0 - 1 - -