Title: Qsearch in Clueless
Post by jdb on Mar 9th, 2009, 3:45pm
This is the Qsearch for clueless 2009.
It is only called at the start of a turn. In the main search, if there is a capture threat or a goal threat, with less than 4 steps left, the search is extended to complete the turn.
Code:
private int Quiesce(int ply, int depth, int alpha, int beta, GameState gs) throws AbortSearchException {
// Always need to have full turn available
assert (gs.getStepsRemaining() == 4);
// Check for abort search
if (abort_search) {
throw new AbortSearchException();
}
// Get a gamestate to work with
GameState new_gs = gs_stack[ply];
// Keep track of how many nodes we have searched
q_nodes_searched++;
// Test for a goal on first step
goal_calls++;
if (goal.test(gs)) {
goal_hits++;
return SCORE_MATE - (depth >>> 2);
}
// If we do nothing, can opponent goal?
if (use_qdefend_search) {
// There is no point in calling this recursively
// The Qsearch will just stand pat
if (depth == max_qsearch_depth) {
// 8 ply goal search
new_gs.playPASS(gs);
goal_calls++;
if (goal.test(new_gs)) {
// SearchTrace(ply, "QS: Goal Threat");
// Opponent can goal, OMG, look for a defence
if (!QuiesceDefendGoal(ply, gs)) {
// SearchTrace(ply, "QS: No Defence to goal threat");
return -SCORE_MATE + 1 + (depth >> 2);
}
// SearchTrace(ply, "QS: Defence found");
}
}
}
// Get a stand pat score
int score = eval.Evaluate(gs, false);
// Limit depth of q search
if (depth <= 0) {
return score;
}
// SearchTrace(ply, "QStand pat score: " + score);
if (score > alpha) {
if (score >= beta) {
return score;
}
alpha = score;
}
// Iterate thru all capture moves
for (long move = qsms[ply].getFirstMove(gs); move != NEW_NO_STEP; move = qsms[ply].getNextMove(gs)) {
int steps = new_gs.play(move, gs);
if (show_alphabeta_search_trace) {
// SearchTrace(ply, -1, alpha, beta, move);
}
if (new_gs.isGameOver()) {
// Note must search rest of possible moves!!!
score = new_gs.getGameResult();
} else {
// Game is NOT over, so we search
int new_ply = ply + steps;
score = -Quiesce(new_ply, depth - 1, -beta, -alpha, new_gs);
}
if (score > alpha) {
if (score >= beta) {
return score;
}
alpha = score;
}
}
return alpha;
}
/**
* Opponent has a goal threat, looks for a defence
*
* @param ply
* @param steps_available
* @param gs
* @return TRUE iff there is a defence to the goal threat
*/
public boolean QuiesceDefendGoal(int ply, GameState gs) throws AbortSearchException {
assert (gs.getStepsRemaining() == 4);
// Best defence is to goal our own rabbit!
if (goal.test(gs)) {
// QSearchTrace(ply, "QDefend: Defender can goal");
return true;
}
// Try qdefend killer moves
GameState new_gs = gs_stack[ply];
for (long move : qdefend_killers[ply]) {
// QSearchTrace(ply, "QDEFKILLER: " + GameState.move_toString(move));
if (new_gs.isLegalMove(move, gs)) {
new_gs.play(move, gs);
// Check if move ends the game
if (new_gs.isGameOver()) {
int score = new_gs.getGameResult();
// We created a win for the enemy, not good
if (score == -SCORE_MATE) {
continue;
}
// We created a win for ourself, great
if (score == SCORE_MATE) {
return true;
}
}
assert (new_gs.isFirstStep());
if (!goal.test(new_gs)) {
// QSearchTrace(ply, "QDefend: Killer move " + GameState.move_toString(move));
return true;
}
}
}
// No known defence, so we must search
// Use iterative deepening, in case there is an easy defence
for (int def_depth = 1; def_depth <= 4; def_depth++) {
// QSearchTrace(ply, "QDefend Starting depth: " + def_depth);
if (QuiesceDefendInternal(ply, def_depth, gs, 0)) {
// QSearchTrace(ply, "QDefend: Searched Defence found " + GameState.move_toString(qdefend_killers[ply][0]));
return true;
}
}
return false;
}
/**
* Internal quiesce defend
* Handles the recursive defence search
*
* @param ply
* @param depth
* @param gs
* @param partial_move
* @return
*/
private boolean QuiesceDefendInternal(int ply, int depth, GameState gs, long partial_move)
throws AbortSearchException {
// Check for abort search
if (abort_search) {
throw new AbortSearchException();
}
GameState new_gs = gs_stack[ply];
long moves[] = qmove_list_stack[ply];
moves[0] = 0;
long steps_available = gs.getStepsRemaining();
// Probe hash table
long probe_result = probeQHash(gs.getZobristPositionHash(), depth, q_hash_defend_table);
if (probe_result == QHASH_DEFEND_WIN) {
return true;
}
if (probe_result == QHASH_DEFEND_LOSS) {
return false;
}
for (long move = qdms[ply].getFirstMove(gs); move != NEW_NO_STEP; move = qdms[ply].getNextMove(gs)) {
// QSearchTrace(ply, depth, move);
q_defence_nodes_searched++;
int steps = new_gs.play(move, gs);
int new_ply = ply + steps;
int new_depth = depth - steps;
long new_partial_move = partial_move | (move << (16 * (4 - steps_available)));
if (new_depth <= 0) {
// Complete the player's turn
if (new_gs.getStepsRemaining() != 4) {
new_partial_move |= (NEW_PASS_MOVE << (16 * (4 - new_gs.getStepsRemaining())));
new_gs.playPASS(new_gs);
}
// Check if move ends the game
if (new_gs.isGameOver()) {
int score = new_gs.getGameResult();
// We created a win for the enemy, not good
if (score == -SCORE_MATE) {
continue;
}
// We created a win for ourself, great
if (score == SCORE_MATE) {
record_qdefend_move(ply, new_partial_move);
return true;
}
}
// Check if move prevents an enemy goal
if (!goal.test(new_gs)) {
record_qdefend_move(ply, new_partial_move);
return true;
}
}
// depth remains, so search deeper
else {
boolean result = QuiesceDefendInternal(new_ply, new_depth, new_gs, new_partial_move);
if (result) {
return true;
}
}
}
// Store search result in hash table
storeQHash(gs.getZobristPositionHash(), depth, QHASH_DEFEND_LOSS, q_hash_defend_table);
return false;
} |
|
|