From: David Balmain <dbalmain.ml@...>
Date: 2005-12-12T12:44:11+09:00
Subject: [QUIZ][SOLUTION] Kalah (#58)

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