bradleyTerry.cc
Go to the documentation of this file.
1 /* bradleyTerry.cc
2  */
4 #include "osl/rating/group.h"
6 #include "osl/record/kisen.h"
7 
8 #include <thread>
9 #include <iostream>
10 #include <iomanip>
11 
12 #ifndef MINIMAL
14 BradleyTerry::BradleyTerry(FeatureSet& f, const std::string& kisen_file, int kisen_start)
15  : features(f), kisen_filename(kisen_file), kisen_start(kisen_start), num_cpus(1), num_records(200),
16  verbose(1), fix_group(-1), min_rating(0)
17 {
18 }
19 
21 {
22 }
23 
24 bool osl::rating::
25 BradleyTerry::addSquare(size_t g, const NumEffectState& state,
26  const RatingEnv& env, Move selected,
27  valarray_t& wins, std::valarray<long double>& denominator) const
28 {
29  MoveVector moves;
30  state.generateLegal(moves);
31  if (! moves.isMember(selected))
32  return false; // checkmate or illegal move
33  const range_t range = features.range(g);
34 #ifdef SPEEDUP_TEST
35  const bool in_check = EffectUtil::isKingInCheck(state.turn(), state);
36  if (! in_check || features.effectiveInCheck(g))
37 #endif
38  {
39  int found = features.group(g).findMatch(state, selected, env);
40  if (found >= 0)
41  ++wins[found+range.first];
42  }
43  valarray_t sum_c(0.0, range.second-range.first);
44  long double sum_e = 0.0;
45  for (size_t i=0; i<moves.size(); ++i) {
46  Move m = moves[i];
47  double product = 1.0;
48  int count = 0;
49  int match_id = -1;
50  for (size_t j=0; j<features.groupSize(); ++j) {
51 #ifdef SPEEDUP_TEST
52  if (in_check && ! features.effectiveInCheck(j))
53  continue;
54 #endif
55  int found = features.group(j).findMatch(state, m, env);
56  if (found < 0)
57  continue;
58  found += features.range(j).first;
59  product *= features.weight(found);
60  ++count;
61  if (j == g) {
62  assert(range.first <= found && found < range.second);
63  match_id = found;
64  }
65  }
66  assert(count);
67  sum_e += product;
68  if (match_id >= 0)
69  sum_c[match_id-range.first] += product / features.weight(match_id);
70  }
71  assert(sum_e > 0);
72  for (int f=range.first; f<range.second; ++f)
73  denominator[f] += sum_c[f-range.first]/sum_e;
74  return true;
75 }
76 
77 class osl::rating::
79 {
80 public:
82  size_t target;
83  size_t first, last;
85  std::valarray<long double> *denominator;
86  size_t *skip;
87  Thread(const BradleyTerry *a, size_t t, size_t f, size_t l, valarray_t *w, std::valarray<long double> *d,
88  size_t *s)
89  : features(a), target(t), first(f), last(l), wins(w), denominator(d), skip(s)
90  {
91  }
92  void operator()()
93  {
94  *skip = features->accumulate(target, first, last, *wins, *denominator);
95  }
96 };
97 
98 size_t osl::rating::
99 BradleyTerry::accumulate(size_t g, size_t first, size_t last, valarray_t& wins, std::valarray<long double>& denominator) const
100 {
101  assert(wins.size() == features.featureSize());
102  KisenFile kisen_file(kisen_filename.c_str());
104  size_t skip = 0;
105  for (size_t i=first; i<last; i++) {
106  if ((i % 4000) == 0)
107  std::cerr << ".";
108  if (ipx.rating(i, BLACK) < min_rating
109  || ipx.rating(i, WHITE) < min_rating) {
110  ++skip;
111  continue;
112  }
113  NumEffectState state(kisen_file.initialState());
114  RatingEnv env;
115  env.make(state);
116  const auto moves=kisen_file.moves(i+kisen_start);
117  for (size_t j=0; j<moves.size(); j++) {
118  if (j<2)
119  goto next;
120  {
121  const Player turn = state.turn();
122  if (! state.inCheck()
123  && ImmediateCheckmate::hasCheckmateMove(turn, state))
124  break;
125  }
126  if (! addSquare(g, state, env, moves[j], wins, denominator))
127  break;
128  next:
129  state.makeMove(moves[j]);
130  env.update(state, moves[j]);
131  }
132  }
133  return skip;
134 }
135 
136 void osl::rating::
138 {
139  std::valarray<valarray_t> wins(valarray_t(0.0, features.featureSize()), num_cpus);
140  std::valarray<std::valarray<long double> > denominator(std::valarray<long double>(0.0, features.featureSize()), num_cpus);
141  assert(wins.size() == num_cpus);
142 
143  KisenFile kisen_file(kisen_filename.c_str());
144  if (num_records==0)
145  num_records=kisen_file.size();
146  if (num_cpus == 1) {
147  accumulate(g, 0, num_records, wins[0], denominator[0]);
148  }
149  else {
150  size_t cur = 0;
151  size_t last = num_records, step = (last - cur)/num_cpus;
152  boost::ptr_vector<std::thread> threads;
153  std::valarray<size_t> skip((size_t)0, num_cpus);
154  for (size_t i=0; i<num_cpus; ++i, cur += step) {
155  size_t next = (i+1 == num_cpus) ? last : cur + step;
156  threads.push_back(new std::thread(Thread(this, g, cur, next, &wins[i], &denominator[i], &skip[i])));
157  }
158  for (size_t i=0; i<num_cpus; ++i)
159  threads[i].join();
160  if (g == 0)
161  std::cerr << "skip " << skip.sum() << " / " << num_records << "\n";
162  }
163  const range_t range = features.range(g);
164  for (int f=range.first; f<range.second; ++f) {
165  const int NPRIOR = 10; // assume NPRIOR wins, NPRIOR losses
166  double sum_win = NPRIOR;
167  long double sum_denom = (1.0 / (features.weight(f) + 1.0)) * 2 * NPRIOR;
168  for (size_t i=0; i<num_cpus; ++i) {
169  sum_win += wins[i][f];
170  sum_denom += denominator[i][f];
171  }
172 #ifdef DEBUG
173  std::cerr << " " << std::setw(14) << features.feature(f).name()
174  << " " << features.weight(f) << " => " << sum_win/sum_denom
175  << " " << sum_win << " / " << sum_denom
176  << " " << 400*log10(sum_win/sum_denom) << "\n";
177 #endif
178  // update
179  if (sum_denom)
180  features.setWeight(f, sum_win/sum_denom);
181  assert(! std::isinf(features.weight(f)));
182  assert(! std::isnan(features.weight(f)));
183  }
184 
185  features.showGroup(std::cerr, g);
186 }
187 
188 void osl::rating::
190 {
191  for (int j=0; j<16; ++j) {
192  std::cerr << "\nnew iteration " << j << "\n";
193  for (size_t i=0; i<features.groupSize(); ++i) {
194  update(i);
196  if ((int)(i+1) == fix_group)
197  break;
198  }
199  }
200 }
201 #endif
202 /* ------------------------------------------------------------------------- */
203 // ;;; Local Variables:
204 // ;;; mode:c++
205 // ;;; c-basic-offset:2
206 // ;;; End:
「.ipx」という拡張子を持つ棋泉形式ファイル.
Definition: kisen.h:67
const range_t & range(size_t group) const
std::valarray< double > valarray_t
Definition: bradleyTerry.h:15
bool addSquare(size_t g, const NumEffectState &state, const RatingEnv &env, Move selected, valarray_t &wins, std::valarray< long double > &denominator) const
Definition: bradleyTerry.cc:25
const double & weight(size_t feature_id) const
const BradleyTerry * features
Definition: bradleyTerry.cc:81
void generateLegal(MoveVector &) const
全ての合法手を生成する.
virtual int findMatch(const NumEffectState &state, Move m, const RatingEnv &env) const
Definition: group.cc:24
std::pair< int, int > range_t
Definition: range.h:10
Thread(const BradleyTerry *a, size_t t, size_t f, size_t l, valarray_t *w, std::valarray< long double > *d, size_t *s)
Definition: bradleyTerry.cc:87
const Feature & feature(size_t feature_id) const
bool isMember(const T &e, const_iterator first, const_iterator last) const
Definition: container.h:257
BradleyTerry(FeatureSet &features, const std::string &kisen_file, int kisen_start=0)
Definition: bradleyTerry.cc:14
圧縮していない moveの表現 .
Definition: basic_type.h:1051
std::string output_directory
Definition: bradleyTerry.h:18
std::valarray< long double > * denominator
Definition: bradleyTerry.cc:85
void showGroup(std::ostream &, size_t group_id) const
Definition: featureSet.cc:642
void setWeight(size_t feature_id, const double &value)
Definition: featureSet.cc:193
Player turn() const
Definition: simpleState.h:220
「.kif」という拡張子を持つ棋泉形式ファイル.
Definition: kisen.h:24
bool effectiveInCheck(size_t group_id) const
利きを持つ局面
size_t size() const
Definition: container.h:243
std::string ipxFileName() const
Definition: kisen.h:39
const Group & group(size_t group_id) const
static bool hasCheckmateMove(NumEffectState const &state, Square target, King8Info mask, Move &bestMove)
void save(const std::string &output_directory, size_t group_id) const
Definition: featureSet.cc:649
Player
Definition: basic_type.h:8
const std::string & name() const
void make(const NumEffectState &new_state)
Definition: ratingEnv.cc:32
size_t accumulate(size_t g, size_t first, size_t last, valarray_t &wins, std::valarray< long double > &denominator) const
Definition: bradleyTerry.cc:99