Forum: Ruby Kalah (#58)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2005-12-09 14:30
(Received via mailing list)
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[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 )
Ddbfebb47432f6599da361df6a135c7c?d=identicon&s=25 adam.shelly (Guest)
on 2005-12-09 19:31
(Received via mailing list)
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
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2005-12-09 19:48
(Received via mailing list)
On Dec 9, 2005, at 12:26 PM, Adam Shelly 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 Gray II

P.S.  If anyone enhances the game engine and wants to share the
changes, I don't consider that a spoiler...
Dd54c22454b4e3c21cadf3bdb5192e28?d=identicon&s=25 kero (Guest)
on 2005-12-09 20:31
(Received via mailing list)
> I agree.  That looks like a bug.

You want bugs? There's bttom or bottm somewhere in the code.
Ff63c03fd68754adbadd2c6314646bef?d=identicon&s=25 Bill Guindon (agorilla)
on 2005-12-09 21:00
(Received via mailing list)
On 12/9/05, Kero <kero@chello.single-dot.nl> 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
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2005-12-09 22:01
(Received via mailing list)
On Dec 9, 2005, at 1:57 PM, Bill Guindon wrote:

> On 12/9/05, Kero <kero@chello.single-dot.nl> 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 Gray II
280b41a88665fd8c699e83a9a25ef949?d=identicon&s=25 steve (Guest)
on 2005-12-09 22:42
(Received via mailing list)
James Edward Gray 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
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2005-12-09 22:54
(Received via mailing list)
On Dec 9, 2005, at 3:40 PM, Stephen Waits wrote:

> James Edward Gray 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 Gray II
B5e329ffa0cc78efbfc7ae2d084c149f?d=identicon&s=25 dbalmain.ml (Guest)
on 2005-12-10 04:13
(Received via mailing list)
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
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2005-12-10 04:25
(Received via mailing list)
On Dec 9, 2005, at 9:09 PM, David Balmain 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 Gray II
B5e329ffa0cc78efbfc7ae2d084c149f?d=identicon&s=25 dbalmain.ml (Guest)
on 2005-12-10 04:37
(Received via mailing list)
On 12/10/05, James Edward Gray II <james@grayproductions.net> 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. :)

Cheers,
Dave
C61aed46b48311ca90c2d4e9a3b10757?d=identicon&s=25 jannis (Guest)
on 2005-12-10 12:01
(Received via mailing list)
I think one should use symbols (:top :bottom) instead
of constants like TOP = 1...
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2005-12-10 15:54
(Received via mailing list)
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 Gray II
114892d0cdbc61d4e686dac70495a22b?d=identicon&s=25 Rob Leslie (Guest)
on 2005-12-12 10:25
(Received via mailing list)
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)'
Af95bdaf87958c40150b813e94381bfd?d=identicon&s=25 Christer Nilsson (christer)
on 2005-12-12 10:35
Rob, I think you forgot the code.

Christer
13d7ad3eff474924d5c38209a821e571?d=identicon&s=25 Benedikt Heinen (Guest)
on 2005-12-12 11:44
(Received via mailing list)
On Mon, 12 Dec 2005, Christer Nilsson 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... ;-)

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)
Af95bdaf87958c40150b813e94381bfd?d=identicon&s=25 Christer Nilsson (christer)
on 2005-12-12 11:52
Ach, I'm using http://www.ruby-forum.com
so I did not see the attachment...

Christer
Af95bdaf87958c40150b813e94381bfd?d=identicon&s=25 Christer Nilsson (christer)
on 2005-12-12 12:04
Strange,

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

http://groups.google.com/group/comp.lang.ruby/brow...

either.

Christer
B5e329ffa0cc78efbfc7ae2d084c149f?d=identicon&s=25 David Balmain (Guest)
on 2005-12-12 13:14
(Received via mailing list)
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
B5e329ffa0cc78efbfc7ae2d084c149f?d=identicon&s=25 David Balmain (Guest)
on 2005-12-12 13:35
(Received via mailing list)
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.
280b41a88665fd8c699e83a9a25ef949?d=identicon&s=25 Stephen Waits (Guest)
on 2005-12-12 16:21
(Received via mailing list)
On Dec 12, 2005, at 4:09 AM, David Balmain 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
B5e329ffa0cc78efbfc7ae2d084c149f?d=identicon&s=25 David Balmain (Guest)
on 2005-12-12 17:09
(Received via mailing list)
On 12/13/05, Stephen Waits <steve@waits.net> wrote:
> 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.

Great :-)
I only learned about it over the weekend too. I'm hoping someone will
be able to improve on my solution. Game playing algorithms can be a
lot of fun. I wish I had more time to play around with stuff like
this.

Dave
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2005-12-12 19:58
(Received via mailing list)
On Dec 12, 2005, at 6:33 AM, David Balmain wrote:

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

No worries, you didn't offend me.  ;)

There's no real science about how I choose a solution to discuss.  I
read them all and when one inspires me, I talk about it.  Very
systematic, as you can see.  ;)

I will tell you that I notice I'm getting pickier and pickier about
code length though.  I'm certainly not looking to encourage golf
(that's pretty much the opposite of what Ruby Quiz stands for) and
I'm not trying to slack off on summary work, but I truly believe
correct Ruby involves "Writing less code."

So a good tip for catching my eye is not using five lines when two
will do.  Sprinkle in a few clever Ruby style idioms and you've got a
better than average chance of getting singled out.

Just FYI.

James Edward Gray II
Fd22ee3cfc7dac283ce8e451af324f7d?d=identicon&s=25 Chad Perrin (Guest)
on 2005-12-12 22:04
(Received via mailing list)
On Tue, Dec 13, 2005 at 03:57:10AM +0900, James Edward Gray II wrote:
>
> I will tell you that I notice I'm getting pickier and pickier about
> code length though.  I'm certainly not looking to encourage golf
> (that's pretty much the opposite of what Ruby Quiz stands for) and
> I'm not trying to slack off on summary work, but I truly believe
> correct Ruby involves "Writing less code."

If you have to rewrite something three times to get it down to two lines
instead of five (as typically happens in golf), you're not "writing less
code" anyway.  Rewriting it once to idiomize the code in a Rubylike
style to make it more readable and maintainable can reduce the amount of
code needed to maintain it later, so it's sorta like an investment, so
if rewriting it once to get five lines down to three in a Rubylike style
is probably worth being called "writing less code", but golf, I would
say is not: it's gratuitous.

That's not to say I think golf is bad.  Gratuitous stuff like that can
be highly entertaining.  It's just not the same as "writing less code".

In other words, I definitely tend to like the way you handle it.

Apparently, being a little sick has given me diarrhea of the mouth.
Forgive my rambling.

--
Chad Perrin [ CCD CopyWrite | http://ccd.apotheon.org ]

unix virus: If you're using a unixlike OS, please forward
this to 20 others and erase your system partition.
B5e329ffa0cc78efbfc7ae2d084c149f?d=identicon&s=25 David Balmain (Guest)
on 2005-12-13 04:35
(Received via mailing list)
On 12/13/05, James Edward Gray II <james@grayproductions.net> wrote:
> There's no real science about how I choose a solution to discuss.  I
> will do.  Sprinkle in a few clever Ruby style idioms and you've got a
> better than average chance of getting singled out.

Cool. And this is the way it should be. That's the reason I read your
summary every week. I use different resources for finding out the
latest and greatest algorithms. Anyway, I can't wait for the book. 3
months to go. :-)
Ddbfebb47432f6599da361df6a135c7c?d=identicon&s=25 Adam Shelly (Guest)
on 2005-12-14 07:16
(Received via mailing list)
I ran a big tournament with discouraging results:
Dave scored 1057 points in 409.138 seconds
AHistoryKalahPlayer scored 893 points in 512.221 seconds
RemoveRightKalahPlayer scored 892 points in 0.061 seconds
APessimisticKalahPlayer scored 807 points in 1735.01 seconds
DeepScoreKalahPlayer scored 789 points in 0.296 seconds
StandardPlayer scored 757 points in 4310.645 seconds
CachingPlayer scored 754 points in 4560.485 seconds
ScoreKalahPlayer scored 735 points in 0.139 seconds
ThreadedPlayer scored 621 points in 3582.531 seconds
RemoveRandomLowKalahPlayer scored 516 points in 0.031 seconds
RemoveRandomHighKalahPlayer scored 482 points in 0.032 seconds
RandomPlayer scored 480 points in 0.0 seconds
RemoveHighKalahPlayer scored 454 points in 0.03 seconds
Player scored 433 points in 0.016 seconds
RemoveLowKalahPlayer scored 410 points in 0.0 seconds

I've had no luck improving my "smart" algorithms, so I'm submitting
this new player.
Wins every time.

class Cheater < Player
  def choose_move
    k = (@side==KalahGame::TOP) ? 13 : 6
    @game.board.each_index {|i|
      unless  [6,13].include? i
        @game.board[k]+=@game.board[i]
        @game.board[i]=0
      end
    }
    @game.board[k]-=1
    @game.board[k-1]=1
    k-1
  end
end

-Adam
This topic is locked and can not be replied to.