PENGEMBANGAN GAME CHINESE DARK CHESS DENGAN MENGGUNAKAN PARALLEL NONDETERMINISTIC MONTE CARLO TREE SEARCH (NMCTS)

Besarnya kompleksitas game tree (10207) pada game Chinese dark chess mengakibatkan tidak mungkin menelusuri game tree secara keseluruhan, sehingga membuat suatu fungsi evaluasi yang tepat menjadi permasalahan utama dalam game ini. Nondeterministic monte carlo tree search (NMCTS) merupakan monte carlo tree search (MCTS) dengan penambahan chance nodes. Fungsi evaluasi yang digunakan dalam NMCTS tidak memerlukan domain pengetahuan sehingga mempunyai keunggulan dibandingkan dengan alpha-beta search with chance nodes. Ada dua fungsi evaluasi yang dapat digunakan pada NMCTS dengan atau tanpa melihat pemain yang diwakilinya (max atau min), yaitu cumulative regret (CR) minimization dan simple regret (SR) minimization. NMCTS dapat dengan mudah diparallelkan menggunakan root parallelization, tree parallelization using local mutex menggunakan virtual loss dan tanpa virtual loss. Untuk menentukan metode yang paling optimal dari ketiga metode parallel NMCTS, maka diukur skalabilitas dari masing-masing metode berdasarkan playout speedup dan strength speedup. Playout speedup menunjukkan peningkatan rata-rata jumlah simulasi yang dapat dilakukan dalam satuan detik. Sedangkan strength speedup menunjukkan peningkatan persentase kemenangan game. Hasil pengujian aplikasi menunjukkan bahwa fungsi evaluasi SR+CR selalu melakukan simulasi yang lebih sedikit sehingga game tree yang terbentuk tidak lebih besar dibandingkan dengan CR dan selalu menghasilkan persentase kemenangan yang lebih besar dibandingkan dengan CR. Selain itu, tree parallelization NMCTS dengan menggunakan fungsi evaluasi SR+CR, 4 parallel task dan lamanya waktu melangkah 5 detik merupakan metode parallelization NMCTS yang paling optimal pada game Chinese dark chess dengan persentase kemenangan sebesar 42.5% .