bot.gno
8.09 Kb · 340 lines
1package minichess
2
3// The bot is an iterative-deepening negamax search with alpha-beta pruning,
4// a check extension and a capped quiescence search. Every level has a hard
5// node budget, so the gas a bot reply costs is bounded no matter how
6// complicated the position is. It is fully deterministic: the same
7// position, level and seed always produce the same move.
8
9const (
10 MinLevel = 1
11 MaxLevel = 3
12
13 mateScore = 100000
14 infScore = 1000000
15 maxPly = 12
16)
17
18// LevelInfo describes the search limits of a bot level.
19type LevelInfo struct {
20 Name string
21 MaxDepth int // full-width plies searched before quiescence
22 QDepth int // capture plies searched after MaxDepth
23 Budget int // maximum nodes visited per move (bounds the gas cost)
24}
25
26var levels = [MaxLevel + 1]LevelInfo{
27 {},
28 {Name: "easy", MaxDepth: 1, QDepth: 2, Budget: 200},
29 {Name: "medium", MaxDepth: 2, QDepth: 3, Budget: 900},
30 {Name: "hard", MaxDepth: 3, QDepth: 3, Budget: 1500},
31}
32
33// Level returns the limits for a level, clamped to [MinLevel, MaxLevel].
34func Level(level int) LevelInfo {
35 if level < MinLevel {
36 level = MinLevel
37 }
38 if level > MaxLevel {
39 level = MaxLevel
40 }
41 return levels[level]
42}
43
44// Evaluate scores the position in centipawns from the side to move's view.
45func (p Position) Evaluate() int {
46 return newEngine(&p).eval()
47}
48
49func (e *engine) eval() int {
50 if e.turn == Black {
51 return -e.score
52 }
53 return e.score
54}
55
56// BestMove returns the bot's choice for the side to move. seed breaks ties
57// between equally scored moves so games don't all look identical; pass
58// something like gameID*1000+ply. ok is false if there are no legal moves.
59func BestMove(p Position, level int, seed int) (Move, bool) {
60 best, _, ok := searchWith(p, Level(level), seed, nil)
61 return best, ok
62}
63
64// BestMoveWithHistory is BestMove for a game in progress: history holds
65// the Hash of earlier positions (since the last capture or pawn move).
66// Moves that repeat one of them are scored as a draw, so the bot avoids
67// repetition when it is ahead and steers toward it when it is behind.
68func BestMoveWithHistory(p Position, level int, seed int, history []uint64) (Move, bool) {
69 best, _, ok := searchWith(p, Level(level), seed, history)
70 return best, ok
71}
72
73// Hash returns a 64-bit hash of the position (for repetition tracking).
74func (p Position) Hash() uint64 {
75 return newEngine(&p).hash()
76}
77
78// search is BestMove plus the number of nodes visited (for tests).
79func search(p Position, level int, seed int) (Move, int, bool) {
80 return searchWith(p, Level(level), seed, nil)
81}
82
83func searchWith(p Position, info LevelInfo, seed int, history []uint64) (Move, int, bool) {
84 e := newEngine(&p)
85 order := e.legal()
86 if len(order) == 0 {
87 return Move{}, 0, false
88 }
89 if len(order) == 1 {
90 return decode(order[0]), 0, true
91 }
92 e.budget = info.Budget
93 e.qdepth = info.QDepth
94 if seed < 0 {
95 seed = -seed
96 }
97
98 var chosen []int
99 for depth := 1; depth <= info.MaxDepth; depth++ {
100 bestScore := -infScore
101 var ties []int
102 for _, m := range order {
103 // Window (bestScore-1, inf): equal-best moves get exact scores,
104 // worse moves fail low at <= bestScore-1.
105 alpha := -infScore
106 if bestScore > -infScore {
107 alpha = bestScore - 1
108 }
109 u := e.make(m)
110 score := 0 // a repeated position counts as a draw
111 if len(history) == 0 || !containsU64(history, e.hash()) {
112 score = -e.negamax(depth-1, -infScore, -alpha, 1, e.givesCheck(m, u))
113 }
114 e.unmake(m, u)
115 if e.aborted {
116 break
117 }
118 if score > bestScore {
119 bestScore = score
120 ties = []int{m}
121 } else if score == bestScore {
122 ties = append(ties, m)
123 }
124 }
125 if e.aborted {
126 // Moves are searched best-first, so any move that finished at
127 // this depth is at least as reliable as the previous result.
128 if len(ties) > 0 {
129 chosen = ties
130 }
131 break
132 }
133 chosen = ties
134 if bestScore >= mateScore-maxPly || depth == info.MaxDepth {
135 break // forced mate found, or done
136 }
137 // Search the current best moves first in the next iteration.
138 next := make([]int, 0, len(order))
139 next = append(next, ties...)
140 for _, m := range order {
141 if !containsInt(ties, m) {
142 next = append(next, m)
143 }
144 }
145 order = next
146 }
147 if len(chosen) == 0 {
148 chosen = order[:1] // budget ran out before depth 1 finished
149 }
150 return decode(chosen[seed%len(chosen)]), e.nodes, true
151}
152
153func containsU64(list []uint64, x uint64) bool {
154 for _, y := range list {
155 if y == x {
156 return true
157 }
158 }
159 return false
160}
161
162func containsInt(list []int, x int) bool {
163 for _, y := range list {
164 if y == x {
165 return true
166 }
167 }
168 return false
169}
170
171// captureKey ranks a capture: most valuable victim first, then least
172// valuable attacker (MVV-LVA). Promotions count as winning a queen.
173func (e *engine) captureKey(m int) int {
174 v := pieceValue[e.b[(m>>6)&63].Type()]*16 - int(e.b[m&63].Type())
175 if m >= 4096 {
176 v += pieceValue[Queen] * 16
177 }
178 return v
179}
180
181// orderCaptures sorts captures by captureKey, best first.
182func (e *engine) orderCaptures(caps []int, n int) {
183 for i := 1; i < n; i++ {
184 m := caps[i]
185 v := e.captureKey(m)
186 j := i - 1
187 for j >= 0 && e.captureKey(caps[j]) < v {
188 caps[j+1] = caps[j]
189 j--
190 }
191 caps[j+1] = m
192 }
193}
194
195// killersFirst moves this ply's killer moves to the front of the quiets.
196func (e *engine) killersFirst(pb *plyBuf, ply int) {
197 if ply > maxPly {
198 return
199 }
200 front := 0
201 for k := 0; k < 2; k++ {
202 km := e.killers[ply][k]
203 if km == 0 {
204 continue
205 }
206 for j := front; j < pb.nq; j++ {
207 if pb.quiets[j] == km {
208 pb.quiets[j], pb.quiets[front] = pb.quiets[front], km
209 front++
210 break
211 }
212 }
213 }
214}
215
216func (e *engine) addKiller(ply, m int) {
217 if e.killers[ply][0] != m {
218 e.killers[ply][1] = e.killers[ply][0]
219 e.killers[ply][0] = m
220 }
221}
222
223// negamax assumes the position is legal; inCheck says whether the side to
224// move is in check (computed cheaply by the parent via givesCheck).
225func (e *engine) negamax(depth, alpha, beta, ply int, inCheck bool) int {
226 e.nodes++
227 if e.nodes > e.budget {
228 e.aborted = true
229 return 0
230 }
231 if e.half >= 100 {
232 return 0
233 }
234 if depth <= 0 {
235 if !inCheck || ply >= maxPly {
236 return e.quiesce(alpha, beta, ply, 0, inCheck)
237 }
238 depth = 1 // check extension: never stop the search in check
239 }
240 pb := e.buf(ply)
241 e.gen(pb, false)
242 if pb.nc > 1 {
243 e.orderCaptures(pb.caps, pb.nc)
244 }
245 e.killersFirst(pb, ply)
246
247 best := -infScore
248 nc, n := pb.nc, pb.nc+pb.nq
249 for i := 0; i < n; i++ {
250 m := 0
251 if i < nc {
252 m = pb.caps[i]
253 } else {
254 m = pb.quiets[i-nc]
255 }
256 u := e.make(m)
257 if !e.moveIsLegal(m, u, inCheck) {
258 e.unmake(m, u)
259 continue
260 }
261 score := -e.negamax(depth-1, -beta, -alpha, ply+1, e.givesCheck(m, u))
262 e.unmake(m, u)
263 if e.aborted {
264 return 0
265 }
266 if score > best {
267 best = score
268 if score > alpha {
269 alpha = score
270 if alpha >= beta {
271 if i >= nc && ply <= maxPly {
272 e.addKiller(ply, m)
273 }
274 return best
275 }
276 }
277 }
278 }
279 if best == -infScore { // no legal moves
280 if inCheck {
281 return -mateScore + ply
282 }
283 return 0 // stalemate
284 }
285 return best
286}
287
288func (e *engine) quiesce(alpha, beta, ply, qdepth int, inCheck bool) int {
289 e.nodes++
290 if e.nodes > e.budget {
291 e.aborted = true
292 return 0
293 }
294 if inCheck && ply < maxPly {
295 // Standing pat is not an option in check: search all evasions.
296 return e.negamax(1, alpha, beta, ply, true)
297 }
298 stand := e.eval()
299 if stand >= beta || qdepth >= e.qdepth {
300 return stand
301 }
302 if stand+1000 <= alpha {
303 return alpha // delta pruning: even winning a queen can't help
304 }
305 if stand > alpha {
306 alpha = stand
307 }
308 pb := e.buf(ply)
309 e.gen(pb, true)
310 if pb.nc > 1 {
311 e.orderCaptures(pb.caps, pb.nc)
312 }
313 them := 1 - e.turn
314 for i := 0; i < pb.nc; i++ {
315 m := pb.caps[i]
316 // Skip losing captures: a more valuable piece taking a defended,
317 // less valuable one (e.g. queen takes a guarded pawn).
318 to := (m >> 6) & 63
319 if m < 4096 && pieceValue[e.b[m&63].Type()] > pieceValue[e.b[to].Type()] && e.attacked(to, them) {
320 continue
321 }
322 u := e.make(m)
323 if !e.moveIsLegal(m, u, inCheck) {
324 e.unmake(m, u)
325 continue
326 }
327 score := -e.quiesce(-beta, -alpha, ply+1, qdepth+1, e.givesCheck(m, u))
328 e.unmake(m, u)
329 if e.aborted {
330 return 0
331 }
332 if score >= beta {
333 return score
334 }
335 if score > alpha {
336 alpha = score
337 }
338 }
339 return alpha
340}
