File: technical_10.txt

package info (click to toggle)
fruit 2.1.dfsg-7
  • links: PTS
  • area: main
  • in suites: buster, sid, stretch
  • size: 1,180 kB
  • ctags: 1,215
  • sloc: cpp: 8,954; makefile: 24
file content (163 lines) | stat: -rw-r--r-- 5,678 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

*** WARNING ***

This file described the older Fruit 1.0
The evaluation function has been mostly rewritten since.
The rest is still mostly accurate.

Fabien, a very lazy man.

---

Fruit overview
--------------

Fruit was designed to help with the study of game-tree search
algorithms, when applied to chess.  It is now released as a chess
engine, which is a somewhat different category of programs.  Therefore
the source code contains entire files and also functions that are
either not used by the engine, or could be replaced with a much
simpler (although somewhat less efficient) equivalent.

As a chess engine, Fruit combines a "robust" search algorithm with a
"minimalist" evaluation function.  The latter is not a design choice,
and will hopefully change in the future.

The following description is only a very incomplete description.
Please consult the source code for an absolute definition.

The search algorithm was designed to accommodate with heavy
forward-pruning eccentricities (such as search inconsistencies).  Note
that in Fruit 1.0 only null-move pruning is used as a forward-pruning
mechanism.


Board data structure
--------------------

Fruit uses the 16x12 board.  Although this structure is not very
popular, it can be seen as simply combining 10x12 (mailbox) with 16x8
(0x88).

0x88 was picked in Fruit because of the small memory requirements of
vector calculations (much smaller tables).  It is possible that Fruit
uses bitboards for pawns in the future.


Search algorithm
----------------

The main search algorithm is a classical PVS with iterative deepening.
Search enhancements such as a transposition table and null-move
pruning are also used (see below).

A few details in the PVS implementation are not-so-standard and are
there to supposedly enhance the stability of the search (like reducing
the consequences of search inconsistencies).  For example the
re-search window after a scout fail high of score "value" (with value
> alpha) is [alpha,beta], not [value,beta].  As another example, I
only allow null move when the static evaluation fails high
(i.e. eval() >= beta).  Whether these features improve the strength of
the engine is an open question.


Transposition table
-------------------

Fruit uses 4 probes and replaces the shallowest entry.  Time stamping
is used so that entries from previous searches are considered
available for overwriting.

Enhanced Transposition Cutoff (ETC) is also used 4 plies (and more)
away from the horizon.


Null move
---------

Fruit uses R=3 recursive null move, even in the endgame.

In Fruit, a precondition to using null move is that the static eval
fails high.  One of the consequences of this is that no two null moves
can be played in a row (this is because the evaluation is
symmetrical).  This is a usual condition but notice that in Fruit the
null-move condition is "pure" (independent of move paths).  The
fail-high condition was selected for other reasons however.

Also, a verification search is launched in the endgame.


Move ordering
-------------

The move ordering is rather basic:

- transposition-table move
- captures sorted by MVV/LVA
- promotions
- killer moves (two per level, no counters)
- history moves (piece-type/to-square table, with "aging").


Evaluation function
-------------------

The evaluation function is pretty minimal and only includes:

- material (only sum of the usual 1/3/3/5/9 values)

- piece-on-square table (that can probably be improved a lot)

- static pawn-structure evaluation (independent of pieces), stored in a
  hash table

- a few boolean features supposed to represent some sort of piece
  activity, such as a penalty for bishops and rooks "blocked" by a
  pawn of the same colour in the "forward" direction.

Note that some vital features such as king safety are completely
missing.  I cannot recommend such an approach in a serious program.

There are two (bad) reasons why the evaluation is so "simple":

1) Fruit was designed to experiment with search algorithms (not just
   for chess)

2) I just can't be bothered with trying to design a "good" evaluation
   function, as this would be an extremely boring occupation for me.


Speed
-----

Fruit is not fast (in nodes per second) given the little it is
calculating.  I actually plan on undoing more "optimisations" in order
to make the code shorter and more flexible.  I will care about raw
speed when (if at all) Fruit's design is more or less "fixed".


Notes for programmers
---------------------

Some people find that Fruit is surprisingly "strong" given the above
(dull) description.  The same persons are probably going to scrutinise
the source code looking for "magic tricks"; I wish them good luck.  If
they find any, those are likely to be "bugs" that I have overlooked or
"features" I have forgotten to remove (please let me know).  The main
search function is full_search() in search_full.cpp

I suggest instead that one ponders on what other "average amateur"
engines might be doing wrong ...  Maybe trying too many heuristics
(they might be conflicting or choosing weights for them is too
difficult) or code that is too complex, maybe features that look
important but are actually performing no useful function ...  Sorry I
do not know, and I don't think we will find the answer in Fruit ...


Disclaimer
----------

Lastly, please take what I am saying with a grain of salt.  I hope
that the reader is not completely lacking any sense of humour and I
certainly did not intend to be insulting to anyone.