NegaScout с таблицами зобристической транспозиции в шахматах

8

Я пытаюсь поместить таблицы транспозиции в мою альфа-бета-версию. Я вижу постепенное повышение скорости в середине или конце игры, однако, даже при размере таблицы 1-2 ГБ, она может или не может быть медленнее, чем просто не читать из таблицы Transpose вообще. Я также заметил некоторые менее эффективные ходы, если бы я играл в ту же игру без столов.

Я проверил хэширование ключей Zobrist, и они правильно вышли даже после выполнения и отмены ходов. Я не верю, что они являются проблемой. Я попытался последовать совету этих статей при разработке обрезки альфа / бета. http://web.archive.org/web/20070809015843/http://www.seanet.com/~brucemo/topics/hashing.htm http://mediocrechess.blogspot.com/2007/01/guide-transposition- tables.html

Может ли кто-нибудь помочь мне определить ошибку? Возможно, я не понимаю оценку проверки альфа против бета из хеша. Или 1-2 ГБ слишком мало, чтобы изменить ситуацию? Я могу опубликовать больше кода таблицы транспозиции, если это будет необходимо.

 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;
}
c# software-engineering ai strategy chess missCache
источник
Мне бы пришлось читать до тех пор, пока я сам не смогу сделать это, чтобы помочь больше, но, с точки зрения чисто C #, мне любопытно, если .GetInstance () использовался по определенной причине, и если вы могли бы опубликовать этот / те метод ( s)?
Джон
Вопрос немного неясен - правильно ли я понимаю, что 1) с таблицей транспонирования вы оцениваете дерево примерно на той же глубине в то же время, что и без транспозиции, и 2) с таблицей транспонирования алгоритм работает немного лучше, чем БЕЗ транспозиции?
Мартин Модрак

Ответы:

0

На первый взгляд код кажется нормальным. Я бы предложил профилировать таблицу транспонирования, возможно, ваша реальная реализация - просто замедлить хранение и извлечение записей. Что также объясняет, почему вы получаете лучшие движения с транспозициями, хотя вы не получаете выигрыша в скорости.

Мартин Модрак
источник
0

Не вставляйте в таблицу транспонирования на листовом узле.

Поэтому прокомментируйте команду «Добавить» в этом блоке «if (board.terminal)»

Абель
источник