いものやま。

雑多な知識の寄せ集め

変種オセロのルール画面を作ってみた。（その3）

ゲーム開発 Swift YWF

昨日は英語のルールを書いた。

今日は、ルールの変更に合わせて、ボードのコードを修正。

ボードの修正

といっても、修正内容は簡単。
結果として、前より簡単なコードになった感じ。

とりあえず、何を修正したのかが分かるように、diffの出力。

diff --git a/YWF/Model/Board.swift b/YWF/Model/Board.swift
index 9729127..a02ef62 100644
--- a/YWF/Model/Board.swift
+++ b/YWF/Model/Board.swift
@@ -65,7 +65,7 @@ public class Board {
     return self.turn.opponent
   }
 
-  private var previous: Board?
+  private var changed: Bool
 
   private var countCache: [Int?]
   private var legalCheckCache: [Bool?]
@@ -88,7 +88,7 @@ public class Board {
     self.turn = .Bad
     self.token = .Common
 
-    self.previous = nil
+    self.changed = false
 
     self.countCache = [Int?](count: 4, repeatedValue: nil)
     self.legalCheckCache = [Bool?](count: Board.RowMax * Board.ColMax, repeatedValue: nil)
@@ -100,6 +100,7 @@ public class Board {
     self.move = other.move
     self.turn = other.turn
     self.token = other.token
+    self.changed = other.changed
   }
 
   private lazy var boardHash: Int = {
@@ -120,6 +121,9 @@ public class Board {
     if self.token != other.token {
       return false
     }
+    if self.changed != other.changed {
+      return false
+    }
     if self.boardHash != other.boardHash {
       return false
     }
@@ -190,20 +194,17 @@ public class Board {
     if self.token == self.opponent {
       return false
     }
+    if self.changed {
+      return false
+    }
 
     let index = (row - 1) * Board.ColMax + (col - 1)
     if let legal = self.legalCheckCache[index] {
       return legal
     } else {
       if self.hasStatusFrom(row, col) {
-        let newBoard = self.change(row, col, check: false)
-        if newBoard.hasSameSituationBefore {
-          self.legalCheckCache[index] = false
-          return false
-        } else {
-          self.legalCheckCache[index] = true
-          return true
-        }
+        self.legalCheckCache[index] = true
+        return true
       } else {
         self.legalCheckCache[index] = false
         return false
@@ -268,23 +269,22 @@ public class Board {
     newBoard.putPiece(row, col)
     newBoard.changeTurn()
     newBoard.addMove()
+    newBoard.changed = false
 
     return newBoard
   }
 
-  public func change(row: Int, _ col: Int, check: Bool = true) -> Board {
-    if check {
-      assert(
-        self.isChangeable(row, col),
-        "not changeable. [row: \(row), col: \(col)]")
-    }
+  public func change(row: Int, _ col: Int) -> Board {
+    assert(
+      self.isChangeable(row, col),
+      "not changeable. [row: \(row), col: \(col)]")
 
     let newBoard = Board(self)
     newBoard.putPiece(row, col)
     newBoard.changeToken()
     newBoard.changeTurn()
-    newBoard.setPrevious(self)
     newBoard.addMove()
+    newBoard.changed = true
 
     return newBoard
   }
@@ -297,6 +297,7 @@ public class Board {
     let newBoard = Board(self)
     newBoard.changeTurn()
     newBoard.addMove()
+    newBoard.changed = false
 
     return newBoard
   }
@@ -305,6 +306,13 @@ public class Board {
     if self.count(.Empty) == 0 {
       return true
     }
+    
+    if self.count(.Bad) == 0 {
+      return true
+    }
+    if self.count(.Good) == 0 {
+      return true
+    }
 
     if self.mustPass {
       let passed = self.pass()
@@ -334,18 +342,6 @@ public class Board {
     }
   }
 
-  private var hasSameSituationBefore: Bool {
-    var ancestorOpt = self.previous
-    while let ancestor = ancestorOpt {
-      if self.isSameSituation(ancestor) {
-        return true
-      } else {
-        ancestorOpt = ancestor.previous
-      }
-    }
-    return false
-  }
-
   private func putPiece(row: Int, _ col: Int) {
     self.board[row][col] = self.turn
 
@@ -372,10 +368,6 @@ public class Board {
     self.token.changeWithStatus(self.opponent)
   }
 
-  private func setPrevious(other: Board) {
-    self.previous = other
-  }
-
   private func addMove() {
     self.move += 1
   }

で、もはやYWFに関する記事が長すぎて、diffだけ見ても分からないだろうから、修正後のコードも。

//==============================
// YWF
//------------------------------
// Board.swift
//==============================

public class Board {
  public enum Status: Int {
    case Wall = -1
    case Empty
    case Bad
    case Common
    case Good

    public var opponent: Status {
      assert(
        (self == .Bad) || (self == .Good),
        "invalid status. [status: \(self)]")

      return Status(rawValue: (self.rawValue + 2) % 4)!
    }

    private mutating func changeWithStatus(status: Status) {
      assert(
        (self == .Bad) || (self == .Common) || (self == .Good),
        "invalid status. [status: \(self)]")
      assert(
        (status == .Bad) || (status == .Good),
        "invalid status. [status: \(status)]")

      let diff: Int
      if status == .Bad {
        diff = -1
      } else {
        diff = 1
      }
      self = Status(rawValue: (self.rawValue + diff))!
    }
  }

  public enum Action {
    case Pass
    case Play(Int, Int)
    case Change(Int, Int)
  }

  public static let RowMin = 1
  public static let RowMax = 9
  public static let ColMin = 1
  public static let ColMax = 9

  private static let Direction = [
    (-1, -1), (-1,  0), (-1,  1),
    ( 0, -1),           ( 0,  1),
    ( 1, -1), ( 1,  0), ( 1,  1),
  ]

  private var board: [[Status]]
  public private(set) var move: Int
  public private(set) var turn: Status
  public private(set) var token: Status
  public var opponent: Status {
    return self.turn.opponent
  }

  private var changed: Bool

  private var countCache: [Int?]
  private var legalCheckCache: [Bool?]

  public init() {
    self.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, .Common, .Bad   , .Good  , .Empty, .Empty, .Empty, .Wall],
      [.Wall, .Empty, .Empty, .Empty, .Good  , .Common, .Bad   , .Empty, .Empty, .Empty, .Wall],
      [.Wall, .Empty, .Empty, .Empty, .Bad   , .Good  , .Common, .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],
    ]
    self.move = 0
    self.turn = .Bad
    self.token = .Common

    self.changed = false

    self.countCache = [Int?](count: 4, repeatedValue: nil)
    self.legalCheckCache = [Bool?](count: Board.RowMax * Board.ColMax, repeatedValue: nil)
  }

  convenience init(_ other: Board) {
    self.init()
    self.board = other.board
    self.move = other.move
    self.turn = other.turn
    self.token = other.token
    self.changed = other.changed
  }

  private lazy var boardHash: Int = {
    [unowned self] in
    var value = 0
    for row in Board.RowMin...Board.RowMax {
      for col in Board.ColMin...Board.ColMax {
        value += row * col * self.board[row][col].rawValue
      }
    }
    return value
  }()

  public func isSameSituation(other: Board) -> Bool {
    if self.turn != other.turn {
      return false
    }
    if self.token != other.token {
      return false
    }
    if self.changed != other.changed {
      return false
    }
    if self.boardHash != other.boardHash {
      return false
    }

    for row in Board.RowMin...Board.RowMax {
      for col in Board.ColMin...Board.ColMax {
        if self.board[row][col] != other.board[row][col] {
          return false
        }
      }
    }

    return true
  }

  public func status(row: Int, _ col: Int) -> Status {
    assert(
      (Board.RowMin <= row) && (row <= Board.RowMax),
      "invalid row. [row: \(row)]")
    assert(
      (Board.ColMin <= col) && (col <= Board.ColMax),
      "invalid col. [col: \(col)]")

    return self.board[row][col]
  }

  public func count(status: Status) -> Int {
    assert(
      status != .Wall,
      "invalid status. [status: \(status)]")

    let index = status.rawValue
    if let count = self.countCache[index] {
      return count
    } else {
      var count = 0
      for row in Board.RowMin...Board.RowMax {
        for col in Board.ColMin...Board.ColMax {
          if self.board[row][col] == status {
            count += 1
          }
        }
      }
      self.countCache[index] = count
      return count
    }
  }

  public func isPlayable(row: Int, _ col: Int) -> Bool {
    if self.status(row, col) != .Empty {
      return false
    }

    let index = (row - 1) * Board.ColMax + (col - 1)
    if let legal = self.legalCheckCache[index] {
      return legal
    } else {
      let legal = self.hasStatusFrom(row, col)
      self.legalCheckCache[index] = legal
      return legal
    }
  }

  public func isChangeable(row: Int, _ col: Int) -> Bool {
    if self.status(row, col) != .Common {
      return false
    }
    if self.token == self.opponent {
      return false
    }
    if self.changed {
      return false
    }

    let index = (row - 1) * Board.ColMax + (col - 1)
    if let legal = self.legalCheckCache[index] {
      return legal
    } else {
      if self.hasStatusFrom(row, col) {
        self.legalCheckCache[index] = true
        return true
      } else {
        self.legalCheckCache[index] = false
        return false
      }
    }
  }

  public var mustPass: Bool {
    return (self.playablePlaces.isEmpty) && (self.changeablePlaces.isEmpty)
  }

  public private(set) lazy var playablePlaces: [(Int, Int)] = {
    [unowned self] in
    var places = [(Int, Int)]()
    for row in Board.RowMin...Board.RowMax {
      for col in Board.ColMin...Board.ColMax {
        if self.isPlayable(row, col) {
          places.append((row, col))
        }
      }
    }
    return places
  }()

  public private(set) lazy var changeablePlaces: [(Int, Int)] = {
    [unowned self] in
    var places = [(Int, Int)]()
    if self.token != self.opponent {
      for row in Board.RowMin...Board.RowMax {
        for col in Board.ColMin...Board.ColMax {
          if self.isChangeable(row, col) {
            places.append((row, col))
          }
        }
      }
    }
    return places
  }()

  public private(set) lazy var legalActions: [Action] = {
    [unowned self] in
    var actions = [Action]()
    if self.mustPass {
      actions.append(.Pass)
    } else {
      for (row, col) in self.playablePlaces {
        actions.append(.Play(row, col))
      }
      for (row, col) in self.changeablePlaces {
        actions.append(.Change(row, col))
      }
    }
    return actions
  }()

  public func play(row: Int, _ col: Int) -> Board {
    assert(
      self.isPlayable(row, col),
      "not playable. [row: \(row), col: \(col)]")

    let newBoard = Board(self)
    newBoard.putPiece(row, col)
    newBoard.changeTurn()
    newBoard.addMove()
    newBoard.changed = false

    return newBoard
  }

  public func change(row: Int, _ col: Int) -> Board {
    assert(
      self.isChangeable(row, col),
      "not changeable. [row: \(row), col: \(col)]")

    let newBoard = Board(self)
    newBoard.putPiece(row, col)
    newBoard.changeToken()
    newBoard.changeTurn()
    newBoard.addMove()
    newBoard.changed = true

    return newBoard
  }

  public func pass() -> Board {
    assert(
      self.mustPass,
      "cannot pass.")

    let newBoard = Board(self)
    newBoard.changeTurn()
    newBoard.addMove()
    newBoard.changed = false

    return newBoard
  }

  public var isGameEnd: Bool {
    if self.count(.Empty) == 0 {
      return true
    }
    
    if self.count(.Bad) == 0 {
      return true
    }
    if self.count(.Good) == 0 {
      return true
    }

    if self.mustPass {
      let passed = self.pass()
      if passed.mustPass {
        return true
      }
    }

    return false
  }

  public func win(status: Status) -> Bool {
    assert(
      (status == .Bad) || (status == .Good),
      "invalid status. [status: \(status)]")

    if !self.isGameEnd {
      return false
    }

    if status == .Bad {
      return (self.count(.Bad) > self.count(.Good)) ||
        ((self.count(.Bad) == self.count(.Good)) && (self.token == .Bad))
    } else {
      return (self.count(.Bad) < self.count(.Good)) ||
        ((self.count(.Bad) == self.count(.Good)) && (self.token == .Good))
    }
  }

  private func putPiece(row: Int, _ col: Int) {
    self.board[row][col] = self.turn

    for direction in Board.Direction {
      if self.hasStatusFrom(row, col, to: direction) {
        self.traverseFrom(row, col, to: direction) {
          stepCount, traverseRow, traverseCol, traverseStatus in
          if traverseStatus == self.turn {
            return false
          } else {
            self.board[traverseRow][traverseCol].changeWithStatus(self.turn)
            return true
          }
        }
      }
    }
  }

  private func changeTurn() {
    self.turn = self.opponent
  }

  private func changeToken() {
    self.token.changeWithStatus(self.opponent)
  }

  private func addMove() {
    self.move += 1
  }

  private func hasStatusFrom(row: Int, _ col: Int) -> Bool {
    for direction in Board.Direction {
      if self.hasStatusFrom(row, col, to: direction) {
        return true
      }
    }
    return false
  }

  private func hasStatusFrom(row: Int, _ col: Int, to direction: (Int, Int)) -> Bool {
    var found = false
    self.traverseFrom(row, col, to: direction) {
      stepCount, traverseRow, traverseCol, traverseStatus in
      if traverseStatus == self.turn {
        if stepCount == 1 {
          found = false
        } else {
          found = true
        }
        return false
      } else {
        return true
      }
    }
    return found
  }

  private func traverseFrom(row: Int, _ col: Int, to direction: (Int, Int),
                _ block: (Int, Int, Int, Status) -> Bool) {
    var traverseRow = row + direction.0
    var traverseCol = col + direction.1
    var traverseStatus = self.board[traverseRow][traverseCol]
    var stepCount = 1
    while (traverseStatus != .Wall) && (traverseStatus != .Empty) {
      let success = block(stepCount, traverseRow, traverseCol, traverseStatus)
      if !success {
        break
      }
      traverseRow += direction.0
      traverseCol += direction.1
      traverseStatus = self.board[traverseRow][traverseCol]
      stepCount += 1
    }
  }
}

コードの詳細な説明は、以下を参照・・・

なお、変更点は、以下のとおり：

以前は、ある手を打ったとき、それによって現れる新しい盤面が以前に現れていた盤面と同じになっていないかをチェックし、もし同じ盤面が現れるようなら、その手は合法手から外す、としていたのだけど（詳細は変種オセロの思考ルーチンを作ってみた。（その5） - いものやま。を参照）、ルールを変更したので、直前にチェンジを行ったかどうかのフラグを単に持つようにして、フラグが立っていたらチェンジ出来ないというふうに変更した。
なお、千日手が起こるのはチェンジの応酬が続いた場合のみなので、この方法でも千日手が起こるのを防げている。

あと、終了条件でどちらかのコマが0個になった場合というのが抜けていたので、追加してある。
（オセロの場合、これは「どちらもパスせざるをえない」という条件と等価なんだけど、変種オセロの場合、チェンジがあるので、等価でない。もっとも、勝敗に変化はないのだけれど）

アルファベータAI同士の対戦成績

ルールを変えたので、それが勝敗に影響を与えてるかなぁと思い、試しにアルファベータAI同士で対戦させてみた。

元のルールの実装だと、勝敗は次のような感じ：

読む手数 結果
3手 51 - 15
5手 32 - 30
7手 24 - 35

変更後のルールの実装だと、次のような感じ：

読む手数 結果
3手 35 - 18
5手 34 - 29
7手 25 - 29

ルール変更後の方が、若干、差がつきにくくなってる？
まぁ、評価関数がシンプルなので、辺や角を取れるかが割と運で、あくまで参考程度だけど。

今日はここまで！