いものやま。

雑多な知識の寄せ集め

変種オセロを考えてみた。(その3)

昨日の続き。

今日は残りの詳細な処理について。

ボードの実装(続き)

走査メソッド

まずおさえておきたいのが、走査メソッド

    # 続き

    private

    def traverse_to(row, col, direction, &block)
      # NOTE:
      # 'traverse_to' accesses to 'WALL',
      # so 'color' cannot be used.
      traverse_row = row + direction[0]
      traverse_col = col + direction[1]
      traverse_color = @board[traverse_row][traverse_col]
      step_count = 1
      while (traverse_color != WALL) && (traverse_color != EMPTY)
        block.call(step_count, traverse_row, traverse_col, traverse_color)
        traverse_row += direction[0]
        traverse_col += direction[1]
        traverse_color = @board[traverse_row][traverse_col]
        step_count += 1
      end
    end

    # 続く

これは、ブロックを伴うメソッドで、指定された位置から指定された方向に向かって1マスずつブロックを実行していく。

オセロの場合、8方向にそれぞれ処理を進めていくことが多く、ベタに書くと次のようなコードになりがち。

# 上方向
traverse_row = row - 1
traverse_color = @board[traverse_row][col]
while (traverse_color != WALL) && (traverse_color != EMPTY)
  # なんか処理
  traverse_row -= 1
  traverse_color = @board[traverse_row][col]
end

# 右上方向
traverse_row = row - 1
traverse_col = col + 1
traverse_color = @board[traverse_row][traverse_col]
while (traverse_color != WALL) && (traverse_color != EMPTY)
  # なんか処理(やることは上方向のときと同じ)
  traverse_row -= 1
  traverse_col += 1
  traverse_color = @board[traverse_row][traverse_col]
end

# 以下、同じように、右、右下、下、左下、左、左上、と書いていく

これだけでもかなり冗長な感じがあるけれど、これをさらに「なんか処理」ごとに書いたりすると、さらに冗長に。

そこで行う工夫が、走査方向をdirectionという差分を表したベクトルで渡して、それを足しこんでいくようにする方法。
そうすることで、同じようなコードを何度も書かなくて済むようになる。
さらに、ブロック(Cの場合なら関数ポインタ)を渡すようなインタフェースにすることで、走査のときに行う処理をブロックに委譲することが出来る。
これでさらにコードがシンプルに。

もう一つ注目したいのが、番兵(WALL)を使う点。

配列にアクセスするときに気をつけないといけないのが、範囲外アクセス。
それをしないようにするためには、基本的にはまず指定されたインデックスが範囲内かを調べないといけないのだけど、そうすると、

  1. インデックスのチェック
  2. 問題なければ配列の要素にアクセス
  3. 配列の要素をチェック

というふうに、ワンクッションおく必要が出てくる。

これが、番兵を置くようにすると、

  1. とりあえず配列の要素にアクセス
  2. 配列の要素をチェック

というふうに、シンプルに書くことが出来るようになる。
これもプログラムを書くときによく使われるので、覚えておきたい手法の一つ。
この記事で、一番最初のprev_tag_sizeに0が入っているのも、一種の番兵)

合法手を実行するための各メソッド

まずは、合法手を実行するための各メソッド
これらは、新しく生成されたオブジェクトに対して呼び出されるので、可視性がprotectedとなってる。
(新しく生成されたオブジェクトに現在のボードの内容をコピーするcopyだけはprivate)

    # 続き

    protected

    def put_piece(row, col)
      @board[row][col] = @turn

      color_diff = (@turn == BLACK) ? -1 : +1
      Direction.each do |direction|
        if has_color_from_to?(row, col, direction)
          traverse_to(row, col, direction) do |step_count, traverse_row, traverse_col, traverse_color|
            if traverse_color == @turn
              break
            else
              @board[traverse_row][traverse_col] += color_diff
            end
          end
        end
      end
    end

    def change_turn
      @turn = self.opponent
    end

    def change_token
      @token += (@turn == BLACK) ? +1 : -1
    end

    def add_move
      @move += 1
    end

    private

    def copy(other)
      (ROW_MIN..ROW_MAX).each do |row|
        (COL_MIN..COL_MAX).each do |col|
          @board[row][col] = other.color(row, col)
        end
      end
      @move = other.move
      @turn = other.turn
      @token = other.token
    end

    # 続く

まず、YWF::Board#put_piece。
これは、指定された位置に石を置き(あるいは指定された位置の灰色の石を手番の色に変え)、挟まれた石の色を変えていくメソッド

行ってる処理は、まずは指定された場所の色を変え、そのあと、各方向について、もしその方向に同じ色の石があるのなら、同じ色が見つかるまで色を変えていくというもの。
ここでさっそく、先ほどのtraverse_toを使ってる。
traverse_toのおかげで、すごくシンプルでしょ?

なお、color_diffというのは、

  • 黒(1)で挟まれると灰色(2)が黒(1)に、白(3)が灰色(2)になる
  • 白(3)で挟まれると灰色(2)が白(3)に、黒(1)が灰色(2)になる

ということから、手番が黒なら挟まれた各色に対して-1を、そうでなければ+1をすればいい、ということを利用したもの。

他のYWF::Board#change_turn、YWF::Board#change_token、YWF::Board#add_move、それとにcopyついては、特に説明は不要かな?

合法手のチェックするための各メソッド

最後に、合法手のチェックをするためのprivateメソッド

    # 続き

    def has_color_from?(row, col)
      Direction.each do |direction|
        if has_color_from_to?(row, col, direction)
          return true
        end
      end
      return false
    end

    def has_color_from_to?(row, col, direction)
      traverse_to(row, col, direction) do |step_count, traverse_row, traverse_col, traverse_color|
        if traverse_color == @turn
          if step_count == 1
            return false
          else
            return true
          end
        end
      end
      return false
    end
  end
end

has_color_from?は、指定された位置から8方向のいずれかに手番の色があるかをチェックするメソッド
そして、has_color_from_to?は、指定された位置から指定された方向に手番の色があるかをチェックするメソッド

has_color_from?は、各方向についてhas_color_from_to?を呼び出しているだけなので、重要なのはhas_color_from_to?の方。
そして、has_color_from_to?では、見ての通り、traverse_toを使ってる。

一つ気をつけたい(というか、実際にミスした)のが、たとえ手番と同じ色を見つけたとしても、現在の位置から1つしか離れていない場合、間に他の色が挟まっていないので、ダメだということ。
なので、traverse_colorが手番の色だとしても、step_countが1ならfalseを返す必要がある。

これでボードの実装はとりあえずオシマイ。
次は、実際に人同士がこのゲームを遊べるようにしていく。

今日はここまで!