[QUIZ] Kalah (#58)

R

Ruby Quiz

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Mark Van Holstyn

For my Computer Science class this month, we had to program a Kalah Player.
Sadly, we had to do our project in Java, but I ported the game code and the
sample players to ruby for this quiz though.

A good explanation of the game can be found at:

http://rubyurl.com/SqU

Your task is to create the best Kalah player you can. The player should look
like the following:

class HumanPlayer < Player
def choose_move
print 'Enter your move choice: '
gets.chomp.to_i
end
end

The 'choose_move' method is what the game will call to request a move from the
player. The Player class which you player should extend looks like so:

class Player
attr_accessor :name
attr_writer :game, :side

def initialize( name )
@name = name
end

def choose_move
if @side==KalahGame::TOP
(7..12).each { |i| return i if @game.stones_at?(i) > 0 }
else
(0..5).each { |i| return i if @game.stones_at?(i) > 0 }
end
end
end

The 'game' and 'side' attributes will be assigned by KalahGame. The side will
either be the constant KalahGame::TOP or KalahGame::BOTTOM. This is what you
will use to determine if you should be making moves from bowls 0-5 or 7-12 and
whether your Kalah is 6 or 13.

KalahMatch plays two games, one with each player on the each side of the board
and then averages their scores, so you must make you player be able to play both
on the top and the bottom.

Here's a sample game engine to get you started:

require 'Player'
require 'HumanPlayer'

class KalahMatch
def start( p1, p2 )
puts ''
puts '========== GAME 1 =========='
p1_score_1, p2_score_1 = KalahGame.new.play_game( p1, p2 )

if p1_score_1 > p2_score_1
puts p1.name+' won game #1: '+p1_score_1.to_s+'-'+p2_score_1.to_s
elsif p2_score_1 > p1_score_1
puts p2.name+' won game #1: '+p2_score_1.to_s+'-'+p1_score_1.to_s
else
puts 'game #1 was a tie: '+p1_score_1.to_s+'-'+p2_score_1.to_s
end

puts ''
puts '========== GAME 2 =========='
p2_score_2, p1_score_2 = KalahGame.new.play_game( p2, p1 )

if p1_score_2 > p2_score_2
puts p1.name+' won game #2: '+p1_score_2.to_s+'-'+p2_score_2.to_s
elsif p2_score_2 > p1_score_2
puts p2.name+' won game #2: '+p2_score_2.to_s+'-'+p1_score_2.to_s
else
puts 'game #2 was a tie: '+p1_score_2.to_s+'-'+p2_score_2.to_s
end

puts ''
puts '========== FINAL =========='

p1_final = p1_score_1+p1_score_2
p2_final = p2_score_1+p2_score_2

if p1_final > p2_final
puts p1.name+' won the match: '+p1_final.to_s+'-'+p2_final.to_s
elsif p2_final > p1_final
puts p2.name+' won the match: '+p2_final.to_s+'-'+p1_final.to_s
else
puts 'the match was tied overall : '+p1_final.to_s+'-'+p2_final.to_s
end
end
end

class KalahGame
NOBODY = 0
TOP = 1
BOTTOM = 2

def stones_at?( i )
@board
end

def legal_move?( move )
( ( @player_to_move==TOP and move >= 7 and move <= 12 ) ||
( @player_to_move==BOTTOM and move >= 0 and move <= 5 ) ) and
@board[move] != 0
end

def game_over?
top = bottom = true
(7..12).each { |i| top = false if @board > 0 }
(0..5).each { |i| bottom = false if @board > 0 }
top or bottom
end

def winner
top, bottom = top_score, bottom_score
if top > bottm
return TOP
elsif bottom > top
return BOTTOM
else
return NOBODY
end
end

def top_score
score = 0
(7..13).each { |i| score += @board }
score
end

def bottom_score
score = 0
(0..6).each { |i| score += @board }
score
end

def make_move( move )
( puts 'Illegal move...' ; return ) unless legal_move?( move )

stones, @board[move] = @board[move], 0

pos = move+1
while stones > 0
pos+=1 if( (@player_to_move==TOP and pos==6) ||
(@player_to_move==BOTTOM and pos==13) )
pos = 0 if pos==14
@board[pos]+=1
stones-=1
pos+=1 if stones > 0
end

if( @player_to_move==TOP and pos>6 and pos<13 and @board[pos]==1 )
@board[13] += @board[12-pos]+1
@board[12-pos] = @board[pos] = 0
elsif( @player_to_move==BOTTOM and pos>=0 and pos<6 and @board[pos]==1 )
@board[6] += @board[12-pos]+1
@board[12-pos] = @board[pos] = 0
end

if @player_to_move==TOP
@player_to_move = BOTTOM unless pos == 13
else
@player_to_move=TOP unless pos == 6
end

end

def display
puts ''
top = ' '
[12,11,10,9,8,7].each { |i| top += @board.to_s+' ' }
puts top
puts @board[13].to_s + ' ' + @board[6].to_s
bottom = ' '
(0..5).each { |i| bottom += @board.to_s+' ' }
puts bottom
puts ''
end

def reset
@board = Array.new( 14, 4 )
@board[6] = @board[13] = 0
@player_to_move = BOTTOM
end

def play_game( bottom, top )
reset

bottom.side = BOTTOM
top.side = TOP
top.game = bottom.game = self

puts bottom.name+' starts...'
display

until game_over?
puts ''
if @player_to_move == TOP
move = top.choose_move
puts top.name+' choose move '+move.to_s
else
move = bottom.choose_move
puts bottom.name+' choose move '+move.to_s
end
make_move( move )
display
end

[top_score, bottom_score]
end
end

p1 = Player.new( 'Player 1' )
p2 = Player.new( 'Player 2' )
KalahMatch.new.start( p1, p2 )
 
A

Adam Shelly

Unless I'm really misreading the rules, there's a bug in the KalahGame clas=
s:

def play_game( bottom, top )
reset ## Play the game here...
[top_score, bottom_score]
end

It's returning the scores in the reverse order of the players..
So in KalahMatch, it reports the wrong winnner:
puts '=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D GAME 1 =3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D'
p1_score_1, p2_score_1 =3D KalahGame.new.play_gam=
e( p1, p2 )

I think the last line of KalahGame#play_game should be:
[bottom_score, top_score]

-Adam
 
J

James Edward Gray II

Unless I'm really misreading the rules, there's a bug in the
KalahGame class:

def play_game( bottom, top )
reset ## Play the game here...
[top_score, bottom_score]
end

It's returning the scores in the reverse order of the players..
So in KalahMatch, it reports the wrong winnner:
puts '========== GAME 1 =========='
p1_score_1, p2_score_1 =
KalahGame.new.play_game( p1, p2 )

I think the last line of KalahGame#play_game should be:
[bottom_score, top_score]

I agree. That looks like a bug.

Thanks for pointing it out.

James Edward Gray II

P.S. If anyone enhances the game engine and wants to share the
changes, I don't consider that a spoiler...
 
K

Kero

I agree. That looks like a bug.

You want bugs? There's bttom or bottm somewhere in the code.
 
B

Bill Guindon

You want bugs? There's bttom or bottm somewhere in the code.

Yep, in the 'winner' code:

def winner
top, bottom =3D top_score, bottom_score
if top > bottm
 
J

James Edward Gray II

Yep, in the 'winner' code:

def winner
top, bottom = top_score, bottom_score
if top > bottm

Ah yes. That's another one. Thanks you two.

James Edward Gray II
 
D

David Balmain

Could we add this enhancement. It makes searching a lot easier.

class KalahGame
attr_reader :board, :player_to_move

def initialize_copy(other_game)
super
@board =3D other_game.board.dup
end
end

Cheers,
Dave
 
J

James Edward Gray II

I think one should use symbols :)top :bottom) instead
of constants like TOP = 1...

While that probably is more Rubyish, let's try to avoid style-only
changes, just so we're not forcing people to download the code again
and break their solutions.

James Edward Gray II
 
B

Benedikt Heinen

Rob, I think you forgot the code.

I don't think he did - there is a solution.tar.gz attached to his mail:

beh@myhost:/tmp/sol $ tar xfvz ~/solution.tar.gz
match.rb
players.rb
state.rb
strategies.rb
beh@myhost:/tmp/sol $ wc *.rb
176 526 4122 match.rb
107 263 2159 players.rb
198 587 4226 state.rb
44 110 978 strategies.rb
525 1486 11485 total
beh@myhost:/tmp/sol $


Looks fine from here... ;-)

Benedikt

ALLIANCE, n. In international politics, the union of two thieves who
have their hands so deeply inserted in each other's pockets that
they cannot separately plunder a third.
(Ambrose Bierce, The Devil's Dictionary)
 
D

David Balmain

Hi Rob,

To you only.

Looks like you are setting up a nice little framework there. Since you
are going to the effort, you might want to have a look at my solution;

MyPlayer won the match: 71-25
MyPlayer took 2.249866 seconds, Standard took 93.019248 seconds

Not sending this to brag. Actually, I think your code is a lot nicer.
I'm betting James will just ignore my solution in his quiz summary
again. Fair enough too. It's not very rubyish and it is a bit complex
but it does a good job. If you'd like to clean it up and incorporate
it into your framework, please do. And since you are using gdbm, maybe
you'll even be able to get my transposition tables to work. Currently
I have to refresh them each turn (which would be completely pointless
if I wasn't using MTD(f)). If you want to read more about the MTD(f)
algorithm I found a good explanation here;

http://www.cs.vu.nl/~aske/mtdf.html

Anyway, hopefully my code will be of interest to someone. ;-)

Cheers,
Dave

PS: if you didn't find my solution in the mailing list, it's here;

http://www.davebalmain.com/pages/kalah
 
D

David Balmain

Whoops, that was supposed to be to Rob only. :p


Errr.... Since it went out to the world I just want to be clear on one
thing. The point I was trying to make about not being included in the
quiz summary was that my solution isn't very Rubyish and is more
interesting from and algorithms perspective than a coding perspective.
I hope that's clear. :-\

Damn, how embarrassing.
 
S

Stephen Waits

Anyway, hopefully my code will be of interest to someone.

Dave,

I should have let you know when I first saw your solution, but I
found it very interesting. I only briefly looked at your code, but
am really thankful that you pointed me to the MTD(f) algorithm. The
last time I looked at dealing with game move trees, this algorithm
wasn't around, and I probably wouldn't have learned about it were it
not for your Solution.

Thanks,
Steve
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,755
Messages
2,569,537
Members
45,023
Latest member
websitedesig25

Latest Threads

Top