/************************************ ChessAI.c Original Author: Eric Rollins. Copyright 1999-2005 Firepad, Inc. All rights reserved. The latest version of this file is located at http://www.whitehorsegames.com/chroma/source/ Use of this file governed by the GNU Public License Version 2, as defined here: http://www.opensource.org/licenses/gpl-license.php This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. Commercial licenses to this software, not subject to the limitations of GPL, are available from Firepad for a fee. Contact: Bill Mitchell Firepad, Inc. 3187-D Airway Avenue Costa Mesa, CA 92626 Or email "support" at "firepad dot com." Or do a whois lookup on firepad.com for the current technical contact. ***********************************/ #include #include #include "Util.h" #include "SharedAI.h" #include "ChessAI.h" #include "ChessmateSave.h" #include "ChessBook.h" //#define BENCHMARK //#define VERIFY_MOVE_RESOURCE //#define VERIFY_BITBOARD_RESOURCE //#define PAWN_STRUCTURE //#define ROOK_STRUCTURE #define FUTILITY_PRUNE // asserts with display of search depth //#define DISPLAY_DEPTH // multiply search time in secs by this value (used for debugging) #define TIME_MULT 1 //#define TIME_MULT 10 // normally bound by time instead, but avoid blowing stack #define MAX_DEPTH 8 #define CHESS_MOVES_RSRC_ID 9001 #define CHESS_BITBOARD_RSRC_ID 9002 #define MY_MAX 30000 #define MY_MIN -30000 #define WHITE_WIN (MY_MAX - 2000) #define BLACK_WIN (MY_MIN + 2000) #define WHITE_WIN_BOUND (WHITE_WIN-100) #define BLACK_WIN_BOUND (BLACK_WIN+100) #define NUM_CHESS_PIECE_CLASSES 7 #define EMPTY 0 #define KING 1 #define QUEEN 2 #define ROOK 3 #define BISHOP 4 #define KNIGHT 5 #define PAWN 6 #define WHITE_FLAG 0 #define BLACK_FLAG 128 #define WHITE_KING (KING | WHITE_FLAG) #define WHITE_QUEEN (QUEEN | WHITE_FLAG) #define WHITE_ROOK (ROOK | WHITE_FLAG) #define WHITE_BISHOP (BISHOP | WHITE_FLAG) #define WHITE_KNIGHT (KNIGHT | WHITE_FLAG) #define WHITE_PAWN (PAWN | WHITE_FLAG) #define BLACK_KING (KING | BLACK_FLAG) #define BLACK_QUEEN (QUEEN | BLACK_FLAG) #define BLACK_ROOK (ROOK | BLACK_FLAG) #define BLACK_BISHOP (BISHOP | BLACK_FLAG) #define BLACK_KNIGHT (KNIGHT | BLACK_FLAG) #define BLACK_PAWN (PAWN | BLACK_FLAG) #define NUM_DIRECTIONS 16 typedef enum Direction { // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dir_w, dir_wnw, dir_nw,dir_nnw,dir_n,dir_nne,dir_ne,dir_ene,dir_e,dir_ese,dir_se,dir_sse,dir_s,dir_ssw,dir_sw,dir_wsw } Direction; #define ROW(loc) ((loc) >> 3) #define COL(loc) ((loc) & 7) FatListNode *gRepeatListHead = 0; /* static const int moveIncrTable[NUM_DIRECTIONS] = { -1, -10, -9, -17, -8, -15, -7, -6, 1, 10, 9, 17, 8, 15, 7, 6 }; // max distance piece can move/attack in this direction // w wnw nw nnw n nne ne ene e ese se sse s ssw sw wsw static const int kingMDP[] = { 2, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0 }; static const int queenMDP[] = { 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0 }; static const int rookMDP[] = { 8, 0, 0, 0, 8, 0, 0, 0, 8, 0, 0, 0, 8, 0, 0, 0 }; static const int bishopMDP[] = { 0, 0, 8, 0, 0, 0, 8, 0, 0, 0, 8, 0, 0, 0, 8, 0 }; static const int knightMDP[] = { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 }; static const int pawnMDP[] = { 0, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0 }; */ // w wnw nw nnw n nne ne ene e ese se sse s ssw sw wsw static const int kingADP[] = { 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 }; static const int queenADP[] = { 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0 }; static const int rookADP[] = { 8, 0, 0, 0, 8, 0, 0, 0, 8, 0, 0, 0, 8, 0, 0, 0 }; static const int bishopADP[] = { 0, 0, 8, 0, 0, 0, 8, 0, 0, 0, 8, 0, 0, 0, 8, 0 }; static const int knightADP[] = { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 }; static const int pawnADP[] = { 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0 }; /* static const int *maxMoveDistPieceTable[NUM_CHESS_PIECE_CLASSES] = { 0, kingMDP, queenMDP, rookMDP, bishopMDP, knightMDP, pawnMDP }; */ static const int *maxAttackDistPieceTable[NUM_CHESS_PIECE_CLASSES] = { 0, kingADP, queenADP, rookADP, bishopADP, knightADP, pawnADP }; /* static const int startDirectionTable[NUM_CHESS_PIECE_CLASSES] = { dir_w, // EMPTY dir_w, // KING dir_w, // QUEEN dir_w, // ROOK dir_nw, // BISHOP dir_wnw, // KNIGHT dir_nw // PAWN }; static const int directionIncrTable[NUM_CHESS_PIECE_CLASSES] = { 0, // EMPTY 2, // KING 2, // QUEEN 4, // ROOK 4, // BISHOP 2, // KNIGHT 2, // PAWN }; // maximum distance a piece on this square can move in each direction typedef struct maxDistStruct { char dist[16]; } maxDistStruct; //static const maxDistStruct maxDistTable[kChessboardSize]; //#include "MaxDist.c" static const char blankPosWeight[kChessboardSize] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; */ static const char whiteQueenPosWeight[kChessboardSize] = { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; static const char blackQueenPosWeight[kChessboardSize] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }; static const char whiteBeginKingPosWeight[kChessboardSize] = { -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -4, -4, -4, -4, -4, -4, -4, -4, 0, 4, 8, -4, 0, -4, 14, 4 }; static const char blackBeginKingPosWeight[kChessboardSize] = { 0, 4, 8, -4, 0, -4, 14, 4, -4, -4, -4, -4, -4, -4, -4, -4, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8, -8 }; static const char whiteBishopPosWeight[kChessboardSize] = { -8, -8, -8, -8, -8, -8, -8, -8, -8, 2, 2, 2, 2, 2, 2, -8, -8, 2, 7, 7, 7, 7, 2, -8, -8, 2, 7, 12, 12, 7, 2, -8, -9, 1, 6, 11, 11, 6, 1, -9, -10, 0, 5, 5, 5, 5, 0, -10, -10, 0, 0, 0, 0, 0, 0, -10, -10, -10, -20, -10, -10, -20, -10, -10 }; static const char blackBishopPosWeight[kChessboardSize] = { -10, -10, -20, -10, -10, -20, -10, -10, -10, 0, 0, 0, 0, 0, 0, -10, -10, 0, 5, 5, 5, 5, 0, -10, -9, 1, 6, 11, 11, 6, 1, -9, -8, 2, 7, 12, 12, 7, 2, -8, -8, 2, 2, 2, 2, 2, 2, -8, -8, -8, -8, -8, -8, -8, -8, -8, }; static const char whiteKnightPosWeight[kChessboardSize] = { -8, -8, -8, -8, -8, -8, -8, -8, -8, 2, 2, 2, 2, 2, 2, -8, -8, 2, 7, 7, 7, 7, 2, -8, -8, 2, 7, 12, 12, 7, 2, -8, -9, 1, 6, 11, 11, 6, 1, -9, -10, 0, 5, 5, 5, 5, 0, -10, -10, 0, 0, 0, 0, 0, 0, -10, -10, -30, -10, -10, -10, -10, -30, -10 }; static const char blackKnightPosWeight[kChessboardSize] = { -10, -30, -10, -10, -10, -10, -30, -10, -10, 0, 0, 0, 0, 0, 0, -10, -10, 0, 5, 5, 5, 5, 0, -10, -9, 1, 6, 11, 11, 6, 1, -9, -8, 2, 7, 12, 12, 7, 2, -8, -8, 2, 7, 7, 7, 7, 2, -8, -8, 2, 2, 2, 2, 2, 2, -8, -8, -8, -8, -8, -8, -8, -8, -8 }; static const char whiteRookPosWeight[kChessboardSize] = { 2, 2, 2, 2, 2, 2, 2, 2, 20, 20, 20, 20, 20, 20, 20, 20, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 5, 0, 0, 0 }; static const char blackRookPosWeight[kChessboardSize] = { 0, 0, 0, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 20, 20, 20, 20, 20, 20, 20, 20, 2, 2, 2, 2, 2, 2, 2, 2 }; static const char whitePawnPosWeight[kChessboardSize] = { 0, 0, 0, 0, 0, 0, 0, 0, 5, 10, 15, 20, 20, 15, 10, 5, 4, 8, 12, 16, 16, 12, 8, 4, 3, 6, 9, 12, 12, 9, 6, 3, 2, 4, 6, 8, 8, 6, 4, 2, 1, 2, 3, -10, -10, 3, 2, 1, 0, 0, 0, -40, -40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; static const char blackPawnPosWeight[kChessboardSize] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -40, -40, 0, 0, 0, 1, 2, 3, -10, -10, 3, 2, 1, 2, 4, 6, 8, 8, 6, 4, 2, 3, 6, 9, 12, 12, 9, 6, 3, 4, 8, 12, 16, 16, 12, 8, 4, 5, 10, 15, 20, 20, 15, 10, 5, 0, 0, 0, 0, 0, 0, 0, 0 }; char endKingPosWeight[kChessboardSize] = { 0, 10, 20, 30, 30, 20, 10, 0, 10, 20, 30, 40, 40, 30, 20, 10, 20, 30, 40, 50, 50, 40, 30, 20, 30, 40, 50, 60, 60, 50, 40, 30, 30, 40, 50, 60, 60, 50, 40, 30, 20, 30, 40, 50, 50, 40, 30, 20, 10, 20, 30, 40, 40, 30, 20, 10, 0, 10, 20, 30, 30, 20, 10, 0 }; static const char castleRelated[kChessboardSize] = { 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1 }; typedef struct RankedMoveType { char from; char to; short rank; } RankedMoveType; #define RANKED_MOVE_SIZE 128 static RankedMoveType rankedMove[MAX_DEPTH][RANKED_MOVE_SIZE]; static int baseMoveCount; // number of entries at depth 0 static PlayerColor baseTurn; // moving player at depth==0 static Boolean easy = false; static const char *whitePosWeightTable[NUM_CHESS_PIECE_CLASSES] = { 0, whiteBeginKingPosWeight,whiteQueenPosWeight,whiteRookPosWeight, whiteBishopPosWeight,whiteKnightPosWeight,whitePawnPosWeight }; static const char *blackPosWeightTable[NUM_CHESS_PIECE_CLASSES] = { 0, blackBeginKingPosWeight,blackQueenPosWeight,blackRookPosWeight, blackBishopPosWeight,blackKnightPosWeight,blackPawnPosWeight }; // time in seconds when we need to stop static UInt32 stopTime; static Boolean abortDueToEvent; // global to avoid overhead of passing on stack static int maxDepth = 0; typedef struct BitBoard { unsigned long top; // top 4 rows of board unsigned long bottom; // bottom 4 rows of board } BitBoard; // MSB = board[0] = Upper Left ... LSB = board[63] = Lower Right //typedef unsigned long long BitBoard; //static const BitBoard moveBoard[5][kChessboardSize]; //static const BitBoard whitePawnMoveBoard[kChessboardSize]; //static const BitBoard blackPawnMoveBoard[kChessboardSize]; //#include "ChessBitBoard.c" typedef BitBoard MoveBoardType[5][kChessboardSize]; MemHandle moveBoardH = 0; MemHandle whitePawnMoveBoardH = 0; MemHandle blackPawnMoveBoardH = 0; MoveBoardType *moveBoard; BitBoard *whitePawnMoveBoard; BitBoard *blackPawnMoveBoard; // Currently = 8 * 16 * 64, or 8192. #define ALLMOVES_TABLE_SIZE 8192 #ifdef VERIFY_MOVE_RESOURCE //#include "MoveTable.c" unsigned char *OLDallMoves[2][7] = { // Will contain pointers to each array of moves, as follows: { 0, (unsigned char *) whiteKingMoves, (unsigned char *) queenMoves, (unsigned char *) rookMoves, (unsigned char *) bishopMoves, (unsigned char *) knightMoves, (unsigned char *) whitePawnMoves }, { 0, (unsigned char *) blackKingMoves, (unsigned char *) queenMoves, (unsigned char *) rookMoves, (unsigned char *) bishopMoves, (unsigned char *) knightMoves, (unsigned char *) blackPawnMoves } }; unsigned char *OLDallOffsets[2][7] = { // Will contain pointers to each array of offsets { 0, (unsigned char *) whiteKingNext, (unsigned char *) queenNext, (unsigned char *) rookNext, (unsigned char *) bishopNext, (unsigned char *) knightNext, (unsigned char *) whitePawnNext }, { 0, (unsigned char *) blackKingNext, (unsigned char *) queenNext, (unsigned char *) rookNext, (unsigned char *) bishopNext, (unsigned char *) knightNext, (unsigned char *) blackPawnNext } }; #endif MemHandle allMovesH[16] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; unsigned char *allMoves[2][7], *allOffsets[2][7]; int moveListSize[8] = {0, 16, 32, 16, 16, 16, 8, 8}; int moveListShift[8] = {0, 4, 5, 4, 4, 4, 3, 3}; int wemIsAttackedPieceSet[2] = {QUEEN, KNIGHT}; int wemIsAttackedStartDir[2] = {dir_w, dir_wnw}; //-------------------------------------------------------------------------- #define PIECE(x) ((((int)x)) & ((int)127)) #define COLOR(x) (((((int)x)) & ((int)128)) ? black : white) //-------------------------------------------------------------------------- inline void clearBoard(FastBoardType *board){ MemSet(board,sizeof(FastBoardType),EMPTY); } //-------------------------------------------------------------------------- inline void copyBoard(FastBoardType *toBoard, const FastBoardType *fromBoard){ //MemMove(toBoard,fromBoard,sizeof(FastBoardType)); *toBoard = *fromBoard; } //-------------------------------------------------------------------------- typedef struct PenaltyType { short castleTurn; short kingSafetyViolations; short undevelopedPieceCount; Boolean nonPawnOpen; Boolean queenOpenEarly; Boolean lostQueenCastle; Boolean lostKingCastle; Boolean evaluated; } PenaltyType; typedef struct CastleInfoType { Boolean lostQueenCastle; Boolean lostKingCastle; Boolean didCastle; } CastleInfoType; //-------------------------------------------------------------------------- static int rankBoard(PlayerColor turn, FastBoardType *board, const CastleInfoType *castleInfo, // optional PenaltyType *outPenalty, // optional const PenaltyType *inPenalty, // optional int depth); static int rankPawns(FastBoardType *board); //-------------------------------------------------------------------------- static void boardToFastBoard(FastBoardType *fast, const GameStateType *board, int boardEnPassantLoc, Boolean blackQueenCastleAllowed, Boolean blackKingCastleAllowed, Boolean whiteQueenCastleAllowed, Boolean whiteKingCastleAllowed, Boolean skipRankInit) // this also skips init of KingLocations! { int i; clearBoard(fast); fast->enPassantLoc = (char)boardEnPassantLoc; fast->blackQueenCastleAllowed = blackQueenCastleAllowed; fast->blackKingCastleAllowed = blackKingCastleAllowed; fast->whiteQueenCastleAllowed = whiteQueenCastleAllowed; fast->whiteKingCastleAllowed = whiteKingCastleAllowed; fast->validRank = false; fast->validPawnRank = false; fast->whiteRankSum = 0; fast->blackRankSum = 0; fast->pawnRankSum = 0; fast->whiteKingLocation = -1; fast->blackKingLocation = -1; for(i = 0; i < kChessboardSize; i++){ switch(board->board.chessboard[i]){ case whiteking: fast->board[i] = WHITE_KING; break; case whitequeen: fast->board[i] = WHITE_QUEEN; break; case whitebishop: fast->board[i] = WHITE_BISHOP; break; case whiteknight: fast->board[i] = WHITE_KNIGHT; break; case whiterook: fast->board[i] = WHITE_ROOK; break; case whitepawn: fast->board[i] = WHITE_PAWN; break; case blackking: fast->board[i] = BLACK_KING; break; case blackqueen: fast->board[i] = BLACK_QUEEN; break; case blackbishop: fast->board[i] = BLACK_BISHOP; break; case blackknight: fast->board[i] = BLACK_KNIGHT; break; case blackrook: fast->board[i] = BLACK_ROOK; break; case blackpawn: fast->board[i] = BLACK_PAWN; break; default: break; } } if(!skipRankInit){ // initialize rank (turn doesn't matter) rankBoard(white,fast,0,0,0,0); rankPawns(fast); } } //-------------------------------------------------------------------------- static Boolean isEqualFastBoard(const FastBoardType *b1, const FastBoardType *b2){ if(MemCmp(&(b1->board[0]),&(b2->board[0]),kChessboardSize) != 0) return false; return true; } //-------------------------------------------------------------------------- inline void initListNode(ListNode *listNode, const FastBoardType *fastBoard, ListNode *next, PlayerColor turn) { listNode->fastBoard = fastBoard; listNode->next = next; listNode->turn = turn; } //-------------------------------------------------------------------------- // returns true if head item is repeated 2 more times in list static Boolean isRepeat3Times(const ListNode *head){ const ListNode *p; int matchCount = 0; assert(head); p = head->next; while(p){ if(head->turn == p->turn){ if(isEqualFastBoard(head->fastBoard,p->fastBoard)){ if(matchCount++ >= 1){ return true; } } } p = p->next; } return false; } //-------------------------------------------------------------------------- inline PlayerColor flipTurn(PlayerColor turn){ return (PlayerColor)((int)black - (int)turn); } //-------------------------------------------------------------------------- #define KING_ATTACK_VALUE 10000 #define KING_VALUE 1 #define QUEEN_VALUE 900 #define ROOK_VALUE 500 #define BISHOP_VALUE 300 #define KNIGHT_VALUE 300 #define PAWN_VALUE 100 static const int pieceAttackVal[NUM_CHESS_PIECE_CLASSES] = { 0, // EMPTY KING_ATTACK_VALUE, QUEEN_VALUE, ROOK_VALUE, BISHOP_VALUE, KNIGHT_VALUE, PAWN_VALUE }; #define START_LEAST_ATTACKER_VAL (KING_ATTACK_VALUE+1) // does opposing player have an attack on this location? // Note it is only fully accurate in the case of check, // since other attacks may be illegal due to exposing opposing // king to check. // Doesn't do En Passant. // if leastAttacker== false, returns 1 on first attacker found // if == true, returns value of least valuable attacker /* static int ECRisAttacked(PlayerColor turn, int loc, const FastBoardType *board, Boolean leastAttacker) { int dir,dist; int maxD; const char *maxDistList = maxDistTable[loc].dist; const unsigned char *b = board->board; int sq; int occupyingPiece; int moveIncr; int leastAttackerVal = START_LEAST_ATTACKER_VAL; int attackerVal; for(dir = dir_w; dir <= dir_wsw; dir++) { if((maxD = maxDistList[dir]) == 0) continue; moveIncr = moveIncrTable[dir]; sq = loc; for(dist = 1; dist <= maxD; dist++) { sq += moveIncr; if((occupyingPiece = b[sq]) != 0) { if(COLOR(occupyingPiece) == turn) break; occupyingPiece = PIECE(occupyingPiece); if(dist <= maxAttackDistPieceTable[occupyingPiece][dir]) { if(occupyingPiece == PAWN) { if(turn == white) { if((dir == dir_ne) || (dir == dir_nw)) { return PAWN_VALUE; } } else { if((dir == dir_se) || (dir == dir_sw)) { return PAWN_VALUE; } } break; } if(leastAttacker) { attackerVal = pieceAttackVal[occupyingPiece]; if(attackerVal < leastAttackerVal) leastAttackerVal = attackerVal; break; } else { return 1; } } break; } } } if(leastAttackerVal < START_LEAST_ATTACKER_VAL) return leastAttackerVal; else return 0; } */ static BitBoard *opposingPawnMoveBoard[2]; // = { blackPawnMoveBoard, whitePawnMoveBoard }; //-------------------------------------------------------------------------- static int isAttacked(PlayerColor turn, int loc, const FastBoardType *board, Boolean leastAttacker) { int leastAttackerVal = START_LEAST_ATTACKER_VAL; int attackerVal; const unsigned char *theBoard; unsigned char *movesForPiece, *curMove, *nextDirOffset, *movesBase, *nextDirBase; int numMoves = 0, listOffset, dest; short destPiece, pieceColor; BitBoard locBoard; const BitBoard *attackerBoard; theBoard = board->board; // This block creates a bitboard for just the location "loc." if (loc < 32) { locBoard.top = 0x80000000 >> loc; locBoard.bottom = 0; } else { locBoard.top = 0; locBoard.bottom = 0x80000000 >> (loc - 32); } if (turn == white) pieceColor = 0; else pieceColor = 0x80; // QUEEN first, then KNIGHT. listOffset = loc << moveListShift[QUEEN]; movesBase = allMoves[turn][QUEEN]; movesForPiece = movesBase + listOffset; nextDirBase = allOffsets[turn][QUEEN]; nextDirOffset = nextDirBase + listOffset; // faster: = movesForPiece + allOffsets - allMoves; curMove = movesForPiece; while ((dest = *curMove++) != 255) { destPiece = theBoard[dest]; if (destPiece) { // Dest was full. See if it can reach the "loc." if ((pieceColor ^ destPiece) & 0x80) // neg xor pos = true -> capture { destPiece = PIECE(destPiece); // Note that, if curPieceType = queen and destPiece = knight, then cannot reach. if (destPiece != KNIGHT) { if (destPiece == PAWN) { attackerBoard = &opposingPawnMoveBoard[turn][dest]; if((attackerBoard->top & locBoard.top) || (attackerBoard->bottom & locBoard.bottom)) return PAWN_VALUE; } else { attackerBoard = &((*moveBoard)[destPiece - 1][dest]); if((attackerBoard->top & locBoard.top) || (attackerBoard->bottom & locBoard.bottom)) { // Found a piece that can reach if (leastAttacker) { attackerVal = pieceAttackVal[destPiece]; if(attackerVal < leastAttackerVal) leastAttackerVal = attackerVal; } else { return 1; } } } } } // Index to next direction. curMove = *(curMove - movesForPiece + nextDirOffset - 1) + movesForPiece; } } // KNIGHT check now. listOffset = loc << moveListShift[KNIGHT]; //movesBase = allMoves[turn][KNIGHT]; movesForPiece = allMoves[turn][KNIGHT] + listOffset; //nextDirBase = allOffsets[turn][KNIGHT]; //nextDirOffset = nextDirBase + listOffset; // faster: = movesForPiece + allOffsets - allMoves; curMove = movesForPiece; while ((dest = *curMove++) != 255) { destPiece = theBoard[dest]; if (destPiece) { // Dest was full. See if it can reach the "loc." if ((pieceColor ^ destPiece) & 0x80) // neg xor pos = true -> capture { destPiece = PIECE(destPiece); // Note that, if curPieceType = knight and destPiece != knight, then cannot reach. if (destPiece == KNIGHT) { if (leastAttacker) { attackerVal = pieceAttackVal[KNIGHT]; if(attackerVal < leastAttackerVal) leastAttackerVal = attackerVal; } else { return 1; } } } } } // NOW RETURN THE LEAST ATTACKER VALUE if(leastAttackerVal < START_LEAST_ATTACKER_VAL) return leastAttackerVal; else return 0; } //-------------------------------------------------------------------------- inline Boolean isKingInCheckBB(PlayerColor turn, const FastBoardType *board) { int kingLoc = -1; if(turn == white){ kingLoc = board->whiteKingLocation; }else{ kingLoc = board->blackKingLocation; } if(isAttacked(turn,kingLoc,board,false)) return true; else return false; } //-------------------------------------------------------------------------n inline void initPenalty(PenaltyType *p){ MemSet(p,sizeof(PenaltyType),EMPTY); } //-------------------------------------------------------------------------n inline void copyPenalty(PenaltyType *outP, const PenaltyType *inP){ MemMove(outP,inP,sizeof(PenaltyType)); } //------------------------------------------------------------------------- static void evalOpeningPenalty(PenaltyType *outP, const CastleInfoType *castleInfo, PlayerColor color, FastBoardType *board, int depth) { int kingSafetyViolations = 0; int col; int i; Boolean queenPawn; Boolean kingPawn; Boolean queenKnight; Boolean kingKnight; Boolean queenBishop; Boolean kingBishop; Boolean queenQueen; unsigned char *bp = board->board; int kingLocation; outP->evaluated = true; if(color == white){ kingLocation = board->whiteKingLocation; queenPawn = (unsigned char)(bp[51] == WHITE_PAWN); kingPawn = (unsigned char)(bp[52] == WHITE_PAWN); queenKnight = (unsigned char)(bp[57] == WHITE_KNIGHT); kingKnight = (unsigned char)(bp[62] == WHITE_KNIGHT); queenBishop = (unsigned char)(bp[58] == WHITE_BISHOP); kingBishop = (unsigned char)(bp[61] == WHITE_BISHOP); queenQueen = (unsigned char)(bp[59] == WHITE_QUEEN); // keep pawn wall in front of king if(ROW(kingLocation) == 7){ col = COL(kingLocation); if(col > 3){ for(i = 53; i <= 55; i++) if(bp[i] != WHITE_PAWN) kingSafetyViolations++; } if(col < 5){ for(i = 48; i <= 50; i++) if(bp[i] != WHITE_PAWN) kingSafetyViolations++; } } } else { kingLocation = board->blackKingLocation; queenPawn = (unsigned char)(bp[11] == BLACK_PAWN); kingPawn = (unsigned char)(bp[12] == BLACK_PAWN); queenKnight = (unsigned char)(bp[1] == BLACK_KNIGHT); kingKnight = (unsigned char)(bp[6] == BLACK_KNIGHT); queenBishop = (unsigned char)(bp[2] == BLACK_BISHOP); kingBishop = (unsigned char)(bp[5] == BLACK_BISHOP); queenQueen = (unsigned char)(bp[3] == BLACK_QUEEN); // keep pawn wall in front of king if(ROW(kingLocation) == 0){ col = COL(kingLocation); if(col > 3){ for(i = 13; i <= 15; i++) if(bp[i] != BLACK_PAWN) kingSafetyViolations++; } if(col < 5){ for(i = 8; i <= 10; i++) if(bp[i] != BLACK_PAWN) kingSafetyViolations++; } } } if(queenPawn && kingPawn) outP->nonPawnOpen = true; if(!queenQueen && (queenKnight || kingKnight || queenBishop || kingBishop)) outP->queenOpenEarly = true; if(castleInfo->lostQueenCastle) outP->lostQueenCastle = true; if(castleInfo->lostKingCastle) outP->lostKingCastle = true; if(castleInfo->didCastle) outP->castleTurn = depth+1; if(kingSafetyViolations > outP->kingSafetyViolations) outP->kingSafetyViolations = kingSafetyViolations; //---------------------------------------------- // encourage new piece development if((depth == 0)||(depth == 1)){ outP->undevelopedPieceCount = queenPawn + kingPawn + queenKnight + kingKnight + queenBishop + kingBishop; } } //------------------------------------------------------------------------- #define NON_PAWN_OPEN_PENALTY 40 #define QUEEN_OPEN_EARLY_PENALTY 20 // will be 90 on king move; 45 on rook move #define LOST_CASTLE_PENALTY 45 #define DID_CASTLE_BONUS 40 #define KING_SAFETY_PENALTY 16 #define KING_SAFETY_PENALTY_SHIFT 4 #define UNDEVELOPED_PIECE_PENALTY 16 #define UNDEVELOPED_PIECE_PENALTY_SHIFT 4 static int assessOpeningPenalty(const PenaltyType *p) { int penalty = 0; if(!(p->evaluated)) return 0; if(p->nonPawnOpen) penalty += NON_PAWN_OPEN_PENALTY; if(p->queenOpenEarly) penalty += QUEEN_OPEN_EARLY_PENALTY; if(p->lostQueenCastle) penalty += LOST_CASTLE_PENALTY; if(p->lostKingCastle) penalty += LOST_CASTLE_PENALTY; // penalty -= DID_CASTLE_BONUS / p->castleTurn if(p->castleTurn) penalty -= (DID_CASTLE_BONUS >> p->castleTurn); //penalty += p->kingSafetyViolations*KING_SAFETY_PENALTY; penalty += (p->kingSafetyViolations << KING_SAFETY_PENALTY_SHIFT); //penalty += p->undevelopedPieceCount*UNDEVELOPED_PIECE_PENALTY; penalty += (p->undevelopedPieceCount << UNDEVELOPED_PIECE_PENALTY_SHIFT); return penalty; } //-------------------------------------------------------------------------- #define HARASS_CHECK_VALUE 1 #define MIN_KING_ENDGAME_SUM 1200 // extra columns to simplify logic #define PAWN_ARR_SIZE 10 static long rankCalls = 0; static const int pieceVal[NUM_CHESS_PIECE_CLASSES] = { 0, // EMPTY KING_VALUE, QUEEN_VALUE, ROOK_VALUE, BISHOP_VALUE, KNIGHT_VALUE, PAWN_VALUE }; // white is maximizing player, black is minimizing // eval on: // 1. material advantage // 2. advancing pawns to be queens // 3. occupy center static int rankCount = 0; static Boolean doStopOnEvent = true; #define ABORT_CHECK_INTERVAL 100 static int rankBoardWithThrow(PlayerColor turn, FastBoardType *board, const CastleInfoType *castleInfo, // optional PenaltyType *outPenalty, // optional const PenaltyType *inPenalty, // optional int depth) { UInt32 time; rankCalls++; // check for abort if(rankCount++ > ABORT_CHECK_INTERVAL){ rankCount = 0; if(doStopOnEvent && EvtEventAvail()){ abortDueToEvent = true; ErrThrow(2); } time = TimGetTicks(); SpinCursor(time); if((maxDepth > 1) && (time >= stopTime)){ ErrThrow(1); } } return rankBoard(turn,board,castleInfo,outPenalty,inPenalty,depth); } static int rankBoard(PlayerColor turn, FastBoardType *board, const CastleInfoType *castleInfo, // optional PenaltyType *outPenalty, // optional const PenaltyType *inPenalty, // optional int depth) { int i; int blacksum = 0; int whitesum = 0; int piece; const unsigned char *boardP; if(outPenalty) copyPenalty(outPenalty,inPenalty); //----------------------------------------------------------- if(!(board->validRank)){ // add piece values & position weights boardP = board->board; for(i = 0; i < kChessboardSize; i++){ if((piece = *boardP++) != 0){ if(COLOR(piece) == white){ piece = PIECE(piece); // separate char adds! whitesum += pieceVal[piece]; whitesum += whitePosWeightTable[piece][i]; if (piece == KING){ board->whiteKingLocation = (char)i; } }else{ piece = PIECE(piece); // separate char adds! blacksum += pieceVal[piece]; blacksum += blackPosWeightTable[piece][i]; if(piece == KING){ board->blackKingLocation = (char)i; } } } } board->whiteRankSum = whitesum; board->blackRankSum = blacksum; }else{ whitesum = board->whiteRankSum; blacksum = board->blackRankSum; } if(blacksum < MIN_KING_ENDGAME_SUM){ if(blacksum < PAWN_VALUE){ whitesum -= whiteBeginKingPosWeight[board->whiteKingLocation]; whitesum += (75 - max(abs(ROW(board->blackKingLocation) - ROW(board->whiteKingLocation)), abs(COL(board->blackKingLocation) - COL(board->whiteKingLocation)))); }else{ whitesum -= whiteBeginKingPosWeight[board->whiteKingLocation]; whitesum += endKingPosWeight[board->whiteKingLocation]; } }else{ if(outPenalty && (turn == white) && (baseTurn == white)){ evalOpeningPenalty(outPenalty, castleInfo, white, board, depth); } } if(whitesum < MIN_KING_ENDGAME_SUM){ if(whitesum < PAWN_VALUE){ blacksum -= blackBeginKingPosWeight[board->blackKingLocation]; blacksum += (75 - max(abs(ROW(board->blackKingLocation) - ROW(board->whiteKingLocation)), abs(COL(board->blackKingLocation) - COL(board->whiteKingLocation)))); }else{ blacksum -= blackBeginKingPosWeight[board->blackKingLocation]; blacksum += endKingPosWeight[board->blackKingLocation]; } }else{ if(outPenalty && (turn == black) && (baseTurn == black)){ evalOpeningPenalty(outPenalty, castleInfo, black, board, depth); } } board->validRank = true; return (whitesum - blacksum); } //-------------------------------------------------------------------------- #define DOUBLED_PAWN_PENALTY 10 #define ISOLATED_PAWN_PENALTY 20 #define BACKWARDS_PAWN_PENALTY 8 #define PASSED_PAWN_BONUS 20 #define ROOK_SEMI_OPEN_FILE_BONUS 10 #define ROOK_OPEN_FILE_BONUS 5 #define DOUBLED_ROOK_BONUS 20 static int rankPawns(FastBoardType *board){ #ifdef PAWN_STRUCTURE int i; int whitePawnCount[PAWN_ARR_SIZE]; int blackPawnCount[PAWN_ARR_SIZE]; int whitePawnLead[PAWN_ARR_SIZE]; int blackPawnLead[PAWN_ARR_SIZE]; int row, col; int whitepawnsum,blackpawnsum; #ifdef ROOK_STRUCTURE int whiteRookCol0; int whiteRookCol1; int blackRookCol0; int blackRookCol1; #endif int *p; int *stopp; int *wpcPtr; int *bpcPtr; int *wplPtr; int *bplPtr; int wpcLeft; int wpcCenter; int wpcRight; int bpcLeft; int bpcCenter; int bpcRight; int wplLeft; int wplCenter; int wplRight; int bplLeft; int bplCenter; int bplRight; const unsigned char *boardP; int piece; #endif #ifndef PAWN_STRUCTURE if(board) return 0; else return 0; #else if(!(board->validPawnRank)){ whitepawnsum = 0; blackpawnsum = 0; #ifdef ROOK_STRUCTURE whiteRookCol0 = 0; whiteRookCol1 = 0; blackRookCol0 = 0; blackRookCol1 = 0; #endif boardP = board->board; // examine pawn structure p = whitePawnCount; stopp = whitePawnCount + PAWN_ARR_SIZE; while(p != stopp) *p++ = 0; p = blackPawnCount; stopp = blackPawnCount + PAWN_ARR_SIZE; while(p != stopp) *p++ = 0; p = whitePawnLead; stopp = whitePawnLead + PAWN_ARR_SIZE; while(p != stopp) *p++ = 8; p = blackPawnLead; stopp = blackPawnLead + PAWN_ARR_SIZE; while(p != stopp) *p++ = -1; for(i = 0; i < kChessboardSize; i++){ if((piece = *boardP++) != 0){ switch(piece){ case WHITE_PAWN: col = COL(i)+1; row = ROW(i); whitePawnCount[col]++; if(row < whitePawnLead[col]){ whitePawnLead[col] = row; } break; case BLACK_PAWN: col = COL(i)+1; row = ROW(i); blackPawnCount[col]++; if(row > blackPawnLead[col]){ blackPawnLead[col] = row; } break; #ifdef ROOK_STRUCTURE case WHITE_ROOK: col = COL(i) + 1; if(whiteRookCol0){ whiteRookCol1 = col; }else{ whiteRookCol0 = col; } break; case BLACK_ROOK: col = COL(i) + 1; if(blackRookCol0){ blackRookCol1 = col; }else{ blackRookCol0 = col; } break; #endif default: break; } } } // look for doubled,isolated,backwards,passed pawns wpcPtr = whitePawnCount; bpcPtr = blackPawnCount; wplPtr = whitePawnLead; bplPtr = blackPawnLead; wpcLeft = *wpcPtr++; wpcCenter = *wpcPtr++; wpcRight = *wpcPtr++; bpcLeft = *bpcPtr++; bpcCenter = *bpcPtr++; bpcRight = *bpcPtr++; wplLeft = *wplPtr++; wplCenter = *wplPtr++; wplRight = *wplPtr++; bplLeft = *bplPtr++; bplCenter = *bplPtr++; bplRight = *bplPtr++; for(i = 1; i <= 8; i++){ if(wpcCenter > 0){ if(wpcCenter > 1){ whitepawnsum -= DOUBLED_PAWN_PENALTY; if(wpcCenter > 2) whitepawnsum -= DOUBLED_PAWN_PENALTY; } if((wpcLeft==0)&&(wpcRight==0)) whitepawnsum -= ISOLATED_PAWN_PENALTY; if((wplLeft < wplCenter)&&(wplRight < wplCenter)) whitepawnsum -= BACKWARDS_PAWN_PENALTY; if(((bpcCenter == 0)|| (wplCenter < bplCenter)) && ((bpcLeft == 0)|| (wplCenter < bplLeft)) && ((bpcRight == 0)|| (wplCenter < bplRight))) { whitepawnsum += PASSED_PAWN_BONUS; } } if(bpcCenter > 0){ if(bpcCenter > 1){ blackpawnsum -= DOUBLED_PAWN_PENALTY; if(bpcCenter > 2) blackpawnsum -= DOUBLED_PAWN_PENALTY; } if((bpcLeft==0)&&(bpcRight==0)) blackpawnsum -= ISOLATED_PAWN_PENALTY; if((bplLeft > bplCenter)&&(bplRight > bplCenter)) blackpawnsum -= BACKWARDS_PAWN_PENALTY; if(((wpcCenter == 0) || (bplCenter > wplCenter))&& ((wpcLeft == 0) || (bplCenter > wplLeft))&& ((wpcRight == 0) || (bplCenter > wplRight))) { blackpawnsum += PASSED_PAWN_BONUS; } } wpcLeft = wpcCenter; wpcCenter = wpcRight; wpcRight = *wpcPtr++; bpcLeft = bpcCenter; bpcCenter = bpcRight; bpcRight = *bpcPtr++; wplLeft = wplCenter; wplCenter = wplRight; wplRight = *wplPtr++; bplLeft = bplCenter; bplCenter = bplRight; bplRight = *bplPtr++; } #ifdef ROOK_STRUCTURE // find rooks on semi-open, open files if(whiteRookCol0){ if(whitePawnCount[whiteRookCol0] == 0){ whitepawnsum += ROOK_SEMI_OPEN_FILE_BONUS; if(blackPawnCount[whiteRookCol0] == 0) whitepawnsum += ROOK_OPEN_FILE_BONUS; } if(whiteRookCol1){ if(whitePawnCount[whiteRookCol1] == 0){ whitepawnsum += ROOK_SEMI_OPEN_FILE_BONUS; if(blackPawnCount[whiteRookCol1] == 0) whitepawnsum += ROOK_OPEN_FILE_BONUS; } } } if(blackRookCol0){ if(blackPawnCount[blackRookCol0] == 0){ blackpawnsum += ROOK_SEMI_OPEN_FILE_BONUS; if(whitePawnCount[blackRookCol0] == 0) blackpawnsum += ROOK_OPEN_FILE_BONUS; } if(blackRookCol1){ if(blackPawnCount[blackRookCol1] == 0){ blackpawnsum += ROOK_SEMI_OPEN_FILE_BONUS; if(whitePawnCount[blackRookCol1] == 0) blackpawnsum += ROOK_OPEN_FILE_BONUS; } } } #endif board->pawnRankSum = whitepawnsum - blackpawnsum; } board->validPawnRank = true; return board->pawnRankSum; #endif // PAWN_STRUCTURE } //-------------------------------------------------------------------------- static void castleRelatedApplyMove(FastBoardType *toBoard, int from, int to, PlayerColor turn, Boolean *repeatable, CastleInfoType *castleInfo) { if(turn == white){ if(toBoard->whiteQueenCastleAllowed && (from == 56)) castleInfo->lostQueenCastle = true; if(toBoard->whiteKingCastleAllowed && (from == 63)) castleInfo->lostKingCastle = true; if((from == 60)&&(toBoard->board[from] == WHITE_KING)&& ((to == 58)||(to == 62))) { // castle castleInfo->didCastle = true; #ifdef ROOK_STRUCTURE toBoard->validPawnRank = false; #endif if(to == 58){ toBoard->board[56] = EMPTY; toBoard->board[59] = WHITE_ROOK; *repeatable = false; toBoard->whiteRankSum += whitePosWeightTable[ROOK][59] - whitePosWeightTable[ROOK][56]; }else{ toBoard->board[63] = EMPTY; toBoard->board[61] = WHITE_ROOK; *repeatable = false; toBoard->whiteRankSum += whitePosWeightTable[ROOK][61] - whitePosWeightTable[ROOK][63]; } } if(from == 60){ if(!(castleInfo->didCastle) && (toBoard->whiteQueenCastleAllowed || toBoard->whiteKingCastleAllowed)) { castleInfo->lostQueenCastle = true; castleInfo->lostKingCastle = true; } toBoard->whiteQueenCastleAllowed = false; toBoard->whiteKingCastleAllowed = false; } }else{ // black if(toBoard->blackQueenCastleAllowed && (from == 0)) castleInfo->lostQueenCastle = true; if(toBoard->blackKingCastleAllowed && (from == 7)) castleInfo->lostKingCastle = true; if((from == 4)&&(toBoard->board[from] == BLACK_KING)&& ((to == 2)||(to == 6))) { // castle castleInfo->didCastle = true; #ifdef ROOK_STRUCTURE toBoard->validPawnRank = false; #endif if(to == 2){ toBoard->board[0] = EMPTY; toBoard->board[3] = BLACK_ROOK; *repeatable = false; toBoard->blackRankSum += (whitePosWeightTable[ROOK][3] - whitePosWeightTable[ROOK][0]); }else{ toBoard->board[7] = EMPTY; toBoard->board[5] = BLACK_ROOK; *repeatable = false; toBoard->blackRankSum += (whitePosWeightTable[ROOK][5] - whitePosWeightTable[ROOK][7]); } } if(from == 4){ if(!(castleInfo->didCastle) && (toBoard->blackQueenCastleAllowed || toBoard->blackKingCastleAllowed)) { castleInfo->lostQueenCastle = true; castleInfo->lostKingCastle = true; } toBoard->blackQueenCastleAllowed = false; toBoard->blackKingCastleAllowed = false; } } if((from == 56) || (to == 56)) toBoard->whiteQueenCastleAllowed = false; if((from == 63) || (to == 63)) toBoard->whiteKingCastleAllowed = false; if((from == 0) || (to == 0)) toBoard->blackQueenCastleAllowed = false; if((from == 7) || (to == 7)) toBoard->blackKingCastleAllowed = false; } //-------------------------------------------------------------------------- // returns isCapture static Boolean applyMove(FastBoardType *toBoard, const FastBoardType *fromBoard, int from, int to, PlayerColor turn, Boolean *repeatable, CastleInfoType *castleInfo) { Boolean isCapture = false; int inputEnPassantLoc; int fromPiece, toPiece; *repeatable = true; castleInfo->lostQueenCastle = false; castleInfo->lostKingCastle = false; castleInfo->didCastle = false; if(fromBoard) copyBoard(toBoard,fromBoard); inputEnPassantLoc = toBoard->enPassantLoc; toBoard->enPassantLoc = -1; if(from < 0) return false; fromPiece = toBoard->board[from]; if(fromPiece == WHITE_KING) toBoard->whiteKingLocation = (char)to; else if(fromPiece == BLACK_KING) toBoard->blackKingLocation = (char)to; fromPiece = PIECE(fromPiece); toPiece = PIECE(toBoard->board[to]); if((fromPiece == PAWN) || (toPiece == PAWN)) { toBoard->validPawnRank = false; } #ifdef ROOK_STRUCTURE if((fromPiece == ROOK) || (toPiece == ROOK)) { toBoard->validPawnRank = false; } #endif if(castleRelated[from] || castleRelated[to]){ castleRelatedApplyMove(toBoard, from,to,turn,repeatable,castleInfo); } if(turn == white){ if(toPiece != 0){ isCapture = true; toBoard->blackRankSum -= pieceVal[toPiece]; toBoard->blackRankSum -= blackPosWeightTable[toPiece][to]; } if(fromPiece == PAWN){ *repeatable = false; if(to == inputEnPassantLoc){ isCapture = true; toBoard->board[to+8] = EMPTY; toBoard->blackRankSum -= pieceVal[PAWN]; toBoard->blackRankSum -= blackPosWeightTable[PAWN][to+8]; } else if((from - to) == 16){ toBoard->enPassantLoc = (char)(to + 8); } } toBoard->board[to] = toBoard->board[from]; toBoard->board[from] = EMPTY; toBoard->whiteRankSum -= whitePosWeightTable[fromPiece][from]; toBoard->whiteRankSum += whitePosWeightTable[fromPiece][to]; }else{ // turn == black if(toPiece != 0){ isCapture = true; toBoard->whiteRankSum -= pieceVal[toPiece]; toBoard->whiteRankSum -= whitePosWeightTable[toPiece][to]; } if(fromPiece == PAWN){ *repeatable = false; if(to == inputEnPassantLoc){ isCapture = true; toBoard->board[to-8] = EMPTY; toBoard->whiteRankSum -= pieceVal[PAWN]; toBoard->whiteRankSum -= whitePosWeightTable[PAWN][to-8]; }else if((to - from) == 16){ toBoard->enPassantLoc = (char)(to - 8); } } toBoard->board[to] = toBoard->board[from]; toBoard->board[from] = EMPTY; toBoard->blackRankSum -= blackPosWeightTable[fromPiece][from]; toBoard->blackRankSum += blackPosWeightTable[fromPiece][to]; } if(isCapture) *repeatable = false; return isCapture; } //-------------------------------------------------------------------------- // returns promotion location, or -1 for none static int findPromotion(const FastBoardType *board){ int i; const unsigned char *b = &(board->board[0]); for(i = 0; i <= 7; i++){ if(b[i] == WHITE_PAWN){ return i; } } for(i = 56; i <= 63; i++){ if(b[i] == BLACK_PAWN){ return i; } } return -1; } //-------------------------------------------------------------------------- static void applyPromotion(FastBoardType *board, int loc, int promotionPiece) { int prevPromotionPiece = PAWN; if(promotionPiece > QUEEN) prevPromotionPiece = promotionPiece - 1; if(loc <= 7){ board->board[loc] = (unsigned char)(promotionPiece | WHITE_FLAG); board->whiteRankSum += pieceVal[promotionPiece] - pieceVal[prevPromotionPiece]; board->whiteRankSum += whitePosWeightTable[promotionPiece][loc]; board->whiteRankSum -= whitePosWeightTable[prevPromotionPiece][loc]; }else{ board->board[loc] = (unsigned char)(promotionPiece | BLACK_FLAG); board->blackRankSum += (pieceVal[promotionPiece] - pieceVal[prevPromotionPiece]); board->blackRankSum += blackPosWeightTable[promotionPiece][loc]; board->blackRankSum -= blackPosWeightTable[prevPromotionPiece][loc]; } } //-------------------------------------------------------------------------- static int generateMove(PlayerColor turn, int *move0, int *move1, const FastBoardType *board, int depth, int *mmRank, int alpha, int beta, int *promotionPieceType, ListNode *repeatListHead, int repeatListLength, const PenaltyType *inPenalty, Boolean isExtension, int baseRank); //-------------------------------------------------------------------------- static int minMaxRankBoard(PlayerColor turn, FastBoardType *board, int depth, int alpha, int beta, ListNode *repeatListHead, int repeatListLength, const CastleInfoType *castleInfo, const PenaltyType *inPenalty, int movingPieceLoc, Boolean isCapture, Boolean isExtension, int bestRank, int *callerMove0, int baseRank) { int move0; int move1; int mmRank = 0; int rank; int promotionPiece = 0; ListNode repeatListNode; PenaltyType outPenalty; int exchangePenalty; int openingPenalty; int leastAttackerVal; Boolean didPawnRank = false; initListNode(&repeatListNode,board,repeatListHead,turn); if(repeatListLength >= 100) return 0; if((repeatListLength >= 8) && isRepeat3Times(&repeatListNode)) return 0; rank = rankBoardWithThrow(turn,board,castleInfo, &outPenalty,inPenalty,depth); openingPenalty = assessOpeningPenalty(&outPenalty); if(baseTurn == black) openingPenalty = -openingPenalty; rank -= openingPenalty; if(depth == 1) baseRank = rank; rank += shiftDivide8(baseRank); if(!isExtension && (depth <= maxDepth)) isExtension = isKingInCheckBB(flipTurn(turn),board); if((depth < maxDepth) || isExtension){ rank += rankPawns(board); didPawnRank = true; } if((depth < (MAX_DEPTH-1)) && ((depth < (maxDepth-1)) || ((depth < maxDepth) && (maxDepth < 2)) || ((depth <= maxDepth) && isExtension && !easy) || ((depth < maxDepth) && (((turn == white) && (rank > bestRank)) || ((turn == black) && (rank < bestRank)) || (depth & 1) || (*callerMove0 == -1))))) { #ifdef FUTILITY_PRUNE if(((turn == white)&&(rank < (bestRank - KNIGHT_VALUE))) || ((turn == black)&&(rank > (bestRank + KNIGHT_VALUE)))) { return rank; } #endif if(generateMove(flipTurn(turn),&move0,&move1,board,depth+1,&mmRank, alpha,beta,&promotionPiece,&repeatListNode, repeatListLength+1,&outPenalty,isExtension,baseRank) != -1) { return mmRank; } } // estimate max pawnRank, skip pawnrank & penalty if not best if(((turn == white)&&(rank < (bestRank - 200))) || ((turn == black)&&(rank > (bestRank + 200)))) { return rank; } if(!didPawnRank) rank += rankPawns(board); // skip penalty if not best if(easy || ((turn == white)&&(rank < bestRank)) || ((turn == black)&&(rank > bestRank))) { return rank; } exchangePenalty = 0; if(isCapture){ if((leastAttackerVal=isAttacked(turn,movingPieceLoc,board,true)) != 0) { // we take a pessimistic view of exchanges: if piece // is under attack, it will be lost & terminate the exchange. // note responding piece may actually be pinned (protecting // king or higher valued piece) & unable to respond. // note also this doesn't account for pieces lost in // discovered attacks, etc. if(turn == white) exchangePenalty = pieceVal[PIECE(board->board[movingPieceLoc])]; else exchangePenalty = -pieceVal[PIECE(board->board[movingPieceLoc])]; // go one level further... // while expensive, appears to generate a lot of cutoffs... if(isAttacked(flipTurn(turn),movingPieceLoc,board,false)) { if(turn == white){ exchangePenalty -= leastAttackerVal; if(exchangePenalty < 0) exchangePenalty = 0; }else{ exchangePenalty += leastAttackerVal; if(exchangePenalty > 0) exchangePenalty = 0; } } } } rank -= exchangePenalty; return rank; } #define CASTLE_MOVE_RANK 1000 #define CAPTURE_MOVE_RANK 1000 #define BEST_MOVE_RANK_BONUS 1000 //-------------------------------------------------------------------------- static void markBestMove(int from, int to){ int i; RankedMoveType *rmP = &(rankedMove[0][0]); int best = 0; for(i = 0; i < baseMoveCount; i++){ if(rmP->rank > best) best = rmP->rank; rmP++; } rmP = &(rankedMove[0][0]); for(i = 0; i < baseMoveCount; i++){ if((rmP->from == from) && (rmP->to == to)){ rmP->rank = best; if(rmP->rank < 30000) rmP->rank += BEST_MOVE_RANK_BONUS; return; } rmP++; } } static const char *posWeightTable[2][NUM_CHESS_PIECE_CLASSES] = { { 0, whiteBeginKingPosWeight,whiteQueenPosWeight,whiteRookPosWeight, whiteBishopPosWeight,whiteKnightPosWeight,whitePawnPosWeight }, { 0, blackBeginKingPosWeight,blackQueenPosWeight,blackRookPosWeight, blackBishopPosWeight,blackKnightPosWeight,blackPawnPosWeight } }; static int generateAllMoves(PlayerColor turn, const FastBoardType *board, int depth, int onlyFrom) { //RankedMoveType *rmP; unsigned char *rmP; int dest, i = 0; const char *theWeightTable; const unsigned char *loc, *theBoard; unsigned char *movesForPiece, *curMove, *nextDirOffset, *movesBase, *nextDirBase; int numMoves = 0, lastSquare = 64, listOffset; short piece, coloredPiece, destPiece; rmP = (unsigned char *) &(rankedMove[depth][0]); //rmP = &(rankedMove[depth][0]); theBoard = board->board; loc = theBoard; if (onlyFrom != -1) { i = onlyFrom; loc += i; lastSquare = onlyFrom; } do { // Find a piece if ((coloredPiece = *loc++) != 0) { // Must be current turn's color if (COLOR(coloredPiece) == turn) { piece = PIECE(coloredPiece); listOffset = i << moveListShift[piece]; movesBase = allMoves[turn][piece]; movesForPiece = movesBase + listOffset; nextDirBase = allOffsets[turn][piece]; nextDirOffset = nextDirBase + listOffset; // Replaced by optimz. below. // Since allMoves and allOffsets are sequential in memory (see MoveTable.c), // nextDirOffset is always equal to the move table position + sizeof(movetable): //nextDirOffset = movesForPiece + ALLMOVES_TABLE_SIZE; curMove = movesForPiece; //curDir = nextDirOffset; while ((dest = *curMove++) != 255) { // SPEEDUP: keep ptr here for "curDir", increment it on each loop. //curDir++; destPiece = theBoard[dest]; if (!destPiece) { // Also: pawn can only move diagonally here if enPassant if ( (piece == PAWN) && ( ((dest - i) & 3) != 0 ) && // i.e., if it's diagonal move ( dest != board->enPassantLoc) ) // to a non-en-passant square, ; // then don't add to move list. else if ( (piece == KING) && (abs(dest - i) == 2) ) { // Dest was empty. Add to moves list. //rmP->from = (char) i; //rmP->to = (char) dest; //theWeightTable = posWeightTable[turn][piece]; //(rmP++)->rank = CASTLE_MOVE_RANK; *rmP++ = (unsigned char) i; *rmP++ = (unsigned char) dest; *( (short *) rmP)++ = CASTLE_MOVE_RANK; numMoves++; } else { // Dest was empty. Add to moves list. //rmP->from = (char) i; //rmP->to = (char) dest; theWeightTable = posWeightTable[turn][piece]; //(rmP++)->rank = theWeightTable[dest] - theWeightTable[i]; *rmP++ = (unsigned char) i; *rmP++ = (unsigned char) dest; *( (short *) rmP)++ = theWeightTable[dest] - theWeightTable[i]; numMoves++; } } else { // Dest was full. Add capture if necessary, then index to next direction. if ((coloredPiece ^ destPiece) & 0x80) // neg xor pos = true -> capture { // Special case: pawn cannot capture along a file if ( (piece == PAWN) && ( ((dest - i) & 3) == 0 ) ) // I.e., if it's pawn capture along file ; // then don't add to move list. else { // Add capture //rmP->from = (char) i; //rmP->to = (char) dest; //(rmP++)->rank = CAPTURE_MOVE_RANK + // pieceVal[PIECE(destPiece)] - (pieceVal[piece] >> 4); *rmP++ = (unsigned char) i; *rmP++ = (unsigned char) dest; *( (short *) rmP)++ = CAPTURE_MOVE_RANK + pieceVal[PIECE(destPiece)] - (pieceVal[piece] >> 4); numMoves++; } } // Index to next direction. curMove = *(curMove - movesForPiece + nextDirOffset - 1) + movesForPiece; //curMove = movesForPiece + *(curDir - 1); } } } } i++; } while (i < lastSquare); // cheap, but after the fact assert(numMoves < RANKED_MOVE_SIZE); return numMoves; } static int generateAllAttacks(PlayerColor turn, const FastBoardType *board, int depth) { int dest, i = 0; unsigned char *rmP; //RankedMoveType *rmP; const unsigned char *loc, *theBoard; unsigned char *movesForPiece, *curMove, *nextDirOffset, *movesBase, *nextDirBase; //unsigned char *curDir; int numMoves = 0, lastSquare = 64, listOffset; short piece, coloredPiece, destPiece; rmP = (unsigned char *) &(rankedMove[depth][0]); //rmP = &(rankedMove[depth][0]); theBoard = board->board; loc = theBoard; do { // Find a piece if ((coloredPiece = *loc++) != 0) { // Must be current turn's color if (COLOR(coloredPiece) == turn) { piece = PIECE(coloredPiece); listOffset = i << moveListShift[piece]; movesBase = allMoves[turn][piece]; movesForPiece = movesBase + listOffset; nextDirBase = allOffsets[turn][piece]; nextDirOffset = nextDirBase + listOffset; // Replaced by optimz. below. // Since allMoves and allOffsets are sequential in memory (see MoveTable.c), // nextDirOffset is always equal to the move table position + sizeof(movetable): //nextDirOffset = movesForPiece + ALLMOVES_TABLE_SIZE; curMove = movesForPiece; //curDir = nextDirOffset; while ((dest = *curMove++) != 255) { // SPEEDUP: keep ptr here for "curDir", increment it on each loop. //curDir++; destPiece = theBoard[dest]; if (destPiece) { // Dest was full. Add capture if necessary, then index to next direction. if ((coloredPiece ^ destPiece) & 0x80) // neg xor pos = true -> capture { // Special case: pawn cannot capture along a file if ( (piece == PAWN) && ( ((dest - i) & 3) == 0 ) ) // I.e., if it's pawn capture along file ; // then don't add to move list. else { // Add capture //rmP->from = (char) i; //rmP->to = (char) dest; //(rmP++)->rank = CAPTURE_MOVE_RANK + // pieceVal[PIECE(destPiece)] - (pieceVal[piece] >> 4); *rmP++ = (unsigned char) i; *rmP++ = (unsigned char) dest; *( (short *) rmP)++ = CAPTURE_MOVE_RANK + pieceVal[PIECE(destPiece)] - (pieceVal[piece] >> 4); numMoves++; } } // Index to next direction. curMove = *(curMove - movesForPiece + nextDirOffset - 1) + movesForPiece; //curMove = movesForPiece + *(curDir - 1); } } } } i++; } while (i < lastSquare); // now add a null move to represent all non-capture moves //rmP->from = -2; //rmP->to = -2; //(rmP++)->rank = 0; *( (short *) rmP)++ = 0xFEFE; *( (short *) rmP)++ = 0x0000; numMoves++; // cheap, but after the fact assert(numMoves < RANKED_MOVE_SIZE); return numMoves; } //-------------------------------------------------------------------------- // returns moveCount /* static int ECRgenerateAllMoves(PlayerColor turn, const FastBoardType *board, int depth, int onlyFrom) { const int *maxMoveDistPieceList; const char *maxDistList; int fromRow; int from; int piece; int tempTo; int enPassantLoc = board->enPassantLoc; RankedMoveType *rmP = &(rankedMove[depth][0]); int moveCount = 0; int curDir; int curDist; int opposingPiece, occupyingPiece; const unsigned char *b = board->board; const unsigned char *bp; int startDir; int dirIncr; int maxDist; int maxMoveDistPiece; int moveIncr; int startFrom; int stopFrom; assert(depth < MAX_DEPTH); if(onlyFrom == -1){ startFrom = 0; stopFrom = kChessboardSize-1; bp = b; }else{ startFrom = onlyFrom; stopFrom = onlyFrom; bp = b + onlyFrom; } for(from = startFrom; from <= stopFrom; from++) { if((piece = *bp++) == 0) continue; if(COLOR(piece) == turn) { piece = PIECE(piece); maxMoveDistPieceList = maxMoveDistPieceTable[piece]; maxDistList = maxDistTable[from].dist; startDir = startDirectionTable[piece]; dirIncr = directionIncrTable[piece]; fromRow = ROW(from); for(curDir = startDir; curDir <= dir_wsw; curDir += dirIncr) { if((maxDist = maxDistList[curDir]) == 0) continue; if((maxMoveDistPiece = maxMoveDistPieceList[curDir]) == 0) continue; if(maxMoveDistPiece < maxDist) maxDist = maxMoveDistPiece; moveIncr = moveIncrTable[curDir]; tempTo = from; for(curDist = 1; curDist <= maxDist; curDist++) { tempTo += moveIncr; // assert(tempTo >= 0); // assert(tempTo < kChessboardSize); // castling //------------------------------------------------------------------- if((piece == KING) && (curDist == 2)) { if((curDir != dir_e) && (curDir != dir_w)) break; if(turn == white) { if(from != 60) // king moved break; if(curDir == dir_w) { if(!board->whiteQueenCastleAllowed) break; if(b[56] != WHITE_ROOK) // rook moved break; // piece in way if(b[57] || b[58] || b[59]) break; // king in check if(isAttacked(white,60,board,false)) break; if(isAttacked(white,59,board,false)) break; if(isAttacked(white,58,board,false)) break; rmP->from = (char)from; rmP->to = 58; (rmP++)->rank = CASTLE_MOVE_RANK; moveCount++; break; } else if (curDir == dir_e) { if(!board->whiteKingCastleAllowed) break; if(b[63] != WHITE_ROOK) // rook moved break; // piece in way if(b[61] || b[62]) break; // king in check if(isAttacked(white,60,board,false)) break; if(isAttacked(white,61,board,false)) break; if(isAttacked(white,62,board,false)) break; rmP->from = (char)from; rmP->to = 62; (rmP++)->rank = CASTLE_MOVE_RANK; moveCount++; break; } } else { // black if(from != 4) // king moved break; if(curDir == dir_w) { if(!board->blackQueenCastleAllowed) break; if(b[0] != BLACK_ROOK) // rook moved break; // piece in way if(b[1] || b[2] || b[3]) break; // king in check if(isAttacked(black,4,board,false)) break; if(isAttacked(black,3,board,false)) break; if(isAttacked(black,2,board,false)) break; rmP->from = (char)from; rmP->to = 2; (rmP++)->rank = CASTLE_MOVE_RANK; moveCount++; break; } else if (curDir == dir_e) { if(!board->blackKingCastleAllowed) break; if(b[7] != BLACK_ROOK) // rook moved break; // piece in way if(b[5] || b[6]) break; // king in check if(isAttacked(black,4,board,false)) break; if(isAttacked(black,5,board,false)) break; if(isAttacked(black,6,board,false)) break; rmP->from = (char)from; rmP->to = 6; (rmP++)->rank = CASTLE_MOVE_RANK; moveCount++; break; } } } //------------------------------------------------------------- if(piece == PAWN) { if((turn == white) && (curDir >= dir_se)) { break; } else if((turn == black) && (curDir <= dir_ne)) { break; } if(curDist == 2) { if(((turn == white) && ((fromRow != 6) || (curDir != dir_n))) || ((turn == black) && ((fromRow != 1) || (curDir != dir_s)))) { break; } } } occupyingPiece = b[tempTo]; if(!occupyingPiece || COLOR(occupyingPiece) == turn) opposingPiece = EMPTY; else opposingPiece = PIECE(occupyingPiece); if((piece == PAWN) && (tempTo == enPassantLoc)) opposingPiece = PAWN; if(piece == PAWN) { if((!opposingPiece && ((curDir != dir_n) && (curDir != dir_s))) || (opposingPiece && ((curDir == dir_n) || (curDir == dir_s)))) { break; } } if(opposingPiece) { rmP->from = (char)from; rmP->to = (char)tempTo; (rmP++)->rank = CAPTURE_MOVE_RANK + pieceVal[opposingPiece] - (pieceVal[piece] >> 4); moveCount++; break; } else { // friendlyPiece = occupyingPiece; if(occupyingPiece) break; rmP->from = (char)from; rmP->to = (char)tempTo; if(turn == white) { (rmP++)->rank = whitePosWeightTable[piece][tempTo] - whitePosWeightTable[piece][from]; } else { (rmP++)->rank = blackPosWeightTable[piece][tempTo] - blackPosWeightTable[piece][from]; } moveCount++; } } } } } // cheap, but after the fact assert(moveCount < RANKED_MOVE_SIZE); return moveCount; } //-------------------------------------------------------------------------- // returns moveCount static int ECRgenerateAllAttacks(PlayerColor turn, const FastBoardType *board, int depth) { const int *maxAttackDistPieceList; const char *maxDistList; int fromRow; int from; int piece; int tempTo; int enPassantLoc = board->enPassantLoc; RankedMoveType *rmP = &(rankedMove[depth][0]); int moveCount = 0; int curDir; int curDist; int opposingPiece, occupyingPiece; const unsigned char *b = board->board; const unsigned char *bp = b; int startDir; int dirIncr; int maxDist; int maxAttackDistPiece; int moveIncr; assert(depth < MAX_DEPTH); for(from = 0; from < kChessboardSize; from++){ if((piece = *bp++) == 0) continue; if(COLOR(piece) == turn){ piece = PIECE(piece); maxAttackDistPieceList = maxAttackDistPieceTable[piece]; maxDistList = maxDistTable[from].dist; startDir = startDirectionTable[piece]; dirIncr = directionIncrTable[piece]; fromRow = ROW(from); for(curDir = startDir; curDir <= dir_wsw; curDir += dirIncr){ if((maxDist = maxDistList[curDir]) == 0) continue; if((maxAttackDistPiece = maxAttackDistPieceList[curDir]) == 0) continue; if(maxAttackDistPiece < maxDist) maxDist = maxAttackDistPiece; moveIncr = moveIncrTable[curDir]; tempTo = from; for(curDist = 1; curDist <= maxDist; curDist++){ tempTo += moveIncr; // assert(tempTo >= 0); // assert(tempTo < kChessboardSize); //------------------------------------------------------------- if(piece == PAWN){ if((turn == white) && (curDir >= dir_se)){ break; } else if((turn == black) && (curDir <= dir_ne)){ break; } } occupyingPiece = b[tempTo]; if(!occupyingPiece || COLOR(occupyingPiece) == turn) opposingPiece = EMPTY; else opposingPiece = PIECE(occupyingPiece); if((piece == PAWN) && (tempTo == enPassantLoc)) opposingPiece = PAWN; if(opposingPiece){ rmP->from = (char)from; rmP->to = (char)tempTo; (rmP++)->rank = CAPTURE_MOVE_RANK + pieceVal[opposingPiece] - (pieceVal[piece] >> 4); moveCount++; break; }else{ // friendlyPiece = occupyingPiece; if(occupyingPiece){ break; } } } } } } // now add a null move to represent all non-capture moves rmP->from = -2; rmP->to = -2; (rmP++)->rank = 0; moveCount++; // cheap, but after the fact assert(moveCount < RANKED_MOVE_SIZE); return moveCount; } */ //-------------------------------------------------------------------------- static Boolean isValidCastle(PlayerColor turn, const FastBoardType *board, int from, int to) { int curDir; const unsigned char *b = board->board; if((to == 2)||(to == 58)) curDir = dir_w; else curDir = dir_e; //------------------------------------------------------------------- if(turn == white){ assert(from == 60); // king moved if(curDir == dir_w){ if(!board->whiteQueenCastleAllowed) return false; if(b[56] != WHITE_ROOK) // rook moved return false;; // piece in way if(b[57] || b[58] || b[59]) return false; // king in check if(isAttacked(white,60,board,false)) return false; if(isAttacked(white,59,board,false)) return false; //if(isAttacked(white,58,board,false)) // return false; return true; } else if (curDir == dir_e){ if(!board->whiteKingCastleAllowed) return false; if(b[63] != WHITE_ROOK) // rook moved return false; // piece in way if(b[61] || b[62]) return false; // king in check if(isAttacked(white,60,board,false)) return false; if(isAttacked(white,61,board,false)) return false; //if(isAttacked(white,62,board,false)) // return false; return true; } } else { // black assert(from == 4); // king moved if(curDir == dir_w){ if(!board->blackQueenCastleAllowed) return false; if(b[0] != BLACK_ROOK) // rook moved return false; // piece in way if(b[1] || b[2] || b[3]) return false; // king in check if(isAttacked(black,4,board,false)) return false; if(isAttacked(black,3,board,false)) return false; //if(isAttacked(black,2,board,false)) // return false; return true; } else if (curDir == dir_e){ if(!board->blackKingCastleAllowed) return false; if(b[7] != BLACK_ROOK) // rook moved return false; // piece in way if(b[5] || b[6]) return false; // king in check if(isAttacked(black,4,board,false)) return false; if(isAttacked(black,5,board,false)) return false; //if(isAttacked(black,6,board,false)) // return false; return true; } } assert(false); return false; } //-------------------------------------------------------------------------- // returns moveCount static int generateMove(PlayerColor turn, int *move0, int *move1, const FastBoardType *board, int depth, int *mmRank, int alpha, int beta, int *promotionPieceType, ListNode *repeatListHead, int repeatListLength, const PenaltyType *inPenalty, Boolean isExtension, int baseRank) { int bestRank; int curRank; int curMove0; int curMove1; int piece; Boolean foundJump = false; int moveCount; // int moveIndex; ListNode *curRepeatListHead; int curRepeatListLength; int promotionLoc; int promotionPiece; Boolean repeatable; Boolean isCapture; CastleInfoType castleInfo; FastBoardType tmpBoard; RankedMoveType *rmP = &(rankedMove[depth][0]); RankedMoveType *curP; RankedMoveType *stopP; RankedMoveType *cmpP; RankedMoveType *maxP; int max; RankedMoveType tmpRM; const unsigned char *b = board->board; int validMoveCount = 0; if(turn == white){ bestRank = MY_MIN + depth; }else{ bestRank = MY_MAX - depth; } curMove0 = -1; curMove1 = -1; *move0 = -1; *move1 = -1; if((depth != 0) || (maxDepth == 0)){ if(!isExtension && (depth > 1) && (depth == maxDepth)){ moveCount = generateAllAttacks(turn,board,depth); }else{ moveCount = generateAllMoves(turn,board,depth,-1); if(depth == 0) baseMoveCount = moveCount; } }else{ moveCount = baseMoveCount; } stopP = rmP + moveCount; // for(moveIndex = 0; moveIndex < moveCount; moveIndex++){ for(curP = rmP; curP < stopP; curP++){ // find largest elem, swap it with moveIndex item cmpP = curP+1; maxP = curP; max = maxP->rank; // for(i = moveIndex+1; i < moveCount; i++){ for(; cmpP < stopP;){ if(cmpP->rank > max){ maxP = cmpP++; max = maxP->rank; }else{ cmpP++; } } if(maxP != curP){ tmpRM = *curP; *curP = *maxP; *maxP = tmpRM; } curMove0 = curP->from; curMove1 = curP->to; if(curMove0 < 0){ piece = KING; }else{ piece = PIECE(b[curMove0]); } if((piece == KING) && (((turn == black) && (curMove0 == 4) && ((curMove1 == 2)||(curMove1 == 6))) || ((turn == white) && (curMove0 == 60) && ((curMove1 == 58)||(curMove1 == 62))))) { if(!isValidCastle(turn,board,curMove0,curMove1)){ curP->rank = MY_MIN; continue; } } isCapture = applyMove(&tmpBoard,board,curMove0,curMove1,turn, &repeatable,&castleInfo); if(curMove0 < 0) repeatable = false; if(repeatable){ curRepeatListHead = repeatListHead; curRepeatListLength = repeatListLength; }else{ curRepeatListHead = 0; curRepeatListLength = 0; } // may not make move (of king or other piece) which places king in check if(isKingInCheckBB(turn,&tmpBoard)){ curP->rank = MY_MIN; continue; } validMoveCount++; if(piece == PAWN) promotionLoc = findPromotion(&tmpBoard); else promotionLoc = -1; for(promotionPiece = QUEEN; promotionPiece < PAWN; promotionPiece++){ if(promotionLoc != -1) applyPromotion(&tmpBoard,promotionLoc,promotionPiece); curRank = minMaxRankBoard(turn,&tmpBoard,depth, alpha,beta, curRepeatListHead,curRepeatListLength, &castleInfo,inPenalty, curMove1, isCapture,isExtension,bestRank,move0,baseRank); if(((turn == white) && (curRank > bestRank)) || ((turn == black) && (curRank < bestRank)) || (*move0 == -1)) { bestRank = curRank; *move0 = curMove0; *move1 = curMove1; *promotionPieceType = promotionPiece; } // note copy below if(turn == white){ if(bestRank > alpha) alpha = bestRank; if(alpha >= beta){ *mmRank = beta; goto doneGenerateMove; } }else{ if(bestRank < beta) beta = bestRank; if(beta <= alpha){ *mmRank = alpha; goto doneGenerateMove; } } if(promotionLoc == -1) break; } } if(turn == white){ *mmRank = alpha; }else{ *mmRank = beta; } doneGenerateMove: if(*move0 == -1){ if(!isKingInCheckBB(turn,board)){ *mmRank = 0; // stalemate draw } } return validMoveCount; } //-------------------------------------------------------------------------- static PieceType fastPieceToBoardPiece(PlayerColor turn, int fastPiece){ if(turn == white){ switch(fastPiece){ case KING: return whiteking; break; case QUEEN: return whitequeen; break; case ROOK: return whiterook; break; case BISHOP: return whitebishop; break; case KNIGHT: return whiteknight; break; case PAWN: return whitepawn; break; } }else{ switch(fastPiece){ case KING: return blackking; break; case QUEEN: return blackqueen; break; case ROOK: return blackrook; break; case BISHOP: return blackbishop; break; case KNIGHT: return blackknight; break; case PAWN: return blackpawn; break; } } return empty; } //-------------------------------------------------------------------------- static void readCastleAllowed( Boolean *blackQueenCastleAllowed, Boolean *blackKingCastleAllowed, Boolean *whiteQueenCastleAllowed, Boolean *whiteKingCastleAllowed) { CastleAllowedType cat[4]; GetMostRecentCastleState(cat); if(cat[0]) *whiteQueenCastleAllowed = true; else *whiteQueenCastleAllowed = false; if(cat[1]) *whiteKingCastleAllowed = true; else *whiteKingCastleAllowed = false; if(cat[2]) *blackQueenCastleAllowed = true; else *blackQueenCastleAllowed = false; if(cat[3]) *blackKingCastleAllowed = true; else *blackKingCastleAllowed = false; } //-------------------------------------------------------------------------- int lengthRepeatList(const FatListNode *repeatListHead){ const FatListNode *tp = repeatListHead; int len = 0; while(tp){ len++; tp = (FatListNode *)tp->node.next; } return len; } //-------------------------------------------------------------------------- // move[] array is filled in: move[0] is start position; // move[1] is destination int ChessAIGenerateMove(PlayerColor turn, Location move[], const GameStateType *board, UInt32 maxTimeInSeconds, Boolean *abortedDueToEvent, PieceType *promotionPieceType, FatListNode *repeatListHead, Boolean stopOnEvent) { int mmRank; FastBoardType fb; int fastPromotionPieceType = EMPTY; Boolean blackQueenCastleAllowed; Boolean blackKingCastleAllowed; Boolean whiteQueenCastleAllowed; Boolean whiteKingCastleAllowed; int realRepeatListLength = lengthRepeatList(repeatListHead); int repeatListLength = movesSinceLastIrreversibleEvent(); PenaltyType penalty; int curMove[2]; int validMoveCount; #ifndef BENCHMARK char *openingMoveStr; #endif UInt32 halfStopTime; if(stopOnEvent) doStopOnEvent = true; else doStopOnEvent = false; //assert((realRepeatListLength+1) == repeatListLength); *promotionPieceType = empty; maxDepth = 0; baseTurn = turn; initPenalty(&penalty); rankCalls = 0; readCastleAllowed(&blackQueenCastleAllowed,&blackKingCastleAllowed, &whiteQueenCastleAllowed,&whiteKingCastleAllowed); boardToFastBoard(&fb,board,GetMostRecentEnPassant(flipTurn(turn)), blackQueenCastleAllowed,blackKingCastleAllowed, whiteQueenCastleAllowed,whiteKingCastleAllowed,false); halfStopTime = TimGetTicks() + ((maxTimeInSeconds * SysTicksPerSecond()) >> 1); stopTime = TimGetTicks() + maxTimeInSeconds * SysTicksPerSecond() * TIME_MULT; if(maxTimeInSeconds == 0) easy = true; else easy = false; #ifdef BENCHMARK halfStopTime = stopTime; #endif abortDueToEvent = false; *abortedDueToEvent = false; curMove[0] = -1; curMove[1] = -1; move[0] = -1; move[1] = -1; #ifndef BENCHMARK openingMoveStr = getOpeningMoves(chess); if(findChessOpening(openingMoveStr,&(move[0]),&(move[1]))) return 1; #endif move[0] = -1; move[1] = -1; // try/catch is used to exit immediately from search // when stop time is reached or event received ErrTry{ do{ fastPromotionPieceType = EMPTY; validMoveCount = generateMove(turn,&(curMove[0]),&(curMove[1]), &fb,0,&mmRank, MY_MIN,MY_MAX,&fastPromotionPieceType, &(repeatListHead->node), repeatListLength,&penalty,false,0); move[0] = (Location)(curMove[0]); move[1] = (Location)(curMove[1]); *promotionPieceType = fastPieceToBoardPiece(turn,fastPromotionPieceType); if((move[0] != -1) && (validMoveCount > 1)){ markBestMove(move[0],move[1]); }else{ break; } if((maxDepth++ >= 1)&&(TimGetTicks() > halfStopTime)) break; } while(maxDepth < MAX_DEPTH); } ErrCatch(error){ } ErrEndCatch if(abortDueToEvent){ *abortedDueToEvent = true; //ErrDisplay("abort due to event!"); return 0; } if(move[0] == -1) return 0; else return 1; } //-------------------------------------------------------------------------- // fills in available move board: empty == invalid move, // whitepawn == valid move Boolean listValidChessMoves(PlayerColor turn, const GameStateType *currentBoard, GameStateType *availableMoveBoard, Location from) { FastBoardType board; FastBoardType tmpBoard; Boolean isCapture; int piece; int to; int enPassantLoc; int i; Boolean blackQueenCastleAllowed; Boolean blackKingCastleAllowed; Boolean whiteQueenCastleAllowed; Boolean whiteKingCastleAllowed; Boolean repeatable; Boolean moveFound = false; CastleInfoType castleInfo; int mFrom; int moveCount; for(i = 0; i < kChessboardSize; i++) availableMoveBoard->board.chessboard[i] = empty; readCastleAllowed(&blackQueenCastleAllowed,&blackKingCastleAllowed, &whiteQueenCastleAllowed,&whiteKingCastleAllowed); boardToFastBoard(&board,currentBoard, GetMostRecentEnPassant(flipTurn(turn)), blackQueenCastleAllowed,blackKingCastleAllowed, whiteQueenCastleAllowed,whiteKingCastleAllowed,false); enPassantLoc = board.enPassantLoc; piece = PIECE(board.board[from]); if(!piece) return false; moveCount = generateAllMoves(turn,&board,0,from); for(i = 0; i < moveCount; i++){ mFrom = rankedMove[0][i].from; to = rankedMove[0][i].to; if(from != mFrom) continue; if((piece == KING) && (((turn == black) && (mFrom == 4) && ((to == 2)||(to == 6))) || ((turn == white) && (mFrom == 60) && ((to == 58)||(to == 62))))) { if(!isValidCastle(turn,&board,mFrom,to)){ continue; } } isCapture = applyMove(&tmpBoard,&board,from,to,turn, &repeatable,&castleInfo); // may not make move (of king or other piece) which places king in check if(isKingInCheckBB(turn,&tmpBoard)){ continue; } availableMoveBoard->board.chessboard[to] = whitepawn; moveFound = true; } return moveFound; } //-------------------------------------------------------------------------- void freeRepeatList(FatListNode *repeatListHead){ FatListNode *tp; while(repeatListHead){ tp = (FatListNode *)repeatListHead->node.next; MemPtrFree(repeatListHead); repeatListHead = tp; } } //-------------------------------------------------------------------------- Boolean isThriceRepeatedBoard(FatListNode *head, GameStateType *state, PlayerColor turn) { FatListNode *p = head; FastBoardType fastboard; int repeatCount = 0; Boolean castle1, castle2, castle3, castle4; readCastleAllowed(&castle1, &castle2, &castle3, &castle4); boardToFastBoard(&fastboard, state, GetMostRecentEnPassant((PlayerColor) (black - turn)), castle1, castle2, castle3, castle4, true); while (p != 0) { if ((p->node.turn != turn) && (isEqualFastBoard(&(p->fb), &fastboard))) repeatCount++; p = (FatListNode *) p->node.next; } if (repeatCount < 3) return false; else return true; } //-------------------------------------------------------------------------- // returns new list head // automatically deletes old list nodes if repeatable == false // If unable to allocate new node repeatList is freed and 0 is returned. // In this case app should display alert // "Dynamic Memory Low. Repeated board configuration and 50 move // rule draw detection disabled." FatListNode *addListNode(FatListNode *repeatListHead, const GameStateType *board, Boolean repeatable, PlayerColor turn) { FatListNode *n = 0; if(!repeatable){ freeRepeatList(repeatListHead); repeatListHead = 0; } n = (FatListNode *)MemPtrNew(sizeof(FatListNode)); if(n == 0){ freeRepeatList(repeatListHead); return 0; } boardToFastBoard(&(n->fb),board,-1,false,false,false,false,true); initListNode(&(n->node),&(n->fb),&(repeatListHead->node),turn); return n; } //-------------------------------------------------------------------------- int getChessAILevel(int *nodes) { *nodes = (int)rankCalls; return maxDepth; } //-------------------------------------------------------------------------- Boolean isKingInCheck(PlayerColor turn, const GameStateType *currentBoard) { FastBoardType board; Boolean blackQueenCastleAllowed; Boolean blackKingCastleAllowed; Boolean whiteQueenCastleAllowed; Boolean whiteKingCastleAllowed; // yes, castle, en-passant probably not necessary... readCastleAllowed(&blackQueenCastleAllowed,&blackKingCastleAllowed, &whiteQueenCastleAllowed,&whiteKingCastleAllowed); boardToFastBoard(&board,currentBoard, GetMostRecentEnPassant(flipTurn(turn)), blackQueenCastleAllowed,blackKingCastleAllowed, whiteQueenCastleAllowed,whiteKingCastleAllowed,false); return isKingInCheckBB(turn,&board); } //-------------------------------------------------------------------------- extern void InitChessAI(); void InitChessAI(){ int setBreakHere = 0; DmResID i; #ifdef VERIFY_MOVE_RESOURCE //DEBUG int j; #endif #ifdef VERIFY_BITBOARD_RESOURCE int k; #endif setBreakHere++; // Resources for valid chess move tables: for (i = 0; i < 16; i++) { allMovesH[i] = DmGetResource('MOVE', CHESS_MOVES_RSRC_ID+i); assert(allMovesH[i]); } allMoves[0][0] = 0; // Empty allMoves[0][1] = MemHandleLock(allMovesH[0]); // White king allMoves[0][2] = MemHandleLock(allMovesH[2]); // Queen allMoves[0][3] = MemHandleLock(allMovesH[5]); // Rook allMoves[0][4] = MemHandleLock(allMovesH[3]); // Bishop allMoves[0][5] = MemHandleLock(allMovesH[4]); // Knight allMoves[0][6] = MemHandleLock(allMovesH[6]); // White pawn allMoves[1][0] = 0; // Empty allMoves[1][1] = MemHandleLock(allMovesH[1]); // Black king allMoves[1][2] = allMoves[0][2]; // Queen allMoves[1][3] = allMoves[0][3]; // Rook allMoves[1][4] = allMoves[0][4]; // Bishop allMoves[1][5] = allMoves[0][5]; // Knight allMoves[1][6] = MemHandleLock(allMovesH[7]); // Black pawn allOffsets[0][0] = 0; // Empty allOffsets[0][1] = MemHandleLock(allMovesH[0 + 8]); // White king allOffsets[0][2] = MemHandleLock(allMovesH[2 + 8]); // Queen allOffsets[0][3] = MemHandleLock(allMovesH[5 + 8]); // Rook allOffsets[0][4] = MemHandleLock(allMovesH[3 + 8]); // Bishop allOffsets[0][5] = MemHandleLock(allMovesH[4 + 8]); // Knight allOffsets[0][6] = MemHandleLock(allMovesH[6 + 8]); // White pawn allOffsets[1][0] = 0; // Empty allOffsets[1][1] = MemHandleLock(allMovesH[1 + 8]); // Black king allOffsets[1][2] = allOffsets[0][2]; // Queen allOffsets[1][3] = allOffsets[0][3]; // Rook allOffsets[1][4] = allOffsets[0][4]; // Bishop allOffsets[1][5] = allOffsets[0][5]; // Knight allOffsets[1][6] = MemHandleLock(allMovesH[7 + 8]); // Black pawn for (i = 1; i < 7; i++) { assert(allMoves[0][i]); assert(allMoves[1][i]); assert(allOffsets[0][i]); assert(allOffsets[1][i]); #ifdef VERIFY_MOVE_RESOURCE // DEBUG for (j = 0; j < 64* moveListSize[i]; j++) { assert(allMoves[0][i][j] == OLDallMoves[0][i][j]); assert(allMoves[1][i][j] == OLDallMoves[1][i][j]); assert(allOffsets[0][i][j] == OLDallOffsets[0][i][j]); assert(allOffsets[1][i][j] == OLDallOffsets[1][i][j]); } #endif } moveBoardH = DmGetResource('BBRD', CHESS_BITBOARD_RSRC_ID); assert(moveBoardH); whitePawnMoveBoardH = DmGetResource('BBRD', CHESS_BITBOARD_RSRC_ID+1); assert(whitePawnMoveBoardH); blackPawnMoveBoardH = DmGetResource('BBRD', CHESS_BITBOARD_RSRC_ID+2); assert(blackPawnMoveBoardH); moveBoard = (MoveBoardType *)MemHandleLock(moveBoardH); assert(moveBoard); whitePawnMoveBoard = (BitBoard *)MemHandleLock(whitePawnMoveBoardH); assert(whitePawnMoveBoard); blackPawnMoveBoard = (BitBoard *)MemHandleLock(blackPawnMoveBoardH); assert(blackPawnMoveBoard); opposingPawnMoveBoard[0] = blackPawnMoveBoard; opposingPawnMoveBoard[1] = whitePawnMoveBoard; #ifdef VERIFY_BITBOARD_RESOURCE for(i = 0; i < 5; i++){ for(k = 0; k < kChessboardSize; k++){ assert((*rmoveBoard)[i][k].top == moveBoard[i][k].top); assert((*rmoveBoard)[i][k].bottom == moveBoard[i][k].bottom); } } for(i = 0; i < kChessboardSize; i++){ assert(whitePawnMoveBoard[i].top == rwhitePawnMoveBoard[i].top); assert(whitePawnMoveBoard[i].bottom == rwhitePawnMoveBoard[i].bottom); } for(i = 0; i < kChessboardSize; i++){ assert(blackPawnMoveBoard[i].top == rblackPawnMoveBoard[i].top); assert(blackPawnMoveBoard[i].bottom == rblackPawnMoveBoard[i].bottom); } #endif } //-------------------------------------------------------------------------- extern void ChessAIStop(); void ChessAIStop() { int i; if (gRepeatListHead) { freeRepeatList(gRepeatListHead); gRepeatListHead = 0; } for (i = 0; i < 16; i++) { if(allMovesH[i]){ MemHandleUnlock(allMovesH[i]); DmReleaseResource(allMovesH[i]); allMovesH[i] = 0; } } if(moveBoardH){ MemHandleUnlock(moveBoardH); DmReleaseResource(moveBoardH); moveBoardH = 0; } if(whitePawnMoveBoardH){ MemHandleUnlock(whitePawnMoveBoardH); DmReleaseResource(whitePawnMoveBoardH); whitePawnMoveBoardH = 0; } if(blackPawnMoveBoardH){ MemHandleUnlock(blackPawnMoveBoardH); DmReleaseResource(blackPawnMoveBoardH); blackPawnMoveBoardH = 0; } }