Bagaimana cara kerja algoritma NegaScout?

8

Pada pemangkasan Alpha-Beta, NegaScout mengklaim bahwa ia dapat mempercepat proses dengan mengatur [Alpha, Beta] ke [Alpha, Alpha-1].

Saya tidak mengerti seluruh proses NegaScout.

Bagaimana cara kerjanya? Apa mekanisme pemulihannya ketika tebakannya gagal?

algorithms algorithm-analysis search-algorithms sam
sumber
1
Harap berikan tautan ke referensi Anda dan rumuskan pertanyaan yang lebih fokus.
Raphael
1
Gagasan utama di balik NegaScout dijelaskan dengan jelas di tautan yang Anda berikan: dengan menggunakan jendela nol (di mana α dan β sama, bukan β=α-1seperti yang Anda katakan), dapat diverifikasi apakah anak paling kiri dari setiap kedalaman terletak pada variasi utama atau tidak. Jika demikian, pencarian dihentikan. Jika tidak, algoritma akan berlanjut sebagai algoritma pencarian minimax biasa dengan pemangkasan alpha-beta. Perhatikan bahwa NegaScout memperluas kembali semua node yang terletak di cabang kiri algoritma pencarian. Selain itu, ini didasarkan pada Negamax bukan Minimax.
Carlos Linares López
Apa arti kalimat ini 'dapat diverifikasi apakah anak paling kiri dari setiap kedalaman terletak pada variasi pokok atau tidak.' ? Apakah ada contoh? Terima kasih ~
sam
@ CarlosLinaresLópez, jika Anda ingin memperluas komentar Anda menjadi sebuah jawaban, kami dapat membersihkan jawaban ini
Merbs

Jawaban:

6

Maaf atas keterlambatan balasan ( 4 tahun !)

NegaScout adalah algoritma yang sangat sederhana. Untuk memahami kita harus merevisi pendalaman iteratif .

Pendalaman berulang adalah teknik untuk mesin catur untuk mencari kedalaman i, lalu i +1, lalu i + 2 dll. Ini adalah contoh pemrograman dinamis. Selama setiap iterasi, kami memiliki tebakan terbaik kami tentang langkah terbaik yang akan diambil. Sebagian besar mesin catur akan menjaga langkah ini dalam tabel hashing.

Bayangkan kita sekarang di iterasi i +1, dan kita memiliki langkah terbaik dari iterasi terakhir i. Sekarang kita memiliki 5 node untuk dicari, apa yang harus kita lakukan?

Jika kita mengasumsikan kita telah melakukan pekerjaan yang cukup baik selama iterasi terakhir kita, langkah terbaik dari iterasi terakhir (yang kita dapatkan dari tabel hash) juga harus menjadi langkah terbaik untuk iterasi saat ini.

Jika asumsi kita benar, kita harus dapat menghemat waktu dengan mencari setiap gerakan selain langkah terbaik (empat langkah tidak dalam tabel hash) dengan a null window. Jendela nol adalah sesuatu seperti:

score := -pvs(child, depth-1, -α-1, -α, -color)

Catatan -α-1dan -α. Nilai tersebut adalah nilai alfa dan beta yang akan kami berikan untuk rekursi berikutnya. Karena lebar jendela hanya 1, pencarian akan selalu gagal:

  • Jika gagal di bawah α, langkah itu lebih buruk daripada yang sudah kita miliki, jadi kita bisa mengabaikannya
  • Jika gagal di atas β, gerakannya terlalu bagus untuk dimainkan, jadi kita bisa mengabaikannya
  • Kalau tidak, kita perlu melakukan pencarian baru dengan benar

Tentu saja, kita masih akan mencari langkah terbaik (yang kita dapatkan dari tabel hash) dengan jendela alpha dan beta yang tepat. Kita perlu melakukan ini karena kita perlu tahu persis nilai node, kita tidak bisa mengabaikannya begitu saja.

Semua yang saya katakan diimplementasikan dalam pseudocode berikut. Kode pseudocode menentukan child is not first childtetapi ini adalah cara untuk memeriksa apakah langkah tersebut juga merupakan langkah terbaik dalam iterasi sebelumnya. Tabel hash adalah implementasi yang paling umum.

# Negasort is also termed Principal Variation Search - hence - pvs

function pvs(node, depth, α, β, color)
    if node is a terminal node or depth = 0
        return color x the heuristic value of node

    for each child of node
        if child is not the first child
            # search with a null window
            score := -pvs(child, depth - 1, -α - 1, -α, -color)

            # if it failed high, do a full re-search
            if α < score < β
                score := -pvs(child, depth - 1, -β, -score, -color)
        else
            score := -pvs(child, depth - 1, -β, -α, -color)

        α := max(α, score)

        # beta cut-off
        if α >= β
            break

    return α
Halo Dunia
sumber