/***********************************************************************************
* Filename $RCSfile: alg1_search.c,v $
* Current CVS $Revision: 1.25 $
* Checked-in by $Author: yves $
*
* $Log: alg1_search.c,v $
*
***********************************************************************************/
#include "belofte.h"
#include "usercmd.h"
#include "alg1_search.h"
#include "alg1_moves.h"
#include "alg1_eval.h"
#include "alg1_book.h"
#include "alg1_board.h"
// --------------------------------------------------------------------
t_alg1_moves m1_movelist;
// --------------------------------------------------------------------
extern t_alg1_board m1_board;
extern t_alg1_board m1_boardmapper;
extern struct st_history m_boardhistory[MAX_GAME_LENGTH];
// --------------------------------------------------------------------
extern int curply;
extern int time_left;
extern int post_mode;
extern int level_mode;
extern int random_mode;
extern int maxdepth;
extern int engine_level;
// --------------------------------------------------------------------
static int iCurPly; // local search buffer to find the current ply while iterating
static int iMaxDepth;
static t_boolean bCountOnly;
static int iStoredMoves;
// --------------------------------------------------------------------
static void fill_movegenerationbuffers(void);
static int select_move(const t_score fScore, const int iDepth);
static t_score search_selectmove(t_depth fDepth, t_score fAlpha, t_score fBeta, t_boolean bQuieuscience);
static void add_singlemove(const posid iFrom, const posid iTo, const t_promotion cFlag);
static void fill_movesforpiecewhite(const posid iPos, const t_piece cPiece, const t_boolean bQuieuscience);
static void fill_movesforpieceblack(const posid iPos, const t_piece cPiece, const t_boolean bQuieuscience);
static void fill_movesforknightwhite(const posid iPos, const t_boolean bQuieuscience);
static void fill_movesforknightblack(const posid iPos, const t_boolean bQuieuscience);
static void fill_movesforpieceonewhite(const posid iPos, const posid iResult, const t_boolean bQuieuscience);
static void fill_movesforpieceoneblack(const posid iPos, const posid iResult, const t_boolean bQuieuscience);
static void fill_movesforpiecedir(const posid iPos, t_colour iCaptureAllowedColour,
const int iDir, const int iRep, const t_boolean bQuieuscience);
static void fill_movesforkingwhite(const posid iPos, const t_boolean bQuieuscience);
static void fill_movesforkingblack(const posid iPos, const t_boolean bQuieuscience);
static void fill_movesforpawnwhite(const posid iPos, const int iDir, const t_boolean bQuieuscience);
static void fill_movesforpawnblack(const posid iPos, const int iDir, const t_boolean bQuieuscience);
static int isInCheckAfterMove(const posid iFrom, const posid iTo, const t_promotion cFlag);
static t_boolean pieceseesmore(const posid iPiecePos, const t_piece cPieceToLookFor1,
const t_piece cPieceToLookFor2, const t_boolean bEvaluateForWhite,
const int iJump, const int iCount);
#define isEndPosition(f) (((f)<=-SCORE_ALMOST_WON)||((f)>=SCORE_ALMOST_WON))
/*----------------------------------------------------------------------+
| I/O functions |
+----------------------------------------------------------------------*/
/**
* function called once for engine construction
*/
void search_constructor(void) {
fill_movegenerationbuffers();
fill_moveevalbuffers();
}
/**
* function called once for new game, here the board position is copied from the board into the engine
* calling this function will cause ep, rock and repetition and 50 moves flags to be reset
*/
void search_init(void) {
search_initboard();
}
/**
* return 0 in case of some problem
* return 1 in case of ok
*/
int search_root(char *szMove, const int iLenMove) {
t_score fScore;
int iSelectedMove;
int iMovesLeft;
int iCalculatedDepth = maxdepth;
char szMessage[MAX_DATANAME_LENGTH];
iCurPly = curply;
bCountOnly = myFALSE;
if (iLenMove < 8) return 0; // some error, return right away
szMove[0] = '\0';
usercmd_delayedconstructor(); // in case we are not in xboard mode and the protover
// command is not called, make sure it gets called upon the first move
if (book_move(m_boardhistory[curply].szFEN, szMove)) {
// here perform opening book move and return
cmdresp_snd_info("book move");
return 1;
}
if (level_mode == 2) {
iMovesLeft = max((30 - curply) / 2, 10);
// increase depth if there is enough time left
// TODO: adjust parameters dynamically depening on game
if ((iCalculatedDepth < 2) && ((time_left / iMovesLeft) > 1)) iCalculatedDepth = 2;
if ((iCalculatedDepth < 3) && ((time_left / iMovesLeft) > 2)) iCalculatedDepth = 3;
if ((iCalculatedDepth < 4) && ((time_left / iMovesLeft) > 5)) iCalculatedDepth = 4;
if ((iCalculatedDepth < 5) && ((time_left / iMovesLeft) > 10)) iCalculatedDepth = 5;
if ((iMovesLeft > 25) && (iCalculatedDepth < 5) && (iCalculatedDepth > 0)) iCalculatedDepth++;
// decrease to avoid out of time
if ((time_left < 10) && (iCalculatedDepth > 2)) iCalculatedDepth = 2;
if ((time_left < 30) && (iCalculatedDepth > 3)) iCalculatedDepth = 3;
if ((time_left < 60) && (iCalculatedDepth > 4)) iCalculatedDepth = 4;
} else if (level_mode == 1) {
if (engine_level <= 2) {
iCalculatedDepth = 2;
} else {
iCalculatedDepth = 5;
}
}
iMaxDepth = iCalculatedDepth + MAX_DEPTH_EXTENTION; // inverted because we will go below zero
sprintf(szMessage, "Starting search depth: %d, maxdepth: %d, mode: %d",
iCalculatedDepth, iMaxDepth, level_mode);
cmdresp_snd_info(szMessage);
// we found a score of what is a good move
fScore = search_selectmove((t_depth) iCalculatedDepth, -SCORE_WON, SCORE_WON, myFALSE);
// when we return the moves, we need to use an 8x8 board, not the internal one
// we do it here, so we can use the moves generated to print out the evaluation results
normalize_movelist();
// now find in the list of moves the move with the corresponding score
iSelectedMove = select_move(fScore, iCalculatedDepth);
if (iSelectedMove >= 0) {
if (fScore < -14) {
if (iCurPly & 1) {
// black resigns
strcpy(szMove, "-4");
} else {
// white resigns
strcpy(szMove, "-5");
}
return 0;
} else {
search_printablemove(iSelectedMove, szMove);
return 1;
}
} else {
if (isInCheck(!(iCurPly & 1)) == 1) {
// in check, so mate
if (iCurPly & 1) {
// white wins
strcpy(szMove, "-3");
} else {
// black to move, and no move, so black wins
strcpy(szMove, "-2");
}
} else {
// not in check but still no move found: stalemate
strcpy(szMove, "-1");
}
}
return 0; // some problem, unidentified
}
// --------------------------------------------------------------------
void search_printablemove(const int iSelectedMove, char *szMove) {
char szPromotion[3];
// we found a move
if (m1_movelist.m1_moves[iSelectedMove].bFlag) {
// promotion flag is set, so write out = plus piece
sprintf(szPromotion, "%c", m1_movelist.m1_moves[iSelectedMove].bFlag);
} else {
szPromotion[0] = '\0';
}
// store it intermediately so we can use the move for internal housekeeping tasks
sprintf(szMove, "%c%c%c%c%s",
M1_LIJN(m1_movelist.m1_moves[iSelectedMove].ucFrom) + 'a',
M1_RIJ(m1_movelist.m1_moves[iSelectedMove].ucFrom) + '1',
M1_LIJN(m1_movelist.m1_moves[iSelectedMove].ucTo) + 'a',
M1_RIJ(m1_movelist.m1_moves[iSelectedMove].ucTo) + '1',
szPromotion);
}
/**
* when we enter, we know we can overwrite the board and the movelist variables
* the initial score is passed along to force cut-offs
* return the best score in the movelist
*
* three functions are available
* the first being the root search function, here all moves are always searched
* the second being an alpha-beta optimized function, for each sub-level
*/
static t_score search_selectmove(t_depth fDepth, t_score fAlpha, t_score fBeta, t_boolean bQuieuscience) {
int iMoves;
int i;
t_score fResult;
#if defined(_DEBUG)
char currentBest[20];
#endif
//byte cDestField;
//byte cSourceField;
t_alg1_board m1_boardbuffer;
t_alg1_moves m1_movesbuffer;
t_score fBestScore = -SCORE_WON;
// curply is even for white
iMoves = fill_movelist((iCurPly & 1) == COLOUR_BLACK, bQuieuscience, FILLMOVES);
if (iMoves > 0) {
order_moves(iMoves);
for (i = 0; i < iMoves; i++) {
// either we are looking for a non silent move or allow all possible moves
//cSourceField = m1_board.m_fields[m1_movelist.m1_moves[i].ucFrom];
//cDestField = m1_board.m_fields[m1_movelist.m1_moves[i].ucTo];
// store board position and movelist, for later restore
memcpy(&m1_boardbuffer, &m1_board, sizeof (m1_board));
memcpy(&m1_movesbuffer, &m1_movelist, sizeof (m1_movelist));
iCurPly++;
if (iCurPly & 1) {
// curply is odd for white
apply_movewhite(m1_movelist.m1_moves[i].ucFrom,
m1_movelist.m1_moves[i].ucTo,
m1_movelist.m1_moves[i].bFlag);
} else {
apply_moveblack(m1_movelist.m1_moves[i].ucFrom,
m1_movelist.m1_moves[i].ucTo,
m1_movelist.m1_moves[i].bFlag);
}
if (((int) fDepth > 1) && (m1_movelist.m1_moves[i].bNonSilent)) {
// search one level deeper
fResult = -search_selectmove(fDepth - CAPTURE_MOVE_EXTENTION, -fBeta, -fAlpha, myFALSE);
m1_movelist.m1_moves[i].iDepth = fDepth - CAPTURE_MOVE_EXTENTION;
} else if ((int) fDepth > 1) {
fResult = -search_selectmove(fDepth - SILENT_EXTENTION, -fBeta, -fAlpha, myFALSE);
m1_movelist.m1_moves[i].iDepth = fDepth - SILENT_EXTENTION;
} else if ((m1_movelist.m1_moves[i].bNonSilent)
&& (fDepth > (t_depth) iMaxDepth)
&& (bQuieuscience)) {
// quiescience search, only reaches this branch after going to depth zero in previous iteration
// so no additional test for depth greater than zero needed
// note: iDepth is negative here, iMaxDepth is even more negative
fResult = -search_selectmove(fDepth - NON_SILENT_EXTENTION, -fBeta, -fAlpha, myTRUE);
m1_movelist.m1_moves[i].iDepth = fDepth - NON_SILENT_EXTENTION;
} else {
// curply is odd for white
fResult = eval_pos(iCurPly & 1);
}
iCurPly--;
// restore old position and movelist
memcpy(&m1_movelist, &m1_movesbuffer, sizeof (m1_movelist));
memcpy(&m1_board, &m1_boardbuffer, sizeof (m1_board));
// keep the score of all moves for the higher level
m1_movelist.m1_moves[i].bValue = fResult;
if (fResult > fBestScore) fBestScore = fResult;
if (fResult >= fBeta) {
break;
}
if (fResult > fAlpha) fAlpha = fResult;
}
} else {
// there are no moves found, this can be in normal or in quieuscence
// when there are no more captures
// curply is even for white
fBestScore = eval_pos(!(iCurPly & 1));
}
// make sure the scores go to zero
if (fBestScore > DEPTH_PENALTY)
return fBestScore - DEPTH_PENALTY;
else if (fBestScore < -DEPTH_PENALTY)
return fBestScore + DEPTH_PENALTY;
return fBestScore;
}
/**
* select among one of the possible moves
* or minus one if no valid move could be found
*/
static int select_move(const t_score fScoreToBeFound, const int iDepth) {
int iIndex = 0;
char szBuffer[MAX_DATANAME_LENGTH];
int iIteration = 0;
t_score allowedDeviation = ALLOWED_DEVIATION;
// if non random, remove the width
if (random_mode == 0) allowedDeviation = 0;
qsort_moves();
if (post_mode) {
while ((iIndex < m1_movelist.m1_count) &&
((iIndex < LIST_LENGTH)
|| (m1_movelist.m1_moves[iIndex].bValue
>= (fScoreToBeFound - allowedDeviation)))) {
// print out all possible moves or best n moves
search_printablemove(iIndex, szBuffer);
cmdresp_snd_thinking(curply, m1_movelist.m1_moves[iIndex].bValue, szBuffer);
iIndex++;
}
sprintf(szBuffer, "== target at depth %d", iDepth);
cmdresp_snd_thinking(curply, fScoreToBeFound, szBuffer);
}
if (m1_movelist.m1_count) {
while (1) {
iIteration++; // make sure in case of serious trouble, to select a move
iIndex = rand() % m1_movelist.m1_count;
if ((m1_movelist.m1_moves[iIndex].bValue
>= (fScoreToBeFound - allowedDeviation))
|| (iIteration > 10000)) break;
}
return iIndex;
}
return -1;
}
/*----------------------------------------------------------------------+
| board interface functions |
+----------------------------------------------------------------------*/
/**
* generate internal buffers to speed up further working of the program
*/
static void fill_movegenerationbuffers(void) {
int iRow, iColumn;
// reset board to invalid
for (iRow = 0; iRow < 12; iRow++) {
for (iColumn = 0; iColumn < 12; iColumn++) {
m1_board.m_fields[iColumn + iRow * 12] = FIELD_BORDER;
}
}
// reset board to invalid
for (iRow = 0; iRow < 12; iRow++) {
for (iColumn = 0; iColumn < 12; iColumn++) {
m1_boardmapper.m_fields[iColumn + iRow * 12] = FIELD_BORDER;
}
}
for (iRow = 0; iRow < 8; iRow++) {
for (iColumn = 0; iColumn < 8; iColumn++) {
m1_boardmapper.m_fields[iColumn + 2 + (iRow + 2)*12] = iColumn + iRow * 8;
}
}
}
/**
* normalize the movelist to a 8x8 board
*/
void normalize_movelist(void) {
int i;
posid iFrom, iTo;
for (i = 0; i < m1_movelist.m1_count; i++) {
iFrom = m1_movelist.m1_moves[i].ucFrom;
iTo = m1_movelist.m1_moves[i].ucTo;
m1_movelist.m1_moves[i].ucFrom = MAP144TO64(iFrom);
m1_movelist.m1_moves[i].ucTo = MAP144TO64(iTo);
}
}
// --------------------------------------------------------------------
int search_apply_move(const char *szMove) {
posid iFrom;
posid iTo;
t_promotion cFlag = PROMOTION_NONE;
if (strlen(szMove) == 5)
cFlag = szMove [4];
iFrom = (2 + szMove[0] - 'a') + (2 + szMove[1] - '1')*12;
iTo = (2 + szMove[2] - 'a') + (2 + szMove[3] - '1')*12;
if (curply & 1) {
// curply is odd for white, because it is updated before this call
apply_movewhite(iFrom, iTo, cFlag);
} else {
apply_moveblack(iFrom, iTo, cFlag);
}
return 0;
}
/*----------------------------------------------------------------------+
| move generation |
+----------------------------------------------------------------------*/
/**
* fill all possible moves in the movelist
*/
int fill_movelist(const enum tColour nColour, const t_boolean bQuieuscience, const enum tFillMoves bFill) {
posid iPos;
t_piece cPiece;
int iMoves;
if (bFill) {
// if the bFill variable is set, moves are not added to the list
// but the global static variable iStoredMoves is updated
// beware, this operation is not recursive
memset(&m1_movelist, 0, sizeof (m1_movelist));
bCountOnly = myFALSE;
} else {
iStoredMoves = 0;
bCountOnly = myTRUE;
}
// we will take each pieace and generate a move for it
if (nColour == COLOUR_BLACK) {
// generate for black
for (iPos = STARTPOS; iPos < ENDPOS; iPos++) {
cPiece = m1_board.m_fields[iPos];
switch (cPiece) {
case BLACK_PAWN:
// black piece found
fill_movesforpawnblack(iPos, -12, bQuieuscience);
break;
case BLACK_KING:
fill_movesforkingblack(iPos, bQuieuscience);
break;
case BLACK_KNIGHT:
fill_movesforknightblack(iPos, bQuieuscience);
break;
case BLACK_ROOK:
case BLACK_BISHOP:
case BLACK_QUEEN:
fill_movesforpieceblack(iPos, cPiece, bQuieuscience);
break;
default:
break;
}
}
} else {
// generate for white
for (iPos = STARTPOS; iPos < ENDPOS; iPos++) {
cPiece = m1_board.m_fields[iPos];
switch (cPiece) {
case PIECE_PAWN:
// white piece found
fill_movesforpawnwhite(iPos, 12, bQuieuscience);
break;
case PIECE_KING:
fill_movesforkingwhite(iPos, bQuieuscience);
break;
case PIECE_KNIGHT:
fill_movesforknightwhite(iPos, bQuieuscience);
break;
case PIECE_ROOK:
case PIECE_BISHOP:
case PIECE_QUEEN:
fill_movesforpiecewhite(iPos, cPiece, bQuieuscience);
break;
default:
break;
}
}
}
if (bFill) {
iMoves = m1_movelist.m1_count;
} else {
iMoves = iStoredMoves;
}
return iMoves;
}
/**
* fill all possibe king moves
*/
static void fill_movesforkingwhite(const posid iPos, const t_boolean bQuieuscience) {
fill_movesforpieceonewhite(iPos, iPos + 11, bQuieuscience);
fill_movesforpieceonewhite(iPos, iPos + 12, bQuieuscience);
fill_movesforpieceonewhite(iPos, iPos + 13, bQuieuscience);
fill_movesforpieceonewhite(iPos, iPos + 1, bQuieuscience);
fill_movesforpieceonewhite(iPos, iPos - 11, bQuieuscience);
fill_movesforpieceonewhite(iPos, iPos - 12, bQuieuscience);
fill_movesforpieceonewhite(iPos, iPos - 13, bQuieuscience);
fill_movesforpieceonewhite(iPos, iPos - 1, bQuieuscience);
if (isUnderAttack(m1_board.m_whiteking, myTRUE) == 0) {
if (m1_board.m_whitecastle[CASTLE_LONG]) {
if ((m1_board.m_fields[27] == FIELD_EMPTY)
&& (m1_board.m_fields[28] == FIELD_EMPTY)
&& (m1_board.m_fields[29] == FIELD_EMPTY)
&& (isUnderAttack(29, myTRUE) == 0)) {
add_singlemove(30, 28, PROMOTION_NONE);
}
}
if (m1_board.m_whitecastle[CASTLE_SHORT]) {
if ((m1_board.m_fields[31] == FIELD_EMPTY)
&& (m1_board.m_fields[32] == FIELD_EMPTY)
&& (isUnderAttack(31, myTRUE) == 0)) {
add_singlemove(30, 32, PROMOTION_NONE);
}
}
}
}
// --------------------------------------------------------------------
static void fill_movesforkingblack(const posid iPos, const t_boolean bQuieuscience) {
fill_movesforpieceoneblack(iPos, (const posid) iPos + 11, bQuieuscience);
fill_movesforpieceoneblack(iPos, (const posid) iPos + 12, bQuieuscience);
fill_movesforpieceoneblack(iPos, (const posid) iPos + 13, bQuieuscience);
fill_movesforpieceoneblack(iPos, (const posid) iPos + 1, bQuieuscience);
fill_movesforpieceoneblack(iPos, (const posid) iPos - 11, bQuieuscience);
fill_movesforpieceoneblack(iPos, (const posid) iPos - 12, bQuieuscience);
fill_movesforpieceoneblack(iPos, (const posid) iPos - 13, bQuieuscience);
fill_movesforpieceoneblack(iPos, (const posid) iPos - 1, bQuieuscience);
if (isUnderAttack(m1_board.m_blackking, myFALSE) == 0) {
if (m1_board.m_blackcastle[CASTLE_LONG]) {
if ((m1_board.m_fields[111] == FIELD_EMPTY)
&& (m1_board.m_fields[112] == FIELD_EMPTY)
&& (m1_board.m_fields[113] == FIELD_EMPTY)
&& (isUnderAttack(113, myFALSE) == 0)) {
add_singlemove(114, 112, PROMOTION_NONE);
}
}
if (m1_board.m_blackcastle[CASTLE_SHORT]) {
if ((m1_board.m_fields[115] == FIELD_EMPTY)
&& (m1_board.m_fields[116] == FIELD_EMPTY)
&& (isUnderAttack(115, myFALSE) == 0)) {
add_singlemove(114, 116, PROMOTION_NONE);
}
}
}
}
/**
* fill all possible moves for a piece on position x
*/
static void fill_movesforpiecewhite(const posid iPos, const t_piece cPiece, const t_boolean bQuieuscience) {
if ((cPiece == PIECE_ROOK) || (cPiece == PIECE_QUEEN)) {
// calculate all rook moves
fill_movesforpiecedir(iPos, CAPTURE_COLOUR_BLACK, 12, 7, bQuieuscience);
fill_movesforpiecedir(iPos, CAPTURE_COLOUR_BLACK, 1, 7, bQuieuscience);
fill_movesforpiecedir(iPos, CAPTURE_COLOUR_BLACK, -12, 7, bQuieuscience);
fill_movesforpiecedir(iPos, CAPTURE_COLOUR_BLACK, -1, 7, bQuieuscience);
}
if ((cPiece == PIECE_BISHOP) || (cPiece == PIECE_QUEEN)) {
// calculate all rook moves
fill_movesforpiecedir(iPos, CAPTURE_COLOUR_BLACK, 13, 7, bQuieuscience);
fill_movesforpiecedir(iPos, CAPTURE_COLOUR_BLACK, 11, 7, bQuieuscience);
fill_movesforpiecedir(iPos, CAPTURE_COLOUR_BLACK, -13, 7, bQuieuscience);
fill_movesforpiecedir(iPos, CAPTURE_COLOUR_BLACK, -11, 7, bQuieuscience);
}
}
// --------------------------------------------------------------------
static void fill_movesforpieceblack(const posid iPos, const t_piece cPiece, const t_boolean bQuieuscience) {
if ((cPiece == BLACK_ROOK) || (cPiece == BLACK_QUEEN)) {
// calculate all rook moves
fill_movesforpiecedir(iPos, CAPTURE_COLOUR_WHITE, 12, 7, bQuieuscience);
fill_movesforpiecedir(iPos, CAPTURE_COLOUR_WHITE, 1, 7, bQuieuscience);
fill_movesforpiecedir(iPos, CAPTURE_COLOUR_WHITE, -12, 7, bQuieuscience);
fill_movesforpiecedir(iPos, CAPTURE_COLOUR_WHITE, -1, 7, bQuieuscience);
}
if ((cPiece == BLACK_BISHOP) || (cPiece == BLACK_QUEEN)) {
// calculate all rook moves
fill_movesforpiecedir(iPos, CAPTURE_COLOUR_WHITE, 13, 7, bQuieuscience);
fill_movesforpiecedir(iPos, CAPTURE_COLOUR_WHITE, 11, 7, bQuieuscience);
fill_movesforpiecedir(iPos, CAPTURE_COLOUR_WHITE, -13, 7, bQuieuscience);
fill_movesforpiecedir(iPos, CAPTURE_COLOUR_WHITE, -11, 7, bQuieuscience);
}
}
// --------------------------------------------------------------------
static void fill_movesforknightwhite(const posid iPos, const t_boolean bQuieuscience) {
// calculate all knights moves
fill_movesforpieceonewhite(iPos, (const posid) iPos + 25, bQuieuscience);
fill_movesforpieceonewhite(iPos, (const posid) iPos + 23, bQuieuscience);
fill_movesforpieceonewhite(iPos, (const posid) iPos + 14, bQuieuscience);
fill_movesforpieceonewhite(iPos, (const posid) iPos + 10, bQuieuscience);
fill_movesforpieceonewhite(iPos, (const posid) iPos - 25, bQuieuscience);
fill_movesforpieceonewhite(iPos, (const posid) iPos - 23, bQuieuscience);
fill_movesforpieceonewhite(iPos, (const posid) iPos - 14, bQuieuscience);
fill_movesforpieceonewhite(iPos, (const posid) iPos - 10, bQuieuscience);
}
// --------------------------------------------------------------------
static void fill_movesforknightblack(const posid iPos, const t_boolean bQuieuscience) {
// calculate all knights moves
fill_movesforpieceoneblack(iPos, (const posid) iPos + 25, bQuieuscience);
fill_movesforpieceoneblack(iPos, (const posid) iPos + 23, bQuieuscience);
fill_movesforpieceoneblack(iPos, (const posid) iPos + 14, bQuieuscience);
fill_movesforpieceoneblack(iPos, (const posid) iPos + 10, bQuieuscience);
fill_movesforpieceoneblack(iPos, (const posid) iPos - 25, bQuieuscience);
fill_movesforpieceoneblack(iPos, (const posid) iPos - 23, bQuieuscience);
fill_movesforpieceoneblack(iPos, (const posid) iPos - 14, bQuieuscience);
fill_movesforpieceoneblack(iPos, (const posid) iPos - 10, bQuieuscience);
}
/**
* add a single move
* fill cflag in case of promotion
* set cNonSilent in case of check or capture
* TODO add notion of king protector, only when moving kingprotector the incheck test needs
* to be performed
* Also, no test required for opponent check through pawn or knight
* TODO add single pawn move
*/
static void add_singlemove(const posid iFrom, const posid iTo, const t_promotion cFlag) {
int iWhoInCheck = isInCheckAfterMove(iFrom, iTo, cFlag);
if (bCountOnly) {
if (iWhoInCheck != 1)
iStoredMoves++;
} else {
auto int i = m1_movelist.m1_count;
if (iWhoInCheck != 1) {
// the player to play is not in check
m1_movelist.m1_moves[i].ucFrom = iFrom;
m1_movelist.m1_moves[i].ucTo = iTo;
m1_movelist.m1_moves[i].bFlag = cFlag;
m1_movelist.m1_moves[i].bValue = -SCORE_ALMOST_WON;
m1_movelist.m1_moves[i].iDepth = 0;
if ((m1_board.m_fields[iTo] != FIELD_EMPTY)) { // || (cFlag)) { // disable promotion non silent for debug
m1_movelist.m1_moves[i].bNonSilent = 1;
} else {
if (iWhoInCheck == 2) {
// but opponent is in check
m1_movelist.m1_moves[i].bNonSilent = 1;
}
}
m1_movelist.m1_count++;
} else {
iStoredMoves++; // for debug only, to set a breakpoint
}
}
}
/**
* add all moves in this direction for a piece
*/
static void fill_movesforpiecedir(const posid iPos, t_colour iCaptureAllowedColour,
const int iDir, const int iRep, const t_boolean bQuieuscience) {
int i;
char cPieceResult;
int isWhite;
posid iResult = iPos;
for (i = 0; i < iRep; i++) {
// repeat all moves in a direction
iResult += iDir;
cPieceResult = m1_board.m_fields[iResult];
if (cPieceResult == FIELD_EMPTY) {
// empty case, no capture move, so move possible
if (!bQuieuscience) add_singlemove(iPos, iResult, PROMOTION_NONE);
} else if (cPieceResult == FIELD_BORDER) {
// if we reach the border, we do not continue anymore
break;
} else {
// we will look if we can capture
isWhite = (!(cPieceResult & (LOWERCASEBIT)));
if ((isWhite && (iCaptureAllowedColour == COLOUR_WHITE)) || ((!isWhite) && (iCaptureAllowedColour == COLOUR_BLACK))) {
// we know that the allowed colour for capture is the colour of the destination piece
add_singlemove(iPos, iResult, PROMOTION_NONE);
}
// we still break out as we cannot take 2 pieces in a row, and cannot jump over own pieces
break;
}
}
}
/**
* add single step move
*/
static void fill_movesforpieceonewhite(const posid iPos, const posid iResult, const t_boolean bQuieuscience) {
char cPieceResult;
cPieceResult = m1_board.m_fields[iResult];
if (cPieceResult == FIELD_EMPTY) {
// empty case, no capture move, so move possible
if (!bQuieuscience) add_singlemove(iPos, iResult, PROMOTION_NONE);
} else if (cPieceResult != FIELD_BORDER) {
// we will look if we can capture
if (cPieceResult & (LOWERCASEBIT)) {
// is it a black piece?
// we know that the allowed colour for capture is the colour of the destination piece
add_singlemove(iPos, iResult, PROMOTION_NONE);
}
}
}
/**
* add single step move
*/
static void fill_movesforpieceoneblack(const posid iPos, const posid iResult, const t_boolean bQuieuscience) {
char cPieceResult;
cPieceResult = m1_board.m_fields[iResult];
if (cPieceResult == FIELD_EMPTY) {
// empty case, no capture move, so move possible
if (!bQuieuscience) add_singlemove(iPos, iResult, PROMOTION_NONE);
} else if (cPieceResult != FIELD_BORDER) {
// we will look if we can capture
// TODO: optimize by giving the bit as parameter
if (!(cPieceResult & (LOWERCASEBIT))) {
// we know that the allowed colour for capture is the colour of the destination piece
add_singlemove(iPos, iResult, PROMOTION_NONE);
}
}
}
/**
* store all promotion moves, also adjust last move so it becomes a promotion
*/
static void fill_movesforpromotion(const posid iPos, const posid iDest) {
// correct last move, it does not have the flag set
m1_movelist.m1_count--;
add_singlemove(iPos, iDest, PROMOTION_QUEEN);
add_singlemove(iPos, iDest, PROMOTION_ROOK);
add_singlemove(iPos, iDest, PROMOTION_KNIGHT);
add_singlemove(iPos, iDest, PROMOTION_BISHOP);
}
/**
* fill all possible moves for a pawn
*/
static void fill_movesforpawnwhite(const posid iPos, const int iDir, const t_boolean bQuieuscience) {
char cPieceResult;
posid iResult = iPos + iDir;
cPieceResult = m1_board.m_fields[iResult];
if (cPieceResult == FIELD_EMPTY) {
// empty case, no capture move, so move possible
if (!bQuieuscience) add_singlemove(iPos, iResult, PROMOTION_NONE);
// add check for promotion moves
if (ROW144TO64(iPos) == 6) {
// always add promotion moves to the movelist
fill_movesforpromotion(iPos, iResult);
}
// check if we can do a double move
if (ROW144TO64(iPos) == 1) {
if (m1_board.m_fields[iResult + iDir] == FIELD_EMPTY) {
if (!bQuieuscience) add_singlemove(iPos, iResult + iDir, PROMOTION_NONE);
}
}
}
cPieceResult = m1_board.m_fields[iResult - 1];
if (cPieceResult != FIELD_BORDER) {
if (cPieceResult != FIELD_EMPTY) {
// we will look if we can capture
// TODO: optimize by giving the bit as parameter
if (cPieceResult & (LOWERCASEBIT)) {
// we know that the allowed colour for capture is the colour of the destination piece
add_singlemove(iPos, iResult - 1, PROMOTION_NONE);
// add check for promotion moves
if (ROW144TO64(iPos) == 6) {
fill_movesforpromotion(iPos, iResult - 1);
}
}
} else if (iResult - 1 == m1_board.m_epfield) {
// ep move
add_singlemove(iPos, iResult - 1, PROMOTION_NONE);
}
}
cPieceResult = m1_board.m_fields[iResult + 1];
if (cPieceResult != FIELD_BORDER) {
if (cPieceResult != FIELD_EMPTY) {
// we will look if we can capture
// TODO: optimize by giving the bit as parameter
if (cPieceResult & (LOWERCASEBIT)) {
// we know that the allowed colour for capture is the colour of the destination piece
add_singlemove(iPos, iResult + 1, PROMOTION_NONE);
// add check for promotion moves
if (ROW144TO64(iPos) == 6) {
fill_movesforpromotion(iPos, iResult + 1);
}
}
} else if (iResult + 1 == m1_board.m_epfield) {
// ep move
add_singlemove(iPos, iResult + 1, PROMOTION_NONE);
}
}
}
/**
* fill all possible moves for a pawn
*/
static void fill_movesforpawnblack(const posid iPos, const int iDir, const t_boolean bQuieuscience) {
char cPieceResult;
posid iResult = iPos + iDir;
cPieceResult = m1_board.m_fields[iResult];
if (cPieceResult == FIELD_EMPTY) {
// empty case, no capture move, so move possible
if (!bQuieuscience) add_singlemove(iPos, iResult, PROMOTION_NONE);
// add check for promotion moves
if (ROW144TO64(iPos) == 1) {
// always add promotion moves to the movelist
fill_movesforpromotion(iPos, iResult);
}
// check if we can do a double move
if (ROW144TO64(iPos) == 6) {
if (m1_board.m_fields[iResult + iDir] == FIELD_EMPTY) {
if (!bQuieuscience) add_singlemove(iPos, (const posid) iResult + iDir, PROMOTION_NONE);
}
}
}
cPieceResult = m1_board.m_fields[iResult - 1];
if (cPieceResult != FIELD_BORDER) {
if (cPieceResult != FIELD_EMPTY) {
// we will look if we can capture
// TODO: optimize by giving the bit as parameter
if (!(cPieceResult & (LOWERCASEBIT))) {
// we know that the allowed colour for capture is the colour of the destination piece
add_singlemove(iPos, (const posid) iResult - 1, PROMOTION_NONE);
// add check for promotion moves
if (ROW144TO64(iPos) == 1) {
// always add promotion moves to the movelist
fill_movesforpromotion(iPos, (const posid) iResult - 1);
}
}
} else if (iResult - 1 == m1_board.m_epfield) {
// ep move
add_singlemove(iPos, (const posid) iResult - 1, PROMOTION_NONE);
}
}
cPieceResult = m1_board.m_fields[iResult + 1];
if (cPieceResult != FIELD_BORDER) {
if (cPieceResult != FIELD_EMPTY) {
// we will look if we can capture
// TODO: optimize by giving the bit as parameter
if (!(cPieceResult & (LOWERCASEBIT))) {
// we know that the allowed colour for capture is the colour of the destination piece
add_singlemove(iPos, (const posid) iResult + 1, PROMOTION_NONE);
// add check for promotion moves
if (ROW144TO64(iPos) == 1) {
// always add promotion moves to the movelist
fill_movesforpromotion(iPos, (const posid) iResult + 1);
}
}
} else if (iResult + 1 == m1_board.m_epfield) {
// ep move
add_singlemove(iPos, (const posid) iResult + 1, PROMOTION_NONE);
}
}
}
/**
* is the player in check after the move is executed (return 1)
* also do check if the current move causes a check (return 2)
*/
static int isInCheckAfterMove(const posid iFrom, const posid iTo, const t_promotion cFlag) {
int iCheck = 0;
// do we need to consider invalid moves?
struct st_alg1_board m1_boardbuffer;
t_boolean isWhite = (m1_board.m_fields [iFrom] & (LOWERCASEBIT)) ? myFALSE : myTRUE;
// store board position, for later restore
memcpy(&m1_boardbuffer, &m1_board, sizeof (m1_board));
if (isWhite) {
apply_movewhite(iFrom, iTo, cFlag);
} else {
apply_moveblack(iFrom, iTo, cFlag);
}
iCheck = isInCheck(isWhite);
if (!iCheck) {
if (isInCheck(!isWhite)) iCheck = 2;
}
// restore old position
memcpy(&m1_board, &m1_boardbuffer, sizeof (m1_board));
return (iCheck);
}
/**
* is the position in check
*/
t_boolean isInCheck(const t_boolean bEvaluateForWhite) {
posid iKingPos = bEvaluateForWhite ? m1_board.m_whiteking : m1_board.m_blackking;
return isUnderAttack(iKingPos, bEvaluateForWhite) > 0;
}
/**
* test if after executing the move, the king is in check
* the king to test will be of the same colour as the colour moving the piece
* we will first apply the move, then see if the king jumps to any of the opposing colours
*/
#define pieceseesone(x,y,z) if(m1_board.m_fields[(z)]==((y)?TO_BLACK(x):TO_WHITE(x))) { isAttack++; }
#define pieceseesdirm(x,y,z,a,b,c) if(pieceseesmore((x),(y),(z),(a),(b),(c))) { isAttack++; }
#define pieceopenline(x,y,z,a) if(pieceseesopen((x),(y),(z),(a))) { isAttack++; }
unsigned int isUnderAttack(const posid iPiecePos, const t_boolean bEvaluateForWhite) {
unsigned int isAttack = 0;
// calculate all knights moves
pieceseesone(PIECE_KNIGHT, bEvaluateForWhite, iPiecePos + 25);
pieceseesone(PIECE_KNIGHT, bEvaluateForWhite, iPiecePos + 23);
pieceseesone(PIECE_KNIGHT, bEvaluateForWhite, iPiecePos + 14);
pieceseesone(PIECE_KNIGHT, bEvaluateForWhite, iPiecePos + 10);
pieceseesone(PIECE_KNIGHT, bEvaluateForWhite, iPiecePos - 25);
pieceseesone(PIECE_KNIGHT, bEvaluateForWhite, iPiecePos - 23);
pieceseesone(PIECE_KNIGHT, bEvaluateForWhite, iPiecePos - 14);
pieceseesone(PIECE_KNIGHT, bEvaluateForWhite, iPiecePos - 10);
// calculate all rook moves
pieceseesdirm(iPiecePos, PIECE_ROOK, PIECE_QUEEN, bEvaluateForWhite, 12, 7);
pieceseesdirm(iPiecePos, PIECE_ROOK, PIECE_QUEEN, bEvaluateForWhite, 1, 7);
pieceseesdirm(iPiecePos, PIECE_ROOK, PIECE_QUEEN, bEvaluateForWhite, -12, 7);
pieceseesdirm(iPiecePos, PIECE_ROOK, PIECE_QUEEN, bEvaluateForWhite, -1, 7);
// calculate all bishop moves
pieceseesdirm(iPiecePos, PIECE_BISHOP, PIECE_QUEEN, bEvaluateForWhite, 13, 7);
pieceseesdirm(iPiecePos, PIECE_BISHOP, PIECE_QUEEN, bEvaluateForWhite, 11, 7);
pieceseesdirm(iPiecePos, PIECE_BISHOP, PIECE_QUEEN, bEvaluateForWhite, -13, 7);
pieceseesdirm(iPiecePos, PIECE_BISHOP, PIECE_QUEEN, bEvaluateForWhite, -11, 7);
// calculate all king moves
pieceseesone(PIECE_KING, bEvaluateForWhite, iPiecePos + 12);
pieceseesone(PIECE_KING, bEvaluateForWhite, iPiecePos + 1);
pieceseesone(PIECE_KING, bEvaluateForWhite, iPiecePos - 12);
pieceseesone(PIECE_KING, bEvaluateForWhite, iPiecePos - 1);
pieceseesone(PIECE_KING, bEvaluateForWhite, iPiecePos + 13);
pieceseesone(PIECE_KING, bEvaluateForWhite, iPiecePos + 11);
pieceseesone(PIECE_KING, bEvaluateForWhite, iPiecePos - 13);
pieceseesone(PIECE_KING, bEvaluateForWhite, iPiecePos - 11);
// handle pawn moves
if (bEvaluateForWhite) {
pieceseesone(PIECE_PAWN, bEvaluateForWhite, iPiecePos + 11);
pieceseesone(PIECE_PAWN, bEvaluateForWhite, iPiecePos + 13);
} else {
pieceseesone(PIECE_PAWN, bEvaluateForWhite, iPiecePos - 11);
pieceseesone(PIECE_PAWN, bEvaluateForWhite, iPiecePos - 13);
}
return (isAttack);
}
/**
* see if the piece gets attached by a minor piece, needed for evaluation
*/
unsigned int isUnderMinorAttack(const posid iPiecePos, const t_piece cPiece, const t_boolean bEvaluateForWhite) {
int isAttack = 0;
if ((cPiece == PIECE_ROOK) || (cPiece == PIECE_QUEEN)) {
// calculate all knights moves
pieceseesone(PIECE_KNIGHT, bEvaluateForWhite, iPiecePos + 25);
pieceseesone(PIECE_KNIGHT, bEvaluateForWhite, iPiecePos + 23);
pieceseesone(PIECE_KNIGHT, bEvaluateForWhite, iPiecePos + 14);
pieceseesone(PIECE_KNIGHT, bEvaluateForWhite, iPiecePos + 10);
pieceseesone(PIECE_KNIGHT, bEvaluateForWhite, iPiecePos - 25);
pieceseesone(PIECE_KNIGHT, bEvaluateForWhite, iPiecePos - 23);
pieceseesone(PIECE_KNIGHT, bEvaluateForWhite, iPiecePos - 14);
pieceseesone(PIECE_KNIGHT, bEvaluateForWhite, iPiecePos - 10);
}
if (cPiece == PIECE_QUEEN) {
// calculate all rook moves
pieceseesdirm(iPiecePos, PIECE_ROOK, PIECE_ROOK, bEvaluateForWhite, 12, 7);
pieceseesdirm(iPiecePos, PIECE_ROOK, PIECE_ROOK, bEvaluateForWhite, 1, 7);
pieceseesdirm(iPiecePos, PIECE_ROOK, PIECE_ROOK, bEvaluateForWhite, -12, 7);
pieceseesdirm(iPiecePos, PIECE_ROOK, PIECE_ROOK, bEvaluateForWhite, -1, 7);
}
if ((cPiece == PIECE_QUEEN) || (cPiece == PIECE_ROOK)) {
// calculate all bishop moves
pieceseesdirm(iPiecePos, PIECE_BISHOP, PIECE_BISHOP, bEvaluateForWhite, 13, 7);
pieceseesdirm(iPiecePos, PIECE_BISHOP, PIECE_BISHOP, bEvaluateForWhite, 11, 7);
pieceseesdirm(iPiecePos, PIECE_BISHOP, PIECE_BISHOP, bEvaluateForWhite, -13, 7);
pieceseesdirm(iPiecePos, PIECE_BISHOP, PIECE_BISHOP, bEvaluateForWhite, -11, 7);
}
if (cPiece != PIECE_PAWN) {
// handle pawn moves
if (bEvaluateForWhite) {
pieceseesone(PIECE_PAWN, bEvaluateForWhite, iPiecePos + 11);
pieceseesone(PIECE_PAWN, bEvaluateForWhite, iPiecePos + 13);
} else {
pieceseesone(PIECE_PAWN, bEvaluateForWhite, iPiecePos - 11);
pieceseesone(PIECE_PAWN, bEvaluateForWhite, iPiecePos - 13);
}
}
return (isAttack);
}
// --------------------------------------------------------------------
static t_boolean pieceseesmore(const posid iPiecePos, const t_piece cPieceToLookFor1, const t_piece cPieceToLookFor2,
const t_boolean bEvaluateForWhite, const int iJump, const int iCount) {
int i;
t_piece cPiece1;
t_piece cPiece2;
t_piece cPieceResult;
int iResult = iPiecePos;
if (bEvaluateForWhite) {
cPiece1 = cPieceToLookFor1 + LOWERCASEBIT;
cPiece2 = cPieceToLookFor2 + LOWERCASEBIT;
} else {
cPiece1 = cPieceToLookFor1;
cPiece2 = cPieceToLookFor2;
}
for (i = 0; i < iCount; i++) {
// repeat all moves in a direction
iResult += iJump;
cPieceResult = m1_board.m_fields[iResult];
if (cPieceResult == FIELD_EMPTY) {
// empty case, no capture move, so move possible
} else if (cPieceResult == cPiece1) {
return myTRUE;
} else if (cPieceResult == cPiece2) {
return myTRUE;
} else {
// if we reach the border or another piece, we do not continue anymore
break;
}
}
return myFALSE;
}
// eof