Subversion Repositories Games.Chess Giants

/*

    Texel - A UCI chess engine.

    Copyright (C) 2014  Peter Österlund, peterosterlund2@gmail.com

    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 3 of the License, or

    (at your option) 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, see <http://www.gnu.org/licenses/>.

*/

/*

 * tbprobe.cpp

 *

 *  Created on: Jun 2, 2014

 *      Author: petero

 */

#include "tbprobe.hpp"

#include "gtb/gtb-probe.h"

#include "syzygy/rtb-probe.hpp"

#include "bitBoard.hpp"

#include "position.hpp"

#include "moveGen.hpp"

#include "constants.hpp"

#include <unordered_map>

#include <cassert>

#include "util/timeUtil.hpp"

static std::string currentGtbPath;

static int currentGtbCacheMB;

static int currentGtbWdlFraction;

static std::string currentRtbPath;

static const char** gtbPaths = nullptr;

static int gtbMaxPieces = 0;

static std::unordered_map<int,int> maxDTM; // MatId -> Max DTM value in GTB TB

static std::unordered_map<int,int> maxDTZ; // MatId -> Max DTZ value in RTB TB

struct IIPairHash {

    size_t operator()(const std::pair<int,int>& p) const {

        return p.first * 0x714d3559 + p.second;

    }

};

// (MatId,maxPawnMoves) -> Max DTM in sub TBs

static std::unordered_map<std::pair<int,int>,int,IIPairHash> maxSubDTM;

void

TBProbe::initialize(const std::string& gtbPath, int cacheMB,

                    const std::string& rtbPath) {

    if (rtbPath != currentRtbPath) {

        Syzygy::init(rtbPath);

        currentRtbPath = rtbPath;

    }

    int wdlFraction = (Syzygy::TBLargest >= 5) ? 8 : 96;

    if ((gtbPath != currentGtbPath) ||

        (cacheMB != currentGtbCacheMB) ||

        (wdlFraction != currentGtbWdlFraction)) {

        gtbInitialize(gtbPath, cacheMB, wdlFraction);

        currentGtbPath = gtbPath;

        currentGtbCacheMB = cacheMB;

        currentGtbWdlFraction = wdlFraction;

    }

    static bool initialized = false;

    if (!initialized) {

        initWDLBounds();

        initialized = true;

    }

}

bool

TBProbe::tbEnabled() {

    return Syzygy::TBLargest > 0 || gtbMaxPieces > 0;

}

bool

TBProbe::tbProbe(Position& pos, int ply, int alpha, int beta,

                 TranspositionTable::TTEntry& ent) {

    const int nPieces = BitBoard::bitCount(pos.occupiedBB());

    bool mateSearch = SearchConst::isLoseScore(alpha) || SearchConst::isWinScore(beta);

    if (mateSearch || pos.getHalfMoveClock() > 0) {

        // Need DTM or DTZ probe

        int dtmScore;

        bool hasDtm = false;

        if (nPieces <= gtbMaxPieces && gtbProbeDTM(pos, ply, dtmScore)) {

            if (SearchConst::MATE0 - 1 - abs(dtmScore) - ply <= 100 - pos.getHalfMoveClock()) {

                ent.setScore(dtmScore, ply);

                ent.setType(TType::T_EXACT);

                return true;

            }

            hasDtm = true;

        }

        int dtzScore;

        if (nPieces <= Syzygy::TBLargest && rtbProbeDTZ(pos, ply, dtzScore)) {

            ent.setScore(dtzScore, ply);

            if (dtzScore > 0)

                ent.setType(TType::T_GE);

            else if (dtzScore < 0)

                ent.setType(TType::T_LE);

            else

                ent.setType(TType::T_EXACT);

            return true;

        }

        if (hasDtm) {

            ent.setScore(dtmScore, ply);

            ent.setType(TType::T_EXACT);

            return true;

        }

    }

    if (pos.getHalfMoveClock() == 0) {

        // Try WDL probe if DTM/DTZ not needed or not available

        int wdlScore;

        if ((nPieces <= Syzygy::TBLargest && rtbProbeWDL(pos, ply, wdlScore)) ||

                (nPieces <= gtbMaxPieces && gtbProbeWDL(pos, ply, wdlScore))) {

            ent.setScore(wdlScore, ply);

            if (wdlScore > 0)

                ent.setType(TType::T_GE);

            else if (wdlScore < 0)

                ent.setType(TType::T_LE);

            else

                ent.setType(TType::T_EXACT);

            return true;

        }

    }

    return false;

}

bool

TBProbe::getSearchMoves(Position& pos, const MoveList& legalMoves,

                        std::vector<Move>& movesToSearch) {

    const int mate0 = SearchConst::MATE0;

    const int ply = 0;

    TranspositionTable::TTEntry rootEnt;

    if (!tbProbe(pos, ply, -mate0, mate0, rootEnt) || rootEnt.getType() == TType::T_LE)

        return false;

    const int rootScore = rootEnt.getScore(ply);

    if (!SearchConst::isWinScore(rootScore))

        return false;

    // Root position is TB win

    bool hasProgress = false;

    UndoInfo ui;

    for (int mi = 0; mi < legalMoves.size; mi++) {

        const Move& m = legalMoves[mi];

        pos.makeMove(m, ui);

        TranspositionTable::TTEntry ent;

        ent.clear();

        bool progressMove = false;

        bool badMove = false;

        if (tbProbe(pos, ply+1, -mate0, mate0, ent)) {

            const int type = ent.getType();

            const int score = -ent.getScore(ply+1);

            if (score >= rootScore && (type == TType::T_EXACT || type == TType::T_LE))

                progressMove = true;

            if ((score < rootScore)) //  && (type == TType::T_EXACT || type == TType::T_GE))

                badMove = true;

        }

        if (progressMove)

            hasProgress = true;

        if (!badMove)

            movesToSearch.push_back(m);

        pos.unMakeMove(m, ui);

    }

    return !hasProgress && !movesToSearch.empty();

}

void

TBProbe::extendPV(const Position& rootPos, std::vector<Move>& pv) {

    Position pos(rootPos);

    UndoInfo ui;

    int ply = 0;

    int score;

    for (int i = 0; i < (int)pv.size(); i++) {

        const Move& m = pv[i];

        pos.makeMove(m, ui);

        if (TBProbe::gtbProbeDTM(pos, ply, score) && SearchConst::isWinScore(std::abs(score)) &&

            (SearchConst::MATE0 - 1 - abs(score) - ply <= 100 - pos.getHalfMoveClock())) {

            // TB win, replace rest of PV since it may be inaccurate

            pv.erase(pv.begin()+i+1, pv.end());

            break;

        }

    }

    if (!TBProbe::gtbProbeDTM(pos, ply, score) || !SearchConst::isWinScore(std::abs(score)))

        return; // No TB win

    if (SearchConst::MATE0 - 1 - abs(score) - ply > 100 - pos.getHalfMoveClock())

        return; // Mate too far away, perhaps 50-move draw

    if (!pos.isWhiteMove())

        score = -score;

    while (true) {

        MoveList moveList;

        MoveGen::pseudoLegalMoves(pos, moveList);

        MoveGen::removeIllegal(pos, moveList);

        bool extended = false;

        for (int mi = 0; mi < moveList.size; mi++) {

            const Move& m = moveList[mi];

            pos.makeMove(m, ui);

            int newScore;

            if (TBProbe::gtbProbeDTM(pos, ply+1, newScore)) {

                if (!pos.isWhiteMove())

                    newScore = -newScore;

                if (newScore == score) {

                    pv.push_back(m);

                    ply++;

                    extended = true;

                    break;

                }

            }

            pos.unMakeMove(m, ui);

        }

        if (!extended)

            break;

    }

}

template <typename ProbeFunc>

static void handleEP(Position& pos, int ply, int& score, bool& ret, ProbeFunc probeFunc) {

    const bool inCheck = MoveGen::inCheck(pos);

    MoveList moveList;

    if (inCheck) MoveGen::checkEvasions(pos, moveList);

    else         MoveGen::pseudoLegalMoves(pos, moveList);

    const int pawn = pos.isWhiteMove() ? Piece::WPAWN : Piece::BPAWN;

    int bestEP = std::numeric_limits<int>::min();

    UndoInfo ui;

    for (int m = 0; m < moveList.size; m++) {

        const Move& move = moveList[m];

        if ((move.to() == pos.getEpSquare()) && (pos.getPiece(move.from()) == pawn)) {

            if (MoveGen::isLegal(pos, move, inCheck)) {

                pos.makeMove(move, ui);

                int score2;

                bool ret2 = probeFunc(pos, ply+1, score2);

                pos.unMakeMove(move, ui);

                if (!ret2) {

                    ret = false;

                    return;

                }

                bestEP = std::max(bestEP, -score2);

            }

        } else if (MoveGen::isLegal(pos, move, inCheck))

            return;

    }

    if (bestEP != std::numeric_limits<int>::min())

        score = bestEP;

}

bool

TBProbe::gtbProbeDTM(Position& pos, int ply, int& score) {

    if (BitBoard::bitCount(pos.occupiedBB()) > gtbMaxPieces)

        return false;

    GtbProbeData gtbData;

    getGTBProbeData(pos, gtbData);

    bool ret = gtbProbeDTM(gtbData, ply, score);

    if (ret && score == 0 && pos.getEpSquare() != -1)

        handleEP(pos, ply, score, ret, [](Position& pos, int ply, int& score) -> bool {

            return TBProbe::gtbProbeDTM(pos, ply, score);

        });

    return ret;

}

bool

TBProbe::gtbProbeWDL(Position& pos, int ply, int& score) {

    if (BitBoard::bitCount(pos.occupiedBB()) > gtbMaxPieces)

        return false;

    GtbProbeData gtbData;

    getGTBProbeData(pos, gtbData);

    bool ret = gtbProbeWDL(gtbData, ply, score);

    if (ret && score == 0 && pos.getEpSquare() != -1)

        handleEP(pos, ply, score, ret, [](Position& pos, int ply, int& score) -> bool {

            return TBProbe::gtbProbeWDL(pos, ply, score);

        });

    return ret;

}

bool

TBProbe::rtbProbeDTZ(Position& pos, int ply, int& score) {

    const int nPieces = BitBoard::bitCount(pos.occupiedBB());

    if (nPieces > Syzygy::TBLargest)

        return false;

    if (pos.getCastleMask())

        return false;

    int success;

    const int dtz = Syzygy::probe_dtz(pos, &success);

    if (!success)

        return false;

    if (dtz == 0) {

        score = 0;

        return true;

    }

    const int maxHalfMoveClock = std::abs(dtz) + pos.getHalfMoveClock();

    if (abs(dtz) <= 2) {

        if (maxHalfMoveClock > 101) {

            score = 0;

            return true;

        } else if (maxHalfMoveClock == 101)

            return false; // DTZ can be wrong when mate-in-1

    } else {

        if (maxHalfMoveClock > 100) {

            score = 0;

            return true;

        }

        // FIXME!! Are there positions where maxHalfMoveclock==101 needs special handling?

    }

    int plyToMate = getMaxSubMate(pos) + std::abs(dtz);

    if (dtz > 0) {

        score = SearchConst::MATE0 - ply - plyToMate - 2;

    } else {

        score = -(SearchConst::MATE0 - ply - plyToMate - 2);

    }

    return true;

}

bool

TBProbe::rtbProbeWDL(Position& pos, int ply, int& score) {

    if (BitBoard::bitCount(pos.occupiedBB()) > Syzygy::TBLargest)

        return false;

    if (pos.getCastleMask())

        return false;

    int success;

    int wdl = Syzygy::probe_wdl(pos, &success);

    if (!success)

        return false;

    int plyToMate;

    switch (wdl) {

    case 0: case 1: case -1:

        score = 0;

        break;

    case 2:

        plyToMate = getMaxSubMate(pos) + getMaxDTZ(pos.materialId());

        score = SearchConst::MATE0 - ply - plyToMate - 2;

        break;

    case -2:

        plyToMate = getMaxSubMate(pos) + getMaxDTZ(pos.materialId());

        score = -(SearchConst::MATE0 - ply - plyToMate - 2);

        break;

    default:

        return false;

    }

    return true;

}

void

TBProbe::gtbInitialize(const std::string& path, int cacheMB, int wdlFraction) {

    static_assert((int)tb_A1 == (int)A1, "Incompatible square numbering");

    static_assert((int)tb_A8 == (int)A8, "Incompatible square numbering");

    static_assert((int)tb_H1 == (int)H1, "Incompatible square numbering");

    static_assert((int)tb_H8 == (int)H8, "Incompatible square numbering");

    tbpaths_done(gtbPaths);

    gtbMaxPieces = 0;

    gtbPaths = tbpaths_init();

    gtbPaths = tbpaths_add(gtbPaths, path.c_str());

    TB_compression_scheme scheme = tb_CP4;

    int verbose = 0;

    int cacheSize = 1024 * 1024 * cacheMB;

    static bool isInitialized = false;

    if (isInitialized) {

        tb_restart(verbose, scheme, gtbPaths);

        tbcache_restart(cacheSize, wdlFraction);

    } else {

        tb_init(verbose, scheme, gtbPaths);

        tbcache_init(cacheSize, wdlFraction);

    }

    isInitialized = true;

    unsigned int av = tb_availability();

    if (av & 3)

        gtbMaxPieces = 3;

    if (av & 12)

        gtbMaxPieces = 4;

    if (av & 48)

        gtbMaxPieces = 5;

}

void

TBProbe::getGTBProbeData(const Position& pos, GtbProbeData& gtbData) {

    gtbData.stm = pos.isWhiteMove() ? tb_WHITE_TO_MOVE : tb_BLACK_TO_MOVE;

    gtbData.epsq = pos.getEpSquare() >= 0 ? pos.getEpSquare() : tb_NOSQUARE;

    gtbData.castles = 0;

    if (pos.a1Castle()) gtbData.castles |= tb_WOOO;

    if (pos.h1Castle()) gtbData.castles |= tb_WOO;

    if (pos.a8Castle()) gtbData.castles |= tb_BOOO;

    if (pos.h8Castle()) gtbData.castles |= tb_BOO;

    int cnt = 0;

    U64 m = pos.whiteBB();

    while (m != 0) {

        int sq = BitBoard::extractSquare(m);

        gtbData.wSq[cnt] = sq;

        switch (pos.getPiece(sq)) {

        case Piece::WKING:   gtbData.wP[cnt] = tb_KING;   break;

        case Piece::WQUEEN:  gtbData.wP[cnt] = tb_QUEEN;  break;

        case Piece::WROOK:   gtbData.wP[cnt] = tb_ROOK;   break;

        case Piece::WBISHOP: gtbData.wP[cnt] = tb_BISHOP; break;

        case Piece::WKNIGHT: gtbData.wP[cnt] = tb_KNIGHT; break;

        case Piece::WPAWN:   gtbData.wP[cnt] = tb_PAWN;   break;

        default:

            assert(false);

        }

        cnt++;

    }

    gtbData.wSq[cnt] = tb_NOSQUARE;

    gtbData.wP[cnt] = tb_NOPIECE;

    cnt = 0;

    m = pos.blackBB();

    while (m != 0) {

        int sq = BitBoard::extractSquare(m);

        gtbData.bSq[cnt] = sq;

        switch (pos.getPiece(sq)) {

        case Piece::BKING:   gtbData.bP[cnt] = tb_KING;   break;

        case Piece::BQUEEN:  gtbData.bP[cnt] = tb_QUEEN;  break;

        case Piece::BROOK:   gtbData.bP[cnt] = tb_ROOK;   break;

        case Piece::BBISHOP: gtbData.bP[cnt] = tb_BISHOP; break;

        case Piece::BKNIGHT: gtbData.bP[cnt] = tb_KNIGHT; break;

        case Piece::BPAWN:   gtbData.bP[cnt] = tb_PAWN;   break;

        default:

            assert(false);

        }

        cnt++;

    }

    gtbData.bSq[cnt] = tb_NOSQUARE;

    gtbData.bP[cnt] = tb_NOPIECE;

    gtbData.materialId = pos.materialId();

}

bool

TBProbe::gtbProbeDTM(const GtbProbeData& gtbData, int ply, int& score) {

    unsigned int tbInfo;

    unsigned int plies;

    if (!tb_probe_hard(gtbData.stm, gtbData.epsq, gtbData.castles,

                       gtbData.wSq, gtbData.bSq,

                       gtbData.wP, gtbData.bP,

                       &tbInfo, &plies))

        return false;

    switch (tbInfo) {

    case tb_DRAW:

        score = 0;

        break;

    case tb_WMATE:

        score = SearchConst::MATE0 - ply - plies - 1;

        break;

    case tb_BMATE:

        score = -(SearchConst::MATE0 - ply - (int)plies - 1); // Pierre-Marie Baty -- added type cast

        break;

    default:

        return false;

    };

    if (gtbData.stm == tb_BLACK_TO_MOVE)

        score = -score;

    return true;

}

bool

TBProbe::gtbProbeWDL(const GtbProbeData& gtbData, int ply, int& score) {

    unsigned int tbInfo;

    if (!tb_probe_WDL_hard(gtbData.stm, gtbData.epsq, gtbData.castles,

                           gtbData.wSq, gtbData.bSq,

                           gtbData.wP, gtbData.bP,

                           &tbInfo))

        return false;

    switch (tbInfo) {

    case tb_DRAW:

        score = 0;

        break;

    case tb_WMATE:

        score = maxDTM[gtbData.materialId] - ply;

        break;

    case tb_BMATE:

        score = -(maxDTM[gtbData.materialId] - ply);

        break;

    default:

        return false;

    };

    if (gtbData.stm == tb_BLACK_TO_MOVE)

        score = -score;

    return true;

}

void

TBProbe::initWDLBounds() {

    initMaxDTM();

    initMaxDTZ();

    // Pre-calculate all interesting maxSubDTM values

    for (int wp = 0; wp <= 4; wp++) {

        std::vector<int> pieces(Piece::nPieceTypes);

        pieces[Piece::WPAWN] = wp;

        pieces[Piece::BPAWN] = 4 - wp;

        getMaxSubMate(pieces, 4*5);

    }

}

/** Maximum DTZ value for a given material configuration. */

int

TBProbe::getMaxDTZ(int matId) {

    auto it = maxDTZ.find(matId);

    if (it == maxDTZ.end())

        return 100;

    int val = it->second;

    if (val < 0)

        return 0;

    else

        return std::min(val+2, 100); // RTB DTZ values are not exact

}

static int

getMaxPawnMoves(const Position& pos) {

    int maxPawnMoves = 0;

    U64 m = pos.pieceTypeBB(Piece::WPAWN);

    while (m != 0) {

        int sq = BitBoard::extractSquare(m);

        maxPawnMoves += 6 - Position::getY(sq);

    }

    m = pos.pieceTypeBB(Piece::BPAWN);

    while (m != 0) {

        int sq = BitBoard::extractSquare(m);

        maxPawnMoves += Position::getY(sq) - 1;

    }

    return maxPawnMoves;

}

/** Get upper bound on longest mate in all possible material configurations

 * after the next zeroing move. */

int

TBProbe::getMaxSubMate(const Position& pos) {

    int maxPawnMoves = getMaxPawnMoves(pos);

    int matId = pos.materialId();

    matId = std::min(matId, MatId::mirror(matId));

    auto it = maxSubDTM.find(std::make_pair(matId,maxPawnMoves));

    if (it != maxSubDTM.end())

        return it->second;

    std::vector<int> pieces(Piece::nPieceTypes);

    for (int p = 0; p < Piece::nPieceTypes; p++)

        pieces[p] = BitBoard::bitCount(pos.pieceTypeBB((Piece::Type)p));

    pieces[Piece::EMPTY] = pieces[Piece::WKING] = pieces[Piece::BKING] = 0;

    return getMaxSubMate(pieces, maxPawnMoves);

}

int

TBProbe::getMaxSubMate(std::vector<int>& pieces, int pawnMoves) {

    assert(pawnMoves >= 0);

    if (pawnMoves > (pieces[Piece::WPAWN] + pieces[Piece::BPAWN]) * 5)

        return 0;

    MatId matId;

    for (int p = 0; p < Piece::nPieceTypes; p++)

        matId.addPieceCnt(p, pieces[p]);

    const int matIdMin = std::min(matId(), MatId::mirror(matId()));

    auto it = maxSubDTM.find(std::make_pair(matIdMin, pawnMoves));

    if (it != maxSubDTM.end())

        return it->second;

    int maxSubMate = 0;

    if (pawnMoves > 0) { // Pawn move

        maxSubMate = getMaxSubMate(pieces, pawnMoves-1) + getMaxDTZ(matId());

    }

    for (int p = 0; p < Piece::nPieceTypes; p++) { // Capture

        if (pieces[p] > 0) {

            pieces[p]--;

            matId.removePiece(p);

            int maxRemovedPawnMoves = 0;

            if (p == Piece::WPAWN || p == Piece::BPAWN)

                maxRemovedPawnMoves = 5;

            for (int i = 0; i <= maxRemovedPawnMoves; i++) {

                int newPawnMoves = pawnMoves - i;

                if (newPawnMoves >= 0) {

                    int tmp = getMaxSubMate(pieces, newPawnMoves) + getMaxDTZ(matId());

                    maxSubMate = std::max(maxSubMate, tmp);

                }

            }

            pieces[p]++;

            matId.addPiece(p);

        }

    }

    for (int c = 0; c < 2; c++) { // Promotion

        const int pawn = (c == 0) ? Piece::WPAWN : Piece::BPAWN;

        if (pieces[pawn] > 0) {

            const int p0 = (c == 0) ? Piece::WQUEEN : Piece::BQUEEN;

            const int p1 = (c == 0) ? Piece::WKNIGHT : Piece::BKNIGHT;

            for (int p = p0; p <= p1; p++) {

                pieces[pawn]--;

                pieces[p]++;

                matId.removePiece(pawn);

                matId.addPiece(p);

                int tmp = getMaxSubMate(pieces, pawnMoves) + getMaxDTZ(matId());

                maxSubMate = std::max(maxSubMate, tmp);

                pieces[pawn]++;

                pieces[p]--;

                matId.addPiece(pawn);

                matId.removePiece(p);

            }

        }

    }

#if 0

    std::cout << "wQ:" << pieces[Piece::WQUEEN]

              << " wR:" << pieces[Piece::WROOK]

              << " wB:" << pieces[Piece::WBISHOP]

              << " wN:" << pieces[Piece::WKNIGHT]

              << " wP:" << pieces[Piece::WPAWN]

              << " bQ:" << pieces[Piece::BQUEEN]

              << " bR:" << pieces[Piece::BROOK]

              << " bB:" << pieces[Piece::BBISHOP]

              << " bN:" << pieces[Piece::BKNIGHT]

              << " bP:" << pieces[Piece::BPAWN]

              << " pMoves:" << pawnMoves << " : " << maxSubMate << std::endl;

#endif

    maxSubDTM[std::make_pair(matIdMin, pawnMoves)] = maxSubMate;

    return maxSubMate;

}

void

TBProbe::initMaxDTM() {

    using MI = MatId;

    auto add = [](int id, int value) {

        maxDTM[id] = value;

        maxDTM[MatId::mirror(id)] = value;

    };

    add(MI::WQ, 31979);

    add(MI::WR, 31967);

    add(MI::WP, 31943);

    add(MI::WQ*2, 31979);

    add(MI::WQ+MI::WR, 31967);

    add(MI::WQ+MI::WB, 31979);

    add(MI::WQ+MI::WN, 31979);

    add(MI::WQ+MI::WP, 31943);

    add(MI::WR*2, 31967);

    add(MI::WR+MI::WB, 31967);

    add(MI::WR+MI::WN, 31967);

    add(MI::WR+MI::WP, 31943);

    add(MI::WB*2, 31961);

    add(MI::WB+MI::WN, 31933);

    add(MI::WB+MI::WP, 31937);

    add(MI::WN*2, 31998);

    add(MI::WN+MI::WP, 31943);

    add(MI::WP*2, 31935);

    add(MI::WQ+MI::BQ, 31974);

    add(MI::WR+MI::BQ, 31929);

    add(MI::WR+MI::BR, 31961);

    add(MI::WB+MI::BQ, 31965);

    add(MI::WB+MI::BR, 31941);

    add(MI::WB+MI::BB, 31998);

    add(MI::WN+MI::BQ, 31957);

    add(MI::WN+MI::BR, 31919);

    add(MI::WN+MI::BB, 31998);

    add(MI::WN+MI::BN, 31998);