00001
00002
00003 #include "osl/search/moveGenerator.h"
00004 #include "osl/search/searchState2.h"
00005 #include "osl/search/shouldPromoteCut.h"
00006 #include "osl/search/sortCaptureMoves.h"
00007 #include "osl/category/breakThreatmate.h"
00008 #include "osl/category/analyzer/categoryMoveVector.h"
00009 #include "osl/move_generator/capture_.h"
00010 #include "osl/move_generator/escape_.h"
00011 #include "osl/move_generator/promote_.h"
00012 #include "osl/move_generator/addEffect_.h"
00013 #include "osl/move_generator/allMoves.h"
00014 #include "osl/move_generator/attackToPinned.h"
00015 #include "osl/move_action/store.h"
00016 #include "osl/move_classifier/check_.h"
00017 #include "osl/move_classifier/kingOpenMove.h"
00018 #include "osl/effect_util/effectUtil.h"
00019 #include "osl/rating/featureSet.h"
00020 #include "osl/rating/ratingEnv.h"
00021 #include "osl/eval/pieceEval.h"
00022 #include "osl/eval/progressEval.h"
00023 #include "osl/stat/average.h"
00024 #include <iostream>
00025 #include <iomanip>
00026
00027
00028
00029 #ifndef NDEBUG
00030 # define SAFE_MOVE_ONLY
00031 #endif
00032 const int max_see = 20000;
00033 static const osl::rating::FeatureSet& feature_set()
00034 {
00035 static osl::rating::StandardFeatureSet feature_set;
00036 return feature_set;
00037 }
00038
00039 namespace osl
00040 {
00041 namespace search
00042 {
00043 const CArray2d<MoveGenerator::generator_t, 2, MoveGenerator::FINISH> MoveGenerator::Generators = {{
00044 {
00045 0,
00046 &MoveGenerator::generateKingEscape<BLACK>,
00047 &MoveGenerator::generateTakeBack<BLACK>,
00048 &MoveGenerator::generateBreakThreatmate<BLACK>,
00049 &MoveGenerator::generateCapture<BLACK>,
00050 0,
00051 &MoveGenerator::generateTesuji<BLACK>,
00052 &MoveGenerator::generateAll<BLACK>,
00053 },
00054 {
00055 0,
00056 &MoveGenerator::generateKingEscape<WHITE>,
00057 &MoveGenerator::generateTakeBack<WHITE>,
00058 &MoveGenerator::generateBreakThreatmate<WHITE>,
00059 &MoveGenerator::generateCapture<WHITE>,
00060 0,
00061 &MoveGenerator::generateTesuji<WHITE>,
00062 &MoveGenerator::generateAll<WHITE>,
00063 }
00064 }};
00065 const CArray<const char *, MoveGenerator::FINISH> MoveGenerator::GeneratorNames = {{
00066 "INITIAL", "KING_ESCAPE", "TAKEBACK", "BREAK_THREATMATE", "TACTICAL", "SENTINEL", "TESUJI", "ALL",
00067 }};
00068 #ifdef STAT_WIDTH_VS_LIMIT
00069 struct WidthVSLimit
00070 {
00071 CArray<stat::Average,10> averages;
00072
00073 ~WidthVSLimit()
00074 {
00075 report();
00076 }
00077 stat::Average& average(int limit)
00078 {
00079 limit /= 100 - 3;
00080 return averages[std::min(std::max(limit,0),(int)averages.size()-1)];
00081 }
00082 void report()
00083 {
00084 std::cerr << "WidthVSLimit@MoveGenerator\n";
00085 for (int limit=300; limit<300+(int)averages.size()*100; limit+=100) {
00086 std::cerr << std::setw(5) << limit << " " << average(limit).getAverage() << std::endl;
00087 }
00088 }
00089 } Width_VS_Limit;
00090 #endif
00091 }
00092 }
00093
00094
00095
00096 osl::search::
00097 MoveMarker::MoveMarker() : cur(1)
00098 {
00099 marker.fill(0);
00100 }
00101
00102 void osl::search::
00103 MoveMarker::clear()
00104 {
00105 ++cur;
00106 if (cur == 0) {
00107 marker.fill(0);
00108 cur = 1;
00109 }
00110 }
00111
00112 bool osl::search::
00113 MoveMarker::registerIfNew(const NumEffectState& state, Move m)
00114 {
00115 value_t& val = marker(toIndex(m), pieceIndex(state, m));
00116 if (val == cur)
00117 return false;
00118 val = cur;
00119 return true;
00120 }
00121
00122 bool osl::search::
00123 MoveMarker::registered(const NumEffectState& state, Move m) const
00124 {
00125 return marker(toIndex(m), pieceIndex(state, m)) == cur;
00126 }
00127
00128
00129
00130 osl::search::
00131 MoveGenerator::MoveGenerator() : record(0), progress(16)
00132 {
00133 }
00134
00135 int osl::search::
00136 MoveGenerator::captureValue(Ptype ptype)
00137 {
00138 if (! isPiece(ptype))
00139 return 0;
00140 int result
00141 = eval::Ptype_Eval_Table.captureValue(newPtypeO(WHITE, ptype));
00142 assert(result >= 0);
00143 return result;
00144 }
00145
00146 void osl::search::
00147 MoveGenerator::init(int l, SimpleHashRecord *r, const eval::ProgressEval& eval,
00148 const NumEffectState& state, bool in_pv, Move hash_move,
00149 bool quiesce)
00150 {
00151 assert(r);
00152 assert(l > 0);
00153 limit = l;
00154 record = r;
00155 cur_state = INITIAL;
00156 moves.clear();
00157 cur_index = tried = 0;
00158 progress = eval.progress32();
00159
00160 marker.clear();
00161 env.make(state, eval.pins(state.getTurn()), eval.pins(alt(state.getTurn())),
00162 eval.progress16());
00163 if (hash_move.isNormal())
00164 marker.registerMove(state, hash_move);
00165 in_quiesce = quiesce;
00166 this->in_pv = in_pv;
00167 }
00168
00169 void osl::search::
00170 MoveGenerator::dump() const
00171 {
00172 std::cerr << "generator " << cur_state << " index " << cur_index
00173 << " limit " << limit << " tried " << tried << "\n";
00174 std::cerr << moves.size() << "\n" << moves;
00175 }
00176
00177 template <osl::Player P>
00178 const osl::MoveLogProb osl::search::
00179 MoveGenerator::nextTacticalMoveWithGeneration(const SearchState2& state)
00180 {
00181 assert(record);
00182 while (true) {
00183 assert(cur_index >= moves.size());
00184 if (cur_state == KING_ESCAPE && record->is_king_in_check) {
00185 cur_state = FINISH;
00186 break;
00187 }
00188 if (++cur_state >= TACTICAL_FINISH)
00189 break;
00190
00191 assert(Generators[playerToIndex(P)][cur_state]);
00192 (this->*Generators[playerToIndex(P)][cur_state])(state);
00193 if (cur_index < moves.size()) {
00194 ++tried;
00195 return moves[cur_index++];
00196 }
00197 }
00198 return MoveLogProb();
00199 }
00200
00201 template <osl::Player P>
00202 const osl::MoveLogProb osl::search::
00203 MoveGenerator::nextMoveWithGeneration(const SearchState2& state)
00204 {
00205 assert(record);
00206 while (true) {
00207 assert(cur_index >= moves.size());
00208 if (++cur_state >= FINISH)
00209 break;
00210
00211 assert(Generators[playerToIndex(P)][cur_state]);
00212 (this->*Generators(playerToIndex(P), cur_state))(state);
00213 if (cur_index < moves.size()) {
00214 ++tried;
00215 return moves[cur_index++];
00216 }
00217 }
00218 return MoveLogProb();
00219 }
00220
00221 template <osl::Player P>
00222 void osl::search::
00223 MoveGenerator::generateKingEscape(const SearchState2& sstate)
00224 {
00225 env.history = sstate.history();
00226 if (! record->is_king_in_check)
00227 return;
00228 using namespace move_action;
00229
00230 const NumEffectState& state = sstate.state();
00231 const Piece king = state.getKingPiece<P>();
00232 assert(state.hasEffectBy(alt(P), king.position()));
00233
00234 MoveVector src;
00235 Store store(src);
00236 move_generator::Escape<P,NumEffectState,Store>::
00237 generateMoves(state,king,store);
00238
00239 if (src.size() == 1) {
00240 moves.push_back(MoveLogProb(src[0], 20));
00241 return;
00242 }
00243 for (MoveVector::const_iterator p=src.begin(); p!=src.end(); ++p) {
00244 const int prob = std::min(limit, feature_set().logProbKingEscape(state, env, *p));
00245 assert(prob > 0);
00246 moves.push_back(MoveLogProb(*p, prob));
00247 }
00248 moves.sortByProbability();
00249 }
00250
00251 template <osl::Player P>
00252 void osl::search::
00253 MoveGenerator::generateBreakThreatmate(const SearchState2& sstate)
00254 {
00255 const NumEffectState& state = sstate.state();
00256 const category::CategoryEnv env(&state, limit, &sstate.history(), progress,
00257 record);
00258 category::BreakThreatmate::generate(env, moves);
00259 for (size_t i=0; i<moves.size(); ++i)
00260 marker.registerMove(state, moves[i].getMove());
00261 }
00262
00263 template <osl::Player P>
00264 void osl::search::
00265 MoveGenerator::generateTakeBack(const SearchState2& sstate)
00266 {
00267 using namespace move_action;
00268 const Move last_move = sstate.lastMove();
00269 if (! last_move.isNormal())
00270 return;
00271 const Position last_to = last_move.to();
00272
00273 const NumEffectState& state = sstate.state();
00274 MoveVector src;
00275 Store store(src);
00276
00277 if (in_quiesce)
00278 return quiesceCapture<P>(state, last_to);
00279
00280 move_generator::Capture<P>::generate(state, last_to, store);
00281 assert(moves.empty());
00282 for (MoveVector::const_iterator p=src.begin(); p!=src.end(); ++p) {
00283 if (ShouldPromoteCut::canIgnoreMove<P>(*p))
00284 continue;
00285 const int prob = feature_set().logProbTakeBack(state, env, *p);
00286 #ifdef OSL_SMP
00287 if (! p->isDrop() && p->ptype() != KING
00288 && env.my_pin.test(state.getPieceOnBoard(p->from()).number())) {
00289 if (move_classifier::KingOpenMove<P>::isMember(state, p->ptype(), p->from(), p->to()))
00290 continue;
00291 }
00292 #endif
00293 if (prob <= std::min(200, limit) && marker.registerIfNew(state, *p))
00294 moves.push_back(MoveLogProb(*p, prob));
00295 }
00296 moves.sortByProbability();
00297 }
00298
00299 namespace osl
00300 {
00301 template <Player P>
00302 static void makeCapture(const NumEffectState& state, int first, int last,
00303 MoveVector& out)
00304 {
00305 move_action::Store store(out);
00306 for (int i = first; i < last; i++) {
00307 const Piece p = state.getPieceOf(i);
00308 if (p.isOnBoardByOwner<PlayerTraits<P>::opponent>())
00309 move_generator::Capture<P>::generate(state, p.position(), store);
00310 }
00311 }
00312 }
00313
00314 template <osl::Player P>
00315 void osl::search::
00316 MoveGenerator::addCapture(const NumEffectState& state, const RatingEnv& env, const MoveVector& src)
00317 {
00318 if (in_quiesce) {
00319 for (MoveVector::const_iterator p=src.begin(); p!=src.end(); ++p) {
00320 if (ShouldPromoteCut::canIgnoreMove<P>(*p))
00321 continue;
00322 const int see = PieceEval::computeDiffAfterMoveForRP(state, *p);
00323 if (see < 0)
00324 continue;
00325 moves.push_back(MoveLogProb(*p, max_see - see));
00326 }
00327 return;
00328 }
00329
00330 for (MoveVector::const_iterator p=src.begin(); p!=src.end(); ++p) {
00331 const Move m = *p;
00332 if (ShouldPromoteCut::canIgnoreMove<P>(m))
00333 continue;
00334 #ifdef SAFE_MOVE_ONLY
00335 if (! m.isDrop() && m.ptype() != KING
00336 && env.my_pin.test(state.getPieceOnBoard(m.from()).number())) {
00337 if (move_classifier::KingOpenMove<P>::isMember(state, m.ptype(), m.from(), m.to()))
00338 continue;
00339 }
00340 #endif
00341 const int prob = feature_set().logProbSeePlus(state, env, *p);
00342
00343 if (prob <= 200 && marker.registerIfNew(state, *p)) {
00344 moves.push_back(MoveLogProb(*p, prob));
00345 }
00346 }
00347 return;
00348 }
00349
00350 template <osl::Player P>
00351 void osl::search::
00352 MoveGenerator::generateCapture(const SearchState2& sstate)
00353 {
00354 using namespace move_action;
00355
00356 const NumEffectState& state = sstate.state();
00357 MoveVector src;
00358
00359 makeCapture<P>(state, PtypeTraits<LANCE>::indexMin, PtypeTraits<ROOK>::indexLimit,
00360 src);
00361
00362 makeCapture<P>(state, PtypeTraits<KNIGHT>::indexMin, PtypeTraits<GOLD>::indexLimit, src);
00363 addCapture<P>(state, env, src);
00364 }
00365
00366 template <osl::Player P>
00367 void osl::search::
00368 MoveGenerator::generateTesuji(const SearchState2& sstate)
00369 {
00370 const NumEffectState& state = sstate.state();
00371 if (in_quiesce) {
00372 MoveVector src;
00373 move_action::Store store(src);
00374 move_generator::Promote<P,NumEffectState,move_action::Store>::
00375 generateMoves(state, store);
00376 makeCapture<P>(state, PtypeTraits<PAWN>::indexMin, PtypeTraits<PAWN>::indexLimit, src);
00377 addCapture<P>(state, env, src);
00378 }
00379 }
00380
00381 template <osl::Player P>
00382 void osl::search::
00383 MoveGenerator::quiesceCapture(const NumEffectState& state, Position to)
00384 {
00385 MoveVector moves;
00386 move_action::Store store(moves);
00387 move_generator::Capture<P>::generate(state, to, store);
00388 for (MoveVector::const_iterator p=moves.begin(); p!=moves.end(); ++p) {
00389 if (ShouldPromoteCut::canIgnoreAndNotDrop<P>(*p))
00390 continue;
00391 int see = PieceEval::computeDiffAfterMoveForRP(state, *p);
00392 if (see < 0)
00393 continue;
00394 this->moves.push_back(MoveLogProb(*p, max_see - see));
00395 }
00396 this->moves.sortByProbabilityReverse();
00397 }
00398
00399 template <osl::Player P>
00400 void osl::search::
00401 MoveGenerator::generateAll(const SearchState2& sstate)
00402 {
00403 if (in_quiesce)
00404 return;
00405 const NumEffectState& state = sstate.state();
00406 MoveLogProbVector all;
00407 feature_set().generateLogProb(state, env, limit, all, in_pv);
00408 #ifdef STAT_WIDTH_VS_LIMIT
00409 const size_t moves_size_before = moves.size();
00410 #endif
00411 for (size_t i=0; i<all.size(); ++i) {
00412 const Move m = all[i].getMove();
00413 if (ShouldPromoteCut::canIgnoreAndNotDrop<P>(m))
00414 continue;
00415 int limit = all[i].getLogProb();
00416 if (all[i].getMove().capturePtype() != PTYPE_EMPTY
00417 || all[i].getMove().isPromote())
00418 limit = std::min(limit, 400);
00419 if (limit <= this->limit
00420 && marker.registerIfNew(state, m)) {
00421 #ifndef NDEBUG
00422 if (! m.isDrop()) {
00423 assert(! (env.my_pin.test(state.getPieceOnBoard(m.from()).number())
00424 && move_classifier::KingOpenMove<P>::isMember(state, m.ptype(), m.from(), m.to())));
00425 assert(! (m.ptype() == KING && state.hasEffectBy(alt(P), m.to())));
00426 }
00427 #endif
00428 moves.push_back(MoveLogProb(all[i].getMove(), limit));
00429 }
00430 }
00431 #ifdef STAT_WIDTH_VS_LIMIT
00432 Width_VS_Limit.average(limit).add(moves.size() - moves_size_before);
00433 #endif
00434 }
00435
00436 void osl::search::
00437 MoveGenerator::generateAll(Player P, const SearchState2& state,
00438 category::analyzer::CategoryMoveVector& out)
00439 {
00440 assert(moves.size() == 0);
00441
00442 for (int i=0; i<FINISH; ++i) {
00443 if (! Generators[playerToIndex(P)][i])
00444 continue;
00445 (this->*Generators[playerToIndex(P)][i])(state);
00446 out.push_front(category::analyzer::CategoryMoves(moves, GeneratorNames[i]));
00447 bool generated = moves.size();
00448 moves.clear();
00449 if (i == KING_ESCAPE && generated)
00450 break;
00451 }
00452 out.reverse();
00453 }
00454
00455 template <osl::Player P>
00456 void
00457 #ifdef __GNUC__
00458 __attribute__ ((used))
00459 #endif
00460 osl::search::
00461 MoveGenerator::generateAll(const SearchState2& state, MoveLogProbVector& out)
00462 {
00463 for (MoveLogProb m = nextTacticalMove<P>(state);
00464 m.validMove(); m = nextTacticalMove<P>(state)) {
00465 out.push_back(m);
00466 }
00467 for (MoveLogProb m = nextMove<P>(state); m.validMove();
00468 m = nextMove<P>(state)) {
00469 out.push_back(m);
00470 }
00471 }
00472
00473 void osl::search::
00474 MoveGenerator::generateAll(Player P, const SearchState2& state, MoveLogProbVector& out)
00475 {
00476 if (P==BLACK)
00477 generateAll<BLACK>(state, out);
00478 else
00479 generateAll<WHITE>(state, out);
00480 }
00481
00482 namespace osl
00483 {
00484 namespace search
00485 {
00486 template const MoveLogProb MoveGenerator::nextMoveWithGeneration<BLACK>(const SearchState2&);
00487 template const MoveLogProb MoveGenerator::nextMoveWithGeneration<WHITE>(const SearchState2&);
00488
00489 template const MoveLogProb MoveGenerator::nextTacticalMoveWithGeneration<BLACK>(const SearchState2&);
00490 template const MoveLogProb MoveGenerator::nextTacticalMoveWithGeneration<WHITE>(const SearchState2&);
00491 }
00492 }
00493
00494
00495
00496
00497
00498