% Prolog tic-tac-toe versus an ai that tries to choose % good moves by looking several turns ahead. % The human player is X, the AI is O. % A single game can be invoked using the prolog query % start. % Multiple games can be invoked using the prolog query % start(N). % If multiple games are played, player X goes first % in the first game, then the players alternate who % goes first from one game to the next. % The game state is represented using a six part list % [Board, State, XScore, OScore, Turn, Moves] % - Board is the current game board % - State is one of 'playing, winX, winO, draw' % - XScore and OScore are the players' scores, % each win scores 1 for the winner, 0 for the loser % (draws leave the score unchanged) % - Turn records whose turn it is, plyrX or plyrO % - Moves records the list of moves taken so far % by which positions were taken each turn, % e.g. [1,5,...] indicates % X took position 1 then O took position 5 % ============================================================================= % OVERALL CONTROL % ============================================================================= % start(NumGames) % =============== % play NumGames games, default 0 start :- playGame(0, 0, plyrX, _). start(N) :- integer(N), N > 0, NewN is N - 1, playGame(0, 0, plyrX, GameResult), quitOrPlay(GameResult, NewN, plyrX). quitOrPlay(GameResult, N, WhoStarts) :- N > 0, NewN is N - 1, write('*****'), write(N), write(' game(s) to go!'), write('*****'), nl, write('.'), nl, sleep(1), write('.'), nl, sleep(1), write('.'), nl, sleep(1), nl, getScore(GameResult, XScore, OScore), switchPlayer(WhoStarts, OtherPlyr), playGame(XScore, OScore, OtherPlyr, NewResult), quitOrPlay(NewResult, NewN, OtherPlyr). quitOrPlay(_,0,_). % ============================================================================= % SINGLE GAME CONTROL % ============================================================================= % playGame(XScore, OScore, FinalState) % ==================================== % plays one game playGame(XScore, OScore, WhoStarts, FinalState) :- initGame(GameState, XScore, OScore, WhoStarts), !, playTurn(GameState, FinalState), !, displayFinalResult(FinalState), !. % initGame(GameState, XScore, OScore) % =================================== % game setup initGame([ % initialize the board [empty, empty, empty, empty, empty, empty, empty, empty, empty ], XScore, OScore, % XScore, OScore at the start of this game playing, % initial state WhoStarts, % who gets the first turn [] ], % moves list is initially empty XScore, OScore, WhoStarts ) :- % displayRules. % display the game rules on screen % playTurn(GameState, FinalState) % =============================== % playing a turn involves current player picking their move % then applying the results % GameState is the state coming into the turn, % FinalState is the end-of-game state that is eventually returned playTurn(GameState, FinalState) :- drawBoard(GameState), % display the current board drawInfo(GameState), % display the score and whose turn it is pickMove(GameState, Move), % current player picks a valid board position !, applyMove(GameState, Move, NewState), % create the revised board % check if the game is over, % if so update the winner, otherwise play another turn. checkResults(NewState, FinalState). % checkResults(NewState, FinalState) % ==================================== % check the newly created state to see if it is an end state, % (i.e. either a win for X/O or a tie) % if so return the final game state % otherwise continue playing, % eventually getting the final state back % check if the game is over because X has won checkResults([Board, XScore, OScore, playing, Plyr, Moves], [Board, NewX, OScore, winX, Plyr, Moves]) :- winner(Board, plyrX), NewX is XScore + 1. % check if the game is over because O has won checkResults([Board, XScore, OScore, playing, Plyr, Moves], [Board, XScore, NewO, winO, Plyr, Moves]) :- winner(Board, plyrO), NewO is OScore + 1. % check if the game is over because board is full checkResults([Board, XScore, OScore, playing, Plyr, Moves], [Board, XScore, OScore, draw, Plyr, Moves]) :- tieGame(Board). % otherwise the game isn't over, % so let the other player take their next turn checkResults(GameState, FinalState) :- switchPlayer(GameState, NewState), playTurn(NewState, FinalState). % winner(Board, Player) % ===================== % Based on the current board, % see if the specified player has won % see if the specified player has won winner([A, A, A, _, _, _, _, _, _], Player) :- A == Player. winner([_, _, _, A, A, A, _, _, _], Player) :- A == Player. winner([_, _, _, _, _, _, A, A, A], Player) :- A == Player. winner([A, _, _, A, _, _, A, _, _], Player) :- A == Player. winner([A, _, _, _, A, _, _, _, A], Player) :- A == Player. winner([_, A, _, _, A, _, _, A, _], Player) :- A == Player. winner([_, _, A, _, _, A, _, _, A], Player) :- A == Player. winner([_, _, A, _, A, _, A, _, _], Player) :- A == Player. % tieGame(Board) % ============== % see if the game board is full, i.e. the empty symbol is no % longer on the board. Assumes we have already checked % to make sure the game has not been won tieGame(Board) :- frequency(Board, empty, Count), !, Count < 1. % switchPlayer(OldState, NewState) % ================================ % switching players simply alternates the current turn % between plyrX and plyrO switchPlayer([Board, XScore, OScore, State, plyrX, Moves], [Board, XScore, OScore, State, plyrO, Moves]). switchPlayer([Board, XScore, OScore, State, plyrO, Moves], [Board, XScore, OScore, State, plyrX, Moves]). % switchPlayer(OldPlyr, NewPlyr) % ============================== % switching between players switchPlayer(plyrX, plyrO). switchPlayer(plyrO, plyrX). % applyMove(OldState, Position, NewState) % ======================================= % applying the move involves updating right the board % to create a new game state, % assumes the validity of the move has already been checked applyMove([Board, XScore, OScore, playing, Player, Moves], Position, [NewBoard, XScore, OScore, playing, Player, NewMoves]) :- appendElem(Moves, Position, NewMoves), changeBoard(Board, NewBoard, Position, Player). % getLastMove(GameState, Move) % ============================ % get the last move made to get to the current game state getLastMove([_, _, _, _, _, Moves], Move) :- getLast(Moves, Move). % getCurrPlayer(GameState, Plyr) % ============================ % get the current player from the game state getCurrPlayer([_, _, _, _, Plyr, _], Plyr). % getScore(GameState, XScore, OScore) % =================================== % get the scores from the game state getScore([_, XScore, OScore, _, _, _], XScore, OScore). % changeBoard(OldBoard, NewBoard, Position, Symbol) % ================================================= % change the specified position to the specified player, % assumes validity of the move has already been checked changeBoard(OldBoard, NewBoard, Position, Symbol) :- setElem(OldBoard, NewBoard, Position, Symbol). % pickMove(GameState, Move) % ========================= % given the current game state (which includes whose turn it is) % pick the next move and check it for validity % the human player picks a valid board position, % which is then recorded in Move pickMove([Board, _, _, _, plyrX, _], Move) :- write('Enter a position and a period, e.g. 3.'), nl, write('position: '), read(Move), validMove(Board, Move). % the AI uses minimax to determine its move % if an invalid spot is chosen) pickMove([Board, XScore, OScore, State, plyrO, Moves], BestMove) :- write('************************************'), nl, % pick how far ahead minimax should look frequency(Board, empty, Avail), minimaxSearchDepth(Avail, Depth), write('The AI is running minimax, depth: '), write(Depth), nl, minimax([Board, XScore, OScore, State, plyrO, Moves], Depth, BestMove, _), write('The AI chose: '), write(BestMove), nl, write('************************************'), nl, validMove(Board, BestMove). % the validity check for the move failed, % print an error message and pick a new move pickMove(GameState, Move) :- write('Please try again'), nl, pickMove(GameState, Move). % validMove(Board, Move) % ===================== % check if the specified position is valid (1-9 and not taken), % otherwise display an error message validMove(Board, Move) :- integer(Move), 1 =< Move, Move =< 9, notTaken(Move, Board). validMove(_, Move) :- write('Error, invalid move: '), write(Move), nl, fail. % notTaken(Position, Board) % ========================= % ensure a position isn't taken, i.e. the empty % symbol appears in that position in the board notTaken(Pos, Board) :- matches(Board, Pos, empty). % otherPlayer(OldPlayer, NewPlayer) % ================================= % matches opposite players otherPlayer(plyrX, plyrO). otherPlayer(plyrO, plyrX). % calcTurns(Board, Turns) % ======================= % calculate the number of turns that have been taken, % i.e. 9 minus the number of spots still empty calcTurns(Board, Turns) :- frequency(Board, empty, LeftOver), Turns is 9 - LeftOver. % ============================================================================= % DISPLAY HANDLING % ============================================================================= % displayRules % ============ % display the game rules displayRules :- write('Basic tic tac toe, X goes first'), nl. % displayFinalResult(GameState) % ============================ % display the end of game information displayFinalResult([_, XScore, OScore, winX, _, _]) :- write('************************************'), nl, write('Player X won, new score is X: '), write(XScore), write(' O: '), write(OScore), nl, write('************************************'), nl. displayFinalResult([_, XScore, OScore, winO, _, _]) :- write('************************************'), nl, write('Player O won, new score is X: '), write(XScore), write(' O: '), write(OScore), nl, write('************************************'), nl. displayFinalResult([_, XScore, OScore, draw, _, _]) :- write('*************************************'), nl, write('Tie game, current score is X: '), write(XScore), write(', O: '), write(OScore), nl, write('*************************************'), nl. % drawBoard(GameState) % ==================== % display the current board and the numbering of board positions drawBoard([[R11, R12, R13, R21, R22, R23, R31, R32, R33] | _]) :- write('Positions Board'), nl, write(' 1 2 3 '), drawLine(R11, R12, R13), write(' 4 5 6 '), drawLine(R21, R22, R23), write(' 7 8 9 '), drawLine(R31, R32, R33). % drawInfo(GameState) % =================== % display the current score, last move, and whose turn it is drawInfo([_, XScore, OScore, _, Player, Moves]) :- write('X score: '), write(XScore), write(', O Score: '), write(OScore), nl, write('Last move: '), getLast(Moves, Move), write(Move), nl, write('Current player:'), writeSym(Player), nl. % drawLine(SymA, SymB, SymC) % ========================= % draw one row of the board drawLine(A, B, C) :- writeSym(A), writeSym(B), writeSym(C), nl. % writeSym(Sym) % ============= % draw the symbol corresponding to plyrX, plyrO, or empty writeSym(empty) :- write(' - '). writeSym(plyrX) :- write(' X '). writeSym(plyrO) :- write(' O '). % ============================================================================= % GENERAL LIST HANDLING % ============================================================================= % appendElem(OldList, Element, NewList) % ===================================== % append an element to the end of a list, % EXCEPT: will NOT append an empty list as an element appendElem(L, [], L). appendElem([], V, [V]). appendElem([H|T], V, [H|NewT]) :- appendElem(T, V, NewT). % setElem(OldList, NewList, Position, Value) % ========================================== % set the value of the i'th element in a list setElem([_|Tail], [Value|Tail], 1, Value). setElem([Head|Tail], [Head|NewTail], I, Value) :- integer(I), I > 0, NewI is I - 1, setElem(Tail, NewTail, NewI, Value). % frequency(List, Element, Count) % =============================== % count number of times an element appears in a list frequency([], _, 0). frequency([Elem|Tail], Elem, Count) :- frequency(Tail, Elem, C), C1 is C+1, Count = C1. frequency([_|Tail], Elem, Count) :- frequency(Tail, Elem, Count). % matches(List, Position, Value) % ============================== % determine if the i'th element in a list % matches the element provided matches([Elem|_], 1, Elem). matches([_|Tail], I, Elem) :- integer(I), I > 1, NewI is I - 1, matches(Tail, NewI, Elem). % getLast(List, Elem) % =================== % get the last element of a list getLast([], none). getLast([V], V). getLast([_|T], V) :- getLast(T, V). % ============================================================================= % MINIMAX HANDLING % ============================================================================= % minimaxSearchDepth(AvailableSpots, Depth) % ========================================= % base the depth on how many moves are available minimaxSearchDepth(9, 4). % if first move, only go depth 4 minimaxSearchDepth(8, 5). % second move go depth 5 minimaxSearchDepth(7, 6). % third move go depth 6 % otherwise search the entire remaining space minimaxSearchDepth(Avail, Depth) :- Depth is min(Avail, 5). % minimax(CurrentState, DepthToGo, BestMove, MoveValue) % =================================================== % from the current state, % if DepthToGo > 0 % generate all legal next states, if any % if any: % pick the best of all those states, % the move that takes you there, % and the 'value' of that state % otherwise this is a terminal state, % establish its value % 0 is used for BestMove if there is no next move, % otherwise move indicates which position to take next % base case, we've reached our turn limit minimax(CurrState, 0, 0, BestValue) :- % just evaluate the score at our current state evaluateState(CurrState, BestValue). % base case: CurrState is a winner, don't explore this branch further minimax([Board|_], _, 0, Score) :- winner(Board, plyrX), calcTurns(Board, Turns), Score is 300 - Turns. minimax([Board|_], _, 0, Score) :- winner(Board, plyrO), calcTurns(Board, Turns), Score is Turns - 300. % base case: the game has ended in a tie, don't explore further minimax([Board|_], _, 0, 0) :- tieGame(Board). % general case, there are still branches to explore minimax(CurrState, TurnLimit, BestMove, MoveValue) :- % make sure the turn limit is valid integer(TurnLimit), 0 < TurnLimit, % generate the possible next moves based on the which of the % 9 board positions are available generateNextStates(CurrState, NextStates, 9), !, % pick the best of the possibiities generated % (there must be at least one, or the minimax % base cases would have applied previously) pickBest(NextStates, TurnLimit, BestMove, MoveValue). % genNthState(CurrState, NthState, N) % =================================== % if possible, generate the state that would be produced % if the current player took position N on the board genNthState([Board, XScore, OScore, State, Player, Moves], [NewBoard, XScore, OScore, State, NewPlayer, NewMoves], N) :- % make sure N is appropriate integer(N), 0 < N, N < 10, % make sure the spot isn't taken notTaken(N, Board), % take the position, producing the new board setElem(Board, NewBoard, N, Player), % add the move to the move list appendElem(Moves, N, NewMoves), % swap whose turn it will be otherPlayer(Player, NewPlayer), !. % if the above fails then the new state is set to an empty list genNthState(_, [], _). % generateNextStates(CurrState, NextStates, N) % ============================================ % consider the remaining N board positions to generate % a list of potential next states % if N is 0 there are no next states generateNextStates(_, [], 0). % :- write('generate empty state list'), nl. % otherwise try to move using position N on the board, and, % if valid, generate the next state that would produce % and add it to the list % note that genNthState gives [] as the NewState if % position N isn't acceptable, but appendElem ignores % [] if asked to append it to a list generateNextStates(CurrState, StateList, N) :- genNthState(CurrState, NewState, N), NewN is N - 1, generateNextStates(CurrState, OtherStates, NewN), appendElem(OtherStates, NewState, StateList). % evaluateState(GameState, Value) % ============================== % evaluate the current game state % (high scores good for X, low scores good for O % % the order in which the evaluation rules are listed is critical, % as it prioritizes the decision making process % e.g. if it is O's turn and both X and O have two-in-a-row somewhere % O should prioritize winning rather than blocking % base cases, the game has been won or drawn evaluateState([Board, _, _, _, _, _], Value) :- winner(Board, plyrX), calcTurns(Board, Turns), Value is 300 - Turns. evaluateState([Board, _, _, _, _, _], Value) :- winner(Board, plyrO), calcTurns(Board, Turns), Value is Turns - 300. evaluateState([Board, _, _, _, _, _], 0) :- tieGame(Board). % if it is X's turn and X can win % treat it like an X win case 1 turn away, 299-Turns evaluateState([Board, _, _, _, plyrX, _], Value) :- winnable(Board, plyrX, Ways), Ways > 0, calcTurns(Board, Turns), Value is 299 - Turns. % if it is O's turn and O can win % treat it like an O win case 1 turn away, Turns-299 evaluateState([Board, _, _, _, plyrO, _], Value) :- winnable(Board, plyrO, Ways), Ways > 0, calcTurns(Board, Turns), Value is Turns - 299. % if it is X's turn and O can win multiple ways % treat it like an O win case 2 turns away, Turns-298 evaluateState([Board, _, _, _, plyrX, _], Value) :- winnable(Board, plyrO, Ways), Ways > 1, calcTurns(Board, Turns), Value is Turns - 298. % if it is O's turn and X can win multiple ways % treat it like an X win case 2 turns away, 298-Turns evaluateState([Board, _, _, _, plyrO, _], Value) :- winnable(Board, plyrX, Ways), Ways > 1, calcTurns(Board, Turns), Value is 298 - Turns. % the default is to treat the current state as indifferent evaluateState(_, 0). % winnable(Board, Player, Count) % ============================= % counts the number of winning moves the player has % on the current board winnable([R11, R12, R13, R21, R22, R23, R31, R32, R33], Player, Count) :- evalTrio(R11, R12, R13, Player, Row1), evalTrio(R21, R22, R23, Player, Row2), evalTrio(R31, R32, R33, Player, Row3), evalTrio(R11, R21, R31, Player, Col1), evalTrio(R12, R22, R32, Player, Col2), evalTrio(R13, R23, R33, Player, Col3), evalTrio(R11, R22, R33, Player, Dia1), evalTrio(R13, R22, R31, Player, Dia2), Count is (Row1 + Row2 + Row3 + Col1 + Col2 + Col3 + Dia1 + Dia2). % evalTrio(A, B, C, Plyr, Count) % ============================== % Count is 1 if the player owns two of the three spots and the other is empty % Count is 0 otherwise evalTrio(Plyr, Plyr, empty, Plyr, 1). evalTrio(Plyr, empty, Plyr, Plyr, 1). evalTrio(empty, Plyr, Plyr, Plyr, 1). evalTrio(_, _, _, _, 0). % pickBest(StateList, TurnLimit, BestMove, MoveValue) % =================================================== % picks the best of a list of states generated by minimax % rule 1 applies when there is only one state in the list % so the turn limit is irrelevant and there is % only one possible move and value pickBest([GmState1], _, Move, Value) :- % for tic tac toe if there is only one next state then it is % the last move of the game so we could simply evaluate it, % but for more general games there might be other moves % enabled afterwards, so we would have to pursue minimax % further to figure out the end value of this move % e.g. NewLimit is TurnLimit - 1, % minimax(GmState1, NewLimit, NextMove, NextValue). getLastMove(GmState1, Move), evaluateState(GmState1, Value). % general case, pick the better of the head state and the best of the rest pickBest([GmState1 | OtherStates], TurnLimit, BestMove, BestValue) :- % evaluate the head state now via minimax NewLimit is TurnLimit - 1, getLastMove(GmState1, Move1), minimax(GmState1, NewLimit, _, Value1), % get the rest of the states evaluated % (they are at the same turn level as GmState1, so pass the original turn limit) pickBest(OtherStates, TurnLimit, Move2, Value2), % choose the better of the head state and the best of the rest getCurrPlayer(GmState1, CurrPlyr), pickBetterMove(CurrPlyr, Move1, Value1, Move2, Value2, BestMove, BestValue). % pickBetterMove(Plyr, Move1, Value1, Move2, Value2, BetterMove, BetterValue) % ========================================================================= % which of two moves has the better associated value for the current player? % for X's sake high values are good, % for O's sake low values are good % rules 1 and 2 apply when the two moves are equal, % there is a 50% chance of picking each of the two states pickBetterMove(_, Move1, Value1, _, Value1, Move1, Value1) :- random(1,3,N), N < 2. pickBetterMove(_, _, Value2, Move2, Value2, Move2, Value2). % rule 3 applies when GmState1 has the better value for current player X % (reversed since have already swapped 'current player' field) pickBetterMove(plyrX, Move1, Value1, _, Value2, Move1, Value1) :- Value1 < Value2, !. % rule 4 applies when GmState1 has the better value for current player O % (reversed since have already swapped 'current player' field) pickBetterMove(plyrO, Move1, Value1, _, Value2, Move1, Value1) :- Value1 > Value2, !. % apply rule 5 for any other case, GmState2 must be better pickBetterMove(_, _, _, Move2, Value2, Move2, Value2).