King of Kings 2.56
Copyright (C) 2000 Koundinya Veluri



--------- CONTENTS ---------
----------------------------

- Package
- Usage
- Creating books for King of Kings
- Anotating an EPD file as text (autotesting)
- About the program
- Distribution/copyright
- References/links
- Thanks to
- Version history



--------- PACKAGE ---------
---------------------------

kk.exe             - GUI executable
kke.exe            - Console executable for use as a WinBoard engine
Unregister.exe     - This program removes the registry entries of King of
                     Kings.
kk.ini             - Configuration file
tables.dmp         - Binary file that holds some large tables
24 .bmp files      - Piece pictures for use in the GUI version
Readme.txt         - This file



--------- USAGE ---------
-------------------------

- Modify kk.ini to your likes. See this file for available settings.
- If you downloaded an opening book from the web site, make sure that
  the bkfile option in the ini file is set to the name of the book
  that you downloaded.

GUI     - run the exe...

Console - run the Winboard Startup Dialog and choose "Play against a
          chess engine or match two engines"
        - enter the exe's full path into:
            - the first box if you wish to play against the engine, or
              if you want the engine to be white in a two-engine matchup
            - the second box if you want the engine to play black in a
              two-engine matchup



--------- CREATING BOOKS FOR KING OF KINGS ---------
----------------------------------------------------

Book files are binary files so a book-creating utility is included in
the console version of the program to make books from PGN files.
Actually the code to create books exists in both versions but there is
no interface for doing this yet from the GUI version. Books can be
created from the console version using the makebook command.

Syntax 1 (used for making books from PGN files):
makebook pgn "PGN file" "BK file" <mb> <m> <f>

pgn - specifies that the input file is PGN.
mb  - the amount of RAM to use for creating books.
m   - the maximum number of half-moves (plies) to scan from each game
      in the PGN file.
f   - the minimum number of times a position or a move at a position
      must be repeated for it to be written to the BK file.

All fields are required. The quotation marks are required.

Example: To make a book from "Games of 2000.pgn", you could type
makebook pgn "Games of last year.pgn" "kk.bk" 8 60 2

When making books from PGN files, you will need a lot of free space,
approximately as much as 2.5 times the size of the PGN file. The book
file is usually much smaller than the PGN file.

The book creation process is quite slow from PGN files, and you may
want to try more than one f value to see the difference in size of the
output file. To allow this without having to spend too much time, when
a book is created from a PGN file, a file called "sorted <m>.bin" is
also generated. Creating subsequent books from this BIN file is a much
faster process.

Syntax 2 (used for making books from BIN files):
makebook bin "BIN file" "BK file" <f>

bin - specifies that the input file is BIN
f   - same as above

All fields are required. The quotation marks are required.

Example: To make a book from "sorted.bin", you could type
makebook bin "sorted 60.bin" "kk.bk" 2

The m value can be set only by creating a book from a PGN file. All
books created from "sorted <m>.bin" will use the same m value that was
used to create the "sorted <m>.bin" file.

When parsing the PGN file, the utility will ignore anything it doesn't
understand. NAGs are ignored. Anything enclosed in (), [], or {} are
skipped; it will even handle nested comments, under one condition. Each
opening bracket ('(', '[', or '{') must have a space before it, and
each closing bracket (')', ']', or '}') must have a space after it. If
this condition is not satisfied, the program will probably skip the
rest of the PGN file thinking that it is all a comment. But this only
happens with nested comments. If you notice any more problems, please
notify me so I can fix them!



--------- ANNOTATING AN EPD FILE AS TEXT (AUTOTESTING) ---------
----------------------------------------------------------------

To annotate an epd file, use the annotate command:

annotate epd "EPD file" "Output file" [<oop> <oop> ...]

epd - specifies that the input file is EPD.
oop - override operation; just an EPD operation. See below.

All fields are required. The quotation marks are required.

Each EPD position contains an FEN position _without_ the half-move
clock or the full-move number. Then follow a number of operations. An
operation consists of an opcode and zero or more operands specific to
the operation, and is terminated with a semicolon (;). The <oop>
parameters are EPD operations that override the ones that exist in the
EPD file. For example, you could use the "acs" operation to specify a
time limit for each position like this:

annotate epd "WAC.epd" "WAC.txt" acs 5;

This command annotates WAC.epd into WAC.txt, analyzing for 5 seconds per
position. If some positions in the EPD file had their own "acs"
operation, those positions will still be analyzed for 5 seconds because
the operations specified in the command override equivalent operations
in the EPD file.

The "acn" operation provides a way to stop the analysis when the program
spots the correct solution. "acn" specifies the minimum number of nodes
King of Kings should search before stopping the search. For example:

annotate epd "WAC.epd" "WAC.txt" acn 100000; acs 5;

This is the command I usually use. Basically, this is what happens: The
program starts analyzing a position. If a correct solution is found, it
stops the search, but only after 1000 nodes have been searched. If the
program changes its mind about the solution and picks another wrong
solution before 100000 nodes, the analysis continues, to a maximum of 5
seconds. This, in my opinion, is a very useful feature because it lets
the program autotest a tactical test suite (such as WAC) in very little
time. WAC has 300 positions and at 5 seconds each, would take 1500
seconds or 25 minutes. Using "acn" with a decent node count, it takes
just 3 minutes to complete!

DEFINING A SOLUTION

King of Kings supports several EPD operations that define a solution.

am - avoid move. Examples: am Qg6; am Na1 Na3;
bm - best move.  Examples: bm Qh1#; bm Ra7+ Re7+ Qe8;
ce - centipawn evaluation. Examples: ce 500; ce -32761;
   - see below for info on how to use this.
dm - direct mate full-move count. Examples: dm 12; dm 3;

For detailed info on specifying checkmate scores using "ce", I refer you
to the PGN standard document available on the internet. For mate
problems, it is easier to use the "dm" operation. For example, if you
wanted to specify that the program must see a mate in 10 to call the
position "solved", use "dm 10;". The disadvantage of "dm" is that it
allows you to set only positive mate scores.

When using "ce", the program has no way of knowing whether you mean that
the score should be greater than or less than the score given. So for
the moment, the program assumes positive scores to be lower bounds and
negative scores to be upper bounds. For example, "ce 500;" would tell
the program to consider the position solved if it gets a score >= 5.00.
"ce -200;" would tell it to consider the position solved if it gets a
score <= -2.00. There is currently no way of setting a positive score as
an upper bound or a negative score as a lower bound.

If several of the above operations are combined, King of Kings considers
the position "solved" only if _all_ of the them are satisfied. If none
of the above operations are specified (i.e., the solution is
unspecified), then the position is considered solved.

Specified                Analysis time
------------------------------------------------------------------------
solution, acs, acn       acs seconds; after acn nodes, stop when solved
solution, acs            acs seconds
solution, acn            forever; after acn nodes, stop when solved
acs                      acs seconds
acn                      forever
<nothing>                1 minute (default is "acs 60;")

For any questions that I did not address here, please e-mail me.
Hopefully you will have as much fun as I did with this autotester :)



--------- ABOUT THE PROGRAM ---------
-------------------------------------

King of Kings was programmed in C++. The GUI version uses MFC. The
executables in this package were compiled with Visual Studio .NET 2003.
They are both 32-bit, and will run only on a Windows operating system.

Web site: http://www.kingofkingschess.com/kingofkings/



--------- DISTRIBUTION/COPYRIGHT ---------
------------------------------------------

Everything in the package (including the bitmaps) is copyright (C)
Koundinya Veluri. Code used to link King of Kings with Nalimov endgame
tablebases is copyright (C) Eugene Nalimov. Some code used to decompress
these tables is copyright (C) Andrew Kadatch. You may distribute an
unmodified copy of the original package freely without charge. According
to copyright law, modification of any components of this package without
my written authorization, is prohibited. You may not enter this program
into any tournament or other event without my (the author's) explicit
permission. Any commercial use of this program is prohibited.



--------- REFERENCES/LINKS ---------
------------------------------------

-   Tom Kerrigan's Simple Chess Program (TSCP)
    http://ucsu.colorado.edu/~kerrigat/
-   Bruce Moreland's Chess and Related Topics
    http://www.seanet.com/~brucemo/toc.htm
-   Robert Hyatt's Crafty
    ftp://ftp.cis.uab.edu/pub/hyatt/
-   Paul Verhelst's Computer Chess Programming web site
    http://www.xs4all.nl/~verhelst/chess/programming.html
-   Strategy and board game programming (lecture notes by David Eppstein)
    http://www.ics.uci.edu/~eppstein/180a/w99.html
-   Tim Mann's Chess Pages (home of WinBoard and XBoard)
    http://www.tim-mann.org/chess.html



--------- THANKS TO ---------
-----------------------------

-   Tim Mann [do I have to explain? ok...] for making WinBoard.
    Without it, I don't know where I would be today :)
-   Tom Kerrigan for the surprisingly simple yet fast and strong TSCP.
-   Bruce Moreland for his excellent web pages on chess programming.
-   Eugene Nalimov for making the tablebases.
-   Andrew Kadatch for permission to use his TB decompression code.
-   All regulars on the WinBoard & CCC Forums for answering my
    questions and running the tournaments.
-   Günther Simon for pointing out a problem when using 6-piece TB's.
-   Peter Berger for giving me his suggestions on how to improve my
    opening book.
-   Dann Corbit for providing a clean pgn file, which I used to create
    my opening books.
-   Leo Dijksman for his very motivating tournaments.
-   Andrew on the WinBoard Forum for giving me information that helped
    me solve a difficult bug.



--------- VERSION HISTORY ---------
-----------------------------------

2.56

-   Fixed a rare synchronization bug.
-   Improved hash table usage.
-   Modified some eval parameters.

2.53

-   Fixed the code that picks a move randomly from an opening book. It is
    now playing a better variety of openings.

2.52

-   Fixed an eval bug and modified some eval terms related to the bug.
-   Fixed an egtb bug that caused the program to occasionally not win in won
    tb positions, or to lose in drawn tb positions, when pondering was on.

2.50

-   Slightly improved king safety and piece type balance.
-   Removed aspiration search and improved time management.
-   Reduces null move by 3 plies instead of 2.

2.40

-   Improved king safety, tweaked some evaluation parameters, and fixed a
    bishop mobility bug. Improved piece type balance. Though it now
    usually avoids exchanging two minor pieces for a rook and a pawn, it
    also started occasionally exchanging a rook for a minor piece and a
    pawn.
-   Slightly modified time management. In moves/time time control, it now
    saves some time for the last move in case of a fail-low. Removed some
    time management code that was conflicting with extending time on a
    fail-low.
-   Compiled with Visual Studio .NET 2003 so it's a bit faster.

2.30

-   Fixed a bug in the GUI that caused it to crash in certain scenarios.
-   Added first move extension.

2.20

-   Added evaluation scaling by value of material.
-   Removed lazy evaluation.
-   Added a GUI feature to show the last move played.
-   The GUI now stores settings in the registry. Settings from the INI
    file supercede registry settings.
-   Unregister is included. This program removes the registry entries of
    King of Kings.

2.15

-   Fixed a synchronization bug when analyzing EPD suites with the acn
    operation specified.

2.14

-   The program now uses more time when it thinks that it has found a
    better move.

2.13

-   Randomization now works again.
-   Fixed another evaluation bug related to king safety.

2.12

-   When a research at the root fails low, the program now switches back
    to the previous PV. This should stop it from making a bad move when
    there is an instability in the search.
-   Fixed some minor evaluation bugs related to king safety.

2.11

-   Fixed a search bug that could occasionally cause the program to play
    a worse move than it really indends to play.

2.10

-   Increased time usage.
-   Added a search reduction that seems to be helping with tactics most
    of the time.

2.03

-   Slightly better search extensions.
-   Slightly improved move ordering.
-   Book building is now much faster since it does the sorting in RAM.
-   A hashtable bug was fixed. The hashtable space will now be used more
    efficiently. Also, opening books created with this version may be
    slightly better, while still being compatible with 2.02.
-   Improved time management.

2.02

-   Improved the null move algorithm to detect more zugzwang cases.
-   Slightly modified the time control to use less time when a ponder
    hit occurs.
-   Rewrote all functions that detect draws. Draw by insufficient
    material is claimed only in KK, KNK, and KBK cases but many other
    draws are recognized more accurately than before.
-   Rewrote the hashing algorithms for more speed. Because of this, old
    opening books will not work with this version. Also now the pawn
    table gets a much higher hit rate and this resulted in a decent
    speedup of 30-40%.
-   Added a second transposition table. Scores related to pawn and kings
    are no longer stored in the pawn table. They are stored in a
    separate pawn-king hash table. This allowed me to halve the size of
    pawn table entries (32 bytes each) and use smaller pawn-king table
    entries (16 bytes each) so memory is used more efficiently and both
    tables get relatively more hits.
-   Better move ordering and many small changes to the search. Fewer
    EGTB hits.
-   Fixed a couple of pawn evaluation bugs and tuned some parameters,
    but not much change to the evaluation since 2.00.
-   Fixed many bugs not worth mentioning.

2.00

-   Greatly improved the aspiration search implementation. Sometimes I
    think the implementation in 1.99 is worse than not using it at all.
-   Added futility pruning, extended futility pruning, and limited
    razoring, thanks to Ernst Heinz and his web site.
-   Improved move ordering for the middlegame.
-   Specialized code for handling king-pawn endgames allows it to play
    significantly better at endgames with pawns and few or zero pieces.
    The new code includes handling of unstoppable pawns, pawn races,
    and the special case where one or both sides could queen with check.
    In the endgame, most often the evaluation function will detect a
    promotion long before the search sees it (sort of like radar ;).
-   Added analysis mode into the GUI and console versions. The GUI now
    also has a human-human mode (a.k.a. force mode).
-   Added EPD test suite autotesting. It supports several EPD operations
    to define a solution (see the section in the readme file).
-   Improved opening book generation by making the program scan only the
    side that won if the game's result is 1-0 or 0-1.
-   Added backward compatibility for WinBoard protocol 1 to the console
    version, to allow it to work under other GUI's as well.

1.99

-   Fixed a bug that allowed it to crash on a draw by repetition.
-   Tuned some evaluation parameters. Added a little more king safety
    knowledge, although king safety is still very inaccurate. Completely
    rewrote weak pawn evaluation for more precice play.
-   Cleaned up a lot of code and refined search routines.
-   Better move ordering for all levels of the tree.
-   Improved time management. Sometimes in 1.98, it makes one or two
    very quick moves and finds itself losing afterwards. Hopefully this
    won't happen in 1.99, except for legitimate cases.
-   It now uses aspiration search at the root of the tree.
-   Fixed some problems with scanning PGN files when creating books.

1.98

-   Fixed synchronization and en passant square bugs that could allow
    the engine to, but rarely, make an illegal and/or absurd move.
-   Due to the en passant square hashing bug mentioned above, I had to
    modify the hashing algorithm. This means that old opening books
    won't work with 1.98. Either replace your opening book with the one
    in the ZIP file, or create a book from a PGN file.
-   Completely rewrote the updates system to allow much faster response
    from the program. In the previous system, the program would only
    respond in intervals of 100 ms, but in lightning games this was
    too long for a reply move and it would often lose on time. This
    should never happen again.
-   Introduced fractional depth increments and completely rewrote and
    retuned all search extensions. Due to this, 1.98 performs
    significantly better than 1.97 on most tactics.
-   Implemented the trick to try the move from the transposition table
    before generating moves --> small speed improvement.
-   Better time management with pondering. Pondering now checks the
    transposition table to get an expected move.

1.97

-   Tuned many evaluation parameters involving kings and minor pieces.
-   Added knowledge of passed pawns and the pressure they exert.
-   Slightly better time management; uses more time at the beginning
    of the game and very little when it's about to lose on time.
-   Slightly faster at tactics in most of the positions I tested.

1.96

-   King of Kings now also plays on the Internet Chess Club (ICC) under
    the login KingKings.
-   Has an opening book and comes with a book-creating utility.
-   Supports Nalimov endgame tablebases, created by Eugene Nalimov.
-   Better time usage with pondering.
-   Better knowledge of king safety.
-   Fixed bugs in detection of draws by insufficient material.
-   Improved pruning for slightly faster detection of tactics.
-   Slightly stronger than 1.95.

1.95

-   King of Kings now plays on the Free Internet Chess Server (FICS)
    under the login KingKings (my login is kount). King of Kings only
    recently joined FICS but at the time of this writing, its ratings
    are: lightning (2274), blitz (2169), standard (2096).
-   Many bugs fixed (evaluation, GUI stalling, console output, etc.).
-   Added a LOT more knowledge (king safety, minor piece mobility,
    space control, etc.).
-   Added razoring and forward pruning. This and the evaluation put
    together tremendously slowed down the search but I think it's
    worth it; it's reaching greater depths than before.
-   King of Kings can now ponder on its opponent's time. This greatly
    helped on FICS.
-   It now recognizes draws by insufficient material. This greatly
    improved its endgame play.
-   Defeats version 1.93 or 1.94 most of the time. Occasionally defeats
    and often draws against Arasan (which was the second chess program
    I had ever seen and I was fascinated by its strength) in blitz
    matches, although Arasan is still much stronger than King of Kings
    (big difference when it comes to test positions).

1.94

-   Some evaluation bugs fixed
-   Some speed improvements
-   A little more knowledge, mostly on pawn structure and king safety
-   Several changes in the search including a faster quiescence search
    and selective extensions
-   Introduced a configuration file from which settings are loaded by
    both the GUI and console version of the program

1.93

-   Evaluation redesigned
-   Much more knowledge (especially about pawn structure and king safety)

1.92

-   All known bugs fixed
-   Supports the WinBoard "setboard" command

1.91

-   There are many known bugs
-   Uses WinBoard protocol version 2