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