-
Notifications
You must be signed in to change notification settings - Fork 87
/
AlphaBeta.swift
211 lines (174 loc) · 8.66 KB
/
AlphaBeta.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
//
// AlphaBeta.swift
// AIToolbox
//
// Created by Kevin Coble on 2/23/15.
// Copyright (c) 2015 Kevin Coble. All rights reserved.
//
import Foundation
/// The AlphaBetaNode protocol is used to provide move generation and static evaluation routines to your node
public protocol AlphaBetaNode {
func generateMoves(_ forMaximizer: Bool) -> [AlphaBetaNode] // Get the nodes for each move below this node
func staticEvaluation() -> Double // Evaluate the worth of this node
}
open class AlphaBetaGraph {
public init() {
}
open func startAlphaBetaWithNode(_ startNode: AlphaBetaNode, forDepth: Int, startingAsMaximizer : Bool = true) -> AlphaBetaNode? {
// Start the recursion
let α = -Double.infinity
let β = Double.infinity
return alphaBeta(startNode, remainingDepth: forDepth, alpha: α, beta : β, maximizer: startingAsMaximizer, topLevel: true).winningNode
}
func alphaBeta(_ currentNode: AlphaBetaNode, remainingDepth: Int, alpha : Double, beta : Double, maximizer: Bool, topLevel : Bool) -> (value: Double, winningNode: AlphaBetaNode?) {
// if this is a leaf node, return the static evaluation
if (remainingDepth == 0) {
return (value: currentNode.staticEvaluation(), winningNode: currentNode)
}
let nextDepth = remainingDepth - 1
// Generate the child nodes
let children = currentNode.generateMoves(maximizer)
// If no children, return the static evaluation for this node
if (children.count == 0) {
return (value: currentNode.staticEvaluation(), winningNode: currentNode)
}
if (topLevel && children.count == 1) {
// Only one move, so we must take it - no reason to evaluate actual values
return (value: 0.0, winningNode: children[0])
}
var winningNode : AlphaBetaNode?
var α = alpha
var β = beta
// If the maximizer, maximize the alpha, and prune with the beta
if (maximizer) {
var value = -Double.infinity
// Iterate through the child nodes
for child in children {
let childValue = alphaBeta(child, remainingDepth: nextDepth, alpha: α, beta: β, maximizer: false, topLevel: false).value
if (childValue > value) {
value = childValue
winningNode = child
}
value = childValue > value ? childValue : value
α = value > α ? value : α
if (β <= α) { // β pruning
break
}
}
return (value: value, winningNode: winningNode)
}
// If the minimizer, maximize the beta, and prune with the alpha
else {
var value = Double.infinity
// Iterate through the child nodes
for child in children {
let childValue = alphaBeta(child, remainingDepth: nextDepth, alpha: α, beta: β, maximizer: true, topLevel: false).value
if (childValue < value) {
value = childValue
winningNode = child
}
β = value < β ? value : β
if (β <= α) { // α pruning
break
}
}
return (value: value, winningNode: winningNode)
}
}
open func startAlphaBetaConcurrentWithNode(_ startNode: AlphaBetaNode, forDepth: Int, startingAsMaximizer : Bool = true) -> AlphaBetaNode? {
// Start the recursion
let α = -Double.infinity
let β = Double.infinity
return alphaBetaConcurrent(startNode, remainingDepth: forDepth, alpha: α, beta : β, maximizer: startingAsMaximizer, topLevel: true).winningNode
}
func alphaBetaConcurrent(_ currentNode: AlphaBetaNode, remainingDepth: Int, alpha : Double, beta : Double, maximizer: Bool, topLevel : Bool) -> (value: Double, winningNode: AlphaBetaNode?) {
// if this is a leaf node, return the static evaluation
if (remainingDepth == 0) {
return (value: currentNode.staticEvaluation(), winningNode: currentNode)
}
let nextDepth = remainingDepth - 1
// Generate the child nodes
let children = currentNode.generateMoves(maximizer)
// If no children, return the static evaluation for this node
if (children.count == 0) {
return (value: currentNode.staticEvaluation(), winningNode: currentNode)
}
if (topLevel && children.count == 1) {
// Only one move, so we must take it - no reason to evaluate actual values
return (value: 0.0, winningNode: children[0])
}
// Create the value array
var childValues : [Double] = Array(repeating: 0.0, count: children.count)
// Get the concurrent queue and group
let tQueue = DispatchQueue.global(qos: DispatchQoS.QoSClass.default)
let tGroup = DispatchGroup()
var winningNode : AlphaBetaNode?
var α = alpha
var β = beta
// If the maximizer, maximize the alpha, and prune with the beta
if (maximizer) {
// Process the first child without concurrency - the alpha-beta range returned allows pruning of the other trees
var value = alphaBetaConcurrent(children[0], remainingDepth: nextDepth, alpha: α, beta: β, maximizer: false, topLevel: false).value
winningNode = children[0]
α = value > α ? value : α
if (β <= α) { // β pruning
return (value: value, winningNode: winningNode)
}
// Iterate through the rest of the child nodes
if (children.count > 1) {
for index in 1..<children.count {
tQueue.async(group: tGroup, execute: {() -> Void in
childValues[index] = self.alphaBetaConcurrent(children[index], remainingDepth: nextDepth, alpha: α, beta: β, maximizer: false, topLevel: false).value
})
}
// Wait for the evaluations
tGroup.wait()
// Prune and find best
for index in 1..<children.count {
if (childValues[index] > value) {
value = childValues[index]
winningNode = children[index]
}
value = childValues[index] > value ? childValues[index] : value
α = value > α ? value : α
if (β <= α) { // β pruning
break
}
}
}
return (value: value, winningNode: winningNode)
}
// If the minimizer, maximize the beta, and prune with the alpha
else {
// Process the first child without concurrency - the alpha-beta range returned allows pruning of the other trees
var value = alphaBetaConcurrent(children[0], remainingDepth: nextDepth, alpha: α, beta: β, maximizer: true, topLevel: false).value
winningNode = children[0]
β = value < β ? value : β
if (β <= α) { // α pruning
return (value: value, winningNode: winningNode)
}
// Iterate through the rest of the child nodes
if (children.count > 1) {
for index in 1..<children.count {
tQueue.async(group: tGroup, execute: {() -> Void in
childValues[index] = self.alphaBetaConcurrent(children[index], remainingDepth: nextDepth, alpha: α, beta: β, maximizer: true, topLevel: false).value
})
}
// Wait for the evaluations
tGroup.wait()
// Prune and find best
for index in 1..<children.count {
if (childValues[index] < value) {
value = childValues[index]
winningNode = children[index]
}
β = value < β ? value : β
if (β <= α) { // α pruning
break
}
}
}
return (value: value, winningNode: winningNode)
}
}
}