/*----------------------------------------- -----------------------------
 | GENERATE.C							940422
 |
 | Contains all move generation procedures.
 +----------------------------------------------------------------------*/


#include "var.h"


static void     GeneratePawnMoves(BoardIndexType square, MoveType * list,
                                                  Unsigned1 * nrMoves);
static void     GenerateKnightMoves(BoardIndexType square, MoveType * list,
                                                    Unsigned1 * nrMoves);
static void     GenerateBishopMoves(BoardIndexType square, MoveType * list,
                                                    Unsigned1 * nrMoves);
static void     GenerateRookMoves(BoardIndexType square, MoveType * list,
                                                  Unsigned1 * nrMoves);
static void     GeneratePawnCaptureMoves(CheckPieceType * piece, MoveType * list,
                                                       Unsigned1 * nrMoves);
static void     GenerateKnightCaptureMoves(CheckPieceType * piece, MoveType * list,
                                                       Unsigned1 * nrMoves);
static void     GenerateBishopCaptureMoves(CheckPieceType * piece, MoveType * list,
                                                       Unsigned1 * nrMoves);
static void     GenerateRookCaptureMoves(CheckPieceType * piece, MoveType * list,
                                                       Unsigned1 * nrMoves);
static void     GenerateToMoves(BoardIndexType to, MoveType * list,
                                                Unsigned1 * nrMoves);
static void     GeneratePawnToMoves(BoardIndexType to, MoveType * list,
                                                    Unsigned1 * nrMoves);
static void     GenerateKnightToMoves(BoardIndexType to, MoveType * list,
                                                      Unsigned1 * nrMoves);
static void     GenerateBishopToMoves(BoardIndexType to, MoveType * list,
                                                      Unsigned1 * nrMoves);
static void     GenerateRookToMoves(BoardIndexType to, MoveType * list,
                                                    Unsigned1 * nrMoves);
static void     SiftUp(MoveType * moveList, Unsigned1 root, Unsigned1 leaf);


/*----------------------------------------------------------------------
 | GenerateMoves						940422
 |
 | Generates all legal moves.
 +----------------------------------------------------------------------*/
void            GenerateMoves(MoveType ** moveList, Unsigned1 * nrMoves)
{
    PieceType      *pieceTable;
    Unsigned1       nr;
    SquareType      piece;
    Signed2         i;
    MoveType        list[MaxMoves];

    pieceTable = pieces[toMove];
    nr = nrPieces[toMove];

    *nrMoves = 0;
    SearchForPinsAndCheck();
    switch (nrCheck) {
    case 0:
        for (i = 0; i < nr; i++) {
            piece = pieceTable[i].type;
            if (IsPawn(piece)) {
                GeneratePawnMoves(pieceTable[i].square, list, nrMoves);
            } else if (IsKnight(piece) && !pinned[pieceTable[i].square]) {
                GenerateKnightMoves(pieceTable[i].square, list, nrMoves);
            } else if (IsKing(piece)) {
                GenerateKingMoves(pieceTable[i].square, list, nrMoves);
            } else {
                if (MovesDiagonal(piece)) {
                    GenerateBishopMoves(pieceTable[i].square, list, nrMoves);
                }
                if (MovesStraight(piece)) {
                    GenerateRookMoves(pieceTable[i].square, list, nrMoves);
                }
            }
        }                       /* for i */
        break;
    case 1:
        /* Capture check-giving piece, NOT with king */
        GenerateCaptureMoves(&(checkingPiece[0]), list, nrMoves);
        /* Interpose piece */
        if (checkingPiece[0].dir &&
            kingSquare[toMove] + checkingPiece[0].dir !=
            checkingPiece[0].square) {
            GenerateInterposingMoves(&(checkingPiece[0]), list, nrMoves);
        }
    case 2:
        /* Move king away, including trying to capture (one of) the
         * check-giving piece(s) */
        GenerateKingMoves(kingSquare[toMove], list, nrMoves);
        break;
    default:
        printf("ERROR: %d times in check\n", nrCheck);
        exit(0);
    }                           /* switch */
    if (*nrMoves) {
        AllocateMoveList(*moveList, *nrMoves);
        memcpy(*moveList, list, *nrMoves * sizeof(MoveType));
    }
/*  HeapSort( *moveList, *nrMoves );
   qsort( *moveList, *nrMoves, sizeof( MoveType ), CompareMoves ); */
    nrGenerates++;
    nrMovesGenerated += *nrMoves;
}                               /* GenerateMoves */


/*----------------------------------------------------------------------
 | GeneratePawnMoves						940420
 |
 | Generates all legal pawn moves.
 +----------------------------------------------------------------------*/
static void     GeneratePawnMoves(BoardIndexType from, MoveType * list,
                                                  Unsigned1 * nrMoves)
{
    BoardIndexType  to;
    SquareType      piece;
    Unsigned1       dir;
    PieceType       attackingPiece;

    /* non-capture moves */
    if (!pinned[from] || pinned[from] == Up || pinned[from] == Down) {
        to = pawnMoveTable[toMove][from][0];
        if (IsEmpty(board[to])) {
            if (OnSeventhRank(toMove, from)) {
                PutMoveInTable(from, to, 0, Queen | toMove, Promotion, list,
                               *nrMoves);
                PutMoveInTable(from, to, 0, Knight | toMove, Promotion, list,
                               *nrMoves);
                PutMoveInTable(from, to, 0, Rook | toMove, Promotion, list,
                               *nrMoves);
                PutMoveInTable(from, to, 0, Bishop | toMove, Promotion, list,
                               *nrMoves);
            } else {
                PutMoveInTable(from, to, 0, 0, Normal, list, *nrMoves);
            }
            to = pawnMoveTable[toMove][from][1];
            if (IsEmpty(board[to])) {
                PutMoveInTable(from, to, 0, 0, Double, list, *nrMoves);
            }
        }                       /* if empty square */
    }                           /* if not pinned */
    /* capture moves */
    for (dir = 0; dir < 2; dir++) {
        if (!pinned[from] || pinned[from] == pawnCaptureDir[toMove][dir] ||
            pinned[from] == -pawnCaptureDir[toMove][dir]) {
            to = pawnCaptureTable[toMove][from][dir];
            if (to == epSquare[nrGamePlies]) {
                if (Rank(kingSquare[toMove]) != (toMove == White ? 5 : 4)) {
                    PutMoveInTable(from, to, Pawn | !toMove, 0,
                                   EnPassant | Capture, list, *nrMoves);
                } else {
                    /* remove pawns temporarily */
                    board[from] = Empty;
                    board[to + (toMove == White ? Down : Up)] = Empty;
                    if (!FindFirstPieceInDir((Unsigned1) MaxRookMoves,
                       rookTable[kingSquare[toMove]][2], &attackingPiece) ||
                        (attackingPiece.type != (Rook | !toMove) &&
                         attackingPiece.type != (Queen | !toMove))) {
                        if (!FindFirstPieceInDir((Unsigned1) MaxRookMoves,
                        rookTable[kingSquare[toMove]][3], &attackingPiece) ||
                            (attackingPiece.type != (Rook | !toMove) &&
                             attackingPiece.type != (Queen | !toMove))) {
                            PutMoveInTable(from, to, Pawn | !toMove, 0,
                                       EnPassant | Capture, list, *nrMoves);
                        }
                    }
                    /* Put pawns back */
                    board[from] = Pawn | toMove;
                    board[to + (toMove == White ? Down : Up)] = Pawn | !toMove;
                }
            } else {
                piece = board[to];
                if (piece && !IsEdge(piece) && !IsColor(piece, toMove)) {
                    if (OnSeventhRank(toMove, from)) {
                        PutMoveInTable(from, to, piece, Queen | toMove,
                                       Promotion | Capture, list, *nrMoves);
                        PutMoveInTable(from, to, piece, Knight | toMove,
                                       Promotion | Capture, list, *nrMoves);
                        PutMoveInTable(from, to, piece, Rook | toMove,
                                       Promotion | Capture, list, *nrMoves);
                        PutMoveInTable(from, to, piece, Bishop | toMove,
                                       Promotion | Capture, list, *nrMoves);
                    } else {
                        PutMoveInTable(from, to, piece, 0, Capture, list, *nrMoves);
                    }
                }               /* if enemy piece */
            }                   /* else */
        }                       /* if not pinned */
    }                           /* for dir */
}                               /* GeneratePawnMoves */


/*----------------------------------------------------------------------
 | GenerateKnightMoves						940422
 |
 | Generates all legal knight moves.
 +----------------------------------------------------------------------*/
static void     GenerateKnightMoves(BoardIndexType from, MoveType * list,
                                                    Unsigned1 * nrMoves)
{
    Signed2         i;
    BoardIndexType  to;
    SquareType      piece;

    for (i = 0; i < MaxKnightMoves; i++) {
        to = knightTable[from][i];
        if (!to) {
            break;
        }
        piece = board[to];
        if (IsEmpty(piece)) {
            PutMoveInTable(from, to, 0, 0, Normal, list, *nrMoves);
        } else if (!IsEdge(piece) && !IsColor(piece, toMove)) {
            PutMoveInTable(from, to, piece, 0, Capture, list, *nrMoves);
        }
    }
}                               /* GenerateKnightMoves */


/*----------------------------------------------------------------------
 | GenerateBishopMoves						940422
 |
 | Generates all legal bishop moves.
 +----------------------------------------------------------------------*/
static void     GenerateBishopMoves(BoardIndexType from, MoveType * list,
                                                    Unsigned1 * nrMoves)
{
    Signed2         i,
                    j;
    BoardIndexType  to;
    SquareType      piece;

    for (i = 0; i < 4; i++) {
        if (!pinned[from] || pinned[from] == bishopDir[i] ||
            pinned[from] == -bishopDir[i]) {
            for (j = 0; j < MaxBishopMoves; j++) {
                to = bishopTable[from][i][j];
                if (!to) {
                    break;
                }
                piece = board[to];
                if (IsEmpty(piece)) {
                    PutMoveInTable(from, to, 0, 0, Normal, list, *nrMoves);
                } else if (!IsEdge(piece) && !IsColor(piece, toMove)) {
                    PutMoveInTable(from, to, piece, 0, Capture, list, *nrMoves);
                    break;
                } else {
                    break;
                }
            }                   /* for j */
        }                       /* if not pinned */
    }                           /* for i */
}                               /* GenerateBishopMoves */


/*----------------------------------------------------------------------
 | GenerateRookMoves						940422
 |
 | Generates all legal rook moves.
 +----------------------------------------------------------------------*/
static void     GenerateRookMoves(BoardIndexType from, MoveType * list,
                                                  Unsigned1 * nrMoves)
{
    Signed2         i,
                    j;
    BoardIndexType  to;
    SquareType      piece;

    for (i = 0; i < 4; i++) {
        if (!pinned[from] || pinned[from] == rookDir[i] ||
            pinned[from] == -rookDir[i]) {
            for (j = 0; j < MaxRookMoves; j++) {
                to = rookTable[from][i][j];
                if (!to) {
                    break;
                }
                piece = board[to];
                if (IsEmpty(piece)) {
                    PutMoveInTable(from, to, 0, 0, Normal, list, *nrMoves);
                } else if (!IsEdge(piece) && !IsColor(piece, toMove)) {
                    PutMoveInTable(from, to, piece, 0, Capture, list, *nrMoves);
                    break;
                } else {
                    break;
                }
            }                   /* for j */
        }                       /* if not pinned */
    }                           /* for i */
}                               /* GenerateRookMoves */


/*----------------------------------------------------------------------
 | GenerateKingMoves						940422
 |
 | Generates all legal king moves.
 +----------------------------------------------------------------------*/
void            GenerateKingMoves(BoardIndexType from, MoveType * list,
                                                  Unsigned1 * nrMoves)
{
    Signed2         i;
    BoardIndexType  to;
    BoardIndexType  square1,
                    square2,
                    square3,
                    square4,
                    square5,
                    square6;
    SquareType      piece;

    /* Remove king temporarily in view of Attacked() */
    board[kingSquare[toMove]] = Empty;
    for (i = 0; i < 4; i++) {
        to = rookTable[from][i][0];
        if (!to) {
            continue;
        }
        piece = board[to];
        if (IsEmpty(piece)) {
            if (!IsCheckingDir(rookDir[i]) &&
                !IsCheckingDir(-rookDir[i]) &&
                !Attacked(to, (Unsigned1) ! toMove)) {
                PutMoveInTable(from, to, 0, 0, Normal, list, *nrMoves);
            }
        } else if (!IsEdge(piece) && !IsColor(piece, toMove)) {
            if (!IsCheckingDir(-rookDir[i]) &&
                !Attacked(to, (Unsigned1) ! toMove)) {
                PutMoveInTable(from, to, piece, 0, Capture, list, *nrMoves);
            }
        }
    }
    for (i = 0; i < 4; i++) {
        to = bishopTable[from][i][0];
        if (!to) {
            continue;
        }
        piece = board[to];
        if (IsEmpty(piece)) {
            if (!IsCheckingDir(bishopDir[i]) &&
                !IsCheckingDir(-bishopDir[i]) &&
                !Attacked(to, (Unsigned1) ! toMove)) {
                PutMoveInTable(from, to, 0, 0, Normal, list, *nrMoves);
            }
        } else if (!IsEdge(piece) && !IsColor(piece, toMove)) {
            if (!IsCheckingDir(-bishopDir[i]) &&
                !Attacked(to, (Unsigned1) ! toMove)) {
                PutMoveInTable(from, to, piece, 0, Capture, list, *nrMoves);
            }
        }
    }
    /* Castling */
    if (!nrCheck) {
        if (IsWhite(toMove)) {
            square1 = E1;
            square2 = F1;
            square3 = G1;
            square4 = D1;
            square5 = C1;
            square6 = B1;
        } else {
            square1 = E8;
            square2 = F8;
            square3 = G8;
            square4 = D8;
            square5 = C8;
            square6 = B8;
        }
        if (ShortCastlingPossible() &&
            IsEmpty(board[square2]) && IsEmpty(board[square3]) &&
            !Attacked(square2, (Unsigned1) ! toMove) &&
            !Attacked(square3, (Unsigned1) ! toMove)) {
            PutMoveInTable(square1, square3, 0, 0, ShortCastle, list, *nrMoves);
        }
        if (LongCastlingPossible() &&
            IsEmpty(board[square4]) && IsEmpty(board[square5]) &&
            IsEmpty(board[square6]) &&
            !Attacked(square4, (Unsigned1) ! toMove) &&
            !Attacked(square5, (Unsigned1) ! toMove) &&
            !Attacked(square6, (Unsigned1) ! toMove)) {
            PutMoveInTable(square1, square5, 0, 0, LongCastle, list, *nrMoves);
        }
    }                           /* if not in check */
    board[kingSquare[toMove]] = King | toMove;
}                               /* GenerateKingMoves */


/*----------------------------------------------------------------------
 | Attacked							940426
 |
 | Checks if square 'square' is attacked by color 'color'.
 +----------------------------------------------------------------------*/
Boolean
Attacked(BoardIndexType square, SquareType color)
{
    Signed2         i;
    PieceType       attackingPiece;
    SquareType      piece;
    BoardIndexType  to;

    /* Attacked by Rook, Bishop or Queen */
    for (i = 0; i < 4; i++) {
        if (FindFirstPieceInDir((Unsigned1) MaxBishopMoves,
                                bishopTable[square][i], &attackingPiece)) {
            if (IsColor(attackingPiece.type, color) &&
                MovesDiagonal(attackingPiece.type)) {
                return (True);
            }
        }
        if (FindFirstPieceInDir((Unsigned1) MaxRookMoves, rookTable[square][i],
                                &attackingPiece)) {
            if (IsColor(attackingPiece.type, color) &&
                MovesStraight(attackingPiece.type)) {
                return (True);
            }
        }
    }
    /* Attacked by Knight */
    for (i = 0; i < 8; i++) {
        to = knightTable[square][i];
        if (!to) {
            break;
        }
        piece = board[to];
        if (IsKnight(piece) && IsColor(piece, color)) {
            return (True);
        }
    }
    /* Attacked by King */
    for (i = 0; i < 4; i++) {
        to = bishopTable[square][i][0];
        if (to) {
            piece = board[to];
            if (IsKing(piece) && IsColor(piece, color)) {
                return (True);
            }
        }
        to = rookTable[square][i][0];
        if (to) {
            piece = board[to];
            if (IsKing(piece) && IsColor(piece, color)) {
                return (True);
            }
        }
    }
    /* Attacked by Pawn */
    to = pawnCaptureTable[!color][square][0];
    if (to) {
        piece = board[to];
        if (IsPawn(piece) && IsColor(piece, color)) {
            return (True);
        }
    }
    to = pawnCaptureTable[!color][square][1];
    if (to) {
        piece = board[to];
        if (IsPawn(piece) && IsColor(piece, color)) {
            return (True);
        }
    }
    return (False);
}                               /* Attacked */


/*----------------------------------------------------------------------
 | FindFirstPieceInDir						940426
 |
 | Searches squares in table 'table' to find a piece. If no piece is
 | found, False is returned.
 +----------------------------------------------------------------------*/
#ifdef Bcc
Boolean
FindFirstPieceInDir(Unsigned1 max, BoardIndexType huge * table,
                    PieceType * attackingPiece)
#else
Boolean
FindFirstPieceInDir(Unsigned1 max, BoardIndexType * table,
                    PieceType * attackingPiece)
#endif
{
    Signed2         i;
    BoardIndexType  to;
    SquareType      piece;

    for (i = 0; i < max; i++) {
        to = table[i];
        if (!to) {
            return (False);
        }
        piece = board[to];
        if (!IsEmpty(piece)) {
            break;
        }
    }                           /* for i */
    if (IsEdge(piece)) {
        return (False);
    } else {
        attackingPiece->type = piece;
        attackingPiece->square = to;
        return (True);
    }
}                               /* FindFirstPieceInDir */


/*----------------------------------------------------------------------
 | SearchForPinsAndCheck					940427
 |
 | Checks if side 'toMove' is inCheck and which pieces are pinned and
 | in what direction.
 +----------------------------------------------------------------------*/
void            SearchForPinsAndCheck(void)
{
    BoardIndexType  square,
                    sq,
                    to;
    Signed2         i;
    SquareType      piece;
    PieceType       attackingPiece;

    nrCheck = 0;
    checkingPiece[0].dir = checkingPiece[1].dir = 0;
    for (i = 0; i < nrPieces[toMove]; i++) {
        pinned[pieces[toMove][i].square] = 0;
    }
    square = kingSquare[toMove];
    /* Check or pinned by Rook, Bishop or Queen */
    for (i = 0; i < 4; i++) {
        if (FindFirstPieceInDir((Unsigned1) MaxBishopMoves,
                                bishopTable[square][i], &attackingPiece)) {
            if (IsColor(attackingPiece.type, !toMove)) {
                if (MovesDiagonal(attackingPiece.type)) {
                    checkingPiece[nrCheck].square = attackingPiece.square;
                    checkingPiece[nrCheck++].dir = bishopDir[i];
                }
            } else {
                sq = attackingPiece.square;
                if (FindFirstPieceInDir((Unsigned1) MaxBishopMoves,
                                     bishopTable[sq][i], &attackingPiece) &&
                    IsColor(attackingPiece.type, !toMove)) {
                    if (MovesDiagonal(attackingPiece.type)) {
                        pinned[sq] = bishopDir[i];
                    }
                }               /* pinned */
            }                   /* else */
        }                       /* if piece */
        if (FindFirstPieceInDir((Unsigned1) MaxRookMoves,
                                rookTable[square][i], &attackingPiece)) {
            if (IsColor(attackingPiece.type, !toMove)) {
                if (MovesStraight(attackingPiece.type)) {
                    checkingPiece[nrCheck].square = attackingPiece.square;
                    checkingPiece[nrCheck++].dir = rookDir[i];
                }
            } else {
                sq = attackingPiece.square;
                if (FindFirstPieceInDir((Unsigned1) MaxRookMoves,
                                        rookTable[sq][i], &attackingPiece) &&
                    IsColor(attackingPiece.type, !toMove)) {
                    if (MovesStraight(attackingPiece.type)) {
                        pinned[sq] = rookDir[i];
                    }
                }               /* pinned */
            }                   /* else */
        }                       /* if piece */
    }
    /* Check by Knight */
    for (i = 0; i < 8; i++) {
        to = knightTable[square][i];
        if (!to) {
            break;
        }
        piece = board[to];
        if (IsKnight(piece) && IsColor(piece, !toMove)) {
            checkingPiece[nrCheck].square = to;
            checkingPiece[nrCheck++].dir = 0;
        }
    }
    /* Check by Pawn */
    to = pawnCaptureTable[toMove][square][0];
    if (to) {
        piece = board[to];
        if (IsPawn(piece) && IsColor(piece, !toMove)) {
            checkingPiece[nrCheck].square = to;
            checkingPiece[nrCheck++].dir = 0;
        }
    }
    to = pawnCaptureTable[toMove][square][1];
    if (to) {
        piece = board[to];
        if (IsPawn(piece) && IsColor(piece, !toMove)) {
            checkingPiece[nrCheck].square = to;
            checkingPiece[nrCheck++].dir = 0;
        }
    }
}                               /* SearchForPinsAndCheck */


/*----------------------------------------------------------------------
 | GenerateCaptureMoves						940428
 |
 | Generate moves for color 'toMove', trying to disable check by
 | capturing the check-giving piece.
 | NOTE: no king capture moves are generated because they are generated
 | later in GenerateKingMoves().
 +----------------------------------------------------------------------*/
void            GenerateCaptureMoves(CheckPieceType * piece, MoveType * list,
                                                     Unsigned1 * nrMoves)
{
    GeneratePawnCaptureMoves(piece, list, nrMoves);
    GenerateKnightCaptureMoves(piece, list, nrMoves);
    GenerateBishopCaptureMoves(piece, list, nrMoves);
    GenerateRookCaptureMoves(piece, list, nrMoves);
}                               /* GenerateCaptureMoves */


/*----------------------------------------------------------------------
 | GeneratePawnCaptureMoves					940428
 |
 | Generate pawn moves for color 'toMove', trying to disable check by
 | capturing the check-giving piece.
 +----------------------------------------------------------------------*/
static void     GeneratePawnCaptureMoves(CheckPieceType * piece, MoveType * list,
                                                         Unsigned1 * nrMoves)
{
    Signed2         dir;
    BoardIndexType  from,
                    to;

    to = piece->square;
    /* Normal capture */
    for (dir = 0; dir < 2; dir++) {
        if (pawnCaptureDir[!toMove][dir] == -piece->dir) {
            continue;
        }
        from = pawnCaptureTable[!toMove][to][dir];
        if (from && board[from] == (Pawn | toMove) && (!pinned[from] ||
                             pinned[from] == pawnCaptureDir[!toMove][dir] ||
                           pinned[from] == -pawnCaptureDir[!toMove][dir])) {
            if (OnSeventhRank(toMove, from)) {
                PutMoveInTable(from, to, board[to], Queen | toMove,
                               Promotion | Capture, list, *nrMoves);
                PutMoveInTable(from, to, board[to], Knight | toMove,
                               Promotion | Capture, list, *nrMoves);
                PutMoveInTable(from, to, board[to], Rook | toMove,
                               Promotion | Capture, list, *nrMoves);
                PutMoveInTable(from, to, board[to], Bishop | toMove,
                               Promotion | Capture, list, *nrMoves);
            } else {
                PutMoveInTable(from, to, board[to], 0, Capture, list,
                               *nrMoves);
            }
        }                       /* if not pinned */
    }                           /* for dir */

    /* En passant */
    dir = toMove == White ? Up : Down;
    if (epSquare[nrGamePlies] == to + dir) {
        from = to + Right;
        if (from && board[from] == (Pawn | toMove) && (!pinned[from] ||
             pinned[from] == dir + Right || pinned[from] == -dir - Right)) {
            PutMoveInTable(from, to + dir, board[to], 0, EnPassant | Capture,
                           list, *nrMoves);
        }                       /* if not pinned */
        from = to + Left;
        if (from && board[from] == (Pawn | toMove) && (!pinned[from] ||
               pinned[from] == dir + Left || pinned[from] == -dir - Left)) {
            PutMoveInTable(from, to + dir, board[to], 0, EnPassant | Capture,
                           list, *nrMoves);
        }                       /* if not pinned */
    }                           /* if */
}                               /* GeneratePawnCaptureMoves */


/*----------------------------------------------------------------------
 | GenerateKnightCaptureMoves					940428
 |
 | Generate knight moves for color 'toMove', trying to disable check by
 | capturing the check-giving piece.
 +----------------------------------------------------------------------*/
static void     GenerateKnightCaptureMoves(CheckPieceType * piece, MoveType * list,
                                                        Unsigned1 * nrMoves)
{
    Signed2         i;
    BoardIndexType  from,
                    to;

    to = piece->square;
    for (i = 0; i < MaxKnightMoves; i++) {
        if (knightDir[i] == -piece->dir) {
            continue;
        }
        from = knightTable[to][i];
        if (!from) {
            break;
        }
        if (board[from] == (Knight | toMove) && !pinned[from]) {
            PutMoveInTable(from, to, board[to], 0, Capture, list, *nrMoves);
        }
    }
}                               /* GenerateKnightCaptureMoves */


/*----------------------------------------------------------------------
 | GenerateBishopCaptureMoves					940428
 |
 | Generate bishop moves for color 'toMove', trying to disable check by
 | capturing the check-giving piece.
 +----------------------------------------------------------------------*/
static void     GenerateBishopCaptureMoves(CheckPieceType * piece, MoveType * list,
                                                        Unsigned1 * nrMoves)
{
    Signed2         i,
                    j;
    BoardIndexType  from,
                    to;

    to = piece->square;
    for (i = 0; i < 4; i++) {
        if (bishopDir[i] == -piece->dir) {
            continue;
        }
        for (j = 0; j < MaxBishopMoves; j++) {
            from = bishopTable[to][i][j];
            if (!from) {
                break;
            }
            if (IsEmpty(board[from])) {
                continue;
            }
            if ((board[from] == (Bishop | toMove) || board[from] == (Queen | toMove)) &&
                (!pinned[from] || pinned[from] == bishopDir[i] ||
                 pinned[from] == -bishopDir[i])) {
                PutMoveInTable(from, to, board[to], 0, Capture, list, *nrMoves);
                break;
            } else {
                break;
            }
        }                       /* for j */
    }                           /* for i */
}                               /* GenerateBishopCaptureMoves */


/*----------------------------------------------------------------------
 | GenerateRookCaptureMoves					940428
 |
 | Generate rook moves for color 'toMove', trying to disable check by
 | capturing the check-giving piece.
 +----------------------------------------------------------------------*/
static void     GenerateRookCaptureMoves(CheckPieceType * piece, MoveType * list,
                                                         Unsigned1 * nrMoves)
{
    Signed2         i,
                    j;
    BoardIndexType  from,
                    to;

    to = piece->square;
    for (i = 0; i < 4; i++) {
        if (rookDir[i] == -piece->dir) {
            continue;
        }
        for (j = 0; j < MaxRookMoves; j++) {
            from = rookTable[to][i][j];
            if (!from) {
                break;
            }
            if (IsEmpty(board[from])) {
                continue;
            }
            if ((board[from] == (Rook | toMove) || board[from] == (Queen | toMove)) &&
                (!pinned[from] || pinned[from] == rookDir[i] ||
                 pinned[from] == -rookDir[i])) {
                PutMoveInTable(from, to, board[to], 0, Capture, list, *nrMoves);
                break;
            } else {
                break;
            }
        }                       /* for j */
    }                           /* for i */
}                               /* GenerateRookCaptureMoves */


/*----------------------------------------------------------------------
 | GenerateInterposingMoves					940428
 |
 | Generate moves for color 'toMove' to disable check by interposing
 | a piece.
 +----------------------------------------------------------------------*/
void            GenerateInterposingMoves(CheckPieceType * piece, MoveType * list,
                                                         Unsigned1 * nrMoves)
{
    BoardIndexType  to;
    DirectionType   dir;

    dir = piece->dir;
    for (to = kingSquare[toMove] + dir; to != piece->square; to += dir) {
        GenerateToMoves(to, list, nrMoves);
    }                           /* for square */
}                               /* GenerateInterposingMoves */


/*----------------------------------------------------------------------
 | GenerateToMoves						940428
 |
 | Generates moves for color 'toMove' to empty square 'to'.
 | NOTE: no king moves are generated.
 +----------------------------------------------------------------------*/
static void     GenerateToMoves(BoardIndexType to, MoveType * list,
                                                Unsigned1 * nrMoves)
{
    GeneratePawnToMoves(to, list, nrMoves);
    GenerateKnightToMoves(to, list, nrMoves);
    GenerateBishopToMoves(to, list, nrMoves);
    GenerateRookToMoves(to, list, nrMoves);
}                               /* GenerateToMoves */


/*----------------------------------------------------------------------
 | GeneratePawnToMoves						940428
 |
 | Generates pawn moves for color 'toMove' to empty square 'to'.
 +----------------------------------------------------------------------*/
static void     GeneratePawnToMoves(BoardIndexType to, MoveType * list,
                                                    Unsigned1 * nrMoves)
{
    BoardIndexType  from;
    Unsigned1       type;

    from = pawnMoveTable[!toMove][to][0];
    /* Move from second rank? */
    if (IsEmpty(board[from]) &&
        Rank(from) == (IsWhite(toMove) ? 3 : 6)) {
        from = pawnMoveTable[!toMove][from][0];
        type = Double;
    } else {
        type = Normal;
    }
    if (board[from] == (Pawn | toMove) && (!pinned[from] ||
                              pinned[from] == Up || pinned[from] == Down)) {
        if (OnSeventhRank(toMove, from)) {
            PutMoveInTable(from, to, 0, Queen | toMove, Promotion, list,
                           *nrMoves);
            PutMoveInTable(from, to, 0, Knight | toMove, Promotion, list,
                           *nrMoves);
            PutMoveInTable(from, to, 0, Rook | toMove, Promotion, list,
                           *nrMoves);
            PutMoveInTable(from, to, 0, Bishop | toMove, Promotion, list,
                           *nrMoves);
        } else {
            PutMoveInTable(from, to, 0, 0, type, list, *nrMoves);
        }
    }                           /* if not pinned */
}                               /* GeneratePawnToMoves */


/*----------------------------------------------------------------------
 | GenerateKnightToMoves						940428
 |
 | Generates knight moves for color 'toMove' to empty square 'to'.
 +----------------------------------------------------------------------*/
static void     GenerateKnightToMoves(BoardIndexType to, MoveType * list,
                                                      Unsigned1 * nrMoves)
{
    Signed2         i;
    BoardIndexType  from;

    for (i = 0; i < MaxKnightMoves; i++) {
        from = knightTable[to][i];
        if (!from) {
            break;
        }
        if (board[from] == (Knight | toMove) && !pinned[from]) {
            PutMoveInTable(from, to, 0, 0, Normal, list, *nrMoves);
        }
    }
}                               /* GenerateKnightToMoves */


/*----------------------------------------------------------------------
 | GenerateBishopToMoves					940428
 |
 | Generates bishop moves for color 'toMove' to empty square 'to'.
 +----------------------------------------------------------------------*/
static void     GenerateBishopToMoves(BoardIndexType to, MoveType * list,
                                                      Unsigned1 * nrMoves)
{
    Signed2         i,
                    j;
    BoardIndexType  from;

    for (i = 0; i < 4; i++) {
        for (j = 0; j < MaxBishopMoves; j++) {
            from = bishopTable[to][i][j];
            if (!from) {
                break;
            }
            if (IsEmpty(board[from])) {
                continue;
            }
            if ((board[from] == (Bishop | toMove) || board[from] == (Queen | toMove)) &&
                (!pinned[from] || pinned[from] == bishopDir[i] ||
                 pinned[from] == -bishopDir[i])) {
                PutMoveInTable(from, to, 0, 0, Normal, list, *nrMoves);
                break;
            } else {
                break;
            }
        }                       /* for j */
    }                           /* for i */
}                               /* GenerateBishopToMoves */


/*----------------------------------------------------------------------
 | GenerateRookToMoves						940428
 |
 | Generates rook moves for color 'toMove' to empty square 'to'.
 +----------------------------------------------------------------------*/
static void     GenerateRookToMoves(BoardIndexType to, MoveType * list,
                                                    Unsigned1 * nrMoves)
{
    Signed2         i,
                    j;
    BoardIndexType  from;

    for (i = 0; i < 4; i++) {
        for (j = 0; j < MaxRookMoves; j++) {
            from = rookTable[to][i][j];
            if (!from) {
                break;
            }
            if (IsEmpty(board[from])) {
                continue;
            }
            if ((board[from] == (Rook | toMove) || board[from] == (Queen | toMove)) &&
                (!pinned[from] || pinned[from] == rookDir[i] ||
                 pinned[from] == -rookDir[i])) {
                PutMoveInTable(from, to, 0, 0, Normal, list, *nrMoves);
                break;
            } else {
                break;
            }
        }                       /* for j */
    }                           /* for i */
}                               /* GenerateRookToMoves */


Signed2
CompareMoves(MoveType * move1, MoveType * move2)
{
/*
   Signed2      diff1, diff2;
   Signed2      *eval1Table, *eval2Table;
 */
    if (move1->to == lastMovedPieceSquare &&
        move2->to == lastMovedPieceSquare) {
        goto sameCapture;
    }
    if (move1->to == lastMovedPieceSquare) {
        return (-1);
    }
    if (move2->to == lastMovedPieceSquare) {
        return (1);
    }
    /* Promotion moves */
    if (move1->promotionPiece > move2->promotionPiece) {
        return (-1);
    }
    if (move1->promotionPiece < move2->promotionPiece) {
        return (1);
    }
    /* Capture moves */
    if (move1->capturedPiece > move2->capturedPiece) {
        return (-1);
    }
    if (move1->capturedPiece < move2->capturedPiece) {
        return (1);
    }
/*
   if (pieceValue[ move1->capturedPiece ]-pieceValue[ board[ move1->from ] ]>
   pieceValue[ move2->capturedPiece ]-pieceValue[ board[ move2->from ] ]) {
   return( -1 );
   }
   if (pieceValue[ move1->capturedPiece ]-pieceValue[ board[ move1->from ] ]<
   pieceValue[ move2->capturedPiece ]-pieceValue[ board[ move2->from ] ]) {
   return( 1 );
   }
 */
sameCapture:
    if (board[move1->from] < board[move2->from]) {
        return (-1);
    }
    if (board[move1->from] > board[move2->from]) {
        return (1);
    }
    /* History heuristic */
    if (historyTable[toMove][move1->from][move1->to] >
        historyTable[toMove][move2->from][move2->to]) {
        return (-1);
    }
    if (historyTable[toMove][move1->from][move1->to] <
        historyTable[toMove][move2->from][move2->to]) {
        return (1);
    }
/*
   GetEvalTable( eval1Table, toMove, board[ move1->from ] );
   GetEvalTable( eval2Table, toMove, board[ move2->from ] );
   diff1 = eval1Table[ move1->to ] - eval1Table[ move1->from ];
   diff2 = eval2Table[ move2->to ] - eval2Table[ move2->from ];
   if (diff1 > diff2) {
   return( -1 );
   }
   if (diff1 < diff2) {
   return( 1 );
   }
 */
    return (0);
}                               /* CompareMoves */


void            HeapSort(MoveType * moveList, Unsigned1 nrMoves)
{
    Unsigned1       i;
    MoveType        temp;

    /* Construct heap */
    for (i = nrMoves / 2 - 1; i > 0; i--) {
        SiftUp(moveList, (Unsigned1) i, (Unsigned1) (nrMoves - 1));
    }
    /* Iterate */
    for (i = nrMoves - 1; i > 0; i--) {
        SiftUp(moveList, (Unsigned1) 0, (Unsigned1) i);
        temp = moveList[0];
        moveList[0] = moveList[i];
        moveList[i] = temp;
    }
}                               /* HeapSort */


static void     SiftUp(MoveType * moveList, Unsigned1 root, Unsigned1 leaf)
{
    Unsigned1       i;
    MoveType        temp;

    for (temp = moveList[root];;) {
        i = 2 * root + 1;       /* Left child */
        if (i <= leaf) {
            if (i < leaf) {
                if (CompareMoves(&(moveList[i + 1]), &(moveList[i])) == 1) {
                    i++;        /* Right child */
                }
            }
            if (CompareMoves(&(moveList[i]), &temp) == 1) {
                moveList[root] = moveList[i];
                root = i;
            } else {
                break;
            }
        } else {
            break;
        }
    }
    moveList[root] = temp;
}                               /* SiftUp */


void            SiftDown(MoveType * moveList, Unsigned1 root, Unsigned1 leaf)
{
    Unsigned1       i;
    MoveType        temp;

    for (temp = moveList[root];;) {
        i = 2 * root + 1;       /* Left child */
        if (i <= leaf) {
            if (i < leaf) {
                if (CompareMoves(&(moveList[i + 1]), &(moveList[i])) == -1) {
                    i++;        /* Right child */
                }
            }
            if (CompareMoves(&(moveList[i]), &temp) == -1) {
                moveList[root] = moveList[i];
                root = i;
            } else {
                break;
            }
        } else {
            break;
        }
    }
    moveList[root] = temp;
}                               /* SiftDown */
