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.


crybot

Member Since 21 Apr 2013
Offline Last Active Jun 20 2013 01:46 PM

Posts I've Made

In Topic: Chess Engine - search development priority

27 April 2013 - 12:49 PM

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 smile.png


In Topic: Chess Engine - search development priority

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 one?


In Topic: Chess Engine - search development priority

26 April 2013 - 09:47 AM

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)...


In Topic: Chess Engine - search development priority

26 April 2013 - 07:57 AM

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)?


In Topic: Chess Engine - search development priority

26 April 2013 - 06:26 AM

You need to debug the difference in perft with and without transposition tables. Can you post the definition of the type of your TT entries?

 

namespace Napoleon
{
    enum ScoreType { Exact, Alpha, Beta };

    class HashEntry
    {
    public:
        ZobristKey Hash; // unsigned long long
        Byte Depth; // unsigned char
        Byte Bound; // unsigned char
        Move BestMove; // 32 bit integer wrapper
        int Score;

        HashEntry();
        HashEntry(ZobristKey, Byte, int, Move, Byte);
    };
}

PARTNERS