engine.gno
28.65 Kb ยท 1197 lines
1// Package chess implements a simple chess engine, designed to implement all
2// of the official FIDE rules with the intention of validating moves for a
3// "chess server" realm (gno.land/r/demo/chess).
4//
5// To implement the rules, the FIDE "Laws of Chess" are used as a reference:
6// https://www.fide.com/FIDE/handbook/LawsOfChess.pdf
7//
8// This package was designed with a focus on clarity and on using this code as
9// a didactic tool. Any contributions to the code should respect this.
10package chess
11
12import (
13 "errors"
14 "sort"
15 "strconv"
16 "strings"
17
18 "gno.land/p/morgan/chess/zobrist"
19)
20
21// PositionFlags. The lower 4 bits indicate an en passant column; the upper
22// 4 indicate castling rights.
23type PositionFlags byte
24
25const (
26 EnPassant PositionFlags = 1 << (iota + 3)
27 NoCastleWQ
28 NoCastleWK
29 NoCastleBQ
30 NoCastleBK
31
32 MaskEnPassant = 7 // low 4 bits
33)
34
35// CastlingRights returns FEN castling rights.
36// https://www.chessprogramming.org/Forsyth-Edwards_Notation#Castling_ability
37func (p PositionFlags) CastlingRights() string {
38 s := ""
39 if p&NoCastleWK == 0 {
40 s += "K"
41 }
42 if p&NoCastleWQ == 0 {
43 s += "Q"
44 }
45 if p&NoCastleBK == 0 {
46 s += "k"
47 }
48 if p&NoCastleBQ == 0 {
49 s += "q"
50 }
51 if s == "" {
52 return "-"
53 }
54 return s
55}
56
57// Position contains the information about a chessboard, and surrounding
58// context: the previous moves, the castling rights and "en passant" column.
59//
60// NOTE: the position of a piece is encoded in a [Square].
61type Position struct {
62 B Board
63 Moves []Move
64 Flags PositionFlags
65
66 // Halfmoves since the last pawn move or capture.
67 // https://www.chessprogramming.org/Halfmove_Clock
68 HalfMoveClock uint16
69 // Used to calculate repeating positions (3- 5-fold repetition).
70 // Zobrist hashing: https://www.chessprogramming.org/Zobrist_Hashing
71 // Reset together with halfmove clock.
72 Hashes []uint64
73}
74
75// NewPosition returns a new Position, set up with the initial board position.
76func NewPosition() Position {
77 return Position{
78 B: NewBoard(),
79 Moves: make([]Move, 0, 80), // typical chess game is ~40 moves, 80 half-moves
80 Hashes: []uint64{zobrist.InitialPosition},
81 }
82}
83
84// Color of the "next" move after p.Moves. (White for even len(p.Moves),
85// Black otherwise)
86func (p Position) Color() Color { return Color(len(p.Moves)&1 == 1) }
87
88// uintSlice attaches the methods of sort.Interface to []uint64, sorting in increasing order.
89type uintSlice []uint64
90
91func (x uintSlice) Len() int { return len(x) }
92func (x uintSlice) Less(i, j int) bool { return x[i] < x[j] }
93func (x uintSlice) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
94
95// maxHashCount counts the maximum number of repeating hashes in p.Hashes.
96func (p Position) maxHashCount() int {
97 if len(p.Hashes) == 0 {
98 return 0
99 }
100 sort.Sort(uintSlice(p.Hashes))
101 var last uint64
102 var cur, max int
103 for _, v := range p.Hashes {
104 if last != v {
105 last = v
106 if cur >= max {
107 max = cur
108 }
109 cur = 0
110 }
111 cur++
112 }
113 if cur >= max {
114 max = cur
115 }
116 return max
117}
118
119func sign(n int8) int8 {
120 switch {
121 case n > 0:
122 return 1
123 case n < 0:
124 return -1
125 default:
126 return 0
127 }
128}
129
130func abs(n int8) int8 {
131 return n * sign(n)
132}
133
134// EncodeFEN encodes p into FEN.
135// https://www.chessprogramming.org/Forsyth-Edwards_Notation
136func (p Position) EncodeFEN() string {
137 var s string
138 emptyCount := 0
139 // FEN has different ordering from us, as [0] is a black rook while for us
140 // is a white rook. So we need to invert the order of rows.
141 for i := 56; i >= 0; i++ {
142 v := p.B[i]
143 if v == PieceEmpty {
144 emptyCount++
145 if i%8 == 7 {
146 s += strconv.Itoa(emptyCount) + "/"
147 emptyCount = 0
148 i -= 16
149 }
150 continue
151 }
152 if emptyCount > 0 {
153 s += strconv.Itoa(emptyCount)
154 emptyCount = 0
155 }
156 s += v.String()
157 if i%8 == 7 {
158 s += "/"
159 i -= 16
160 }
161 }
162 // remove trailing slash
163 s = s[:len(s)-1]
164
165 strs := []string{
166 s, // 0: piece placement
167 "w", // 1: side to move
168 p.Flags.CastlingRights(), // 2: castling ability
169 "-", // 3: e.p. target square
170
171 strconv.Itoa(int(p.HalfMoveClock)), // 4: halfmove clock
172 strconv.Itoa(len(p.Moves)/2 + 1), // 5: fullmove counter
173 }
174
175 var epFile byte
176 if p.Flags&EnPassant > 0 {
177 epFile = 'a' + byte(p.Flags&MaskEnPassant)
178 }
179
180 if p.Color() == Black {
181 strs[1] = "b"
182 if epFile != 0 {
183 strs[3] = string(epFile) + "3"
184 }
185 } else if epFile != 0 {
186 strs[3] = string(epFile) + "6"
187 }
188
189 return strings.Join(strs, " ")
190}
191
192// ValidateMove checks whether the given move is legal in Chess.
193//
194// Caller must guarantee m.To and m.From to be valid (<64).
195func (p Position) ValidateMove(m Move) (newP Position, valid bool) {
196 if p.B[m.To].StripColor() == PieceKing {
197 return
198 }
199
200 return p.validateMove(m)
201}
202
203// validateMove allows for m to be a "king-capture" move, which is illegal in
204// chess, but it is useful for InCheck.
205// This is commonly known in chess programming as a "pseudo-legal" move.
206func (oldp Position) validateMove(m Move) (newPos Position, ok bool) {
207 p := oldp
208
209 piece := p.B[m.From]
210
211 // piece moved must be of player's color
212 color := p.Color()
213 if piece == PieceEmpty || piece.Color() != color ||
214 // additionally, check piece has actually moved
215 m.From == m.To {
216 return
217 }
218 // destination must not be occupied by piece of same color
219 if to := p.B[m.To]; to != PieceEmpty && to.Color() == color {
220 return
221 }
222
223 // one of the two necessarily != 0 (consequence of m.From != m.To).
224 delta := m.From.Sub(m.To)
225 dr, dc := delta[0], delta[1]
226
227 // Keep old castling rights; remove en passant info.
228 newFlags := p.Flags &^ (MaskEnPassant | EnPassant)
229 // Marked as true for succesful promotions.
230 var promoted bool
231
232 isDiag := func() bool {
233 // move diagonally (|dr| == |dc|)
234 if abs(dr) != abs(dc) {
235 return false
236 }
237 signr, signc := sign(dr), sign(dc)
238 // squares crossed must be empty
239 for i := int8(1); i < abs(dr); i++ {
240 if p.B[m.From.Move(i*signr, i*signc)] != PieceEmpty {
241 return false
242 }
243 }
244 return true
245 }
246 isHorizVert := func() bool {
247 // only one of dr, dc must be 0 (horiz/vert movement)
248 if dr != 0 && dc != 0 {
249 return false
250 }
251 // squares crossed must be empty
252 for i := int8(1); i < abs(dr); i++ {
253 if p.B[m.From.Move(i*sign(dr), 0)] != PieceEmpty {
254 return false
255 }
256 }
257 for i := int8(1); i < abs(dc); i++ {
258 if p.B[m.From.Move(0, i*sign(dc))] != PieceEmpty {
259 return false
260 }
261 }
262 return true
263 }
264
265 switch piece.StripColor() {
266 case PieceRook:
267 if !isHorizVert() {
268 return
269 }
270 // if rook has moved from a starting position, this disables castling
271 // on the side of the rook. flag accordingly in the move.
272 var fg Square
273 if color == Black {
274 fg = 7 << 3
275 }
276 switch m.From {
277 case fg: // a-col rook (either side)
278 if color == White {
279 newFlags |= NoCastleWQ
280 } else {
281 newFlags |= NoCastleBQ
282 }
283 case fg | 7: // h-col rook (either side)
284 if color == White {
285 newFlags |= NoCastleWK
286 } else {
287 newFlags |= NoCastleBK
288 }
289 }
290
291 case PieceKnight:
292 // move L-shaped
293 // rationale: if you only have positive integers, the only way you can
294 // obtain x * y == 2 is if x,y are either 1,2 or 2,1.
295 if abs(dc*dr) != 2 {
296 return
297 }
298
299 case PieceBishop:
300 if !isDiag() {
301 return
302 }
303
304 case PieceQueen:
305 if !isHorizVert() && !isDiag() {
306 return
307 }
308
309 case PieceKing:
310 // castling
311 if abs(dc) == 2 && dr == 0 {
312 // determine if castle is a valid form of castling for the given color
313 ctype := m.isCastle(color)
314 if ctype == 0 {
315 return
316 }
317
318 if false ||
319 // check that there are no previous moves which disable castling
320 p.castlingDisabled(color, ctype) ||
321 // check that we have the exact board set ups we need
322 // + make sure that the original and crossed squares are not in check
323 !p.checkCastlingSetup(ctype) {
324 return
325 }
326
327 // perform rook move here
328 p.B = p.B.castleRookMove(color, ctype)
329 // add NoCastle flags to prevent any further castling
330 if color == White {
331 newFlags |= NoCastleWQ | NoCastleWK
332 } else {
333 newFlags |= NoCastleBQ | NoCastleBK
334 }
335 break
336 }
337 // move 1sq in all directions
338 if dc < -1 || dc > 1 || dr < -1 || dr > 1 {
339 return
340 }
341 // king has moved: disable castling.
342 if color == White {
343 newFlags |= NoCastleWQ | NoCastleWK
344 } else {
345 newFlags |= NoCastleBQ | NoCastleBK
346 }
347
348 case PiecePawn:
349 // determine direction depending on color
350 dir := int8(1)
351 if color == Black {
352 dir = -1
353 }
354
355 switch {
356 case dc == 0 && dr == dir: // 1sq up
357 // destination must be empty (no captures allowed)
358 if p.B[m.To] != PieceEmpty {
359 return
360 }
361 case dc == 0 && dr == dir*2: // 2sq up (only from starting row)
362 wantRow := Square(1)
363 if color == Black {
364 wantRow = 6
365 }
366 // check starting row, and that two squares are empty
367 if (m.From>>3) != wantRow ||
368 p.B[m.From.Move(int8(dir), 0)] != PieceEmpty ||
369 p.B[m.To] != PieceEmpty {
370 return
371 }
372 _, col := m.To.Split()
373 newFlags |= EnPassant | PositionFlags(col)
374 case abs(dc) == 1 && dr == dir: // capture on diag
375 // must be a capture
376 if p.B[m.To] == PieceEmpty {
377 if sq := p.checkEnPassant(color, m.To); sq != SquareInvalid {
378 // remove other pawn
379 p.B[sq] = PieceEmpty
380 break
381 }
382 return
383 }
384 // p.B[m.To] is necessarily an opponent piece; we check & return
385 // p.B[m.To].Color == color at the beginning of the fn.
386 default: // not a recognized move
387 return
388 }
389
390 row := m.To >> 3
391 if (color == White && row == 7) ||
392 (color == Black && row == 0) {
393 switch m.Promotion {
394 case 0:
395 // m.To is a king? then this is a pseudo-move check.
396 // assume queen in that case.
397 if p.B[m.To].StripColor() != PieceKing {
398 // no promotion given, invalid
399 return
400 }
401 m.Promotion = PieceQueen
402 case PieceQueen, PieceBishop, PieceKnight, PieceRook:
403 default:
404 return
405 }
406 promoted = true
407 p.B[m.From] = m.Promotion | color.Piece()
408 }
409 }
410
411 // reject moves with promotion if there's nothing to promote
412 if m.Promotion != 0 && !promoted {
413 return
414 }
415
416 if p.B[m.To].StripColor() == PieceKing {
417 // King captures don't check for our own king in check;
418 // these are only "theoretical" moves.
419 return Position{}, true
420 }
421
422 // perform board mutation
423 capture := p.B[m.To] != PieceEmpty
424 p.B[m.From], p.B[m.To] = PieceEmpty, p.B[m.From]
425 p.Flags = newFlags
426 p.Moves = append([]Move{}, p.Moves...)
427 p.Moves = append(p.Moves, m)
428
429 // halfmove clock + hashes logic
430 if piece.StripColor() == PiecePawn || capture {
431 // reset both
432 p.HalfMoveClock = 0
433 p.Hashes = nil
434 } else {
435 p.HalfMoveClock++
436 }
437 ep := byte(255)
438 if p.Flags&EnPassant != 0 {
439 ep = byte(p.Flags & MaskEnPassant)
440 }
441 // Not ideal, but avoids GenMoves potentially polluting "real moves" hashes.
442 p.Hashes = append([]uint64{}, p.Hashes...)
443 p.Hashes = append(
444 p.Hashes,
445 // color is inverted, because we consider the present move as already
446 // done (hence, it is the other player to move).
447 zobrist.Hash(toZobristBoard(p.B), bool(!color), byte(p.Flags)>>4, ep),
448 )
449
450 // is our king in check, as a result of the current move?
451 if p.B.InCheck(color) {
452 return
453 }
454 return p, true
455}
456
457func toZobristBoard(src Board) zobrist.Board {
458 var zb zobrist.Board
459 for pos, piece := range src {
460 zb[pos] = zobrist.Piece(piece)
461 }
462 return zb
463}
464
465// used by InCheck to simulate a move by black player.
466var blackPrevMoves = make([]Move, 1)
467
468// InCheck checks whether the king with the given color is in check.
469// If such king does not exist on the board, InCheck returns false.
470//
471// A king is in check if the move from a piece of the other color
472// towards the king is valid, ignoring any checks on the other color's king.
473//
474// NOTE: the last remark is important:
475// https://lichess.org/analysis/4k3/8/4b3/8/8/8/K3R3/8_w_-_-_0_1?color=white
476// -- this is still a check for white, even if _technically_ black couldn't
477// move the bishop (as that would check its own king)
478func (b Board) InCheck(color Color) bool {
479 pWant := PieceKing | color.Piece()
480 kingp := b.findPiece(pWant)
481 if kingp == SquareInvalid {
482 return false
483 }
484
485 pos := Position{B: b}
486 if color == White {
487 // color == White -> simulate a move by black player -> pos.Moves odd
488 pos.Moves = blackPrevMoves
489 }
490
491 for sq, piece := range b {
492 if piece == PieceEmpty || piece.Color() == color {
493 continue
494 }
495 _, ok := pos.validateMove(Move{
496 From: Square(sq),
497 To: kingp,
498 // validateMove (unexp) understands that moves to capture a king are
499 // pseudo moves, so it doesn't check for checking on its own king,
500 // or promotion.
501 })
502 if ok {
503 return true
504 }
505 }
506
507 return false
508}
509
510// Board is a representation of a chess board.
511// Details on how to transform a chess algebraic position into an index
512// can be found at [Square].
513type Board [64]Piece
514
515// NewBoard returns a Board normally set up at the initial position for standard
516// chess.
517func NewBoard() Board {
518 return Board{
519 // row 1
520 p['R'], p['N'], p['B'], p['Q'],
521 p['K'], p['B'], p['N'], p['R'],
522 // row 2
523 p['P'], p['P'], p['P'], p['P'],
524 p['P'], p['P'], p['P'], p['P'],
525
526 // rows 3, 4, 5, 6
527 0, 0, 0, 0, 0, 0, 0, 0,
528 0, 0, 0, 0, 0, 0, 0, 0,
529 0, 0, 0, 0, 0, 0, 0, 0,
530 0, 0, 0, 0, 0, 0, 0, 0,
531
532 // row 7
533 p['p'], p['p'], p['p'], p['p'],
534 p['p'], p['p'], p['p'], p['p'],
535 // row 8
536 p['r'], p['n'], p['b'], p['q'],
537 p['k'], p['b'], p['n'], p['r'],
538 }
539}
540
541func (b Board) findPiece(pWant Piece) Square {
542 for sq, p := range b {
543 if p == pWant {
544 return Square(sq)
545 }
546 }
547 return SquareInvalid
548}
549
550func (p Position) checkCastlingSetup(typ byte) bool {
551 // set up correct row and piece flags according to color
552 c := p.Color()
553 b := p.B
554 var fg Square
555 var pfg Piece
556 if c == Black {
557 fg, pfg = 7<<3, PieceBlack
558 }
559
560 // _cross are the squares that the king starts from,
561 // crosses and "lands". they are recorded as they must all be
562 // not in check by any opponent piece.
563 var _cross [3]Square
564
565 if typ == 'K' {
566 if !(b[fg|4] == pfg|PieceKing &&
567 b[fg|5] == PieceEmpty &&
568 b[fg|6] == PieceEmpty &&
569 b[fg|7] == pfg|PieceRook) {
570 return false
571 }
572 _cross = [3]Square{fg | 4, fg | 5, fg | 6}
573 } else {
574 if !(b[fg|4] == pfg|PieceKing &&
575 b[fg|3] == PieceEmpty &&
576 b[fg|2] == PieceEmpty &&
577 b[fg|1] == PieceEmpty &&
578 b[fg|0] == pfg|PieceRook) {
579 return false
580 }
581 _cross = [3]Square{fg | 4, fg | 3, fg | 2}
582 }
583
584 testb := p.B
585 for _, sq := range _cross {
586 testb[sq] = pfg | PieceKing
587 if testb.InCheck(c) {
588 return false
589 }
590 testb[sq] = PieceEmpty
591 }
592
593 return true
594}
595
596func (b Board) castleRookMove(c Color, typ byte) Board {
597 var fg Square
598 var pfg Piece
599 if c == Black {
600 fg, pfg = 7<<3, PieceBlack
601 }
602
603 if typ == 'K' {
604 b[fg|7], b[fg|5] = PieceEmpty, PieceRook|pfg
605 } else {
606 b[fg|0], b[fg|3] = PieceEmpty, PieceRook|pfg
607 }
608 return b
609}
610
611func (p Position) castlingDisabled(color Color, kind byte) bool {
612 if kind != 'K' && kind != 'Q' {
613 return false
614 }
615
616 // Determine what flag we're looking for.
617 var want PositionFlags
618 switch {
619 case color == White && kind == 'K':
620 want = NoCastleWK
621 case color == White && kind == 'Q':
622 want = NoCastleWQ
623 case color == Black && kind == 'K':
624 want = NoCastleBK
625 case color == Black && kind == 'Q':
626 want = NoCastleBQ
627 }
628
629 return p.Flags&want != 0
630}
631
632func (p Position) checkEnPassant(c Color, sq Square) Square {
633 row, col := sq.Split()
634 if p.Flags&EnPassant == 0 ||
635 (c == White && row != 5) ||
636 (c == Black && row != 2) {
637 return SquareInvalid
638 }
639 wantCol := byte(p.Flags & MaskEnPassant)
640
641 if col != wantCol {
642 return SquareInvalid
643 }
644
645 if c == White {
646 return Square(4<<3 | col)
647 }
648 return Square(3<<3 | col)
649}
650
651// InsufficientMaterial tests for insufficient material on the board, in which
652// case it returns true.
653//
654// See this reference for the rules used:
655// https://www.chess.com/article/view/how-chess-games-can-end-8-ways-explained#insufficient-material
656//
657// - king vs king
658// - king+N/B vs king
659// - king+NN vs king
660// - king+N/B vs king+N/B
661func (bd Board) InsufficientMaterial() bool {
662 // strategy:
663 // store the pieces which could count for an insufficient material
664 // scenario in w, b.
665 // if we encounter any pawn, queen, or rook, material is sufficient.
666 // if we encounter 2 bishops, material is sufficient.
667 // afterwards, we verify that w and b are one of the possible insuf material
668 // scenarios.
669
670 const (
671 imN byte = 1 << iota // knight
672 imN2 // second knight
673 imB // bishop
674 )
675 var w, b byte
676 for _, p := range bd {
677 strip := p.StripColor()
678 switch strip {
679 case PieceQueen, PiecePawn, PieceRook:
680 return false
681 case PieceKing, PieceEmpty:
682 continue
683 }
684 // strip is one of PieceBishop PieceKnight
685 t := &w
686 if p.Color() == Black {
687 t = &b
688 }
689 if strip == PieceBishop {
690 if *t&imB != 0 {
691 return false
692 }
693 *t |= imB
694 } else {
695 if *t&imN2 != 0 {
696 // third knight (ie. from pawn promotion)
697 return false
698 }
699 if *t&imN != 0 {
700 *t |= imN2
701 } else {
702 *t |= imN
703 }
704 }
705 }
706 // make it so that w is bigger than b
707 if b > w {
708 w, b = b, w
709 }
710 switch [2]byte{w, b} {
711 case [2]byte{0, 0}, // king vs king
712 [2]byte{imN, 0}, // king+N/B vs king
713 [2]byte{imB, 0},
714 [2]byte{imN | imN2, 0}, // king+NN vs king
715 [2]byte{imN, imN}, // king+N/B vs king+N/B
716 [2]byte{imB, imB},
717 [2]byte{imB, imN}: // imB > imN, so [2]byte{imN, imB} cannot happen
718 return true
719 }
720 return false
721}
722
723// GenMoves implements a rudimentary move generator.
724// This is not used beyond aiding in determing stalemate and doing perft tests.
725// Each generated move is passed to cb.
726// If cb returns an error, it is returned without processing further moves.
727func (p Position) GenMoves(cb func(Position, Move) error) error {
728 color := p.Color()
729 for sq, piece := range p.B {
730 if piece == PieceEmpty || piece.Color() != color {
731 continue
732 }
733
734 from := Square(sq)
735
736 pstrip := piece.StripColor()
737 // If the piece is a pawn, and they are on the second last row, we know
738 // that whatever move they do (advance, or take diagonally) they're going
739 // to promote.
740 prom := pstrip == PiecePawn &&
741 ((color == White && from>>3 == 6) ||
742 (color == Black && from>>3 == 1))
743
744 // delta generator needs to know if p is black
745 if pstrip == PiecePawn && color == Black {
746 pstrip |= Black.Piece()
747 }
748
749 var err error
750 deltaGenerator(pstrip, func(delta Delta) byte {
751 // create move; if the resulting square is oob, continue
752 m := Move{
753 From: from,
754 To: from.Apply(delta),
755 }
756 if m.To == SquareInvalid ||
757 (p.B[m.To] != PieceEmpty && p.B[m.To].Color() == color) {
758 return deltaGenStopLinear
759 }
760
761 // handle promotion case
762 if prom {
763 m.Promotion = PieceQueen
764 }
765
766 // if it's a valid move, call cb on it
767 newp, ok := p.ValidateMove(m)
768 if !ok {
769 return deltaGenOK
770 }
771 if err = cb(newp, m); err != nil {
772 return deltaGenStop
773 }
774
775 // if we've promoted, handle the cases where we've promoted to a non-queen.
776 if !prom {
777 return deltaGenOK
778 }
779
780 for _, promPiece := range [...]Piece{PieceRook, PieceKnight, PieceBishop} {
781 newp.B[m.To] = promPiece | color.Piece()
782 m.Promotion = promPiece
783 if err = cb(newp, m); err != nil {
784 return deltaGenStop
785 }
786 }
787 return deltaGenOK
788 })
789 if err != nil {
790 return err
791 }
792 }
793 return nil
794}
795
796const (
797 // carry on normally
798 deltaGenOK = iota
799 // if the generator is doing a linear attack (ie. rook, bishop, queen),
800 // then stop that (there is a piece of same colour in the way.)
801 deltaGenStopLinear
802 // abort generation asap.
803 deltaGenStop
804)
805
806/*func init() {
807 for i := PiecePawn; i <= PieceKing; i++ {
808 println("generator ", i.String())
809 deltaGenerator(i, func(d Delta) byte {
810 println(" ", d[0], d[1])
811 return deltaGenOK
812 })
813 }
814}*/
815
816// deltaGenerator generates the possible ways in which p can move.
817// the callback may return one of the three deltaGen* values.
818func deltaGenerator(p Piece, cb func(d Delta) byte) {
819 doLinear := func(d Delta) bool {
820 for i := int8(1); i <= 7; i++ {
821 switch cb(d.Mul(i)) {
822 case deltaGenStopLinear:
823 return false
824 case deltaGenStop:
825 return true
826 }
827 }
828 return false
829 }
830 rotate := func(d Delta, lin bool) bool {
831 for i := 0; i < 4; i++ {
832 if lin {
833 if doLinear(d) {
834 return true
835 }
836 } else {
837 if cb(d) == deltaGenStop {
838 return true
839 }
840 }
841
842 d = d.Rot()
843 }
844 return false
845 }
846
847 // In the following, we use logical OR's to do conditional evaluation
848 // (if the first item returns true, the second won't be evaluated)
849 switch p {
850 case PiecePawn, PiecePawn | PieceBlack:
851 dir := int8(1)
852 if p.Color() == Black {
853 dir = -1
854 }
855 // try moving 1sq forward; if we get StopLinear, don't try to do 2sq.
856 fw := cb(Delta{dir, 0})
857 if fw == deltaGenStop {
858 return
859 }
860 if fw != deltaGenStopLinear {
861 if cb(Delta{dir * 2, 0}) == deltaGenStop {
862 return
863 }
864 }
865
866 _ = cb(Delta{dir, 1}) == deltaGenStop ||
867 cb(Delta{dir, -1}) == deltaGenStop
868
869 case PieceRook:
870 rotate(Delta{0, 1}, true)
871 case PieceBishop:
872 rotate(Delta{1, 1}, true)
873 case PieceKnight:
874 _ = rotate(Delta{1, 2}, false) ||
875 rotate(Delta{2, 1}, false)
876 case PieceQueen:
877 _ = rotate(Delta{0, 1}, true) ||
878 rotate(Delta{1, 1}, true)
879 case PieceKing:
880 _ = rotate(Delta{0, 1}, false) ||
881 rotate(Delta{1, 1}, false) ||
882 cb(Delta{0, 2}) == deltaGenStop ||
883 cb(Delta{0, -2}) == deltaGenStop
884 }
885}
886
887// Outcome is returned by IsFinished, and indicates if the game has finished,
888// and additionally if either of the player can claim draw by the 50-move rule
889// or by 3-fold repetition.
890//
891// Either one of the sequential outcomes will be set (values 1-5), indicating
892// that the game is terminated, or the low 3 bits will be 0, and
893// the Can* flags may be set.
894type Outcome byte
895
896const (
897 NotFinished Outcome = iota
898 Checkmate
899 Stalemate
900 Drawn75Move
901 Drawn5Fold
902
903 Can50Move Outcome = 8
904 Can3Fold Outcome = 16
905 CanInsufficient Outcome = 32
906)
907
908var errFound = errors.New("found")
909
910// IsFinished determines if the game at the given position can be considered
911// "finished".
912// See [Outcome] for the possible results.
913func (p Position) IsFinished() Outcome {
914 err := p.GenMoves(func(Position, Move) error {
915 return errFound
916 })
917 // If there is any legal move, this is not any kind of mate.
918 if err != nil {
919 mhc := p.maxHashCount()
920 switch {
921 case mhc >= 5:
922 return Drawn5Fold
923 case p.HalfMoveClock >= 150:
924 return Drawn75Move
925 }
926 var o Outcome
927 if mhc >= 3 {
928 o |= Can3Fold
929 }
930 if p.HalfMoveClock >= 100 {
931 o |= Can50Move
932 }
933 if p.B.InsufficientMaterial() {
934 o |= CanInsufficient
935 }
936 return o
937 }
938
939 // No legal moves. Is the king in check?
940 if p.B.InCheck(p.Color()) {
941 return Checkmate
942 }
943 return Stalemate
944}
945
946// Color determines a player's color -- either white or black.
947type Color bool
948
949const (
950 White Color = false
951 Black Color = true
952)
953
954// Piece returns the color as a piece to be OR'd into a Piece;
955// ie. 0 on White, and [PieceBlack] on black.
956func (c Color) Piece() Piece {
957 if c == White {
958 return 0
959 }
960 return PieceBlack
961}
962
963// Piece represents a piece on the board.
964type Piece byte
965
966// PieceFromChar returns the piece corresponding to the given character.
967// White pieces are uppercase, and black pieces are lowercase.
968// If a piece is invalid, PieceInvalid is returned.
969func PieceFromChar(b byte) Piece {
970 return p[b]
971}
972
973// piece character to internal piece
974var p = [256]Piece{
975 'P': PiecePawn,
976 'R': PieceRook,
977 'N': PieceKnight,
978 'B': PieceBishop,
979 'Q': PieceQueen,
980 'K': PieceKing,
981
982 'p': PieceBlack | PiecePawn,
983 'r': PieceBlack | PieceRook,
984 'n': PieceBlack | PieceKnight,
985 'b': PieceBlack | PieceBishop,
986 'q': PieceBlack | PieceQueen,
987 'k': PieceBlack | PieceKing,
988}
989
990var pstring = [PieceBlack | PieceKing + 1]byte{
991 PiecePawn: 'P',
992 PieceRook: 'R',
993 PieceKnight: 'N',
994 PieceBishop: 'B',
995 PieceQueen: 'Q',
996 PieceKing: 'K',
997 PieceBlack | PiecePawn: 'p',
998 PieceBlack | PieceRook: 'r',
999 PieceBlack | PieceKnight: 'n',
1000 PieceBlack | PieceBishop: 'b',
1001 PieceBlack | PieceQueen: 'q',
1002 PieceBlack | PieceKing: 'k',
1003}
1004
1005func (p Piece) String() string {
1006 if int(p) >= len(pstring) {
1007 return ""
1008 }
1009 v := pstring[p]
1010 if v == 0 {
1011 return ""
1012 }
1013 return string(v)
1014}
1015
1016// Possible values of Piece. Within the context of Board, Piece is assumed to
1017// be white, unless p&PieceBlack != 0. Note PieceBlack is not a valid piece; it
1018// must be bitwise OR'd to a non-empty piece.
1019const (
1020 PieceEmpty Piece = iota
1021
1022 PiecePawn
1023 PieceRook
1024 PieceKnight
1025 PieceBishop
1026 PieceQueen
1027 PieceKing
1028
1029 PieceBlack Piece = 8 // bit-flag
1030)
1031
1032// Color returns the color of the piece.
1033func (p Piece) Color() Color { return Color(p&PieceBlack != 0) }
1034
1035// Piece returns the given Piece without color information.
1036func (p Piece) StripColor() Piece { return p &^ PieceBlack }
1037
1038// Switch switches the color of the given piece.
1039func (p Piece) Switch() Piece {
1040 if p.Color() == Black {
1041 return p &^ PieceBlack
1042 }
1043 return p | PieceBlack
1044}
1045
1046// Delta represents a 2d vector for indicating a movement from one square
1047// to another. The first value indicates the change in column, the second the
1048// change in rows.
1049type Delta [2]int8
1050
1051// Valid ensures the two values of delta are valid.
1052func (d Delta) Valid() bool {
1053 return d[0] >= -7 && d[0] <= 7 &&
1054 d[1] >= -7 && d[1] <= 7 &&
1055 !(d[0] == 0 && d[1] == 0)
1056}
1057
1058// Rot applies a 90 degree anti-clockwise rotation to d.
1059func (d Delta) Rot() Delta {
1060 // Rationale: this is just matrix-vector multiplication.
1061 // 90 deg rotation is just the matrix {0, -1; 1, 0}.
1062 return Delta{d[1], -d[0]}
1063}
1064
1065// Mul multiplies both values by n, otherwise known as scalar product.
1066func (d Delta) Mul(n int8) Delta {
1067 return Delta{d[0] * n, d[1] * n}
1068}
1069
1070// Square encodes piece position information, in chess the "square" the piece is on.
1071// Indexing 0 as the LSB, bits 0-3 indicate the column and bits 4-6 indicate
1072// the row. For instance, square 44 (decimal) is:
1073//
1074// 44 = 0b00 101 100 = d5
1075// ^row ^col
1076//
1077// (note: in algebraic notation, this is swapped: the letter represents the
1078// column, and the number represents the row).
1079type Square byte
1080
1081// SquareInvalid is returned by some Square-related methods to indicate
1082// invalid parameters.
1083const SquareInvalid Square = 255
1084
1085// String returns p in algebraic notation.
1086func (q Square) String() string {
1087 if q >= 64 {
1088 return "<invalid>"
1089 }
1090 return string(q&7+'a') + string(q>>3+'1')
1091}
1092
1093// SquareFromString returns Square, reading the human-readable algebraic
1094// notation in s. s must be 2 bytes long, with the first byte a letter included
1095// between ['a'; 'h'], and the second a number included between ['1';'8'].
1096// If s is invalid, SquareInvalid is returned.
1097func SquareFromString(s string) Square {
1098 if len(s) != 2 {
1099 return SquareInvalid
1100 }
1101 col, row := s[0]-'a', s[1]-'1'
1102 // because s[0] is a byte, if s[0] < 'a' then the above will underflow and
1103 // row will be >= 8 (same for col).
1104 if row >= 8 || col >= 8 {
1105 return SquareInvalid
1106 }
1107 return Square(row<<3 | col)
1108}
1109
1110// Move changes the square of q, moving it vertically according to dr
1111// (delta row) and horizontally according to dc (delta column).
1112// If the resulting square is not on the board, then SquareInvalid is returned.
1113func (q Square) Move(dr, dc int8) Square {
1114 if q == SquareInvalid || !(Delta{dr, dc}).Valid() {
1115 return SquareInvalid
1116 }
1117
1118 row, col := int8(q>>3), int8(q&7)
1119 row += dr
1120 col += dc
1121
1122 nr, nc := Square(row), Square(col)
1123 if nr >= 8 || nc >= 8 {
1124 return SquareInvalid
1125 }
1126 return nr<<3 | nc
1127}
1128
1129// Apply applies the given delta to the square.
1130// It is shorthand for q.Move(d[0], d[1]).
1131func (q Square) Apply(d Delta) Square { return q.Move(d[0], d[1]) }
1132
1133// Split splits Square into its components.
1134// This function does not check if p is invalid.
1135func (q Square) Split() (row, col byte) {
1136 return byte(q >> 3), byte(q & 7)
1137}
1138
1139// SplitI works like [Square.Split], but returns int8's instead
1140// of bytes.
1141func (q Square) SplitI() (row, col int8) {
1142 return int8(q >> 3), int8(q & 7)
1143}
1144
1145// Sub calculates the difference between the two squares.
1146// q is the originating square, s is the ending square. The difference in
1147// rows and columns from q to s is returned; for instance, d1.Sub(a4) yields
1148// Delta{3, -3}.
1149func (q Square) Sub(s Square) Delta {
1150 fr, fc := q.SplitI()
1151 tr, tc := s.SplitI()
1152 return Delta{tr - fr, tc - fc}
1153}
1154
1155// Move represents a chess game move.
1156type Move struct {
1157 From, To Square
1158 Promotion Piece
1159}
1160
1161// String returns a string representation of Move.
1162// It is in the form of "Long Algebraic Notation".
1163// https://backscattering.de/chess/uci/#move-lan
1164func (m Move) String() string {
1165 p := ""
1166 if m.Promotion != 0 {
1167 p = string(m.Promotion.String()[0] + ('a' - 'A'))
1168 }
1169 return m.From.String() + m.To.String() + p
1170}
1171
1172var (
1173 castleWhiteQ = Move{From: SquareFromString("e1"), To: SquareFromString("c1")}
1174 castleWhiteK = Move{From: SquareFromString("e1"), To: SquareFromString("g1")}
1175 castleBlackQ = Move{From: SquareFromString("e8"), To: SquareFromString("c8")}
1176 castleBlackK = Move{From: SquareFromString("e8"), To: SquareFromString("g8")}
1177)
1178
1179// returns 0, 'K' or 'Q'.
1180func (m Move) isCastle(c Color) (kind byte) {
1181 if c == White {
1182 switch m {
1183 case castleWhiteQ:
1184 return 'Q'
1185 case castleWhiteK:
1186 return 'K'
1187 }
1188 } else {
1189 switch m {
1190 case castleBlackQ:
1191 return 'Q'
1192 case castleBlackK:
1193 return 'K'
1194 }
1195 }
1196 return 0
1197}
