Prolog Tic-Tac-Toe

My college class on Artificial Intelligence required me to write a program to play Tic-Tac-Toe.
This implementation is written using the Prolog language.
It employs the Minimax algorithm to find the best move.
The program runs inside any Java-enabled browser using the JLog Applet.

Instructions
Enter your answers in the Input Box.
Always end your input with a period before submitting it. (Not my idea, Prolog requires it)

 

Here is the source code (markup produced by the excellent CopySourceAsHtml Visual Studio 2005 Add-In):

    1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    2 %%% CST 381 -– Artificial Intelligence
    3 %%% Robert Pinchbeck
    4 %%% Final Project 
    5 %%% Due December 20, 2006
    6 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    7 
    8 
    9 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   10 %%% A Prolog Implementation of Tic-Tac-Toe
   11 %%% using the minimax strategy
   12 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   13 
   14 /*
   15 
   16 The following conventions are used in this program...
   17 
   18 Single letter variables represent:
   19 
   20 L - a list
   21 N - a number, position, index, or counter
   22 V - a value (usually a string)
   23 A - an accumulator
   24 H - the head of a list
   25 T - the tail of a list
   26 
   27 For this implementation, these single letter variables represent:
   28 
   29 P - a player number (1 or 2)
   30 B - the board (a 9 item list representing a 3x3 matrix)
   31     each "square" on the board can contain one of 3 values: x ,o, or e (for empty)
   32 S - the number of a square on the board (1 - 9)
   33 M - a mark on a square (x or o)
   34 E - the mark used to represent an empty square ('e').
   35 U - the utility value of a board position
   36 R - a random number
   37 D - the depth of the minimax search tree (for outputting utility values, and for debugging)
   38 
   39 Variables with a numeric suffix represent a variable based on another variable.
   40 (e.g. B2 is a new board position based on B)
   41 
   42 For predicates, the last variable is usually the "return" value.
   43 (e.g. opponent_mark(P,M), returns the opposing mark in variable M)
   44 
   45 Predicates with a numeric suffix represent a "nested" predicate.
   46 
   47 e.g. myrule2(...) is meant to be called from myrule(...) 
   48      and myrule3(...) is meant to be called from myrule2(...)
   49 
   50 
   51 There are only two assertions that are used in this implementation
   52 
   53 asserta( board(B) ) - the current board 
   54 asserta( player(P, Type) ) - indicates which players are human/computer.
   55 
   56 */
   57 
   58 
   59 
   60 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   61 %%%     FACTS
   62 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   63 
   64 next_player(1, 2).      %%% determines the next player after the given player
   65 next_player(2, 1).
   66 
   67 inverse_mark('x', 'o'). %%% determines the opposite of the given mark
   68 inverse_mark('o', 'x').
   69 
   70 player_mark(1, 'x').    %%% the mark for the given player
   71 player_mark(2, 'o').    
   72 
   73 opponent_mark(1, 'o').  %%% shorthand for the inverse mark of the given player
   74 opponent_mark(2, 'x').
   75 
   76 blank_mark('e').        %%% the mark used in an empty square
   77 
   78 maximizing('x').        %%% the player playing x is always trying to maximize the utility of the board position
   79 minimizing('o').        %%% the player playing o is always trying to minimize the utility of the board position
   80 
   81 corner_square(1, 1).    %%% map corner squares to board squares
   82 corner_square(2, 3).
   83 corner_square(3, 7).
   84 corner_square(4, 9).
   85 
   86 
   87 
   88 
   89 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   90 %%%     MAIN PROGRAM
   91 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   92 
   93 
   94 run :-
   95     hello,          %%% Display welcome message, initialize game
   96 
   97     play(1),        %%% Play the game starting with player 1
   98 
   99     goodbye         %%% Display end of game message
  100     .
  101 
  102 run :-
  103     goodbye
  104     .
  105 
  106 
  107 hello :-
  108     initialize,
  109 %    cls,
  110     nl,
  111     nl,
  112     nl,
  113     write('Welcome to Tic-Tac-Toe.'),
  114     read_players,
  115     output_players
  116     .
  117 
  118 initialize :-
  119     random_seed,          %%% use current time to initialize random number generator
  120     blank_mark(E),
  121     asserta( board([E,E,E, E,E,E, E,E,E]) )  %%% create a blank board
  122     .
  123 
  124 goodbye :-
  125     board(B),
  126     nl,
  127     nl,
  128     write('Game over: '),
  129     output_winner(B),
  130     retract(board(_)),
  131     retract(player(_,_)),
  132     read_play_again(V), !,
  133     (V == 'Y' ; V == 'y'), 
  134     !,
  135     run
  136     .
  137 
  138 read_play_again(V) :-
  139     nl,
  140     nl,
  141     write('Play again (Y/N)? '),
  142     read(V),
  143     (V == 'y' ; V == 'Y' ; V == 'n' ; V == 'N'), !
  144     .
  145 
  146 read_play_again(V) :-
  147     nl,
  148     nl,
  149     write('Please enter Y or N.'),
  150     read_play_again(V)
  151     .
  152 
  153 
  154 read_players :-
  155     nl,
  156     nl,
  157     write('Number of human players? '),
  158     read(N),
  159     set_players(N)
  160     .
  161 
  162 set_players(0) :- 
  163     asserta( player(1, computer) ),
  164     asserta( player(2, computer) ), !
  165     .
  166 
  167 set_players(1) :-
  168     nl,
  169     write('Is human playing X or O (X moves first)? '),
  170     read(M),
  171     human_playing(M), !
  172     .
  173 
  174 set_players(2) :- 
  175     asserta( player(1, human) ),
  176     asserta( player(2, human) ), !
  177     .
  178 
  179 set_players(N) :-
  180     nl,
  181     write('Please enter 0, 1, or 2.'),
  182     read_players
  183     .
  184 
  185 
  186 human_playing(M) :- 
  187     (M == 'x' ; M == 'X'),
  188     asserta( player(1, human) ),
  189     asserta( player(2, computer) ), !
  190     .
  191 
  192 human_playing(M) :- 
  193     (M == 'o' ; M == 'O'),
  194     asserta( player(1, computer) ),
  195     asserta( player(2, human) ), !
  196     .
  197 
  198 human_playing(M) :-
  199     nl,
  200     write('Please enter X or O.'),
  201     set_players(1)
  202     .
  203 
  204 
  205 play(P) :-
  206     board(B), !,
  207     output_board(B), !,
  208     not(game_over(P, B)), !,
  209     make_move(P, B), !,
  210     next_player(P, P2), !,
  211     play(P2), !
  212     .
  213 
  214 
  215 %.......................................
  216 % square
  217 %.......................................
  218 % The mark in a square(N) corresponds to an item in a list, as follows:
  219 
  220 square([M,_,_,_,_,_,_,_,_],1,M).
  221 square([_,M,_,_,_,_,_,_,_],2,M).
  222 square([_,_,M,_,_,_,_,_,_],3,M).
  223 square([_,_,_,M,_,_,_,_,_],4,M).
  224 square([_,_,_,_,M,_,_,_,_],5,M).
  225 square([_,_,_,_,_,M,_,_,_],6,M).
  226 square([_,_,_,_,_,_,M,_,_],7,M).
  227 square([_,_,_,_,_,_,_,M,_],8,M).
  228 square([_,_,_,_,_,_,_,_,M],9,M).
  229 
  230 
  231 %.......................................
  232 % win
  233 %.......................................
  234 % Players win by having their mark in one of the following square configurations:
  235 %
  236 
  237 win([M,M,M, _,_,_, _,_,_],M).
  238 win([_,_,_, M,M,M, _,_,_],M).
  239 win([_,_,_, _,_,_, M,M,M],M).
  240 win([M,_,_, M,_,_, M,_,_],M).
  241 win([_,M,_, _,M,_, _,M,_],M).
  242 win([_,_,M, _,_,M, _,_,M],M).
  243 win([M,_,_, _,M,_, _,_,M],M).
  244 win([_,_,M, _,M,_, M,_,_],M).
  245 
  246 
  247 %.......................................
  248 % move
  249 %.......................................
  250 % applies a move on the given board
  251 % (put mark M in square S on board B and return the resulting board B2)
  252 %
  253 
  254 move(B,S,M,B2) :-
  255     set_item(B,S,M,B2)
  256     .
  257 
  258 
  259 %.......................................
  260 % game_over
  261 %.......................................
  262 % determines when the game is over
  263 %
  264 game_over(P, B) :-
  265     game_over2(P, B)
  266     .
  267 
  268 game_over2(P, B) :-
  269     opponent_mark(P, M),   %%% game is over if opponent wins
  270     win(B, M)
  271     .
  272 
  273 game_over2(P, B) :-
  274     blank_mark(E),
  275     not(square(B,S,E))     %%% game is over if opponent wins
  276     .
  277 
  278 
  279 %.......................................
  280 % make_move
  281 %.......................................
  282 % requests next move from human/computer, 
  283 % then applies that move to the given board
  284 %
  285 
  286 make_move(P, B) :-
  287     player(P, Type),
  288 
  289     make_move2(Type, P, B, B2),
  290 
  291     retract( board(_) ),
  292     asserta( board(B2) )
  293     .
  294 
  295 make_move2(human, P, B, B2) :-
  296     nl,
  297     nl,
  298     write('Player '),
  299     write(P),
  300     write(' move? '),
  301     read(S),
  302 
  303     blank_mark(E),
  304     square(B, S, E),
  305     player_mark(P, M),
  306     move(B, S, M, B2), !
  307     .
  308 
  309 make_move2(human, P, B, B2) :-
  310     nl,
  311     nl,
  312     write('Please select a numbered square.'),
  313     make_move2(human,P,B,B2)
  314     .
  315 
  316 make_move2(computer, P, B, B2) :-
  317     nl,
  318     nl,
  319     write('Computer is thinking about next move...'),
  320     player_mark(P, M),
  321     minimax(0, B, M, S, U),
  322     move(B,S,M,B2),
  323 
  324     nl,
  325     nl,
  326     write('Computer places '),
  327     write(M),
  328     write(' in square '),
  329     write(S),
  330     write('.')
  331     .
  332 
  333 
  334 %.......................................
  335 % moves
  336 %.......................................
  337 % retrieves a list of available moves (empty squares) on a board.
  338 %
  339 
  340 moves(B,L) :-
  341     not(win(B,x)),                %%% if either player already won, then there are no available moves
  342     not(win(B,o)),
  343     blank_mark(E),
  344     findall(N, square(B,N,E), L), 
  345     L \= []
  346     .
  347 
  348 
  349 %.......................................
  350 % utility
  351 %.......................................
  352 % determines the value of a given board position
  353 %
  354 
  355 utility(B,U) :-
  356     win(B,'x'),
  357     U = 1, 
  358     !
  359     .
  360 
  361 utility(B,U) :-
  362     win(B,'o'),
  363     U = (-1), 
  364     !
  365     .
  366 
  367 utility(B,U) :-
  368     U = 0
  369     .
  370 
  371 
  372 %.......................................
  373 % minimax
  374 %.......................................
  375 % The minimax algorithm always assumes an optimal opponent.
  376 % For tic-tac-toe, optimal play will always result in a tie, so the algorithm is effectively playing not-to-lose.
  377 
  378 % For the opening move against an optimal player, the best minimax can ever hope for is a tie.
  379 % So, technically speaking, any opening move is acceptable.
  380 % Save the user the trouble of waiting  for the computer to search the entire minimax tree 
  381 % by simply selecting a random square.
  382 
  383 minimax(D,[E,E,E, E,E,E, E,E,E],M,S,U) :-   
  384     blank_mark(E),
  385     random_int_1n(9,S),
  386     !
  387     .
  388 
  389 minimax(D,B,M,S,U) :-
  390     D2 is D + 1,
  391     moves(B,L),          %%% get the list of available moves
  392     !,
  393     best(D2,B,M,L,S,U),  %%% recursively determine the best available move
  394     !
  395     .
  396 
  397 % if there are no more available moves, 
  398 % then the minimax value is the utility of the given board position
  399 
  400 minimax(D,B,M,S,U) :-
  401     utility(B,U)      
  402     .
  403 
  404 
  405 %.......................................
  406 % best
  407 %.......................................
  408 % determines the best move in a given list of moves by recursively calling minimax
  409 %
  410 
  411 % if there is only one move left in the list...
  412 
  413 best(D,B,M,[S1],S,U) :-
  414     move(B,S1,M,B2),        %%% apply that move to the board,
  415     inverse_mark(M,M2), 
  416     !,  
  417     minimax(D,B2,M2,_S,U),  %%% then recursively search for the utility value of that move.
  418     S = S1, !,
  419     output_value(D,S,U),
  420     !
  421     .
  422 
  423 % if there is more than one move in the list...
  424 
  425 best(D,B,M,[S1|T],S,U) :-
  426     move(B,S1,M,B2),             %%% apply the first move (in the list) to the board,
  427     inverse_mark(M,M2), 
  428     !,
  429     minimax(D,B2,M2,_S,U1),      %%% recursively search for the utility value of that move,
  430     best(D,B,M,T,S2,U2),         %%% determine the best move of the remaining moves,
  431     output_value(D,S1,U1),      
  432     better(D,M,S1,U1,S2,U2,S,U)  %%% and choose the better of the two moves (based on their respective utility values)
  433     .
  434 
  435 
  436 %.......................................
  437 % better
  438 %.......................................
  439 % returns the better of two moves based on their respective utility values.
  440 %
  441 % if both moves have the same utility value, then one is chosen at random.
  442 
  443 better(D,M,S1,U1,S2,U2,     S,U) :-
  444     maximizing(M),                     %%% if the player is maximizing
  445     U1 > U2,                           %%% then greater is better.
  446     S = S1,
  447     U = U1,
  448     !
  449     .
  450 
  451 better(D,M,S1,U1,S2,U2,     S,U) :-
  452     minimizing(M),                     %%% if the player is minimizing,
  453     U1 < U2,                           %%% then lesser is better.
  454     S = S1,
  455     U = U1, 
  456     !
  457     .
  458 
  459 better(D,M,S1,U1,S2,U2,     S,U) :-
  460     U1 == U2,                          %%% if moves have equal utility,
  461     random_int_1n(10,R),               %%% then pick one of them at random
  462     better2(D,R,M,S1,U1,S2,U2,S,U),    
  463     !
  464     .
  465 
  466 better(D,M,S1,U1,S2,U2,     S,U) :-        %%% otherwise, second move is better
  467     S = S2,
  468     U = U2,
  469     !
  470     .
  471 
  472 
  473 %.......................................
  474 % better2
  475 %.......................................
  476 % randomly selects two squares of the same utility value given a single probability
  477 %
  478 
  479 better2(D,R,M,S1,U1,S2,U2,  S,U) :-
  480     R < 6,
  481     S = S1,
  482     U = U1, 
  483     !
  484     .
  485 
  486 better2(D,R,M,S1,U1,S2,U2,  S,U) :-
  487     S = S2,
  488     U = U2,
  489     !
  490     .
  491 
  492 
  493 
  494 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  495 %%% OUTPUT
  496 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  497 
  498 output_players :- 
  499     nl,
  500     player(1, V1),
  501     write('Player 1 is '),   %%% either human or computer
  502     write(V1),
  503 
  504     nl,
  505     player(2, V2),
  506     write('Player 2 is '),   %%% either human or computer
  507     write(V2), 
  508     !
  509     .
  510 
  511 
  512 output_winner(B) :-
  513     win(B,x),
  514     write('X wins.'),
  515     !
  516     .
  517 
  518 output_winner(B) :-
  519     win(B,o),
  520     write('O wins.'),
  521     !
  522     .
  523 
  524 output_winner(B) :-
  525     write('No winner.')
  526     .
  527 
  528 
  529 output_board(B) :-
  530     nl,
  531     nl,
  532     output_square(B,1),
  533     write('|'),
  534     output_square(B,2),
  535     write('|'),
  536     output_square(B,3),
  537     nl,
  538     write('-----------'),
  539     nl,
  540     output_square(B,4),
  541     write('|'),
  542     output_square(B,5),
  543     write('|'),
  544     output_square(B,6),
  545     nl,
  546     write('-----------'),
  547     nl,
  548     output_square(B,7),
  549     write('|'),
  550     output_square(B,8),
  551     write('|'),
  552     output_square(B,9), !
  553     .
  554 
  555 output_board :-
  556     board(B),
  557     output_board(B), !
  558     .
  559 
  560 output_square(B,S) :-
  561     square(B,S,M),
  562     write(' '), 
  563     output_square2(S,M),  
  564     write(' '), !
  565     .
  566 
  567 output_square2(S, E) :- 
  568     blank_mark(E),
  569     write(S), !              %%% if square is empty, output the square number
  570     .
  571 
  572 output_square2(S, M) :- 
  573     write(M), !              %%% if square is marked, output the mark
  574     .
  575 
  576 output_value(D,S,U) :-
  577     D == 1,
  578     nl,
  579     write('Square '),
  580     write(S),
  581     write(', utility: '),
  582     write(U), !
  583     .
  584 
  585 output_value(D,S,U) :- 
  586     true
  587     .
  588 
  589 
  590 
  591 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  592 %%% PSEUDO-RANDOM NUMBERS 
  593 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  594 
  595 %.......................................
  596 % random_seed
  597 %.......................................
  598 % Initialize the random number generator...
  599 % If no seed is provided, use the current time
  600 %
  601 
  602 random_seed :-
  603     random_seed(_),
  604     !
  605     .
  606 
  607 random_seed(N) :-
  608     nonvar(N),
  609 % Do nothing, SWI-Prolog does not support seeding the random number generator
  610     !
  611     .
  612 
  613 random_seed(N) :-
  614     var(N),
  615 % Do nothing, SWI-Prolog does not support seeding the random number generator
  616     !
  617     .
  618 
  619 /*****************************************
  620  OTHER COMPILER SUPPORT
  621 ******************************************
  622 
  623 arity_prolog___random_seed(N) :-
  624     nonvar(N),
  625     randomize(N), 
  626     !
  627     .
  628 
  629 arity_prolog___random_seed(N) :-
  630     var(N),
  631     time(time(Hour,Minute,Second,Tick)),
  632     N is ( (Hour+1) * (Minute+1) * (Second+1) * (Tick+1)),
  633     randomize(N), 
  634     !
  635     .
  636 
  637 ******************************************/
  638 
  639 
  640 
  641 %.......................................
  642 % random_int_1n
  643 %.......................................
  644 % returns a random integer from 1 to N
  645 %
  646 random_int_1n(N, V) :-
  647     V is random(N) + 1,
  648     !
  649     .
  650 
  651 /*****************************************
  652  OTHER COMPILER SUPPORT
  653 ******************************************
  654 
  655 arity_prolog___random_int_1n(N, V) :-
  656     R is random,
  657     V2 is (R * N) - 0.5,           
  658     float_text(V2,V3,fixed(0)),
  659     int_text(V4,V3),
  660     V is V4 + 1,
  661     !
  662     .
  663 
  664 ******************************************/
  665 
  666 
  667 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  668 %%% LIST PROCESSING
  669 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  670 
  671 member([V|T], V).
  672 member([_|T], V) :- member(T,V).
  673 
  674 append([], L, L).
  675 append([H|T1], L2, [H|T3]) :- append(T1, L2, T3).
  676 
  677 
  678 %.......................................
  679 % set_item
  680 %.......................................
  681 % Given a list L, replace the item at position N with V
  682 % return the new list in list L2
  683 %
  684 
  685 set_item(L, N, V, L2) :-
  686     set_item2(L, N, V, 1, L2)
  687         .
  688 
  689 set_item2( [], N, V, A, L2) :- 
  690     N == -1, 
  691     L2 = []
  692     .
  693 
  694 set_item2( [_|T1], N, V, A, [V|T2] ) :- 
  695     A = N,
  696     A1 is N + 1,
  697     set_item2( T1, -1, V, A1, T2 )
  698     .
  699 
  700 set_item2( [H|T1], N, V, A, [H|T2] ) :- 
  701     A1 is A + 1, 
  702     set_item2( T1, N, V, A1, T2 )
  703     .
  704 
  705 
  706 %.......................................
  707 % get_item
  708 %.......................................
  709 % Given a list L, retrieve the item at position N and return it as value V
  710 %
  711 
  712 get_item(L, N, V) :-
  713     get_item2(L, N, 1, V)
  714     .
  715 
  716 get_item2( [], _N, _A, V) :- 
  717     V = [], !,
  718     fail
  719         .
  720 
  721 get_item2( [H|_T], N, A, V) :- 
  722     A = N,
  723     V = H
  724     .
  725 
  726 get_item2( [_|T], N, A, V) :-
  727     A1 is A + 1,
  728     get_item2( T, N, A1, V)
  729     .
  730 
  731 
  732 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  733 %%% End of program
  734 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Copyright (C) 2006-2009 by Robert Pinchbeck
All Rights Reserved