Line data Source code
1 : /*
2 : * Copyright (C) 1999 Shane Hudson
3 : * Copyright (C) 2015 Fulvio Benini
4 :
5 : * This file is part of Scid (Shane's Chess Information Database).
6 : *
7 : * Scid is free software: you can redistribute it and/or modify
8 : * it under the terms of the GNU General Public License as published by
9 : * the Free Software Foundation.
10 : *
11 : * Scid is distributed in the hope that it will be useful,
12 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : * GNU General Public License for more details.
15 : *
16 : * You should have received a copy of the GNU General Public License
17 : * along with Scid. If not, see <http://www.gnu.org/licenses/>.
18 : */
19 :
20 : #ifndef SCID_TREE_H
21 : #define SCID_TREE_H
22 :
23 : #include "common.h"
24 : #include "filter.h"
25 : #include <vector>
26 : #include <algorithm>
27 :
28 :
29 : //
30 : // Our tree structures:
31 : //
32 :
33 : // MAX_TREE_NODES: Fixed maximum number of moves a treeT can store.
34 : // The number of played legal moves in a position rarely is over
35 : // 20, so 60 is a sane limit.
36 : //
37 :
38 : #define MAX_TREE_NODES 60
39 :
40 : // treeNodeT:
41 : // Stores the move data, frequency, score, results by result type,
42 : // and eco code of a single move played from a position.
43 : //
44 : struct treeNodeT {
45 : simpleMoveT sm;
46 : char san[8];
47 : uint freq [NUM_RESULT_TYPES];
48 : uint total; // Total count
49 : uint score; // Score for white, in points per 1000 games, so
50 : // 55.1% would be a score of 551.
51 : ecoT ecoCode;
52 : uint eloCount; // Count of games with an Elo.
53 : uint eloSum; // Sum of Elos.
54 : uint perfCount; // Count of games with an opponent Elo.
55 : uint perfSum; // Sum of opponent Elos.
56 : uint64_t yearCount; // Count of games with year != 0.
57 : uint64_t yearSum; // Sum of years.
58 : };
59 :
60 : inline void initTreeNode (treeNodeT * tnode) {
61 : tnode->freq[RESULT_White] = tnode->freq[RESULT_Black]
62 : = tnode->freq[RESULT_Draw] = tnode->freq[RESULT_None] = 0;
63 : for (uint i=0; i < 8; i++) { tnode->san[i] = 0; }
64 : tnode->total = 0;
65 : tnode->score = 0;
66 : tnode->ecoCode = 0;
67 : tnode->eloCount = 0;
68 : tnode->eloSum = 0;
69 : tnode->perfCount = 0;
70 : tnode->perfSum = 0;
71 : tnode->yearCount = 0;
72 : tnode->yearSum = 0;
73 : }
74 :
75 :
76 :
77 : // treeT:
78 : // Stores an array of tree nodes (each has a move, its frequency,
79 : // score and ECO code) for a certain position.
80 : //
81 : struct treeT {
82 : treeNodeT node [MAX_TREE_NODES];
83 : uint moveCount;
84 : uint totalCount;
85 : };
86 :
87 :
88 : // cachedTreeT:
89 : // Stores a board position and its associated tree of all moves
90 : // played at that position.
91 : //
92 7000 : class cachedTreeT {
93 : pieceT board_[64];
94 : colorT toMove_;
95 : treeT tree_;
96 : CompressedFilter cfilter_;
97 : uint32_t time_;
98 :
99 : friend class TreeCache;
100 :
101 : public:
102 : void set(Position* pos, treeT* tree, Filter* filter, uint32_t time) {
103 : std::copy(pos->GetBoard(), pos->GetBoard() + 64, board_);
104 : toMove_ = pos->GetToMove();
105 : tree_ = *tree;
106 : cfilter_.CompressFrom(filter);
107 : time_ = time;
108 : }
109 : errorT restoreFilter(Filter* filter) const {
110 : return cfilter_.UncompressTo(filter);
111 : }
112 : const treeT& getTree() const {
113 : return tree_;
114 : }
115 : static bool cmpTime(const cachedTreeT& a, const cachedTreeT& b) {
116 : return a.time_ < b.time_;
117 : }
118 : };
119 :
120 :
121 :
122 : // A TreeCache object stores a fixed number of positions and their
123 : // tree data. The idea is that the common positions (the starting
124 : // position, the basic opening positions like 1.e4, 1.d4, etc) will
125 : // be have their tree information stored in a cache to save doing a
126 : // position search.
127 :
128 :
129 : class TreeCache {
130 : size_t NumInUse;
131 : cachedTreeT* Cache;
132 : size_t CacheSize;
133 : uint32_t counter_;
134 :
135 : public:
136 14 : TreeCache()
137 14 : : NumInUse(0),
138 : Cache(NULL),
139 : CacheSize(0),
140 14 : counter_(0) {
141 14 : }
142 28 : ~TreeCache() {
143 14 : if (Cache) delete [] Cache;
144 14 : }
145 :
146 39 : void Clear() {
147 39 : NumInUse = 0;
148 39 : counter_ = 0;
149 39 : }
150 : size_t Size() {
151 : return CacheSize;
152 : }
153 : size_t UsedSize() {
154 : return NumInUse;
155 : }
156 14 : void CacheResize(size_t max_size) {
157 14 : if (max_size != CacheSize) {
158 14 : CacheSize = max_size;
159 14 : if (Cache) delete [] Cache;
160 14 : if (max_size == 0) Cache = NULL;
161 14 : else Cache = new cachedTreeT[max_size];
162 : }
163 14 : Clear();
164 14 : }
165 :
166 : const cachedTreeT* Lookup(Position* pos) {
167 : int idx = LookupIndex(pos);
168 : if (idx == -1) return NULL;
169 : return &(Cache[idx]);
170 : }
171 : bool Add(Position* pos, treeT* tree, Filter* filter);
172 :
173 : private:
174 : TreeCache(const TreeCache&);
175 : void operator=(const TreeCache&);
176 :
177 : int LookupIndex(Position* pos);
178 : };
179 :
180 :
181 :
182 :
183 : //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
184 : // TreeCache::LookupIndex():
185 : // Lookup a position in the tree cache, and return its index or -1
186 : // if it is not in the cache.
187 : //
188 : inline int
189 : TreeCache::LookupIndex (Position * pos)
190 : {
191 : for (uint i=0; i < NumInUse; i++) {
192 : if (Cache[i].toMove_ != pos->GetToMove()) { continue; }
193 :
194 : const pieceT* board = pos->GetBoard();
195 : const pieceT* board2 = Cache[i].board_;
196 : bool found = true;
197 : for (squareT sq=A1; sq <= H8; sq++, board++, board2++) {
198 : if (*board != *board2) { found = false; break; }
199 : }
200 : if (found) {
201 : Cache[i].time_ = counter_++;
202 : return static_cast<int>(i);
203 : }
204 : }
205 : // Ended the search, no match:
206 : return -1;
207 : }
208 :
209 :
210 : //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
211 : // TreeCache::Add():
212 : // Add a position to the cache if applicable..
213 : //
214 : inline bool
215 : TreeCache::Add (Position * pos, treeT * pTree, Filter * filter)
216 : {
217 : ASSERT(LookupIndex(pos) == -1);
218 :
219 : if (NumInUse < CacheSize) {
220 : // Cache is not yet full. Add the position to the cache:
221 : Cache[NumInUse++].set(pos, pTree, filter, counter_++);
222 : } else {
223 : // Cache is full!
224 : // Replace the oldest node:
225 : cachedTreeT* end = Cache + CacheSize;
226 : cachedTreeT* replace = std::min_element(Cache, end, cachedTreeT::cmpTime);
227 : if (replace == end) return false;
228 :
229 : ASSERT(replace->time_ <= counter_);
230 : replace->set(pos, pTree, filter, counter_++);
231 : }
232 : return true;
233 : }
234 :
235 :
236 : #endif
237 :
238 : //////////////////////////////////////////////////////////////////////
239 : // EOF: tree.h
240 : //////////////////////////////////////////////////////////////////////
241 :
|
