Recursive minimax with alpha/beta prunning (first version)

gistfile1.rb

def minimax(max_player = true, ply = 0, alpha = -9999, beta = 9999)                                        

  # Return from recursive calls for the following escape conditions: 
  # 1. winning move found
  # 2. resulting game tree ended in a draw

  if board.winner?
    # to differentiate between a win later in the game tree versus near the root, we + or - the ply from alpha or beta,
    # depending on if the current move represents a win for the max player, or the min player, respectively.
    return(max_player ? (-9999 + ply) : (9999 - ply)) 
  elsif board.draw_game?
    return 0               
  end   

  best_move = 0
  ab_value  = (max_player ? -9999 : 9999)

  available_moves.each do |index|
    board[][index] = ( max_player ? side : opposite_side(side) )
    score          = minimax(!max_player, ply+1, alpha, beta)
    undo_move(index)

    # as max player, we want to maximize the min's score (represented by the -alpha value)
    if max_player && score > ab_value
      ab_value, alpha = [score, score]
      best_move = index
    # as a min player, we want to minimize the max's score (represented by the +beta value)
    elsif !max_player && score < ab_value
      ab_value, beta = [score, score]
    end

    # For game trees as small as Tic Tac Toe combined with alpha / beta pruning, we don't have to worry so much about exhausting
    # memory and blowing the stack. But one strategy for dealing with game trees that will never result in a best move and
    # prevent wasting cycles on evaluating their terminal nodes is to compare the alpha and beta values, and break the 
    # expansion of the current game tree.
    if alpha >= beta
      break
    end
  end


  # In order to get the score to return to our root nodes, we want the score to stay on top of the stack when we return from 
  # the recursive calls. This works great, until we want to return the best move. To know whether or not to return the best move     
  # found, or a score, we check the current ply. If ply == 0, we know we are at a root node, and only then will we want to
  # return the best move. Otherwise, we happily pass the score back to the most recent minimax invocation as the CPU iteratively
  # pops the stack of recursive calls.
  return (ply == 0 ? best_move : ab_value)
end