ルールは昨日書いた通り。
さっそく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のインタフェースは、こんな感じ。
詳細な処理のいくつかが後回しになってるけど、長くなったので、今日はここまで!