From 3fd43cd5fcb22bb65bf2a92a25d95d801b11c9e0 Mon Sep 17 00:00:00 2001 From: Scott Gasch Date: Wed, 1 Jun 2016 18:58:58 -0700 Subject: Initial checkin for typhoon chess engine. --- src/see.c | 981 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 981 insertions(+) create mode 100755 src/see.c (limited to 'src/see.c') diff --git a/src/see.c b/src/see.c new file mode 100755 index 0000000..292cbf1 --- /dev/null +++ b/src/see.c @@ -0,0 +1,981 @@ +/** + +Copyright (c) Scott Gasch + +Module Name: + + see.c + +Abstract: + + Static exchange evaluator and support code. See also x86.asm. + +Author: + + Scott Gasch (scott.gasch@gmail.com) 11 Jun 2004 + +Revision History: + + $Id: see.c 348 2008-01-05 07:11:36Z scott $ + +**/ + +#include "chess.h" + +#define ADD_ATTACKER(p, c, v) \ + pList->data[pList->uCount].pPiece = (p); \ + pList->data[pList->uCount].cLoc = (c); \ + pList->data[pList->uCount].uVal = (v); \ + pList->uCount++; + +void CDECL +SlowGetAttacks(IN OUT SEE_LIST *pList, + IN POSITION *pos, + IN COOR cSquare, + IN ULONG uSide) +/*++ + +Routine description: + + SlowGetAttacks is the C version of GetAttacks; it should be + identical to the GetAttacks code in x86.asm. The job of the + function is, given a position, square and side, to populate the + SEE_LIST with the locations and types of enemy pieces attacking + the square. + +Parameters: + + SEE_LIST *pList : list to populate + POSITION *pos : the board + COOR cSquare : square in question + ULONG uSide : side we are looking for attacks from + +Return value: + + void + +--*/ +{ + register ULONG x; + PIECE p; + COOR c; + int iIndex; + COOR cBlockIndex; + int iDelta; + static PIECE pPawn[2] = { BLACK_PAWN, WHITE_PAWN }; + static int iSeeDelta[2] = { -17, +15 }; + +#ifdef DEBUG + ASSERT(IS_ON_BOARD(cSquare)); + ASSERT(IS_VALID_COLOR(uSide)); + VerifyPositionConsistency(pos, FALSE); +#endif + pList->uCount = 0; + + // + // Check for pawns attacking cSquare + // + c = cSquare + (iSeeDelta[uSide]); + if (IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + if (p == pPawn[uSide]) + { + // + // N.B. Don't use ADD_ATTACKER here because we know we're + // at element zero. + // + pList->data[0].pPiece = p; + pList->data[0].cLoc = c; + pList->data[0].uVal = VALUE_PAWN; + pList->uCount = 1; + } + } + + c += 2; + if (IS_ON_BOARD(c)) + { + p = pos->rgSquare[c].pPiece; + if (p == pPawn[uSide]) + { + ADD_ATTACKER(p, c, VALUE_PAWN); + } + } + + // + // Check for pieces attacking cSquare + // + for (x = pos->uNonPawnCount[uSide][0] - 1; + x != (ULONG)-1; + x--) + { + c = pos->cNonPawns[uSide][x]; + ASSERT(IS_ON_BOARD(c)); + + p = pos->rgSquare[c].pPiece; + ASSERT(p && !IS_PAWN(p)); + ASSERT(GET_COLOR(p) == uSide); + + iIndex = (int)c - (int)cSquare; + if (0 == (CHECK_VECTOR_WITH_INDEX(iIndex, GET_COLOR(p)) & + (1 << PIECE_TYPE(p)))) + { + continue; + } + + if (IS_KNIGHT_OR_KING(p)) + { + ASSERT(IS_KNIGHT(p) || IS_KING(p)); + ADD_ATTACKER(p, c, PIECE_VALUE(p)); + continue; + } + + // + // Check to see if there is a piece in the path from cSquare + // to c that blocks the attack. + // + iDelta = NEG_DELTA_WITH_INDEX(iIndex); + ASSERT(iDelta == -1 * CHECK_DELTA_WITH_INDEX(iIndex)); + ASSERT(iDelta != 0); + for (cBlockIndex = cSquare + iDelta; + cBlockIndex != c; + cBlockIndex += iDelta) + { + if (!IS_EMPTY(pos->rgSquare[cBlockIndex].pPiece)) + { + goto done; + } + } + + // + // Nothing in the way. + // + ADD_ATTACKER(p, c, PIECE_VALUE(p)); + + done: + ; + } +} + +#ifdef SEE_HEAPS +// +// SEE_HEAPS works great in principle but makes MinLegalPiece +// inaccurate if the top of the heap is not a legal move (i.e. the +// piece is pinned etc...) When tested the result of this was minimal +// and the use of a heap instead of a sorted list sped up the SEE +// code. +// +#define PARENT(x) ((x - 1) / 2) +#define LEFT_CHILD(x) (((x) * 2) + 1) +#define RIGHT_CHILD(x) (((x) * 2) + 2) + +#ifdef DEBUG +static FLAG +_IsValidHeap(IN SEE_LIST *p) +/** + +Routine description: + + Is the minheap in SEE_LIST p->data[] valid (i.e. does it satisfy + the minheap property?) + +Parameters: + + SEE_LIST *p : SEE_LIST to check + +Return value: + + static FLAG : TRUE if valid, FALSE otherwise + +**/ +{ + ULONG u, l, r; + + for (u = 0; u < p->uCount; u++) + { + l = LEFT_CHILD(u); + if ((l < p->uCount) && (p->data[l].uVal < p->data[u].uVal)) + { + return(FALSE); + } + + r = RIGHT_CHILD(u); + if ((r < p->uCount) && (p->data[r].uVal < p->data[u].uVal)) + { + return(FALSE); + } + } + return(TRUE); +} +#endif // DEBUG + + +static void +_PushDown(IN OUT SEE_LIST *p, + IN ULONG u) +/** + +Routine description: + + Take heap node number u and compare its value with the value of + its children. Swap smallest value into position u and continue + the push-down process if warranted. + +Parameters: + + SEE_LIST *p : SEE_LIST/minheap + ULONG u : node number in consideration + +Return value: + + static void + +**/ +{ + ULONG l = LEFT_CHILD(u); + ULONG r; + ULONG uSmallest; + SEE_THREESOME temp; + + // + // The heap is a complete tree -- if there's no left child of this + // node then there's no right child either. If this is a leaf node + // then our work is done. + // + ASSERT(p->uCount > 0); + if (l >= p->uCount) + { + return; + } + ASSERT(PARENT(l) == u); + + // + // Otherwise, find the smallest of u, l and r. + // + r = l + 1; + ASSERT(r == RIGHT_CHILD(u)); + ASSERT(PARENT(r) == u); + ASSERT((r != u) && (r != l) && (l != u)); + uSmallest = u; + if (p->data[l].uVal < p->data[u].uVal) + { + uSmallest = l; + } + if ((r < p->uCount) && (p->data[r].uVal < p->data[uSmallest].uVal)) + { + uSmallest = r; + } + + // + // If it's anything other than u, swap them and continue to push. + // + if (uSmallest != u) + { + ASSERT((uSmallest == l) || (uSmallest == r)); + temp = p->data[uSmallest]; + p->data[uSmallest] = p->data[u]; + p->data[u] = temp; + _PushDown(p, uSmallest); + } +} + +static void +_BuildHeap(IN OUT SEE_LIST *p) +/** + +Routine description: + + Convert a random array into a minheap. Start at the first + internal node and push it down into place. Continue to work + backwards until we get to the root (index 0). + +Parameters: + + SEE_LIST *p : list to heapify + +Return value: + + static void + +**/ +{ + int iStart = (p->uCount / 2) - 1; + int i; + + ASSERT(iStart < (int)p->uCount); + for (i = iStart; i > -1; i--) + { + ASSERT(i >= 0); + _PushDown(p, (ULONG)i); + } + ASSERT(_IsValidHeap(p)); +} + + +static void +_BubbleUp(IN OUT SEE_LIST *p, IN ULONG u) +/** + +Routine description: + + Take a node and bubble it up into place to re-create a minheap. + +Parameters: + + SEE_LIST *p : heap + ULONG u : index of node to bubble up + +Return value: + + static void + +**/ +{ + ULONG uParent; + SEE_THREESOME temp; + + ASSERT(p->uCount > 0); + if (u == 0) return; + + uParent = PARENT(u); + ASSERT((LEFT_CHILD(uParent) == u) || + (RIGHT_CHILD(uParent) == u)); + ASSERT(uParent < u); + if (p->data[uParent].uVal > p->data[u].uVal) + { + temp = p->data[uParent]; + p->data[uParent] = p->data[u]; + p->data[u] = temp; + _BubbleUp(p, uParent); + } +} + +#else // !SEE_HEAPS + +static void +_SortList(IN OUT SEE_LIST *pList) +/** + +Routine description: + + Sort the SEE list by piece value with a selection sort. + +Parameters: + + SEE_LIST *pList + +Return value: + + static void + +**/ +{ + ULONG x; + ULONG y; + register ULONG uMaxVal; + register ULONG uMaxLoc; + SEE_THREESOME sTemp; + + for (x = 0; + x < pList->uCount; + x++) + { + // + // Assume index X is the largest value item in the list + // + uMaxVal = pList->data[x].uVal; + uMaxLoc = x; + + // + // Look for others with a larger value + // + for (y = x + 1; + y < pList->uCount; + y++) + { + if (pList->data[y].uVal > uMaxVal) + { + uMaxVal = pList->data[y].uVal; + uMaxLoc = y; + } + } + + sTemp = pList->data[uMaxLoc]; + pList->data[uMaxLoc] = pList->data[x]; + pList->data[x] = sTemp; + } +} + +#endif + +static void INLINE +_RemoveItem(IN OUT SEE_LIST *pList, + IN ULONG x) +/** + +Routine description: + + Delete item x from the list. + +Parameters: + + SEE_LIST *pList, + ULONG x + +Return value: + + static void INLINE + +**/ +{ +#ifndef SEE_HEAPS + ULONG y; +#endif + + ASSERT(x < pList->uCount); + ASSERT(pList->uCount > 0); + +#ifdef SEE_HEAPS + // + // Swap item x with the last thing on the heap and then push the + // node back down. + // + if (x != (pList->uCount - 1)) + { + pList->data[x] = pList->data[pList->uCount - 1]; + pList->uCount--; + _PushDown(pList, 0); + } + else + { + pList->uCount--; + } + +#else // !SEE_HEAPS + + // + // If X is not the last thing in the list we will have to ripple + // shift to close the hole. This is rare. + // + for (y = x + 1; + y < pList->uCount; + y++) + { + pList->data[y - 1] = pList->data[y]; + } + pList->uCount--; + +#endif // SEE_HEAPS +} + + +static void +_ClearPieceByLocation(IN OUT SEE_LIST *pList, + IN COOR cLoc) +/** + +Routine description: + + Find a piece on the SEE list at COOR cLoc and delete it. + +Parameters: + + SEE_LIST *pList, + COOR cLoc + +Return value: + + static void + +**/ +{ + ULONG x = 0; + + while (x < pList->uCount) + { + if (pList->data[x].cLoc == cLoc) + { + _RemoveItem(pList, x); + return; + } + x++; + } + + // + // This can happen if, for example, the SEE move was a passed pawn push + // +} + + +#ifdef SEE_HEAPS +static PIECE +_MinLegalPiece(IN POSITION *pos, + IN ULONG uColor, + IN SEE_LIST *pList, + IN SEE_LIST *pOther, + IN COOR *pc, + IN COOR cIgnore) +/** + +Routine description: + + Return the piece from the SEE list with the lowest value that is + not pinned to its own king. Because we are storing the SEE_LISTS + as heaps, this is only an approximate value in the event that the + real min value piece is indeed pinned to its own king. I + considered sorting the list in this case but it seems like (in + tests) this inaccuracy really has little or no impact on the + search tree size. The speedup with heaps instead of sorted lists + seems worth the price. + +Parameters: + + POSITION *pos : the board + ULONG uColor : the color on move + SEE_LIST *pList : the list we're selecting from + SEE_LIST *pOther : the other side's list + COOR *pc, + COOR cIgnore + +Return value: + + static PIECE + +**/ +{ + COOR cKing; + PIECE p; + register ULONG x; + COOR c; + + // + // The list is a minheap with the min value piece at index 0. + // + for (x = 0; + x < pList->uCount; + x++) + { + p = pList->data[x].pPiece; + + // + // If this piece is the king, then no need to see if the move + // exposes the king to check.. just play the move as long as + // it's legal (i.e. no defenders to the square) + // + if (IS_KING(p)) + { + if (pOther->uCount == 0) + { + *pc = pList->data[0].cLoc; + + // + // Note: if p is a king and we allow them to play it then + // by definition the other side has nothing to counter + // with... otherwise we'd be moving into check here. So + // even if we had other pieces that were pinned to the + // king, empty out the list because we're done in the next + // SEE loop. + // + pList->uCount = 0; + return(p); + } + } + else + { + // + // Otherwise... consider pins. If the least valuable + // defender of the square cannot move because doing so + // would exposes his king to check, skip it and try the + // next least valuable. + // + cKing = pos->cNonPawns[uColor][0]; + c = ExposesCheck(pos, pList->data[x].cLoc, cKing); + + // + // cIgnore is the coordinate of the last piece the other + // side "moved" in this capture sequence. This is a hack + // to ignore pins based on a piece that has already moved + // in the computation but is already on the board. This + // of course does not work for positions where the piece + // you expose check to was "moved" two turns ago but these + // are pretty rare. + // + if (!IS_ON_BOARD(c) || (c == cIgnore)) + { + *pc = pList->data[x].cLoc; + _RemoveItem(pList, x); + return(p); + } + } + } + + // + // There are no legal pieces to move to square + // + return(0); +} + +#else // !SEE_HEAPS + +static PIECE +_MinLegalPiece(IN POSITION *pos, + IN ULONG uColor, + IN SEE_LIST *pList, + IN SEE_LIST *pOther, + IN COOR *pc, + IN COOR cIgnore) +/** + +Routine description: + + Return the piece from the SEE list with the lowest value that is + not pinned to its own king. + +Parameters: + + POSITION *pos : the board + ULONG uColor : the color on move + SEE_LIST *pList : the list we're selecting from + SEE_LIST *pOther : the other side's list + COOR *pc, + COOR cIgnore + +Return value: + + static PIECE + +**/ +{ + COOR cKing; + PIECE p; + register ULONG x; + COOR c; + + // + // The list is sorted from most valuable (index 0) to least valuable + // (index N). Begin at the least valuable and work up. + // + for (x = pList->uCount - 1; + x != (ULONG)-1; + x--) + { + p = pList->data[x].pPiece; + // + // If this piece is the king, then no need to see if the move + // exposes the king to check.. just play the move as long as + // it's legal (i.e. no defenders to the square) + // + if ((IS_KING(p)) && (pOther->uCount == 0)) + { + ASSERT(x == 0); + *pc = pList->data[0].cLoc; + pList->uCount = 0; + return(p); + } + else + { + // + // Otherwise... consider pins. If the least valuable + // defender of the square cannot move because doing so + // would exposes his king to check, skip it and try the + // next least valuable. + // + cKing = pos->cNonPawns[uColor][0]; + c = ExposesCheck(pos, pList->data[x].cLoc, cKing); + + // + // cIgnore is the coordinate of the last piece the other + // side "moved" in this capture sequence. This is a hack + // to ignore pins based on a piece that has already moved + // in the computation but is already on the board. This + // of course does not work for positions where the piece + // you expose check to was "moved" two turns ago but these + // are pretty rare. + // + if (!IS_ON_BOARD(c) || (c == cIgnore)) + { + *pc = pList->data[x].cLoc; + _RemoveItem(pList, x); + return(p); + } + } + } + + // + // There are no legal pieces to move to square + // + return(0); +} +#endif // SEE_HEAPS + +static void _AddXRays(IN POSITION *pos, + IN INT iAttackerColor, + IN COOR cTarget, + IN COOR cObstacle, + IN OUT SEE_LIST *pAttacks, + IN OUT SEE_LIST *pDefends) +/** + +Routine description: + + We just "moved" a piece in the SEE sequence... add any xray + attacks that it exposed to the SEE list to be take part as the + sequence plays out. + +Parameters: + + POSITION *pos, + INT iAttackerColor, + COOR cTarget, + COOR cObstacle, + SEE_LIST *pAttacks, + SEE_LIST *pDefends + +Return value: + + static void + +**/ +{ + int iDelta; + COOR cIndex; + PIECE xPiece; + int iIndex; + + iIndex = (int)cTarget - (int)cObstacle; + + // + // If there is no way for a queen sitting on the target square to + // reach the obsticle square then there is no discovered attack. + // (This could happen, for instance, if a knight captured. It + // can't uncover a new attack on the square where it took. + // + if (0 == (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) & (1 << QUEEN))) + { + return; + } + + // + // The squares are on the same rank, file or diagonal. iDelta is + // the way to move from target towards obstacle. + // + iDelta = CHECK_DELTA_WITH_INDEX(iIndex); + + // + // Search for a piece that moves the right way to attack the target + // square starting at the obstacle square + delta. + // + for (cIndex = cObstacle + iDelta; + IS_ON_BOARD(cIndex); + cIndex += iDelta) + { + xPiece = pos->rgSquare[cIndex].pPiece; + if (!IS_EMPTY(xPiece)) + { + // + // Does it move the right way to hit cTarget? TODO: can this + // be optimized? Remember pawns though... + // + if (0 != (CHECK_VECTOR_WITH_INDEX((int)cIndex - (int)cTarget, + GET_COLOR(xPiece)) & + (1 << PIECE_TYPE(xPiece)))) + { + // + // Add this attacker to the proper SEE_LIST + // + if (GET_COLOR(xPiece) == iAttackerColor) + { + pAttacks->data[pAttacks->uCount].pPiece = xPiece; + pAttacks->data[pAttacks->uCount].cLoc = cIndex; + pAttacks->data[pAttacks->uCount].uVal = + PIECE_VALUE(xPiece); + pAttacks->uCount++; + ASSERT(pAttacks->uCount > 0); +#ifdef SEE_HEAPS + _BubbleUp(pAttacks, pAttacks->uCount - 1); +#else + _SortList(pAttacks); +#endif + } + else + { + pDefends->data[pDefends->uCount].pPiece = xPiece; + pDefends->data[pDefends->uCount].cLoc = cIndex; + pDefends->data[pDefends->uCount].uVal = + PIECE_VALUE(xPiece); + pDefends->uCount++; + ASSERT(pDefends->uCount > 0); +#ifdef SEE_HEAPS + _BubbleUp(pDefends, pDefends->uCount - 1); +#else + _SortList(pDefends); +#endif + } + } + return; + } + } +} + + +SCORE +SEE(IN POSITION *pos, + IN MOVE mv) +/** + +Routine description: + + Given a board and a move on the board, estimate the value of the + move by considering the friend/enemy pieces that attack the move's + destination square. + +Parameters: + + POSITION *pos, + MOVE mv + +Return value: + + SCORE : the estimate of the move's score + +**/ +{ + SEE_LIST rgPieces[2]; + PIECE pPiece; + ULONG uInPeril; + SCORE rgiList[32]; + ULONG uListIndex; + ULONG uWhoseTurn = GET_COLOR(mv.pMoved); + ULONG uOrig = uWhoseTurn; + int iSign = 1; + ULONG uPromValue; + ULONG uVal; + COOR cFrom = mv.cFrom; + static FLAG _Table[2][3] = { + // ab + { FALSE, FALSE, TRUE }, // uVal==0 + { TRUE, FALSE, FALSE }, // uVal==1 + }; + +#ifdef DEBUG + ASSERT(mv.uMove != 0); + memset(rgiList, 0xFF, sizeof(rgiList)); + memset(rgPieces, 0xFF, sizeof(rgPieces)); +#endif + + // + // Create a sorted list of pieces attacking and defending the + // square. + // + GetAttacks(&(rgPieces[uWhoseTurn]), pos, mv.cTo, uWhoseTurn); + GetAttacks(&(rgPieces[FLIP(uWhoseTurn)]), pos, mv.cTo, FLIP(uWhoseTurn)); +#ifdef SEE_HEAPS + _BuildHeap(&(rgPieces[FLIP(uWhoseTurn)])); + _BuildHeap(&(rgPieces[uWhoseTurn])); +#else + _SortList(&(rgPieces[FLIP(uWhoseTurn)])); + _SortList(&(rgPieces[uWhoseTurn])); +#endif + + // + // Play the first move -- TODO: the first move may be illegal... + // fix this? + // + rgiList[0] = (PIECE_VALUE(mv.pCaptured) + + PIECE_VALUE(mv.pPromoted)); + uInPeril = (PIECE_VALUE(mv.pMoved) + + PIECE_VALUE(mv.pPromoted)); + uListIndex = 1; + + _ClearPieceByLocation(&(rgPieces[uWhoseTurn]), mv.cFrom); + _AddXRays(pos, + uWhoseTurn, + mv.cTo, + mv.cFrom, + &(rgPieces[uWhoseTurn]), + &(rgPieces[FLIP(uWhoseTurn)])); + + // + // Play moves 2..n + // + do + { + // + // Other side's turn now... + // + uWhoseTurn = FLIP(uWhoseTurn); + iSign = -iSign; + pPiece = _MinLegalPiece(pos, + uWhoseTurn, + &(rgPieces[uWhoseTurn]), + &(rgPieces[FLIP(uWhoseTurn)]), + &cFrom, + cFrom); + if (0 == pPiece) break; // no legal piece + // + // If this is a pawn capturing and it ends on the queening + // rank, set uPromValue appropriately. Bitwise operators are + // correct here, done for speed and branch removal; this loop + // is pretty heavily used. + // + uPromValue = IS_PAWN(pPiece) & (RANK1(mv.cTo) | RANK8(mv.cTo)); + uPromValue *= VALUE_QUEEN; + ASSERT((uPromValue == 0) || (uPromValue == VALUE_QUEEN)); + + ASSERT(uListIndex != 0); + rgiList[uListIndex] = rgiList[uListIndex - 1] + + iSign * (uInPeril + uPromValue); + uListIndex++; + ASSERT(uListIndex < ARRAY_LENGTH(rgiList)); + uInPeril = PIECE_VALUE(pPiece) + uPromValue; + + _AddXRays(pos, + GET_COLOR(mv.pMoved), + mv.cTo, + cFrom, + &(rgPieces[uOrig]), // These must be rgAttacks and + &(rgPieces[FLIP(uOrig)])); // rgDefends. Not based on tomove + } + while(1); + + // + // The swaplist is now complete but we still must consider that either + // side has the option of not taking (not continuing the exchange). + // + ASSERT(uListIndex >= 1); + uListIndex--; + + while (uListIndex > 0) + { + uVal = (uListIndex & 1); + iSign = ((rgiList[uListIndex] > rgiList[uListIndex - 1]) - + (rgiList[uListIndex] < rgiList[uListIndex - 1])) + 1; + ASSERT((iSign >= 0) && (iSign <= 2)); + if (TRUE == _Table[uVal][iSign]) + { + rgiList[uListIndex - 1] = rgiList[uListIndex]; + } + uListIndex--; + } + +#ifdef TEST_BROKEN + iSign = DebugSEE(pos, mv); + + if ((rgiList[0] != iSign) && + (iSign != INVALID_SCORE)) + { + DumpPosition(pos); + DumpMove(mv.uMove); + Trace("Real SEE says: %d\n" + "Test SEE says: %d\n", + rgiList[0], iSign); + UtilPanic(TESTCASE_FAILURE, + NULL, + "See mismatch", + rgiList[0], + iSign, + __FILE__, __LINE__); + } +#endif + return(rgiList[0]); +} -- cgit v1.3