昨日は、パフォーマンスを改善して、ミニマックスAIがそれなりのスピードで動くようにした。
今日はちょっと話題を変えて、千日手の話。
千日手
将棋の場合、何度も同じ局面になってしまって、手が進まなくなってしまうことがある。
これを「千日手」といって、今のルールでは、同一局面が4回現れると、先後を入れ替えて指し直しというルールになっている。
囲碁にも同じようなケースがあり、お互いに石を取り合う手がずっと続く形が出てくる。
こちらは「コウ」（未来永劫の"劫"）と呼ばれ、コウになった場合、すぐには相手の石を取り返せず、一手別の場所に手を入れる必要があるというルールになっている。
さて、今考えている変種オセロの場合、こういったことは起きるのだろうか？
まず、普通のオセロの場合、こういったことは絶対に起きない。
というのも、盤面に置かれている石の数は常に増えていくので、同一の盤面になりようがないからだ。
しかし、この変種オセロの場合、灰色の石を自分の色に変えるという手があるので、盤面の石の数が増えない場合がある。
そうなると、お互いに灰色の石を自分の色に変え合うことで、同一の盤面が何度も現れる可能性がある。
実際、ミニマックス法の思考ルーチンを実装しているときに、ちょっとしたプログラムのミスで、そういった手順が見つかってしまった。
なので、千日手になるような手を禁止する必要が出てきた。
千日手になる形
では、実際にどういう形で千日手になるのか。
[001] turn: O, token: -
1 2 3
+---+---+---
1 | O | - | O
+---+---+---
2 | X | - | X
+---+---+---
3 | - | - | O
+---+---+---
4 | X | - | X
change [3, 1]
[002] turn: X, token: X
1 2 3
+---+---+---
1 | O | - | O
+---+---+---
2 | - | O | X
+---+---+---
3 | O | O | O
+---+---+---
4 | X | - | X
change [2, 1]
[003] turn: O, token: -
1 2 3
+---+---+---
1 | O | - | O
+---+---+---
2 | X | - | X
+---+---+---
3 | - | - | O
+---+---+---
4 | X | - | X
change [3, 1]
〜以下、ずっと繰り返し〜
見ての通り、3手目の形が1手目とまったく同じになってる。
なので、この場合、2手目でXが(2, 1)をXに変える手を禁止しないと、同一盤面が現れることになってしまう。
千日手の禁止
ということで、千日手の禁止を実装していく。
具体的には、ある手を打ったとき、それによって現れる新しい盤面が以前に現れていた盤面と同じになっていないかをチェックし、もし同じ盤面が現れるようなら、その手は合法手から外す、という処理だ。
その修正が、以下。
def initialize(other=nil)
@board = [
# 省略
]
@move = 1
@turn = BLACK
@token = GRAY
if other
copy(other)
end
+ # to avoid appearing same situation by 'change'
+ @previous = nil
+
# cache (lazy)
@count = Array.new(4)
@legal_check_cache = Array.new(ROW_MAX*COL_MAX)
@playable_places_cache = nil
@changeable_places_cache = nil
+ @board_hash_cache = nil
end
# 省略
+ def board_hash
+ if @board_hash_cache.nil?
+ value = 0
+ (ROW_MIN..ROW_MAX).each do |row|
+ (COL_MIN..COL_MAX).each do |col|
+ value += row * col * @board[row][col]
+ end
+ end
+ @board_hash_cache = value
+ end
+ @board_hash_cache
+ end
+
+ def same_situation?(other)
+ if @turn != other.turn
+ return false
+ end
+ if @token != other.token
+ return false
+ end
+ if self.board_hash != other.board_hash
+ return false
+ end
+ (ROW_MIN..ROW_MAX).each do |row|
+ (COL_MIN..COL_MAX).each do |col|
+ if @board[row][col] != other.color(row, col)
+ return false
+ end
+ end
+ end
+ true
+ end
# 省略
def changeable?(row, col)
if self.color(row, col) != GRAY
return false
end
index = (row - 1) * COL_MAX + (col - 1)
if @legal_check_cache[index].nil?
if (@token != GRAY) && (@token != @turn)
@legal_check_cache[index] = false
else
- @legal_check_cache[index] = has_color_from?(row, col)
+ if has_color_from?(row, col)
+ new_board = self.change(row, col, false)
+ if new_board.has_same_situation_before?
+ @legal_check_cache[index] = false
+ else
+ @legal_check_cache[index] = true
+ end
+ else
+ @legal_check_cache[index] = false
+ end
end
end
@legal_check_cache[index]
end
# 省略
- def change(row, col)
- unless self.changeable?(row, col)
- raise "not changeable. [row: #{row}, col: #{col}]"
+ def change(row, col, check=true)
+ if check
+ unless self.changeable?(row, col)
+ raise "not changeable. [row: #{row}, col: #{col}]"
+ end
end
new_board = self.class.new(self)
new_board.put_piece(row, col)
new_board.change_token
new_board.change_turn
+ new_board.set_previous(self)
new_board.add_move
new_board
end
# 省略
protected
+ attr_reader :previous
+
+ def has_same_situation_before?
+ ancestor = @previous
+ while (ancestor != nil)
+ if self.same_situation?(ancestor)
+ return true
+ else
+ ancestor = ancestor.previous
+ end
+ end
+ false
+ end
# 省略
+ def set_previous(other)
+ @previous = other
+ end
まず、直前の盤面を覚えておくために、@previousというインスタンス変数を用意。
それと、盤面の比較を出来るように、YWF::Board#board_hashというメソッドと、YWF::Board#same_situation?というメソッドを用意した。
このboard_hashというメソッドは盤面の比較を高速に出来るようにするためのもので、盤面の状態を「ハッシュ値」という値に変換している。
普通に盤面の比較を行おうとすると、各マスを順番に比較していく必要があり、これを毎回やっていると大変。
そこで、ある一定の規則に従って、盤面の状態を数値（ハッシュ値）に変換してやる。
そうすれば、ある一定の規則に従っていることで、「盤面が同じ⇒ハッシュ値が同じ」という命題が真となるので、その対偶の「ハッシュ値が異なる⇒盤面が異なる」も真となる。
なので、ハッシュ値が違っていれば、盤面全部を見なくても盤面が異なっていることは分かる、という仕組みだ。
ただし、一つ気をつけないといけないのは、その逆の「ハッシュ値が同じ⇒盤面が同じ」という命題は成り立つとは限らないということ。
なので、ハッシュ値が同じだった場合には、実際に盤面全部を確認して、盤面が同じかどうかを判断する必要がある。
そして、YWF::Board#changeable?では、ボードの石を実際に変えてみて、それが以前の盤面と同じになっていないかのチェックも行うようにした。
ここで一つ注目したいのが、YWF::Board#changeのインタフェースの最後に、checkという引数が追加されていること。
これは、changeの最初でchangeable?を呼び出しているので、下手するとchangeable?→change→changeable?→...と呼び出しがループし続けてしまう可能性があるので、それを防ぐため。
changeable?からchangeを呼ぶ場合には、この引数にfalseを渡すことで、再度changeable?が呼ばれないようにしている。
最後に、YWF::Board#has_same_situation_before?。
インスタンス変数の@previousをずっと辿っていくことで、以前に同じ盤面が現れていないかをチェックしている。
なお、同じ盤面が現れているとすれば、それはchangeがずっと続いているとき（playが挟まれば石の数が変わるので、同一盤面になることは絶対にない）なので、@previousに直前の盤面を覚えさせるのは、changeのときだけでいいというのも、気をつけたいところ。
これで千日手の禁止の実装はOK。
次は、ミニマックスAIのさらなる高速化を目指す。
今日はここまで！
