Hey guys,
Here’s my solution to this weeks Ruby quiz. I used the MTD(f) algorithm.
Unfortunately I couldn’t seem to get my transposition tables to work
correctly. The garbage collector kept crashing. I think that to get a
solution like this to work well you need to store the transposition
tables on disk. Pity I haven’t finished cFerret yet.
By the way, I’m afraid my solution probably isn’t very Rubyish. You
can probably tell I’ve been doing a lot of C coding lately. If anyone
wants to clean it up and improve it, please do and let me know about
it. 
Looking forward to seeing some other solutions.
Cheers,
Dave
See a syntax coloured version here;
http://www.davebalmain.com/pages/kalah
require ‘player’
class Dave < Player
START_BOARD = [4,4,4,4,4,4,0,4,4,4,4,4,4,0]
Bounds = Struct.new(:lower, :upper, :lower_move, :upper_move)
def initialize(name, depth = [6,8])
super(name)
@depth = depth
@guess = 0
@transposition_table = {}
@previous_transposition_table = {}
end
def choose_move
board = @game.board
# start move is always the same;
if board == START_BOARD
# we are first to go
@guess = 8
@move_list = [5]
return 2
elsif board[13] == 0 and @game.player_to_move == KalahGame::TOP
# we are second to go
@guess = -9
return 9 if board[9] == 4
return 8
end
return @move_list.pop if @move_list and @move_list.size > 0
# If the next move is from the top then we rotate the board so that
all
# operations would be the same as if we were playing from the bottom
if (@game.player_to_move == KalahGame::TOP)
# We do iterative deepening here. Unfortunately, due to memory
# constraints, the transpositon table has to be reset every turn
so we
# can’t go very deep. For a depth of 8, one step seems to be the
same as
# two but we’ll keep it for demonstration purposes.
@depth.each do |depth|
@guess, @move_list = mtdf(board[7,7] + board[0,7], @guess,
depth)
@previous_transposition_table = @transposition_table
@transposition_table = {}
end
@move_list.size.times {|i| @move_list[i] += 7}
else
@depth.each do |depth|
@guess, @move_list = mtdf(board.dup, @guess, depth)
@previous_transposition_table = @transposition_table
@transposition_table = {}
end
end
return @move_list.pop
end
def make_move(move, board)
stones = board[move]
board[move] = 0
pos = move
while stones > 0
pos += 1
pos = 0 if pos==13
board[pos] += 1
stones -= 1
end
if(pos.between?(0,5) and board[pos] == 1)
board[6] += board[12-pos] + 1
board[12-pos] = board[pos] = 0
end
board
end
def game_over?(board)
top = bottom = true
(7…12).each { |i| top = false if board[i] > 0 }
(0… 5).each { |i| bottom = false if board[i] > 0 }
top or bottom
end
def game_over_score(board)
score = 0
(0… 6).each { |i| score += board[i] }
(7…13).each { |i| score -= board[i] }
return score
end
def mtdf(game, guess, depth)
upper = 1000
lower = -1000
move = -1
begin
alpha = (guess == upper) ? guess - 1 : guess
guess, move = alpha_beta(game, alpha, alpha + 1, depth)
if guess > alpha
best_move = move
lower = guess
else
upper = guess
end
end while lower < upper
return guess, best_move
end
def alpha_beta(board, lower, upper, depth)
# Check the transposition table to see if we’ve tried this board
before
if (bounds = @transposition_table[board])
return bounds.lower, bounds.lower_move if bounds.lower >= upper
return bounds.upper, bounds.upper_move if bounds.upper <= lower
# last time we were with these bounds so use the same position
that we
# found last time
first_move = (bounds.upper_move||bounds.lower_move).last
else
# We haven’t tried this board before during this round
bounds = @transposition_table[board] = Bounds.new(-1000, 1000,
nil, nil)
# If we tried this board in a previous round see what move was
found to
# be the best. We’ll try it first.
if (prev_bounds = @previous_transposition_table[board])
first_move =
(prev_bounds.upper_move||prev_bounds.lower_move).last
end
end
if (game_over?(board))
guess = game_over_score(board)
best = []
elsif (depth == 0)
guess = board[6] - board[13]
best = []
else
best = -1
guess = -1000
moves = []
(0..5).each do |i|
next if board[i] == 0
if board[i] == 6-i
moves.unshift(i)
else
moves.push(i)
end
end
# move the previous best move for this board to the front
if first_move and first_move != moves[0]
moves.delete(first_move)
moves.unshift(first_move)
end
moves.each do |i|
next_board = make_move(i, board.dup)
if board[i] == 6-i
next_guess, move_list = alpha_beta(next_board, lower, upper,
depth)
else
next_guess, = alpha_beta(next_board[7,7] + next_board[0,7],
0-upper, 0-lower, depth - 1)
next_guess *= -1
move_list = []
end
if (next_guess > guess)
guess = next_guess
best = move_list + [i]
# beta pruning
break if (guess >= upper)
end
#lower = guess if (guess > lower)
end
end
# record the upper or lower bounds for this position if we have
found a
# new best bound
if guess <= lower
bounds.upper = guess
bounds.upper_move = best
end
if guess >= upper
bounds.lower = guess
bounds.lower_move = best
end
return guess, best
end
end
