変種オセロをSwiftに移植してみた。（その11）

昨日はランダムAIを実装した。

今日はアルファベータAIの実装。

アルファベータAI

さっそくコードを。

public class AlphaBetaCom: Player {
  private var color: Board.Color
  private lazy var opponent: Board.Color = self.color.opponent
  private var depth: Int

  public init(color: Board.Color, depth: Int = 3) {
    self.color = color
    self.depth = depth
  }

  public func select(board: Board) -> Board.Action? {
    var currentSelect: Board.Action! = nil
    var currentSelectValue = -1000
    var opponentBestValue = 1000
    for action in board.legalActions {
      let value = self.calculateActionValue(board, action, self.depth,
                           currentSelectValue, opponentBestValue)
      if value > currentSelectValue {
        currentSelect = action
        currentSelectValue = value
        if currentSelectValue >= opponentBestValue {
          break
        }
      }
    }

    switch currentSelect! {
    case .Pass:
      println("pass.")
    case let .Play(row, col):
      println("play (\(row), \(col)).")
    case let .Change(row, col):
      println("change (\(row), \(col)).")
    }
    return currentSelect!
  }

  private func calculateActionValue(board: Board, _ action: Board.Action, _ depth: Int,
                    _ selfBestValue: Int, var _ opponentBestValue: Int) -> Int {
    let newBoard: Board
    switch action {
    case .Pass:
      newBoard = board.pass()
    case let .Play(row, col):
      newBoard = board.play(row, col)
    case let .Change(row, col):
      newBoard = board.change(row, col)
    }

    if (depth == 1) || newBoard.isGameEnd {
      if newBoard.win(self.color) {
        return 100
      } else if newBoard.win(self.opponent) {
        return -100
      } else {
        return newBoard.count(self.color) - newBoard.count(self.opponent)
      }
    } else {
      let sign = (newBoard.turn == self.color) ? 1 : -1

      for newAction in newBoard.legalActions {
        let value = self.calculateActionValue(newBoard, newAction, depth - 1,
                            opponentBestValue, selfBestValue)
        if (value * sign) > (opponentBestValue * sign) {
          opponentBestValue = value
        }

        if (opponentBestValue * sign) >= (selfBestValue * sign) {
          break
        }
      }

      return opponentBestValue
    }
  }
}

といっても、Rubyのコードをそのまま移植しただけなので、特に書くことなし。
アルゴリズムの説明については、変種オセロの思考ルーチンを作ってみた。（その6） - いものやま。を参照。

実行速度

さて、Swiftはコンパイルして実行できるので、Rubyよりも速く動くことが期待できる。

さっそく、以下のようなコードを用意して、コンパイルを行い、動かしてみた。

/* alphabetagame.swift */

let blackPlayer = AlphaBetaCom(color: .BLACK)
let whitePlayer = AlphaBetaCom(color: .WHITE)
let game = Game(blackPlayer: blackPlayer, whitePlayer: whitePlayer)

game.start()

・・・あれ？
遅い？？？

なんか動きがモッサリしているので、試しにRubyと速さを比べてみると・・・

# Ruby
$ time ./alphabeta_com.rb
（省略）

real    0m26.777s
user    0m26.006s
sys     0m0.626s

# Swift
$ time ./alphabetagame
（省略）

real    0m31.791s
user    0m31.469s
sys     0m0.060s

ちょっと待って。

Rubyに負けてるじゃん！

お前、それでもコンパイラ言語なのか！？

Rubyだと26秒強なのに対し、Swiftだと31秒強かかってる。
一方は（最適化が進んでいるとはいえ）インタープリタ言語なのに、それに負けるコンパイラ言語ってどうよ・・・

最適化

さすがにこのままじゃアカンので、Swiftの名誉を挽回するためにも、-Ouncheckedオプションをつけて再コンパイル。
このオプションをつけると、状態のチェックを行うassert()がすべて取り除かれ、コードの最適化も行われる。

その状態で再実行した結果が、以下。

# Swift with -Ounchecked option
$ time ./alphabetagame
（省略）

real    0m1.996s
user    0m1.980s
sys     0m0.007s

これなら約2秒で終了。
ふぅ、一安心・・・

今日はここまで！