B Star Tree

Interval evaluasi daripada perkiraan
Simpul daun B * -tree diberi evaluasi yaitu interval daripada bilangan tunggal. Interval seharusnya mengandung nilai sebenarnya dari simpul itu. Jika semua interval yang menempel pada nodus daun memenuhi properti ini, maka B * akan mengidentifikasi jalur optimal menuju keadaan tujuan.

Proses backup
Untuk mencadangkan interval di dalam pohon, batas atas orang tua diatur ke batas maksimum anak-anak. Batas bawah orang tua diatur ke batas bawah anak-anak yang paling rendah. Perhatikan bahwa anak-anak yang berbeda mungkin akan menyediakan batas-batas ini.

Penghentian pencarian
B * secara sistematis memperluas node untuk menciptakan "pemisahan," yang terjadi ketika batas bawah anak langsung akar setidaknya sama besar dengan batas atas anak langsung lainnya dari akar. Pohon yang menciptakan pemisahan di akar berisi bukti bahwa anak terbaik setidaknya sama baiknya dengan anak lainnya.
Dalam prakteknya, pencarian yang kompleks mungkin tidak berhenti dalam batasan sumber daya praktis. Jadi algoritma ini biasanya ditambah dengan kriteria penghentian buatan seperti batas waktu atau memori. Bila batas buatan terpukul, maka Anda harus membuat penilaian heuristik tentang perpindahan mana yang akan dipilih. Biasanya, pohon itu akan memberi Anda bukti luas, seperti interval nodus akar.

Ekspansi
B * adalah proses terbaik pertama, yang berarti bahwa seluruh pohon disimpan dalam ingatan, dan berulang kali turun untuk menemukan daun untuk berkembang. Bagian ini menjelaskan bagaimana memilih node untuk memperluas.
Pada akar pohon, algoritma menerapkan salah satu dari dua strategi, yang disebut proof-best and disprove-rest. Dalam strategi terbaik, algoritme memilih nodus yang terkait dengan batas atas tertinggi. Harapannya adalah bahwa memperluas simpul tersebut akan menaikkan batas bawahnya lebih tinggi daripada batas atas simpul lainnya.
Strategi penyangkalan memutuskan memilih anak dari akar yang memiliki batas atas tertinggi kedua. Harapannya adalah dengan memperluas simpul itu Anda mungkin bisa mengurangi batas atas menjadi kurang dari batas bawah anak terbaik.

Pilihan strategi
Perhatikan bahwa menerapkan strategi penyangkalan tidak ada gunanya sampai batas bawah simpul anak yang memiliki batas atas tertinggi adalah yang tertinggi di antara semua batas bawah.
Keterangan algoritma asli tidak memberikan panduan lebih lanjut mengenai strategi mana yang akan dipilih. Ada beberapa alternatif yang masuk akal, seperti memperluas pilihan yang memiliki pohon lebih kecil.
Pemilihan strategi pada node non-root
Begitu seorang anak dari akar telah dipilih (menggunakan membuktikan-terbaik atau tidak-terbaik) maka algoritma turun ke simpul daun dengan berulang kali memilih anak yang memiliki batas atas tertinggi.
Ketika simpul daun tercapai, algoritma menghasilkan semua simpul penerus dan memberikan interval kepada mereka dengan menggunakan fungsi evaluasi. Kemudian interval semua node harus didukung dengan menggunakan operasi backup.
Bila transposisi dimungkinkan, maka operasi back-up mungkin perlu mengubah nilai simpul yang tidak terletak pada jalur seleksi. Dalam hal ini, algoritma membutuhkan petunjuk dari anak-anak kepada semua orang tua sehingga perubahannya bisa disebarkan. Perhatikan bahwa propagasi dapat berhenti saat operasi backup tidak mengubah interval yang terkait dengan node.

Robustness
Jika interval tidak benar (dalam arti bahwa nilai teoritis permainan dari simpul tidak terdapat dalam interval), maka B * mungkin tidak dapat mengidentifikasi jalur yang benar. Namun, algoritma ini cukup kuat untuk kesalahan dalam praktek.
Program Maven (Scrabble) memiliki inovasi yang meningkatkan ketahanan B * saat kesalahan evaluasi dimungkinkan. Jika pencarian berakhir karena perpisahan maka Maven memulai kembali pencarian setelah meluaskan semua interval evaluasi dengan jumlah kecil. Kebijakan ini semakin meluas pohon, akhirnya menghapus semua kesalahan.
Perpanjangan ke permainan dua pemain
Algoritma B * berlaku untuk dua pemain deterministik zero-sum games. Sebenarnya, satu-satunya perubahan adalah menafsirkan "terbaik" sehubungan dengan sisi yang bergerak di simpul itu. Jadi Anda akan mengambil maksimal jika sisi Anda bergerak, dan minimum jika lawan bergerak. Secara ekivalen, Anda dapat mewakili semua interval dari sudut pandang sisi untuk bergerak, dan kemudian meniadakan nilai selama operasi back-up.

Aplikasi
Andrew Palay menerapkan B * untuk catur. Evaluasi endpoint ditugaskan dengan melakukan pencarian null-move. Tidak ada laporan seberapa baik sistem ini dilakukan dibandingkan dengan mesin pencari pemangkasan alfa beta yang berjalan pada perangkat keras yang sama.
Program Maven (Scrabble) menerapkan pencarian B * ke endgames. Evaluasi endpoint ditugaskan menggunakan sistem perencanaan heuristik.
Algoritma pencarian B * telah digunakan untuk menghitung strategi optimal dalam permainan penjumlahan dari serangkaian permainan kombinatorial.
sib.stts.edu