Chess-Related Programs

The History of my Chess Programs

• ChessR
  • The first chess program I wrote. Unfortunately, I lost the entire source code due to a split second power cut while compiling. Backup!!!
• Chess
  • The second chess program: Since I lost the source for the first one and I had a project to complete for my Java course, I decided to rewrite it. This is the base program I used to make King of Kings and Ultimate Chess.
• Ultimate Chess 2000
  • I created an interface in C++ and ported the whole thing to a Java applet for my course.
• King of Kings
  • 1.0
    • After rewriting much of the code in the interfaced C++ program and solving literally thousands of problems, I ended up with this, my first chess program that plays somewhat decently, although it still gets whooped when compared to others. Since King of Kings 1.0 is my first chess program, the source is VERY messy. My design was very bad and every time I did some research on something new I could add, it just made my code so much more complicated because that feature was difficult to incorporate into my design. One of things I did wrong was to evaluate moves instead of positions. Although this generally gives an extra ply of searching in the same amount of time (because one evaluation considers two plies), the evaluation function gets very complicated and slow. Another problem was that I didn't know about quiescence searching (even though implementing it with my evaluation function would have been difficult). So I created my own solution to extend the search for all recaptures. And I didn't know about null moves either, so I didn't have a method for stopping the extensions (partly because I had no method of evaluating the position before extending the search). My program couldn't handle the situations where, after the search horizon, there is possible but unwise recapture. So I created my own solution for that too. You can see how quickly it gets complicated. Although version 1.0 was very sloppy, I learned from it, and when I did a lot of research on chess programming, I was amazed to see that they all ran across the same problems I did! From all the debugging in the first program, I could understand the problems and exactly how and why they occurred, and of course I was impressed with their solution. I'm hoping that version 2.0 will prove to be more competitive.
  • 1.91
    • one executable has its own GUI, another executable runs as a WinBoard-compatible engine (protocol version 2). WinBoard (by Tim Mann) is a program that has the ability to match two chess engines against one another, and to let a chess engine play on an internet chess server (ICS).
    • everything except move generation is bitboard-based (move generation is done almost entirely by table lookup)
    • uses principal variation search (PVS) with quiescence search
    • uses a resizable transposition table
    • searches approximately 100 K nodes per second in the middlegame
    • evaluation is primitive at the moment; it looks at pawn structure, piece position, and opening development. It also distinguishes the three stages of a chess game (opening, middlegame, endgame) and plays accordingly in each stage. It does not do any special endgame evaluation except pawn advancement, and often ignores king safety in the middlegame.
    • always wins against King of Kings 1.0. I've played it against many other amateur chess programs and it fairs well against some of them. But it's no Crafty... yet :)
  • 1.92
    • many, many bug fixes
    • the console version supports the WinBoard protocol version 2 setboard command and the GUI version can open .fen position files.
  • 1.93
    • redesign of evaluation functions
    • much more knowledge (especially about pawn structure and king safety)
    • plays a more solid, aggressive game
    • almost always beats version 1.92
  • 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
    • Defeats version 1.93 the majority of times.
  • 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 extra knowledge 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.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.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.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.99
    • Large opening book: The ZIP file includes a small opening book. The large opening book is 3.3 MB zipped and 6.0 MB unzipped.
    • 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.

Tools

• Chess Tournament Organizer
  • My utility for setting up tournament matches. The program follows a neat algorithm that uses the results from previous rounds to decide the matches for the next round. The algorithm works in such a way that it well distinguishes players similar in rating. Say, for example, there are 30 engines and 30 rounds. After about 10 rounds, players that vary highly in rating will probably never play again (that is, the various levels of participants becomes clear at this point). Since players of equal strength play more games against one another, it becomes easier to distinguish between closely rated players. The program also takes into account the level of opponent each player faces. Suppose that in the first round (when the program has no idea on which players are strong or weak), an average-level player gets a very strong opponent. After a few rounds, as the program begins to realize the strength of both players, it will take that unfair game into consideration and may assign the average-level player to a weaker player and the strong player to a stronger player, as compensation.
  • One disadvantage is that if you are using chess engines, you have to run the games yourself. I thought about automating the process using WinBoard and its command-line options, but there are many situations where an engine crashes or stalls (the engine has to be manually terminated); I've even seen a few illegal move scenarios. I might add that in a future version. Another disadvantage is that the Chess Tournament Organizer has no built-in saving, loading, or resuming features, so once the program is closed, the tournament is over. If there is a future version, it will have resuming capabilities. Anyway, it worked very well on a couple of engine tournaments I ran at home (no, I have no life, lol!).

Links

• (||) Tom Kerrigan's Simple Chess Program (TSCP)
• (||) Robert Hyatt's Crafty (FTP site)
• (||) Eugene Nalimov (endgame tablebases) (e-mail)
• (||) Paul Verhelst's Computer Chess Programming web site
• (||) Strategy and board game programming (lecture notes by David Eppstein)
• (||) Tim Mann's Chess Pages (home of WinBoard and XBoard)
• (||) Thomas Mayer's WinBoard Engines Newsticker
• (||) Free Internet Chess Server (FICS)
• (||) Internet Chess Club (ICC)

If you have any comments or suggestions, e-mail me at kountv@hotmail.com.