Pengaruh Global Transposition Table dan Algoritma Pvs dan Negascout Pada Puzzle Games

Authors

DOI:

https://doi.org/10.33633/tc.v19i3.3422

Keywords:

Performance, GTT, Negascout, Strategy, Nine Men’s Morris

Abstract

Nine Men’s Morris merupakan game puzzle berbentuk board game 2 pemain. Papan terdiri dari kotak dengan dua puluh empat persimpangan atau titik. Permainan Nine Men’s Morris bersifat fully observable yang artinya bahwa seluruh kondisi pada papan permainan dan bidak-bidak dapat dipersepsi dan dinilai dengan baik. Penelitian ini melihat pengaruh penggunaan algoritma-algoritma dalam performa game Nine Men’s Morris. Performa permainan dilihat dari kemenangan, panjang jumlah jalur, lama pencarian. Penggunaan Global Transposition Table (GTT) sebagai penyimpanan memiliki keunggulan – dimana penyimpanannya lebih banyak sehingga memberikan ruang penelusuran lebih besar. Kemampuan ini disebabkan karena sifat GTT yang paralel. Dengan GTT ini diharapkan mampu menemukan solusi lebih cepat. Global Transposition Table sendiri adalah kumpulan dari beberapa tabel transposisi di dalam sebuah tabel transposisi lebih besar. GTT dapat diibaratkan seperti folder yang memiliki banyak subfolder dengan setiap subfolder berisi tipe file yang sama, dan memiliki nama depan file yang sama. Maka dengan menggabungkan Algoritma pencaria dan penggunakan GTT dalam permaian Nine Man’s Morris ini diharapkan dapat mengetahui performa dari penggunaan Algoritma Negascout dan juga pengaruh tambahan dari penggunaan GTT dalam game puzzle Nine Men’s Morris.

Author Biography

Ali Mustopa, Universitas Amikom Yogyakarta

Prodi Sistem Informasi, Direktorat BPC (Career Center)

References

Petcu, S.A., Holban, S., 2008, Nine Men’s Morris: evaluation functions. In: International Conferencs on Development and Application Systems, Mei 22-24

Gasser, Ralph. 1998. Solving Nine Men's Morris. Nowakowski, R., & Mathematical Sciences Research Institute, Games of No Chance. Cambridge University Press. Berkeley

Santoso, Kevin Alan Kurniawan. 2018. Membangun Game “NINE MEN’S MORRIS” dengan kecerdasan buatan. Fakultas Ilmu Komputer, Universitas AMIKOM, Yogyakarta

David. 2013, Perbandingan Algoritma Minimax Dan Negascout Pada Permainan Catur Sederhana. Informatika Mulawarman: Jurnal Ilmiah Ilmu Komputer, Vol 8, No 2 hal. 29-33. http://e-journals.unmul.ac.id/index.php/JIM/article/view/193/pdf

Kevin Winata. 2012, “Penerapan Algoritma Alpha Beta Pruning pada Permainan Nine Men’s Morris.” https://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2012-2013/Makalah2012/Makalah-IF3051-2012-061.pdf, diakses 20 Juni 2019

Elnaggar, Ahmed & Gadallah, Mahmoud & Mostafa, Mostafa & Eldeeb, Hesham. 2014. A Comparative Study of Game Tree Searching Methods. International Journal of Advanced Computer Science and Applications. Vol 5. No 5. 68-77.

Beal, D. F., & Smith, M. C. (1996). Multiple probes of transposition tables. ICGA Journal, vol 19 no 4, 227-233.

A. Kishimoto, A. Fukunaga, and A. Botea, 2013. “Evaluation of a simple, scalable, parallel best-first search strategy,” Artif. Intell., vol. 195, 222–248, 2013

Loewer, Wesley. 2016. The Effects of Rule Variations on Perfect Play Databases for Nine Men's Morris. https://www.researchgate.net/profile/Wesley_Loewer/publication/305413042_The_Effects_of_Rule_Variations_on_Perfect_Play_Databases_for_Nine_Men's_Morris/links/578e374608ae35e97c3f6570/The-Effects-of-Rule-Variations-on-Perfect-Play-Databases-for-Nine-Mens-Morris.pdf, diakses tgl 27 Mei 2020

J. W. Romein, H. E. Bal, J. Schaeffer and A. Plaat, "A performance analysis of transposition-table-driven work scheduling in distributed search," , IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 5, hal. 447-459, Mei 2002,.

Downloads

Published

2020-08-28

Issue

Vol. 19 No. 3 (2020): Agustus 2020

Section

Articles

License

Copyright (c) 2020 Ali Mustopa

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

 

License Terms

All articles published in Techno.COM Journal are licensed under the Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0). This means:

1. Attribution

Readers and users are free to:

  • Share – Copy and redistribute the material in any medium or format.

  • Adapt – Remix, transform, and build upon the material.

As long as proper credit is given to the original work by citing the author(s) and the journal.

2. Non-Commercial Use

  • The material cannot be used for commercial purposes.

  • Commercial use includes selling the content, using it in commercial advertising, or integrating it into products/services for profit.

3. Rights of Authors

  • Authors retain copyright and grant Techno.COM Journal the right to publish the article.

  • Authors can distribute their work (e.g., in institutional repositories or personal websites) with proper acknowledgment of the journal.

4. No Additional Restrictions

  • The journal cannot apply legal terms or technological measures that restrict others from using the material in ways allowed by the license.

5. Disclaimer

  • The journal is not responsible for how the published content is used by third parties.

  • The opinions expressed in the articles are solely those of the authors.

For more details, visit the Creative Commons License Page:
? https://creativecommons.org/licenses/by-nc/4.0/

 

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.