Tic Tac Toe MiniMax in Scheme
I am trying to make a Tic Tac Toe game in intermediate student language that is similar to Scheme. If possible, I would like it to work using datatypes that I have defined, but will change as needed. In my code below, I have implemented a series of functions that bring me closer to where I want:
- potential-moves, which lists all possible next steps
- game-over? which tells me if any player has selected winning numbers (spaces) on the tic tac toe board
Just a head, as I designed this game with tic tac toe, was using the "pick 3 numbers (between 1 and 9) that add up to 15" method - I'm willing to change that.
I'm just lost and I'm not sure what to do next. I want my main minimax function to return the next step, which minimizes the score if it flips to the computer, and maximizes the score if the player turns.
(define-struct board [turn compmoves playermoves remaining])
; A Board is a (make-game symbol [List-of Number] [List-of Number] [List-of Number])
; interpretation -> who turn is it, which spaces have been played by computer,
; which spaces have been played by the player, and
; which spaces remain
;Winning combinations (order doesn't matter,
;and this is reflected in the 'game-over?' function
(define winr1 '(8 1 6))
(define winr2 '(3 5 7))
(define winr3 '(4 9 2))
(define winc1 '(8 3 4))
(define winc2 '(1 5 9))
(define winc3 '(6 7 2))
(define wind1 '(8 5 2))
(define wind2 '(4 5 6))
(define a-win (list winr1 winr1 winr3 winc1 winc2 winc3 wind1 wind2))
(define BOARD0 (make-board 'player '(9 3 1) '(4 8 6) '(2 5 7)))
(define BOARD1 (make-board 'player '(8 6 5 9) '(1 3 7 4 2) '()))
(define BOARD2 (make-board 'player '(4 2 5 8) '(1 9 6) '(3 7)))
;Board -> Number
;evaluates a game tree
;NOT SURE WHAT TO DO HERE
#;(define (minimax board)
(cond
[(game-over? board) (evaluate board)]
[else minimax ?]))
;(check-expect (minimax BOARD1) 0)
;(check-expect (minimax BOARD2) -1)
;Board -> [List-of Board]
;returns a list of potential boards
(define (potential-moves board)
(local (;Number -> [List-of Number]
;takes a referenced nummber in a list
;and adds it to another list
(define (add-move n)
(cond
[(player-turn? board)(cons (list-ref (board-remaining board) n)
(board-playermoves board))]
[else (cons (list-ref (board-remaining board) n)
(board-compmoves board))]))
;Number [List-of Number] -> [List-of Number]
;returns a list without the nth term
(define (extract n xs)
(cond
[(= n 0)(rest xs)]
[else (cons (first xs) (extract (sub1 n) (rest xs)))]))
)
(build-list (length (board-remaining board))
(λ (i) (make-board (next-player (board-turn board))
(if (not (player-turn? board))
(add-move i)
(board-compmoves board))
(if (player-turn? board)
(add-move i)
(board-playermoves board))
(extract i (board-remaining board)))))))
;Symbol -> Symbol
;changes the turn
(define (next-player s)
(if (symbol=? s 'player)
'computer
'player))
(check-expect (next-player 'player) 'computer)
(check-expect (next-player 'computer) 'player)
;Board -> Number
;evaluates the board
(define (evaluate board)
(cond
[(empty? (board-remaining board)) 0]
[(player-turn? board) -1]
[else 1]))
(check-expect (evaluate BOARD1) 0)
(check-expect (evaluate BOARD2) -1)
;Board -> Boolean
;the game is over if
; - there are no more moves remaining,
; - the player has a winning combination, or
; - the computer has a winning combination
(define (game-over? board)
(or (empty? (board-remaining board))
(ormap (λ (win) (in-moves? win (board-compmoves board))) a-win)
(ormap (λ (win) (in-moves? win (board-playermoves board))) a-win)))
(check-expect (game-over? BOARD1) true)
(check-expect (game-over? BOARD2) true)
;[List-of Number] [List-of Number] -> Boolean
;are the values from the first list in the second, in any order?
(define (in-moves? combo moves)
(andmap (λ (number) (member? number moves)) combo))
(check-expect (in-moves? '(4 5 6) '(4 1 8 6 5 3 2)) true)
;Board -> Boolean
;determines if it the player turn
(define (player-turn? board)
(symbol=? 'player (board-turn board)))
(check-expect (player-turn? BOARD1) true)
;Board -> Boolean
;determines if it the computer turn
(define (computer-turn? board)
(symbol=? 'computer (board-turn board)))
(check-expect (computer-turn? BOARD2) false)
source to share
Fee evaluation
The main part of Minimax is in-depth board evaluation. By that I mean figuring out who wins if both players play great.
If the game is over (because the player has three in a row or the board is full), then it is easy to determine who is the winner. Otherwise, the algorithm tries all possible moves and evaluates the resulting fee and then chooses the best result.
Here is a sketch of a computerized evaluation algorithm. Given the board (assuming it is a computer turnover), it returns -1 if the computer wins, 1 if the player wins (or has already won), or 0 if the game ends in a draw.
function computer_evaluate(board):
if player has three in a row:
return 1 # player won
if there are no more moves:
return 0 # draw
for each board in possible moves:
calculate player_evaluate(new board)
return best (i.e. minimum) of player evaluations
Notes:
- It is important to first check if the player has won, and only then check if the board is full. This is not what the function
evaluate
in the question does . The reason is that the player's final move can fill the board and end the row at the same time, in which case they won anyway. - It is not necessary to check if the computer has three lines in the given board, since the last one was played by the turntable.
The calculation algorithm is player_evaluation
very similar. It takes the board the player is turning on and returns -1 if the computer wins (or has already won), 1 if the player wins, or 0 if the game ends in a draw.
function player_evaluate(board):
if computer has three in a row:
return -1 # computer won
if there are no more moves:
return 0 # draw
for each board in possible moves:
calculate computer_evaluate(new board)
return best (i.e. maximum) of computer evaluations
If we knew what step the player would take, we only need to consider this move. However, it is impossible to tell which one they will choose, so all possible actions will be checked and it is assumed that the player will choose the best one.
These two functions are so similar that it makes sense to combine them into one function minimax
.
Choosing the best move
In the previous section, I described how to perform a deep board assessment and determine who will win. However, the computer must also know which step leads to the best result.
To get this information, the function computer_evaluate
must return both the best result and the move that leads to that result.
The implementation potential-moves
inserts the last step at the beginning compmoves
, so it's easy to find the move that matches the potential board. For example, if a board that minimizes a player's rating is (make-board 'player '(5 9 3 1) '(2 4 8 6) '(7))
, the best way for a computer is 5
.
You might want to write a function find-min-by
that takes a scoring function and a list of items and returns a pair containing the item with the lowest score and its score. For example,
(define (demo-score elem) (- (% remainder 3) 1)) ; returns -1, 0, or +1
(find-min-by demo-score '(1234 69 100 101))
; => (69, -1), since (demo-score 69) = -1
There are many excellent resources on the Minimax algorithm, so if you get stuck take a look.
source to share