LCOV - code coverage report
Current view: top level - src - tree.h (source / functions) Hit Total Coverage
Test: test_coverage.info Lines: 16 16 100.0 %
Date: 2017-06-21 14:32:49 Functions: 2 2 100.0 %

          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        8000 : 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             :     TreeCache()
     137           8 :     : NumInUse(0),
     138             :       Cache(NULL),
     139             :       CacheSize(0),
     140           8 :       counter_(0) {
     141             :     }
     142          16 :     ~TreeCache() {
     143          16 :         if (Cache) delete [] Cache;
     144           8 :     }
     145             : 
     146             :     void Clear() {
     147          27 :         NumInUse = 0;
     148          27 :         counter_ = 0;
     149             :     }
     150             :     size_t Size() {
     151             :         return CacheSize;
     152             :     }
     153             :     size_t UsedSize() {
     154             :         return NumInUse;
     155             :     }
     156           8 :     void CacheResize(size_t max_size) {
     157           8 :         if (max_size != CacheSize) {
     158           8 :             CacheSize = max_size;
     159           8 :             if (Cache) delete [] Cache;
     160           8 :             if (max_size == 0) Cache = NULL;
     161        2008 :             else Cache = new cachedTreeT[max_size];
     162             :         }
     163           8 :         Clear();
     164           8 :     }
     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             : 

Generated by: LCOV version 1.12