The data structure seems correct. The only comment I have is that if you switch to using a 16-bit representation for the move, the size of a hash entry will go from 24 bytes to 16 bytes (this depends on the compiler, of course).

I know, I planned to change move encoding not just for the hashentry, but also for move generation. It will take some time, so i'll do it when i can.

Anyway now a HashEntry is a 18 bytes object.

Can you tell me something about what i wrote in my previous post?

The last thing I have doubts about is principal variation: I'm triyng to improve move ordering and it seems that principal variation moves are the most important moves to try during alpha-beta search, but, with transposition table implemented, aren't them already the first moves tried (best moves)?

Please, print sizeof(Napoleon::HashEntry) and see if you get 18 (you won't).

I agree that there is nothing special to do about principal-variation moves when sorting, because using the move from the hash should be about the same thing as picking it from the PV.

Please, print sizeof(Napoleon::HashEntry) and see if you get 18 (you won't).

you are right... I didn't know that even if a char should be of size 1 byte the compiler allocate 4 byte for it(I still don't get why)...

It doesn't... but what it does do (EDIT: by default) is align 32 bit ints on a 4 byte boundary, and 16 bit ints on a 2 byte boundary. So there is 2 bytes wasted after you have 2 bytes followed by an int.

You get the best packing in classes and structs by having the largest members first in the struct/class. Changing the order shouldn't require changes to any client code.

In 64-bit code your struct will probably get a size of 24 bytes, because the 64-bit integer will be aligned to 8 bytes.

http://en.wikipedia.org/wiki/Data_structure_alignment

I understand.

I finally completely debugged my engine and found an other few bugs and now the transposition table is bug free (tested with my perft suite).

Despite this, when i make my program match itself it still produce a different end state with and without transposition table.

What could be the problem? Are we sure that it should produce the same result?

for clarity i post my actual code:

alpha-beta search:

    int Search::search(int depth, int alpha, int beta, Board& board)
    {
        int bound = Alpha;
        int pos = 0;
        int score;
        Move best = Constants::NullMove;
        Move moves[Constants::MaxMoves];

        if((score = board.Table.Probe(board.zobrist, depth, alpha, &best, beta)) != TranspositionTable::Unknown)
            return score;

        if(depth == 0)
            return quiesce(alpha, beta, board);

        BitBoard pinned = board.GetPinnedPieces();

        // tries best move first (if there is one)
        if(best != Constants::NullMove)
        {
            assert(board.IsMoveLegal(best, pinned));

            legal++;
            board.MakeMove(best);
            score = -search(depth - 1, -beta, -alpha, board);
            board.UndoMove(best);

            if( score >= beta )
                return beta;

            if( score > alpha )
            {
                bound = Exact;
                alpha = score;
            }
        }

        MoveGenerator::GetPseudoLegalMoves<false>(moves, pos, board); // get captures and non-captures

        for (int i=0; i<pos; i++)
        {
            if (board.IsMoveLegal(moves, pinned))
            {
                board.MakeMove(moves);
                score = -search(depth - 1, -beta, -alpha, board);
                board.UndoMove(moves);

                if( score >= beta )
                {
                    board.Table.Save(board.zobrist, depth, beta, best, Beta);
                    return beta;   //  fail hard beta-cutoff
                }
                if( score > alpha )
                {
                    bound = Exact;
                    alpha = score; // alpha acts like max in MiniMax
                    best = moves;
                }
            }
        }

        board.Table.Save(board.zobrist, depth, alpha, best, bound);
        return alpha;
}

transposition table class:

    TranspositionTable::TranspositionTable(unsigned long size)
    {
        Size = size;
        Table = new HashEntry[size]; // dynamic allocation is fine during program initialization
    }

    void TranspositionTable::Save(ZobristKey key, Byte depth, int score, Move move, Byte bound)
    {
        HashEntry* hash = &Table[key % Size];

        if (depth >= hash->Depth) // it runs faster than depth > hash->Depth
        {
            hash->Hash = key;
            hash->Score = score;
            hash->Depth = depth;
            hash->Bound = bound;
            hash->BestMove = move;
        }
    }

    int TranspositionTable::Probe(ZobristKey key, Byte depth, int alpha, Move* move, int beta)
    {
        HashEntry* hash = &Table[key % Size];

        if (hash->Hash == key)
        {
            if (hash->Depth >= depth)
            {
                if (hash->Bound == Exact)
                    return hash->Score;
                if (hash->Bound == Alpha && hash->Score <= alpha)
                    return alpha;
                if (hash->Bound == Beta && hash->Score >= beta)
                    return beta;
            }

            *move = hash->BestMove; // get best move on this position
        }
        return TranspositionTable::Unknown;
    }

could it be a replacement scheme problem or maybe a hash collision one?

You can't expect the state to be the same (see [url="http://chessprogramming.wikispaces.com/Search+Instability"search instability). But you can expect playing at a fixed depth should produce similar playing strength with and without transposition tables, which is what I suggested you test.

You can't expect the state to be the same (see [url="http://chessprogramming.wikispaces.com/Search+Instability"search instability). But you can expect playing at a fixed depth should produce similar playing strength with and without transposition tables, which is what I suggested you test.

sorry then, I misunderstood what you said.

Now I think i have no more problems and dubts with search, I just have to improve move ordering and try to apply more advanced search strategies.

Thank you for all