D
David Balmain
Hey guys,
Here's my solution to this weeks Ruby quiz. I used the MTD(f) algorithm.
http://en.wikipedia.org/wiki/MTD(f)
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 =3D [4,4,4,4,4,4,0,4,4,4,4,4,4,0]
Bounds =3D Struct.new
lower, :upper, :lower_move, :upper_move)
def initialize(name, depth =3D [6,8])
super(name)
@depth =3D depth
@guess =3D 0
@transposition_table =3D {}
@previous_transposition_table =3D {}
end
def choose_move
board =3D @game.board
# start move is always the same;
if board =3D=3D START_BOARD
# we are first to go
@guess =3D 8
@move_list =3D [5]
return 2
elsif board[13] =3D=3D 0 and @game.player_to_move =3D=3D KalahGame::TOP
# we are second to go
@guess =3D -9
return 9 if board[9] =3D=3D 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 =3D=3D KalahGame::TOP)
# We do iterative deepening here. Unfortunately, due to memory
# constraints, the transpositon table has to be reset every turn so w=
e
# 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 =3D mtdf(board[7,7] + board[0,7], @guess, depth)
@previous_transposition_table =3D @transposition_table
@transposition_table =3D {}
end
@move_list.size.times {|i| @move_list +=3D 7}
else
@depth.each do |depth|
@guess, @move_list =3D mtdf(board.dup, @guess, depth)
@previous_transposition_table =3D @transposition_table
@transposition_table =3D {}
end
end
return @move_list.pop
end
def make_move(move, board)
stones =3D board[move]
board[move] =3D 0
pos =3D move
while stones > 0
pos +=3D 1
pos =3D 0 if pos=3D=3D13
board[pos] +=3D 1
stones -=3D 1
end
if(pos.between?(0,5) and board[pos] =3D=3D 1)
board[6] +=3D board[12-pos] + 1
board[12-pos] =3D board[pos] =3D 0
end
board
end
def game_over?(board)
top =3D bottom =3D true
(7..12).each { |i| top =3D false if board > 0 }
(0.. 5).each { |i| bottom =3D false if board > 0 }
top or bottom
end
def game_over_score(board)
score =3D 0
(0.. 6).each { |i| score +=3D board }
(7..13).each { |i| score -=3D board }
return score
end
def mtdf(game, guess, depth)
upper =3D 1000
lower =3D -1000
move =3D -1
begin
alpha =3D (guess =3D=3D upper) ? guess - 1 : guess
guess, move =3D alpha_beta(game, alpha, alpha + 1, depth)
if guess > alpha
best_move =3D move
lower =3D guess
else
upper =3D 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 =3D @transposition_table[board])
return bounds.lower, bounds.lower_move if bounds.lower >=3D upper
return bounds.upper, bounds.upper_move if bounds.upper <=3D lower
# last time we were with these bounds so use the same position that w=
e
# found last time
first_move =3D (bounds.upper_move||bounds.lower_move).last
else
# We haven't tried this board before during this round
bounds =3D @transposition_table[board] =3D Bounds.new(-1000, 1000, ni=
l, 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 =3D @previous_transposition_table[board])
first_move =3D (prev_bounds.upper_move||prev_bounds.lower_move).las=
t
end
end
if (game_over?(board))
guess =3D game_over_score(board)
best =3D []
elsif (depth =3D=3D 0)
guess =3D board[6] - board[13]
best =3D []
else
best =3D -1
guess =3D -1000
moves =3D []
(0..5).each do |i|
next if board =3D=3D 0
if board =3D=3D 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 !=3D moves[0]
moves.delete(first_move)
moves.unshift(first_move)
end
moves.each do |i|
next_board =3D make_move(i, board.dup)
if board =3D=3D 6-i
next_guess, move_list =3D alpha_beta(next_board, lower, upper, de=
pth)
else
next_guess, =3D alpha_beta(next_board[7,7] + next_board[0,7],
0-upper, 0-lower, depth - 1)
next_guess *=3D -1
move_list =3D []
end
if (next_guess > guess)
guess =3D next_guess
best =3D move_list +
# beta pruning
break if (guess >=3D upper)
end
#lower =3D 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 <=3D lower
bounds.upper =3D guess
bounds.upper_move =3D best
end
if guess >=3D upper
bounds.lower =3D guess
bounds.lower_move =3D best
end
return guess, best
end
end
Here's my solution to this weeks Ruby quiz. I used the MTD(f) algorithm.
http://en.wikipedia.org/wiki/MTD(f)
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 =3D [4,4,4,4,4,4,0,4,4,4,4,4,4,0]
Bounds =3D Struct.new
def initialize(name, depth =3D [6,8])
super(name)
@depth =3D depth
@guess =3D 0
@transposition_table =3D {}
@previous_transposition_table =3D {}
end
def choose_move
board =3D @game.board
# start move is always the same;
if board =3D=3D START_BOARD
# we are first to go
@guess =3D 8
@move_list =3D [5]
return 2
elsif board[13] =3D=3D 0 and @game.player_to_move =3D=3D KalahGame::TOP
# we are second to go
@guess =3D -9
return 9 if board[9] =3D=3D 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 =3D=3D KalahGame::TOP)
# We do iterative deepening here. Unfortunately, due to memory
# constraints, the transpositon table has to be reset every turn so w=
e
# 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 =3D mtdf(board[7,7] + board[0,7], @guess, depth)
@previous_transposition_table =3D @transposition_table
@transposition_table =3D {}
end
@move_list.size.times {|i| @move_list +=3D 7}
else
@depth.each do |depth|
@guess, @move_list =3D mtdf(board.dup, @guess, depth)
@previous_transposition_table =3D @transposition_table
@transposition_table =3D {}
end
end
return @move_list.pop
end
def make_move(move, board)
stones =3D board[move]
board[move] =3D 0
pos =3D move
while stones > 0
pos +=3D 1
pos =3D 0 if pos=3D=3D13
board[pos] +=3D 1
stones -=3D 1
end
if(pos.between?(0,5) and board[pos] =3D=3D 1)
board[6] +=3D board[12-pos] + 1
board[12-pos] =3D board[pos] =3D 0
end
board
end
def game_over?(board)
top =3D bottom =3D true
(7..12).each { |i| top =3D false if board > 0 }
(0.. 5).each { |i| bottom =3D false if board > 0 }
top or bottom
end
def game_over_score(board)
score =3D 0
(0.. 6).each { |i| score +=3D board }
(7..13).each { |i| score -=3D board }
return score
end
def mtdf(game, guess, depth)
upper =3D 1000
lower =3D -1000
move =3D -1
begin
alpha =3D (guess =3D=3D upper) ? guess - 1 : guess
guess, move =3D alpha_beta(game, alpha, alpha + 1, depth)
if guess > alpha
best_move =3D move
lower =3D guess
else
upper =3D 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 =3D @transposition_table[board])
return bounds.lower, bounds.lower_move if bounds.lower >=3D upper
return bounds.upper, bounds.upper_move if bounds.upper <=3D lower
# last time we were with these bounds so use the same position that w=
e
# found last time
first_move =3D (bounds.upper_move||bounds.lower_move).last
else
# We haven't tried this board before during this round
bounds =3D @transposition_table[board] =3D Bounds.new(-1000, 1000, ni=
l, 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 =3D @previous_transposition_table[board])
first_move =3D (prev_bounds.upper_move||prev_bounds.lower_move).las=
t
end
end
if (game_over?(board))
guess =3D game_over_score(board)
best =3D []
elsif (depth =3D=3D 0)
guess =3D board[6] - board[13]
best =3D []
else
best =3D -1
guess =3D -1000
moves =3D []
(0..5).each do |i|
next if board =3D=3D 0
if board =3D=3D 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 !=3D moves[0]
moves.delete(first_move)
moves.unshift(first_move)
end
moves.each do |i|
next_board =3D make_move(i, board.dup)
if board =3D=3D 6-i
next_guess, move_list =3D alpha_beta(next_board, lower, upper, de=
pth)
else
next_guess, =3D alpha_beta(next_board[7,7] + next_board[0,7],
0-upper, 0-lower, depth - 1)
next_guess *=3D -1
move_list =3D []
end
if (next_guess > guess)
guess =3D next_guess
best =3D move_list +
# beta pruning
break if (guess >=3D upper)
end
#lower =3D 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 <=3D lower
bounds.upper =3D guess
bounds.upper_move =3D best
end
if guess >=3D upper
bounds.lower =3D guess
bounds.lower_move =3D best
end
return guess, best
end
end