[QUIZ] Kalah (#58)

Discussion in 'Ruby' started by Ruby Quiz, Dec 9, 2005.

  1. Ruby Quiz

    Ruby Quiz Guest

    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 )
    Ruby Quiz, Dec 9, 2005
    #1
    1. Advertising

  2. Ruby Quiz

    Adam Shelly Guest

    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
    Adam Shelly, Dec 9, 2005
    #2
    1. Advertising

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

    > 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...
    James Edward Gray II, Dec 9, 2005
    #3
  4. Ruby Quiz

    Kero Guest

    > I agree. That looks like a bug.

    You want bugs? There's bttom or bottm somewhere in the code.
    Kero, Dec 9, 2005
    #4
  5. Ruby Quiz

    Bill Guindon Guest

    On 12/9/05, Kero <-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 =3D top_score, bottom_score
    if top > bottm

    --
    Bill Guindon (aka aGorilla)
    Bill Guindon, Dec 9, 2005
    #5
  6. On Dec 9, 2005, at 1:57 PM, Bill Guindon wrote:

    > On 12/9/05, Kero <-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
    James Edward Gray II, Dec 9, 2005
    #6
  7. 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
    Stephen Waits, Dec 9, 2005
    #7
  8. 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
    James Edward Gray II, Dec 9, 2005
    #8
  9. 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

    On 12/10/05, James Edward Gray II <> wrote:
    > 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
    >
    >
    David Balmain, Dec 10, 2005
    #9
  10. 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
    James Edward Gray II, Dec 10, 2005
    #10
  11. On 12/10/05, James Edward Gray II <> wrote:
    > 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 =3D other_game.board.dup
    > > 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

    > James Edward Gray II
    >
    >
    David Balmain, Dec 10, 2005
    #11
  12. I think one should use symbols :)top :bottom) instead
    of constants like TOP = 1...

    --
    Jannis
    Jannis Harder, Dec 10, 2005
    #12
  13. 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
    James Edward Gray II, Dec 10, 2005
    #13
  14. Christer Nilsson, Dec 12, 2005
    #14
  15. Re: [SOLUTION] Kalah (#58)

    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)
    Benedikt Heinen, Dec 12, 2005
    #15
  16. Christer Nilsson, Dec 12, 2005
    #16
  17. Christer Nilsson, Dec 12, 2005
    #17
  18. Re: [QUIZ][SOLUTION] Kalah (#58)

    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

    On 12/12/05, Rob Leslie <> 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
    >
    >
    >
    >
    >
    >
    >
    David Balmain, Dec 12, 2005
    #18
  19. Re: [QUIZ][SOLUTION] Kalah (#58)

    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.

    On 12/12/05, David Balmain <> 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;
    >
    > 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
    >
    > On 12/12/05, Rob Leslie <> 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=
    David Balmain, Dec 12, 2005
    #19
  20. Re: [QUIZ][SOLUTION] Kalah (#58)

    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
    Stephen Waits, Dec 12, 2005
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ruby Quiz

    [QUIZ] Animal Quiz (#15)

    Ruby Quiz, Jan 14, 2005, in forum: Ruby
    Replies:
    11
    Views:
    341
    James Edward Gray II
    Jan 18, 2005
  2. David Tran
    Replies:
    9
    Views:
    166
    David Tran
    Jan 21, 2005
  3. David Balmain

    [QUIZ][SOLUTION] Kalah (#58)

    David Balmain, Dec 12, 2005, in forum: Ruby
    Replies:
    9
    Views:
    140
    James Edward Gray II
    Dec 13, 2005
  4. Ruby Quiz

    [SUMMARY] Kalah (#58)

    Ruby Quiz, Dec 15, 2005, in forum: Ruby
    Replies:
    2
    Views:
    101
    James Edward Gray II
    Dec 15, 2005
  5. Replies:
    2
    Views:
    122
    Ezra Zygmuntowicz
    Dec 16, 2005
Loading...

Share This Page