Asp Forum - [QUIZ][SOLUTION] Kalah (#58

David Balmain

12/12/2005 3:44:00 AM

Hey guys,

Here's my solution to this weeks Ruby quiz. I used the MTD(f) algorithm.

http://en.wikipedia.org/wiki/...

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/p...

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

13 Answers

Adam Shelly

12/12/2005 8:26:00 PM

Here are my Kalah Players.
My first trick was to create subclass of Player so that my players are
always playing from bins 0..5. This got rid of a lot of messy
conditions. It also contains a move simulator.

AdamsPlayers.rb contains some very simple test players, as well as 2
reasonably good players:
DeepScoreKalahPlayer tries to find the biggest gain in points for a
single move, and APessimisticKalahPlayer does the same, but subtracts
the opponent's best possible next move.

AHistoryPlayer.rb contains a player which ranks the results of each
move, and keeps a history. The idea is that the more it plays, the
less likely it is to choose bad moves.
It stores the history in a Yaml file, which definitely causes a
slowdown as it gets bigger.
That's one thing I'd like to improve if I have time. I also added a
line to the game engine to report the final score back to the players.
AHistoryPlayer still works without it, but it's less accurate I
think, since it never records the final result.

None of these players pay much attention to the number of stones
remaining on the opponent's side, which is one factor in why they fail
miserably against Dave's player. But they do tend to beat Rob's
players. I'm hoping some more people submit solutions.

Add your players to TestMatch.rb to run them in a roundRobin

-Adam

Adam Shelly

12/12/2005 10:25:00 PM

Of course I introduced an error while cleaning up my code:
That will teach me to skip unit tests...

in AdamsPlayers.rb, line 111
i = best_move(b) if taketurn
should be
m = best_move(b) if taketurn

-Adam.

On 12/12/05, Adam Shelly <adam.shelly@gmail.com> wrote:
> Here are my Kalah Players.

Adam Shelly

12/12/2005 10:57:00 PM

Not strictly quiz related, but why do my emails to the list get have
certain characters garbled when they are added to the ruby-talk
archives (linked from the ruby quiz site)?

My post at http://www.ruby-talk.org/cgi-bin/scat.rb/ruby/ruby-t...
has =09 in place of tabs and =3D instead of equals.

Or at least that's what I see. I'm not even sure if it's a problem
with the mail I send from gmail, or with my browser settings viewing
the archive...
Any Ideas?

Thanks,
-Adam

MenTaLguY

12/12/2005 11:25:00 PM

Quoting Adam Shelly <adam.shelly@gmail.com>:

> My post at
> http://www.ruby-talk.org/cgi-bin/scat.rb/ruby/ruby-t...
> has =09 in place of tabs and =3D instead of equals.

As far as I can see, it's because the archive software doesn't
implement MIME completely enough. For some "interesting" messages,
it seems to just dump the raw message rather than decoding it.

-mental

Steve Litt

12/13/2005 1:37:00 AM

On Monday 12 December 2005 05:24 pm, Adam Shelly wrote:
> Of course I introduced an error while cleaning up my code:
> That will teach me to skip unit tests...

Could you please tell me more about the use of test units?

Thanks

SteveT

Steve Litt
http://www.troublesh...
slitt@troubleshooters.com

James Gray

12/13/2005 3:37:00 AM

On Dec 12, 2005, at 7:36 PM, Steve Litt wrote:

> On Monday 12 December 2005 05:24 pm, Adam Shelly wrote:
>> Of course I introduced an error while cleaning up my code:
>> That will teach me to skip unit tests...
>
> Could you please tell me more about the use of test units?

If you're looking for a definition, try Wikipedia:

http://en.wikipedia.org/wiki/Un...

If you are curious about Ruby's Unit Test library, it is documented
here:

http://www.ruby-doc.org/stdlib/libdoc/test/unit/rdoc/...

Hope that helps.

James Edward Gray II

James Gray

12/13/2005 3:37:00 AM

David Balmain

12/13/2005 3:44:00 AM

Hi Adam,
Just ran a tournament with your players. In case you or anyone else is
interested;

APessimisticKalahPlayer scored 527 points in 2265.782466 seconds
AHistoryKalahPlayer scored 478 points in 98.2062879999999 seconds
RemoveRightKalahPlayer scored 469 points in 0.004744 seconds
DeepScoreKalahPlayer scored 460 points in 0.055886 seconds
ScoreKalahPlayer scored 450 points in 0.020305 seconds
RemoveRandomLowKalahPlayer scored 312 points in 0.012781 seconds
RemoveRandomHighKalahPlayer scored 309 points in 0.013103 seconds
RemoveHighKalahPlayer scored 264 points in 0.005501 seconds
RemoveLowKalahPlayer scored 187 points in 0.007318 seconds

Cheers,
Dave

On 12/13/05, Adam Shelly <adam.shelly@gmail.com> wrote:
> Of course I introduced an error while cleaning up my code:
> That will teach me to skip unit tests...
>
> in AdamsPlayers.rb, line 111
> i = best_move(b) if taketurn
> should be
> m = best_move(b) if taketurn
>
> -Adam.
>
>
> On 12/12/05, Adam Shelly <adam.shelly@gmail.com> wrote:
> > Here are my Kalah Players.
>
>
>

David Balmain

12/13/2005 3:44:00 AM

Adam Shelly

12/13/2005 6:09:00 AM

Cool.
I'm suprised RemoveRight did better than DeepScore.
I was looking more at HistoryPlayer, (which should do better than
Pessimistic, since it uses the same choice for any unknown situations)
and I realized that when scoring a move, it is giving too much weight
to the subsequent turns. So it can choose the absolute best move on
turn 2, for instance, then make a bad move 3 turns later, and end up
ranking the turn 2 choice as the worst possibility. So for now, the
history information it keeps is mostly useless, except for a speedup.
My history algorithm needs some tuning (if it can be salvaged at all
:)

I'd be curious to see what happens if you add the other submitted
players to the tournament. Can you post the tourney framework?

-Adam

On 12/12/05, David Balmain <dbalmain.ml@gmail.com> wrote:
> Hi Adam,
> Just ran a tournament with your players. In case you or anyone else is
> interested;
>
> APessimisticKalahPlayer scored 527 points in 2265.782466 seconds
> AHistoryKalahPlayer scored 478 points in 98.2062879999999 seconds
> RemoveRightKalahPlayer scored 469 points in 0.004744 seconds
> DeepScoreKalahPlayer scored 460 points in 0.055886 seconds
> ScoreKalahPlayer scored 450 points in 0.020305 seconds
> RemoveRandomLowKalahPlayer scored 312 points in 0.012781 seconds
> RemoveRandomHighKalahPlayer scored 309 points in 0.013103 seconds
> RemoveHighKalahPlayer scored 264 points in 0.005501 seconds
> RemoveLowKalahPlayer scored 187 points in 0.007318 seconds
>
> Cheers,
> Dave
>
> On 12/13/05, Adam Shelly <adam.shelly@gmail.com> wrote:
> > Of course I introduced an error while cleaning up my code:
> > That will teach me to skip unit tests...
> >
> > in AdamsPlayers.rb, line 111
> > i = best_move(b) if taketurn
> > should be
> > m = best_move(b) if taketurn
> >
> > -Adam.
> >
> >
> > On 12/12/05, Adam Shelly <adam.shelly@gmail.com> wrote:
> > > Here are my Kalah Players.
> >
> >
> >
>
>

comp.lang.ruby

[QUIZ][SOLUTION] Kalah (#58

David Balmain

Adam Shelly

Adam Shelly

Adam Shelly

MenTaLguY

Steve Litt

James Gray

James Gray

David Balmain

David Balmain

Adam Shelly

x Login to ForumsZone