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.
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.
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
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
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
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
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
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.
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
···
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...
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;
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.
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)
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.
···
On 12/12/05, David Balmain <dbalmain.ml@gmail.com> wrote:
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;
On 12/12/05, Rob Leslie <rob@mars.org> wrote:
> 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)'
>
>
>
>
> --
> Rob Leslie
> rob@mars.org
>
>
>
>
>
>
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
···
On Dec 12, 2005, at 4:09 AM, David Balmain wrote:
Anyway, hopefully my code will be of interest to someone.
> 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.
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
···
On 12/13/05, Stephen Waits <steve@waits.net> wrote:
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
···
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. :-\
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.
···
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."
> 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.
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.
···
On 12/13/05, James Edward Gray II <james@grayproductions.net> wrote:
