- Mizar chess engine
-
Mizar Developer(s) Nicola Rizzuti Stable release 3.0 / May 16, 2006 Written in C Operating system Windows Type Chess engine Website Mizar web site 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.
Contents
Technical details of Mizar 3.0
Mizar is written in C.
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 bitboards (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 tables.
Move Generation
Mizar generates all possible moves at every ply. 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 algorithm. 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:
- PV move of previous iteration or move stored in transposition table;
- Positive capture and promotion(MVA\LVV);
- "Countermove" heuristic;
- Two "killer moves"(Killer Heuristic);
- 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: 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.
Quiescence Search
Mizar uses quiescence search. During quiescence search only capture moves and promotion to queen are generated.
Evaluation features
Mizar uses evaluation cache: 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 pawns
- Isolated pawns
- Backward pawns
- Protected passed pawns
- Hanging pawns
- Pawn majority on the queenside
- Group of weak square of one color
- Outpost
- Bad pieces (pieces with low mobility)
Heuristic
Mizar uses some bonus to fix some opening and development mistakes.
See also
- List of chess engines
- Chess engine
- Computer chess
- World Computer Speed Chess Championship
External links
Categories:- 2006 software
- Chess engines
Wikimedia Foundation. 2010.
