Penerapan Algoritma Minimax pada Game Tic Tac Toe

Abstract

Algoritma minimax adalah algoritma yang digunakan untuk menentukan pilihan dengan memperkecil kemungkinan kehilangan nilai maksimal, hal ini dapat diartikan bahwa kemungkinan kekalahan akan diminimalkan dan kemenangan akan dimaksimalkan. Algoritma minimax dapat diterapkan dalam game berbasis papan permainan/board sehingga komputer akan berpikir seperti manusia dan memiliki kecerdasan buatan, seperti tic tac toe, catur, othello, dan lain lain. Game papan permainan/board yang akan diterapkan algoritma minimax ini adalah tic tac toe 4 x 4. Keuntungan dari penerapan algoritma minimax ini adalah mampu menganalisis segala kemungkinan posisi papan permainan/board untuk menghasilkan keputusan yang terbaik/bernilai maksimal karena algoritma minimax ini bekerja secara rekursif dengan mencari langkah yang akan membuat lawan mengalami kerugian minimum. Game akan lebih seru dan lebih menantang apabila diterapkan kecerdasan buatan melalui algoritma minimax ini. Game tic tac toe ini akan dirancang dengan 3 mode yaitu manusia vs manusia, manusia vs komputer yang memilih secara random, dan manusia vs komputer dengan diterapkan algoritma minimax. Hasil dari penerapan algoritma minimax pada game tic tac toe 4 x 4 untuk waktu eksekusi minimax atau waktu komputer mencari langkah terbaik sangat lama untuk 12 kotak kosong memerlukan waktu sampai 3 jam, ini belum 15 kotak kosong pasti akan lebih lama karena algoritma minimax mengecek semua kemungkinan pada papan permainan/board, berbeda dengan penerapan algoritma minimax pada game ic tac toe 3 x 3 untuk 9 kotak kosong menghasilkan waktu yang cepat sekitar 6 detik untuk komputer memilih Langkah terbaik. dapat disimpulkan bahwa algoritma minimax bergantung pada banyaknya jumlah papan permainan/board.