8
\$\begingroup\$

I'm trying to put Transposition tables into my alpha beta scout. I do see an incremental speed boost I think toward mid or late game, however, even with a table size of 1-2GB, its may or may not be slower than just not reading from the Transpose table at all. I'm also noticing some less than efficient moves if I were to play the exact same game without the tables.

I tested my Zobrist key hashing, and they come out properly even after making and undoing moves. I don't believe they are the issue. I tried to follow the advice of these articles in designing the alpha/beta pruning. http://web.archive.org/web/20070809015843/http://www.seanet.com/~brucemo/topics/hashing.htm http://mediocrechess.blogspot.com/2007/01/guide-transposition-tables.html

Can anyone help me identify a mistake? Perhaps I'm not understanding the evaluation of checking alpha vs beta from the hash. Or is 1-2GB too small to make a difference? I can post more of the Transposition table code if need be.

 public int alphaBetaScout(Board board, int depth, int alpha, int beta, bool color, bool 
quiscence)
{
    // !!!! With or without this specific section, and any other Transpose.Insert, doesn't make the game play or evaluate any faster.
    HashType type = HashType.AlphaPrune;
    HashEntry h = Transpose.GetInstance().Get(board.zobristKey);
    if (h != null)
    {
        if (h.depth >= depth)
        {
            if (h.flag == HashType.ExactPrune)
            {
                return h.scored;
            }
            if (h.flag == HashType.AlphaPrune)
            {
                if(h.scoredState > alpha)
                {
                    alpha = h.scored;
                }
            }
            if (h.flag == HashType.BetaPrune)
            {
                if(h.scoredState < beta)
                {
                    beta = h.scored;
                }
            }
            if (alpha >= beta)
            {
                return alpha;
            }
        }
    }

    if (board.terminal)
    {
        int scoredState = board.Evaluate(color);
        Table.GetInstance().Add(board.zobristKey, depth, Entry.EXACT, scoredState);
        return scoredState;
    }

    //May do Quescience search here if necessary && depth = 0

    Stack movesGenerated = GeneratePossibleMoves();
    while(!movesGenerated.isEmpty())
    {
        int scoredState = MAXNEGASCOUT;

        board.MakeMove(movesGenerated.pop());
        int newAlpha = -(alpha +1)
        scoredState = -alphaBetaScout(board, depth - 1, newAlpha, -alpha, !color, quiscence);

        if (scoredState < beta && alpha < scoredState)
        {
            scoredState = -alphaBetaScout(board, depth - 1, -beta, -scoredState, !color, quiscence);
        }

        board.UndoMove();

        if (scoredState >= beta)
        {
            Table.GetInstance().Add(key, depth, Entry.BETA, beta);
            return scoredState;
        }

        if (scoredState > alpha)
        {
            type = HashType.ExactPrune;
            alpha = scoredState;
        }
    }
    Table.GetInstance().Add(key, depth, type, alpha);
    return alpha;
}
Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ I would pretty much have to read until I could do this myself to help more but, from a purely-C# perspective, I'm curious if .GetInstance() was used for a specific reason and if you could post that/those method(s)? \$\endgroup\$
    – Jon
    Feb 17, 2015 at 0:49
  • \$\begingroup\$ The question is a bit unclear - am I correct to understand, that 1) WITH transposition table, you evaluate the tree to about the same depth in the same time as WITHOUT transpositions and 2) WITH transposition table, the algorithm plays slightly better than WITHOUT transpositions? \$\endgroup\$
    – Martin Modrák
    Oct 14, 2015 at 13:43

2 Answers 2

Reset to default
0
\$\begingroup\$

The code seems OK at first glance. I would suggest profiling the transposition table, maybe your actual implementation is just to slow at storing and retrieving the entries. Which would also explain why you get better moves with transpositions, although you do not get a speed benefit.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Do not insert into transposition table at the leaf node.

So comment the "Add" command in this block "if (board.terminal)"

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ This answer would be better if it explained why this solves the problem. \$\endgroup\$
    – DMGregory ♦
    Aug 21, 2020 at 11:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .