00001
00002
00003 #include "osl/checkmate/dominanceTable.h"
00004 #include "osl/checkmate/checkHashRecord.h"
00005 #include "osl/checkmate/sameBoardList.h"
00006 #include "osl/stat/histogram.h"
00007 #include "osl/hash/hashKey.h"
00008 #include "osl/stl/hash_map.h"
00009 #include <algorithm>
00010 #include <iostream>
00011
00012 namespace osl
00013 {
00014 namespace checkmate
00015 {
00016 #ifdef OSL_SMP
00017 static const int initial_capacity = 100;
00018 #else
00019 static const int initial_capacity = 1000000;
00020 #endif
00021 }
00022
00023 typedef hash_map<SignatureKey,checkmate::SameBoardList> hash_map_t;
00024 }
00025
00026
00027 struct osl::checkmate::DominanceTable::Table : public hash_map_t
00028 {
00029 explicit Table(size_t capacity) : hash_map_t(capacity)
00030 {
00031 }
00032 };
00033
00034 osl::checkmate::
00035 DominanceTable::DominanceTable(Player a)
00036 : table(new Table(initial_capacity)), attacker(a),
00037 rootNode(new CheckHashRecord)
00038 {
00039 }
00040 osl::checkmate::
00041 DominanceTable::~DominanceTable()
00042 {
00043 #ifdef CHECKMATE_DEBUG
00044 confirmNoVisitedRecords();
00045 #endif
00046 #ifdef DOMINANCETABLE_SHOW_STAT
00047 if (! table->empty())
00048 {
00049 stat::Histogram h(1,100);
00050 for (Table::iterator p=table->begin(); p!=table->end(); ++p)
00051 {
00052 h.add(p->second.size());
00053 }
00054 h.show(std::cerr);
00055 }
00056 #endif
00057 }
00058
00059 osl::checkmate::CheckHashRecord * osl::checkmate::
00060 DominanceTable::find(const HashKey& key)
00061 {
00062 Table::iterator p=table->find(key.getSignatureKey());
00063 if (p==table->end())
00064 return 0;
00065 return p->second.find(key.blackStand());
00066 }
00067
00068 osl::checkmate::CheckHashRecord * osl::checkmate::
00069 DominanceTable::allocate(const HashKey& key, const PieceStand& white_stand,
00070 const PathEncoding& path)
00071 {
00072 size_t count = 0;
00073 SameBoardList& l = (*table)[key.getSignatureKey()];
00074 if (attacker == BLACK)
00075 return l.allocate<BLACK>(key.blackStand(), white_stand, path, count);
00076 else
00077 return l.allocate<WHITE>(key.blackStand(), white_stand, path, count);
00078 }
00079
00080 void osl::checkmate::
00081 DominanceTable::clear()
00082 {
00083 TwinTableHolder::clear();
00084 table->clear();
00085 }
00086
00087 const osl::checkmate::CheckHashRecord * osl::checkmate::
00088 DominanceTable::find(const HashKey& key) const
00089 {
00090 Table::const_iterator p=table->find(key.getSignatureKey());
00091 if (p==table->end())
00092 return 0;
00093 return p->second.find(key.blackStand());
00094 }
00095 size_t osl::checkmate::
00096 DominanceTable::size() const
00097 {
00098 return table->size();
00099 }
00100
00101 void osl::checkmate::
00102 DominanceTable::confirmNoVisitedRecords() const
00103 {
00104 int visited = 0;
00105 for (Table::const_iterator p=table->begin(); p!=table->end(); ++p)
00106 {
00107 const int curVisited = p->second.confirmNoVisitedRecords();
00108 #ifdef CHECKMATE_EXTRA_DEBUG
00109 if (curVisited)
00110 std::cerr << p->first.getSignature()
00111 << " " << p->first.getBoardKey()[0]
00112 << "\n";
00113 #endif
00114 visited += curVisited;
00115 }
00116 if (visited != countVisited())
00117 {
00118
00119
00120 std::cerr << "DominanceTable::confirmNoVisitedRecords "
00121 << visited << " visited nodes found\n";
00122 }
00123 }
00124
00125
00126
00127
00128