【Ruby】リバーシのプログラムを書いたりするためのgemをつくった

概要

誰もが知っているボードゲームのリバーシで遊ぶためのgemをつくりました。

自分で対戦して遊んだり、プログラム同士で試合をさせたり、自分でプレイヤーのアルゴリズムを書いてみたりすることができます。

ソースコード

インストール

gem install reversi

デモ

reversi.rb

require 'reversi'

Reversi.configure do |config|
  config.disk_color_b = 'cyan'
  config.disk_b = 'O'
  config.disk_w = 'O'
  config.progress = true
end

game = Reversi::Game.new

game.start
puts "black #{game.board.status[:black].size}"
puts "white #{game.board.status[:white].size}"

これを実行すると...

対戦が開始されます。
ソースコードへのリンク先のREADMEで実際に動いてる様子を見ることができます。

実行前の設定

Reversi.configure にデモの例の様にブロックを渡すことで各種設定を行います。
変更が無い限り、それ以降の処理全てに反映されます。

ちなみにゲームで使う石はここではディスクと呼ぶことにしました。pieceとかstoneとかdiscとか呼び方はいろいろあるようです。

名前	説明	初期値
player_b	先手のプレイヤーが使うアルゴリズムを実装したクラスオブジェクト	Reversi::Player::RandomAI
player_w	後手のプレイヤーが使うアルゴリズムを実装したクラスオブジェクト	Reversi::Player::RandomAI
disk_b	先手が使うディスクの文字列 半角1文字	'b'
disk_w	後手が使うディスクの文字列 半角1文字	'w'
disk_color_b	先手が使うディスクの色の文字列かシンボル	色指定なし
disk_color_w	後手が使うディスクの色の文字列かシンボル	色指定なし
progress	途中経過表示モードのon/off	false
stack_limit	連続で「戻る( Reversi::Board#undo! )」が使用できる上限回数	3

ディスクの文字列や色は Reversi::Board#to_s で返される文字列に反映されます。
ディスクの色は black, red, green, yellow, blue, magenda, cyan, white, gray から選べます。

途中経過表示モードをoffにすると何も出力されません。

自分で手を入力する

いわゆる人間がコンピュータと対戦するモードです。
どちらかのプレイヤーに Reversi::Player::Human をセットします。両方にセットすることもできますが、両方とも自分で入力することになります。

自分のつくったプログラムと対戦して、どんな感じになってるか確認したりするのにも使えます。

これを実行すると現在の状態が表示され入力待ちになるので d3 のように位置を入力していきます。ゲームが終了すればそのまま終わりますが、途中で終了したい場合は q か exit　と入力します。

Reversi.configure do |config|
  config.player_b = Reversi::Player::Human
end

game = Reversi::Game.new
game.start

思考ルーチンを自分で書いてみる

Reversi::Player::BasePlayer を継承して moveメソッドを定義することで、オリジナルのプレイヤークラスをつくることができます。

スーパークラスのmoveを呼び出す必要はありませんが、initializeメソッドを用意する場合は必ず呼び出してください。Reversi::Game#start でそれぞれの手を逐一チェックしているので、不正な手(相手のディスクをひっくり返せない手など)を打つようなプレイヤーを戦わせようとしても、途中でエラーが発生します。

なお、長くなりそうなのでここではアルゴリズムの説明はしません。Negamax法の例だけ書いてみたので興味のある人は調べてみてください。

自作プレイヤー作成方法

1. Reversi::Player::BasePlayer#next_moves で現在打てる手の全ての位置を配列として得る。
2. その中からなんらかの方法で手をひとつ選ぶ。
3. Reversi::Player::BasePlayer#put_disk の引数にその手を渡す。

以上が大まかな流れです。 next_moves を使用した際、 得られる配列が空である場合は打てる場所が無いので何もしないでください。

また、手を選ぶ段階において探索として局面を進めてみたい場合があるかと思います。 next_moves と put_disk はそれぞれ第一引数、第三引数にtrueとfalseのどちらを与えるかによって、自分と相手どちらの操作を行うかを選ぶことができます。(どちらもデフォルトはtrueで自分に対する操作になります) 移動した局面において自分や相手のディスクがどこにあるかという情報は Reversi::Player::BasePlayer#status で得ることができます。

最後に局面の評価が終了したら、前の局面に戻る必要があります。 そこで、 move メソッドに引数として与えられたReversi::Board クラスのオブジェクトである board に対して undo! メソッドを使用します。このメソッドは直前の put_disk で行った変更を取り消します。

簡単に言うとゲーム木をイメージした際、 現在の節点から伸びている枝が next_moves で、そのうちのひとつを選び次の節点(局面)に移動するのが put_disk、現在の節点からひとつ上の節点へ戻るのが undo! です。

ランダムな手を打つ例

現在打てる手の中からランダムに一手を選ぶ例で、moveメソッド内でしなければならないことを守った上での必要最低限のものになっています。 Reversi::Player::RandomAI が同様の内容となっています。

class MyAI < Reversi::Player::BasePlayer
  def move(board)
    moves = next_moves
    put_disk(*moves.sample) unless moves.empty?
  end
end

Reversi.configure do |config|
  config.player_b = MyAI
  config.progress = true  
end

game = Reversi::Game.new
game.start

NegaMax法の例

MinMax法の亜種みたいなやつです。デフォルトの設定では3つ前の状態までしか連続で戻れないので、以下の例では3手先読みにしていますが、それより先まで読む場合は最初の設定で stack_limit に何手前まで保持するかの数字をセットしてください。局面評価では単純に各位置に重みを与え、自分のディスクがある位置の合計値をみています。 Reversi::Player::NegaMaxAI が同様の内容になっています。

class MyAI < Reversi::Player::BasePlayer

  def initialize(_color, _board)
    super

    # 盤の位置による重み付け
    point = [
      100, -10,  0, -1, -1,  0, -10, 100,
      -10, -30, -5, -5, -5, -5, -30, -10,
        0,  -5,  0, -1, -1,  0,  -5,   0,
       -1,  -5, -1, -1, -1, -1,  -5,  -1,
       -1,  -5, -1, -1, -1, -1,  -5,  -1,
        0,  -5,  0, -1, -1,  0,  -5,   0,
      -10, -30, -5, -5, -5, -5, -30, -10,
      100, -10,  0, -1, -1,  0, -10, 100
    ]
    @evaluation_value = 
      Hash[(1..8).map{ |x| (1..8).map{ |y| [[x, y], point.shift] } }.flatten(1) ]
  end

  def move(board)
    moves = next_moves
    return if moves.empty?
    next_move = moves.map do |move|
      { :move => move, :point => evaluate(move, board, 1, true) }
    end
    .max_by{ |v| v[:point] }[:move]
    put_disk(*next_move)
  end

  def evaluate(move, board, depth, color)
    # 次の局面へ移動
    put_disk(*move, color)
    # そこから伸びる枝
    moves = next_moves(!color)
    if depth == 3
      # 3手先まできたら自分のディスクがある位置の点数によって局面を評価
      status[:mine].inject(0){ |sum, xy| sum + @evaluation_value[xy] }
    elsif moves.empty?
      -100
    else
      # 子ノードの内最大の評価値であるものを選び符号を反転して現ノードの評価値とする
      -( moves.map{ |move| evaluate(move, board, depth + 1, !color) }.max )
    end
  ensure
    # 前の局面へ戻る
    board.undo!
  end
end

Reversi.configure do |config|
  config.player_b = MyAI
  config.progress = true
end

game = Reversi::Game.new
game.start

この他にも MinMax法の例などが Reversi::Player 以下にあります。これらの例も単純に位置の重み付けだけで局面評価を行っていますが、それ以外にも、着手可能数や開放度理論による評価など様々な工夫ができると思います。

おわりに

今回の反省点としては、自分の力不足であまりRubyっぽく書けなかったということと、実行に致命的に時間がかかるということです。3手先読みするプレイヤーを対戦させるだけで1試合が終わるのに分単位で時間がかかります。

C拡張で書き直して改善する予定ですが、現状では何千何万回繰り返し戦わせるみたいなことには向いてないです。

別言語でリバーシを実装しようと思ってるけど書いてみたアルゴリズムが正しいか試してみたい方、思考ルーチンを書く練習をしてみたい方などはぜひ触ってみてください。

メソッド名や全体の構成についてご意見ご感想ご指摘ごマサカリ等お待ちしています。

追記(2015/03/10)

v1.0.0 以降の変更点

C拡張で書き直したのでかなり高速になりました。それに伴い、今まで [:a, 3] のような形で得ていた盤の座標を表す配列は [1, 3] のように変更されました。本稿の該当箇所は修正済みです。