00001
00002
00003 #include "osl/search/simpleHashTable.h"
00004 #include "osl/search/simpleHashRecord.h"
00005 #include "osl/search/analyzer/recordSet_.h"
00006 #include "osl/container/generalSimpleHashTable.tcc"
00007 #include <iostream>
00008
00009 namespace osl
00010 {
00011 template class container::GeneralSimpleHashTable <SimpleHashRecord>;
00012 }
00013
00014 osl::search::SimpleHashTable::
00015 SimpleHashTable(unsigned int capacity, int minimum_recordlimit, int v)
00016 : GeneralSimpleHashTable<SimpleHashRecord>(capacity),
00017 minimum_limit(minimum_recordlimit), verbose(v)
00018 {
00019 }
00020
00021 osl::search::SimpleHashTable::
00022 ~SimpleHashTable()
00023 {
00024 if (verbose > 1 && size())
00025 {
00026 std::cerr << "SimpleHashTable size: " << size()
00027 << ", cache hit " << table->num_cache_hit
00028 << ", table full " << table->num_record_after_full << "\n";
00029 }
00030 }
00031
00032 void osl::search::SimpleHashTable::
00033 setVerbose(int v)
00034 {
00035 verbose = v;
00036 }
00037
00038 void osl::search::SimpleHashTable::
00039 setMinimumRecordLimit(int new_limit)
00040 {
00041 minimum_limit = new_limit;
00042 }
00043
00044 int osl::search::SimpleHashTable::
00045 minimumRecordLimit() const
00046 {
00047 return minimum_limit;
00048 }
00049
00050 osl::search::SimpleHashRecord *
00051 osl::search::SimpleHashTable::
00052 allocate(const HashKey& key, int limit)
00053 {
00054 if (limit < minimumRecordLimit())
00055 return find(key);
00056 return GeneralSimpleHashTable <SimpleHashRecord>::allocate (key);
00057 }
00058
00059 int osl::search::SimpleHashTable::
00060 verboseLevel() const
00061 {
00062 return verbose;
00063 }
00064
00065 osl::search::SimpleHashRecord* osl::search::SimpleHashTable::
00066 migrate(const HashKey& root, int max_depth, int min_limit,
00067 SimpleHashTable& out) const
00068 {
00069 const SimpleHashRecord *original = find(root);
00070 if (original == 0)
00071 return 0;
00072 const int target_limit
00073 = std::max(original->lowerLimit(), original->upperLimit());
00074 if (target_limit < min_limit)
00075 return 0;
00076 SimpleHashRecord *copy = out.find(root);
00077 if (copy)
00078 return copy;
00079 copy = out.allocate(root, target_limit);
00080 if (! copy)
00081 return 0;
00082 copy->copyFrom(*original);
00083 if (max_depth > 0)
00084 {
00085 SearchMoveSet::const_range r(copy->moves());
00086 for (SearchMoveSet::const_iterator p=r.first; p!=r.last; ++p)
00087 {
00088 const HashKey next = root.newHashWithMove(p->getMove());
00089 p->record = migrate(next, max_depth - 1, min_limit, out);
00090 }
00091 }
00092 copy->fixBestMove();
00093 return copy;
00094 }
00095
00096 bool osl::search::SimpleHashTable::
00097 isConsistent() const
00098 {
00099 for(size_t i=0;i<Table::DIVSIZE;i++){
00100 for (Table::const_iterator p=table->tables[i].begin();
00101 p!=table->tables[i].end(); ++p)
00102 {
00103 const HashKey& key = p->first;
00104 const SimpleHashRecord& record = p->second;
00105 SearchMoveSet::const_range r(record.moves());
00106 for (SearchMoveSet::const_iterator q=r.first; q!=r.last; ++q)
00107 {
00108 if (q->record == 0)
00109 continue;
00110 const HashKey next = key.newHashWithMove(q->getMove());
00111 if (q->record != find(next))
00112 return false;
00113 }
00114 }
00115 }
00116 return true;
00117 }
00118
00119 int osl::search::SimpleHashTable::
00120 divSize() const
00121 {
00122 return GeneralSimpleHashTable<SimpleHashRecord>::divSize();
00123 }
00124
00125 void osl::search::SimpleHashTable::
00126 getPV(const HashKey& root, MoveVector& out, size_t *quiesce_start) const
00127 {
00128 analyzer::RecordSet dejavu;
00129 HashKey key = root;
00130 const SimpleHashRecord *record;
00131 while (true) {
00132 record = table->find(key);
00133 if (! record || dejavu.find(record) != dejavu.end()) {
00134 break;
00135 }
00136 const Move best_move = record->bestMove().getMove();
00137 if (best_move.isInvalid()) {
00138 break;
00139 }
00140 dejavu.insert(record);
00141 out.push_back(best_move);
00142 key = key.newHashWithMove(best_move);
00143 }
00144 if (! quiesce_start || ! record)
00145 return;
00146 *quiesce_start = out.size();
00147 while (true) {
00148 const Move best_move = record->qrecord.bestMove();
00149 if (best_move.isInvalid()) {
00150 break;
00151 }
00152 out.push_back(best_move);
00153
00154 key = key.newHashWithMove(best_move);
00155 record = table->find(key);
00156 if (! record || dejavu.find(record) != dejavu.end()) {
00157 break;
00158 }
00159 dejavu.insert(record);
00160 }
00161 }
00162
00163
00164
00165
00166
00167