algorithm - Tic Tac Toe MiniMax 方案

Question

我正在尝试用中级学生语言制作一款类似于 Scheme 的 Tic Tac Toe 游戏。如果可能的话，我想让它使用我定义的数据类型来工作，但如果需要的话会改变。在我下面的代码中，我制作了一些功能，这些功能让我接近我想要的地方:

• potential-moves，列出每一个可能的下一步行动
• game-over?，它告诉我是否有玩家在井字棋盘中选择了中奖号码(空格)

请注意，我设计这款井字游戏的方式是使用“选择 3 个数字(1 到 9 之间)加起来等于 15”的方法 - 我愿意改变这一点。

我只是迷路了，我不确定下一步该做什么。我想要的是让我的主要 minimax 函数返回下一步，如果轮到计算机，则将分数最小化，如果轮到玩家，则将分数最大化。

(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

评估董事会

Minimax 的主要部分是对棋盘的深度评估。我的意思是找出如果两位玩家都发挥完美的话谁会获胜。

如果游戏结束(因为玩家连成三盘或棋盘已满)，很容易算出谁是赢家。否则算法会尝试所有可能的移动并评估结果棋盘，然后选择最佳结果。

这是计算机评估算法的草图。给定一个棋盘(假设轮到计算机了)，如果计算机获胜则返回 -1，如果玩家获胜(或已经获胜)则返回 1，如果游戏以平局结束则返回 0。

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

注意事项:

• 重要的是首先检查玩家是否赢了，然后才检查棋盘是否已满。这不是问题中的 evaluate 函数所做的。原因是玩家的最后一步可能会填满棋盘并同时完成一行，在这种情况下他们仍然赢了。
• 没有必要检查计算机是否在给定的棋盘上连续三个，因为它是最后轮到玩家的。

计算player_evaluation的算法非常相似。它在轮到玩家的时候拿一个棋盘，如果计算机赢(或已经赢)则返回 -1，如果玩家赢则返回 1，如果游戏以平局结束则返回 0。

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

如果我们知道玩家会采取什么行动，我们只需考虑该行动即可。然而，没有办法告诉他们会选择哪一个，因此尝试了所有可能的 Action ，并假设玩家会选择最好的一个。

这两个函数非常相似，因此将它们组合成一个 minimax 函数是有意义的。

选择最佳着法

在上一节中，我描述了如何对棋盘进行深入评估并确定谁将获胜。然而，计算机还需要知道哪一步会导致最好的结果。

要获取该信息，computer_evaluate 函数应返回最佳分数和导致该分数的移动。

potential-moves 的实现在compmoves 的开头插入最新的着法，因此很容易找到与潜在棋盘相对应的着法。例如，如果最小化玩家评估的棋盘是 (make-board 'player '(5 9 3 1) '(2 4 8 6) '(7))，计算机是 5。

您可能想要编写一个函数 find-min-by，它接受一个评分函数和一个元素列表，并返回包含最低分数的元素及其分数的对。例如，

(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

---

有很多关于 Minimax 算法的优秀资源，所以如果您遇到困难，请看一看。