我正在尝试用中级学生语言制作一个 Tic Tac Toe 游戏,类似于 Scheme。如果可能,我想使用我定义的数据类型使其工作,但如有必要会进行更改。在我下面的代码中,我创建了许多使我接近我想要的地方的函数:

  • 潜在移动,它列出了所有可能的下一步移动
  • 游戏结束?,它告诉我是否有玩家选择了井字棋盘中的中奖号码(空格)

  • 提醒一下,我设计这款井字游戏的方式是使用“选择 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)
    

    最佳答案

    评估董事会

    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
    

    如果我们知道玩家会采取什么行动,我们只需要考虑那个行动。但是,无法确定他们会选择哪一个,因此会尝试所有可能的移动,并假设玩家会选择最好的移动。

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

    选择最佳举措

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

    要获得该信息,函数 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 算法有很多优秀的资源,所以如果你被卡住了,可以看看。

    关于algorithm - 井字游戏 MiniMax in Scheme,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/30155180/

    10-11 23:08
    查看更多