winboard/install/files/root/Fruit/technical_10.txt

   1 \r
   2 *** WARNING ***\r
   3 \r
   4 This file described the older Fruit 1.0\r
   5 The evaluation function has been mostly rewritten since.\r
   6 The rest is still mostly accurate.\r
   7 \r
   8 Fabien, a very lazy man.\r
   9 \r
  10 ---\r
  11 \r
  12 Fruit overview\r
  13 --------------\r
  14 \r
  15 Fruit was designed to help with the study of game-tree search\r
  16 algorithms, when applied to chess.  It is now released as a chess\r
  17 engine, which is a somewhat different category of programs.  Therefore\r
  18 the source code contains entire files and also functions that are\r
  19 either not used by the engine, or could be replaced with a much\r
  20 simpler (although somewhat less efficient) equivalent.\r
  21 \r
  22 As a chess engine, Fruit combines a "robust" search algorithm with a\r
  23 "minimalist" evaluation function.  The latter is not a design choice,\r
  24 and will hopefully change in the future.\r
  25 \r
  26 The following description is only a very incomplete description.\r
  27 Please consult the source code for an absolute definition.\r
  28 \r
  29 The search algorithm was designed to accommodate with heavy\r
  30 forward-pruning eccentricities (such as search inconsistencies).  Note\r
  31 that in Fruit 1.0 only null-move pruning is used as a forward-pruning\r
  32 mechanism.\r
  33 \r
  34 \r
  35 Board data structure\r
  36 --------------------\r
  37 \r
  38 Fruit uses the 16x12 board.  Although this structure is not very\r
  39 popular, it can be seen as simply combining 10x12 (mailbox) with 16x8\r
  40 (0x88).\r
  41 \r
  42 0x88 was picked in Fruit because of the small memory requirements of\r
  43 vector calculations (much smaller tables).  It is possible that Fruit\r
  44 uses bitboards for pawns in the future.\r
  45 \r
  46 \r
  47 Search algorithm\r
  48 ----------------\r
  49 \r
  50 The main search algorithm is a classical PVS with iterative deepening.\r
  51 Search enhancements such as a transposition table and null-move\r
  52 pruning are also used (see below).\r
  53 \r
  54 A few details in the PVS implementation are not-so-standard and are\r
  55 there to supposedly enhance the stability of the search (like reducing\r
  56 the consequences of search inconsistencies).  For example the\r
  57 re-search window after a scout fail high of score "value" (with value\r
  58 > alpha) is [alpha,beta], not [value,beta].  As another example, I\r
  59 only allow null move when the static evaluation fails high\r
  60 (i.e. eval() >= beta).  Whether these features improve the strength of\r
  61 the engine is an open question.\r
  62 \r
  63 \r
  64 Transposition table\r
  65 -------------------\r
  66 \r
  67 Fruit uses 4 probes and replaces the shallowest entry.  Time stamping\r
  68 is used so that entries from previous searches are considered\r
  69 available for overwriting.\r
  70 \r
  71 Enhanced Transposition Cutoff (ETC) is also used 4 plies (and more)\r
  72 away from the horizon.\r
  73 \r
  74 \r
  75 Null move\r
  76 ---------\r
  77 \r
  78 Fruit uses R=3 recursive null move, even in the endgame.\r
  79 \r
  80 In Fruit, a precondition to using null move is that the static eval\r
  81 fails high.  One of the consequences of this is that no two null moves\r
  82 can be played in a row (this is because the evaluation is\r
  83 symmetrical).  This is a usual condition but notice that in Fruit the\r
  84 null-move condition is "pure" (independent of move paths).  The\r
  85 fail-high condition was selected for other reasons however.\r
  86 \r
  87 Also, a verification search is launched in the endgame.\r
  88 \r
  89 \r
  90 Move ordering\r
  91 -------------\r
  92 \r
  93 The move ordering is rather basic:\r
  94 \r
  95 - transposition-table move\r
  96 - captures sorted by MVV/LVA\r
  97 - promotions\r
  98 - killer moves (two per level, no counters)\r
  99 - history moves (piece-type/to-square table, with "aging").\r
 100 \r
 101 \r
 102 Evaluation function\r
 103 -------------------\r
 104 \r
 105 The evaluation function is pretty minimal and only includes:\r
 106 \r
 107 - material (only sum of the usual 1/3/3/5/9 values)\r
 108 \r
 109 - piece-on-square table (that can probably be improved a lot)\r
 110 \r
 111 - static pawn-structure evaluation (independent of pieces), stored in a\r
 112   hash table\r
 113 \r
 114 - a few boolean features supposed to represent some sort of piece\r
 115   activity, such as a penalty for bishops and rooks "blocked" by a\r
 116   pawn of the same colour in the "forward" direction.\r
 117 \r
 118 Note that some vital features such as king safety are completely\r
 119 missing.  I cannot recommend such an approach in a serious program.\r
 120 \r
 121 There are two (bad) reasons why the evaluation is so "simple":\r
 122 \r
 123 1) Fruit was designed to experiment with search algorithms (not just\r
 124    for chess)\r
 125 \r
 126 2) I just can't be bothered with trying to design a "good" evaluation\r
 127    function, as this would be an extremely boring occupation for me.\r
 128 \r
 129 \r
 130 Speed\r
 131 -----\r
 132 \r
 133 Fruit is not fast (in nodes per second) given the little it is\r
 134 calculating.  I actually plan on undoing more "optimisations" in order\r
 135 to make the code shorter and more flexible.  I will care about raw\r
 136 speed when (if at all) Fruit's design is more or less "fixed".\r
 137 \r
 138 \r
 139 Notes for programmers\r
 140 ---------------------\r
 141 \r
 142 Some people find that Fruit is surprisingly "strong" given the above\r
 143 (dull) description.  The same persons are probably going to scrutinise\r
 144 the source code looking for "magic tricks"; I wish them good luck.  If\r
 145 they find any, those are likely to be "bugs" that I have overlooked or\r
 146 "features" I have forgotten to remove (please let me know).  The main\r
 147 search function is full_search() in search_full.cpp\r
 148 \r
 149 I suggest instead that one ponders on what other "average amateur"\r
 150 engines might be doing wrong ...  Maybe trying too many heuristics\r
 151 (they might be conflicting or choosing weights for them is too\r
 152 difficult) or code that is too complex, maybe features that look\r
 153 important but are actually performing no useful function ...  Sorry I\r
 154 do not know, and I don't think we will find the answer in Fruit ...\r
 155 \r
 156 \r
 157 Disclaimer\r
 158 ----------\r
 159 \r
 160 Lastly, please take what I am saying with a grain of salt.  I hope\r
 161 that the reader is not completely lacking any sense of humour and I\r
 162 certainly did not intend to be insulting to anyone.\r
 163 \r