NegaScout avec des tables de transposition Zobrist aux échecs

8

J'essaie de mettre des tables de transposition dans mon éclaireur alpha bêta. Je vois une augmentation de vitesse incrémentielle, je pense vers le milieu ou la fin du jeu, cependant, même avec une taille de table de 1 à 2 Go, cela peut ou non être plus lent que de ne pas lire du tout de la table Transpose. Je remarque également des mouvements moins qu'efficaces si je devais jouer exactement le même jeu sans les tables.

J'ai testé mon hachage de clé Zobrist, et ils sortent correctement même après avoir effectué et annulé des mouvements. Je ne pense pas que ce soit le problème. J'ai essayé de suivre les conseils de ces articles lors de la conception de l'élagage alpha / bêta. http://web.archive.org/web/20070809015843/http://www.seanet.com/~brucemo/topics/hashing.htm http://mediocrechess.blogspot.com/2007/01/guide-transposition- tables.html

Quelqu'un peut-il m'aider à identifier une erreur? Peut-être que je ne comprends pas l'évaluation de la vérification alpha vs bêta du hachage. Ou est-ce que 1-2 Go est trop petit pour faire la différence? Je peux poster plus de code de table de transposition si besoin est.

 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
la source
Je devrais à peu près lire jusqu'à ce que je puisse le faire moi-même pour aider davantage mais, d'un point de vue purement C #, je suis curieux de savoir si .GetInstance () a été utilisé pour une raison spécifique et si vous pouviez poster cette / ces méthode ( s)?
Jon
La question n'est pas claire - ai-je raison de comprendre que 1) AVEC la table de transposition, vous évaluez l'arbre à environ la même profondeur en même temps que SANS transpositions et 2) AVEC la table de transposition, l'algorithme joue légèrement mieux que SANS transpositions?
Martin Modrák

Réponses:

0

Le code semble correct à première vue. Je suggérerais de profiler la table de transposition, peut-être que votre implémentation réelle est juste de ralentir le stockage et la récupération des entrées. Ce qui expliquerait également pourquoi vous obtenez de meilleurs mouvements avec les transpositions, bien que vous n'obteniez pas d'avantage de vitesse.

Martin Modrák
la source
0

Ne pas insérer dans la table de transposition au nœud feuille.

Alors commentez la commande "Ajouter" dans ce bloc "if (board.terminal)"

Abel
la source