Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


#Actualcrybot

Posted 27 April 2013 - 11:07 AM

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[i], pinned))
            {
                board.MakeMove(moves[i]);
                score = -search(depth - 1, -beta, -alpha, board);
                board.UndoMove(moves[i]);

                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[i];
                }
            }
        }

        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?


#2crybot

Posted 27 April 2013 - 11:06 AM

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[i], pinned))
            {
                board.MakeMove(moves[i]);
                score = -search(depth - 1, -beta, -alpha, board);
                board.UndoMove(moves[i]);

                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[i];
                }
            }
        }

        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?


#1crybot

Posted 27 April 2013 - 11:05 AM

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[i], pinned))
            {
                board.MakeMove(moves[i]);
                score = -search(depth - 1, -beta, -alpha, board);
                board.UndoMove(moves[i]);

                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[i];
                }
            }
        }

        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?


PARTNERS