rodent chess

Rodent, a UCI chess playing engine derived from Sungorus 1.4 Copyright (C) 2009-2011 Pablo Vazquez (Sungorus author) Copyright (C) 2011-2012 Pawel Koziol http://www.pkoziol.cal24.pl/rodent/rodent.htm https://github.com/nescitus/rodent_code I. GPL License Rodent is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. Rodent 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. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. II. Acknowledgments Rodent is an open source chess program derived from Sungorus 1.4 by Pablo Vazquez. Seeing the simplicity of his code I instantly fell in love with it, started adding chess knowledge and advanced search algorithms. Hopefully code quality didn't deteriorate too much because of that attempt at learning by emulation. The second most important source is excellent document called "Toga LOG user manual" by josephd, which is accessible from http://members.aon.at/josefd/Toga%20LOG.html . It describes evaluation function of Fruit/Toga in a natural language. First draft of Rodent evaluation function relied heavily on this document. Currently at least king safety code is different, but for example weak pawn evaluation remains basically the same. Open source programming makes most sense as a collaborative effort. Rodent would be clearly weaker without the following contributions: *Kestutis Gasaitis* has made a thorough inspection of Rodent's code, pointing out many bugs and suggesting several improvements. See changelog and github tickets for details. *Dann Corbit* supplied fast population count functions making use of advanced 64-bit instructions and first bit intrinsics (used since version 0.11 onwards) *Denis Mendoza* and *Graham Banks* independently pointed out an important time management bug in version 0.12, affecting repeated time controls. *Dann Corbit* and *Denis Mendoza* supplied me with 64-bit compiles. III. Project goals: 1. Creating a didactic bitboard engine of reasonable strength, using object-oriented design, modern search techniques and relatively small codebase. There are many superb open source engines, like Fruit, Crafty, Stockfish, to name but a few, and Rodent is unlikely to compete with them on equal footing for some time to come. One thing it can give, however, is a search function that can be read at one sitting (thank You, Pablo Vazquez, it would not be possible without Your work!) 2. Providing a simple framework for testing new ideas and showcasing them (I'm planning a short paper on a "sliding LMR" concept) 3. Providing an engine that is fun to play against, with adjustable strength and different personalities. IV. The most important changes (comparing with Sungorus 1.4) include: - making most of the code object-oriented (in progress) - enabling fractional extensions and reductions - rewriting piece/square code, so that we can use asymmetric pst tables and interpolate between midgame and endgame scores - adding futility pruning - adding "sliding LMR" (see section on search) - adding eval pruning (inspired by DiscoCheck) - adding many evaluation features and weights as described in Toga LOG user manual - adding logarithmic king safety function - some speed optimizations, including pawn hash table and specialized PopCnt functions (many thanks to Dann Corbit for his patch making use of advanced 64-bit instructions) - about 300 Elo gain over the original - opening book in a silly proprietary format - position learning - weaker levels of play V. SEARCH (featuring "sliding LMR" proof of concept) - fail soft alpha beta with principal variation search (from Sungorus) - transposition table (from Sungorus) - null move with variable reduction depth (modified) and with threat detection in order to sort evasion higher (modified) - futility pruning (added) - "sliding" late move reduction (added) - late move pruning (added) - eval pruning (a.k.a. static null move) - internal iterative deepening in pv nodes Rodent uses PVS search with null move and transposition table inherited from Sungorus. It has been enhanced in several standard ways - by adding futility pruning, internal iterative deepening in pv nodes, check extension, Stockfish-like null move pruning and using capture threats uncovered by null move for better move sorting. The only non-standard solution is what I call "sliding Late Move Reduction". Since Rodent from the very beginning uses fractional plies, it made sense to check whether smoothly scaling reduction can help. And it certainly did. It works as follows. Instead of a fixed one ply reduction, Rodent uses something like: QUARTER_PLY * ( (moves_tried / 5)+3 ) where moves_tried counts moves accepted by search as legal. Thus the first reduction occurs much later under normal scheme, but as the search proceeds, the effect of accumulated quarter ply reductions more than compensates for it, without hurting the playing strength. This kind of reduction has a chance of being much less detrimental to the tactical ability of the engine. After all, it is geared towards reducing more deeply when the engine encounters a series of moves that have low probability of changing the node value (move ordering, especially using history heuristic, is a measure of that probability). Imagine a tactical shot requiring two quiet moves, the rest being forcing and therefore exempt from reduction. Both are sorted around move 20. Under normal scheme both would get reduced, the new one reduces just one. Instead, it trims the lines where many moves are sorted down the list. It's true that finding really deep combintations, full of quiet moves, is equally difficult under both schemes. However, probability of such a combination is P(one_move_cuts) * P(next_move_cuts) ... * P(last_required_move_cuts) IIRC (I've never been much into maths, much less into the English math terminology) the right word for this kind of function is "exponential". If we manage to keep the growth of a reduction factor just a bit slower, we'll have a beautifully scalable reduction algorithm. VI. EVALUATION - Fruit-like piece/square tables and mobility values - Fruit-like weak pawns eval - passed pawns eval - strong squares (B, N, even R) - logaritmic, and therefore dynamic King safety evaluation Creating version 0.13 I looked for more aggressive King safety function, using Rebel-like additive table approach. I also wanted my function to ne initialized at startup using some relatively simple mathematical formula. After some experiments with logistic function, I settled for an addition of logarithmic and linear function. I'd like to express my gratitude to Agnieszka Ziomek for discussing these mathematical matters with a noob like me. Mobility evaluation is sometimes inexact due to the concept of "transparent pieces". For example, own queen is considered transparent for the bishop. This might cause occasional error in evaluating whether a bishop can check enemy king, or force the engine to rely on search in order to avoid certain blockages. However, tests has shown that this solution is better than more exact mobility calculation. VII. OPENING BOOK Since version 0.14 Rodent uses its own opening book, encoded in a rather inefficient manner. At startup, it reads two files: book.txt written in a human readable format, and bigbook.wtf using Rodent's own ugly format (hence the file extension). Rodent first looks for moves from the book.txt, and if none is found, it falls back to big main book. book.txt encodes one opening in each line, and its format looks like that: e2e4 a7a6? d2d4 b7b5 a2a4 c8b7 b1d2 e2e4 d7d5!! e4d5 d8d5 b1c3 d8d6! It allows users to write down their own book preferences if they for example want to practice Ruy Lopez or Pirc Defense or force Rodent to play unusual openings. Moves may be followed by punctuation marks: ? (frequency -= 100), ! (frequency += 100), ?? (frequency -= 5000), !! (frequency += 5000). Additionally, a move with "xx" appended will be deleted from the main book permanently. A really desperate user might even create main opening book. All he needs is any of files called feed.txt, feedwhite.txt and feedblack.txt placed in the program directory, Rodent opened in the console mode and manually typed command "feedbook". Program first reads bigbook.wtf (if found), then supplements it with the lines froom feed files, then chokes itself on shaker sort algorithm while displaying number of its iterations, and finally saves a file called newbook.wtf. At this stage user MUST RENAME newbook.wtf to bigbook.wtf. This is a precaution allowing to save old book in case that user considers feed files corrupt. Rodent contains small utility reformatting book files from something like: e2e4e7e6d2d4d7d5b1c3f8b4 to version with spaces between the moves. In order to do this, one needs to copy "dense" opening book into the file "dense.txt", open Rodent in the console mode and type command "split". Result will be saved in "loose.txt". Another additional command is "bookdoctor". This command causes Rodent to investigate its main book file and stop at first point where it finds either an infrequent move or missing transposition into book line. In both cases it would be prudent to decide whether a move should be upgraded or marked as unplayable. Rodent may use big book in two modes: it may pick moves according to their frequency or conduct short verification search. The latter causes it to play moves that it likes and to reject errors that are likely to be found in the big book. The second mode can be turned on using UCI option "VerifyBook" VIII. WEAKENING Rodent has a feature allowing to reduce its playing strength. For now, it is still in the experimental phase and still undergoes tweaking and tuning, but basic infrastructure is already in place. It consists of three parts: 1. Weaker levels play slower. On starting a new iteration or changing a move Rodent "freezes" for a moment, depending on its Elo command. 2. Weaker levels add random value to evaluation score. 3. Weaker levels are more likely to blunder, because they forget about calculating consequences of certain moves. As You can probably guess, tuning the third element of the algorithm presents the hardest challenge. Engine forgetting about certain moves (like captures by a pawn or (re)captures of recently moved piece) would look unnatural, except of the lowest levels. Engine forgetting about escapes from check would happily sack material for false checkmates. Engine not missing tactical moves would not be weak enough. IX. INI FILE rodent.ini file contains the following information - panel type, determined by string "user nomal" or "user power" - list of available strength levels - list of available playing styles - list of available opening books Normal user panel lists available levels, strength and personalities, registered in the ini file. Power user obtains the ability to manually set internal engine parameters via UCI options. X. CONVENTIONS AND STRUCTURAL DECISIONS Naming conventions: - an asterisk before a comment announcing a code segment means that this part of code is undergoing modification and testing - variable names start with small letters - function names start with captital letters - variables treated as flags have "f" prefix, i.e. f_in_check - bitboard variables have "bb" prefix, i.e. bbControl in piece evaluators - struct definitions have "s" prefix, i.e. sEvaluator Classes: - sParser - UCI parser - sTransTable - transposition table (no functional change vs Sungorus) - sHistory - global history and killer tables - sGenCache - caching generated bitboards for minimal speedup - sTimer - setting and enforcing time controls - sSelector - picks moves in an ordered fashion - sSearcher - implements classical alpha-beta pvs search algorithm - sEvaluator - implements valuation function - sData - globally accessible configurable data; in the target version, if someone wants to concentrate on just one facet of a program, he will have to know just sData and the relevant class. Structural decisions: - we use the same square ordering as Crafty and Stockfish (A1 = 0) - we DO NOT split Search function into pv and non-pv, since resulting complexity isn't worth small speed gain.