00001
00021 #include "osl/search/quiescenceSearch.h"
00022 #include "osl/search/simpleHashTable.h"
00023 #include "osl/checkmate/dualCheckmateSearcher.h"
00024 #include "osl/state/hashEffectState.h"
00025 #include "osl/record/csaString.h"
00026 #include "osl/record/csaRecord.h"
00027 #include "osl/eval/progressEval.h"
00028 #include "osl/apply_move/applyMove.h"
00029 #include "osl/stat/average.h"
00030
00031 #include "osl/stl/slist.h"
00032 #include <iostream>
00033 #include <cstdio>
00034 #include <fstream>
00035 #include <cstdlib>
00036
00037 using namespace osl;
00038 using namespace osl::search;
00039 using namespace osl::misc;
00040
00041 void qsearch(const char *filename);
00042
00043 void usage(const char *program_name)
00044 {
00045 std::cerr << program_name << " [-d depth] [-s skip] [-v] csafiles\n";
00046 exit(1);
00047 }
00048
00049 int record_depth = -6;
00050 bool verbose = false;
00051 size_t skip_first = 0;
00052 int center = 0;
00053
00054 int main(int argc, char **argv)
00055 {
00056 const char *program_name = argv[0];
00057 bool error_flag = false;
00058
00059 extern char *optarg;
00060 extern int optind;
00061 char c;
00062 while ((c = getopt(argc, argv, "c:d:s:vh")) != EOF)
00063 {
00064 switch(c)
00065 {
00066 case 'c': center = atoi(optarg);
00067 break;
00068 case 'd': record_depth = atoi(optarg);
00069 break;
00070 case 's': skip_first = atoi(optarg);
00071 break;
00072 case 'v': verbose = true;
00073 break;
00074 default: error_flag = true;
00075 }
00076 }
00077 argc -= optind;
00078 argv += optind;
00079
00080 if (error_flag || (argc < 1))
00081 usage(program_name);
00082
00083 std::cerr << "using table record depth " << record_depth << "\n";
00084 try
00085 {
00086 for (int i=0; i<argc; ++i)
00087 {
00088 qsearch(argv[i]);
00089 }
00090 }
00091 catch (std::exception& e)
00092 {
00093 std::cerr << e.what() << "\n";
00094 return 1;
00095 }
00096 catch (...)
00097 {
00098 throw;
00099 }
00100 }
00101
00102 typedef DualCheckmateSearcher<> checkmate_t;
00103 typedef QuiescenceSearch<eval::ProgressEval> qsearch_t;
00104 typedef qsearch_t::eval_t eval_t;
00105
00106 class Searcher
00107 {
00108 protected:
00109 stat::Average width, nodes, diff, accuracy;
00110 qsearch_t **searcher;
00111 const eval_t& eval;
00112 public:
00113 Searcher(qsearch_t **q, const eval_t& e) : searcher(q), eval(e)
00114 {
00115 }
00116 virtual ~Searcher()
00117 {
00118 }
00119 virtual const std::string name() const=0;
00120 virtual const std::pair<int,int> alphaBeta(Player turn,
00121 int pawn_value, int real_value) const=0;
00125 virtual int search(Player turn, int pawn_value, int real_value,
00126 Move last_move)=0;
00127 protected:
00128 const std::pair<int,int>
00129 count(Player turn, int alpha, int beta, Move last_move)
00130 {
00131 width.add(abs(alpha-beta));
00132 alpha = eval::max(turn, alpha, FixedEval::winThreshold(alt(turn)));
00133 beta = eval::max(alt(turn), beta, FixedEval::winThreshold(turn));
00134 const int before = (*searcher)->nodeCount();
00135 int result;
00136 if (turn == BLACK)
00137 result = (*searcher)->search<BLACK>(alpha, beta, eval, last_move);
00138 else
00139 result = (*searcher)->search<WHITE>(alpha, beta, eval, last_move);
00140 const int after = (*searcher)->nodeCount();
00141 return std::make_pair(after - before, result);
00142 }
00143 public:
00144 void report() const
00145 {
00146 const std::string n = name();
00147 fprintf(stderr, "%s\t%8.3f\t%8.3f\t%10.3f\t%8.3f\n",
00148 n.c_str(), width.getAverage(), nodes.getAverage(),
00149 diff.getAverage(), accuracy.getAverage());
00150 };
00151 };
00152
00153 class NormalSearcher : public Searcher
00154 {
00155 public:
00156 NormalSearcher(qsearch_t **q, const eval_t& e) : Searcher(q,e)
00157 {
00158 }
00162 int search(Player turn, int pawn_value, int real_value,
00163 Move last_move)
00164 {
00165 const std::pair<int,int> alpha_beta = alphaBeta(turn, pawn_value, real_value);
00166 const std::pair<int,int> node_result
00167 = count(turn, alpha_beta.first, alpha_beta.second, last_move);
00168
00169 nodes.add(node_result.first);
00170 diff.add(abs(real_value - node_result.second));
00171 accuracy.add(real_value == node_result.second);
00172 return node_result.second;
00173 }
00174 };
00175
00176 class FullWidth : public NormalSearcher
00177 {
00178 public:
00179 FullWidth(qsearch_t **q, const eval_t& e) : NormalSearcher(q, e)
00180 {
00181 }
00182 const std::string name() const { return "full width"; }
00183 const std::pair<int,int> alphaBeta(Player turn, int , int ) const
00184 {
00185 const int alpha = FixedEval::winThreshold(alt(turn));
00186 const int beta = FixedEval::winThreshold(turn);
00187 return std::make_pair(alpha, beta);
00188 }
00189 };
00190
00194 class FixedRange : public NormalSearcher
00195 {
00196 protected:
00197 int divider;
00198 public:
00199 FixedRange(qsearch_t **q, const eval_t& e, int d) : NormalSearcher(q,e), divider(d)
00200 {
00201 }
00202 virtual int center(int real_value) const=0;
00203 int halfRange(int pawn_value) const
00204 {
00205 return pawn_value/divider;
00206 }
00207 const std::pair<int,int> alphaBeta(Player turn, int pawn_value, int real_value) const
00208 {
00209 const int center=this->center(real_value);
00210 const int half_range=halfRange(pawn_value);
00211 const int alpha = center - half_range + eval::delta(turn);
00212 const int beta = center + half_range - eval::delta(turn);
00213 return std::make_pair(alpha, beta);
00214 }
00215 };
00216
00217 const std::string tos(int val)
00218 {
00219 assert(val < 100);
00220 assert(val >= 0);
00221 std::string result = "00";
00222 sprintf(&result[0], "%d", val);
00223 return result;
00224 }
00225
00226 class FixedCenter : public FixedRange
00227 {
00228 protected:
00229 const int center_value;
00230 public:
00231 FixedCenter(qsearch_t **q, const eval_t& e, int d, int c)
00232 : FixedRange(q, e, d), center_value(c)
00233 {
00234 }
00235 int center(int ) const
00236 {
00237 return center_value;
00238 }
00239 const std::string name() const {
00240 return "fixedcenter" + tos(center_value) +"/"+ tos(divider);
00241 }
00242 };
00243
00244 class AccurateCenter : public FixedRange
00245 {
00246 public:
00247 AccurateCenter(qsearch_t **q, const eval_t& e, int d)
00248 : FixedRange(q, e, d)
00249 {
00250 }
00251 int center(int real_value) const { return real_value; }
00252 const std::string name() const {
00253 return "acc_center" + tos(divider);
00254 }
00255 };
00256
00257 class RootCenter : public FixedRange
00258 {
00259 public:
00260 RootCenter(qsearch_t **q, const eval_t& e, int d)
00261 : FixedRange(q, e, d)
00262 {
00263 }
00264 int center(int ) const { return eval.value(); }
00265 const std::string name() const {
00266 return "root_center" + tos(divider);
00267 }
00268 };
00269
00273 class ExtendToCenter : public FixedCenter
00274 {
00275 const int extend_multiplier;
00276 public:
00277 ExtendToCenter(qsearch_t **q, const eval_t& e, int range_d, int c,
00278 int extend_m)
00279 : FixedCenter(q, e, range_d, c), extend_multiplier(extend_m)
00280 {
00281 }
00282 const std::string name() const {
00283 return "extend2c" + tos(divider) + tos(extend_multiplier);
00284 }
00285 const std::pair<int,int> alphaBeta(Player turn, int pawn_value, int real_value) const
00286 {
00287 const int root_value = eval.value();
00288 const int extend_range = pawn_value * extend_multiplier;
00289 const std::pair<int,int> alpha_beta
00290 = FixedCenter::alphaBeta(turn, pawn_value, real_value);
00291 const int delta = eval::delta(turn);
00292 int alpha = alpha_beta.first;
00293 int beta = alpha_beta.second;
00294
00295 if (eval::betterThan(turn, center(real_value), root_value))
00296 {
00297 alpha = eval::min(turn, root_value+extend_range-delta, alpha);
00298 }
00299 else
00300 {
00301 beta = eval::max(turn, root_value-extend_range+delta, beta);
00302 }
00303 return std::make_pair(alpha, beta);
00304 }
00305 };
00306
00311 class ExtendToCenterModest : public FixedCenter
00312 {
00313 const int extend_multiplier;
00314 public:
00315 ExtendToCenterModest(qsearch_t **q, const eval_t& e, int range_d, int c,
00316 int extend_m)
00317 : FixedCenter(q, e, range_d, c), extend_multiplier(extend_m)
00318 {
00319 }
00320 const std::string name() const {
00321 return "extend2cm" + tos(divider) + tos(extend_multiplier);
00322 }
00323 const std::pair<int,int> alphaBeta(Player turn, int pawn_value, int real_value) const
00324 {
00325 const int root_value = eval.value();
00326 const int extend_range = pawn_value * extend_multiplier;
00327 const int center=this->center(real_value);
00328 const int half_range=halfRange(pawn_value);
00329 const int delta = eval::delta(turn);
00330
00331 int alpha = center - half_range - delta;
00332 int beta = center + half_range + delta;
00333 if (eval::betterThan(turn, center, root_value))
00334 {
00335 alpha = eval::min(turn, root_value+extend_range-delta,
00336 center - half_range/2 - delta);
00337 }
00338 else
00339 {
00340 beta = eval::max(turn, root_value-extend_range+delta,
00341 center + half_range/2 + delta);
00342 }
00343 return std::make_pair(alpha, beta);
00344 }
00345 };
00346
00350 class ExtendToOther : public FixedCenter
00351 {
00352 static const int extend_multiplier=2;
00353 public:
00354 ExtendToOther(qsearch_t **q, const eval_t& e, int range_d, int c)
00355 : FixedCenter(q, e, range_d, c)
00356 {
00357 }
00358 const std::string name() const {
00359 return "extend2o" + tos(divider) + tos(extend_multiplier);
00360 }
00361 const std::pair<int,int> alphaBeta(Player turn, int pawn_value, int real_value) const
00362 {
00363 const int root_value = eval.value();
00364 const int center=this->center(real_value);
00365 const int half_range=halfRange(pawn_value);
00366
00367 int alpha = center - half_range - eval::delta(turn);
00368 int beta = center + half_range + eval::delta(turn);
00369 if (eval::betterThan(turn, center, root_value))
00370 {
00371 beta = center + half_range*extend_multiplier + eval::delta(turn);
00372 }
00373 else
00374 {
00375 alpha = center - half_range*extend_multiplier - eval::delta(turn);
00376 }
00377 return std::make_pair(alpha, beta);
00378 }
00379 };
00380
00381 class Analyzer
00382 {
00383 size_t records;
00384 HashEffectState state;
00385 eval_t ev;
00386 checkmate_t checkmate;
00387 SimpleHashTable table;
00388 qsearch_t *qs;
00389 FullWidth full_searcher;
00390 typedef slist<Searcher*> list_t;
00391 list_t searchers;
00392 public:
00393 Analyzer() : records(0), state(SimpleState(HIRATE)), ev(state),
00394 table(100000,record_depth,verbose),
00395 full_searcher(&qs, ev)
00396 {
00397 searchers.push_front(new AccurateCenter(&qs, ev, 2));
00398 searchers.push_front(new AccurateCenter(&qs, ev, 4));
00399 searchers.push_front(new RootCenter(&qs, ev, 2));
00400 searchers.push_front(new RootCenter(&qs, ev, 4));
00401 searchers.push_front(new RootCenter(&qs, ev, 8));
00402 searchers.push_front(new RootCenter(&qs, ev, 16));
00403
00404 searchers.push_front(new FixedCenter(&qs, ev, 2, center));
00405 #if 0
00406 searchers.push_front(new ExtendToCenter(&qs, ev, 2, center, 4));
00407 searchers.push_front(new ExtendToCenterModest(&qs, ev, 2, center, 4));
00408 searchers.push_front(new ExtendToCenter(&qs, ev, 2, center, 8));
00409 searchers.push_front(new ExtendToCenterModest(&qs, ev, 2, center, 8));
00410 searchers.push_front(new ExtendToOther(&qs, ev, 2, center));
00411 #endif
00412 searchers.push_front(new FixedCenter(&qs, ev, 4, center));
00413 #if 0
00414 searchers.push_front(new ExtendToCenter(&qs, ev, 4, center, 4));
00415 searchers.push_front(new ExtendToCenterModest(&qs, ev, 4, center, 4));
00416 #endif
00417 searchers.push_front(new ExtendToCenter(&qs, ev, 4, center, 6));
00418 searchers.push_front(new ExtendToCenterModest(&qs, ev, 4, center, 6));
00419 #if 0
00420 searchers.push_front(new ExtendToCenter(&qs, ev, 4, center, 8));
00421 searchers.push_front(new ExtendToCenterModest(&qs, ev, 4, center, 8));
00422 searchers.push_front(new ExtendToOther(&qs, ev, 4, center));
00423 #endif
00424 searchers.push_front(new FixedCenter(&qs, ev, 8, center));
00425 searchers.push_front(new ExtendToCenter(&qs, ev, 8, center, 4));
00426 searchers.push_front(new ExtendToCenterModest(&qs, ev, 8, center, 4));
00427 #if 0
00428 searchers.push_front(new ExtendToCenter(&qs, ev, 8, center, 6));
00429 searchers.push_front(new ExtendToCenterModest(&qs, ev, 8, center, 6));
00430 searchers.push_front(new ExtendToCenter(&qs, ev, 8, center, 8));
00431 searchers.push_front(new ExtendToCenterModest(&qs, ev, 8, center, 8));
00432 searchers.push_front(new ExtendToOther(&qs, ev, 8, center));
00433 #endif
00434 searchers.reverse();
00435 }
00436 void report() const
00437 {
00438 std::cerr << "\nrecords " << records << "\n";
00439 full_searcher.report();
00440 for (list_t::const_iterator p=searchers.begin(); p!=searchers.end(); ++p)
00441 {
00442 (*p)->report();
00443 }
00444 }
00445 void search(size_t i, Move last_move)
00446 {
00447 SearchStateCore core(state, checkmate);
00448 qsearch_t searcher(core, table);
00449 qs = &searcher;
00450 const Player turn = state.getTurn();
00451 const int pawn_value
00452 = qsearch_t::eval_t::captureValue(newPtypeO(alt(turn),PAWN));
00453 if (verbose)
00454 std::cerr << i << " " << record::csa::show(last_move) << "\n";
00455
00456 table.clear();
00457 const int real_value_dummy = 0;
00458 const int real_value
00459 = full_searcher.search(turn, pawn_value, real_value_dummy, last_move);
00460
00461 for (list_t::iterator p=searchers.begin(); p!=searchers.end(); ++p)
00462 {
00463 table.clear();
00464 (*p)->search(turn, pawn_value, real_value, last_move);
00465 }
00466 }
00467 void search(const char *filename)
00468 {
00469 Record rec=CsaFile(filename).getRecord();
00470 state = HashEffectState(rec.getInitialState());
00471 ev = eval_t(state);
00472 const vector<osl::Move> moves=rec.getMoves();
00473 size_t i=0;
00474 while (true)
00475 {
00476 if (i >= skip_first)
00477 {
00478 const Move last_move
00479 = (i > 0) ? moves[i-1] : Move::PASS(alt(moves[0].player()));
00480 search(i, last_move);
00481 }
00482 if (i >= moves.size())
00483 break;
00484 const Move move = moves[i++];
00485 ApplyMoveOfTurn::doMove(state, move);
00486 ev.update(state, move);
00487 }
00488 ++records;
00489 report();
00490 }
00491 };
00492
00493 Analyzer analyzer;
00494
00495 void qsearch(const char *filename)
00496 {
00497 analyzer.search(filename);
00498 }
00499
00500
00501
00502
00503
00504