/* this structure is meant to include data determining performance
of the search routine, such as timing method, available time
or depth, as well as boolean flags for additional heuristics
*/struct sSearchDriver {int DEPTH;};extern sSearchDriver d;/* this structure contains some statistical data about current search */struct sSearchStat {int nodes;int qnodes;}extern sSearchStat stat;
#include "stdafx.h"
#define MAX_DEPTH 100#define LEAVES_IN_TT 1
/* symbols used to enhance readability */#define DO_NULL 1#define NO_NULL 0#define IS_PV 1#define NO_PV 0
int AlphaBeta(int depth, int alpha, int beta, int can_null, int is_pv ){int val;char bestmove;char tt_move;int tt_flag = TT_ALPHA;int in_check;int legal_move =0;int raised_alpha =0;
/* Check for timeout */if(!time_over &&!(sd.nodes&0x3FF))
time_over = time_stop();
/***************************************************************
* Are we in check? If so, extend. It also means that program *
* will never enter quiescence search while in check. *
***************************************************************/
/***************************************************************
* At leaf nodes we do quiescence search (captures only) *
* to make sure that only relatively quiet positions *
* with no hanging pieces will be evaluated. *
***************************************************************/
if( depth ==0){
val = Quiesce(alpha, beta);
if( LEAVES_IN_TT )
tt_saveLeaf( alpha, beta, val );
return val;}
sd.nodes++;
if( isRepetition())return contempt;
if(( val = tt_probe(depth, alpha, beta, &tt_move))!= INVALID )return val;/***************************************************************
* Here we introduce null move pruning. It means allowing *
* opponent to execute two moves in a row, i.e. capturing *
* something and escaping a recapture. If this cannot wreck *
* our position, then it is so good that there's no point *
* in searching further. The flag "can_null" ensures we don't *
* do two null moves in a row. Null move is not used in the *
* endgame because of the risk of zugzwang. *
***************************************************************/
/**************************************************
* Now it's time to loop through the move list *
***************************************************/for(int i =0; i < mcount; i++){
movegen_sort( mcount, m, i );
if( m[i].piece_cap== PIECE_KING )return INFINITY;
// problem: we do this test several times, even though// king capture is sorted fist
move_make( m[i]);/*******************************************************************
* The code below introduces principle variation search. It means *
* that once we are in a PV-node (indicated by IS_PV flag) and we *
* have found a move that raises alpha, we assume that the rest *
* of moves ought to be refuted. This is done relatively cheaply *
* by using a null-window search centered around alpha. Only if *
* this search fails high, we are forced to do a real one. This is *
* not done when the remaining depth is less than 2 plies. *
*******************************************************************/
if(!is_pv || depth <3)// non-pv node or low depth - don't use pvs
val =-AlphaBeta( depth-1, -beta, -alpha, DO_NULL, NO_PV );else{if(!raised_alpha)// alpha isn't raised - full width search
val =-AlphaBeta( depth-1, -beta, -alpha, DO_NULL, IS_PV );else{// first try to refute a move - if this fails, do a real searchif(-AlphaBeta( depth-1, -alpha-1, -alpha, DO_NULL, NO_PV )> alpha )
val =-AlphaBeta( depth-1, -beta, -alpha, DO_NULL, IS_PV );}}
move_unmake(m[i]);
/********************************************************************
* If the move doesn't return -INFINITY, it means that the King *
* couldn't be captured immediately. So the move was legal. In this *
* case we increase the legal_move counter, to look afterwards, *
* whether there were any legal moves on the board at all. * *
********************************************************************/
legal_move +=( val !=-INFINITY );
if( time_over )return0;/********************************************************************
* Beta cutoff - the position is so good that the score will not *
* be accepted one ply below. *
********************************************************************/
if( val >= beta ){
bestmove = m[i].id;// bugfix 2008-07-18
sd.history[m[i].from][m[i].to]+= depth*depth;#ifdef USE_KILLERS/* if a move isn't a capture, save it as a killer move */if( m[i].piece_cap== PIECE_EMPTY ){
/* make sure killer moves are different
before saving secondary killer move */if( m[i].from!= sd.killers[depth][0].from||
m[i].to!= sd.killers[depth][0].to)
sd.killers[depth][1]= sd.killers[depth][0];
/* save primary killer move */
sd.killers[depth][0]= m[i];}#endif
tt_save(depth, beta, TT_BETA, bestmove);return beta;}/****************************************************************
* We can improve over alpha, so we change the node value *
* together with the expected move. Also the raised_alpha flag, *
* used to decide about PVS, is set. *
****************************************************************/if( val > alpha ){
raised_alpha =1;
tt_flag = TT_EXACT;
alpha = val;
bestmove = m[i].id;}}// end of looping through the moves
/* Checkmate and stalemate detection */if(!legal_move ){
bestmove =-1;
int info_pv(int val ){char buffer[2048];char score[10];char pv[2048];
if(abs( val )< INFINITY -2000){sprintf( score,"cp %d", val );}else{//the mating value is returned in moves not pliesif(val >0)sprintf( score,"mate %d",(INFINITY - val+1)/2);elsesprintf( score,"mate %d",(-INFINITY - val+1)/2);}
Table of Contents
Header
#include "stdafx.h"sSearchDriver sd;/* Check extension is done also at the root *///info_currmove(m[i],i);/* the "if" line introduces PVS at root */}/*************************************************************** * Are we in check? If so, extend. It also means that program * * will never enter quiescence search while in check. * ***************************************************************//*************************************************************** * At leaf nodes we do quiescence search (captures only) * * to make sure that only relatively quiet positions * * with no hanging pieces will be evaluated. * ***************************************************************/smove m[256]; int mcount = movegen( m, tt_move ); #ifdef USE_KILLERS /* reorder killer moves */ for ( int j=1; j<mcount; j++ ) {/******************************************************************** * If the move doesn't return -INFINITY, it means that the King * * couldn't be captured immediately. So the move was legal. In this * * case we increase the legal_move counter, to look afterwards, * * whether there were any legal moves on the board at all. * * ********************************************************************//* this function guards against overflow and allows to display correct nps for longer searches. */External calls:
Up one Level