engine.gno
15.91 Kb · 671 lines
1package minichess
2
3// engine is the mutable, allocation-light core used by move generation and
4// the bot. GnoVM charges gas per operation (roughly 1k gas per loop
5// iteration, ~4k per append), so the engine uses precomputed tables, piece
6// lists (only occupied squares are visited), integer-encoded moves written
7// into reused buffers, in-place make/unmake and an incrementally updated
8// evaluation.
9
10// Encoded move: from | to<<6 | promo<<12.
11func enc(from, to int, promo Piece) int { return from | to<<6 | int(promo)<<12 }
12
13func decode(m int) Move {
14 return Move{From: m & 63, To: (m >> 6) & 63, Promo: Piece(m >> 12)}
15}
16
17func (m Move) encode() int { return enc(m.From, m.To, m.Promo) }
18
19const bufSize = 256 // more than the maximum number of pseudo-legal moves
20
21// Lookup tables. A deployed package pays a storage deposit for everything
22// it persists, so target-square lists are stored as strings (one byte per
23// square): compact on-chain, and ranging over them costs about the same
24// gas as ranging over a slice.
25var (
26 knightT [NumSquares]string
27 kingT [NumSquares]string
28 rays [NumSquares * 8]string // [sq*8+dir]; dirs 0-3 orthogonal, 4-7 diagonal
29 pawnAtk [2 * NumSquares]string // [c*64+sq]: squares a pawn of colour c on sq attacks
30 psqt [13][NumSquares]int // [piece+6][sq], signed (white +)
31
32 // geo[a*64+b] flags: geoLine (shared rank/file/diagonal), geoKnight,
33 // geoKing (adjacent).
34 geo string
35)
36
37const (
38 geoLine byte = 1
39 geoKnight byte = 2
40 geoKing byte = 4
41)
42
43var pieceValue = [7]int{0, 100, 320, 330, 500, 900, 0}
44
45func inside(r, f int) bool { return r >= 0 && r < Size && f >= 0 && f < Size }
46
47// init fills the lookup tables. Pure packages are immutable after init, so
48// the tables are built once here and only read afterwards.
49func init() {
50 dirs8 := [8][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}
51 knightD := [8][2]int{{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}}
52
53 // Piece-square tables ("simplified evaluation function"), written
54 // from white's point of view with rank 8 first.
55 pst := [7][64]int{
56 {},
57 { // pawn
58 0, 0, 0, 0, 0, 0, 0, 0,
59 50, 50, 50, 50, 50, 50, 50, 50,
60 10, 10, 20, 30, 30, 20, 10, 10,
61 5, 5, 10, 25, 25, 10, 5, 5,
62 0, 0, 0, 20, 20, 0, 0, 0,
63 5, -5, -10, 0, 0, -10, -5, 5,
64 5, 10, 10, -20, -20, 10, 10, 5,
65 0, 0, 0, 0, 0, 0, 0, 0,
66 },
67 { // knight
68 -50, -40, -30, -30, -30, -30, -40, -50,
69 -40, -20, 0, 0, 0, 0, -20, -40,
70 -30, 0, 10, 15, 15, 10, 0, -30,
71 -30, 5, 15, 20, 20, 15, 5, -30,
72 -30, 0, 15, 20, 20, 15, 0, -30,
73 -30, 5, 10, 15, 15, 10, 5, -30,
74 -40, -20, 0, 5, 5, 0, -20, -40,
75 -50, -40, -30, -30, -30, -30, -40, -50,
76 },
77 { // bishop
78 -20, -10, -10, -10, -10, -10, -10, -20,
79 -10, 0, 0, 0, 0, 0, 0, -10,
80 -10, 0, 5, 10, 10, 5, 0, -10,
81 -10, 5, 5, 10, 10, 5, 5, -10,
82 -10, 0, 10, 10, 10, 10, 0, -10,
83 -10, 10, 10, 10, 10, 10, 10, -10,
84 -10, 5, 0, 0, 0, 0, 5, -10,
85 -20, -10, -10, -10, -10, -10, -10, -20,
86 },
87 { // rook
88 0, 0, 0, 0, 0, 0, 0, 0,
89 5, 10, 10, 10, 10, 10, 10, 5,
90 -5, 0, 0, 0, 0, 0, 0, -5,
91 -5, 0, 0, 0, 0, 0, 0, -5,
92 -5, 0, 0, 0, 0, 0, 0, -5,
93 -5, 0, 0, 0, 0, 0, 0, -5,
94 -5, 0, 0, 0, 0, 0, 0, -5,
95 0, 0, 0, 5, 5, 0, 0, 0,
96 },
97 { // queen
98 -20, -10, -10, -5, -5, -10, -10, -20,
99 -10, 0, 0, 0, 0, 0, 0, -10,
100 -10, 0, 5, 5, 5, 5, 0, -10,
101 -5, 0, 5, 5, 5, 5, 0, -5,
102 0, 0, 5, 5, 5, 5, 0, -5,
103 -10, 5, 5, 5, 5, 5, 0, -10,
104 -10, 0, 5, 0, 0, 0, 0, -10,
105 -20, -10, -10, -5, -5, -10, -10, -20,
106 },
107 { // king (middlegame)
108 -30, -40, -40, -50, -50, -40, -40, -30,
109 -30, -40, -40, -50, -50, -40, -40, -30,
110 -30, -40, -40, -50, -50, -40, -40, -30,
111 -30, -40, -40, -50, -50, -40, -40, -30,
112 -20, -30, -30, -40, -40, -30, -30, -20,
113 -10, -20, -20, -20, -20, -20, -20, -10,
114 20, 20, 0, 0, 0, 0, 20, 20,
115 20, 30, 10, 0, 0, 10, 30, 20,
116 },
117 }
118
119 sqs := func(list []int) string {
120 b := make([]byte, len(list))
121 for i, v := range list {
122 b[i] = byte(v)
123 }
124 return string(b)
125 }
126 for sq := 0; sq < NumSquares; sq++ {
127 r, f := sq/Size, sq%Size
128 var kn, kg []int
129 for _, d := range knightD {
130 if inside(r+d[0], f+d[1]) {
131 kn = append(kn, (r+d[0])*Size+f+d[1])
132 }
133 }
134 for i, d := range dirs8 {
135 if inside(r+d[0], f+d[1]) {
136 kg = append(kg, (r+d[0])*Size+f+d[1])
137 }
138 var ray []int
139 nr, nf := r+d[0], f+d[1]
140 for inside(nr, nf) {
141 ray = append(ray, nr*Size+nf)
142 nr += d[0]
143 nf += d[1]
144 }
145 rays[sq*8+i] = sqs(ray)
146 }
147 knightT[sq] = sqs(kn)
148 kingT[sq] = sqs(kg)
149 for c := 0; c < 2; c++ {
150 nr := r + 1
151 if c == 1 {
152 nr = r - 1
153 }
154 var pa []int
155 for _, df := range [2]int{-1, 1} {
156 if inside(nr, f+df) {
157 pa = append(pa, nr*Size+f+df)
158 }
159 }
160 pawnAtk[c*NumSquares+sq] = sqs(pa)
161 }
162 for t := 1; t <= 6; t++ {
163 v := pieceValue[t] + pst[t][(Size-1-r)*Size+f]
164 psqt[6+t][sq] = v
165 psqt[6-t][(Size-1-r)*Size+f] = -v
166 }
167 }
168
169 g8 := make([]byte, NumSquares*NumSquares)
170 for a := 0; a < NumSquares; a++ {
171 for b := 0; b < NumSquares; b++ {
172 if a == b {
173 continue
174 }
175 dr, df := a/Size-b/Size, a%Size-b%Size
176 var g byte
177 if dr == 0 || df == 0 || dr == df || dr == -df {
178 g |= geoLine
179 }
180 if dr*df == 2 || dr*df == -2 {
181 g |= geoKnight
182 }
183 if dr >= -1 && dr <= 1 && df >= -1 && df <= 1 {
184 g |= geoKing
185 }
186 g8[a*NumSquares+b] = g
187 }
188 }
189 geo = string(g8)
190}
191
192// castleKeep returns the castling rights that survive a move touching sq.
193func castleKeep(sq int) int {
194 switch sq {
195 case 0:
196 return ^CastleWQ
197 case 4:
198 return ^(CastleWK | CastleWQ)
199 case 7:
200 return ^CastleWK
201 case 56:
202 return ^CastleBQ
203 case 60:
204 return ^(CastleBK | CastleBQ)
205 case 63:
206 return ^CastleBK
207 }
208 return ^0
209}
210
211type undo struct {
212 moved Piece
213 captured Piece
214 capSq int
215 capIdx int
216 castle int
217 ep int
218 half int
219 score int
220 special int // 0 normal, 1 en passant, 2 castling
221}
222
223// plyBuf holds the moves generated at one search ply.
224type plyBuf struct {
225 caps []int
226 quiets []int
227 nc, nq int
228}
229
230func newPlyBuf() *plyBuf {
231 return &plyBuf{caps: make([]int, bufSize), quiets: make([]int, bufSize)}
232}
233
234type engine struct {
235 b [NumSquares]Piece
236 turn Color
237 castle int
238 ep int
239 half int
240 kings [2]int
241 score int // white-perspective evaluation, updated incrementally
242
243 // Piece lists: squares of each side's pieces, and each occupied
244 // square's index in its list.
245 plist [2][16]int
246 pcount [2]int
247 pidx [NumSquares]int
248
249 nodes int
250 budget int
251 qdepth int
252 aborted bool
253 bufs []*plyBuf
254 killers [maxPly + 2][2]int // quiet moves that caused a cutoff, per ply
255}
256
257func newEngine(p *Position) *engine {
258 e := &engine{b: p.Board, turn: p.Turn, castle: p.Castling, ep: p.EP, half: p.Halfmove}
259 for sq := 0; sq < NumSquares; sq++ {
260 pc := e.b[sq]
261 if pc == Empty {
262 continue
263 }
264 e.score += psqt[pc+6][sq]
265 c := 0
266 if pc < 0 {
267 c = 1
268 }
269 if pc.Type() == King {
270 e.kings[c] = sq
271 }
272 if e.pcount[c] < 16 {
273 e.pidx[sq] = e.pcount[c]
274 e.plist[c][e.pcount[c]] = sq
275 e.pcount[c]++
276 }
277 }
278 return e
279}
280
281func (e *engine) buf(ply int) *plyBuf {
282 for len(e.bufs) <= ply {
283 e.bufs = append(e.bufs, newPlyBuf())
284 }
285 return e.bufs[ply]
286}
287
288// attacked reports whether sq is attacked by colour by.
289func (e *engine) attacked(sq int, by Color) bool {
290 sign := Piece(1)
291 if by == Black {
292 sign = -1
293 }
294 b := &e.b
295 // A pawn of colour `by` attacks sq if it sits on a square that a pawn
296 // of the other colour on sq would attack.
297 pw := sign * Pawn
298 for _, ch := range pawnAtk[int(1-by)*NumSquares+sq] {
299 if b[int(ch)] == pw {
300 return true
301 }
302 }
303 kn := sign * Knight
304 for _, ch := range knightT[sq] {
305 if b[int(ch)] == kn {
306 return true
307 }
308 }
309 kg := sign * King
310 for _, ch := range kingT[sq] {
311 if b[int(ch)] == kg {
312 return true
313 }
314 }
315 q := sign * Queen
316 slider := sign * Rook
317 for d := 0; d < 8; d++ {
318 if d == 4 {
319 slider = sign * Bishop
320 }
321 for _, ch := range rays[sq*8+d] {
322 pc := b[int(ch)]
323 if pc != Empty {
324 if pc == slider || pc == q {
325 return true
326 }
327 break
328 }
329 }
330 }
331 return false
332}
333
334func (e *engine) inCheck() bool {
335 return e.attacked(e.kings[e.turn], 1-e.turn)
336}
337
338// gen fills pb with pseudo-legal moves: captures and queen promotions in
339// pb.caps, everything else in pb.quiets (skipped when capsOnly).
340func (e *engine) gen(pb *plyBuf, capsOnly bool) {
341 caps, quiets := pb.caps, pb.quiets
342 nc, nq := 0, 0
343 b := &e.b
344 us := e.turn
345 sign := Piece(1)
346 fwd, startRank, promoRank := Size, 1, Size-1
347 if us == Black {
348 sign, fwd, startRank, promoRank = -1, -Size, Size-2, 0
349 }
350 list := &e.plist[us]
351 for i := 0; i < e.pcount[us]; i++ {
352 sq := list[i]
353 pc := b[sq] * sign
354 switch pc {
355 case Pawn:
356 to := sq + fwd
357 promo := to/Size == promoRank
358 if b[to] == Empty {
359 if promo {
360 caps[nc] = enc(sq, to, Queen)
361 nc++
362 if !capsOnly {
363 quiets[nq] = enc(sq, to, Knight)
364 quiets[nq+1] = enc(sq, to, Rook)
365 quiets[nq+2] = enc(sq, to, Bishop)
366 nq += 3
367 }
368 } else if !capsOnly {
369 quiets[nq] = sq | to<<6
370 nq++
371 if sq/Size == startRank && b[to+fwd] == Empty {
372 quiets[nq] = sq | (to+fwd)<<6
373 nq++
374 }
375 }
376 }
377 for _, ch := range pawnAtk[int(us)*NumSquares+sq] {
378 t := int(ch)
379 if b[t]*sign < 0 {
380 if promo {
381 caps[nc] = enc(sq, t, Queen)
382 nc++
383 if !capsOnly {
384 quiets[nq] = enc(sq, t, Knight)
385 quiets[nq+1] = enc(sq, t, Rook)
386 quiets[nq+2] = enc(sq, t, Bishop)
387 nq += 3
388 }
389 } else {
390 caps[nc] = sq | t<<6
391 nc++
392 }
393 } else if t == e.ep {
394 caps[nc] = sq | t<<6
395 nc++
396 }
397 }
398 case Knight, King:
399 targets := knightT[sq]
400 if pc == King {
401 targets = kingT[sq]
402 }
403 for _, ch := range targets {
404 t := int(ch)
405 v := b[t]
406 if v == Empty {
407 if !capsOnly {
408 quiets[nq] = sq | t<<6
409 nq++
410 }
411 } else if v*sign < 0 {
412 caps[nc] = sq | t<<6
413 nc++
414 }
415 }
416 default: // sliders
417 lo, hi := 0, 8
418 if pc == Rook {
419 hi = 4
420 } else if pc == Bishop {
421 lo = 4
422 }
423 for d := lo; d < hi; d++ {
424 for _, ch := range rays[sq*8+d] {
425 t := int(ch)
426 v := b[t]
427 if v == Empty {
428 if !capsOnly {
429 quiets[nq] = sq | t<<6
430 nq++
431 }
432 continue
433 }
434 if v*sign < 0 {
435 caps[nc] = sq | t<<6
436 nc++
437 }
438 break
439 }
440 }
441 }
442 }
443 if !capsOnly && e.castle != 0 {
444 nq = e.genCastles(quiets, nq)
445 }
446 pb.nc, pb.nq = nc, nq
447}
448
449// genCastles adds castling moves. The king may not castle out of, through
450// or into check, and the squares between king and rook must be empty.
451func (e *engine) genCastles(quiets []int, nq int) int {
452 b := &e.b
453 them := 1 - e.turn
454 base, rook, kRight, qRight := 0, Rook, CastleWK, CastleWQ
455 if e.turn == Black {
456 base, rook, kRight, qRight = 56, -Rook, CastleBK, CastleBQ
457 }
458 k := base + 4
459 if e.castle&kRight != 0 && b[base+5] == Empty && b[base+6] == Empty && b[base+7] == rook &&
460 !e.attacked(k, them) && !e.attacked(k+1, them) && !e.attacked(k+2, them) {
461 quiets[nq] = k | (k+2)<<6
462 nq++
463 }
464 if e.castle&qRight != 0 && b[base+3] == Empty && b[base+2] == Empty && b[base+1] == Empty &&
465 b[base] == rook && !e.attacked(k, them) && !e.attacked(k-1, them) && !e.attacked(k-2, them) {
466 quiets[nq] = k | (k-2)<<6
467 nq++
468 }
469 return nq
470}
471
472// movePiece updates the board and piece list for a piece moving from->to.
473func (e *engine) movePiece(c Color, from, to int) {
474 i := e.pidx[from]
475 e.plist[c][i] = to
476 e.pidx[to] = i
477 e.b[to] = e.b[from]
478 e.b[from] = Empty
479}
480
481// removePiece takes the piece on sq out of colour c's list; returns its
482// former index so restorePiece can undo it exactly.
483func (e *engine) removePiece(c Color, sq int) int {
484 i := e.pidx[sq]
485 n := e.pcount[c] - 1
486 last := e.plist[c][n]
487 e.plist[c][i] = last
488 e.pidx[last] = i
489 e.pcount[c] = n
490 return i
491}
492
493func (e *engine) restorePiece(c Color, sq, i int) {
494 n := e.pcount[c]
495 moved := e.plist[c][i]
496 e.plist[c][n] = moved
497 e.pidx[moved] = n
498 e.plist[c][i] = sq
499 e.pidx[sq] = i
500 e.pcount[c] = n + 1
501}
502
503func (e *engine) make(m int) undo {
504 from, to := m&63, (m>>6)&63
505 us, them := e.turn, 1-e.turn
506 pc := e.b[from]
507 pt := pc.Type()
508 u := undo{moved: pc, capSq: to, castle: e.castle, ep: e.ep, half: e.half, score: e.score}
509
510 capt := e.b[to]
511 if pt == Pawn && to == e.ep && capt == Empty && (from&7) != (to&7) {
512 // En passant: the captured pawn is behind the target square.
513 u.special = 1
514 if us == White {
515 u.capSq = to - Size
516 } else {
517 u.capSq = to + Size
518 }
519 capt = e.b[u.capSq]
520 }
521 u.captured = capt
522 if capt != Empty {
523 u.capIdx = e.removePiece(them, u.capSq)
524 e.score -= psqt[capt+6][u.capSq]
525 e.b[u.capSq] = Empty
526 }
527
528 e.movePiece(us, from, to)
529 np := pc
530 if m >= 4096 {
531 np = Piece(m >> 12)
532 if pc < 0 {
533 np = -np
534 }
535 e.b[to] = np
536 }
537 e.score += psqt[np+6][to] - psqt[pc+6][from]
538
539 if pt == King {
540 e.kings[us] = to
541 if to-from == 2 || from-to == 2 {
542 u.special = 2
543 rf, rt := from+3, from+1
544 if to < from {
545 rf, rt = from-4, from-1
546 }
547 rk := e.b[rf]
548 e.movePiece(us, rf, rt)
549 e.score += psqt[rk+6][rt] - psqt[rk+6][rf]
550 }
551 }
552 if e.castle != 0 {
553 e.castle &= castleKeep(from) & castleKeep(to)
554 }
555 e.ep = -1
556 if pt == Pawn && (to-from == 16 || from-to == 16) {
557 e.ep = (from + to) / 2
558 }
559 if pt == Pawn || capt != Empty {
560 e.half = 0
561 } else {
562 e.half++
563 }
564 e.turn = them
565 return u
566}
567
568func (e *engine) unmake(m int, u undo) {
569 from, to := m&63, (m>>6)&63
570 them := e.turn
571 us := 1 - them
572 e.turn = us
573 if u.special == 2 {
574 rf, rt := from+3, from+1
575 if to < from {
576 rf, rt = from-4, from-1
577 }
578 e.movePiece(us, rt, rf)
579 }
580 e.movePiece(us, to, from)
581 e.b[from] = u.moved
582 if u.moved == King || u.moved == -King {
583 e.kings[us] = from
584 }
585 if u.captured != Empty {
586 e.b[u.capSq] = u.captured
587 e.restorePiece(them, u.capSq, u.capIdx)
588 }
589 e.castle, e.ep, e.half, e.score = u.castle, u.ep, u.half, u.score
590}
591
592// moveIsLegal is called right after make(m) (so e.turn is the opponent).
593// wasInCheck says whether the mover was in check before m. A normal
594// non-king move from a square not lined up with its own king cannot
595// expose that king, so the attack test is skipped.
596func (e *engine) moveIsLegal(m int, u undo, wasInCheck bool) bool {
597 k := e.kings[1-e.turn]
598 if !wasInCheck && u.special == 0 && u.moved != King && u.moved != -King &&
599 geo[k*NumSquares+m&63]&geoLine == 0 {
600 return true
601 }
602 return !e.attacked(k, e.turn)
603}
604
605// givesCheck is called right after make(m): does the side to move now
606// stand in check? Cheap geometric filters avoid most attack tests.
607func (e *engine) givesCheck(m int, u undo) bool {
608 ek := e.kings[e.turn]
609 from, to := m&63, (m>>6)&63
610 g := ek * NumSquares
611 maybe := u.special != 0 || geo[g+from]&geoLine != 0 // castling, e.p., discovery
612 if !maybe {
613 switch e.b[to].Type() {
614 case Knight:
615 maybe = geo[g+to]&geoKnight != 0
616 case Pawn:
617 maybe = geo[g+to]&geoKing != 0
618 case King:
619 default:
620 maybe = geo[g+to]&geoLine != 0
621 }
622 }
623 return maybe && e.attacked(ek, 1-e.turn)
624}
625
626// legal returns the legal moves (captures first) as encoded ints.
627func (e *engine) legal() []int {
628 pb := newPlyBuf()
629 e.gen(pb, false)
630 out := make([]int, 0, pb.nc+pb.nq)
631 for i := 0; i < pb.nc+pb.nq; i++ {
632 m := 0
633 if i < pb.nc {
634 m = pb.caps[i]
635 } else {
636 m = pb.quiets[i-pb.nc]
637 }
638 u := e.make(m)
639 if !e.attacked(e.kings[1-e.turn], e.turn) {
640 out = append(out, m)
641 }
642 e.unmake(m, u)
643 }
644 return out
645}
646
647// mix is a splitmix64-style mixer used to build position hashes.
648func mix(x uint64) uint64 {
649 x += 0x9e3779b97f4a7c15
650 x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9
651 x = (x ^ (x >> 27)) * 0x94d049bb133111eb
652 return x ^ (x >> 31)
653}
654
655// hash is a Zobrist-style hash of the position (pieces, side to move,
656// castling rights, en passant square), used to detect repetitions.
657func (e *engine) hash() uint64 {
658 var h uint64
659 for c := 0; c < 2; c++ {
660 for i := 0; i < e.pcount[c]; i++ {
661 sq := e.plist[c][i]
662 h ^= mix(uint64(int(e.b[sq]+6)*NumSquares + sq))
663 }
664 }
665 return h ^ mix(uint64(1000+int(e.turn)+2*e.castle+32*(e.ep+1)))
666}
667
668// position converts the engine state back to a Position.
669func (e *engine) position(fullmove int) Position {
670 return Position{Board: e.b, Turn: e.turn, Castling: e.castle, EP: e.ep, Halfmove: e.half, Fullmove: fullmove}
671}
