--- /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