Ruby: implementing alpha-beta pruning for tic-tac-toe
- by DerNalia
So, alpha-beta pruning seems to be the most efficient algorithm out there aside from hard coding (for tic tac toe). However, I'm having problems converting the algorithm from the C++ example given in the link: http://www.webkinesia.com/games/gametree.php
#based off http://www.webkinesia.com/games/gametree.php
# (converted from C++ code from the alpha - beta pruning section)
# returns 0 if draw
LOSS = -1
DRAW = 0
WIN = 1
@next_move = 0
def calculate_ai_next_move
score = self.get_best_move(COMPUTER, WIN, LOSS)
return @next_move
end
def get_best_move(player, alpha, beta)
best_score = nil
score = nil
if not self.has_available_moves?
return false
elsif self.has_this_player_won?(player)
return WIN
elsif self.has_this_player_won?(1 - player)
return LOSS
else
best_score = alpha
NUM_SQUARES.times do |square|
if best_score >= beta
break
end
if self.state[square].nil?
self.make_move_with_index(square, player)
# set to negative of opponent's best move; we only need the returned score;
# the returned move is irrelevant.
score = -get_best_move(1-player, -beta, -alpha)
if (score > bestScore)
@next_move = square
best_score = score
end
undo_move(square)
end
end
end
return best_score
end
the problem is that this is returning nil.
some support methods that are used above:
WAYS_TO_WIN = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8],[0, 4, 8], [2, 4, 6]]
def has_this_player_won?(player)
result = false
WAYS_TO_WIN.each {|solution| result = self.state[solution[0]] if contains_win?(solution) }
return (result == player)
end
def contains_win?(ttt_win_state)
ttt_win_state.each do |pos|
return false if self.state[pos] != self.state[ttt_win_state[0]] or self.state[pos].nil?
end
return true
end
def make_move(x, y, player)
self.set_square(x,y, player)
end
