Kalah (#58)

The three rules of Ruby Q.:

  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 Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

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

by Mark Van H.

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[i]
	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[i] > 0 }
		(0..5).each { |i| bottom = false if @board[i] > 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[i] }
		score
	end

	def bottom_score
		score = 0
		(0..6).each { |i| score += @board[i] }
		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[i].to_s+'  ' }
		puts top
		puts @board[13].to_s + '                     ' + @board[6].to_s
		bottom = '    '
		(0..5).each { |i| bottom += @board[i].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 )

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]

-Adam

On Dec 9, 2005, at 12:26 PM, Adam S. wrote:

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 G. II

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

On 12/9/05, Kero [email protected] wrote:

I agree. That looks like a bug.

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

Yep, in the ‘winner’ code:

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

I agree. That looks like a bug.

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

On Dec 9, 2005, at 1:57 PM, Bill G. wrote:

On 12/9/05, Kero [email protected] wrote:

I agree. That looks like a bug.

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

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 G. II

James Edward G. II wrote:

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

Is there a place where we can easily grab the most recent version?

Thanks,
Steve

On Dec 9, 2005, at 3:40 PM, Stephen W. wrote:

James Edward G. II wrote:

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

Is there a place where we can easily grab the most recent version?

Sure. I’ve put it up here:

http://rubyquiz.com/KalahMatch.rb

James Edward G. II

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 = other_game.board.dup
end

end

Cheers,
Dave

On 12/10/05, James Edward G. II [email protected] wrote:

end

end

I’m pretty sure I did what you wanted. Double check me please.

http://rubyquiz.com/KalahMatch.rb

Perfect. Thanks. Sorry I wasn’t very clear. :slight_smile:

Cheers,
Dave

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

On Dec 9, 2005, at 9:09 PM, David B. wrote:

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 = other_game.board.dup
end

end

I’m pretty sure I did what you wanted. Double check me please.

http://rubyquiz.com/KalahMatch.rb

James Edward G. II

On Dec 10, 2005, at 5:00 AM, Jannis Harder wrote:

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 G. II

Rob, I think you forgot the code.

Christer

Here’s my solution. I’m still playing with it, but I’m posting it now
for the benefit of others to look at.

The solution is divided into strategies and players. Strategies are
used to estimate the value of any particular board configuration to a
player without any deep recursion or other lengthy operations. The
only strategy I have now is BasicStrategy.

Players implement a tactic for finding the best move based on the
strategy. StandardPlayer uses a 6-ply alpha-beta search, and plays
fairly well. The ply depth can be changed by modifying the DEPTH
constant.

ThreadedPlayer is an experimental time-limited player using a
multithreaded search. It doesn’t tend to play as well or as fast as
StandardPlayer. CachingPlayer is an experimental GDBM-based caching
player I wrote in an attempt to improve StandardPlayer’s performance.

RandomPlayer simply plays random moves, and has been useful for testing.

To play, you can:

ruby -r ./match.rb -e ‘run(StandardPlayer, RandomPlayer)’

Ach, I’m using http://www.ruby-forum.com
so I did not see the attachment…

Christer

On Mon, 12 Dec 2005, Christer N. wrote:

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… :wink:

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)

Strange,

I didn’t get the email and the contribution by Rob is not available at

http://groups.google.com/group/comp.lang.ruby/browse_thread/thread/687c4a8c70e6753c/c7cb35eea87ea78f?q=kalah&rnum=1#c7cb35eea87ea78f

either.

Christer

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. :wink:

Cheers,
Dave

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

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

On Dec 12, 2005, at 4:09 AM, David B. wrote:

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