Analisis Efisiensi Algoritma Alpha Beta Pruning dan MTD(f) pada Connect4

Lukas Tommy(1*), Eza Budi Perkasa(2)

(1) 
(2) 
(*) Corresponding Author

Abstract


Komputer membutuhkan kecerdasan buatan/artificial intelligence agar dapat bermain selayaknya manusia pada Connect Four/Connect4. Terdapat beberapa algoritma yang dapat diterapkan pada Connect4, namun tidak diketahui mana yang cocok. Algoritma yang cocok berarti optimal dalam memilih langkah sekaligus waktu eksekusinya tidak lambat pada kedalaman pencarian/depth yang cukup dalam. Pada penelitian ini, akan dilakukan analisis dan perbandingan antara alpha beta (AB) Pruning dan MTD(f) pada prototipe Connect4, dalam hal keoptimalan (persentase kemenangan) dan kecepatan (waktu eksekusi dan jumlah simpul daun). Pengujian dilakukan dengan menjalankan mode komputer melawan komputer dengan kondisi berbeda. Persentase yang diraih MTD(f) berdasarkan pengujian adalah menang 41,67%, kalah 41,67% dan seri 16,66%. Pada pengujian dengan depth 8, waktu eksekusi MTD(f) 35,19% lebih cepat dan mengevaluasi simpul daun 66,2% lebih sedikit dibandingkan AB Pruning. Hasil dari penelitian ini adalah MTD(f) sama optimalnya dengan AB Pruning pada prototipe Connect4, namun MTD(f) secara rata-rata lebih cepat dan mengevaluasi simpul daun lebih sedikit dibandingkan AB Pruning. Waktu eksekusi MTD(f) tidak lambat dan jauh lebih cepat dibandingkan AB Pruning pada depth yang cukup dalam.

Keywords


Efisiensi Algoritma, Connect4, Artificial Intelligence, Alpha Beta Pruning, MTD(f)

Full Text:

PDF

References


Lestari, J. dan Winata, A. 2012, Implementasi Algoritma Minimax dengan Optimasi Alpha-Beta Pruning pada Aplikasi Permainan Connect Four, Prosiding Seminar Nasional Multidisiplin Ilmu (SeNMI), Jakarta, 8 Desember.

Sarhan, A.M., Shaout, A. dan Shock, M. 2009, Real - Time Connect 4 Game Using Artificial Intelligence, Journal of Computer Science, vol. 5, no. 4, hal. 283–289.

Handayani, M.S., Arisandi, D. dan Sitompul, O.S. 2012, Rancangan Permainan Othello Berbasis Android Menggunakan Algoritma Depth - First Search, Jurnal Dunia Teknologi Informasi, vol. 1, no. 1, hal. 28–34.

Siswanto, Laurentsia, dan Anif, M. 2014, Pengembangan Aplikasi Permainan Othello dengan Negamax Alpha Beta Pruning dan Brute Force, Seminar Nasional Sistem Informasi Indonesia (SESINDO), Surabaya, 22 September.

Millington, I. dan Funge, J. 2009, Artificial Intelligence for Games, Ed. 2. Morgan Kaufmann, Burlington.

Gunawan, Kristian, Y. dan Andika, H. 2009, Game Playing untuk Othello dengan Menggunakan Algoritma Negascout dan MTDF, Seminar Nasional Aplikasi Teknologi Informasi (SNATI), Yogyakarta, 20 Juni.

Plaat, A. 1997, Aske Plaat MTD(f) - a new chess algorithm, http://people.csail.mit.edu/plaat/mtdf.html, diakses tgl 29 Februari 2016.

Shibahara, K., Inui, N. and Kotani, Y. 2005, Adaptive Strategies of MTD-f for Actual Games, Proceedings of the 2005 Symposium on Computational Intelligence and Games (CIG05), Essex, April 4-6.

Stenmark, M. 2005, Synthesizing Board Evaluation Functions for Connect4 using Machine Learning Techniques, thesis, M.C.S. Department Computer Science, Østfold University College, Halden.

Rivest, R. L. 1988, Game Tree Searching by Min / Max Approximation, Artificial Intelligence, vol. 34, hal. 77–96.




DOI: https://doi.org/10.32736/sisfokom.v5i2.190

Refbacks

  • There are currently no refbacks.


Indexed By:

 


Creative Commons License
Jurnal Sisfokom (Sistem Informasi dan Komputer) has ISSN 2301-7988 and e-ISSN 2581-0588 which is published by Lembaga Penelitian dan Pengabdian Masyarakat (LPPM) ISB Atma Luhur under a Creative Commons Attribution-ShareAlike 4.0 International License.
Web Analytics Made Easy - StatCounter