変種オセロを考えてみた。（その2）

ルールは昨日書いた通り。

さっそくSwiftで書き始めてもいいんだけど、いきなり書き始めるのも大変なので、まずは書き慣れたRubyで書いてみて、感触を確かめてみようかなと。

ボードの実装

まずはボードの実装から。

データ構造と初期化

module YWF
  class Board
    ROW_MIN = 1
    ROW_MAX = 9
    COL_MIN = 1
    COL_MAX = 9

    WALL = -1
    EMPTY = 0
    BLACK = 1
    GRAY = 2
    WHITE = 3

    Direction = [
      [-1, -1], [-1,  0], [-1,  1],
      [ 0, -1],           [ 0,  1],
      [ 1, -1], [ 1,  0], [ 1,  1],
    ]

    def initialize(other=nil)
      @board = [
        [WALL, WALL , WALL , WALL , WALL , WALL , WALL , WALL , WALL , WALL , WALL],
        [WALL, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, WALL],
        [WALL, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, WALL],
        [WALL, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, WALL],
        [WALL, EMPTY, EMPTY, EMPTY, GRAY , BLACK, WHITE, EMPTY, EMPTY, EMPTY, WALL],
        [WALL, EMPTY, EMPTY, EMPTY, WHITE, GRAY , BLACK, EMPTY, EMPTY, EMPTY, WALL],
        [WALL, EMPTY, EMPTY, EMPTY, BLACK, WHITE, GRAY , EMPTY, EMPTY, EMPTY, WALL],
        [WALL, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, WALL],
        [WALL, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, WALL],
        [WALL, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, WALL],
        [WALL, WALL , WALL , WALL , WALL , WALL , WALL , WALL , WALL , WALL , WALL],
      ]
      @move = 1
      @turn = BLACK
      @token = GRAY
      if other
        copy(other)
      end
    end
    
    # 続く

ボードのサイズは9x9。

各マスの状態は、空（EMPTY）か、黒（BLACK）か、灰色（GRAY）か、白（WHITE）。
ここで一つ、WALLとあるのは、番兵。
オセロのプログラムを作るときの定番の手法で、外側に壁を用意しておくことで、走査を書きやすくする。

Directionという配列も、走査を書きやすくするためのもの。
具体的な使い方は、このあとのコードで。

そして、初期化メソッド。
インスタンス変数として、各マスの状態（@board）、手数（@move）、手番（@turn）、トークン（@token）を用意しておく。

このトークンというのは、「灰色を自分の色に変えるのは、相手がやった回数より高々1回多い回数まで」というのを分かりやすく表すためのもの。
具体的には、

トークンが灰色のときは、どちらのプレイヤーも灰色を自分の色に変えることが出来る
トークンが灰色のときに灰色を自分の色に変えると、トークンは相手の色になる
トークンが相手の色の場合、灰色を自分の色に変えることは出来ない
トークンが自分の色の場合、灰色を自分の色に変えることが出来る
トークンが自分の色のときに灰色を自分の色に変えると、トークンは灰色に戻る

とすることで、このルールを実現できる。

あと、コピーコンストラクタの役割も持たせるために、もし引数で他のボードが指定されたら、その内容をコピーする。

アクセサ

    # 続き

    attr_reader :move, :turn, :token

    def opponent
      (@turn + 2) % 4
    end

    def color(row, col)
      if (row < ROW_MIN) || (ROW_MAX < row)
        raise "invalid row. [row: #{row}]"
      end
      if (col < COL_MIN) || (COL_MAX < col)
        raise "invalid col. [col: #{col}]"
      end
      @board[row][col]
    end

    def count(color)
      if (color != EMPTY) && (color != BLACK) && (color != GRAY) && (color != WHITE)
        raise "invalid color. [color: #{color}]"
      end

      count = 0
      (ROW_MIN..ROW_MAX).each do |row|
        (COL_MIN..COL_MAX).each do |col|
          if self.color(row, col) == color
            count += 1
          end
        end
      end

      count
    end

    # 続く

次に、アクセサの定義。
基本的に外側から情報を変えられてしまうと困るので、定義するのはリーダのみ。

手数、手番、トークンのリーダは、attr_readerでサクッと定義。
Rubyのこういうところはいいよねw

YWF::Board#opponentというメソッドは、手番じゃないプレイヤーを示すメソッド。
BLACKを1、WHITEを3と定義しているので、それをうまく使ってる。

YWF::Board#colorは、指定されたマスの状態を返すメソッド。
一応、範囲外かどうかをチェックするようにしてある。

YWF::Board#countは、指定された色の数を返すメソッド。
ここでは単に数えてるだけ。

合法手のチェック

    # 続き

    def playable?(row, col)
      if self.color(row, col) != EMPTY
        return false
      end

      has_color_from?(row, col)
    end

    def changeable?(row, col)
      if self.color(row, col) != GRAY
        return false
      end

      if (@token != GRAY) && (@token != @turn)
        return false
      end

      has_color_from?(row, col)
    end

    def must_pass?
      (self.playable_places.size == 0) && (self.changeable_places.size == 0)
    end

    def playable_places
      places = []
      (ROW_MIN..ROW_MAX).each do |row|
        (COL_MIN..COL_MAX).each do |col|
          if self.playable?(row, col)
            places.push [row, col]
          end
        end
      end
      places
    end

    def changeable_places
      places = []
      if @token != opponent
        (ROW_MIN..ROW_MAX).each do |row|
          (COL_MIN..COL_MAX).each do |col|
            if self.changeable?(row, col)
              places.push [row, col]
            end
          end
        end
      end
      places
    end

    def legal_actions
      actions = Array.new
      if self.must_pass?
        actions.push [:pass, nil]
      else
        self.playable_places.each do |place|
          actions.push [:play, place]
        end
        self.changeable_places.each do |place|
          actions.push [:change, place]
        end
      end
      actions
    end

    # 続く

今度は合法手のチェック。

まず、石を置けるかどうかチェックするのが、YWF::Board#playable?。
指定されたマスが空じゃないと石を置けないので、その場合はfalseを返してる。
そして、指定されたマスから8方向に手番プレイヤーと同じ色の石があるかどうかを判断しているのが、has_color_from?というprivateメソッド。
この詳細は後ほど。

同様に、灰色の石を自分の色に変えられるかチェックするのが、YWF::Board#changeable?。
指定されたマスが灰色でなかったり、トークンが相手の色だったりした場合には無理なので、falseを返してる。
そうでない場合、YWF::Board#playable?と同様に、指定されたマスから8方向に手番プレイヤーと同じ色の石があるかどうかを判断して返してる。

そして、石を置くのも灰色の石を変えるのも出来ない場合にのみ、そしてそのときに限り、パスをしなければならないので、そのチェックをしているのがYWF::Board#must_pass?。
すぐ後ろで定義されているYWF::Board#playable_places、YWF::Board#changeable_placesで、石を置ける場所、灰色の石を変えられる場所の配列を取得し、そのサイズをチェックしている。

YWF::Board#legal_actionsは、合法手の配列を返すメソッド。
配列の各要素には、行動の種類を表すシンボル（:passか:playか:change）とその場所が入っている。

合法手の実行

    # 続き

    def play(row, col)
      unless self.playable?(row, col)
        raise "not playable. [row: #{row}, col: #{col}]"
      end

      new_board = self.class.new(self)
      new_board.put_piece(row, col)
      new_board.change_turn
      new_board.add_move

      new_board
    end

    def change(row, col)
      unless self.changeable?(row, col)
        raise "not changeable. [row: #{row}, col: #{col}]"
      end

      new_board = self.class.new(self)
      new_board.put_piece(row, col)
      new_board.change_token
      new_board.change_turn
      new_board.add_move

      new_board
    end

    def pass
      unless self.must_pass?
        raise "cannot pass."
      end

      new_board = self.class.new(self)
      new_board.change_turn
      new_board.add_move

      new_board
    end

    # 続く

そして、合法手の実行。

ここで、方法が2通りあって、

元のオブジェクトのデータ構造を書き換える
新しいオブジェクトを作って、新しいオブジェクトのデータ構造を書き換える

当然、実行コストは前者の方や低いんだけど、その場合、盤面を元に戻すという機能もつけてやる必要が出てくる。
（でないと、AIが現在の盤面から先読み出来ない）
将棋とか囲碁なら、これはそれほど難しくないんだけど、オセロの場合はちょっと面倒くさい・・・
というのも、駒がひっくり返ったときに、どこがひっくり返った場所なのかを記憶しておかないといけないから。
例えば、（普通のオセロで）|空|白|黒|黒|のときに、空の場所に黒を置くと|黒|黒|黒|黒|となるけど、置いた石の情報（太字の黒）が分かっているだけだと、元の様子が|空|白|黒|黒|だったのか|空|白|白|黒|だったのかは判断できない。
これを防ぐには、ひっくり返った場所や、あるいは挟んだ相手となる石の情報を覚えておかないといけなくなる。

もう一つ、前者の場合、キャッシュをとったり、並列化したりするのが難しくなるという問題もある。
例えば合法手を毎回チェックするのは大変なので、キャッシュをとっておこうとした場合に、データ構造が書き換わってしまってはキャッシュも破棄しなくてはいけなくなってしまう。
そうなると、スピードが足りなかった場合に高速化するのが大変だ。
また、並列化しようとした場合も、1つのオブジェクトをみんなでやりくりしようとすると、その資源の取り合いによって結局実行が直列化されてしまうなんてことが起きてくる。

ということで、今回は関数型プログラミング的な後者の方法をとってる。
その方が実装が楽というのもあるけどw

YWF::Board#put_piece、YWF::Board#change_token、YWF::Board#change_turn、YWF::Board#add_moveというのはprotectedメソッドで、それぞれ、石を置いて（変えて）挟まれた石の色を変えていくメソッド、トークンの位置を変えるメソッド、手番を変えるメソッド、手数を増やすメソッド。
詳細は後で。

終了判定

    # 続き

    def game_end?
      if self.count(EMPTY) == 0
        return true
      end

      if self.must_pass?
        passed = self.pass
        if passed.must_pass?
          return true
        end
      end

      false
    end

    def win?(color)
      if (color != BLACK) && (color != WHITE)
        raise "invalid color. [color: #{color}]"
      end

      unless self.game_end?
        return false
      end

      if color == BLACK
        (self.count(BLACK) > self.count(WHITE)) ||
          ((self.count(BLACK) == self.count(WHITE)) && (@token == BLACK))
      else
        (self.count(BLACK) < self.count(WHITE)) ||
          ((self.count(BLACK) == self.count(WHITE)) && (@token == WHITE))
      end
    end

    # 続く

終了判定は、以下のとおり。

まず、空いてるマスがなければ、（灰色の石を変えることが出来たとしても）即終了
そうでない場合、お互いにパスしなければならないなら、終了

そして、指定された色が勝ってるかどうかの判定は、以下のとおり。

相手の色よりも数が多ければ勝ち
もし同数の場合、トークンを持っている方（＝灰色を自分の色に変えた回数が少ない方）が勝ち

YWF::Boardのインタフェースは、こんな感じ。

詳細な処理のいくつかが後回しになってるけど、長くなったので、今日はここまで！

いものやま。

雑多な知識の寄せ集め