ANALISIS ALGORITMA MINIMAX DENGAN OPTIMASI ALPHA BETA PRUNIGN PADA PERMAINAN FIVE IN ROW

Abstract

Keberadaan industri game yang berkembang pesat membuktikan bahwa masyarakat menaruh minat yang besar terhadap permainan komputer. Salah satu jenis game komputer yang beredar luas antara lain game kecerdasan buatan, misalnya catur, dan Five In Row. Five In Row merupakan game logika yang membutuhkan strategi untuk mengalahkan lawan dengan menyusun lima buah keping sewarna dalam satu baris baik horizontal, vertikal, maupun diagonal. Algoritma yang diimplementasikan pada permainan ini adalah Minimax yang dioptimasikan dengan Alpha Beta Pruning. Minimax yang merupakan algoritma pohon pencarian akan melakukan penelusuran pada setiap node hingga diperoleh nilai maksimum untuk memenangkan pertandingan. Namun, pohon pencarian pada Five In Row memiliki kedalaman dan ruang lingkup percabangan yang luas, sehingga dibutuhkan waktu cukup lama untuk mengevaluasi seluruh kemungkinan. Untuk itulah dibutuhkan sebuah algoritma yang dapat mengoptimalkan pencarian, yaitu Alpha Beta Pruning. Algoritma ini akan memangkas beberapa percabangan pada pohon pencarian yang tidak mempengaruhi hasil evaluasi Minimax. Dengan adanya Alpha Beta Pruning maka ruang pencarian dapat dikurangi sehingga proses penelusuran dan evaluasi dapat dilakukan lebih cepat.

Kata Kunci : Algoritma Minimax, Alpha Beta Pruning, Five In row