Subversion Repositories Games.Chess Giants

/*

    Texel - A UCI chess engine.

    Copyright (C) 2012-2013  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/>.

*/

/*

 * treeLogger.hpp

 *

 *  Created on: Feb 25, 2012

 *      Author: petero

 */

#ifndef TREELOGGER_HPP_

#define TREELOGGER_HPP_

#include "util/util.hpp"

#include "move.hpp"

#include "parallel.hpp"

#include <vector>

#include <type_traits>

#include <utility>

#include <cstring>

#include <fstream>

class TreeLoggerWriter;

class TreeLoggerWriterDummy;

/** Change to TreeLoggerWriter to enable tree logging. */

using TreeLogger = TreeLoggerWriterDummy;

class Position;

namespace Serializer {

    template <typename Type>

    typename std::enable_if<std::is_integral<Type>::value, U8*>::type

    putBytes(U8* buffer, Type value) {

        int s = sizeof(value);

        memcpy(buffer, &value, s);

        return buffer + s;

    }

    template <int N>

    static U8* serialize(U8* buffer) {

        static_assert(N >= 0, "Buffer too small");

        return buffer;

    }

    /** Store a sequence of values in a byte buffer. */

    template <int N, typename Type0, typename... Types>

    static U8* serialize(U8* buffer, Type0 value0, Types... values) {

        const int s = sizeof(Type0);

        buffer = putBytes(buffer, value0);

        return serialize<N-s>(buffer, values...);

    }

    template <typename Type>

    typename std::enable_if<std::is_integral<Type>::value, const U8*>::type

    getBytes(const U8* buffer, Type& value) {

        int s = sizeof(value);

        memcpy(&value, buffer, s);

        return buffer + s;

    }

    template <int N>

    static const U8* deSerialize(const U8* buffer) {

        static_assert(N >= 0, "Buffer too small");

        return buffer;

    }

    /** Retrieve a sequence of values from a byte buffer. */

    template <int N, typename Type0, typename... Types>

    static const U8* deSerialize(const U8* buffer, Type0& value0, Types&... values) {

        const int s = sizeof(Type0);

        buffer = getBytes(buffer, value0);

        return deSerialize<N-s>(buffer, values...);

    }

}

/** Base class for logging search trees to file. */

class TreeLoggerBase {

    friend class TreeLoggerTest;

protected:

    /**

     * Rules for the log file format

     * - A log file contains a search tree dump for one thread.

     * - The file contains information for 0 or more searches.

     * - The log file for thread 0 contains information for a single search.

     * - Information for one search tree starts with a Position0 record and

     *   ends at the next Position0 record or at the end of the file.

     * - A start entry may not have a corresponding end entry. This happens

     *   if the search was interrupted.

     * - Start and end entries are properly nested (assuming the end entries exist)

     *   s1.index < s2.index => e1.index > e2.index

     */

    enum class EntryType : U8 {

        POSITION_INCOMPLETE, // First entry in file has this type when endIndex

                             // has not yet been computed for all StartEntries.

        POSITION_PART0,      // Position entry, first part.

        POSITION_PART1,      // Position entry, second part.

        POSITION_PART2,      // Position entry, third part.

        NODE_START,          // Start of a search node.

        NODE_END             // End of a search node.

    };

    static const U32 endMark = 0xffffffff;

    struct Position0 {

        U32 nextIndex;     // Index of next position, or endMark for last position.

        U64 word0;

        U64 word1;

        template <int N> U8* serialize(U8 buffer[N]) const {

            return Serializer::serialize<N>(buffer, nextIndex, word0, word1);

        }

        template <int N> void deSerialize(const U8 buffer[N]) {

            Serializer::deSerialize<N>(buffer, nextIndex, word0, word1);

        }

    };

    struct Position1 {

        U32 t0Index;

        U64 word2;

        U64 word3;

        template <int N> U8* serialize(U8 buffer[N]) const {

            return Serializer::serialize<N>(buffer, t0Index, word2, word3);

        }

        template <int N> void deSerialize(const U8 buffer[N]) {

            Serializer::deSerialize<N>(buffer, t0Index, word2, word3);

        }

    };

    struct Position2 {

        U64 word4;

        U8 owningThread;

        U8 moveNo;

        U32 parentIndex;    // Index in owning threads tree log

        template <int N> U8* serialize(U8 buffer[N]) const {

            return Serializer::serialize<N>(buffer, word4, owningThread, moveNo, parentIndex);

        }

        template <int N> void deSerialize(const U8 buffer[N]) {

            Serializer::deSerialize<N>(buffer, word4, owningThread, moveNo, parentIndex);

        }

    };

    struct StartEntry {

        U32 endIndex;

        U32 parentIndex;    // Points to NODE_START or POSITION_PART0 node.

        U16 move;

        S16 alpha;

        S16 beta;

        U8 ply;

        U16 depth;

        U32 t0Index;        // Current entry in thread 0

        Move getMove() const {

            Move ret;

            ret.setMove(move & 63, (move >> 6) & 63, (move >> 12) & 15, 0);

            return ret;

        }

        template <int N> U8* serialize(U8 buffer[N]) const {

            return Serializer::serialize<N>(buffer, endIndex, parentIndex, move,

                                            alpha, beta, ply, depth, t0Index);

        }

        template <int N> void deSerialize(const U8 buffer[N]) {

            Serializer::deSerialize<N>(buffer, endIndex, parentIndex, move,

                                       alpha, beta, ply, depth, t0Index);

        }

    };

    struct EndEntry {

        U32 startIndex;

        S16 score;

        U8 scoreType;

        S16 evalScore;

        U64 hashKey;

        U32 t0Index;        // Current entry in thread 0

        template <int N> U8* serialize(U8 buffer[N]) const {

            return Serializer::serialize<N>(buffer, startIndex, score, scoreType,

                                            evalScore, hashKey, t0Index);

        }

        template <int N> void deSerialize(const U8 buffer[N]) {

            Serializer::deSerialize<N>(buffer, startIndex, score, scoreType,

                                       evalScore, hashKey, t0Index);

        }

    };

    struct Entry {

        EntryType type;

        union {

            Position0 p0;

            Position1 p1;

            Position2 p2;

            StartEntry se;

            EndEntry ee;

        };

        static const int bufSize = 22;

        using Buffer = U8[bufSize];

        void serialize(U8 buffer[bufSize]) const {

            U8* ptr = buffer;

            using UType = std::underlying_type<EntryType>::type;

            const int su = sizeof(UType);

            UType uType = static_cast<UType>(type);

            ptr = Serializer::serialize<bufSize>(ptr, uType);

            switch (type) {

            case EntryType::POSITION_INCOMPLETE: p0.serialize<bufSize-su>(ptr); break;

            case EntryType::POSITION_PART0:      p0.serialize<bufSize-su>(ptr); break;

            case EntryType::POSITION_PART1:      p1.serialize<bufSize-su>(ptr); break;

            case EntryType::POSITION_PART2:      p2.serialize<bufSize-su>(ptr); break;

            case EntryType::NODE_START:          se.serialize<bufSize-su>(ptr); break;

            case EntryType::NODE_END:            ee.serialize<bufSize-su>(ptr); break;

            }

        }

        void deSerialize(U8 buffer[bufSize]) {

            const U8* ptr = buffer;

            using UType = std::underlying_type<EntryType>::type;

            const int su = sizeof(UType);

            UType uType;

            ptr = Serializer::deSerialize<bufSize>(ptr, uType);

            type = static_cast<EntryType>(uType);

            switch (type) {

            case EntryType::POSITION_INCOMPLETE: p0.deSerialize<bufSize-su>(ptr); break;

            case EntryType::POSITION_PART0:      p0.deSerialize<bufSize-su>(ptr); break;

            case EntryType::POSITION_PART1:      p1.deSerialize<bufSize-su>(ptr); break;

            case EntryType::POSITION_PART2:      p2.deSerialize<bufSize-su>(ptr); break;

            case EntryType::NODE_START:          se.deSerialize<bufSize-su>(ptr); break;

            case EntryType::NODE_END:            ee.deSerialize<bufSize-su>(ptr); break;

            }

        }

    };

    Entry entry;

    U8 entryBuffer[Entry::bufSize];

};

/** Writer class for logging search trees to file. */

class TreeLoggerWriter : public TreeLoggerBase {

public:

    /** Constructor. */

    TreeLoggerWriter();

    /** Destructor. */

    ~TreeLoggerWriter();

    /** Open log file for writing. */

    void open(const std::string& filename, ParallelData& pd, int threadNo);

    /** Flush write cache and close log file. */

    void close();

    /** Return true if log file is opened. */

    bool isOpened() const;

    /** Log information for new position to search.

     * Return index of position entry. */

    U64 logPosition(const Position& pos, int owningThread, U64 parentIndex, int moveNo);

    /**

     * Log information when entering a search node.

     * @param parentId     Index of parent node.

     * @param m            Move made to go from parent node to this node

     * @param alpha        Search parameter

     * @param beta         Search parameter

     * @param ply          Search parameter

     * @param depth        Search parameter

     * @return node index

     */

    U64 logNodeStart(U64 parentIndex, const Move& m, int alpha, int beta, int ply, int depth);

    /**

     * Log information when leaving a search node.

     * @param startIndex Pointer to corresponding start node entry.

     * @param score      Computed score for this node.

     * @param scoreType  See TranspositionTable, T_EXACT, T_GE, T_LE.

     * @param evalScore  Score returned by evaluation function at this node, if known.

     * @return node index

     */

    U64 logNodeEnd(U64 startIndex, int score, int scoreType, int evalScore, U64 hashKey);

private:

    /** Write position entries to end of file. */

    void writePosition(const Position& pos, int owningThread, U64 parentIndex, int moveNo);

    /** Write entry to end of file. Uses internal buffering, flushed in close(). */

    void appendEntry(const Entry& entry);

    bool opened;

    std::ofstream os;

    U64 nextIndex;

    ParallelData* pd;

    int threadNo;

    static const int writeCacheSize = 1024;

    U8 writeCache[Entry::bufSize * writeCacheSize];

    int nInWriteCache;

};

/** Dummy version of TreeLoggerWriter. */

class TreeLoggerWriterDummy {

public:

    TreeLoggerWriterDummy() { }

    void open(const std::string& filename, ParallelData& pd, int threadNo) { }

    void close() { }

    bool isOpened() const { return false; }

    U64 logPosition(const Position& pos, int owningThread, U64 parentIndex, int moveNo) { return 0; }

    U64 logNodeStart(U64 parentIndex, const Move& m, int alpha, int beta, int ply, int depth) { return 0; }

    U64 logNodeEnd(U64 startIndex, int score, int scoreType, int evalScore, U64 hashKey) { return 0; }

};

/**

 * Reader/analysis class for a search tree dumped to a file.

 */

class TreeLoggerReader : public TreeLoggerBase {

public:

    /** Constructor. */

    TreeLoggerReader(const std::string& filename);

    void close();

    /** Main loop of the interactive tree browser. */

    static void main(const std::string& filename);

private:

    /** Compute endIndex for all StartNode entries. */

    void computeForwardPointers();

    /** Write forward pointer data to disk. */

    void flushForwardPointerData(std::vector<std::pair<U64,U64>>& toWrite);

    /** Get root node information. */

    void getRootNode(U64 index, Position& pos);

    void getRootNode(U64 index, Position& pos, int& owningThread,

                     U64& parentIndex, int& moveNo, U64& t0Index);

    /** Read an entry. */

    void readEntry(U64 index, Entry& entry);

    /** Write an entry. */

    void writeEntry(U64 index, const Entry& entry);

    /** Run the interactive analysis main loop. */

    void mainLoop();

    bool isMove(std::string cmdStr) const;

    /** Return all nodes with a given hash key. */

    void getNodesForHashKey(U64 hashKey, std::vector<U64>& nodes, U64 maxEntry);

    /** Get hash key from an input string. */

    U64 getHashKey(std::string& s, U64 defKey) const;

    /** Get integer parameter from an input string. */

    static int getArg(const std::string& s, int defVal);

    /** Get a list of integer parameters from an input string. */

    void getArgs(const std::string& s, int defVal, std::vector<int>& args);

    /** Get a string parameter from an input string. */

    static std::string getArgStr(const std::string& s, const std::string& defVal);

    void printHelp();

    /** Read start/end entries for a tree node. Return true if the end entry exists. */

    bool readEntries(int index, StartEntry& se, EndEntry& ee);

    /** Find the parent node to a node. */

    S64 findParent(S64 index);

    /** Find all children of a node. */

    void findChildren(S64 index, std::vector<U64>& childs);

    /** Get node position in parents children list. */

    int getChildNo(U64 index);

    /** Get list of nodes from root position to a node. */

    void getNodeSequence(U64 index, std::vector<U64>& nodes);

    /** Find list of moves from root node to a node.

     * Return root node index. */

    U64 getMoveSequence(U64 index, std::vector<Move>& moves);

    /** Find the position corresponding to a node. */

    Position getPosition(U64 index);

    void printNodeInfo(U64 index, int childNo = -1, const std::string& filterMove = "");

    std::fstream fs;

    S64 filePos;        // Current file read position (seekg)

    U64 numEntries;

};

inline

TreeLoggerWriter::TreeLoggerWriter()

    : opened(false), nextIndex(0), pd(nullptr), threadNo(-1), nInWriteCache(0) {

}

inline

TreeLoggerWriter::~TreeLoggerWriter() {

    close();

}

inline bool

TreeLoggerWriter::isOpened() const {

    return opened;

}

inline U64

TreeLoggerWriter::logPosition(const Position& pos, int owningThread, U64 parentIndex, int moveNo) {

    U64 ret = nextIndex;

    if (threadNo == 0)

        pd->t0Index = (U32)ret;

    writePosition(pos, owningThread, parentIndex, moveNo);

    return ret;

}

inline U64

TreeLoggerWriter::logNodeStart(U64 parentIndex, const Move& m, int alpha, int beta, int ply, int depth) {

    if (!opened)

        return 0;

    if (threadNo == 0)

        pd->t0Index = (U32)nextIndex;

    entry.type = EntryType::NODE_START;

    entry.se.endIndex = -1;

    entry.se.parentIndex = (U32)parentIndex;

    entry.se.move = m.from() + (m.to() << 6) + (m.promoteTo() << 12);

    entry.se.alpha = alpha;

    entry.se.beta = beta;

    entry.se.ply = ply;

    entry.se.depth = depth;

    entry.se.t0Index = pd->t0Index;

    appendEntry(entry);

    return nextIndex++;

}

inline U64

TreeLoggerWriter::logNodeEnd(U64 startIndex, int score, int scoreType, int evalScore, U64 hashKey) {

    if (!opened)

        return 0;

    if (threadNo == 0)

        pd->t0Index = (U32)nextIndex;

    entry.type = EntryType::NODE_END;

    entry.ee.startIndex = (U32)startIndex;

    entry.ee.score = score;

    entry.ee.scoreType = scoreType;

    entry.ee.evalScore = evalScore;

    entry.ee.hashKey = hashKey;

    entry.ee.t0Index = pd->t0Index;

    appendEntry(entry);

    return nextIndex++;

}

inline void

TreeLoggerReader::getRootNode(U64 index, Position& pos) {

    int owningThread;

    U64 parentIndex;

    int moveNo;

    U64 t0Index;

    getRootNode(index, pos, owningThread, parentIndex, moveNo, t0Index);

}

#endif /* TREELOGGER_HPP_ */