Algoritma Alpha-Beta Pruning

Alpha Beta Pruning adalah cara untuk mengurangi jumlah simpul yang dieksplorasi dalam algoritma MinMax. Dengan alpha-beta, waktu yang diperlukan dalam pencarian akan berkurang dengan cara membatasi waktu yang terbuang percuma pada saat mengevaluasi pohon permainan. Implementasi alpha-beta akan memberikan jalur terbaik dalam setiap kemungkinan permainan dalam pohon permainan yang terbentuk.

Dalam algoritma alpha-beta, urutan jalannya algoritma akan dimulai sama seperti algoritma minmax. Untuk simpul MIN, nilai yang dihitung dimulai dengan +infinity dan akan menurun seiring jalannya permainan. Untuk simpul MAX, nilai akan dihitung mulai dengan –infinity dan akan menaik seiring berjalannya waktu.

Efisiensi prosedur alpha – beta akan sangat tergantung pada urutan simpul berikutnya dari sebuah simpul yang sedang dieksplorasi. Jika beruntung, maka sebuah simpul MIN akan dianggap sebagai simpul dengan urutan nilai dari rendah ke tinggi, dan simpul MAX dari tinggi ke rendah. Secara umum, dapat diperlihatkan bahwa dalam kondisi yang terbaik, alpha-beta akan membuka jumlah terminal nodes yang sama dengan MInMax dalam pohon permainan, dengan dua kali lipat tingkat kedalaman pohon.