Kombinasi Algoritma MCTS dengan Alpha Beta Pruning dan Rhea untuk Ataxx

Abstract

Gim adalah sebuah aktivitas yang dilakukan untuk mencari kesenangan dan dibatasi dengan adanya suatu aturan tertentu. Pada dasarnya gim dilakukan dengan adanya persaingan antara pemain-pemain dalam gim tersebut, di mana pemain-pemain tersebut merupakan orang. Namun, seiring perkembangan zaman, gim juga bisa dilakukan pada perangkat-perangkat elektronik. Mengikuti perkembangan zaman terhadap gim tersebut, pemain gim sekarang juga bisa berupa komputer yang disebut agen atau Game Playing Agent (GPA). Contoh dari GPA yang sudah terbukti memiliki performa yang cukup bagus adalah Deep Blue (pada permainan catur) dan AlphaGo (Pada permainan Go). Namun GPA tersebut hanya dapat menunjukkan performa yang bagus saat bermain gim tertentu saja. Sehingga dari pemikiran tersebut dikembangkan istilah yang bernama General Game Playing (GGP), yaitu agen yang dapat memainkan lebih dari satu gim dengan performa yang bagus. Dalam pengembangan GGP, terdapat juga pengembangan general game system, yaitu perangkat lunak yang dapat menjalankan gim secara umum. Salah satu general game system adalah Ludii. Ludii diciptakan untuk dapat menjalankan berbagai macam gim strategi tradisional dunia. Hal tersebut dicapai dengan menggunakan Game Description Language (GDL) miliknya yang bernama Ludii Game Description Language (L-GDL). Salah satu gim yang dimodelkan oleh Ludii adalah gim Ataxx. Ludii juga sudah menyediakan agen yang bisa digunakan untuk bermain gim. Salah satu dari agen tersebut adalah agen yang menggunakan algoritma yang akan dibuat pada penelitian ini yaitu Monte Carlo Tree Search (MCTS). MCTS adalah algoritma yang digunakan untuk mengambil keputusan dengan melakukan pencarian pada ruang kombinatorial yang dilambangkan oleh tree. Namun untuk permainan Ataxx, algoritma MCTS murni tidak memberikan performa yang cukup bagus dalam memainkan permainan tersebut. Sehingga diperlukan adanya variasi tambahan terhadap algoritma tersebut. Modifikasi yang akan digunakan pada penelitian ini adalah modifikasi dengan algoritma Alpha Beta Pruning dan Rolling Horizon Evolutionary Algorithm (RHEA). Kedua agen yang akan dibuat tersebut akan diuji dengan agen yang sudah terdapat pada sistem Ludii. Berdasarkan hasil dari eksperimen, salah satu variasi algoritma MCTS yaitu MCTS-Solver, yang digabung dengan algoritma Alpha-Beta serta menggunakan algoritma Secure Child sebagai pemilihan langkah terakhir, mendapatkan persentase kemenangan sebesar 87% melawan agen One-Ply (No Heuristic). Sementara untuk agen RHEA persentase kemenangan tertinggi melawan agen One-Ply (No Heuristic) adalah 60% dengan hyperparameter tertentu.