Abstract:
2048 adalah permainan video open-source yang viral pada tahun 2014. Daya tarik permainan
tersebut terdapat pada mekanismenya yang sederhana, namun cukup menantang untuk dimainkan
oleh pemain manusia. Sudah banyak model game-playing agent (GPA) yang dibuat untuk
memainkan permainan tersebut secara otomatis. Berbagai GPA tersebut mengimplementasikan
algoritma yang berbeda-beda sehingga memiliki tingkat keberhasilan yang bervariasi pula. Salah
satu algoritma yang pernah diimplementasikan menjadi GPA untuk 2048 adalah algoritma Monte
Carlo Tree Search (MCTS). Meskipun begitu, potensi MCTS dalam memainkan permainan tersebut
belum sepenuhnya terealisasikan sebab MCTS memiliki banyak varian dan modifikasi yang
dapat meningkatkan performa agen. Salah satu modifikasinya adalah dengan menggabungkan
MCTS dengan temporal-difference learning (TD-Learning) sehingga menghasilkan algoritma
Temporal Difference Tree Search (TDTS).
Pada penelitian ini, akan dibangun perangkat lunak permainan 2048 dan GPA dengan
algoritma MCTS dan TDTS menggunakan bahasa pemrograman Java. Secara spesifik, varian
algoritma yang digunakan adalah UCT dan Sarsa-UCT(λ), di mana UCT adalah varian MCTS
yang memakai selection policy UCB1 dan Sarsa-UCT(λ) adalah varian TDTS yang dihasilkan
dengan menggabungkan TD-Learning dengan algoritma UCT. Dilakukan berbagai analisis
terhadap kedua algoritma tersebut untuk menerapkannya pada permainan 2048. Kemudian,
sejumlah eksperimen dilakukan untuk mencari konfigurasi parameter optimum untuk kedua
algoritma tersebut. Lalu, performa keduanya dibandingkan dan dianalisis.
Hasil eksperimen menunjukkan bahwa, pada konfigurasi optimumnya masing-masing, algoritma
Sarsa-UCT(λ) memiliki performa yang setidaknya sama baiknya dengan algoritma UCT
pada permainan 2048. Bahkan, jika anggaran komputasi yang tersedia sangat sedikit, algoritma
Sarsa-UCT(λ) cenderung menghasilkan rata-rata skor yang lebih tinggi daripada algoritma UCT.
Di sisi lain, skor yang dicapai oleh algoritma Sarsa-UCT(λ) tampak lebih fluktuatif daripada
UCT sehingga Sarsa-UCT(λ) lebih sering menghasilkan skor yang lebih tinggi, namun lebih
sering juga menghasilkan yang lebih rendah dari UCT. Selain itu, ditemukan bahwa beberapa
nilai parameter optimal dari algoritma UCT dan Sarsa-UCT(λ) seperti konstanta eksplorasi,
reward discount rate, dan eligibility trace decay rate memiliki korelasi positif dengan jumlah
anggaran komputasi yang tersedia.
