+++ /dev/null
-\r
-*** WARNING ***\r
-\r
-This file described the older Fruit 1.0\r
-The evaluation function has been mostly rewritten since.\r
-The rest is still mostly accurate.\r
-\r
-Fabien, a very lazy man.\r
-\r
----\r
-\r
-Fruit overview\r
---------------\r
-\r
-Fruit was designed to help with the study of game-tree search\r
-algorithms, when applied to chess. It is now released as a chess\r
-engine, which is a somewhat different category of programs. Therefore\r
-the source code contains entire files and also functions that are\r
-either not used by the engine, or could be replaced with a much\r
-simpler (although somewhat less efficient) equivalent.\r
-\r
-As a chess engine, Fruit combines a "robust" search algorithm with a\r
-"minimalist" evaluation function. The latter is not a design choice,\r
-and will hopefully change in the future.\r
-\r
-The following description is only a very incomplete description.\r
-Please consult the source code for an absolute definition.\r
-\r
-The search algorithm was designed to accommodate with heavy\r
-forward-pruning eccentricities (such as search inconsistencies). Note\r
-that in Fruit 1.0 only null-move pruning is used as a forward-pruning\r
-mechanism.\r
-\r
-\r
-Board data structure\r
---------------------\r
-\r
-Fruit uses the 16x12 board. Although this structure is not very\r
-popular, it can be seen as simply combining 10x12 (mailbox) with 16x8\r
-(0x88).\r
-\r
-0x88 was picked in Fruit because of the small memory requirements of\r
-vector calculations (much smaller tables). It is possible that Fruit\r
-uses bitboards for pawns in the future.\r
-\r
-\r
-Search algorithm\r
-----------------\r
-\r
-The main search algorithm is a classical PVS with iterative deepening.\r
-Search enhancements such as a transposition table and null-move\r
-pruning are also used (see below).\r
-\r
-A few details in the PVS implementation are not-so-standard and are\r
-there to supposedly enhance the stability of the search (like reducing\r
-the consequences of search inconsistencies). For example the\r
-re-search window after a scout fail high of score "value" (with value\r
-> alpha) is [alpha,beta], not [value,beta]. As another example, I\r
-only allow null move when the static evaluation fails high\r
-(i.e. eval() >= beta). Whether these features improve the strength of\r
-the engine is an open question.\r
-\r
-\r
-Transposition table\r
--------------------\r
-\r
-Fruit uses 4 probes and replaces the shallowest entry. Time stamping\r
-is used so that entries from previous searches are considered\r
-available for overwriting.\r
-\r
-Enhanced Transposition Cutoff (ETC) is also used 4 plies (and more)\r
-away from the horizon.\r
-\r
-\r
-Null move\r
----------\r
-\r
-Fruit uses R=3 recursive null move, even in the endgame.\r
-\r
-In Fruit, a precondition to using null move is that the static eval\r
-fails high. One of the consequences of this is that no two null moves\r
-can be played in a row (this is because the evaluation is\r
-symmetrical). This is a usual condition but notice that in Fruit the\r
-null-move condition is "pure" (independent of move paths). The\r
-fail-high condition was selected for other reasons however.\r
-\r
-Also, a verification search is launched in the endgame.\r
-\r
-\r
-Move ordering\r
--------------\r
-\r
-The move ordering is rather basic:\r
-\r
-- transposition-table move\r
-- captures sorted by MVV/LVA\r
-- promotions\r
-- killer moves (two per level, no counters)\r
-- history moves (piece-type/to-square table, with "aging").\r
-\r
-\r
-Evaluation function\r
--------------------\r
-\r
-The evaluation function is pretty minimal and only includes:\r
-\r
-- material (only sum of the usual 1/3/3/5/9 values)\r
-\r
-- piece-on-square table (that can probably be improved a lot)\r
-\r
-- static pawn-structure evaluation (independent of pieces), stored in a\r
- hash table\r
-\r
-- a few boolean features supposed to represent some sort of piece\r
- activity, such as a penalty for bishops and rooks "blocked" by a\r
- pawn of the same colour in the "forward" direction.\r
-\r
-Note that some vital features such as king safety are completely\r
-missing. I cannot recommend such an approach in a serious program.\r
-\r
-There are two (bad) reasons why the evaluation is so "simple":\r
-\r
-1) Fruit was designed to experiment with search algorithms (not just\r
- for chess)\r
-\r
-2) I just can't be bothered with trying to design a "good" evaluation\r
- function, as this would be an extremely boring occupation for me.\r
-\r
-\r
-Speed\r
------\r
-\r
-Fruit is not fast (in nodes per second) given the little it is\r
-calculating. I actually plan on undoing more "optimisations" in order\r
-to make the code shorter and more flexible. I will care about raw\r
-speed when (if at all) Fruit's design is more or less "fixed".\r
-\r
-\r
-Notes for programmers\r
----------------------\r
-\r
-Some people find that Fruit is surprisingly "strong" given the above\r
-(dull) description. The same persons are probably going to scrutinise\r
-the source code looking for "magic tricks"; I wish them good luck. If\r
-they find any, those are likely to be "bugs" that I have overlooked or\r
-"features" I have forgotten to remove (please let me know). The main\r
-search function is full_search() in search_full.cpp\r
-\r
-I suggest instead that one ponders on what other "average amateur"\r
-engines might be doing wrong ... Maybe trying too many heuristics\r
-(they might be conflicting or choosing weights for them is too\r
-difficult) or code that is too complex, maybe features that look\r
-important but are actually performing no useful function ... Sorry I\r
-do not know, and I don't think we will find the answer in Fruit ...\r
-\r
-\r
-Disclaimer\r
-----------\r
-\r
-Lastly, please take what I am saying with a grain of salt. I hope\r
-that the reader is not completely lacking any sense of humour and I\r
-certainly did not intend to be insulting to anyone.\r
-\r
projects / xboard.git / blobdiff