Skip to content

Instantly share code, notes, and snippets.

@AgileMantis
Created December 29, 2011 15:16
Show Gist options
  • Save AgileMantis/1534520 to your computer and use it in GitHub Desktop.
Save AgileMantis/1534520 to your computer and use it in GitHub Desktop.
Minimax Algorithm
# (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_comp_move] = 'O'
# Minmax Algorithm
def best_comp_move(ply=0, alpha=-99999, beta=99999)
if is_won? # Human won before comp move
reset_winner_state
return -9999+ply # A Win closer to root is better than one deeper in the tree
end
return 0 if full_board?
value = -99999
best_move = 0
legal_moves.each do |sqr|
state[sqr] = 'O'
response = best_human_move(ply+1,alpha,beta)
state[sqr] = ' '
if response > value
if ply==0 then puts "New best value #{response} from sqr #{sqr}" end
value = alpha = response
best_move = sqr
end
if beta <= alpha
break
end
end
return best_move if ply==0
value
end
def best_human_move(ply,alpha,beta)
if is_won? # Comp won before human move
reset_winner_state
return 9999-ply # A Win closer to root is better than one deeper in the tree
end
return 0 if full_board?
if ply >= 3
return score
end
value = 99999
legal_moves.each do |sqr|
state[sqr] = 'X'
response = best_comp_move(ply+1,alpha,beta)
state[sqr] = ' '
if response < value
value = beta = response
end
if beta <= alpha
break
end
end
value
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment