Perbandingan game-playing agent dengan algoritma Monte Carlo Tree Search dan temporal difference Tree Search pada permainan 2048

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.