00001 #include "osl/brinkmate/searcher.h"
00002 #include "osl/move_generator/legalMoves.h"
00003 #include "osl/move_classifier/check_.h"
00004 #include "osl/move_classifier/moveAdaptor.h"
00005 #include "osl/move_order/captureEstimation.h"
00006 #include "osl/effect_util/effectUtil.h"
00007 #include "osl/effect_util/neighboring8Direct.h"
00008 #include "osl/effect_util/additionalEffect.h"
00009 #include "osl/container/moveVector.h"
00010 #include "osl/record/csa.h"
00011 #include "osl/misc/alarm.h"
00012 #include "osl/centering3x3.h"
00013 #include "osl/neighboring8.h"
00014 #include "osl/boardTable.h"
00015 #include <iostream>
00016 #include <string>
00017
00018 static const int report_do_undo = 2;
00019 static const int max_threshold = 1600;
00020
00021 osl::brinkmate::
00022 Searcher::Searcher(Player attack, size_t capacity, int verbose)
00023 : table(attack, capacity),
00024 checkmator(CHECKMATE_DEFAULT_TOTAL_NODE_LIMIT*64),
00025 stop_flag(0),
00026 count(0), max_depth(0), verbose(verbose)
00027 {
00028 state.init(checkmator);
00029 }
00030
00031 osl::brinkmate::
00032 Searcher::~Searcher()
00033 {
00034 }
00035
00036 const osl::Move osl::brinkmate::
00037 Searcher::search(HashEffectState& state, int depth)
00038 {
00039 max_depth = depth;
00040 int t = 60;
00041 int c = 120;
00042 int d = 0;
00043 int r = 60;
00044 BrinkmateResult last_result = UNKNOWN;
00045 int solution_depth = -1;
00046 try
00047 {
00048 while (true)
00049 {
00050 if (verbose)
00051 std::cerr << "threatmate " << t
00052 << ", checkmate " << c
00053 << ", defense check " << d
00054 << ", checkmate-1 " << r << "\n";
00055 for (int i=1; i<=depth; i++)
00056 {
00057 if (verbose)
00058 std::cerr << "depth " << i
00059 << ", count " << count
00060 << ", table " << table.size() << "\n";
00061 last_result = search(state, i, t, c, d, r);
00062 if (solution_depth <= i)
00063 {
00064 showBestMoves();
00065 if (isAttackSuccess(last_result))
00066 {
00067 solution_depth = i;
00068 if (verbose)
00069 {
00070 std::cerr << "success!" << " count " << count
00071 << " / " << table.size()
00072 << ", result " << last_result << "\n";
00073 }
00074 break;
00075 }
00076 else
00077 {
00078 if (solution_depth >= 0)
00079 {
00080 solution_depth = -1;
00081 if (verbose)
00082 {
00083 std::cerr << "escape found!" << " count " << count
00084 << " / " << table.size()
00085 << ", result " << last_result << "\n";
00086 }
00087
00088 }
00089 }
00090 }
00091 }
00092 if (isAttackSuccess(last_result))
00093 {
00094 assert(solution_depth >= 0);
00095 r*=2;
00096 d+=1;
00097 if (r > max_threshold)
00098 break;
00099 }
00100 else
00101 {
00102 assert(solution_depth < 0);
00103 t*=2;
00104 c*=2;
00105 if (t > max_threshold)
00106 break;
00107 }
00108 }
00109 }
00110 catch(TableFull&)
00111 {
00112 if (verbose)
00113 std::cerr << "table full in brinkmate\n";
00114 }
00115 catch(std::bad_alloc&)
00116 {
00117 std::cerr << "bad alloc in brinkmate\n";
00118 this->state.setEmergency();
00119 }
00120 if (solution_depth < 0)
00121 return Move::INVALID();
00122
00123 const BrinkmateRecord *record = table.find(state.getHash());
00124 assert(record);
00125 return record->best_move;
00126 }
00127
00128 osl::brinkmate::BrinkmateResult osl::brinkmate::
00129 Searcher::search(HashEffectState& state,
00130 int depth, int tnode, int cnode,
00131 int dcm, int rnode)
00132 {
00133 assert(this->state.depth() == 0);
00134 assert(this->state.defenseCheckCount() == 0);
00135
00136 if (this->state.state() != state)
00137 {
00138 this->state.init(state);
00139 killer_moves.clear();
00140 }
00141 root_conf.depth = depth;
00142 root_conf.threatmate_node = tnode;
00143 root_conf.checkmate_node = cnode;
00144 root_conf.defense_checkmove_count = dcm;
00145 root_conf.defense_checkmate_node = rnode;
00146
00147
00148 if (! EffectUtil::isKingInCheck(state.getTurn(), state))
00149 {
00150 const bool root_threatmate
00151 = this->state.isThreatmateState(root_conf.threatmate_node);
00152 if (verbose >= report_do_undo && root_threatmate)
00153 std::cerr << "root threatmate\n";
00154 }
00155
00156
00157 const BrinkmateResult result = attack();
00158 assert(isSearchResult(result));
00159
00160 assert(this->state.depth() == 0);
00161 assert(this->state.defenseCheckCount() == 0);
00162
00163 return result;
00164 }
00165
00166 bool osl::brinkmate::
00167 Searcher::threatmateCandidate(const BrinkmateState& state, Move move,
00168 Position king)
00169 {
00170 const Position to = move.to();
00171 const Move last_move = state.lastMove();
00172 if (last_move.isNormal() && (last_move.to() != to))
00173 return true;
00174 if (Neighboring8::isNeighboring8(to, king))
00175 return true;
00176 if (Neighboring8Direct::hasEffect
00177 (state.state(), move.ptypeO(), to, king))
00178 return true;
00179 if (last_move.isNormal()
00180 && Ptype_Table.hasLongMove(last_move.ptype()))
00181 {
00182 const Piece last_piece = state.state().getPieceOnBoard(last_move.to());
00183 if (state.state().hasEffectByPiece(last_piece, to))
00184 return true;
00185 }
00186
00187 if ((move.ptype() == LANCE)
00188 && (abs(king.x() - to.x()) <= 1)
00189 && (move.isDrop() || (move.capturePtype() != PTYPE_EMPTY)))
00190 {
00191 const Offset front = Board_Table.getOffset(move.player(), U);
00192 Position rook_position = to + front;
00193 Piece rook;
00194 while ((rook = state.state().getPieceAt(rook_position)) == Piece::EMPTY())
00195 rook_position += front;
00196 if (rook.isPiece() && (unpromote(rook.ptype())==ROOK)
00197 && (rook.owner() == move.player())
00198 && ((to.y() - king.y())*front.dy() > 0))
00199 {
00200 return true;
00201 }
00202 }
00203
00204
00205 if ((move.capturePtype() == PTYPE_EMPTY)
00206 || (unpromote(move.capturePtype()) == PAWN))
00207 return false;
00208 return true;
00209 }
00210
00211 void osl::brinkmate::
00212 Searcher::setUpAttack(BrinkmateRecord *record)
00213 {
00214 const int depth_left = depthLeft();
00215 const bool in_check
00216 = EffectUtil::isKingInCheck(state.turn(), state.state());
00217 if ((record->conf.threatmate_node < root_conf.threatmate_node)
00218 || (record->conf.checkmate_node < root_conf.checkmate_node)
00219 || (record->conf.defense_checkmove_count
00220 < root_conf.defense_checkmove_count)
00221 || (record->conf.defense_checkmate_node
00222 < root_conf.defense_checkmate_node))
00223 {
00224 record->conf.depth = depth_left;
00225 if (! record->moves.empty())
00226 record->result = WORST_ATTACK;
00227 }
00228 else
00229 {
00230 record->conf.depth = std::max(record->conf.depth, depth_left);
00231 }
00232 if (record->conf.threatmate_node < root_conf.threatmate_node)
00233 {
00234 record->conf.threatmate_node = root_conf.threatmate_node;
00235 record->result = WORST_ATTACK;
00236
00237 MoveVector moves;
00238 LegalMoves::generate(state.state(), moves);
00239 if (moves.empty())
00240 {
00241 record->result = NOT_BRINKMATE;
00242 record->conf.threatmate_node = max_threshold;
00243 record->conf.checkmate_node = max_threshold;
00244 }
00245
00246 const Position raw_king
00247 = state.state().getKingPosition(alt(state.turn()));
00248 const ThreatmatePool::vector_t& candidates = pool.find(raw_king);
00249
00250 const Position king = Centering3x3::adjustCenter(raw_king);
00251 for (MoveVector::const_iterator p=moves.begin(); p!=moves.end(); ++p)
00252 {
00253 if (std::find(record->moves.begin(), record->moves.end(), *p)
00254 != record->moves.end())
00255 continue;
00256
00257 using namespace osl::move_classifier;
00258 if (PlayerMoveAdaptor<Check>::isMember(state.state(), *p))
00259 {
00260
00261 record->moves.push_back(*p);
00262 continue;
00263 }
00264 bool is_candidate = threatmateCandidate(state, *p, king);
00265 if ((state.depth() > 0) && (! in_check)
00266 && (std::find(candidates.begin(), candidates.end(), *p)
00267 == candidates.end())
00268 && (! is_candidate))
00269 continue;
00270
00271
00272 state.push(*p, false);
00273 const int tnode = (state.depth() && is_candidate
00274 && (root_conf.threatmate_node > 400))
00275 ? 26000 : root_conf.threatmate_node;
00276 const ProofDisproof threatmate = state.testThreatmateState(tnode);
00277 if (threatmate.isCheckmateSuccess())
00278 {
00279 record->moves.push_back(*p);
00280 pool.add(*p, raw_king);
00281 }
00282 else if (threatmate.isUnknown())
00283 {
00284 record->result = NOT_BRINKMATE;
00285 }
00286
00287 state.pop();
00288 }
00289 if (in_check)
00290 std::sort(record->moves.begin(), record->moves.end(),
00291 move_order::CaptureEstimation(state.state()));
00292 if (record->moves.empty())
00293 {
00294 if (in_check)
00295 record->result = INVERSE_CHECKMATE;
00296 else
00297 record->result = NOT_BRINKMATE;
00298 }
00299 }
00300 record->conf.checkmate_node = std::max(record->conf.checkmate_node,
00301 root_conf.checkmate_node);
00302 record->conf.defense_checkmove_count
00303 = std::max(record->conf.defense_checkmove_count,
00304 root_conf.defense_checkmove_count);
00305 record->conf.defense_checkmate_node
00306 = std::max(record->conf.defense_checkmate_node,
00307 root_conf.defense_checkmate_node);
00308 }
00309
00310 bool osl::brinkmate::
00311 Searcher::attack(BrinkmateRecord *record, Move todo)
00312 {
00313 if (verbose >= report_do_undo)
00314 std::cerr << std::string(state.depth(),'+') << todo << "\n";
00315 const Move last_move = state.lastMove();
00316
00317 record->is_visited = true;
00318 const bool take_back
00319 = state.lastMove().isNormal() && (last_move.to() == todo.to())
00320 && (! state.state().hasEffectBy(alt(todo.player()), todo.to()));
00321 const bool in_check = EffectUtil::isKingInCheck(state.turn(), state.state());
00322 state.push(todo, take_back || in_check);
00323 const BrinkmateResult result = defense();
00324 state.pop();
00325 record->is_visited = false;
00326
00327 assert(isSearchResult(result));
00328 record->result = betterForAttack(record->result, result);
00329
00330 if (isAttackSuccess(result))
00331 {
00332 if (verbose >= report_do_undo)
00333 std::cerr << "threat\n";
00334 record->best_move = todo;
00335 if (last_move.isNormal())
00336 killer_moves.setMove(last_move, todo);
00337 return true;
00338 }
00339 return false;
00340 }
00341
00342 osl::brinkmate::BrinkmateResult osl::brinkmate::
00343 Searcher::attack()
00344 {
00345 ++count;
00346 assert(state.turn() == table.attacker);
00347 if (stop_flag && (*stop_flag == Alarm::TIMEOUT))
00348 throw TableFull();
00349
00350 if (state.isWinningState(root_conf.checkmate_node))
00351 {
00352 BrinkmateRecord *record = table.allocate(state.state().getHash());
00353 record->result = CHECKMATE;
00354 record->conf.depth = max_threshold;
00355 record->conf.defense_checkmove_count = max_threshold;
00356 record->conf.defense_checkmate_node = max_threshold;
00357 return record->result;
00358 }
00359 const int depth_left = depthLeft();
00360 if (depth_left <= 0)
00361 return NOT_BRINKMATE;
00362 BrinkmateRecord *record = table.allocate(state.state().getHash());
00363 assert(record);
00364 record->visit_count++;
00365 if (record->is_visited)
00366 return LOOP_DETECTION;
00367 if (provedByRecord(*record))
00368 return record->result;
00369 if (disprovedByRecord(*record))
00370 return record->result;
00371 setUpAttack(record);
00372
00373 if (record->best_move.isNormal() && attack(record, record->best_move))
00374 return record->result;
00375 MoveVector killers;
00376 #ifdef BRINKMATE_BIGRAM_KILLERS
00377 killer_moves.getMove(state.state(), state.lastMove(), killers);
00378 for (MoveVector::const_iterator p=killers.begin(); p!=killers.end(); ++p)
00379 {
00380 if ((*p != record->best_move)
00381 && (std::find(record->moves.begin(), record->moves.end(), *p)
00382 != record->moves.end()))
00383 {
00384 if (attack(record, *p))
00385 return record->result;
00386 }
00387 }
00388 #endif
00389 for (BrinkmateRecord::vector_t::const_iterator p=record->moves.begin();
00390 p!=record->moves.end(); ++p)
00391 {
00392 if (record->best_move == *p)
00393 continue;
00394 if (killers.isMember(*p))
00395 continue;
00396 if (attack(record, *p))
00397 return record->result;
00398 }
00399
00400 return record->result;
00401 }
00402
00403 void osl::brinkmate::
00404 Searcher::setUpDefense(BrinkmateRecord *record)
00405 {
00406 const int depth_left = depthLeft();
00407 if ((record->conf.threatmate_node < root_conf.threatmate_node)
00408 || (record->conf.checkmate_node < root_conf.checkmate_node)
00409 || (record->conf.defense_checkmove_count
00410 < root_conf.defense_checkmove_count)
00411 || (record->conf.defense_checkmate_node
00412 < root_conf.defense_checkmate_node))
00413 {
00414 record->conf.depth = depth_left;
00415 if (! record->moves.empty())
00416 record->result = WORST_DEFENSE;
00417 }
00418 else
00419 {
00420 record->conf.depth = std::max(record->conf.depth, depth_left);
00421 }
00422 if (record->moves.empty())
00423 {
00424 MoveVector all_moves;
00425 LegalMoves::generate(state.state(), all_moves);
00426 for (MoveVector::const_iterator p=all_moves.begin(); p!=all_moves.end(); ++p)
00427 {
00428 if (state.isEffectiveDefense(*p))
00429 {
00430 record->moves.push_back(*p);
00431 }
00432 }
00433 std::sort(record->moves.begin(), record->moves.end(),
00434 move_order::CaptureEstimation(state.state()));
00435 }
00436 record->conf.threatmate_node = std::max(record->conf.threatmate_node,
00437 root_conf.threatmate_node);
00438 record->conf.checkmate_node = std::max(record->conf.checkmate_node,
00439 root_conf.checkmate_node);
00440 record->conf.defense_checkmove_count
00441 = std::max(record->conf.defense_checkmove_count,
00442 root_conf.defense_checkmove_count);
00443 record->conf.defense_checkmate_node
00444 = std::max(record->conf.defense_checkmate_node,
00445 root_conf.defense_checkmate_node);
00446
00447 record->result = record->moves.empty() ? CHECKMATE : WORST_DEFENSE;
00448 }
00449
00450 bool osl::brinkmate::
00451 Searcher::defense(BrinkmateRecord *record, Move todo)
00452 {
00453 using namespace move_classifier;
00454 const bool is_check
00455 = PlayerMoveAdaptor<Check>::isMember(state.state(), todo);
00456 const Move last_move = state.lastMove();
00457 const Piece last_piece = state.state().getPieceOnBoard(last_move.to());
00458 const Player defender = todo.player();
00459 bool is_sacrifice = false;
00460 {
00461 const int d = state.state().countEffect(defender, todo.to())
00462 + (todo.isDrop() ? 1 : 0);
00463 const int a = state.state().countEffect(alt(defender), todo.to());
00464 if (d <= 1)
00465 {
00466 if (a - d >= 0)
00467 is_sacrifice = true;
00468 }
00469 else if ((d == 2) && todo.isDrop())
00470 {
00471 const Position king = state.state().getKingPosition(defender);
00472 if (Neighboring8::isNeighboring8(king, todo.to())
00473 && (a + AdditionalEffect::count2(state.state(), todo.to(),
00474 alt(defender)) >= 2))
00475 is_sacrifice = true;
00476 }
00477 }
00478
00479 const bool is_check_or_similar = is_check || is_sacrifice;
00480 if (is_check_or_similar &&
00481 (root_conf.defense_checkmove_count <= state.defenseCheckCount()))
00482 {
00483 record->result = betterForDefense(record->result, BRINKMATE);
00484 return false;
00485 }
00486
00487 if (verbose >= report_do_undo)
00488 std::cerr << std::string(state.depth(),'+') << todo << "\n";
00489 record->is_visited = true;
00490 state.push(todo, is_check_or_similar);
00491 const BrinkmateResult result = attack();
00492 state.pop();
00493 record->is_visited = false;
00494
00495 assert(isSearchResult(result));
00496 record->result = betterForDefense(record->result, result);
00497
00498 if (! isAttackSuccess(result))
00499 {
00500 if (verbose >= report_do_undo)
00501 std::cerr << "defend\n";
00502 if (last_move.isNormal())
00503 killer_moves.setMove(last_move, todo);
00504 record->best_move = todo;
00505 return true;
00506 }
00507 return false;
00508 }
00509
00510
00511 osl::brinkmate::BrinkmateResult osl::brinkmate::
00512 Searcher::defense()
00513 {
00514 ++count;
00515 assert(alt(state.turn()) == table.attacker);
00516 if (state.isWinningState(0))
00517 return INVERSE_CHECKMATE;
00518 const int depth_left = depthLeft();
00519 const bool in_check = EffectUtil::isKingInCheck(state.turn(), state.state());
00520
00521 if (depth_left <= 0)
00522 {
00523 if (in_check)
00524 {
00525 MoveVector all_moves;
00526 LegalMoves::generate(state.state(), all_moves);
00527 if (all_moves.empty())
00528 return CHECKMATE;
00529 }
00530 return NOT_BRINKMATE;
00531 }
00532
00533 BrinkmateRecord *record = table.allocate(state.state().getHash());
00534 assert(record);
00535 record->visit_count++;
00536 if (record->is_visited)
00537 return LOOP_DETECTION;
00538 if (provedByRecord(*record))
00539 return record->result;
00540 if (disprovedByRecord(*record))
00541 return record->result;
00542
00543 setUpDefense(record);
00544
00545 if (record->best_move.isNormal() && defense(record, record->best_move))
00546 return record->result;
00547 MoveVector killers;
00548 #ifdef BRINKMATE_BIGRAM_KILLERS
00549 killer_moves.getMove(state.state(), state.lastMove(), killers);
00550 for (MoveVector::const_iterator p=killers.begin(); p!=killers.end(); ++p)
00551 {
00552 if ((*p != record->best_move)
00553 && (std::find(record->moves.begin(), record->moves.end(), *p)
00554 != record->moves.end()))
00555 {
00556 if (defense(record, *p))
00557 return record->result;
00558 }
00559 }
00560 #endif
00561 for (BrinkmateRecord::vector_t::const_iterator p=record->moves.begin();
00562 p!=record->moves.end(); ++p)
00563 {
00564 if (record->best_move == *p)
00565 continue;
00566 if (killers.isMember(*p))
00567 continue;
00568 if (defense(record, *p))
00569 return record->result;
00570 }
00571
00572 const ProofDisproof attack_back
00573 = state.testWinningState(root_conf.defense_checkmate_node);
00574 if (attack_back.isCheckmateSuccess())
00575 {
00576 if (verbose >= report_do_undo)
00577 std::cerr << "attack_back\n";
00578 record->result = INVERSE_CHECKMATE;
00579 return record->result;
00580 }
00581 else if (attack_back.isUnknown())
00582 {
00583 record->result = betterForDefense(record->result, BRINKMATE);
00584 }
00585 if ((record->result == CHECKMATE) && (! in_check))
00586 record->result = BRINKMATE;
00587 return record->result;
00588 }
00589
00590 bool osl::brinkmate::
00591 Searcher::provedByRecord(const BrinkmateRecord& record) const
00592 {
00593 if (record.result == CHECKMATE)
00594 return true;
00595 if (record.result != BRINKMATE)
00596 return false;
00597 return (record.conf.depth >= depthLeft())
00598 && (record.conf.defense_checkmove_count
00599 >= root_conf.defense_checkmove_count)
00600 && (record.conf.defense_checkmate_node
00601 >= root_conf.defense_checkmate_node);
00602 }
00603
00604 bool osl::brinkmate::
00605 Searcher::disprovedByRecord(const BrinkmateRecord& record) const
00606 {
00607 if (record.result == INVERSE_CHECKMATE)
00608 return true;
00609 if (record.result == LOOP_DETECTION)
00610 return true;
00611 if (record.result != NOT_BRINKMATE)
00612 return false;
00613 return (record.conf.depth >= depthLeft())
00614 && (record.conf.threatmate_node >= root_conf.threatmate_node)
00615 && (record.conf.checkmate_node >= root_conf.checkmate_node);
00616 }
00617
00618 void osl::brinkmate::
00619 Searcher::showBestMoves() const
00620 {
00621 HashKey key = state.state().getHash();
00622 const BrinkmateRecord *record = table.find(key);
00623 while (record && (! record->moves.empty()))
00624 {
00625 Move best_move = record->best_move;
00626 if (! best_move.isNormal())
00627 {
00628 int max_depth = 0;
00629 for (BrinkmateRecord::vector_t::const_iterator p=record->moves.begin();
00630 p!=record->moves.end(); ++p)
00631 {
00632 const HashKey new_key = key.newHashWithMove(*p);
00633 const BrinkmateRecord *new_record = table.find(new_key);
00634 if (new_record && new_record->conf.depth > max_depth)
00635 {
00636 max_depth = new_record->conf.depth;
00637 best_move = *p;
00638 }
00639 }
00640 }
00641 std::cerr << record::csa::show(best_move)
00642 << " " << record->result << " ";
00643 if ((record->result == CHECKMATE)
00644 || (record->result == INVERSE_CHECKMATE))
00645 break;
00646 if (! best_move.isNormal())
00647 break;
00648 key = key.newHashWithMove(best_move);
00649 record = table.find(key);
00650 }
00651 std::cerr << "\n";
00652 }
00653
00654 void osl::brinkmate::
00655 Searcher::showTree(const HashKey& key, int depth) const
00656 {
00657 const BrinkmateRecord *record = table.find(key);
00658 if (! record)
00659 return;
00660 if (depth >= max_depth + root_conf.defense_checkmove_count)
00661 return;
00662 std::cerr << record->result << " t " << record->conf.threatmate_node
00663 << " v " << record->visit_count
00664 << " d " << record->conf.depth
00665 << " b " << record::csa::show(record->best_move)
00666 << "\n";
00667 if (record->best_move.isNormal())
00668 {
00669 std::cerr << std::string(depth,'*')
00670 << record::csa::show(record->best_move)
00671 << "\n";
00672 const HashKey new_key = key.newHashWithMove(record->best_move);
00673 showTree(new_key, depth+1);
00674 }
00675 else
00676 {
00677 for (BrinkmateRecord::vector_t::const_iterator p=record->moves.begin();
00678 p!=record->moves.end(); ++p)
00679 {
00680 std::cerr << std::string(depth,'*')
00681 << record::csa::show(*p)
00682 << "\n";
00683 const HashKey new_key = key.newHashWithMove(*p);
00684 showTree(new_key, depth+1);
00685 }
00686 }
00687 }
00688
00689
00690
00691
00692