Abstract
Pada permainan Ntil, jumlah seluruh kombinasi langkah bidak yang mungkin terjadi sangat banyak. Dari keseluruhan langkah tersebut, terdapat langkah yang akan merugikan pemain, dan terdapat langkah yang akan menguntungkan pemain. Berdasarkan hal ini, maka dibutuhkan sebuah algoritma untuk menentukan langkah yang akan menguntungkan pemain atau agen dari kumpulan langkah yang ada. Skripsi ini membahas mengenai implementasi algoritma Minimax, dan Algoritma Alpha-beta Pruning untuk pencarian langkah terbaik yang akan diambil oleh agen cerdas dalam permainan Ntil. Algoritma Minimax akan memaksimalkan langkah agen dan meminimalkan langkah lawan dari agen. Algoritma Alpha-beta Pruning merupakan optimasi dari algoritma Minimax, yang akan mengurangi jumlah simpul yang dievaluasi dalam pohon pencarian. Pohon pencarian dibangkitkan dengan mengambil semua kemungkinan langkah bidak pada permainan Ntil. Algoritma Minimax dan Alpha-beta Pruning dapat diimplementasikan untuk pencarian langkah terbaik yang akan diambil oleh agen dalam permainan Ntil. Pencarian langkah terbaik dengan menggunakan algoritma Minimax menghasilkan langkah yang sama dengan algoritma Alpha-beta Pruning. Algoritma Alpha-beta Pruning memiliki kinerja yang lebih baik dibandingkan algoritma Minimax dengan rata-rata perbedaan running time sebesar 1354.367 ms terhadap nilai depth, dan 65.9776 ms terhadap ukuran papan permainan.
