00001 #include "osl/checkmate/dualCheckmateSearcher.h"
00002 #include "osl/checkmate/dualCheckmateSearcher.tcc"
00003 #include "osl/checkmate/checkmateSearcher.tcc"
00004 #include "osl/checkmate/fixedDepthSearcher.tcc"
00005 #include "osl/checkmate/oracleProver.tcc"
00006 #include "osl/checkmate/oracleDisprover.tcc"
00007
00008 #include "osl/checkmate/analyzer/checkTableAnalyzer.h"
00009 #include "osl/checkmate/analyzer/proofTreeDepth.h"
00010 #include "osl/checkmate/simpleCheckHashTable.h"
00011 #include "osl/checkmate/dominanceTable.h"
00012 #include "osl/checkmate/checkHashRecord.h"
00013 #include "osl/checkmate/checkmateRecorder.h"
00014 #include "osl/checkmate/libertyEstimator.h"
00015 #include "osl/checkmate/nullEstimator.h"
00016 #include "osl/checkmate/pieceCost.h"
00017 #include "osl/checkmate/nullCost.h"
00018 #include "osl/record/csaString.h"
00019 #include "osl/record/csaRecord.h"
00020 #include "osl/state/hashEffectState.h"
00021 #include "osl/misc/perfmon.h"
00022 #include "osl/misc/realTime.h"
00023
00024 #include <boost/scoped_ptr.hpp>
00025 #include <string>
00026 #include <iostream>
00027 #include <fstream>
00028 #include <cstdlib>
00029 #include <unistd.h>
00030
00031 using namespace osl;
00032 using namespace osl::checkmate;
00033 using namespace osl::misc;
00034 using osl::checkmate::analyzer::ProofTreeDepth;
00035 void usage(const char *prog)
00036 {
00037 using namespace std;
00038 cerr << "Usage: " << prog << " [-vpPEOt] [-T tree-size-out] [-F FILES] [-l nodelimit] [-L loglimit] [-o tree-output-filename] [-d logdepth] [-A depth(>0)] [-a depth(>0)] csa-filenames "
00039 << endl
00040 << "-v show result\n"
00041 << "-p show proof tree\n"
00042 << "-P (plain) don't use heuristics\n"
00043 << "-A depth show all tree (expanding solved branch)\n"
00044 << "-a depth show tree\n"
00045 << "-E show filnames that are solved and found to be 'escape'\n"
00046 << "-t force turn's player to attack even if he is in check\n"
00047 << "-O use outline format for dumping tree\n"
00048 << endl;
00049 exit(1);
00050 }
00051
00052 bool verbose=false;
00053 unsigned long long total_cycles=0;
00054 size_t limit = 409600;
00055 bool showProofTree = false;
00056 int showAllTreeDepth = 0;
00057 int showTreeDepth = 0;
00058 bool showEscapeFilename = false;
00059 bool force_attack = false;
00060 bool useDominanceRelation = false;
00061 int num_checkmate=0, num_escape=0, num_unkown=0;
00062 double total_nodes=0, total_tables=0;
00063 bool useOutlineFormat = false;
00064 size_t logThreshold = 0;
00065 bool useHeuristics = true;
00066
00067 std::ostream *treeOut = 0;
00068 std::ostream *tree_size_out = 0;
00069
00070 template <class Table, class H, class Cost>
00071 void search(const char *filename);
00072 void searchFile(const char *filename);
00073
00074 int main(int argc, char **argv)
00075 {
00076 const char *program_name = argv[0];
00077 bool error_flag = false;
00078 extern char *optarg;
00079 extern int optind;
00080
00081 const char *FILES = 0;
00082 treeOut = &std::cout;
00083 boost::scoped_ptr<std::ofstream> treefs, treesizefs;
00084
00085 char c;
00086 while ((c = getopt(argc, argv, "A:a:Dd:F:EL:l:Oo:T:Pptvh")) != EOF)
00087 {
00088 switch(c)
00089 {
00090 case 'A': showAllTreeDepth = atoi(optarg);
00091 assert(showAllTreeDepth);
00092 break;
00093 case 'a': showTreeDepth = atoi(optarg);
00094 assert(showTreeDepth);
00095 break;
00096 case 'D': useDominanceRelation = true;
00097 break;
00098 case 'd': checkmate::CheckmateRecorder::DepthTracer::maxVerboseLogDepth
00099 = atoi(optarg);
00100 break;
00101 case 'E': showEscapeFilename = true;
00102 break;
00103 case 'F': FILES = optarg;
00104 break;
00105 case 'L': logThreshold = atoi(optarg);
00106 assert(logThreshold);
00107 break;
00108 case 'l': limit = atoi(optarg);
00109 assert(limit);
00110 break;
00111 case 'O': useOutlineFormat = true;
00112 break;
00113 case 'o': treefs.reset(new std::ofstream(optarg));
00114 treeOut = &*treefs;
00115 break;
00116 case 'P': useHeuristics = false;
00117 break;
00118 case 'p': showProofTree = true;
00119 break;
00120 case 't': force_attack = true;
00121 break;
00122 case 'T': treesizefs.reset(new std::ofstream(optarg));
00123 tree_size_out = &*treesizefs;
00124 break;
00125 case 'v': verbose = true;
00126 break;
00127 default: error_flag = true;
00128 }
00129 }
00130 argc -= optind;
00131 argv += optind;
00132
00133 if (error_flag || ((argc < 1) && (! FILES)))
00134 usage(program_name);
00135
00136 std::cerr << "limit " << limit << "\n";
00137 try
00138 {
00139 for (int i=0; i<argc; ++i)
00140 {
00141 searchFile(argv[i]);
00142 total_cycles = 0;
00143 }
00144 if (FILES)
00145 {
00146 std::ifstream is(FILES);
00147 std::string filename;
00148 size_t count=0;
00149 while (is >> filename)
00150 {
00151 if (tree_size_out && (++count % 512) == 0)
00152 *tree_size_out << std::flush;
00153 searchFile(filename.c_str());
00154 total_cycles = 0;
00155 }
00156 }
00157 std::cerr << "check " << num_checkmate << " escape " << num_escape
00158 << " unknown " << num_unkown << "\n";
00159 std::cerr << "total nodes " << total_nodes
00160 << " tables " << total_tables << "\n";
00161 }
00162 catch (std::exception& e)
00163 {
00164 std::cerr << e.what() << "\n";
00165 return 1;
00166 }
00167 }
00168
00169 void dumpTree(const CheckTableAnalyzer& analyzer,
00170 const CheckHashRecord *record)
00171 {
00172 if (! record)
00173 return;
00174 Move debug_move;
00175 for (CheckMoveList::const_iterator p=record->moves.begin(); p!=record->moves.end();
00176 ++p)
00177 {
00178 if (p->move == debug_move)
00179 {
00180 if (p->record)
00181 {
00182 p->record->dump();
00183 record = p->record;
00184 }
00185 break;
00186 }
00187 }
00188
00189 if (showAllTreeDepth)
00190 {
00191 analyzer.showTree(record,*treeOut,showAllTreeDepth,true,false,logThreshold);
00192 }
00193 if (showTreeDepth)
00194 {
00195 analyzer.showTree(record,*treeOut,showTreeDepth,false,false,logThreshold);
00196 }
00197 }
00198
00199 void searchFile(const char *filename)
00200 {
00201 if (useDominanceRelation)
00202 {
00203 if (useHeuristics)
00204 search<DominanceTable,LibertyEstimator,PieceCost>(filename);
00205 else
00206 search<DominanceTable,PureLibertyEstimator,NullCost>(filename);
00207 }
00208 else
00209 {
00210 if (useHeuristics)
00211 search<SimpleCheckHashTable,LibertyEstimator,PieceCost>(filename);
00212 else
00213 search<SimpleCheckHashTable,PureLibertyEstimator,NullCost>(filename);
00214 }
00215 }
00216
00220 void readCsaState(std::istream& is, SimpleState& state)
00221 {
00222 Record rec;
00223 record::csa::InputStream irs(is);
00224 irs.load(&rec);
00225 state = rec.getInitialState();
00226 }
00227
00228 double real_seconds = 0.0;
00229
00230 template <Player P, class Searcher>
00231 void testWinOrLose(const char *curFilename,
00232 Searcher& searcher,
00233 const SimpleState& sstate, int limit)
00234 {
00235 typedef typename Searcher::table_t table_t;
00236 HashEffectState state((NumEffectState(sstate)));
00237 const PathEncoding path(state.getTurn());
00238 const Position my_king = state.template getKingPosition<P>();
00239 if ((! force_attack)
00240 && ! my_king.isPieceStand() && state.hasEffectBy(alt(P), my_king))
00241 {
00242
00243 RealTime timer(0);
00244 misc::PerfMon clock;
00245 const bool lose
00246 = searcher.template isLosingState<P>(limit, state, state.getHash(), path);
00247 total_cycles += clock.stop();
00248 real_seconds = timer.getConsumedInDouble();
00249
00250 const HashKey& key = state.getHash();
00251 const table_t& table = searcher.getTable(alt(P));
00252 const CheckHashRecord *record = table.find(key);
00253 if (lose) {
00254 ++num_checkmate;
00255 }
00256 else {
00257 if (record->proofDisproof().isCheckmateFail()
00258 || record->findLoop(path, table.getTwinTable()))
00259 ++num_escape;
00260 else {
00261 assert(! record->proofDisproof().isFinal());
00262 ++num_unkown;
00263 }
00264 }
00265
00266 if (! verbose)
00267 return;
00268
00269 CheckTableAnalyzer analyzer(table.getTwinTable(), useOutlineFormat);
00270 dumpTree(analyzer, record);
00271 if (lose)
00272 {
00273 size_t leaf_size;
00274 const size_t tree_size
00275 = analyzer.proofTreeSize(record,key,path,false,leaf_size);
00276 ProofTreeDepth depth_analyzer;
00277 const unsigned int depth = depth_analyzer.depth(record, false);
00278 std::cerr << "lose\n";
00279 std::cerr << "proof tree " << tree_size
00280 << " leaf " << leaf_size
00281 << " depth " << depth << "\n";
00282 if (tree_size_out)
00283 {
00284 *tree_size_out << tree_size << " " << table.size() << "\n";
00285 }
00286 if (showProofTree)
00287 analyzer.showProofTree(record,key,path,false,*treeOut);
00288 return;
00289 }
00290 else
00291 {
00292 assert(record);
00293 if (showEscapeFilename)
00294 std::cerr << curFilename << "\n";
00295 if (record->proofDisproof().isCheckmateFail()
00296 || record->findLoop(path, table.getTwinTable()))
00297 {
00298 size_t leaf_size;
00299 const size_t tree_size
00300 = analyzer.disproofTreeSize(record,key,path,true, leaf_size);
00301 std::cerr << "escape\n";
00302 std::cerr << "disproof tree " << tree_size
00303 << " leaf " << leaf_size << "\n";
00304 if (tree_size_out)
00305 *tree_size_out << tree_size << " " << table.size() << "\n";
00306
00307 if (showProofTree)
00308 analyzer.showProofTree(record,key,path,true,*treeOut);
00309 return;
00310 }
00311 else
00312 {
00313 assert(! record->proofDisproof().isFinal());
00314 std::cerr << "unknown " << record->proofDisproof() << "\n";
00315 return;
00316 }
00317 }
00318 }
00319 else
00320 {
00321 Move checkmateMove;
00322 RealTime timer(0);
00323 PerfMon clock;
00324 AttackOracleAges age;
00325 const bool win = searcher.
00326 template isWinningState<P>(limit, state, state.getHash(), path, checkmateMove, age);
00327 total_cycles += clock.stop();
00328 real_seconds = timer.getConsumedInDouble();
00329 #if 0
00330 std::cerr << " done\n";
00331 #endif
00332 const HashKey& key = state.getHash();
00333 const table_t& table = searcher.getTable(P);
00334 const CheckHashRecord *record = table.find(state.getHash());
00335 if (win) {
00336 ++num_checkmate;
00337 }
00338 else {
00339 assert(record);
00340 if (record->proofDisproof().isFinal()
00341 || record->findLoop(path, table.getTwinTable()))
00342 ++num_escape;
00343 else
00344 ++num_unkown;
00345 }
00346 if (! verbose)
00347 return;
00348
00349 CheckTableAnalyzer analyzer(table.getTwinTable(), useOutlineFormat);
00350 if ((record->proofDisproof() != ProofDisproof::Checkmate())
00351 && (record->proofDisproof() != ProofDisproof::NoCheckmate()))
00352 std::cerr << record->proofDisproof() << "\n";
00353
00354 dumpTree(analyzer, record);
00355 if (win)
00356 {
00357 size_t leaf_size;
00358 const size_t tree_size = analyzer.proofTreeSize(record,key,path,true,
00359 leaf_size);
00360 ProofTreeDepth depth_analyzer;
00361 const unsigned int depth = depth_analyzer.depth(record, true);
00362 std::cerr << "win by " << checkmateMove << "\n";
00363 std::cerr << "proof tree " << tree_size
00364 << " leaf " << leaf_size
00365 << " depth " << depth << "\n";
00366 if (tree_size_out)
00367 *tree_size_out << tree_size << " " << table.size() << "\n";
00368 if (showProofTree)
00369 analyzer.showProofTree(record,key,path,true,*treeOut);
00370 return;
00371 }
00372 else
00373 {
00374 assert(record);
00375 if (record->proofDisproof().isFinal()
00376 || record->findLoop(path, table.getTwinTable()))
00377 {
00378 size_t leaf_size;
00379 const size_t tree_size
00380 = analyzer.disproofTreeSize(record,key,path,false, leaf_size);
00381 std::cerr << "no checkmate\n";
00382 std::cerr << "disproof tree " << tree_size
00383 << " leaf " << leaf_size << "\n";
00384 if (tree_size_out)
00385 *tree_size_out << tree_size << " " << table.size() << "\n";
00386 if (showProofTree)
00387 analyzer.showProofTree(record,key,path,false,*treeOut);
00388 return;
00389 }
00390 else
00391 {
00392 std::cerr << "unknown " << record->proofDisproof() << "\n";
00393 return;
00394 }
00395 }
00396 }
00397 }
00398
00399 template <class Table, class H, class Cost>
00400 void search(const char *filename)
00401 {
00402 std::ifstream is(filename);
00403 if (! is) {
00404 std::cerr << "\nskipping " << filename << "\n";
00405 return;
00406 }
00407 if (verbose)
00408 std::cerr << "\nsolving " << filename << "\n";
00409
00410 typedef DualCheckmateSearcher<Table, H, Cost> searcher_t;
00411 searcher_t searcher(std::max(limit, (size_t)20000000));
00412 searcher.setVerbose(verbose);
00413
00414 SimpleState state;
00415 readCsaState(is, state);
00416
00417 if (state.getTurn() == BLACK)
00418 testWinOrLose<BLACK,searcher_t>(filename, searcher, state, limit);
00419 else
00420 testWinOrLose<WHITE,searcher_t>(filename, searcher, state, limit);
00421
00422 const size_t table_used = searcher.getTable(BLACK).size()
00423 + searcher.getTable(WHITE).size();
00424
00425 total_nodes += searcher.totalNodeCount();
00426 total_tables += table_used;
00427
00428 if (verbose) {
00429 PerfMon::message(total_cycles, "total ",
00430 searcher.totalNodeCount());
00431 PerfMon::message(total_cycles, "unique", table_used);
00432 std::cerr << "real " << real_seconds << " sec.\n";
00433 }
00434 }
00435
00436
00437
00438
00439
00440
00441