================================================================================
MIZAR 2.0
================================================================================

Mizar is a freeware chess engine for Winboard.
Copyright (c) 2006 Nicola Rizzuti - ITALY

This product uses parts of the iMatix SFL,
Copyright  1991-2000 iMatix Corporation <http://www.imatix.com>

Corrected and improved by Dann Corbit


Content of this file:
	1 License
	2 Release Notes
	3 Inside Mizar
	4 Test, improvements and bugs
	5 History
	6 Thanks to
	7 Contact


1 License
================================================================================

1.1 Disclaimer
--------------
Mizar is a freeware software; it is copyrighted but under terms
that allow free distribution; it is distributed in the hope that it will
be useful, but WITHOUT ANY WARRANTY; without even the implied warranty
of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

THE AUTHOR OF THIS SOFTWARE DISCLAIMS ALL WARRANTIES OF ANY KIND.
IN NO EVENT SHALL THE AUTHOR OF THIS SOFTWARE BE LIABLE FOR ANY DAMAGES
WHATSOEVER INCLUDING DIRECT, INDIRECT, INCIDENTAL, CONSEQUENTIAL LOSS
OF BUSINESS PROFITS OR SPECIAL DAMAGES, EVEN IF THE AUTHOR OF THIS
SOFTWARE HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.


1.2 Licensing
-------------
Mizar is distribuited with its source code for the use of programmers
who may wish to understand how a chess program works.

You CAN'T compile it and distribuite it as a software of yours, even if
you have make changes in source code.

You CAN'T use it to enter any computer chess competition where other
program authors are invited to participate.

You CAN use it to do your own local tournament.

You CAN use it for research pourpose: new search algorithms, new move
ordering schemes,new pruning schemes...In this case you MUST distribuited
Mizar with: modified source code, an intact copy of this file, a text file
where you explain yours improvements


2 Release Notes
================================================================================

Second release:
[Bug Fixed]
George Lyapko found a setboard bug: added winboard's "setboard" command
Slodoban R. Stojanovic found an "insane" memory consume: countermove table was too big! 

[Improvement]
- Dann Corbit adds evaluation cache
- Transposition Table in search
- add winboard's "setboard" command
- now list of pieces is sorted;
- moves at root are generated only once; then sorted.
- minor changes in xboard()
- changed comment style from '//...' to '/*...*/'


3 Inside Mizar
================================================================================

Mizar is written in C under Windows XP with 
Microsoft Visual C++ 2005 Express Edition

3.1 Board representation
------------------------

The chess board in Mizar is represented by an array of 256 squares,
layed 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...)
- the color of piece (0 Black, 1 White, 2 Empty, -1 Out)
- the position in the "list position"

Mizar uses two list of pieces instead to scan the board
everytime. 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 number":
see Bruce Moreland web site for more information). Castling status,en passant
status, 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 3-fold repetition of moves.


3.2 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 stuct 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).


3.3 Search Techniques
---------------------

Mizar's search function is based on "alpha-beta" alghorithm.
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 "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:
1 PV move of previus iteration or move stored in transposition table;
2 Positive capture and promotion(MVA\LVV);
3 "Countermove" heuristic;
4 Two "killer moves"("Killer Heuristic");
5 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 or it is under
"x-ray attack".
At the horizon depth Mizar must return a value for position: it uses a quiescent search
to calculate a stable value for the position. 


3.3.1 Quiescent Search

Mizar uses quiescence search. During quiescence search only capture moves and
promotion to queen are generated.

3.4 Evaluation features
-----------------------

Mizar uses evaluation cache (thanks to Dann Corbit): before to start to evaluate a
position, Mizar see if the same position was evaluated previously: if so directly it returns score.

3.4.1 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.(See REBEL web site http://members.home.nl/matador/chess.htm)


3.4.2 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.


3.4.3 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)
	

3.4.4 Heuristic

It is my opinion that only static factors are usefull in drawing up the static
balance. Search covers dynamic factors. But now my search function isn't able to
do that. So Mizar uses some bonus to fix some opening and development mistakes.


4 Test, improvements and bugs
================================================================================

Writing a chess engine is hard. If you want help me you are welcome!
You could help me in these ways:
	-Compiling Mizar with a better compiler
	-Porting Mizar to another OS
	-Adding UCI support
	-Tuning evaluation function
	-Finding and fixing bugs
	-Writing Mizar's functions in faster way
	-...
contact me!

5 History
================================================================================

2.0: 20/04/2006 "Memories"
1.0: 09/04/2006 "Death & Rebirth"


6 Thanks to
================================================================================

All people of g6 group (www.gsei.org)
I'll do nothing without them!!
Grazie ragazzi!

Dann Corbit for evaluation cache code, codes fixing and suggestions.

George Lyapko, Slodoban R. Stojanovic for reporting bugs.
 
I have studied the following source code for realize my program:
    -Amy by Thorsten Greiner
    -Arasan by Jon Dart
    -Beowulf by Colin Frayn and Dann Corbit
    -Crafty by Robert Hyatt
    -Galahad by James Swafford
    -Phalanx by Dusan Dobes
    -TSCP by Tom Kerrigan


7 Contact
================================================================================
 
 web site: http://digilander.libero.it/mizarchessengine
 email: mizarchessengine@libero.it


Have a good time!
Nicola Rizzuti