Mizar chess engine
Encyclopedia
Mizar is a chess engine developed by Nicola Rizzuti. Mizar is distributed with its source code for the use of programmers who may wish to understand how a chess program works. Mizar uses the Chess Engine Communication Protocol
and can run under the popular chess interfaces XBoard
and Arena.
Each square contains:
Mizar uses two lists of pieces instead to scan the board every time. The list position is sorted by piece value, king position is always in 0. When a piece is captured a flag is set to an appropriate value.
Mizar uses also two bitboard
s (64-bit) to store white and black pieces and two bitboards to store white and black pawns. Bitboards are used to speed up attack detection and in evaluation function.
The enp variable stores the square position at which an en passant
capture is possible. The castle struct stores both a bitset
indicating the castling
right and a bitset to know where the castle move was done.
Each board position also has a hash code associated with it. The hash code is 64 bits and is computed by fetching, for each piece and square combination, a unique 64-bit code from a table of random numbers, and computing the exclusive or (XOR) of these codes (Zobrist hashing
). Castling status, en passant status, and color to move are also folded into the hash code, because positions with the same piece layout but different castling rights or possible en-passant captures or different side to move must be kept distinct. Mizar uses this hash code to detect a threefold repetition
of moves and in transposition table
s.
. The function "gen_all" scans the list of the pieces and calls "gen_piece_moves" that depending on type of piece, walks over the board. Mizar doesn't use 0x88 method to detect edges: thanks to its board representation Mizar knows if the square is empty, occupied or out of board by a simple color control; Mizar iterates until the square isn't empty (storing normal moves)than if the color of the square is "enemy_color" it stores a capture move.
Mizar uses a 32-bit struct to store move information. Each move contains a start square, a destination square, an identifier of the piece to copy in destination square and the type of move. Each move is stored in an array, for the current ply moves are located from first_move[ply] to (first_move[ply+1]-1).
. When Mizar must find a move, it calls "find_best_move". "find_best_move" does some initialization and then calls "search", which implements the alpha-beta search algorithm over a search tree
.
Mizar uses Iterative deeping
: first a one-ply search is done, then a two-ply search, then three, etc. until either the maximum ply limit has been reached or the time control has been exceeded. Before iterative deeping starts Mizar generates all moves at root position; each move is evaluated and then sorted. After every iteration root moves list is sorted again. Mizar uses Aspiration window: after every iteration Mizar starts new search with a window [last_score-value,last_score+value]; if search returns a value outside this window, Mizar research with normal window [-Mate_score,+Mate_score].
Mizar uses "Static Pruning
": at depth 1 and 2, if side to move isn't in check and it isn't in PV, Mizar tries to stop search and to return a score. If material score is < alpha and this score + 'static margin' is even < alpha then return alpha (Futility Pruning, Extend Futility Pruning...). If material score is > beta and static score (Material+positional score) is > beta: if score - 'dynamic margin' > beta then return beta. 'Dinamic margin' is calculated in this way:
if the piece is attacked by a smaller piece, margin = 2/3 of hanging piece;
if the piece is attacked by a greater piece and not defended by pawn, margin = 2/3 of hanging piece;
if the piece is attacked by an equal piece and number of attacker is > of defender margin = 2/3 of hanging piece;
in other cases margin = 0. A hanging passed pawn in 7th is like a hanging queen, but an enemy passed pawn in 7th is very dangerous and margin = queen_value.
Mizar uses Transposition table
: if the current position was searched before, Mizar returns a value instead to search again.
Mizar uses search extension: if king is in check Mizar extend the search depth by one ply.
Every ply Mizar generates all possible moves. Moves are sorted to speed up alpha beta search.
The total move ordering then is as follow:
Mizar makes the move, then Mizar calls the attack info for the board to see if the side to move is in check; If a move into check is found, the next move is tried. If the move passes the legality check, then search is called again. the legality check is done only if the move is a king move, the king is in check, it is an en-passant capture or it is under "x-ray attack".
Mizar uses an alpha-beta's version called negascout
: when a move returns a score > alpha, then the remaining move are searched with a window (alpha,alpha+1), if someone returns score>alpha but < beta, Mizar researches with a window(alpha,beta). At the horizon depth Mizar must return a value for position: it uses a quiescence search
to calculate a stable value for the position. Mizar can use "ponder": Mizar plays the second move in PV and restart search; if opponent plays the same move Mizar has hash-tables full of useful information.
: before starting to evaluate a position, Mizar see if the same position was evaluated previously: if so directly it returns score.
A bonus is given for "rook and bishop vs rook and knight" and "queen and knight vs queen and bishop" and for bishop pair.
and development mistakes.
Chess Engine Communication Protocol
The Chess Engine Communication Protocol is an open communication protocol that enables a chess engine to communicate with its user interface....
and can run under the popular chess interfaces XBoard
XBoard
XBoard and WinBoard are free graphical user interface clients. Originally developed by Tim Mann, these programs are compatible with various chess engines that support the Chess Engine Communication Protocol such as GNU Chess...
and Arena.
Board representation
The chess board in Mizar is represented by an array of 256 squares, laid out so that square a8 has the value 68 and square h1 has the value 187 (you can imagine a 16×16 board where the real board is centered in it).Each square contains:
- a piece identifier (0 no piece, -1 out of board, 1 white pawn, 2 black pawn, 3 knight...)
- the color of piece\square (0 Black, 1 White, 2 Empty, -1 Out)
- the position in the "list position"
Mizar uses two lists of pieces instead to scan the board every time. The list position is sorted by piece value, king position is always in 0. When a piece is captured a flag is set to an appropriate value.
Mizar uses also two bitboard
Bitboard
A bitboard is a data structure commonly used in computer systems that play board games.A bitboard, often used for boardgames such as chess, checkers and othello, is a specialization of the bitset data structure, where each bit represents a game position or state, designed for optimization of speed...
s (64-bit) to store white and black pieces and two bitboards to store white and black pawns. Bitboards are used to speed up attack detection and in evaluation function.
The enp variable stores the square position at which an en passant
En passant
En passant is a move in the board game of chess . It is a special pawn capture which can occur immediately after a player moves a pawn two squares forward from its starting position, and an enemy pawn could have captured it had it moved only one square forward...
capture is possible. The castle struct stores both a bitset
Bit field
A bit field is a common idiom used in computer programming to compactly store multiple logical values as a short series of bits where each of the single bits can be addressed separately. A bit field is most commonly used to represent integral types of known, fixed bit-width. A well-known usage of...
indicating the castling
Castling
Castling is a special move in the game of chess involving the king and either of the original rooks of the same color. It is the only move in chess in which a player moves two pieces at the same time. Castling consists of moving the king two squares towards a rook on the player's first rank, then...
right and a bitset to know where the castle move was done.
Each board position also has a hash code associated with it. The hash code is 64 bits and is computed by fetching, for each piece and square combination, a unique 64-bit code from a table of random numbers, and computing the exclusive or (XOR) of these codes (Zobrist hashing
Zobrist hashing
Zobrist hashing is a hash function construction used in computer programs that play abstract board games, such as chess and Go, to implement transposition tables, a special kind of hash table that is indexed by a board position and used to avoid analyzing the same position more than once...
). Castling status, en passant status, and color to move are also folded into the hash code, because positions with the same piece layout but different castling rights or possible en-passant captures or different side to move must be kept distinct. Mizar uses this hash code to detect a threefold repetition
Threefold repetition
In chess and some other abstract strategy games, the threefold repetition rule states that a player can claim a draw if the same position occurs three times, or will occur after their next move, with the same player to move. The repeated positions need not occur in succession...
of moves and in transposition table
Transposition table
In computer chess and other computer games, transposition tables are used to speed up the search of the game tree. Transposition tables are primarily useful in perfect information games, meaning the entire state of the game is known to all players at all times....
s.
Move Generation
Mizar generates all possible moves at every plyPly (game theory)
In two-player sequential games, a ply refers to one turn taken by one of the players. The word is used to clarify what is meant when one might otherwise say "turn"....
. The function "gen_all" scans the list of the pieces and calls "gen_piece_moves" that depending on type of piece, walks over the board. Mizar doesn't use 0x88 method to detect edges: thanks to its board representation Mizar knows if the square is empty, occupied or out of board by a simple color control; Mizar iterates until the square isn't empty (storing normal moves)than if the color of the square is "enemy_color" it stores a capture move.
Mizar uses a 32-bit struct to store move information. Each move contains a start square, a destination square, an identifier of the piece to copy in destination square and the type of move. Each move is stored in an array, for the current ply moves are located from first_move[ply] to (first_move[ply+1]-1).
Search Techniques
Mizar's search function is based on alpha-beta algorithmAlpha-beta pruning
Alpha-beta pruning is a search algorithm which seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games...
. When Mizar must find a move, it calls "find_best_move". "find_best_move" does some initialization and then calls "search", which implements the alpha-beta search algorithm over a search tree
Game tree
In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that...
.
Mizar uses Iterative deeping
Iterative deepening depth-first search
Iterative deepening depth-first search is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state...
: first a one-ply search is done, then a two-ply search, then three, etc. until either the maximum ply limit has been reached or the time control has been exceeded. Before iterative deeping starts Mizar generates all moves at root position; each move is evaluated and then sorted. After every iteration root moves list is sorted again. Mizar uses Aspiration window: after every iteration Mizar starts new search with a window [last_score-value,last_score+value]; if search returns a value outside this window, Mizar research with normal window [-Mate_score,+Mate_score].
Mizar uses "Static Pruning
Pruning (algorithm)
Pruning is a technique in machine learning that reduces the size of decision trees by removing sections of the tree that provide little power to classify instances...
": at depth 1 and 2, if side to move isn't in check and it isn't in PV, Mizar tries to stop search and to return a score. If material score is < alpha and this score + 'static margin' is even < alpha then return alpha (Futility Pruning, Extend Futility Pruning...). If material score is > beta and static score (Material+positional score) is > beta: if score - 'dynamic margin' > beta then return beta. 'Dinamic margin' is calculated in this way:
if the piece is attacked by a smaller piece, margin = 2/3 of hanging piece;
if the piece is attacked by a greater piece and not defended by pawn, margin = 2/3 of hanging piece;
if the piece is attacked by an equal piece and number of attacker is > of defender margin = 2/3 of hanging piece;
in other cases margin = 0. A hanging passed pawn in 7th is like a hanging queen, but an enemy passed pawn in 7th is very dangerous and margin = queen_value.
Mizar uses Transposition table
Transposition table
In computer chess and other computer games, transposition tables are used to speed up the search of the game tree. Transposition tables are primarily useful in perfect information games, meaning the entire state of the game is known to all players at all times....
: if the current position was searched before, Mizar returns a value instead to search again.
Mizar uses search extension: if king is in check Mizar extend the search depth by one ply.
Every ply Mizar generates all possible moves. Moves are sorted to speed up alpha beta search.
The total move ordering then is as follow:
- PV move of previous iteration or move stored in transposition table;
- Positive capture and promotion(MVA\LVV);
- "Countermove" heuristic;
- Two "killer moves"(Killer HeuristicKiller heuristicIn competitive two-player games, the killer heuristic is a technique for improving the efficiency of alpha-beta pruning, which in turn improves the efficiency of the minimax algorithm. This algorithm has an exponential search time to find the optimal next move, so general methods for speeding it...
); - All remaining legal moves sorted in according their history values(History Heuristic);
Mizar makes the move, then Mizar calls the attack info for the board to see if the side to move is in check; If a move into check is found, the next move is tried. If the move passes the legality check, then search is called again. the legality check is done only if the move is a king move, the king is in check, it is an en-passant capture or it is under "x-ray attack".
Mizar uses an alpha-beta's version called negascout
Negascout
NegaScout or Principal Variation Search is a negamax algorithm that can be faster than alpha-beta pruning. Like alpha-beta pruning, NegaScout is a directional search algorithm for computing the minimax value of a node in a tree...
: when a move returns a score > alpha, then the remaining move are searched with a window (alpha,alpha+1), if someone returns score>alpha but < beta, Mizar researches with a window(alpha,beta). At the horizon depth Mizar must return a value for position: it uses a quiescence search
Quiescence search
Quiescence search is an algorithm typically used to evaluate minimax game trees in game-playing computer programs. It is a remedy for the horizon problem faced by AI engines for various games like chess and Go.-The horizon effect:...
to calculate a stable value for the position. Mizar can use "ponder": Mizar plays the second move in PV and restart search; if opponent plays the same move Mizar has hash-tables full of useful information.
Quiescence Search
Mizar uses quiescence search. During quiescence search only capture moves and promotion to queen are generated.Evaluation features
Mizar uses evaluation cacheCache
In computer engineering, a cache is a component that transparently stores data so that future requests for that data can be served faster. The data that is stored within a cache might be values that have been computed earlier or duplicates of original values that are stored elsewhere...
: before starting to evaluate a position, Mizar see if the same position was evaluated previously: if so directly it returns score.
King Safety
Mizar counts attacks on squares around kings. Each king safety term has a small value like 1 or 2. Mizar adds them all up in linear fashion and use this as an index into a table that is not linear.Material Correlation
Mizar counts number of pieces for each side; each piece has a weight.A bonus is given for "rook and bishop vs rook and knight" and "queen and knight vs queen and bishop" and for bishop pair.
Pawn formation
Positive or negative bonuses are given for:- Doubled and tripled pawnsDoubled pawnsIn chess, doubled pawns are two pawns of the same color residing on the same file. Pawns can become doubled only when one pawn captures onto a file on which another friendly pawn resides. In the diagram, the pawns on the b-file and e-file are doubled...
- Isolated pawnIsolated pawnIn chess, an isolated pawn is a pawn which has no friendly pawn on an adjacent file. An isolated queen's pawn is often called an isolani. Isolated pawns are usually a weakness because they cannot be protected by other pawns...
s - Backward pawnBackward pawnIn chess, a backward pawn is a pawn that is behind the pawns of the same color on the adjacent files and that cannot be advanced without loss of material, usually the backward pawn itself....
s - Protected passed pawnsPassed pawnIn chess, a passed pawn is a pawn with no opposing pawns to prevent it from advancing to the eighth rank, i.e. there are no opposing pawns in front of it on the same file nor on an adjacent file. A passed pawn is sometimes colloquially called a passer...
- Hanging pawns
- Pawn majority on the queenside
- Group of weak square of one color
- OutpostOutpost (chess)An outpost is a square which is protected by a pawn and which cannot be attacked by an opponent's pawn. In the figure to the right, c4 is an outpost, occupied by White's knight...
- Bad pieces (pieces with low mobility)
Heuristic
Mizar uses some bonus to fix some openingChess opening
A chess opening is the group of initial moves of a chess game. Recognized sequences of opening moves are referred to as openings as initiated by White or defenses, as created in reply by Black. There are many dozens of different openings, and hundreds of named variants. The Oxford Companion to...
and development mistakes.
See also
- List of chess engines
- Chess engine
- Computer chessComputer chessComputer chess is computer architecture encompassing hardware and software capable of playing chess autonomously without human guidance. Computer chess acts as solo entertainment , as aids to chess analysis, for computer chess competitions, and as research to provide insights into human...
- World Computer Speed Chess ChampionshipWorld Computer Speed Chess ChampionshipWorld Computer Speed Chess Championship is an annual event where computer chess engines compete against each other at blitz chess time controls. It is held in conjunction with the World Computer Chess Championship...