bradleyTerry.cc
Go to the documentation of this file.
/* bradleyTerry.cc
*/
#include "osl/rating/bradleyTerry.h"
#include "osl/rating/group.h"
#include "osl/checkmate/immediateCheckmate.h"
#include "osl/record/kisen.h"
#include <thread>
#include <iostream>
#include <iomanip>
#ifndef MINIMAL
osl::rating::
BradleyTerry::BradleyTerry(FeatureSet& f, const std::string& kisen_file, int kisen_start)
: features(f), kisen_filename(kisen_file), kisen_start(kisen_start), num_cpus(1), num_records(200),
verbose(1), fix_group(-1), min_rating(0)
{
}
osl::rating::BradleyTerry::~BradleyTerry()
{
}
bool osl::rating::
BradleyTerry::addSquare(size_t g, const NumEffectState& state,
const RatingEnv& env, Move selected,
valarray_t& wins, std::valarray<long double>& denominator) const
{
MoveVector moves;
state.generateLegal(moves);
if (! moves.isMember(selected))
return false; // checkmate or illegal move
const range_t range = features.range(g);
#ifdef SPEEDUP_TEST
const bool in_check = EffectUtil::isKingInCheck(state.turn(), state);
if (! in_check || features.effectiveInCheck(g))
#endif
{
int found = features.group(g).findMatch(state, selected, env);
if (found >= 0)
++wins[found+range.first];
}
valarray_t sum_c(0.0, range.second-range.first);
long double sum_e = 0.0;
for (size_t i=0; i<moves.size(); ++i) {
Move m = moves[i];
double product = 1.0;
int count = 0;
int match_id = -1;
for (size_t j=0; j<features.groupSize(); ++j) {
#ifdef SPEEDUP_TEST
if (in_check && ! features.effectiveInCheck(j))
continue;
#endif
int found = features.group(j).findMatch(state, m, env);
if (found < 0)
continue;
found += features.range(j).first;
product *= features.weight(found);
++count;
if (j == g) {
assert(range.first <= found && found < range.second);
match_id = found;
}
}
assert(count);
sum_e += product;
if (match_id >= 0)
sum_c[match_id-range.first] += product / features.weight(match_id);
}
assert(sum_e > 0);
for (int f=range.first; f<range.second; ++f)
denominator[f] += sum_c[f-range.first]/sum_e;
return true;
}
class osl::rating::
BradleyTerry::Thread
{
public:
const BradleyTerry *features;
size_t target;
size_t first, last;
valarray_t *wins;
std::valarray<long double> *denominator;
size_t *skip;
Thread(const BradleyTerry *a, size_t t, size_t f, size_t l, valarray_t *w, std::valarray<long double> *d,
size_t *s)
: features(a), target(t), first(f), last(l), wins(w), denominator(d), skip(s)
{
}
void operator()()
{
*skip = features->accumulate(target, first, last, *wins, *denominator);
}
};
size_t osl::rating::
BradleyTerry::accumulate(size_t g, size_t first, size_t last, valarray_t& wins, std::valarray<long double>& denominator) const
{
assert(wins.size() == features.featureSize());
KisenFile kisen_file(kisen_filename.c_str());
KisenIpxFile ipx(KisenFile::ipxFileName(kisen_filename));
size_t skip = 0;
for (size_t i=first; i<last; i++) {
if ((i % 4000) == 0)
std::cerr << ".";
if (ipx.rating(i, BLACK) < min_rating
|| ipx.rating(i, WHITE) < min_rating) {
++skip;
continue;
}
NumEffectState state(kisen_file.initialState());
RatingEnv env;
env.make(state);
const auto moves=kisen_file.moves(i+kisen_start);
for (size_t j=0; j<moves.size(); j++) {
if (j<2)
goto next;
{
const Player turn = state.turn();
if (! state.inCheck()
&& ImmediateCheckmate::hasCheckmateMove(turn, state))
break;
}
if (! addSquare(g, state, env, moves[j], wins, denominator))
break;
next:
state.makeMove(moves[j]);
env.update(state, moves[j]);
}
}
return skip;
}
void osl::rating::
BradleyTerry::update(size_t g)
{
std::valarray<valarray_t> wins(valarray_t(0.0, features.featureSize()), num_cpus);
std::valarray<std::valarray<long double> > denominator(std::valarray<long double>(0.0, features.featureSize()), num_cpus);
assert(wins.size() == num_cpus);
KisenFile kisen_file(kisen_filename.c_str());
if (num_records==0)
num_records=kisen_file.size();
if (num_cpus == 1) {
accumulate(g, 0, num_records, wins[0], denominator[0]);
}
else {
size_t cur = 0;
size_t last = num_records, step = (last - cur)/num_cpus;
boost::ptr_vector<std::thread> threads;
std::valarray<size_t> skip((size_t)0, num_cpus);
for (size_t i=0; i<num_cpus; ++i, cur += step) {
size_t next = (i+1 == num_cpus) ? last : cur + step;
threads.push_back(new std::thread(Thread(this, g, cur, next, &wins[i], &denominator[i], &skip[i])));
}
for (size_t i=0; i<num_cpus; ++i)
threads[i].join();
if (g == 0)
std::cerr << "skip " << skip.sum() << " / " << num_records << "\n";
}
const range_t range = features.range(g);
for (int f=range.first; f<range.second; ++f) {
const int NPRIOR = 10; // assume NPRIOR wins, NPRIOR losses
double sum_win = NPRIOR;
long double sum_denom = (1.0 / (features.weight(f) + 1.0)) * 2 * NPRIOR;
for (size_t i=0; i<num_cpus; ++i) {
sum_win += wins[i][f];
sum_denom += denominator[i][f];
}
#ifdef DEBUG
std::cerr << " " << std::setw(14) << features.feature(f).name()
<< " " << features.weight(f) << " => " << sum_win/sum_denom
<< " " << sum_win << " / " << sum_denom
<< " " << 400*log10(sum_win/sum_denom) << "\n";
#endif
// update
if (sum_denom)
features.setWeight(f, sum_win/sum_denom);
assert(! std::isinf(features.weight(f)));
assert(! std::isnan(features.weight(f)));
}
features.showGroup(std::cerr, g);
}
void osl::rating::
BradleyTerry::iterate()
{
for (int j=0; j<16; ++j) {
std::cerr << "\nnew iteration " << j << "\n";
for (size_t i=0; i<features.groupSize(); ++i) {
update(i);
features.save(output_directory, i);
if ((int)(i+1) == fix_group)
break;
}
}
}
#endif
/* ------------------------------------------------------------------------- */
// ;;; Local Variables:
// ;;; mode:c++
// ;;; c-basic-offset:2
// ;;; End:
bradleyTerry.h
osl::FixedCapacityVector::size
size_t size() const
Definition container.h:243
osl::FixedCapacityVector::isMember
bool isMember(const T &e, const_iterator first, const_iterator last) const
Definition container.h:257
osl::ImmediateCheckmate::hasCheckmateMove
static bool hasCheckmateMove(NumEffectState const &state, Square target, King8Info mask, Move &bestMove)
osl::KisenFile::ipxFileName
std::string ipxFileName() const
Definition kisen.h:39
osl::MoveVector
Definition container.h:293
osl::Move
圧縮していない moveの表現 .
Definition basic_type.h:1052
osl::NumEffectState
利きを持つ局面
Definition numEffectState.h:34
osl::NumEffectState::generateLegal
void generateLegal(MoveVector &) const
全ての合法手を生成する.
Definition numEffectState.cc:1086
osl::NumEffectState::makeMove
void makeMove(Move move)
Definition numEffectState.cc:201
osl::NumEffectState::inCheck
bool inCheck(Player P) const
Pの玉が王手状態
Definition numEffectState.h:88
osl::SimpleState::turn
Player turn() const
Definition simpleState.h:220
osl::rating::BradleyTerry::Thread
Definition bradleyTerry.cc:79
osl::rating::BradleyTerry::Thread::operator()
void operator()()
Definition bradleyTerry.cc:92
osl::rating::BradleyTerry::Thread::last
size_t last
Definition bradleyTerry.cc:83
osl::rating::BradleyTerry::Thread::wins
valarray_t * wins
Definition bradleyTerry.cc:84
osl::rating::BradleyTerry::Thread::denominator
std::valarray< long double > * denominator
Definition bradleyTerry.cc:85
osl::rating::BradleyTerry::Thread::target
size_t target
Definition bradleyTerry.cc:82
osl::rating::BradleyTerry::Thread::features
const BradleyTerry * features
Definition bradleyTerry.cc:81
osl::rating::BradleyTerry::Thread::Thread
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
osl::rating::BradleyTerry::Thread::first
size_t first
Definition bradleyTerry.cc:83
osl::rating::BradleyTerry::Thread::skip
size_t * skip
Definition bradleyTerry.cc:86
osl::rating::BradleyTerry::update
void update(size_t g)
Definition bradleyTerry.cc:137
osl::rating::BradleyTerry::num_records
size_t num_records
Definition bradleyTerry.h:20
osl::rating::BradleyTerry::kisen_filename
std::string kisen_filename
Definition bradleyTerry.h:18
osl::rating::BradleyTerry::valarray_t
std::valarray< double > valarray_t
Definition bradleyTerry.h:15
osl::rating::BradleyTerry::BradleyTerry
BradleyTerry(FeatureSet &features, const std::string &kisen_file, int kisen_start=0)
Definition bradleyTerry.cc:14
osl::rating::BradleyTerry::features
FeatureSet & features
Definition bradleyTerry.h:16
osl::rating::BradleyTerry::addSquare
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
osl::rating::BradleyTerry::~BradleyTerry
~BradleyTerry()
Definition bradleyTerry.cc:20
osl::rating::BradleyTerry::accumulate
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
osl::rating::BradleyTerry::fix_group
int fix_group
Definition bradleyTerry.h:22
osl::rating::BradleyTerry::num_cpus
size_t num_cpus
Definition bradleyTerry.h:20
osl::rating::BradleyTerry::verbose
int verbose
Definition bradleyTerry.h:21
osl::rating::BradleyTerry::kisen_start
int kisen_start
Definition bradleyTerry.h:19
osl::rating::BradleyTerry::Thread
friend class Thread
Definition bradleyTerry.h:43
osl::rating::BradleyTerry::output_directory
std::string output_directory
Definition bradleyTerry.h:18
osl::rating::BradleyTerry::iterate
void iterate()
Definition bradleyTerry.cc:189
osl::rating::BradleyTerry::min_rating
size_t min_rating
Definition bradleyTerry.h:23
osl::rating::FeatureSet
Definition rating/featureSet.h:31
osl::rating::RatingEnv
Definition ratingEnv.h:16
osl::rating::RatingEnv::make
void make(const NumEffectState &new_state)
Definition ratingEnv.cc:32
osl::rating::RatingEnv::update
void update(const NumEffectState &new_state, Move last_move)
Definition ratingEnv.cc:9
osl::record::KisenFile
「.kif」という拡張子を持つ棋泉形式ファイル.
Definition kisen.h:24
osl::record::KisenFile::size
size_t size() const
Definition kisen.h:35
osl::record::KisenFile::moves
std::vector< Move > moves(size_t index)
Definition kisen.cc:94
osl::record::KisenFile::initialState
NumEffectState initialState() const
Definition kisen.h:36
osl::record::KisenIpxFile
「.ipx」という拡張子を持つ棋泉形式ファイル.
Definition kisen.h:67
osl::record::KisenIpxFile::rating
unsigned int rating(size_t index, Player pl)
Definition kisen.cc:152
group.h
immediateCheckmate.h
kisen.h
osl::rating
Definition construct.h:18
osl::rating::range_t
std::pair< int, int > range_t
Definition range.h:10
osl::Player
Player
Definition basic_type.h:8
osl::WHITE
@ WHITE
Definition basic_type.h:10
osl::BLACK
@ BLACK
Definition basic_type.h:9