00001
00002
00003 #include "osl/rating/bradleyTerry.h"
00004 #include "osl/rating/group.h"
00005 #include "osl/checkmate/immediateCheckmate.h"
00006 #include "osl/record/kisen.h"
00007
00008 #include <thread>
00009 #include <iostream>
00010 #include <iomanip>
00011
00012 #ifndef MINIMAL
00013 osl::rating::
00014 BradleyTerry::BradleyTerry(FeatureSet& f, const std::string& kisen_file, int kisen_start)
00015 : features(f), kisen_filename(kisen_file), kisen_start(kisen_start), num_cpus(1), num_records(200),
00016 verbose(1), fix_group(-1), min_rating(0)
00017 {
00018 }
00019
00020 osl::rating::BradleyTerry::~BradleyTerry()
00021 {
00022 }
00023
00024 bool osl::rating::
00025 BradleyTerry::addSquare(size_t g, const NumEffectState& state,
00026 const RatingEnv& env, Move selected,
00027 valarray_t& wins, std::valarray<long double>& denominator) const
00028 {
00029 MoveVector moves;
00030 state.generateLegal(moves);
00031 if (! moves.isMember(selected))
00032 return false;
00033 const range_t range = features.range(g);
00034 #ifdef SPEEDUP_TEST
00035 const bool in_check = EffectUtil::isKingInCheck(state.turn(), state);
00036 if (! in_check || features.effectiveInCheck(g))
00037 #endif
00038 {
00039 int found = features.group(g).findMatch(state, selected, env);
00040 if (found >= 0)
00041 ++wins[found+range.first];
00042 }
00043 valarray_t sum_c(0.0, range.second-range.first);
00044 long double sum_e = 0.0;
00045 for (size_t i=0; i<moves.size(); ++i) {
00046 Move m = moves[i];
00047 double product = 1.0;
00048 int count = 0;
00049 int match_id = -1;
00050 for (size_t j=0; j<features.groupSize(); ++j) {
00051 #ifdef SPEEDUP_TEST
00052 if (in_check && ! features.effectiveInCheck(j))
00053 continue;
00054 #endif
00055 int found = features.group(j).findMatch(state, m, env);
00056 if (found < 0)
00057 continue;
00058 found += features.range(j).first;
00059 product *= features.weight(found);
00060 ++count;
00061 if (j == g) {
00062 assert(range.first <= found && found < range.second);
00063 match_id = found;
00064 }
00065 }
00066 assert(count);
00067 sum_e += product;
00068 if (match_id >= 0)
00069 sum_c[match_id-range.first] += product / features.weight(match_id);
00070 }
00071 assert(sum_e > 0);
00072 for (int f=range.first; f<range.second; ++f)
00073 denominator[f] += sum_c[f-range.first]/sum_e;
00074 return true;
00075 }
00076
00077 class osl::rating::
00078 BradleyTerry::Thread
00079 {
00080 public:
00081 const BradleyTerry *features;
00082 size_t target;
00083 size_t first, last;
00084 valarray_t *wins;
00085 std::valarray<long double> *denominator;
00086 size_t *skip;
00087 Thread(const BradleyTerry *a, size_t t, size_t f, size_t l, valarray_t *w, std::valarray<long double> *d,
00088 size_t *s)
00089 : features(a), target(t), first(f), last(l), wins(w), denominator(d), skip(s)
00090 {
00091 }
00092 void operator()()
00093 {
00094 *skip = features->accumulate(target, first, last, *wins, *denominator);
00095 }
00096 };
00097
00098 size_t osl::rating::
00099 BradleyTerry::accumulate(size_t g, size_t first, size_t last, valarray_t& wins, std::valarray<long double>& denominator) const
00100 {
00101 assert(wins.size() == features.featureSize());
00102 KisenFile kisen_file(kisen_filename.c_str());
00103 KisenIpxFile ipx(KisenFile::ipxFileName(kisen_filename));
00104 size_t skip = 0;
00105 for (size_t i=first; i<last; i++) {
00106 if ((i % 4000) == 0)
00107 std::cerr << ".";
00108 if (ipx.rating(i, BLACK) < min_rating
00109 || ipx.rating(i, WHITE) < min_rating) {
00110 ++skip;
00111 continue;
00112 }
00113 NumEffectState state(kisen_file.initialState());
00114 RatingEnv env;
00115 env.make(state);
00116 const auto moves=kisen_file.moves(i+kisen_start);
00117 for (size_t j=0; j<moves.size(); j++) {
00118 if (j<2)
00119 goto next;
00120 {
00121 const Player turn = state.turn();
00122 if (! state.inCheck()
00123 && ImmediateCheckmate::hasCheckmateMove(turn, state))
00124 break;
00125 }
00126 if (! addSquare(g, state, env, moves[j], wins, denominator))
00127 break;
00128 next:
00129 state.makeMove(moves[j]);
00130 env.update(state, moves[j]);
00131 }
00132 }
00133 return skip;
00134 }
00135
00136 void osl::rating::
00137 BradleyTerry::update(size_t g)
00138 {
00139 std::valarray<valarray_t> wins(valarray_t(0.0, features.featureSize()), num_cpus);
00140 std::valarray<std::valarray<long double> > denominator(std::valarray<long double>(0.0, features.featureSize()), num_cpus);
00141 assert(wins.size() == num_cpus);
00142
00143 KisenFile kisen_file(kisen_filename.c_str());
00144 if (num_records==0)
00145 num_records=kisen_file.size();
00146 if (num_cpus == 1) {
00147 accumulate(g, 0, num_records, wins[0], denominator[0]);
00148 }
00149 else {
00150 size_t cur = 0;
00151 size_t last = num_records, step = (last - cur)/num_cpus;
00152 boost::ptr_vector<std::thread> threads;
00153 std::valarray<size_t> skip((size_t)0, num_cpus);
00154 for (size_t i=0; i<num_cpus; ++i, cur += step) {
00155 size_t next = (i+1 == num_cpus) ? last : cur + step;
00156 threads.push_back(new std::thread(Thread(this, g, cur, next, &wins[i], &denominator[i], &skip[i])));
00157 }
00158 for (size_t i=0; i<num_cpus; ++i)
00159 threads[i].join();
00160 if (g == 0)
00161 std::cerr << "skip " << skip.sum() << " / " << num_records << "\n";
00162 }
00163 const range_t range = features.range(g);
00164 for (int f=range.first; f<range.second; ++f) {
00165 const int NPRIOR = 10;
00166 double sum_win = NPRIOR;
00167 long double sum_denom = (1.0 / (features.weight(f) + 1.0)) * 2 * NPRIOR;
00168 for (size_t i=0; i<num_cpus; ++i) {
00169 sum_win += wins[i][f];
00170 sum_denom += denominator[i][f];
00171 }
00172 #ifdef DEBUG
00173 std::cerr << " " << std::setw(14) << features.feature(f).name()
00174 << " " << features.weight(f) << " => " << sum_win/sum_denom
00175 << " " << sum_win << " / " << sum_denom
00176 << " " << 400*log10(sum_win/sum_denom) << "\n";
00177 #endif
00178
00179 if (sum_denom)
00180 features.setWeight(f, sum_win/sum_denom);
00181 assert(! std::isinf(features.weight(f)));
00182 assert(! std::isnan(features.weight(f)));
00183 }
00184
00185 features.showGroup(std::cerr, g);
00186 }
00187
00188 void osl::rating::
00189 BradleyTerry::iterate()
00190 {
00191 for (int j=0; j<16; ++j) {
00192 std::cerr << "\nnew iteration " << j << "\n";
00193 for (size_t i=0; i<features.groupSize(); ++i) {
00194 update(i);
00195 features.save(output_directory, i);
00196 if ((int)(i+1) == fix_group)
00197 break;
00198 }
00199 }
00200 }
00201 #endif
00202
00203
00204
00205
00206