All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
range-vs-nodes.cc
Go to the documentation of this file.
1 
24 #include "osl/checkmate/dualDfpn.h"
26 #include "osl/record/csaString.h"
27 #include "osl/record/csaRecord.h"
28 #include "osl/eval/progressEval.h"
29 #include "osl/stat/average.h"
30 
31 #include "osl/stl/slist.h"
32 #include <iostream>
33 #include <cstdio>
34 #include <fstream>
35 #include <cstdlib>
36 
37 using namespace osl;
38 using namespace osl::search;
39 using namespace osl::misc;
40 
41 void qsearch(const char *filename);
42 
43 void usage(const char *program_name)
44 {
45  std::cerr << program_name << " [-d depth] [-s skip] [-v] csafiles\n";
46  exit(1);
47 }
48 
49 int record_depth = -6;
50 bool verbose = false;
51 size_t skip_first = 0;
52 int center = 0;
53 
54 int main(int argc, char **argv)
55 {
56  const char *program_name = argv[0];
57  bool error_flag = false;
58 
59  extern char *optarg;
60  extern int optind;
61  char c;
62  while ((c = getopt(argc, argv, "c:d:s:vh")) != EOF)
63  {
64  switch(c)
65  {
66  case 'c': center = atoi(optarg);
67  break;
68  case 'd': record_depth = atoi(optarg);
69  break;
70  case 's': skip_first = atoi(optarg);
71  break;
72  case 'v': verbose = true;
73  break;
74  default: error_flag = true;
75  }
76  }
77  argc -= optind;
78  argv += optind;
79 
80  if (error_flag || (argc < 1))
81  usage(program_name);
82 
83  std::cerr << "using table record depth " << record_depth << "\n";
84  try
85  {
86  for (int i=0; i<argc; ++i)
87  {
88  qsearch(argv[i]);
89  }
90  }
91  catch (std::exception& e)
92  {
93  std::cerr << e.what() << "\n";
94  return 1;
95  }
96  catch (...)
97  {
98  throw;
99  }
100 }
101 
105 
106 class Searcher
107 {
108 protected:
109  stat::Average width, nodes, diff, accuracy;
112 public:
113  Searcher(qsearch_t **q, eval_t& e) : searcher(q), eval(e)
114  {
115  }
116  virtual ~Searcher()
117  {
118  }
119  virtual const std::string name() const=0;
120  virtual const std::pair<int,int> alphaBeta(Player turn,
121  int pawn_value, int real_value) const=0;
125  virtual int search(Player turn, int pawn_value, int real_value,
126  Move last_move)=0;
127 protected:
128  const std::pair<int,int>
129  count(Player turn, int alpha, int beta, Move last_move)
130  {
131  width.add(abs(alpha-beta));
132  alpha = eval::max(turn, alpha, FixedEval::winThreshold(alt(turn)));
133  beta = eval::max(alt(turn), beta, FixedEval::winThreshold(turn));
134  const int before = (*searcher)->nodeCount();
135  int result;
136  if (turn == BLACK)
137  result = (*searcher)->search<BLACK>(alpha, beta, eval, last_move);
138  else
139  result = (*searcher)->search<WHITE>(alpha, beta, eval, last_move);
140  const int after = (*searcher)->nodeCount();
141  return std::make_pair(after - before, result);
142  }
143 public:
144  void report() const
145  {
146  const std::string n = name();
147  fprintf(stderr, "%s\t%8.3f\t%8.3f\t%10.3f\t%8.3f\n",
148  n.c_str(), width.getAverage(), nodes.getAverage(),
149  diff.getAverage(), accuracy.getAverage());
150  };
151 };
152 
153 class NormalSearcher : public Searcher
154 {
155 public:
157  {
158  }
162  int search(Player turn, int pawn_value, int real_value,
163  Move last_move)
164  {
165  const std::pair<int,int> alpha_beta = alphaBeta(turn, pawn_value, real_value);
166  const std::pair<int,int> node_result
167  = count(turn, alpha_beta.first, alpha_beta.second, last_move);
168 
169  nodes.add(node_result.first);
170  diff.add(abs(real_value - node_result.second));
171  accuracy.add(real_value == node_result.second);
172  return node_result.second;
173  }
174 };
175 
176 class FullWidth : public NormalSearcher
177 {
178 public:
180  {
181  }
182  const std::string name() const { return "full width"; }
183  const std::pair<int,int> alphaBeta(Player turn, int /*pawn_value*/, int /*real_value*/) const
184  {
185  const int alpha = FixedEval::winThreshold(alt(turn));
186  const int beta = FixedEval::winThreshold(turn);
187  return std::make_pair(alpha, beta);
188  }
189 };
190 
195 {
196 protected:
197  int divider;
198 public:
199  FixedRange(qsearch_t **q, eval_t& e, int d) : NormalSearcher(q,e), divider(d)
200  {
201  }
202  virtual int center(int real_value) const=0;
203  int halfRange(int pawn_value) const
204  {
205  return pawn_value/divider;
206  }
207  const std::pair<int,int> alphaBeta(Player turn, int pawn_value, int real_value) const
208  {
209  const int center=this->center(real_value);
210  const int half_range=halfRange(pawn_value);
211  const int alpha = center - half_range + eval::delta(turn);
212  const int beta = center + half_range - eval::delta(turn);
213  return std::make_pair(alpha, beta);
214  }
215 };
216 
217 const std::string tos(int val)
218 {
219  assert(val < 100);
220  assert(val >= 0);
221  std::string result = "00";
222  sprintf(&result[0], "%d", val);
223  return result;
224 }
225 
226 class FixedCenter : public FixedRange
227 {
228 protected:
229  const int center_value;
230 public:
231  FixedCenter(qsearch_t **q, eval_t& e, int d, int c)
232  : FixedRange(q, e, d), center_value(c)
233  {
234  }
235  int center(int /*real_value*/) const
236  {
237  return center_value;
238  }
239  const std::string name() const {
240  return "fixedcenter" + tos(center_value) +"/"+ tos(divider);
241  }
242 };
243 
245 {
246 public:
248  : FixedRange(q, e, d)
249  {
250  }
251  int center(int real_value) const { return real_value; }
252  const std::string name() const {
253  return "acc_center" + tos(divider);
254  }
255 };
256 
257 class RootCenter : public FixedRange
258 {
259 public:
260  RootCenter(qsearch_t **q, eval_t& e, int d)
261  : FixedRange(q, e, d)
262  {
263  }
264  int center(int /*real_value*/) const { return eval.value(); }
265  const std::string name() const {
266  return "root_center" + tos(divider);
267  }
268 };
269 
274 {
275  const int extend_multiplier;
276 public:
277  ExtendToCenter(qsearch_t **q, eval_t& e, int range_d, int c,
278  int extend_m)
279  : FixedCenter(q, e, range_d, c), extend_multiplier(extend_m)
280  {
281  }
282  const std::string name() const {
283  return "extend2c" + tos(divider) + tos(extend_multiplier);
284  }
285  const std::pair<int,int> alphaBeta(Player turn, int pawn_value, int real_value) const
286  {
287  const int root_value = eval.value();
288  const int extend_range = pawn_value * extend_multiplier;
289  const std::pair<int,int> alpha_beta
290  = FixedCenter::alphaBeta(turn, pawn_value, real_value);
291  const int delta = eval::delta(turn);
292  int alpha = alpha_beta.first;
293  int beta = alpha_beta.second;
294 
295  if (eval::betterThan(turn, center(real_value), root_value))
296  {
297  alpha = eval::min(turn, root_value+extend_range-delta, alpha);
298  }
299  else
300  {
301  beta = eval::max(turn, root_value-extend_range+delta, beta);
302  }
303  return std::make_pair(alpha, beta);
304  }
305 };
306 
312 {
313  const int extend_multiplier;
314 public:
315  ExtendToCenterModest(qsearch_t **q, eval_t& e, int range_d, int c,
316  int extend_m)
317  : FixedCenter(q, e, range_d, c), extend_multiplier(extend_m)
318  {
319  }
320  const std::string name() const {
321  return "extend2cm" + tos(divider) + tos(extend_multiplier);
322  }
323  const std::pair<int,int> alphaBeta(Player turn, int pawn_value, int real_value) const
324  {
325  const int root_value = eval.value();
326  const int extend_range = pawn_value * extend_multiplier;
327  const int center=this->center(real_value);
328  const int half_range=halfRange(pawn_value);
329  const int delta = eval::delta(turn);
330 
331  int alpha = center - half_range - delta;
332  int beta = center + half_range + delta;
333  if (eval::betterThan(turn, center, root_value))
334  {
335  alpha = eval::min(turn, root_value+extend_range-delta,
336  center - half_range/2 - delta);
337  }
338  else
339  {
340  beta = eval::max(turn, root_value-extend_range+delta,
341  center + half_range/2 + delta);
342  }
343  return std::make_pair(alpha, beta);
344  }
345 };
346 
351 {
352  static const int extend_multiplier=2;
353 public:
354  ExtendToOther(qsearch_t **q, eval_t& e, int range_d, int c)
355  : FixedCenter(q, e, range_d, c)
356  {
357  }
358  const std::string name() const {
359  return "extend2o" + tos(divider) + tos(extend_multiplier);
360  }
361  const std::pair<int,int> alphaBeta(Player turn, int pawn_value, int real_value) const
362  {
363  const int root_value = eval.value();
364  const int center=this->center(real_value);
365  const int half_range=halfRange(pawn_value);
366 
367  int alpha = center - half_range - eval::delta(turn);
368  int beta = center + half_range + eval::delta(turn);
369  if (eval::betterThan(turn, center, root_value))
370  {
371  beta = center + half_range*extend_multiplier + eval::delta(turn);
372  }
373  else
374  {
375  alpha = center - half_range*extend_multiplier - eval::delta(turn);
376  }
377  return std::make_pair(alpha, beta);
378  }
379 };
380 
381 class Analyzer
382 {
383  size_t records;
384  NumEffectState state;
390  typedef slist<Searcher*> list_t;
392 public:
393  Analyzer() : records(0), state(SimpleState(HIRATE)), ev(state),
394  table(100000,record_depth,verbose),
395  full_searcher(&qs, ev)
396  {
397  searchers.push_front(new AccurateCenter(&qs, ev, 2));
398  searchers.push_front(new AccurateCenter(&qs, ev, 4));
399  searchers.push_front(new RootCenter(&qs, ev, 2));
400  searchers.push_front(new RootCenter(&qs, ev, 4));
401  searchers.push_front(new RootCenter(&qs, ev, 8));
402  searchers.push_front(new RootCenter(&qs, ev, 16));
403 
404  searchers.push_front(new FixedCenter(&qs, ev, 2, center));
405 #if 0
406  searchers.push_front(new ExtendToCenter(&qs, ev, 2, center, 4));
407  searchers.push_front(new ExtendToCenterModest(&qs, ev, 2, center, 4));
408  searchers.push_front(new ExtendToCenter(&qs, ev, 2, center, 8));
409  searchers.push_front(new ExtendToCenterModest(&qs, ev, 2, center, 8));
410  searchers.push_front(new ExtendToOther(&qs, ev, 2, center));
411 #endif
412  searchers.push_front(new FixedCenter(&qs, ev, 4, center));
413 #if 0
414  searchers.push_front(new ExtendToCenter(&qs, ev, 4, center, 4));
415  searchers.push_front(new ExtendToCenterModest(&qs, ev, 4, center, 4));
416 #endif
417  searchers.push_front(new ExtendToCenter(&qs, ev, 4, center, 6));
418  searchers.push_front(new ExtendToCenterModest(&qs, ev, 4, center, 6));
419 #if 0
420  searchers.push_front(new ExtendToCenter(&qs, ev, 4, center, 8));
421  searchers.push_front(new ExtendToCenterModest(&qs, ev, 4, center, 8));
422  searchers.push_front(new ExtendToOther(&qs, ev, 4, center));
423 #endif
424  searchers.push_front(new FixedCenter(&qs, ev, 8, center));
425  searchers.push_front(new ExtendToCenter(&qs, ev, 8, center, 4));
426  searchers.push_front(new ExtendToCenterModest(&qs, ev, 8, center, 4));
427 #if 0
428  searchers.push_front(new ExtendToCenter(&qs, ev, 8, center, 6));
429  searchers.push_front(new ExtendToCenterModest(&qs, ev, 8, center, 6));
430  searchers.push_front(new ExtendToCenter(&qs, ev, 8, center, 8));
431  searchers.push_front(new ExtendToCenterModest(&qs, ev, 8, center, 8));
432  searchers.push_front(new ExtendToOther(&qs, ev, 8, center));
433 #endif
434  searchers.reverse();
435  }
436  void report() const
437  {
438  std::cerr << "\nrecords " << records << "\n";
439  full_searcher.report();
440  for (list_t::const_iterator p=searchers.begin(); p!=searchers.end(); ++p)
441  {
442  (*p)->report();
443  }
444  }
445  void search(size_t i, Move last_move)
446  {
447  SearchState2Core core(state, checkmate);
448  qsearch_t searcher(core, table);
449  qs = &searcher;
450  const Player turn = state.turn();
451  const int pawn_value
452  = qsearch_t::eval_t::captureValue(newPtypeO(alt(turn),PAWN));
453  if (verbose)
454  std::cerr << i << " " << record::csa::show(last_move) << "\n";
455 
456  table.clear();
457  const int real_value_dummy = 0;
458  const int real_value
459  = full_searcher.search(turn, pawn_value, real_value_dummy, last_move);
460 
461  for (list_t::iterator p=searchers.begin(); p!=searchers.end(); ++p)
462  {
463  table.clear();
464  (*p)->search(turn, pawn_value, real_value, last_move);
465  }
466  }
467  void search(const char *filename)
468  {
469  Record rec=CsaFile(filename).getRecord();
470  state = NumEffectState(rec.getInitialState());
471  ev = eval_t(state);
472  const vector<osl::Move> moves=rec.getMoves();
473  size_t i=0;
474  while (true)
475  {
476  if (i >= skip_first)
477  {
478  const Move last_move
479  = (i > 0) ? moves[i-1] : Move::PASS(alt(moves[0].player()));
480  search(i, last_move);
481  }
482  if (i >= moves.size())
483  break;
484  const Move move = moves[i++];
485  state.makeMove(move);
486  ev.update(state, move);
487  }
488  ++records;
489  report();
490  }
491 };
492 
494 
495 void qsearch(const char *filename)
496 {
497  analyzer.search(filename);
498 }
499 
500 /* ------------------------------------------------------------------------- */
501 // ;;; Local Variables:
502 // ;;; mode:c++
503 // ;;; c-basic-offset:2
504 // ;;; End: