Minimax Algorithm - Direct Recursion

minimax_snippet_direct.rb

# (The MIT License)
# 
# Copyright (c) 2011 Ledsworth Consulting LLC
# 
# Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
# documentation files (the "Software"), to deal in the Software without restriction, including without limitation the 
# rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit 
# persons to whom the Software is furnished to do so, subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be included in all copies or substantial portions of the 
# Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE 
# WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR 
# COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR 
# OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
#
# Call to algorithm (computer plays 'O', state array holds the current game board)
state[best_move] = 'O'

# Minmax Algorithm
def best_move(max_player=true, ply=0, alpha=-99999, beta=99999)
  # Terminal conditions
  if is_won? 
    reset_winner_state  # Undo winner state
    return (max_player ? (-9999+ply) : ( 9999-ply))
  end
  return 0 if full_board?
  if ply >= 3
    return score
  end

  best_move = 0
  value = (max_player ? -99999 : 99999)
  legal_moves.each do |sqr|

    state[sqr] = (max_player ? 'O' : 'X')
    response = best_move(!max_player,ply+1,alpha,beta)
    state[sqr] = ' '  # Undo move

    if max_player && response > value  
      value = alpha = response
      best_move = sqr
    end
    if !max_player && response < value  
      value = beta = response
    end
    # Alpha-beta cut-off
    if beta <= alpha   
      break
    end
  end

  return (ply==0 ? best_move : value)
end