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