Tic Tac Toe MiniMax in Scheme

Question

I'm trying to make a Tic Tac Toe game in Intermediate Student Language, which is similar to Scheme. If possible, I'd like to make it work using the data types I've defined, but will change if necessary. In my code below I've made a number of functions that are getting me close to where I want to:

• potential-moves, which makes a list of every possible next move
• game-over?, which tells me if any player has chosen the winning numbers (spaces) in the tic tac toe board

Just a heads up, the way I designed this tic tac toe game was using the "pick 3 numbers (between 1 and 9) that add up to 15" method - I'm willing to change this.

I'm just lost and I'm not sure what to do next. What I want is for my main minimax function to return the next move that will minimize the score if it's the computer's turn, and maximize the score if it's the player's turn.

(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's 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's the player's turn
(define (player-turn? board)
  (symbol=? 'player (board-turn board)))

(check-expect (player-turn? BOARD1) true)

;Board -> Boolean
;determines if it's the computer's turn
(define (computer-turn? board)
  (symbol=? 'computer (board-turn board)))

(check-expect (computer-turn? BOARD2) false)

Answer 1

Evaluating the Board

The main part of Minimax is deep evaluation of the board. By that I mean finding out who would win if both players play perfectly.

If the game is over (because a player has three in a row or the board is full) it is simple to work out who the winner is. Otherwise the algorithm tries all possible moves and evaluates the resulting board, then picks the best outcome.

Here is a sketch of the computer's evaluation algorithm. Given a board (assuming it is the computer's turn), it returns -1 if the computer will win, 1 if the player will win (or already won), or 0 if the game will end 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 evaluate function in the question does. The reason is that the player's final move may fill the board and complete a row simultaneously, in which case they still won.
• There is no need to check if the computer has three in a row in the given board since it was the player's turn last.

The algorithm for computing player_evaluation very similar. It takes a board where it is the player's turn and returns -1 if the computer will win (or already won), 1 if the player will win, or 0 if the game will end 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 move the player would make we would only have to consider that move. However there is no way to tell which one they'll pick, so all possible moves are tried and it is assumed the player will pick the best one.

These two functions are so similar it makes sense to combine them into one minimax function.

Choosing the Best Move

In the previous section I described how to perform a deep evaluation of the board and determine who will win. However the computer also needs to know which move leads to the best outcome.

To get that information, the function computer_evaluate should return both the best score and the move that leads to that score.

The implementation of potential-moves inserts the latest move at the start of compmoves, so it is easy to find the move that corresponds to a potential board. For example, if the board that minimizes the player's evaluation is (make-board 'player '(5 9 3 1) '(2 4 8 6) '(7)), the best move for the computer is 5.

You may want to write a function find-min-by that takes a scoring function and a list of elements and returns a pair containing the element 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 plenty of excellent resources on the Minimax algorithm, so if you are stuck have a look.