online multiplayer chess game (note server currently down)
Diffstat (limited to 'board/chess.gd')
| -rw-r--r-- | board/chess.gd | 1205 |
1 files changed, 1205 insertions, 0 deletions
diff --git a/board/chess.gd b/board/chess.gd new file mode 100644 index 0000000..77a74bd --- /dev/null +++ b/board/chess.gd @@ -0,0 +1,1205 @@ +extends Node +class_name Chess +# ported from https://github.com/jhlywa/chess.js +const SYMBOLS := "pnbrqkPNBRQK" + +const DEFAULT_POSITION := "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" + +const TERMINATION_MARKERS := ["1-0", "0-1", "1/2-1/2", "*"] + +const PAWN_OFFSETS := { + b = [16, 32, 17, 15], + w = [-16, -32, -17, -15], +} + +const PIECE_OFFSETS := { + n = [-18, -33, -31, -14, 18, 33, 31, 14], + b = [-17, -15, 17, 15], + r = [-16, 1, 16, -1], + q = [-17, -16, -15, 1, 17, 16, 15, -1], + k = [-17, -16, -15, 1, 17, 16, 15, -1], +} + +var ATTACKS: PoolIntArray = [ + 20, 0, 0, 0, 0, 0, 0, 24, 0, 0, 0, 0, 0, 0,20, 0, + 0,20, 0, 0, 0, 0, 0, 24, 0, 0, 0, 0, 0,20, 0, 0, + 0, 0,20, 0, 0, 0, 0, 24, 0, 0, 0, 0,20, 0, 0, 0, + 0, 0, 0,20, 0, 0, 0, 24, 0, 0, 0,20, 0, 0, 0, 0, + 0, 0, 0, 0,20, 0, 0, 24, 0, 0,20, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0,20, 2, 24, 2,20, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 2,53, 56, 53, 2, 0, 0, 0, 0, 0, 0, + 24,24,24,24,24,24,56, 0, 56,24,24,24,24,24,24, 0, + 0, 0, 0, 0, 0, 2,53, 56, 53, 2, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0,20, 2, 24, 2,20, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0,20, 0, 0, 24, 0, 0,20, 0, 0, 0, 0, 0, + 0, 0, 0,20, 0, 0, 0, 24, 0, 0, 0,20, 0, 0, 0, 0, + 0, 0,20, 0, 0, 0, 0, 24, 0, 0, 0, 0,20, 0, 0, 0, + 0,20, 0, 0, 0, 0, 0, 24, 0, 0, 0, 0, 0,20, 0, 0, + 20, 0, 0, 0, 0, 0, 0, 24, 0, 0, 0, 0, 0, 0,20 +] + +var RAYS: PoolIntArray = [ + 17, 0, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 15, 0, + 0, 17, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 15, 0, 0, + 0, 0, 17, 0, 0, 0, 0, 16, 0, 0, 0, 0, 15, 0, 0, 0, + 0, 0, 0, 17, 0, 0, 0, 16, 0, 0, 0, 15, 0, 0, 0, 0, + 0, 0, 0, 0, 17, 0, 0, 16, 0, 0, 15, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 17, 0, 16, 0, 15, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 17, 16, 15, 0, 0, 0, 0, 0, 0, 0, + 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1,-1, -1, -1, -1, 0, + 0, 0, 0, 0, 0, 0,-15,-16,-17, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0,-15, 0,-16, 0,-17, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0,-15, 0, 0,-16, 0, 0,-17, 0, 0, 0, 0, 0, + 0, 0, 0,-15, 0, 0, 0,-16, 0, 0, 0,-17, 0, 0, 0, 0, + 0, 0,-15, 0, 0, 0, 0,-16, 0, 0, 0, 0,-17, 0, 0, 0, + 0,-15, 0, 0, 0, 0, 0,-16, 0, 0, 0, 0, 0,-17, 0, 0, + -15, 0, 0, 0, 0, 0, 0,-16, 0, 0, 0, 0, 0, 0,-17 +] + +const SQUARE_MAP := { + a8 = 0, b8 = 1, c8 = 2, d8 = 3, e8 = 4, f8 = 5, g8 = 6, h8 = 7, + a7 = 16, b7 = 17, c7 = 18, d7 = 19, e7 = 20, f7 = 21, g7 = 22, h7 = 23, + a6 = 32, b6 = 33, c6 = 34, d6 = 35, e6 = 36, f6 = 37, g6 = 38, h6 = 39, + a5 = 48, b5 = 49, c5 = 50, d5 = 51, e5 = 52, f5 = 53, g5 = 54, h5 = 55, + a4 = 64, b4 = 65, c4 = 66, d4 = 67, e4 = 68, f4 = 69, g4 = 70, h4 = 71, + a3 = 80, b3 = 81, c3 = 82, d3 = 83, e3 = 84, f3 = 85, g3 = 86, h3 = 87, + a2 = 96, b2 = 97, c2 = 98, d2 = 99, e2 = 100, f2 = 101, g2 = 102, h2 = 103, + a1 = 112, b1 = 113, c1 = 114, d1 = 115, e1 = 116, f1 = 117, g1 = 118, h1 = 119 +} + +const SHIFTS := {p = 0, n = 1, b = 2, r = 3, q = 4, k = 5} + +const BITS := { + NORMAL = 1, + CAPTURE = 2, + BIG_PAWN = 4, # 2 step pawn + EP_CAPTURE = 8, + PROMOTION = 16, + KSIDE_CASTLE = 32, + QSIDE_CASTLE = 64, +} + +const ROOKS := { + w = [ + {square = SQUARE_MAP.a1, flag = BITS.QSIDE_CASTLE}, + {square = SQUARE_MAP.h1, flag = BITS.KSIDE_CASTLE}, + ], + b = [ + {square = SQUARE_MAP.a8, flag = BITS.QSIDE_CASTLE}, + {square = SQUARE_MAP.h8, flag = BITS.KSIDE_CASTLE}, + ], +} +enum { RANK_8, RANK_7, RANK_6, RANK_5, RANK_4, RANK_3, RANK_2, RANK_1 } +enum { PARSER_STRICT, PARSER_SLOPPY } +const BLACK := "b" +const WHITE := "w" +const EMPTY := -1 +const PAWN := "p" +const KNIGHT := "n" +const BISHOP := "b" +const ROOK := "r" +const QUEEN := "q" +const KING := "k" +const FLAGS := { + NORMAL = "n", + CAPTURE = "c", + BIG_PAWN = "b", + EP_CAPTURE = "e", + PROMOTION = "p", + KSIDE_CASTLE = "k", + QSIDE_CASTLE = "q", +} + + +# parses all of the decorators out of a SAN string +static func stripped_san(move: String) -> String: + var reg := RegEx.new() + reg.compile("(\\+|\\#)?(\\?\\?|\\?|\\?!|!|!!)?$") + return reg.sub(move.replace("=", ""), "") + + +# this func is used to uniquely identify ambiguous moves +func get_disambiguator(move: Dictionary, moves: Array) -> String: + var from: int = move.from + var to: int = move.to + var piece: String = move.piece + + var ambiguities := 0 + var same_rank := 0 + var same_file := 0 + var ambig_piece: String + var ambig_to: int + var ambig_from: int + for i in range(moves.size()): + ambig_from = moves[i].from + ambig_to = moves[i].to + ambig_piece = moves[i].piece + + # if a move of the same piece type ends on the same to square, we'll + # need to add a disambiguator to the algebraic notation + if piece == ambig_piece && from != ambig_from && to == ambig_to: + ambiguities += 1 + + if rank(from) == rank(ambig_from): + same_rank += 1 + + if file(from) == file(ambig_from): + same_file += 1 + + if ambiguities > 0: + # if there exists a similar moving piece on the same rank and file as + # the move in question, use the square as the disambiguator + if same_rank > 0 && same_file > 0: + return algebraic(from) + elif same_file > 0: + # if the moving piece rests on the same file, use the rank symbol as the + # disambiguator + return algebraic(from)[1] + else: + # else use the file symbol + return algebraic(from)[0] + return "" + + +static func infer_piece_type(san: String) -> String: + var piece_type := san[0] + if piece_type >= "a" && piece_type <= "h": + return PAWN + piece_type = piece_type.to_lower() + if piece_type == "o": + return KING + return piece_type + + +### +### utility functions +### +static func rank(i: int) -> int: + return i >> 4 + + +static func file(i: int) -> int: + return i & 15 + + +static func vec2algebraic(pos: Vector2) -> String: + var column := "abcdefgh"[pos.x] + var row := str(round(8 - pos.y)) + return column + row + + +static func algebraic2vec(alg: String) -> Vector2: + return Vector2("abcdefgh".find(alg[0]), 8 - int(alg[1])) + + +static func algebraic(i: int) -> String: + var f := file(i) + var r := rank(i) + return "abcdefgh"[f] + "87654321"[r] + + +static func __swap_color(c: String) -> String: + return BLACK if c == WHITE else WHITE + + +static func offset(pos, offset: Vector2) -> String: + if typeof(pos) == TYPE_STRING: # algbraic + return vec2algebraic(algebraic2vec(pos) + offset) + elif typeof(pos) == TYPE_INT: # board pos + return offset(algebraic(pos), offset) # supreme lazy + return "" + + +# begin main functions + +var board := [] # stores all the pieces +var kings := {w = EMPTY, b = EMPTY} # stores the square of the kings +var turn := WHITE # whose turn is it +var castling := {w = 0, b = 0} # castling abilities +var ep_square := EMPTY # current en passant square; will be `e3` if you make `e4` +var half_moves := 0 # halfmove counter +var fullmoves := 1 # fullmove counter +var __history := [] + + +func _init(fen := DEFAULT_POSITION) -> void: + load_fen(fen) + board.resize(128) + + +# removes everything on the board ( 8/8/8/8/8/8/8/8 w - - 0 1 ) +func clear() -> void: + board.resize(0) + board.resize(128) + kings = {w = EMPTY, b = EMPTY} + turn = WHITE + castling = {w = 0, b = 0} + ep_square = EMPTY + half_moves = 0 + fullmoves = 1 + __history = [] + + +# goes back to the default position +func reset() -> void: + load_fen(DEFAULT_POSITION) + + +# loads a FEN string. see `fen()` +# returns false in the event of a failure to parse the FEN string. +func load_fen(fen): + var parsed: Dictionary = Fen.parse(fen) + if !parsed: + return false + clear() + + for x in range(8): + for y in range(8): + var piece: String = parsed.mat[y][x] + if piece: + put( + {type = piece.to_lower(), color = WHITE if piece < "a" else BLACK}, + vec2algebraic(Vector2(x, y)) + ) + turn = parsed.turn + if "K" in parsed.castling: + castling.w |= BITS.KSIDE_CASTLE + if "Q" in parsed.castling: + castling.w |= BITS.QSIDE_CASTLE + if "k" in parsed.castling: + castling.b |= BITS.KSIDE_CASTLE + if "q" in parsed.castling: + castling.b |= BITS.QSIDE_CASTLE + + ep_square = SQUARE_MAP[parsed.enpassant] if parsed.enpassant != "-" else EMPTY + half_moves = parsed.halfmove + fullmoves = parsed.fullmove + return true + + +# returns the FEN string of the current position +func fen() -> String: + var empty := 0 + var pieces := "" + var i := 0 + while i < SQUARE_MAP.h1: + if board[i] == null: + empty += 1 + else: + if empty > 0: + pieces += str(empty) + empty = 0 + var piece: String = board[i].type + var color: String = board[i].color + pieces += piece.to_upper() if color == WHITE else piece.to_lower() + + if (i + 1) & 0x88: + if empty > 0: + pieces += str(empty) + + if i != SQUARE_MAP.h1: + pieces += "/" + + empty = 0 + i += 8 + i += 1 + + var cflags := "" + if castling[WHITE] & BITS.KSIDE_CASTLE: + cflags += "K" + if castling[WHITE] & BITS.QSIDE_CASTLE: + cflags += "Q" + if castling[BLACK] & BITS.KSIDE_CASTLE: + cflags += "k" + if castling[BLACK] & BITS.QSIDE_CASTLE: + cflags += "q" + cflags = cflags if cflags else "-" + var epflags := "-" if ep_square == EMPTY else algebraic(ep_square) + + return "%s %s %s %s %s %s" % [pieces, turn, cflags, epflags, half_moves, fullmoves] + + +# gets a square from the board +func get(square: String) -> Dictionary: + var piece = board[SQUARE_MAP[square]] + return {type = piece.type, color = piece.color} if piece else {} + + +# PUTs a piece object into the specified square on the board, returns OK on sucess +func put(piece: Dictionary, square: String) -> int: + # check for valid piece object + valid piece + valid square + if ( + !("type" in piece && "color" in piece) + or SYMBOLS.find(piece.type.to_lower()) == -1 + or not square in SQUARE_MAP + ): + return ERR_INVALID_DATA + + var sq: int = SQUARE_MAP[square] + + # only one king + if piece.type == KING && !(kings[piece.color] == EMPTY || kings[piece.color] == sq): + return ERR_ALREADY_EXISTS + + board[sq] = {type = piece.type, color = piece.color} + if piece.type == KING: + kings[piece.color] = sq + + return OK + + +func remove(square) -> Dictionary: + var piece := get(square) + if piece: + board[SQUARE_MAP[square]] = null + if piece && piece.type == KING: + kings[piece.color] = EMPTY + return piece + + +# warning-ignore:shadowed_variable +func __build_move(board: Array, from: int, to: int, flags: int, promotion := ""): + var move := { + color = turn, + from = from, + to = to, + flags = flags, + piece = board[from].type, + } + + if promotion: + move.flags |= BITS.PROMOTION + move.promotion = promotion + + if board[to]: + move.captured = board[to].type + elif flags & BITS.EP_CAPTURE: + move.captured = PAWN + return move + + +# warning-ignore:shadowed_variable +func __add_move(board: Array, moves: Array, from: int, to: int, flags: int) -> void: + # if pawn promotion + if board[from].type == PAWN && (rank(to) == RANK_8 || rank(to) == RANK_1): + var pieces := [QUEEN, ROOK, BISHOP, KNIGHT] + for p in pieces: + moves.append(__build_move(board, from, to, flags, p)) + else: + moves.append(__build_move(board, from, to, flags)) + + +func __generate_moves(options := {}) -> Array: + var moves := [] + var us := turn + var them := __swap_color(us) + var second_rank := {b = RANK_7, w = RANK_2} + + var first_sq: int = SQUARE_MAP.a8 + var last_sq: int = SQUARE_MAP.h1 + var single_square := false + + # legal moves? + var legal: bool = options.legal if "legal" in options else true + var piece_type: String = ( + options.piece.to_lower() + if "piece" in options and typeof(options.piece) == TYPE_STRING + else "-1" + ) + # generating moves for a single square? + if "square" in options: + if options.square in SQUARE_MAP: + last_sq = SQUARE_MAP[options.square] + first_sq = last_sq - 1 + single_square = true + else: + return [] + + var i := first_sq + while i < last_sq: + i += 1 + # are we off the edge of the board + if i & 0x88: + i += 7 + continue + var piece = board[i] + if piece == null || piece.color != us: + continue + + if piece.type == PAWN && (piece_type == "-1" || piece_type == PAWN): + # single square, non capturing + var square = i + PAWN_OFFSETS[us][0] + if square <= SQUARE_MAP.h1 and board[square] == null: + __add_move(board, moves, i, square, BITS.NORMAL) + + # double square + var _square: int = i + PAWN_OFFSETS[us][1] + if second_rank[us] == rank(i) && board[_square] == null: + __add_move(board, moves, i, _square, BITS.BIG_PAWN) + + # pawn captures + for j in range(2, 4): + var _square: int = i + PAWN_OFFSETS[us][j] + if _square & 0x88: + continue + + if board[_square] != null && board[_square].color == them: + __add_move(board, moves, i, _square, BITS.CAPTURE) + elif _square == ep_square: + __add_move(board, moves, i, ep_square, BITS.EP_CAPTURE) + elif piece_type == "-1" || piece_type == piece.type: + for offset in PIECE_OFFSETS[piece.type]: + var square := i + + while true: + square += offset + if square & 0x88: + break + + if board[square] == null: + __add_move(board, moves, i, square, BITS.NORMAL) + else: + if board[square].color == us: + break + __add_move(board, moves, i, square, BITS.CAPTURE) + break + + # break, if knight or king + if piece.type == "n" || piece.type == "k": + break + + # check for castling if: a) we're generating all moves, or b) we're doing + # single square move generation on the king's square + if piece_type == "-1" || piece_type == KING: + if !single_square || last_sq == kings[us]: + # king-side castling + if castling[us] & BITS.KSIDE_CASTLE: + var castling_from: int = kings[us] + var castling_to: int = castling_from + 2 + + if ( + board[castling_from + 1] == null + && board[castling_to] == null + && !__attacked(them, kings[us]) + && !__attacked(them, castling_from + 1) + && !__attacked(them, castling_to) + ): + __add_move(board, moves, kings[us], castling_to, BITS.KSIDE_CASTLE) + + # queen-side castling + if castling[us] & BITS.QSIDE_CASTLE: + var castling_from: int = kings[us] + var castling_to := castling_from - 2 + + if ( + board[castling_from - 1] == null + && board[castling_from - 2] == null + && board[castling_from - 3] == null + && !__attacked(them, kings[us]) + && !__attacked(them, castling_from - 1) + && !__attacked(them, castling_to) + ): + __add_move(board, moves, kings[us], castling_to, BITS.QSIDE_CASTLE) + + # return all pseudo-legal moves (this includes moves that allow the king + # to be captured) + if !legal: + return moves + + # filter out illegal moves + var legal_moves := [] + for move in moves: + __make_move(move) + if !__king_attacked(us): + legal_moves.append(move) + __undo_move() + + return legal_moves + + +# convert a move from 0x88 coordinates to Standard Algebraic Notation +# (SAN) +# +# @param {boolean} sloppy Use the sloppy SAN generator to work around over +# disambiguation bugs in Fritz and Chessbase. See below: +# +# r1bqkbnr/ppp2ppp/2n5/1B1pP3/4P3/8/PPPP2PP/RNBQK1NR b KQkq - 2 4 +# 4. ... Nge7 is overly disambiguated because the knight on c6 is pinned +# 4. ... Ne7 is technically the valid SAN +func __move_to_san(move, moves := __generate_moves({legal = true}), annotations := true) -> String: + var output := "" + + if move.flags & BITS.KSIDE_CASTLE: + output = "O-O" + elif move.flags & BITS.QSIDE_CASTLE: + output = "O-O-O" + else: + if move.piece != PAWN: + var disambiguator := get_disambiguator(move, moves) + output += move.piece.to_upper() + disambiguator + + if move.flags & (BITS.CAPTURE | BITS.EP_CAPTURE): + if move.piece == PAWN: + output += algebraic(move.from)[0] + output += "x" + + output += algebraic(move.to) + + if move.flags & BITS.PROMOTION: + output += "=" + move.promotion.to_upper() + if annotations: + __make_move(move) + if in_check(): + if in_checkmate(): + output += "#" + else: + output += "+" + __undo_move() + return output + + +func __attacked(color: String, square: int): + var i := 0 + + while i < SQUARE_MAP.h1: + i += 1 + # did we run off the end of the board + if i & 0x88: + i += 7 + continue + + # if empty square or wrong color + if board[i] == null || board[i].color != color: + continue + + var piece: Dictionary = board[i] + var difference := i - square + var index := difference + 119 + + if ATTACKS[index] & (1 << SHIFTS[piece.type]): + if piece.type == PAWN: + if difference > 0: + if piece.color == WHITE: + return true + else: + if piece.color == BLACK: + return true + continue + + # if the piece is a knight or a king + if piece.type == "n" || piece.type == "k": + return true + + var offset := RAYS[index] + var j := i + offset + + var blocked := false + while j != square: + if board[j] != null: + blocked = true + break + j += offset + + if !blocked: + return true + return false + + +func __king_attacked(color): + return __attacked(__swap_color(color), kings[color]) + + +func in_check(): + return __king_attacked(turn) + + +func in_checkmate(): + return in_check() && __generate_moves().size() == 0 + + +func in_stalemate(): + return !in_check() && __generate_moves().size() == 0 + + +func insufficient_material(): + var pieces := {b = 0, k = 0, r = 0, q = 0, n = 0, p = 0} + var bishops := [] + var num_pieces := 0 + var sq_color := 0 + var i := 0 + while i < SQUARE_MAP.h1: + i += 1 + + sq_color = (sq_color + 1) % 2 + if i & 0x88: + i += 7 + continue + + var piece = board[i] + if piece: + pieces[piece.type] += 1 + if piece.type == BISHOP: + bishops.append(sq_color) + num_pieces += 1 + # k vs k + if num_pieces == 2: + return true + elif num_pieces == 3 && (pieces[BISHOP] == 1 || pieces[KNIGHT] == 1): + # k vs. kn .... or .... k vs. kb + return true + elif num_pieces == pieces[BISHOP] + 2: + # kb vs. kb where any number of bishops are all on the same color + var sum := 0 + var lent := bishops.size() + for b in bishops: + sum += b + if sum == 0 || sum == lent: # check if on same color + return true + return false + + +func in_threefold_repetition(): + # TODO: while this func is fine for casual use, a better + # implementation would use a Zobrist key (instead of FEN). the + # Zobrist key would be maintained in the __make_move/__undo_move funcs, + # avoiding the costly funcs that we do below. + var moves := [] + var positions := {} + var repetition := false + + while true: + var move: Dictionary = __undo_move() + if !move: + break + moves.append(move) + + while true: + # remove the last two fields in the FEN string, they're not needed + # when checking for draw by rep + if !repetition: + var fen := PoolStringArray(Array(fen().split(" ")).slice(0, 3)).join(" ") + + # has the position occurred three or more times + positions[fen] = positions[fen] + 1 if fen in positions else 1 + if positions[fen] >= 3: + repetition = true + + if !moves.size(): + break + __make_move(moves.pop_back()) + + return repetition + + +func __push(move): + __history.append( + { + move = move, + kings = {b = kings.b, w = kings.w}, + turn = turn, + castling = {b = castling.b, w = castling.w}, + ep_square = ep_square, + half_moves = half_moves, + fullmoves = fullmoves, + } + ) + + +func __make_move(move: Dictionary): + var us := turn + var them := __swap_color(us) + __push(move) + + board[move.to] = board[move.from] + board[move.from] = null + + # if ep capture, remove the captured pawn + if move.flags & BITS.EP_CAPTURE: + if turn == BLACK: + board[move.to - 16] = null + else: + board[move.to + 16] = null + + # if pawn promotion, replace with new piece + if move.flags & BITS.PROMOTION: + board[move.to] = {type = move.promotion, color = us} + + # if we moved the king + if board[move.to].type == KING: + kings[board[move.to].color] = move.to + + # if we castled, move the rook next to the king + if move.flags & BITS.KSIDE_CASTLE: + var castling_to: int = move.to - 1 + var castling_from: int = move.to + 1 + board[castling_to] = board[castling_from] + board[castling_from] = null + elif move.flags & BITS.QSIDE_CASTLE: + var castling_to: int = move.to + 1 + var castling_from: int = move.to - 2 + board[castling_to] = board[castling_from] + board[castling_from] = null + + # turn off castling + castling[us] = 0 + + # turn off castling if we move a rook + if castling[us]: + for rook in ROOKS[us]: + if move.from == rook.square && castling[us] & rook.flag: + castling[us] ^= rook.flag + break + # turn off castling if we capture a rook + if castling[them]: + for rook in ROOKS[them]: + if move.to == rook.square && castling[them] & rook.flag: + castling[them] ^= rook.flag + break + + # if big pawn move, update the en passant square + if move.flags & BITS.BIG_PAWN: + if turn == "b": + ep_square = move.to - 16 + else: + ep_square = move.to + 16 + else: + ep_square = EMPTY + + # reset the 50 move counter if a pawn is moved or a piece is captured + if move.piece == PAWN: + half_moves = 0 + elif move.flags & (BITS.CAPTURE | BITS.EP_CAPTURE): + half_moves = 0 + else: + half_moves += 1 + + if turn == BLACK: + fullmoves += 1 + turn = __swap_color(turn) + + +func __undo_move() -> Dictionary: + var old = __history.pop_back() + if old == null: + return {} + + var move: Dictionary = old.move + kings = old.kings + turn = old.turn + if typeof(old.castling.w) != TYPE_INT || typeof(old.castling.b) != TYPE_INT: + breakpoint + castling = old.castling + ep_square = old.ep_square + half_moves = old.half_moves + fullmoves = old.fullmoves + + var us := turn + var them := __swap_color(turn) + + board[move.from] = board[move.to] + board[move.from].type = move.piece # to undo any promotions + board[move.to] = null + + if move.flags & BITS.CAPTURE: + board[move.to] = {type = move.captured, color = them} + elif move.flags & BITS.EP_CAPTURE: + var index + if us == BLACK: + index = move.to - 16 + else: + index = move.to + 16 + board[index] = {type = PAWN, color = them} + + if move.flags & (BITS.KSIDE_CASTLE | BITS.QSIDE_CASTLE): + var castling_to + var castling_from + if move.flags & BITS.KSIDE_CASTLE: + castling_to = move.to + 1 + castling_from = move.to - 1 + elif move.flags & BITS.QSIDE_CASTLE: + castling_to = move.to - 2 + castling_from = move.to + 1 + + board[castling_to] = board[castling_from] + board[castling_from] = null + + return move + + +# convert a move from Standard Algebraic Notation (SAN) to 0x88 coordinates +func __move_from_san(move, sloppy := false) -> Dictionary: + # strip off any move decorations: e.g Nf3+?! becomes Nf3 + var clean_move := stripped_san(move) + + var overly_disambiguated := false + var piece + var from + var to + var promotion + var matches + + # the move parsers is a 2-step state + for parser in range(2): + if parser == PARSER_SLOPPY: + # only run the sloppy parse if explicitly requested + if !sloppy: + return {} + + # The sloppy parser allows the user to parse non-standard chess + # notations. This parser is opt-in (by specifying the + # '{ sloppy: true }' setting) and is only run after the Standard + # Algebraic Notation (SAN) parser has failed. + # + # When running the sloppy parser, we'll run a regex to grab the piece, + # the to/from square, and an optional promotion piece. This regex will + # parse common non-standard notation like: Pe2-e4, Rc1c4, Qf3xf7, + # f7f8q, b1c3 + # + # NOTE: Some positions and moves may be ambiguous when using the + # sloppy parser. For example, in this position: + # 6k1/8/8/B7/8/8/8/BN4K1 w - - 0 1, the move b1c3 may be interpreted + # as Nc3 or B1c3 (a disambiguated bishop move). In these cases, the + # sloppy parser will default to the most most basic interpretation + # (which is b1c3 parsing to Nc3). + + var move_regex := RegEx.new() + move_regex.compile("([pnbrqkPNBRQK])?([a-h][1-8])x?-?([a-h][1-8])([qrbnQRBN])") + + # The [a-h]?[1-8]? portion of the regex below handles moves that may + # be overly disambiguated (e.g. Nge7 is unnecessary and non-standard + # when there is one legal knight move to e7). In this case, the value + # of 'from' variable will be a rank or file, not a square. + var fallback := RegEx.new() + fallback.compile("([pnbrqkPNBRQK])?([a-h]?[1-8]?)x?-?([a-h][1-8])([qrbnQRBN])?") + + var result := move_regex.search(clean_move) + if result: + matches = result.strings + piece = matches[1] + from = matches[2] + to = matches[3] + promotion = matches[4] + else: + var _result := fallback.search(clean_move) + + if _result: + matches = _result.strings + piece = matches[1] + from = matches[2] + to = matches[3] + promotion = matches[4] + + if from.length() == 1: + overly_disambiguated = true + + var piece_type := infer_piece_type(clean_move) + var moves := __generate_moves( + { + legal = true, + piece = piece if piece else piece_type, + } + ) + for move in moves: + match parser: + PARSER_STRICT: + var m := stripped_san(__move_to_san(move, moves, false)) + if clean_move == m: + return move + continue + PARSER_SLOPPY: + if matches: + # hand-compare move properties with the results from our sloppy regex + if ( + (!piece || piece.to_lower() == move.piece) + && from in SQUARE_MAP + && to in SQUARE_MAP + && SQUARE_MAP[from] == move.from + && SQUARE_MAP[to] == move.to + && (!promotion || promotion.to_lower() == move.promotion) + ): + return move + elif overly_disambiguated: + # SPECIAL CASE: we parsed a move string that may have an + # unneeded rank/file disambiguator (e.g. Nge7). The 'from' + # variable will be validated + var square := algebraic(move.from) + if ( + (!piece || piece.to_lower() == move.piece) + && to in SQUARE_MAP + && SQUARE_MAP[to] == move.to + && (from == square[0] || from == square[1]) + && (!promotion || promotion.to_lower() == move.promotion) + ): + return move + return {} + + +func __make_pretty(ugly_move: Dictionary) -> Dictionary: + var move := ugly_move.duplicate() + move.san = __move_to_san(move, __generate_moves({legal = true})) + move.to = algebraic(move.to) + move.from = algebraic(move.from) + + var flags := "" + + for flag in BITS: + if BITS[flag] & move.flags: + flags += FLAGS[flag] + + move.flags = flags + return move + + +#***************************************************************************** +#* DEBUGGING UTILITIES +#****************************************************************************/ +func perft(depth: int) -> int: + var moves := __generate_moves({legal = false}) + var nodes := 0 + var color := turn + for move in moves: + __make_move(move) + if !__king_attacked(color): + if depth - 1 > 0: + var child_nodes := perft(depth - 1) + nodes += child_nodes + else: + nodes += 1 + __undo_move() + + return nodes + + +#*************************************************************************** +#* PUBLIC API +#*************************************************************************** + + +func in_draw(): + return half_moves >= 50 || in_stalemate() || insufficient_material() || in_threefold_repetition() + + +func game_over(): + return ( + half_moves >= 50 + || in_checkmate() + || in_stalemate() + || insufficient_material() + || in_threefold_repetition() + ) + + +# lists the possible legal moves. +func moves(options := {}): + # The internal representation of a chess move is in 0x88 format, and + # not meant to be human-readable. The code below converts the 0x88 + # square coordinates to algebraic coordinates. It also prunes an + # unnecessary move keys resulting from a verbose call. + + var ugly_moves := __generate_moves(options) + var moves := [] + for ugly_move in ugly_moves: + # does the user want a full move object (most likely not), or just + # SAN + if "verbose" in options && options.verbose: + moves.append(__make_pretty(ugly_move)) + else: + moves.append(__move_to_san(ugly_move, __generate_moves({legal = true}))) + return moves + + +# warning-ignore:function_conflicts_variable +# returns a 2d matrix of the board. +func board(): + var output := [] + var row := [] + var i := 0 + while i < SQUARE_MAP.h1: + i += 1 + if board[i] == null: + row.append(null) + else: + row.append( + { + square = algebraic(i), + type = board[i].type, + color = board[i].color, + } + ) + if (i + 1) & 0x88: + output.append(row) + row = [] + i += 8 + return output + + +func pgn() -> String: + # using the specification from http://www.chessclub.com/help/PGN-spec + # pop all of __history onto reversed_history + var reversed_history := [] + while !__history.empty(): + reversed_history.append(__undo_move()) + var moves: PoolStringArray = [] + var move_string := "" + # build the list of moves. a move_string looks like: "3. e3 e6" + while reversed_history.size() > 0: + var move: Dictionary = reversed_history.pop_back() + + # if the position started with black to move, start PGN with 1. ... + if !__history.size() and move.color == "b": + move_string = "%s ..." % fullmoves + elif move.color == "w": + if move_string.length() > 0: + moves.append(move_string) + move_string = "%s." % fullmoves + + move_string += " %s" % __move_to_san(move, __generate_moves({legal = true})) + __make_move(move) + + # __history should be back to what it was before we started generating PGN, + # so join together moves + return moves.join(" ") + + +func load_pgn(pgn, options := {}) -> int: # FIXME: mildly broken. move generator for a8 cannot get a4, for some reason. + # allow the user to specify the sloppy move parser to work around over + # disambiguation bugs in Fritz and Chessbase + var sloppy: bool = options.sloppy if "sloppy" in options else false + + var parsed: Dictionary = Pgn.parse(pgn) + + # Put the board in the starting position + reset() + + var fen := "" + + for key in parsed.headers: + # check to see user is including fen (possibly with wrong tag case) + if key.to_lower() == "fen": + fen = parsed.headers[key] + + # sloppy parser should attempt to load a fen tag, even if it's + # the wrong case and doesn't include a corresponding [SetUp "1"] tag */ + if sloppy and fen: + if !load_fen(fen): + return ERR_INVALID_DATA + else: + # strict parser - load_fen the starting position indicated by [Setup '1'] + # and [FEN position] + if "SetUp" in parsed.headers and parsed.headers["SetUp"] == "1": + if !("FEN" in parsed.headers && load_fen(parsed.headers["FEN"])): + return ERR_INVALID_DATA + + var moves: Array = parsed.moves + var move := {} + var result := "" + for mov in moves: + move = __move_from_san(mov, sloppy) + if !move: + # was the move an end of game marker + if TERMINATION_MARKERS.find(mov) != -1: + result = mov + else: + return ERR_INVALID_DATA + else: + # reset the end of game marker if making a valid move + result = "" + __make_move(move) + # Per section 8.2.6 of the PGN spec, the Result tag pair must match + # match the termination marker. Only do this when headers are present, + # but the result tag is missing + if result && parsed.headers.size() && !parsed.header["Result"]: + moves.append(result) + return OK + + +# The move func can be called with in the following parameters: +# +# .move('Nxb7') <- where 'move' is a case-sensitive SAN string +# +# .move({ from: 'h7', to :'h8', promotion: 'q'}) <- where the 'move' is a move obj +func move(move, sloppy := false) -> Dictionary: + var move_obj = null + + if typeof(move) == TYPE_STRING: + move_obj = __move_from_san(move, sloppy) + elif typeof(move) == TYPE_DICTIONARY: + var moves := __generate_moves() + + # uglify move + for m in moves: + if ( + move.from == algebraic(m.from) + && move.to == algebraic(m.to) + && (!("promotion" in m) || move.promotion == m.promotion) + ): + move_obj = m + break + + # failed to find move + if !move_obj: + return {} + + # need to make a copy of move because we can't generate SAN after the + # move is made + var pretty_move := __make_pretty(move_obj) + + __make_move(move_obj) + + return pretty_move + + +func undo() -> Dictionary: + var move := __undo_move() + return __make_pretty(move) if move else {} + + +func ascii() -> String: + var s := " +------------------------+\n" + var i := 0 + while i < SQUARE_MAP.h1 + 1: + # display the rank + if file(i) == 0: + s += " " + "87654321"[rank(i)] + " |" + + # empty piece + if board[i] == null: + s += " . " + else: + var piece: String = board[i].type + var color: String = board[i].color + var symbol := piece.to_upper() if color == WHITE else piece.to_lower() + s += " " + symbol + " " + if (i + 1) & 0x88: + s += "|\n" + i += 8 + i += 1 + s += " +------------------------+\n" + s += " a b c d e f g h" + + return s + + +static func square_color(square): + if square in SQUARE_MAP: + var sq_0x88: int = SQUARE_MAP[square] + return "light" if (rank(sq_0x88) + file(sq_0x88)) % 2 == 0 else "dark" + return null + + +func history(verbose := false) -> Array: + var reversed_history := [] + var move_history := [] + + while __history.size() > 0: + reversed_history.append(__undo_move()) + + while reversed_history.size() > 0: + var move: Dictionary = reversed_history.pop_back() + if verbose: + move_history.append(__make_pretty(move)) + else: + move_history.append(__move_to_san(move, __generate_moves({legal = true}))) + __make_move(move) + + return move_history |