This project is a simple chess engine implemented in Python, providing a basic framework for playing chess, move generation, and position hashing using Zobrist hashing.
-
Chessboard Representation: The chessboard is represented as a 2D array, and the game state is maintained using a
GameState
class. -
Move Generation: The engine can generate legal moves for each piece on the board, considering special moves like castling and en passant.
-
Zobrist Hashing: Zobrist hashing is implemented for efficient position hashing. It uses a random bitstring for each piece at each square on the board.
-
Undo Move: The engine supports undoing moves, allowing for exploration of different lines of play.
-
Game Visualization Using pygame, the board is visualized including move highlighting
To use the chess engine, you can instantiate a GameState
object and make moves using the make_move
method. You can also generate valid moves for a given position using the get_valid_moves
method.
Example:
from engine.chess_engine import *
from engine.chess_algorithm import *
from visual import *
ChessEngine = GameState()
print(ChessEngine.board)
visualize("stockfish")
Alpha-Beta Pruning is an optimization technique used in decision trees and game trees to reduce the number of nodes evaluated in the search tree. It is commonly applied in two-player games, such as chess, to enhance the efficiency of the minimax algorithm.
In game-playing scenarios, the minimax algorithm is often used to determine the best move for a player by exploring all possible moves up to a certain depth in the game tree. However, the number of possible game states can be prohibitively large, making an exhaustive search impractical.
The minimax algorithm works on the principle of evaluating the game states from the perspective of both players, maximizing the score for the current player and minimizing it for the opponent. This is done recursively, exploring the tree until a terminal state or a specified depth is reached.
Alpha-Beta Pruning enhances the minimax algorithm by introducing two parameters, alpha and beta, to keep track of the best choices found for the maximizing and minimizing players, respectively.
- Alpha: The best value that the maximizing player can currently guarantee at the current level or above.
- Beta: The best value that the minimizing player can currently guarantee at the current level or above.
The pruning occurs when a player discovers a move that is guaranteed to be worse than a previously examined move. If the current move is worse than the best move found so far, it can be safely ignored, and the search can be pruned. This reduces the number of nodes evaluated, significantly improving the efficiency of the search.
# base case
if depth == 0:
return turn_multiplier * score_board(game_state)
# move ordering
valid_moves = order_moves(valid_moves, game_state)
# get hash key
hash_k = chess_hash.zobrist_key(game_state)
# check if transpositional table is empty
if len(transpositional_table) == 0:
tt_entry = None
else:
tt_entry = transpositional_table.get(hash_k)
# check if transpositional table entry is valid
if tt_entry is not None and tt_entry.depth >= depth:
# check transpositional table entry flag
if tt_entry.flag == "exact":
return tt_entry.score
# if flag is alphga, check if score is less than alpha
elif tt_entry.flag == "alpha" and tt_entry.score <= alpha:
return alpha
# if flag is beta, check if score is greater than beta
elif tt_entry.flag == "beta" and tt_entry.score >= beta:
return beta
# initial score
best_score = float("-inf")
# iterate through valid moves
for move in valid_moves:
# make move
game_state.make_move(move)
# get next moves
next_moves = game_state.get_valid_moves()
# recursive call
if best_score == float("-inf"):
score = -find_negascout(game_state, next_moves, depth - 1, -beta, -alpha, -turn_multiplier)
else:
score = -find_negascout(game_state, next_moves, depth - 1, -alpha - 1, -alpha, -turn_multiplier)
# check if score is between alpha and beta
if alpha < score < beta:
# recursive call
score = -find_negascout(game_state, next_moves, depth - 1, -beta, -score, -turn_multiplier)
# if score is greater than best score, update best score
if score > best_score:
best_score = score
# check if depth is 0
if depth == DEPTH:
# update next move
next_move = move
# undo move
game_state.undo_move()
# update alpha
alpha = max(alpha, best_score)
# check if alpha is greater than or equal to beta
if alpha >= beta:
break
# check if best score is less than or equal to alpha
if best_score <= alpha:
flag = "beta"
# check if best score is greater than or equal to beta
elif best_score >= beta:
flag = "alpha"
# otherwise, flag is exact
else:
flag = "exact"
# create transpositional table entry
tt_entry = TranspositionTableEntry(depth, best_score, flag)
# add entry to transpositional table
hash_k = chess_hash.zobrist_key(game_state)
transpositional_table[hash_k] = tt_entry
return best_score
get_fen -> Returns the FEN (Forsyth-Edwards Notation) representation of the current chess position.
make_move -> Makes a move on the chess board and updates the game state accordingly.
undo_move -> Undoes the last move made on the chess board and restores the previous game state.
get_valid_moves -> Returns a list of all valid moves for the current player in the current game state.
square_under_attack -> Checks if a given square on the chess board is under attack by any opponent piece.
check_for_pins_and_checks -> Checks for pinned pieces and checks on the current chess board.
get_all_possible_moves -> Returns a list of all possible moves for the current player in the current game state.
get_pawn_moves -> Generates all possible moves for a pawn piece on the chess board.
get_rook_moves -> Generates all possible moves for a rook piece on the chess board.
get_bishop_moves -> Generates all possible moves for a bishop piece on the chess board.
get_knight_moves -> Generates all possible moves for a knight piece on the chess board.
get_queen_moves -> Generates all possible moves for a queen piece on the chess board.
get_king_moves -> Generates all possible moves for a king piece on the chess board.
get_castle_moves -> Generates all possible castle moves for the king on the chess board.
get_king_side_castle_moves -> Generates all possible king side castle moves for the king on the chess board.
get_queen_side_castle_moves -> Generates all possible queen side castle moves for the king on the chess board.