didistribusikan pemangkasan alpha beta

19

Saya mencari algoritma yang efisien yang memungkinkan saya memproses pohon pencarian minimax untuk catur dengan pemangkasan alpha-beta pada arsitektur terdistribusi. Algoritma yang saya temukan (PVS, YBWC, DTS lihat di bawah) semuanya cukup tua (1990 adalah yang terbaru). Saya berasumsi ada banyak kemajuan besar sejak itu. Apa standar saat ini di bidang ini?

Juga tolong tunjukkan saya pada penjelasan idiot tentang DTS karena saya tidak dapat memahaminya dari makalah penelitian yang telah saya baca.

Algoritma yang disebutkan di atas:

  • PVS: Pemisahan Variasi Prinsip
  • YBWC: Young Brothers Wait Concept
  • DTS: Dynamic Tree Splitting

semua dibahas di sini .

algorithms distributed-systems board-games wirate
sumber
Mungkin ini bacaan yang menarik: chessbase.com/newsdetail.asp?newsid=8047
Alex ten Brink
2
Nah, ini masalah (memparalelkan pencarian minimax atau variannya) khususnya yang sulit. Dalam sebuah makalah yang akan muncul tahun ini oleh Richard Korf berjudul "Tantangan Penelitian dalam Pencarian Combinatorial", berikut ini dapat dibaca: "[...] pencarian minimum dengan pemangkas alfa-beta, telah terkenal sulit untuk diparalelkan" Saya dengan tulus ragu ada sebuah algoritma yang membuatnya selalu efisien ...
Carlos Linares López
Jadi, mengingat saya hanya seorang sarjana ilmu komputer semester 4 yang sangat rendah hati, haruskah saya mencari algoritma serial atau saya harus mencoba mengharapkan beberapa speedup sub-linear yang dapat diterima?
wirate
Maaf atas keterlambatan balasan saya, ini berlalu tanpa disadari di Kotak Masuk saya. Sebagai soal fakta, saya berharap bahwa penghematan akhir benar-benar tergantung pada distribusi skor yang diberikan oleh fungsi evaluasi Anda ke daun pohon pencarian. Secara umum, tidak ada jaminan bahwa algoritma pencarian terdistribusi akan berkinerja lebih baik secara signifikan daripada algoritma pencarian alpha-beta serial. Jadi, saya pasti akan menggunakan versi serialnya untuk mencoba sebanyak mungkin peningkatan yang dimungkinkan (urutan pemesanan, tabel transposisi, dll.)
Carlos Linares López
Saya sudah cukup sukses dengan alpha-beta paralel (pada dasarnya seperti yang dijelaskan pada halaman wiki yang Anda tautkan).
Daftar Jeremy

Jawaban:

3

ya teorinya telah maju secara signifikan dan agak karena literatur analisis catur dan teknik pemrograman paralel umum. berikut adalah beberapa referensi terbaru tentang (catur) pemangkasan alpha beta atas cluster / paralelisme yang didistribusikan. juga beberapa literatur catur komputasi terdistribusi awal mendahului banyak pola desain paralel dasar dan dapat dikonseptualisasikan dalam kerangka itu.

ide dasar di balik DTS adalah bahwa pohon pencarian didistribusikan di antara node komputasi berdasarkan kompleksitas pindah / tata letak. prosesor yang tidak digunakan yang "selesai lebih awal" dapat melakukan pekerjaan tambahan di luar alokasi awal yang dapat didistribusikan secara merata pada awalnya tetapi akan berubah menjadi tidak merata. karenanya pada dasarnya semacam antrian "load balancing" dan "produsen / konsumen" , atau juga mirip dengan penjadwalan pekerjaan.

Prosesor idle ini menyiarkan (menggunakan memori bersama) bahwa ia idle, dan tersedia untuk "membantu" setiap prosesor lain selesai mencari pohonnya. Prosesor yang sibuk mengumpulkan data "keadaan pohon", dan menyimpannya dalam memori bersama untuk diperiksa oleh prosesor yang menganggur. Prosesor idle ini menganalisis data ini, dan memutuskan yang mana (jika ada) dari prosesor yang sibuk tampaknya memiliki pohon yang cukup rumit sehingga akan efisien untuk membantu pencarian. Jika posisi seperti itu ditemukan, prosesor idle memberi tahu prosesor yang memiliki simpul ini dan mereka "bergabung".

ay
sumber