PENGAMBILAN KEPUTUSAN DENGAN ALGORITMA MINIMAX DALAM PERMAINAN “NIM”

Abstract

Permainan NIM merupakan permainan yang dapat melatih pengguna untuk belajar cara memenangkan permainan tanpa ada kata seri. Pemain secara bergantian mengambil biji pada papan NIM dan pemain yang mengambil biji terakhir memenangkan permainan. Tentunya akan sangat menarik untuk membangun sebuah aplikasi yang dapat memberikan perlawanan tangguh terhadap lawan mainnya.

Untuk menjadi lawan yang tangguh, komputer harus dapat memprediksi langkah yang akan diambil oleh komputer dan pemain. Salah satu algoritma yang dapat digunakan adalah algoritma Minimax. Algoritma Minimax yang digunakan akan men-generate tree kemungkinan langkah komputer, kemungkinan langkah pemakin dan kemungkinan langkah komputer setelah pemain bermain. Algoritma ini akan membentuk tree kemungkinan langkah sampai node paling dalam, kemudian diikuti dengan node selanjutnya. Setiap node akan diberi nilai untuk menjadi nilai pada node diatasnya dengan menerapkan prinsip min dan max.

Penulis telah menerapkan algoritma Minimax pada permainan NIM. Dari hasil penelitian yang dilakukan, penggunaan algoritma Minimax mampu memberikan perlawanan terbaik dengan tingkat kemenangan yang lebih besar dari peman. Akan tetapi, semakin bertambahnya jumlah baris dan jumlah biji, akan membutuhkan waktu yang lama dan tree yang panjang untuk menemukan langkah terbaik.