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

Authors

  • Lukas Tommy
  • Eza Budi Perkasa

DOI:

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

Keywords:

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

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.

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.

Downloads

Published

2016-10-01

Issue

Vol. 5 No. 2 (2016): September

Section

Articles

License

The copyright of the article that accepted for publication shall be assigned to Jurnal Sisfokom (Sistem Informasi dan Komputer) and LPPM ISB Atma Luhur as the publisher of the journal. Copyright includes the right to reproduce and deliver the article in all form and media, including reprints, photographs, microfilms, and any other similar reproductions, as well as translations.

Jurnal Sisfokom (Sistem Informasi dan Komputer), LPPM ISB Atma Luhur, and the Editors make every effort to ensure that no wrong or misleading data, opinions or statements be published in the journal. In any way, the contents of the articles and advertisements published in Jurnal Sisfokom (Sistem Informasi dan Komputer) are the sole and exclusive responsibility of their respective authors.

Jurnal Sisfokom (Sistem Informasi dan Komputer) has full publishing rights to the published articles. Authors are allowed to distribute articles that have been published by sharing the link or DOI of the article. Authors are allowed to use their articles for legal purposes deemed necessary without the written permission of the journal with the initial publication notification from the Jurnal Sisfokom (Sistem Informasi dan Komputer).

The Copyright Transfer Form can be downloaded [Copyright Transfer Form Jurnal Sisfokom (Sistem Informasi dan Komputer).

This agreement is to be signed by at least one of the authors who have obtained the assent of the co-author(s). After submission of this agreement signed by the corresponding author, changes of authorship or in the order of the authors listed will not be accepted. The copyright form should be signed originally, and send it to the Editorial in the form of scanned document to sisfokom@atmaluhur.ac.id.