00001 #include "osl/checkmate/analyzer/proofTreeDepth.h" 00002 #include "osl/checkmate/checkHashRecord.h" 00003 #include "osl/stl/hash_map.h" 00004 #include "osl/stl/pointerHash.h" 00005 00010 struct osl::checkmate::analyzer::ProofTreeDepth::Table 00011 : public osl::hash_map<const CheckHashRecord*, int> 00012 { 00013 }; 00014 00015 osl::checkmate::analyzer:: 00016 ProofTreeDepth::ProofTreeDepth() 00017 : table(new Table()) 00018 { 00019 } 00020 00021 osl::checkmate::analyzer:: 00022 ProofTreeDepth::~ProofTreeDepth() 00023 { 00024 } 00025 00026 int osl::checkmate::analyzer:: 00027 ProofTreeDepth::depth(const CheckHashRecord *record, bool is_or_node) const 00028 { 00029 if (! record) 00030 { 00031 assert(is_or_node); // ImmediateCheckmate 00032 return 1; 00033 } 00034 assert(record); 00035 assert(record->proofDisproof().isCheckmateSuccess()); 00036 return (is_or_node ? orNode(record) : andNode(record)); 00037 } 00038 00039 int osl::checkmate::analyzer:: 00040 ProofTreeDepth::orNode(const CheckHashRecord *record) const 00041 { 00042 assert(record); 00043 assert(record->proofDisproof().isCheckmateSuccess()); 00044 const Table::const_iterator p = table->find(record); 00045 if (p != table->end()) 00046 return p->second; 00047 (*table)[record] = -1; 00048 00049 if (record->bestMove && (! record->bestMove->record)) 00050 { 00051 // ImmediateCheckmate 00052 assert(record->bestMove->flags.isSet(MoveFlags::ImmediateCheckmate)); 00053 (*table)[record] = 1; 00054 return 1; 00055 } 00056 const CheckMoveList& l = record->finalByDominance() 00057 ? record->finalByDominance()->moves 00058 : record->moves; 00059 for (CheckMoveList::const_iterator p=l.begin(); p!=l.end(); ++p) 00060 { 00061 if (! p->record) 00062 continue; 00063 if (! p->record->proofDisproof().isCheckmateSuccess()) 00064 continue; 00065 const int depth = andNode(p->record); 00066 if (depth >= 0) 00067 { 00068 (*table)[record] = depth+1; 00069 return (*table)[record]; 00070 } 00071 } 00072 if (! l.empty()) 00073 return -1; // 롼¤ 00074 00075 (*table)[record] = 0; 00076 return 0; // or node ǻؼ꤬ʤƵ => ƨƤʤ 00077 } 00078 00079 int osl::checkmate::analyzer:: 00080 ProofTreeDepth::andNode(const CheckHashRecord *record) const 00081 { 00082 assert(record); 00083 assert(record->proofDisproof().isCheckmateSuccess()); 00084 const Table::const_iterator p = table->find(record); 00085 if (p != table->end()) 00086 return p->second; 00087 (*table)[record] = -1; 00088 00089 int result = 0; // and node ǻؼ꤬ʤƵ => ƨʤ 00090 00091 const CheckMoveList& l = record->finalByDominance() 00092 ? record->finalByDominance()->moves 00093 : record->moves; 00094 for (CheckMoveList::const_iterator p=l.begin(); p!=l.end(); ++p) 00095 { 00096 if (! p->record) 00097 continue; 00098 const int depth = orNode(p->record); 00099 if (depth < 0) 00100 return depth; // loop found 00101 result = std::max(depth+1, result); 00102 } 00103 00104 (*table)[record] = result; 00105 return result; 00106 } 00107 // ;;; Local Variables: 00108 // ;;; mode:c++ 00109 // ;;; c-basic-offset:2 00110 // ;;; End: