YWF with Swift

AlphaBetaCom.swift

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
    }
  }
}

alphabetatest.swift

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

game.start()

Board.swift

public class Board {
  public enum Color: Int {
    case WALL = -1
    case EMPTY
    case BLACK
    case GRAY
    case WHITE

    public var opponent: Color {
      assert(
        (self == .BLACK) || (self == .WHITE),
        "invalid color. [color: \(self)]")

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

    private mutating func changeWithColor(color: Color) {
      assert(
        (self == .BLACK) || (self == .GRAY) || (self == .WHITE),
        "invalid color. [color: \(self)]")
      assert(
        (color == .BLACK) || (color == .WHITE),
        "invalid color. [color: \(color)]")

      let diff: Int
      if color == .BLACK {
        diff = -1
      } else {
        diff = 1
      }
      self = Color(rawValue: (self.rawValue + diff))!
    }
  }

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

  public static let ROW_MIN = 1
  public static let ROW_MAX = 9
  public static let COL_MIN = 1
  public static let COL_MAX = 9

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

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

  private var previous: Board?

  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, .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],
    ]
    self.move = 1
    self.turn = .BLACK
    self.token = .GRAY

    self.previous = nil

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

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

  private lazy var boardHash: Int = {
    [unowned self] in
    var value = 0
    for row in Board.ROW_MIN...Board.ROW_MAX {
      for col in Board.COL_MIN...Board.COL_MAX {
        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.boardHash != other.boardHash {
      return false
    }

    for row in Board.ROW_MIN...Board.ROW_MAX {
      for col in Board.COL_MIN...Board.COL_MAX {
        if self.board[row][col] != other.board[row][col] {
          return false
        }
      }
    }

    return true
  }

  public func color(row: Int, _ col: Int) -> Color {
    assert(
      (Board.ROW_MIN <= row) && (row <= Board.ROW_MAX),
      "invalid row. [row: \(row)]")
    assert(
      (Board.COL_MIN <= col) && (col <= Board.COL_MAX),
      "invalid col. [col: \(col)]")

    return self.board[row][col]
  }

  public func count(color: Color) -> Int {
    assert(
      color != .WALL,
      "invalid color. [color: \(color)]")

    let index = color.rawValue
    if let count = self.countCache[index] {
      return count
    } else {
      var count = 0
      for row in Board.ROW_MIN...Board.ROW_MAX {
        for col in Board.COL_MIN...Board.COL_MAX {
          if self.board[row][col] == color {
            count += 1
          }
        }
      }
      self.countCache[index] = count
      return count
    }
  }

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

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

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

    let index = (row - 1) * Board.COL_MAX + (col - 1)
    if let legal = self.legalCheckCache[index] {
      return legal
    } else {
      if self.hasColorFrom(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
        }
      } 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.ROW_MIN...Board.ROW_MAX {
      for col in Board.COL_MIN...Board.COL_MAX {
        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.ROW_MIN...Board.ROW_MAX {
        for col in Board.COL_MIN...Board.COL_MAX {
          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()

    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)]")
    }

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

    return newBoard
  }

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

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

    return newBoard
  }

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

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

    return false
  }

  public func win(color: Color) -> Bool {
    assert(
      (color == .BLACK) || (color == .WHITE),
      "invalid color. [color: \(color)]")

    if !self.isGameEnd {
      return false
    }

    if color == .BLACK {
      return (self.count(.BLACK) > self.count(.WHITE)) ||
        ((self.count(.BLACK) == self.count(.WHITE)) && (self.token == .BLACK))
    } else {
      return (self.count(.BLACK) < self.count(.WHITE)) ||
        ((self.count(.BLACK) == self.count(.WHITE)) && (self.token == .WHITE))
    }
  }

  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

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

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

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

  private func setPrevious(other: Board) {
    self.previous = other
  }

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

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

  private func hasColorFrom(row: Int, _ col: Int, to direction: (Int, Int)) -> Bool {
    var found = false
    self.traverseFrom(row, col, to: direction) {
      stepCount, traverseRow, traverseCol, traverseColor in
      if traverseColor == 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, Color) -> Bool) {
    var traverseRow = row + direction.0
    var traverseCol = col + direction.1
    var traverseColor = self.board[traverseRow][traverseCol]
    var stepCount = 1
    while (traverseColor != .WALL) && (traverseColor != .EMPTY) {
      let success = block(stepCount, traverseRow, traverseCol, traverseColor)
      if !success {
        break
      }
      traverseRow += direction.0
      traverseCol += direction.1
      traverseColor = self.board[traverseRow][traverseCol]
      stepCount += 1
    }
  }
}

boardtest.swift

var board = Board()
BoardViewer.view(board)

board = board.play(6, 7)
BoardViewer.view(board)

board = board.play(7, 6)
BoardViewer.view(board)

board = board.change(6, 6)
BoardViewer.view(board)

board = board.play(5, 7)
BoardViewer.view(board)

BoardViewer.swift

import Foundation

public struct BoardViewer {
    private static let COL_INDEX = "     1   2   3   4   5   6   7   8   9"
    private static let LINE      = "   +---+---+---+---+---+---+---+---+---+"

  public static func view(board: Board) {
    println(String(format: "[%03d] turn: %@, token: %@",
            board.move, BoardViewer.mark(board.turn), BoardViewer.mark(board.token)))
    println(BoardViewer.COL_INDEX)
    println(BoardViewer.LINE)
    for row in Board.ROW_MIN...Board.ROW_MAX {
      print(" \(row) ")
      for col in Board.COL_MIN...Board.COL_MAX {
        let color = board.color(row, col)
        print("| \(BoardViewer.mark(color)) ")
      }
      println("|")
      println(BoardViewer.LINE)
    }
  }

  public static func mark(color: Board.Color) -> String {
    assert(
      color != .WALL, 
      "invalid color. [color: \(color)]")

    switch color {
    case .EMPTY:
      return " "
    case .BLACK:
      return "O"
    case .GRAY:
      return "-"
    case .WHITE:
      return "X"
    default:
      return " "
    }
  }

  private init?() {
    return nil
  }
}

Game.swift

public class Game {
  public private(set) var blackPlayer: Player
  public private(set) var whitePlayer: Player

  public init(blackPlayer: Player, whitePlayer: Player) {
    self.blackPlayer = blackPlayer
    self.whitePlayer = whitePlayer
  }

  public func start() {
    var board = Board()

    var done = false
    while true {
      BoardViewer.view(board)

      if board.isGameEnd {
        done = true
        break
      }

      if board.mustPass {
        println("pass!")
        board = board.pass()
      } else {
        let player: Player
        if board.turn == .BLACK {
          player = self.blackPlayer
        } else {
          player = self.whitePlayer
        }

        let actionOpt = player.select(board)
        if let action = actionOpt {
          switch action {
          case let .Play(row, col):
            board = board.play(row, col)
          case let .Change(row, col):
            board = board.change(row, col)
          default:
            break
          }
        } else {
          break
        }
      }
    }

    println("----------")
    println("black: \(board.count(.BLACK)), white: \(board.count(.WHITE))")
    if done {
      if board.win(.BLACK) {
        println("\(BoardViewer.mark(.BLACK)) win.")
      } else if board.win(.WHITE) {
        println("\(BoardViewer.mark(.WHITE)) win.")
      } else {
        println("draw.")
      }
    } else {
      println("exit.")
    }
  }
}

Human.swift

import Foundation

extension NSFileHandle {
  func readString() -> String {
    let data = self.availableData
    let string = NSString(data: data, encoding: NSUTF8StringEncoding)!
    return string.stringByTrimmingCharactersInSet(NSCharacterSet.whitespaceAndNewlineCharacterSet())
  }

  func writeString(string: String) -> Void {
    let data = string.dataUsingEncoding(NSUTF8StringEncoding)!
    self.writeData(data)
  }
}

extension NSString {
  func split(regexp: NSRegularExpression) -> [String] {
    var ret = [String]()

    var searchRange = NSRange(location: 0, length: self.length)
    while searchRange.location < self.length {
      var resultRange = regexp.rangeOfFirstMatchInString(self as String,
                                                         options: NSMatchingOptions(0),
                                                         range: searchRange)
      if resultRange.location == NSNotFound {
        resultRange.location = self.length
        resultRange.length = 0
      }

      let substringRange = NSRange(location: searchRange.location,
                                   length: resultRange.location - searchRange.location)
      let substring = self.substringWithRange(substringRange)
      if !substring.isEmpty {
        ret.append(substring)
      }
      searchRange.location = resultRange.location + resultRange.length
      searchRange.length = self.length - searchRange.location
    }

    return ret
  }
}

public class Human: Player {
  private static let separator = NSRegularExpression(pattern: "\\s*[\\s,]\\s*",
                                                     options: NSRegularExpressionOptions(0),
                                                     error: nil)!

  public func select(board: Board) -> Board.Action? {
    println("playable  : \(board.playablePlaces)")
    println("changeable: \(board.changeablePlaces)")

    let stdin = NSFileHandle.fileHandleWithStandardInput()
    let stdout = NSFileHandle.fileHandleWithStandardOutput()

    var action: Board.Action? = nil
    while action == nil {
      stdout.writeString("> ")
      let input = stdin.readString()

      let (command, args) = self.getCommandAndArgs(input)
      if command == "e" {
        break
      }

      action = self.getAction(board, command, args)
      if action == nil {
        println("input 'play row, col', 'change row, col', or 'exit'.")
      }
    }
    return action
  }

  private func getCommandAndArgs(string: String) -> (String, [String]) {
    var components = string.split(Human.separator)
    if components.count == 0 {
      return ("", [])
    }
    let command = (components.removeAtIndex(0) as NSString).substringToIndex(1)
    return (command, components)
  }

  private func getAction(board: Board, _ command: String, _ args: [String]) -> Board.Action? {
    if args.count < 2 {
      return nil
    }

    let row = args[0].toInt() ?? 0
    let col = args[1].toInt() ?? 0
    if (row < Board.ROW_MIN ) || (Board.ROW_MAX < row) ||
        (col < Board.COL_MIN) || (Board.COL_MAX < col) {
      return nil
    }

    switch command {
    case "p":
      if board.isPlayable(row, col) {
        return Board.Action.Play(row, col)
      } else {
        return nil
      }
    case "c":
      if board.isChangeable(row, col) {
        return Board.Action.Change(row, col)
      } else {
        return nil
      }
    default:
      return nil
    }
  }
}

humantest.swift

let human = Human()
let game = Game(blackPlayer: human, whitePlayer: human)

game.start()

Makefile

# source files of module
SOURCE = Board.swift BoardViewer.swift Player.swift Human.swift RandomCom.swift AlphaBetaCom.swift Game.swift

# source files for test
TEST_SOURCE = boardtest.swift humantest.swift randomtest.swift alphabetatest.swift

# test application name (Don't Edit)
TEST_APP = $(TEST_SOURCE:%.swift=%)

### make rules (Don't Edit) ###

testbuild: $(TEST_APP)

$(TEST_APP): $(SOURCE)

$(TEST_APP):%:%.swift
	cp $< main.swift
	xcrun -sdk macosx swiftc $(SWIFT_OPT) -o $@ main.swift $(SOURCE)
	rm main.swift

clean:
	-rm $(TEST_APP)

.PHONY: testbuild clean

Player.swift

public protocol Player {
  func select(board: Board) -> Board.Action?
}

RandomCom.swift

import Security

private func getUniformedRandom(upperBound: UInt32) -> UInt32 {
  let ignoreRegion = 0xffff_ffff - 0xffff_ffff % upperBound

  while true {
    var buf = UnsafeMutablePointer<UInt32>.alloc(1)
    SecRandomCopyBytes(kSecRandomDefault, 4, UnsafeMutablePointer<UInt8>(buf))
    let randomValue = buf.memory
    buf.dealloc(1)
    if randomValue < ignoreRegion {
      return randomValue % upperBound
    }
  }
}

extension Array {
  private func sample() -> T {
    let index = getUniformedRandom(UInt32(self.count))
    return self[Int(index)]
  }
}

public class RandomCom: Player {
  public func select(board: Board) -> Board.Action? {
    let action = board.legalActions.sample()
    switch action {
    case .Pass:
      println("pass.")
    case let .Play(row, col):
      println("play (\(row), \(col)).")
    case let .Change(row, col):
      println("change (\(row), \(col)).")
    }
    return action
  }
}

randomtest.swift

let random = RandomCom()
let game = Game(blackPlayer: random, whitePlayer: random)

game.start()