search.cpp

将UCOS与UCGUI整合到一起,并在BORLAND C++上运行通过的源程序.

            memmove(&P->S->line[0], P->bestline, sizeof(LINETYPE));
            /* P->S->line = *bestline; */
    }
    /*  Principvar indicates principal variation search  */
    /*  Zerowindow indicates zero - width alpha - beta window  */
    P->S->next.principvar = 0;
    P->S->zerowindow = 0;
    if (P->inf->principvar)
        if (P->S->movgentype == mane)
            P->S->next.principvar = (P->bestline[Depth+1].movpiece != empty);
        else
            P->S->zerowindow = (P->S->maxval >= P->alpha);
REPEATSEARCH:
    if (update(P)) return 0;
    if (Level == matesearch)  /*  stop evt. search  */
        if ((P->S->nextply <= 0) && !checktab[Depth]) goto NOTSEARCH;
    if (drawgame(P->S)) goto NOTSEARCH;
    if (Depth >= MAXPLY)
        goto NOTSEARCH;
    /*  Analyse nextply using a recursive call to search  */
    oldplayer = Player;
    Player = Opponent;
    Opponent = oldplayer;
    Depth++;
    if (P->S->zerowindow)
        P->S->next.evaluation = -search(-P->alpha - 1, -P->alpha, P->S->nextply,
                &P->S->next, &P->S->line[0]);
    else
        P->S->next.evaluation = -search(-P->beta, -P->alpha, P->S->nextply,
                &P->S->next, &P->S->line[0]);
    Depth--;
    oldplayer = Opponent;
    Opponent = Player;
    Player = oldplayer;
NOTSEARCH:
    Perform(&MovTab[Depth], 1);  /*  take back move  */
    if (SkipSearch)
        return 1;
    lastanalysis = Analysis;  /*  scan messages and test SkipSearch  */
    MessageScan();
    if (!SkipSearch)
        if (Analysis && !SingleStep && ((!Depth) || !lastanalysis))
        {
            StopTime(&ChessClock);
            if (MainEvalu > alphawindow)
                SkipSearch = ChessClock.totaltime >= (WantedTime * 1.5);
        }
    if (Analysis && (MaxDepth <= 1))
        SkipSearch = 0;
    P->S->maxval = max(P->S->maxval, P->S->next.evaluation);  /*  Update Maxval  */
    IF_EQMOVE(P->bestline[Depth], MovTab[Depth])  /*  Update evt. bestline  */
        updatebestline(P);
    if (P->alpha < P->S->maxval)      /*  update alpha and test cutoff */
    {
        updatebestline(P);
        if (P->S->maxval >= P->beta)
            return 1;
        /*  Adjust maxval (tolerance search)  */
        if (P->ply >= 2  && P->inf->principvar && !P->S->zerowindow)
            P->S->maxval = min(P->S->maxval + TOLERANCE, P->beta - 1);
        P->alpha = P->S->maxval;
        if (P->S->zerowindow && ! SkipSearch)
        {
            /*  repeat search with full window  */
            P->S->zerowindow = 0;
            goto REPEATSEARCH;
        }
    }
    return SkipSearch;
}


/*
 *  generate  pawn promotions
 */

static short pawnpromotiongen(PARAMTYPE *P)
{
    PIECETYPE promote;

    MovTab[Depth].spe = 1;
    for (promote = queen; promote <= knight; ((int)promote)++)
    {
        MovTab[Depth].movpiece = promote;
        if (loopbody(P)) return 1;
    }
    MovTab[Depth].spe = 0;
    return 0;
}


/*
 *  Generate captures of the piece on Newsq
 */

static short capmovgen(SQUARETYPE newsq, PARAMTYPE *P)
{
    EDGESQUARETYPE nxtsq, sq;
    INDEXTYPE i;

    MovTab[Depth].content = Board[newsq].piece;
    MovTab[Depth].spe = 0;
    MovTab[Depth].new1 = newsq;
    MovTab[Depth].movpiece = pawn;  /*  pawn captures  */
    nxtsq = MovTab[Depth].new1 - PawnDir[Player];
    for (sq = nxtsq - 1; sq <= nxtsq + 1; sq++)
        if (sq != nxtsq)
            if (!(sq & 0x88))
                if (Board[sq].piece == pawn && Board[sq].color == Player)
                {
                    MovTab[Depth].old = sq;
                    if (MovTab[Depth].new1 < 8 || MovTab[Depth].new1
                            >= 0x70)
                    {
                        if (pawnpromotiongen(P))
                            return 1;
                    }
                    else if (loopbody(P))
                        return 1;
                }
    for (i = OfficerNo[Player]; i >= 0; i--)  /*  other captures  */
        if (PieceTab[Player][i].ipiece != empty &&
                PieceTab[Player][i].ipiece != pawn)
            if (PieceAttacks(PieceTab[Player][i].ipiece, Player,
                    PieceTab[Player][i].isquare, newsq))
            {
                MovTab[Depth].old = PieceTab[Player][i].isquare;
                MovTab[Depth].movpiece = PieceTab[Player][i].ipiece;
                if (loopbody(P)) return 1;
            }
    return 0;
}
              

/*
 *  Generates non captures for the piece on oldsq
 */

static short noncapmovgen(SQUARETYPE oldsq, PARAMTYPE *P)
{
    DIRTYPE first, last, dir;
    int direction;
    EDGESQUARETYPE newsq;

    MovTab[Depth].spe = 0;
    MovTab[Depth].old = oldsq;
    MovTab[Depth].movpiece = Board[oldsq].piece;
    MovTab[Depth].content = empty;
    switch (MovTab[Depth].movpiece)
    {
        case king :
            for (dir = 7; dir >= 0; dir--)
            {
                newsq = MovTab[Depth].old + DirTab[dir];
                if (!(newsq & 0x88))
                    if (Board[newsq].piece == empty)
                    {
                        MovTab[Depth].new1 = newsq;
                        if (loopbody(P))
                             return 1;
                    }
            }
            break;
        case knight :
            for (dir = 7; dir >= 0; dir--)
            {
                newsq = MovTab[Depth].old + KnightDir[dir];
                if (!(newsq & 0x88))
                    if (Board[newsq].piece == empty)
                    {
                        MovTab[Depth].new1 = newsq;
                        if (loopbody(P))
                            return 1;
                    }
            }
            break;
        case queen :
        case rook  :
        case bishop :
            first = 7;
            last = 0;
            if (MovTab[Depth].movpiece == rook) first = 3;
            else if (MovTab[Depth].movpiece == bishop) last = 4;
            for (dir = first; dir >= last; dir--)
            {
                direction = DirTab[dir];
                newsq = MovTab[Depth].old + direction;
                while (!(newsq & 0x88))
                {
                    if (Board[newsq].piece != empty) goto TEN;
                    MovTab[Depth].new1 = newsq;
                    if (loopbody(P))
                        return 1;
                    newsq = MovTab[Depth].new1 + direction;
                }
TEN:
                continue;
            }
            break;
        case pawn :
            /*  One square forward  */
            MovTab[Depth].new1 = MovTab[Depth].old + PawnDir[Player];
            if (Board[MovTab[Depth].new1].piece == empty)
                if (MovTab[Depth].new1 < 8 || MovTab[Depth].new1 >= 0x70)
                {
                    if (pawnpromotiongen(P)) return 1;
                }
                else
                {
                    if (loopbody(P))
                        return 1;
                    if (MovTab[Depth].old < 0x18 || MovTab[Depth].old
                                >= 0x60)
                    {
                        /*  two squares forward  */
                        MovTab[Depth].new1 += (MovTab[Depth].new1
                                    - MovTab[Depth].old);
                        if (Board[MovTab[Depth].new1].piece == empty)
                            if (loopbody(P))
                                return 1;
                    }
               }
    } /*  switch  */
    return 0;
}


/*
 *  castling moves
 */

static short castlingmovgen(PARAMTYPE *P)
{
    CASTDIRTYPE castdir;

    MovTab[Depth].spe = 1;
    MovTab[Depth].movpiece = king;
    MovTab[Depth].content = empty;
    for (castdir = (CASTDIRTYPE)(lng-1); castdir <= shrt-1; ((int)castdir)++)
    {
        MovTab[Depth].new1 = CastMove[Player][castdir].castnew;
        MovTab[Depth].old = CastMove[Player][castdir].castold;
        if (KillMovGen(&MovTab[Depth]))
            if (loopbody(P))
                return 1;
    }
    return 0;
}


/*
 *  e.p. captures
 */

static short epcapmovgen(PARAMTYPE *P)
{
    EDGESQUARETYPE sq;

    if (MovTab[Depth - 1].movpiece == pawn)
        if (abs(MovTab[Depth - 1].new1 - MovTab[Depth - 1].old) >= 0x20)
        {
            MovTab[Depth].spe = 1;
            MovTab[Depth].movpiece = pawn;
            MovTab[Depth].content = empty;
            MovTab[Depth].new1 = (MovTab[Depth - 1].new1 +
                    MovTab[Depth - 1].old) / 2;
            for (sq = MovTab[Depth - 1].new1 - 1; sq <=
                    MovTab[Depth - 1].new1 + 1; sq++)
                if (sq != MovTab[Depth - 1].new1)
                    if (!(sq & 0x88))
                    {
                        MovTab[Depth].old = sq;
                        if (KillMovGen(&MovTab[Depth]))
                            if (loopbody(P))
                                return 1;
                    }
        }
    return 0;
}


/*
 *  Generate the next move to be analysed.
 *   Controls the order of the movegeneration.
 *      The moves are generated in the order:
 *      Main variation
 *      Captures of last moved piece
 *      Killing moves
 *      Other captures
 *      Pawnpromovtions
 *      Castling
 *      Normal moves
 *      E.p. captures
 */

static void searchmovgen(PARAMTYPE *P)
{
    INDEXTYPE index;
    char killno;

    /*  generate move from main variation  */
    if (P->bestline[Depth].movpiece != empty)
    {
        MovTab[Depth] = P->bestline[Depth];
        P->S->movgentype = mane;
        if (loopbody(P)) return;
    }
    if (MovTab[Depth - 1].movpiece != empty)
        if (MovTab[Depth - 1].movpiece != king)
        {
            P->S->movgentype = specialcap;
            if (capmovgen(MovTab[Depth - 1].new1, P)) return;
        }
    P->S->movgentype = kill;
    if (!P->S->capturesearch)
        for (killno = 0; killno <= 1; killno++)
        {
            MovTab[Depth] = killingmove[Depth][killno];
            if (MovTab[Depth - 1].movpiece != empty)
                if (KillMovGen(&MovTab[Depth]))
                    if (loopbody(P)) return;
        }
    P->S->movgentype = norml;
    for (index = 1; index <= PawnNo[Opponent]; index++)
        if (PieceTab[Opponent][index].ipiece != empty)
            if (MovTab[Depth-1].movpiece == empty ||
                    PieceTab[Opponent][index].isquare !=
                    MovTab[Depth-1].new1)
                if (capmovgen(PieceTab[Opponent][index].isquare, P))
                    return;
    if (P->S->capturesearch)
    {
        if (passedpawn[Depth-2] >= 0)
            if (Board[passedpawn[Depth-2]].piece == pawn &&
                    Board[passedpawn[Depth-2]].color == Player)
                if (noncapmovgen(passedpawn[Depth-2], P)) return;
    }
    if (!P->S->capturesearch)                /*  non-captures  */
    {
        if (castlingmovgen(P))
            return;      /*  castling  */
        for (index = PawnNo[Player]; index >= 0; index--)
            if (PieceTab[Player][index].ipiece != empty)
                if (noncapmovgen(PieceTab[Player][index].isquare, P)) return;
    }
    if (epcapmovgen(P))
        return;  /*  e.p. captures  */
}


/*
 *  Perform the search
 *  On entry :
 *    Player is next to move
 *    MovTab[Depth-1] contains last move
 *    alpha, beta contains the alpha - beta window
 *    ply contains the Depth of the search
 *    inf contains various information
 *
 *  On exit :
 *    Bestline contains the principal variation
 *    search contains the evaluation for Player
 */

static MAXTYPE search(MAXTYPE alpha, MAXTYPE beta, int ply, INFTYPE *inf,
    MOVETYPE *bestline)
{
    SEARCHTYPE S;
    PARAMTYPE P;
    /*  Perform capturesearch if ply <= 0 and !check  */
    S.capturesearch = ((ply <= 0) && !checktab[Depth-1]);
    if (S.capturesearch)  /*  initialize maxval  */
    {
        S.maxval = -inf->evaluation;
        if (alpha < S.maxval)
        {
            alpha = S.maxval;
            if (S.maxval >= beta) goto STOP;
        }
    }
    else
        S.maxval = -(LOSEVALUE - Depth*DEPTHFACTOR);
    P.alpha = alpha;
    P.beta = beta;
    P.ply = ply;
    P.inf = inf;
    P.bestline = bestline;
    P.S = &S;
    searchmovgen(&P);   /*  The search loop  */
    if (SkipSearch) goto STOP;
    if (S.maxval == -(LOSEVALUE - Depth * DEPTHFACTOR))   /*  Test stalemate  */
        if (!Attacks(Opponent, PieceTab[Player][0].isquare))
        {
            S.maxval = 0;
            goto STOP;
        }
    updatekill(&bestline[Depth]);
STOP:
    return S.maxval;
}


/*
 *  Begin the search
 */

static MAXTYPE callsearch(MAXTYPE alpha, MAXTYPE beta)
{
    MAXTYPE maxval;

    startinf.principvar = (MainLine[0].movpiece != empty);
    LegalMoves = 0;
    maxval = search(alpha, beta, MaxDepth, &startinf, &MainLine[0]);
    if (!LegalMoves)
        MainEvalu = maxval;
    return maxval;
}


/*
 *  Checks whether the search time is used
 */

inline short timeused(void)
{
    short tu = 0;

    if (Analysis && !SingleStep)
    {
        StopTime(&ChessClock);
        tu = (ChessClock.totaltime >= WantedTime);
    }
    return tu;
}


/*
 *  setup search
 */

void FindMove(int maxlevel)
{
    MAXTYPE maxval;
    double calcpvtime;
    InitTime(&ChessClock);
    StartTime(&ChessClock);
    InitNode(&Nodes);
    SkipSearch = 0;
    clearkillmove();
    CalcPVTable();
    StopTime(&ChessClock);
    calcpvtime = ChessClock.totaltime;
    startinf.value = startinf.evaluation = -RootValue;
    MaxDepth = 0;
    MainLine[0] = ZeroMove;
    MainEvalu = RootValue;
    alphawindow = MAXINT;
    ComputerThinking = TRUE;
    do
    {
        /*  update various variables  */
        if (MaxDepth <= 1) repeatevalu = MainEvalu;
        alphawindow = min(alphawindow, MainEvalu - 0x80);
        if (Level == matesearch)
        {
            alphawindow = 0x6000;
            if (MaxDepth > 0) MaxDepth++;
        }
        MaxDepth++;
        maxval = callsearch(alphawindow, 0x7f00);  /*  perform the search  */
        if (maxval <= alphawindow && !SkipSearch && Level != matesearch &&
                LegalMoves > 0)
        {
            /*  Repeat the search if the value falls below the
                    alpha-window  */
            MainEvalu = alphawindow;
            maxval = callsearch(-0x7F00, alphawindow - TOLERANCE * 2);
            LegalMoves = 2;
        }
    } while (!SkipSearch && !timeused() && (MaxDepth < maxlevel) &&
            (LegalMoves > 1) &&
            (abs(MainEvalu) < MATEVALUE - 24 * DEPTHFACTOR));
   ComputerThinking = FALSE;
   StopTime(&ChessClock);

   if (Analysis)
      PrintNodes(&Nodes, (ChessClock.totaltime - calcpvtime));
}