Forum: Ruby [SOLUTION] 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.
B5e329ffa0cc78efbfc7ae2d084c149f?d=identicon&s=25 David Balmain (Guest)
on 2005-12-12 04:45
(Received via mailing list)
Hey guys,

Here's my solution to this weeks Ruby quiz. I used the MTD(f) algorithm.

http://en.wikipedia.org/wiki/MTD%28f%29

Unfortunately I couldn't seem to get my transposition tables to work
correctly. The garbage collector kept crashing. I think that to get a
solution like this to work well you need to store the transposition
tables on disk. Pity I haven't finished cFerret yet.

By the way, I'm afraid my solution probably isn't very Rubyish. You
can probably tell I've been doing a lot of C coding lately. If anyone
wants to clean it up and improve it, please do and let me know about
it. :-)

Looking forward to seeing some other solutions.

Cheers,
Dave

See a syntax coloured version here;

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


require 'player'

class Dave < Player
  START_BOARD = [4,4,4,4,4,4,0,4,4,4,4,4,4,0]

  Bounds = Struct.new(:lower, :upper, :lower_move, :upper_move)

  def initialize(name, depth = [6,8])
    super(name)
    @depth = depth
    @guess = 0
    @transposition_table = {}
    @previous_transposition_table = {}
  end

  def choose_move
    board = @game.board
    # start move is always the same;
    if board == START_BOARD
      # we are first to go
      @guess = 8
      @move_list = [5]
      return 2
    elsif board[13] == 0 and @game.player_to_move == KalahGame::TOP
      # we are second to go
      @guess = -9
      return 9 if board[9] == 4
      return 8
    end


    return @move_list.pop if @move_list and @move_list.size > 0

    # If the next move is from the top then we rotate the board so that
all
    # operations would be the same as if we were playing from the bottom
    if (@game.player_to_move == KalahGame::TOP)
      # We do iterative deepening here. Unfortunately, due to memory
      # constraints, the transpositon table has to be reset every turn
so we
      # can't go very deep. For a depth of 8, one step seems to be the
same as
      # two but we'll keep it for demonstration purposes.
      @depth.each do |depth|
        @guess, @move_list = mtdf(board[7,7] + board[0,7], @guess,
depth)
        @previous_transposition_table = @transposition_table
        @transposition_table = {}
      end
      @move_list.size.times {|i| @move_list[i] += 7}
    else
      @depth.each do |depth|
        @guess, @move_list = mtdf(board.dup, @guess, depth)
        @previous_transposition_table = @transposition_table
        @transposition_table = {}
      end
    end
    return @move_list.pop
  end

  def make_move(move, board)
    stones = board[move]
    board[move] = 0

    pos = move
    while stones > 0
      pos += 1
      pos = 0 if pos==13
      board[pos] += 1
      stones -= 1
    end

    if(pos.between?(0,5) and board[pos] == 1)
      board[6] += board[12-pos] + 1
      board[12-pos] = board[pos] = 0
    end
    board
  end

  def game_over?(board)
    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 game_over_score(board)
    score = 0
    (0.. 6).each { |i| score += board[i] }
    (7..13).each { |i| score -= board[i] }
    return score
  end

  def mtdf(game, guess, depth)
    upper =  1000
    lower = -1000
    move = -1

    begin
      alpha = (guess == upper) ? guess - 1 : guess
      guess, move = alpha_beta(game, alpha, alpha + 1, depth)
      if guess > alpha
        best_move = move
        lower = guess
      else
        upper = guess
      end
    end while lower < upper

    return guess, best_move
  end

  def alpha_beta(board, lower, upper, depth)
    # Check the transposition table to see if we've tried this board
before
    if (bounds = @transposition_table[board])
      return bounds.lower, bounds.lower_move if bounds.lower >= upper
      return bounds.upper, bounds.upper_move if bounds.upper <= lower

      # last time we were with these bounds so use the same position
that we
      # found last time
      first_move = (bounds.upper_move||bounds.lower_move).last
    else
      # We haven't tried this board before during this round
      bounds = @transposition_table[board] = Bounds.new(-1000, 1000,
nil, nil)

      # If we tried this board in a previous round see what move was
found to
      # be the best. We'll try it first.
      if (prev_bounds = @previous_transposition_table[board])
        first_move =
(prev_bounds.upper_move||prev_bounds.lower_move).last
      end
    end

    if (game_over?(board))
      guess = game_over_score(board)
      best = []
    elsif (depth == 0)
      guess = board[6] - board[13]
      best = []
    else
      best = -1
      guess = -1000
      moves = []

      (0..5).each do |i|
        next if board[i] == 0
        if board[i] == 6-i
          moves.unshift(i)
        else
          moves.push(i)
        end
      end
      # move the previous best move for this board to the front
      if first_move and first_move != moves[0]
        moves.delete(first_move)
        moves.unshift(first_move)
      end

      moves.each do |i|
        next_board = make_move(i, board.dup)
        if board[i] == 6-i
          next_guess, move_list = alpha_beta(next_board, lower, upper,
depth)
        else
          next_guess, = alpha_beta(next_board[7,7] + next_board[0,7],
                                   0-upper, 0-lower, depth - 1)

          next_guess *= -1
          move_list = []
        end
        if (next_guess > guess)
          guess = next_guess
          best = move_list + [i]
          # beta pruning
          break if (guess >= upper)
        end
        #lower = guess if (guess > lower)
      end
    end

    # record the upper or lower bounds for this position if we have
found a
    # new best bound
    if guess <= lower
      bounds.upper = guess
      bounds.upper_move = best
    end
    if guess >= upper
      bounds.lower = guess
      bounds.lower_move = best
    end
    return guess, best
  end
end
Ddbfebb47432f6599da361df6a135c7c?d=identicon&s=25 Adam Shelly (Guest)
on 2005-12-12 21:28
(Received via mailing list)
Here are my Kalah Players.
My first trick was to create subclass of Player so that my players are
always playing from bins 0..5.  This got rid of a lot of messy
conditions. It also contains a move simulator.

AdamsPlayers.rb contains some very simple test players, as well as 2
reasonably good players:
DeepScoreKalahPlayer tries to find the biggest gain in points for a
single move, and APessimisticKalahPlayer does the same, but subtracts
the opponent's best possible next move.

AHistoryPlayer.rb contains a player which ranks the results of each
move, and keeps a history.  The idea is that the more it plays, the
less likely it is to choose bad moves.
It stores the history in a Yaml file, which definitely causes a
slowdown as it gets bigger.
That's one thing I'd like to improve if I have time.  I also added a
line to the game engine to report the final score back to the players.
 AHistoryPlayer still works without it, but it's less accurate I
think, since it never records the final result.

None of these players pay much attention to the number of stones
remaining on the opponent's side, which is one factor in why they fail
miserably against Dave's player.  But they do tend to beat Rob's
players.  I'm hoping some more people submit solutions.

Add your players to TestMatch.rb to run them in a roundRobin

-Adam
Ddbfebb47432f6599da361df6a135c7c?d=identicon&s=25 Adam Shelly (Guest)
on 2005-12-12 23:25
(Received via mailing list)
Of course I introduced an error while cleaning up my code:
That will teach me to skip unit tests...

in AdamsPlayers.rb, line 111
			i = best_move(b) if taketurn
should be
			m = best_move(b) if taketurn

-Adam.
Ddbfebb47432f6599da361df6a135c7c?d=identicon&s=25 Adam Shelly (Guest)
on 2005-12-12 23:59
(Received via mailing list)
Not strictly quiz related, but why do my emails to the list get have
certain characters garbled when they are added to the ruby-talk
archives (linked from the ruby quiz site)?

My post at
http://www.ruby-talk.org/cgi-bin/scat.rb/ruby/ruby...
has =09 in place of tabs and =3D instead of equals.

Or at least that's what I see. I'm not even sure if it's a problem
with the mail I send from gmail, or with my browser settings viewing
the archive...
Any Ideas?

Thanks,
-Adam
912c61d9da47754de7039f4271334a9f?d=identicon&s=25 unknown (Guest)
on 2005-12-13 00:26
(Received via mailing list)
Quoting Adam Shelly <adam.shelly@gmail.com>:

> My post at
> http://www.ruby-talk.org/cgi-bin/scat.rb/ruby/ruby...
> has =09 in place of tabs and =3D instead of equals.

As far as I can see, it's because the archive software doesn't
implement MIME completely enough.  For some "interesting" messages,
it seems to just dump the raw message rather than decoding it.

-mental
1b62a85b59ccab03b84ee5ec378f75b4?d=identicon&s=25 Steve Litt (Guest)
on 2005-12-13 02:38
(Received via mailing list)
On Monday 12 December 2005 05:24 pm, Adam Shelly wrote:
> Of course I introduced an error while cleaning up my code:
> That will teach me to skip unit tests...

Could you please tell me more about the use of test units?

Thanks

SteveT

Steve Litt
http://www.troubleshooters.com
slitt@troubleshooters.com
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2005-12-13 04:38
(Received via mailing list)
On Dec 12, 2005, at 7:36 PM, Steve Litt wrote:

> On Monday 12 December 2005 05:24 pm, Adam Shelly wrote:
>> Of course I introduced an error while cleaning up my code:
>> That will teach me to skip unit tests...
>
> Could you please tell me more about the use of test units?

If you're looking for a definition, try Wikipedia:

http://en.wikipedia.org/wiki/Unit_testing

If you are curious about Ruby's Unit Test library, it is documented
here:

http://www.ruby-doc.org/stdlib/libdoc/test/unit/rd...

Hope that helps.

James Edward Gray II
B5e329ffa0cc78efbfc7ae2d084c149f?d=identicon&s=25 David Balmain (Guest)
on 2005-12-13 04:45
(Received via mailing list)
Hi Adam,
Just ran a tournament with your players. In case you or anyone else is
interested;

APessimisticKalahPlayer scored 527 points in 2265.782466 seconds
AHistoryKalahPlayer scored 478 points in 98.2062879999999 seconds
RemoveRightKalahPlayer scored 469 points in 0.004744 seconds
DeepScoreKalahPlayer scored 460 points in 0.055886 seconds
ScoreKalahPlayer scored 450 points in 0.020305 seconds
RemoveRandomLowKalahPlayer scored 312 points in 0.012781 seconds
RemoveRandomHighKalahPlayer scored 309 points in 0.013103 seconds
RemoveHighKalahPlayer scored 264 points in 0.005501 seconds
RemoveLowKalahPlayer scored 187 points in 0.007318 seconds

Cheers,
Dave
Ddbfebb47432f6599da361df6a135c7c?d=identicon&s=25 Adam Shelly (Guest)
on 2005-12-13 07:12
(Received via mailing list)
Cool.
I'm suprised RemoveRight did better than DeepScore.
I was looking more at HistoryPlayer, (which should do better than
Pessimistic, since it uses the same choice for any unknown situations)
and I realized that when scoring a move, it is giving too much weight
to the subsequent turns.   So it can choose the absolute best move on
turn 2, for instance, then make a bad move 3 turns later, and end up
ranking the turn 2 choice as the worst possibility.  So for now, the
history information it keeps is mostly useless, except for a speedup.
 My history algorithm needs some tuning (if it can be salvaged at all
:)

I'd be curious to see what happens if you add the other submitted
players to the tournament.  Can you post the tourney framework?

-Adam
B5e329ffa0cc78efbfc7ae2d084c149f?d=identicon&s=25 David Balmain (Guest)
on 2005-12-13 08:12
(Received via mailing list)
On 12/13/05, Adam Shelly <adam.shelly@gmail.com> wrote:
> :)
>
> I'd be curious to see what happens if you add the other submitted
> players to the tournament.  Can you post the tourney framework?

It's just a simple hack. I've attached the code. I changed your
HistoryPlayer to use classname as the default name in the initializer
so you'll need to make that change too to get it to work.

Enjoy,
Dave
1b62a85b59ccab03b84ee5ec378f75b4?d=identicon&s=25 Steve Litt (Guest)
on 2005-12-13 13:58
(Received via mailing list)
On Monday 12 December 2005 10:36 pm, James Edward Gray II wrote:
> On Dec 12, 2005, at 7:36 PM, Steve Litt wrote:
> > On Monday 12 December 2005 05:24 pm, Adam Shelly wrote:
> >> Of course I introduced an error while cleaning up my code:
> >> That will teach me to skip unit tests...
> >
> > Could you please tell me more about the use of test units?
>
> If you're looking for a definition, try Wikipedia:
>
> http://en.wikipedia.org/wiki/Unit_testing

Ahhhh, I've always called those things "test jigs". Thanks.
>
> If you are curious about Ruby's Unit Test library, it is documented
> here:
>
> http://www.ruby-doc.org/stdlib/libdoc/test/unit/rd...

I'm gonna actually have to see some real code with the Ruby unit test.
The
preceding URL makes it look harder and more cumbersome than just writing
a
subroutine to exercise your new class.

Thanks

SteveT

Steve Litt
http://www.troubleshooters.com
slitt@troubleshooters.com
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2005-12-13 14:55
(Received via mailing list)
On Dec 13, 2005, at 6:55 AM, Steve Litt wrote:

> I'm gonna actually have to see some real code with the Ruby unit test.

There are many examples on the Ruby Quiz site.

Rubyforge would also be an excellent place to search.  I can tell you
at least two projects that have a complete test suit (because they
are mine):  HighLine and FasterCSV.  Download the source and take a
peak.

James Edward Gray II
This topic is locked and can not be replied to.