NegaScout dengan Tabel Transposisi Zobrist di Catur

8

Saya mencoba untuk menempatkan tabel Transposisi ke dalam pramuka alfa beta saya. Saya memang melihat peningkatan kecepatan tambahan yang saya pikir menuju pertengahan atau akhir permainan, namun, bahkan dengan ukuran meja 1-2GB, mungkin atau mungkin tidak lebih lambat daripada tidak membaca dari tabel Transpose sama sekali. Saya juga memperhatikan beberapa gerakan yang kurang efisien jika saya memainkan permainan yang sama persis tanpa tabel.

Saya menguji hashing kunci Zobrist saya, dan mereka keluar dengan benar bahkan setelah membuat dan membatalkan gerakan. Saya tidak percaya itu masalahnya. Saya mencoba mengikuti saran dari artikel ini dalam mendesain pemangkasan alpha / beta. http://web.archive.org/web/20070809015843/http://www.seanet.com/~brucemo/topics/hashing.htm http://mediocrechess.blogspot.com/2007/01/guide-transposition- tables.html

Adakah yang bisa membantu saya mengidentifikasi kesalahan? Mungkin saya tidak mengerti evaluasi memeriksa alpha vs beta dari hash. Atau 1-2GB terlalu kecil untuk membuat perbedaan? Saya dapat memposting lebih banyak kode tabel Transposisi jika perlu.

 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;
}
missCache
sumber
Saya cukup banyak harus membaca sampai saya bisa melakukan ini sendiri untuk membantu lebih tetapi, dari perspektif C-murni, saya ingin tahu apakah .GetInstance () digunakan untuk alasan tertentu dan jika Anda dapat memposting metode / itu ( s)?
Jon
Pertanyaannya agak tidak jelas - apakah saya benar untuk memahami, bahwa 1) DENGAN tabel transposisi, Anda mengevaluasi pohon dengan kedalaman yang sama dalam waktu yang sama dengan TANPA transposisi dan 2) DENGAN tabel transposisi, algoritma bermain sedikit lebih baik daripada TANPA transposisi?
Martin Modrák

Jawaban:

0

Sekilas kode tampak OK. Saya akan menyarankan profil tabel transposisi, mungkin implementasi Anda yang sebenarnya hanya memperlambat menyimpan dan mengambil entri. Yang juga akan menjelaskan mengapa Anda mendapatkan gerakan yang lebih baik dengan transposisi, meskipun Anda tidak mendapatkan manfaat kecepatan.

Martin Modrák
sumber
0

Jangan masukkan ke tabel transposisi di simpul daun.

Jadi komentari perintah "Tambah" di blok ini "jika (board.terminal)"

Abel
sumber