关于

一个使用 Swift 构建的用于回合制游戏的 蒙特卡洛树搜索 (MCTS) 库

导入

通过将以下行添加到任何 .swift 文件来导入 Carlo

import Carlo

实现

通过设计符合 CarloGamePlayer、CarloGameMove 和 CarloGame 协议的 player（玩家）、move（移动）和 game（游戏）结构体来实现 Carlo。

虽然前两个协议没有明确的要求，但“符合”它们可能看起来像这样

enum ConnectThreePlayer: Int, CarloGamePlayer, CustomStringConvertible {
    case one = 1
    case two = 2
    
    var opposite: Self {
        switch self {
        case .one: return .two
        case .two: return .one
        }
    }
    
    var description: String {
        "\(rawValue)"
    }
}

typealias ConnectThreeMove = Int
extension ConnectThreeMove: CarloGameMove {}

符合 CarloGame 需要以下内容

public protocol CarloGame: Equatable {
    associatedtype Player: CarloGamePlayer
    associatedtype Move: CarloGameMove
  
    var currentPlayer: Player { get }
    func availableMoves() -> [Move]
    func update(_ move: Move) -> Self
    func evaluate(for player: Player) -> Evaluation
}

正确实现后，它可能看起来像这样

struct ConnectThreeGame: CarloGame, CustomStringConvertible, Equatable {
    typealias Player = ConnectThreePlayer
    typealias Move = ConnectThreeMove

    var array: Array<Int>
  
    // REQUIRED
    var currentPlayer: Player
    
    init(length: Int = 10, currentPlayer: Player = .one) {
        self.array = Array.init(repeating: 0, count: length)
        self.currentPlayer = currentPlayer
    }

    // REQUIRED
    func availableMoves() -> [Move] {
        array
            .enumerated()
            .compactMap { $0.element == 0 ? Move($0.offset) : nil}
    }
    
    // REQUIRED
    func update(_ move: Move) -> Self {
        var copy = self
        copy.array[move] = currentPlayer.rawValue
        copy.currentPlayer = currentPlayer.opposite
        return copy
    }
    
    // REQUIRED
    func evaluate(for player: Player) -> Evaluation {
        let player3 = three(for: player)
        let oppo3 = three(for: player.opposite)
        let remaining0 = array.contains(0)
        switch (player3, oppo3, remaining0) {
        case (true, true, _): return .draw
        case (true, false, _): return .win
        case (false, true, _): return .loss
        case (false, false, false): return .draw
        default: return .ongoing(0.5)
        }
    }
    
    private func three(for player: Player) -> Bool {
        var count = 0
        for slot in array {
            if slot == player.rawValue {
                count += 1
            } else {
                count = 0
            }
            if count == 3 {
                return true
            }
        }
        return false
    }
    
    var description: String {
        return array.reduce(into: "") { result, i in
            result += String(i)
        }
    }
}

使用

通过在 CarloGame 上搭建 CarloTactician 来使用 Carlo

typealias Computer = CarloTactician<ConnectThreeGame>

使用 CarloGamePlayer 的参数和单次搜索迭代中展开的回合数的限制来实例化

let computer = Computer(for: .two, maxRolloutDepth: 5)

调用 .iterate() 方法在树中执行一次搜索迭代，调用 .bestMove 来获取搜索算法找到的最佳移动（目前为止），以及调用 .uproot(to:) 来回收树并更新内部游戏状态

var game = ConnectThreeGame(length: 10, currentPlayer: .one)
/// 0000000000
game = game.update(4)
/// 0000100000
game = game.update(0)
/// 2000100000
game = game.update(7)
/// 2000100000
game = game.update(2)
/// 2020100000
game = game.update(9)
/// 2020100001 ... player 2 can win if move => 1

computer.uproot(to: game)
for _ in 0..<50 {
    computer.iterate()
}

let move = computer.bestMove!
game = game.update(move)
/// 2220100001 ... game over

安装

如果您使用 Swift Package Manager，将 Carlo 添加为依赖项就像将其添加到您的 Package.swift 的 dependencies 中一样简单

dependencies: [
    .package(url: "https://github.com/maxhumber/Carlo.git", from: "1.0.2")
]