Scid  4.6.5
tree.h
Go to the documentation of this file.
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 {
46  char san[8];
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.
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 {
85 };
86 
87 
88 // cachedTreeT:
89 // Stores a board position and its associated tree of all moves
90 // played at that position.
91 //
92 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:
137  : NumInUse(0),
138  Cache(NULL),
139  CacheSize(0),
140  counter_(0) {
141  }
143  if (Cache) delete [] Cache;
144  }
145 
146  void Clear() {
147  NumInUse = 0;
148  counter_ = 0;
149  }
150  size_t Size() {
151  return CacheSize;
152  }
153  size_t UsedSize() {
154  return NumInUse;
155  }
156  void CacheResize(size_t max_size) {
157  if (max_size != CacheSize) {
158  CacheSize = max_size;
159  if (Cache) delete [] Cache;
160  if (max_size == 0) Cache = NULL;
161  else Cache = new cachedTreeT[max_size];
162  }
163  Clear();
164  }
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 
uint score
Definition: tree.h:49
sqsqname
Definition: board.tcl:292
void set(Position *pos, treeT *tree, Filter *filter, uint32_t time)
Definition: tree.h:102
uint perfCount
Definition: tree.h:54
uint freq[NUM_RESULT_TYPES]
Definition: tree.h:47
const uint NUM_RESULT_TYPES
Definition: common.h:182
const treeT & getTree() const
Definition: tree.h:112
static bool cmpTime(const cachedTreeT &a, const cachedTreeT &b)
Definition: tree.h:115
const cachedTreeT * Lookup(Position *pos)
Definition: tree.h:166
#define ASSERT(f)
Definition: common.h:67
const resultT RESULT_Black
Definition: common.h:187
void initTreeNode(treeNodeT *tnode)
Definition: tree.h:60
uint eloSum
Definition: tree.h:53
uint moveCount
Definition: tree.h:83
errorT UncompressTo(Filter *filter) const
Definition: filter.cpp:107
size_t UsedSize()
Definition: tree.h:153
const resultT RESULT_Draw
Definition: common.h:188
uint64_t yearSum
Definition: tree.h:57
char san[8]
Definition: tree.h:46
const squareT A1
Definition: common.h:343
ecoT ecoCode
Definition: tree.h:51
TreeCache()
Definition: tree.h:136
uint perfSum
Definition: tree.h:55
#define MAX_TREE_NODES
Definition: tree.h:38
bool Add(Position *pos, treeT *tree, Filter *filter)
Definition: tree.h:215
void CompressFrom(Filter *filter)
Definition: filter.cpp:76
errorT restoreFilter(Filter *filter) const
Definition: tree.h:109
const resultT RESULT_White
Definition: common.h:186
uint32_t uint
Definition: common.h:99
Definition: board.tcl:276
uint totalCount
Definition: tree.h:84
const squareT H8
Definition: common.h:350
uint eloCount
Definition: tree.h:52
ushort ecoT
Definition: common.h:161
Clear
Definition: game.tcl:8
unsigned short errorT
Definition: error.h:20
Definition: tree.h:81
simpleMoveT sm
Definition: tree.h:45
const pieceT * GetBoard() const
Definition: position.h:189
uint64_t yearCount
Definition: tree.h:56
Definition: filter.h:32
byte colorT
Definition: common.h:112
Definition: tree.h:44
void CacheResize(size_t max_size)
Definition: tree.h:156
colorT GetToMove()
Definition: position.h:155
const resultT RESULT_None
Definition: common.h:185
size_t Size()
Definition: tree.h:150
Definition: tree.tcl:6
~TreeCache()
Definition: tree.h:142
byte squareT
Definition: common.h:113
byte pieceT
Definition: common.h:111
uint total
Definition: tree.h:48
void Clear()
Definition: tree.h:146