3

（注意：这不是 CS 作业）

我已经尝试在 Coffeescript 中实现 minimax 游戏树搜索算法，并继续使用我的算法出错。似乎有两个主要问题：1）算法本身在 alpha-beta 修剪期间似乎没有返回正确的值（显然是更大的问题），以及 2）我的游戏板对象，由 9 个整数组成的数组表示，似乎附加到 DOM，使板的复制并将其作为参数传递给 minimax 搜索函数的递归调用有问题。

有 3 类：棋盘、机器人（极小极大算法所在的位置）和游戏。请注意，加载时会启动一个新游戏（相应地弹出调试警报），并且使用预先配置的播放来模拟板以简化调试。

您会注意到，我已经尝试了三个单独的极小极大解决方案尝试（在我的业余时间我一直在努力解决这个问题），后两个现在已被注释掉。在我的最终解决方案中，我一直在关注这个伪代码。

索引.html

<!DOCTYPE html>
<!--[if lt IE 7]>      <html class="no-js lt-ie9 lt-ie8 lt-ie7"> <![endif]-->
<!--[if IE 7]>         <html class="no-js lt-ie9 lt-ie8"> <![endif]-->
<!--[if IE 8]>         <html class="no-js lt-ie9"> <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js"> <!--<![endif]-->
  <head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
    <title>Tic Tac Toe | JMS</title>
    <meta name="description" content="Tic-tac-toe using the minimax algorithm">
    <meta name="viewport" content="width=device-width">

    <link rel="stylesheet" href="css/normalize.min.css">
    <link rel="stylesheet" href="css/main.css">

    <script src="js/vendor/modernizr-2.6.2-respond-1.1.0.min.js"></script>
  </head>
  <body>

    <h1 id="output">empty</h1>

    <script src="http://ajax.googleapis.com/ajax/libs/jquery/1.9.0/jquery.min.js"></script>
    <script>window.jQuery || document.write('<script src="js/vendor/jquery-1.9.0.min.js"><\/script>')</script>

    <!-- <script src="js/main.js"></script> -->
    <script src="js/rules.js"></script>
    <script src="js/board.js"></script>
    <script src="js/game.js"></script>
    <script src="js/bot.js"></script>


    <!-- <script>
      var _gaq=[['_setAccount','UA-XXXXX-X'],['_trackPageview']];
      (function(d,t){var g=d.createElement(t),s=d.getElementsByTagName(t)[0];
      g.src=('https:'==location.protocol?'//ssl':'//www')+'.google-analytics.com/ga.js';
      s.parentNode.insertBefore(g,s)}(document,'script'));
    </script> -->
  </body>
</html>

board.coffee

class Board 
  constructor: ->
    @spaces = [0,1,2,3,4,5,6,7,8]

  reset: ->
    @spaces = [0,1,2,3,4,5,6,7,8]

  setSpace: (index, side) ->
    console.log "board.setSpace: played at index #{index} with side #{side}"
    @spaces[index] = side
    $('#output').text(@spaces)

  setSpaces: (array) ->
    @spaces = array

  getSpace: (index) ->
    @spaces[index]

  getSpaces: ->
    @spaces

机器人咖啡

class Bot
  constructor: (side) ->
    console.log "created a new bot!"
    @name = "Gandalf"
    @infinity = 99
    @side = side


  calculateMove: (board) ->
    console.log "Bot.calculateMove with #{board.getSpaces()}"
    debugger 

    isBoardEmpty = (board) -> # works
      console.log "Bot.calculateMove: board is #{board.getSpaces()}"
      boardSpaces = board.getSpaces()
      for space in boardSpaces
        console.log "Bot.calculateMove: checking if space #{space} is empty"
        if typeof space is "string" 
          console.log "Bot.calculateMove: board isn't empty"
          return false
      return true

    return 4 if isBoardEmpty(board)

    boardCopy = jQuery.extend({}, board) # this copies the board 
                                         # but still refers to the same spaces 
                                         # in the copy. Necessary?
    console.log "about to call Bot.move"
    move = @search(boardCopy, @side, 0, -@infinity, +@infinity)

    return move

  search: (board, side, depth, alpha, beta)->
    # needs to return the index of the move
    debugger

    ##### TRY 1 #####
    #################    
    value = @nodeValue(board, side)
    if value isnt 0
      if value > 0 then return value - depth else return value + depth

    otherside = if side is 'X' then 'O' else 'X'
    moves = @generateMoves board


    boardSpaces = board.getSpaces()
    boardCopy = new Board()
    boardCopy.setSpaces(boardSpaces) 


    if side is 'O'
      for move in moves
        boardCopy.setSpace(move, side)
        score = @search(boardCopy, otherside, depth + 1, beta, alpha)
        alpha = score if score > alpha
        @undoMove(boardCopy, move)
        return alpha if alpha >= beta

    if side is 'X'
      for move in moves
        boardCopy.setSpace(move, side)
        score = @search(boardCopy, otherside, depth + 1, beta, alpha)
        beta = score if score < beta
        @undoMove(boardCopy, move)
        return beta if alpha >= beta

    ##### TRY 2 #####
    #################    
    # value = @nodeValue(board, side)
    # console.log "Bot.search: depth is #{depth}"
    # console.log "Bot.search: value is #{value}"

    # if value isnt 0
    #   if value > 0 then return value - depth else return value + depth

    # moves = @generateMoves board

    # return value if moves.length is 0

    # otherside = if side is 'X' then 'O' else 'X'

    # for move in moves
    #   console.log "Bot.search: #{move} in moves" 

    #   boardSpaces = board.getSpaces()
    #   boardCopy = new Board()
    #   boardCopy.setSpaces(boardSpaces) # This could be rolled into a optional argument 
    #                                    # on the board constructor

    #   @makeMove(boardCopy, move, side)
    #   potentialAlpha = -@search(board, otherside, depth + 1, -beta, -alpha)
    #   @undoMove(boardCopy, move)  # THINK ITS SOMETHING WITH THE BOARD BEING USED
    #   break if beta <= alpha

    #   if potentialAlpha > alpha
    #     alpha = potentialAlpha
    #     if depth is 0
    #       bestMove = move

    # if depth isnt 0 then return alpha else return bestMove


    ##### TRY 3 #####
    #################
    # value = @nodeValue(board, side)
    # console.log "Bot.search: depth is #{depth}"
    # console.log "Bot.search: value is #{value}"

    # if value isnt 0
    #   if value > 0 then return value - depth else return value + depth

    # moves = @generateMoves board

    # return value if moves.length is 0 # ?

    # otherside = if side is 'X' then 'O' else 'X'

    # boardSpaces = board.getSpaces()
    # boardCopy = new Board()
    # boardCopy.setSpaces(boardSpaces) # This could be rolled into a optional argument 
    #                                  # on the board constructor
    # if side is 'O'
    #   for move in moves

    #     boardCopy.setSpace(move, side)
    #     score = @search(boardCopy, otherside, depth + 1, beta, alpha)
    #     alpha = score if score > alpha
    #     return alpha if alpha >= beta
    #     break if beta > alpha

    # else
    #   for move in moves
    #     boardCopy.setSpace(move, side)
    #     score = @search(boardCopy, otherside, depth + 1, beta, alpha)
    #     beta = score if score < beta
    #     return beta if alpha >= beta
    #     break if alph > beta


  nodeValue: (board, side) ->
    console.log "Bot.nodeValue: board is #{board.getSpaces()} and side is #{side}"
    gameResult = checkGameOver board
    console.log "Bot.nodeValue: gameResult is #{gameResult}"
    if gameResult is false or gameResult is 'tie'
      console.log "returning 0 for nodeValue"
      return 0 
    else if gameResult is side
      console.log "returning #{@infinity} for nodeValue"
      return @infinity
    else
      console.log "returning #{-@infinity} for nodeValue"
      return -@infinity

  generateMoves: (board) ->
    console.log "Bot.generateMoves: board is #{board.getSpaces()}"
    moves = []
    boardSpaces = board.getSpaces()

    for space in boardSpaces
      if typeof space is "number"
        moves.push(space)

    console.log "Bot.generateMoves: moves are #{moves}"
    return moves

  makeMove: (board, move, side) ->
    console.log "makeMove: board before makeMove with move #{move} is #{board.getSpaces()}"
    board.setSpace(move, side)
    # board[move] = side
    console.log "makeMove: board after makeMove is #{board.getSpaces()}"

    return board                                   #####

  undoMove: (board, move) ->

    console.log board.getSpaces()
    boardSpaces = board.getSpaces()
    board.setSpace(move, move)
    console.log board.getSpaces()

    return board 

# minimax = (player, board) ->

# minimax (player, board) ->
#   winner if gameOver(currentPosition)

规则.咖啡

checkGameOver = (board) ->
  opportunities = 8
  result        = false

  check = (space) ->
    board.getSpace(space)

  winningCombinations = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],
                         [1,4,7],[2,5,8],[0,4,8],[2,4,6]]

  for combo in winningCombinations
    firstPlay       = combo[0]
    secondPlay      = combo[1]
    thirdPlay       = combo[2]

    if typeof check(firstPlay) is "string" and 
    typeof check(secondPlay) is "string" and 
    typeof check(thirdPlay) is "string"
      opportunities -= 1
      console.log "checkGameOver: opportunities decreased to #{opportunities}"

    if check(firstPlay) is check(secondPlay) is check(thirdPlay)
      alert "Winner is #{board.getSpace(firstPlay)}"
      return result = board.getSpace(firstPlay)

    if opportunities is 0
      alert "tie"
      return result = "tie"

  return result

游戏.咖啡

class Game
  constructor: ->
    @board = new Board()
    $('#output').text(@board.getSpaces())

  new: ->
    @board.reset()
    @result = false
    @side = "X"
    @bot = new Bot "O"
    @moves = 0

  firstTurn: ->
    # Production
    # space = prompt "What space are you playing?"
    # @makeMove space

    # Testing
    @board.setSpaces ['X',1,2,3,'O',5,6,7,8] # Testing – Bot should output 1 for calMove
    @makeMove 2

  makeMove: (space) =>
    @board.setSpace(space, @side)
    @moves += 1
    @concludeTurn()

  listenForMove: ->
    space = prompt "What space are you playing?"
    @makeMove space

  concludeTurn: ->
    @result = checkGameOver @board
    console.log "Result is #{@result}"

    if @result is 'X' or @result is 'O' or @result is 'tie'
      alert "Game.concludeTurn: game is over, heading into gameOver"
      return @gameOver @result 
    @changeTurn()

  changeTurn: ->
    @side = if @side is 'X' then 'O' else 'X'
    console.log "in change turn, side is now #{@side}"
    @listenForMove() if @side is 'X'

    console.log "Game.changeTurn: bot (#{@bot}) is about to calc move"
    @makeMove(@bot.calculateMove @board) if @side is 'O'

    # placement = @bot.calculateMove @board if @side is 'O'
    # console.log placement
    # @board.setSpace(placement, 'O') # give a secondary argument to makeMove and remove
    # @concludeTurn()


  gameOver: (winner) ->
    console.log "Game.concludeTurn: winner is #{@result}"
    return
    # answer = prompt "Winner is #{winner}! Would you like to play again?"
    # @playAgain answer

  # playAgain: (answer) ->
  #   alert "Suite yourself" if answer is false
  #   @new() if answer is true


# check if game is over
# check moves
#   if even then human
# else 
#   bot
# 
# increment moves?

# reset grid
# turn = "X"
# move = 0

g = new Game()
g.new()
g.firstTurn()

非常感谢任何帮助。

4

1 回答 1

0

问题一：

return value if moves.length is 0在计算移动之后，您的尝试#1 就丢失了。当我测试您的尝试 #2 时，它完美无缺。我必须围绕该代码做很多工作才能使整个工作正常，但这与尝试#2 中的极小极大代码无关。在您的bot.coffee中，请禁用您的其他 2 次尝试，仅启用尝试 #2。然后game.coffee用下面的替换。

class Game
  constructor: ->
    @board = new Board()
    $('#output').text(@board.getSpaces())

  new: ->
    @board.reset()
    @result = false
    @side = "X"
    @bot = new Bot "O"
    @moves = 0

  firstTurn: ->
    # Production
    space = prompt "What space are you playing?"
    if space is null
      return
    @makeMove space

    # Testing
    #@board.setSpaces ['X',1,2,3,'O',5,6,7,8] # Testing – Bot should output 1 for calMove
    #@makeMove 2

  makeMove: (space) =>
    @board.setSpace(space, @side, true)
    @moves += 1
    @concludeTurn()

  listenForMove: ->
    space = prompt "What space are you playing?"
    if space is null
      return
    @makeMove space

  concludeTurn: ->
    @result = checkGameOver @board
    #alert "Result is #{@result}"

    if @result is 'X' or @result is 'O' or @result is 'tie'
      alert "Game.concludeTurn: game is over, heading into gameOver"
      return @gameOver @result 
    @changeTurn()

  changeTurn: ->
    @side = if @side is 'X' then 'O' else 'X'
    console.log "in change turn, side is now #{@side}"
    if @side is 'X'
      @listenForMove()
    else if @side is 'O'
      console.log "Game.changeTurn: bot (#{@bot}) is about to calc move"
      @makeMove(@bot.calculateMove @board)

    # placement = @bot.calculateMove @board if @side is 'O'
    # console.log placement
    # @board.setSpace(placement, 'O') # give a secondary argument to makeMove and remove
    # @concludeTurn()


  gameOver: (winner) ->
    console.log "Game.concludeTurn: winner is #{@result}"
    answer = prompt "Winner is #{winner}! Would you like to play again?"
    @playAgain answer

  playAgain: (answer) ->
    alert "Suite yourself" if answer is false
    @new() if answer is true


# check if game is over
# check moves
#   if even then human
# else 
#   bot
# 
# increment moves?

# reset grid
# turn = "X"
# move = 0

g = new Game()
g.new()
g.firstTurn()

并board.coffee变成：

class Board 
  constructor: ->
    @spaces = [0,1,2,3,4,5,6,7,8]

  reset: ->
    @spaces = [0,1,2,3,4,5,6,7,8]

  setSpace: (index, side, print = false) ->
    #console.log "board.setSpace: played at index #{index} with side #{side}"
    @spaces[index] = side
    if print
      $('#output').text(@spaces)

  setSpaces: (array) ->
    @spaces = array

  getSpace: (index) ->
    @spaces[index]

  getSpaces: ->
    @spaces

问题2：

游戏板对象未绑定到 DOM，但每次移动时都会将其打印出来。而且由于您使用它的实例来计算您的极小值，因此您总是在不应该打印的时候打印到屏幕上。所以我在board.coffee上面进行了更改，只添加了一个打印参数来解决这个问题。我不喜欢你写整个东西的方式，它在所有方面都是完全低效的，我永远不会那样写，但问题不在于效率，所以我会留在那里。

于 2013-04-06T07:38:18.027 回答