Sebagai gantinya, kali ini saya nulis yang agak pendek aja, yaitu tentang aplikasi N-Gram pada game. Yap, sesuai judulnya, N-Gram ini kalau di dalam game biasanya digunakan untuk action prediction. Contohnya ya pada game2x fighting, di mana si AI akan memprediksi gerakan selanjutnya dari player. Bagaimana cara si AI memprediksi pergerakan lawan? Akan kita bahas…
Atau implementasi yang lain lagi yaitu untuk check bahasa yang digunakan dalam suatu artikel. Misalnya kita dapat mengetahui sebuah artikel itu menggunakan bahasa inggris dengan menggunakan N-Gram, karena dalam bahasa inggris kata yang paling sering muncul adalah kata ‘the’, maka jika ternyata artikel tsb data/kata yang paling sering muncul adalah ‘the’ juga, berarti artikel tsb menggunakan bahasa inggris.
Itu, contoh simpel aja sih, jelas masih perlu analisis2x lain yang diperlukan untuk mendukung keakuratannya. Dan sudah jelas saya juga ga ngerti untuk urusan yang kayak begituan. Jadi ya sekali lagi, googel aja kalo mau tau lebih lanjut.
Nah kalo diimplementasikan ke dalam game, ga jauh beda juga sih, kita juga akan mengekstraksi data dari player, deteksi pattern + frequensi nya, trus memprediksi aksi player selanjutnya.
Untuk memprediksi, kita bisa ambil 2 sampel terakhir yaitu RS, tinggal kita liat aja dari sequence tsb pola yang diawali oleh RS ada apa saja dan berapa jumlahnya. Dari data kita peroleh ada RSR dengan 2 kemunculan dan RSS dengan 1 kali kemunculan. Kemudian kita ambil saja yang punya frequensi paling tinggi yaitu RSR, berarti si AI akan memprediksi bahwa si Player akan mengeluarkan R(Rock) untuk aksi selanjutnya.
Nah, 2 sampel itu yang disebut dengan window. Window size sendiri selalu bernilai n-1. Jadi untuk 3-Gram maka window size nya adalah 2, sementara untuk 4-Gram window sizenya 3, dan seterusnya.
Kalau sudah didapat key nya, seperti yang sudah dibahas sebelumnya, kita bisa memprediksi aksi selanjutnya dengan mencocokkan window terakhir dengan key yang ada. Kalau ada yang cocok, ambil dan cari yang punya frequensi paling tinggi. Dan itu lah prediksi akhirnya.
Mengutip dari bukunya Ian Millington & John Funge, memperbesar window size pada awalnya akan memperakurat prediksi yang dilakukan, namun juga jika semakin besar akan menurunkan keakuratan prediksi. Bingung? lebih jelasnya mending liat gambar:
Diagram di atas diambil dari hasil eksperimen mereka, yang melakukan 1000 kali trials pada game Left or Right. Akurasi akan optimal jika nilai N nya antara 2 s/d 9. Selebihnya nilai akurasinya justru malah dibawah jika kita melakukan random.
Di bukunya mereka ada alasannya sih sebenernya kenapa bisa terjadi fenomena tsb, cm lagi2x saya males untuk ngejelasinnya…
Dan juga jika nilai N nya besar, maka pembentukan pattern juga akan menjadi lebih lama karena kombinasi pattern nya lebih banyak, sehingga akhirnya proses untuk menuju prediksi yang optimal juga menjadi lebih lambat.
Kayanya sudah cukup jelas nih, yaitu prediksi akan menajdi lebih akurat jika AI menyimpan banyak data dari hasil aksi seorang player. Jadi AI yang menyimpan 1000 data aksi player tentu prediksinya akan lebih akurat dibanding yang hanya menyimpan 100 data.
Kali ini saya gak akan membuat diagram classnya terlebih dahulu karena memang hanya ada 2 class untuk N-Gram nya dan 1 Main Class.
8: nLength, sperti yang sudah dijelaskan, untuk menentukan window size dan juga nilai N untuk melakukan pemecahan data
11: Constructor, akan melakukan checking apakah nilai nLength dan maxData kurang dari 1 atau tidak, jika ya, throw an Error.
Isinya juga kurang lebih sama, yaitu cek jika sudah mencapai nilai max, jika ya hapus dulu data paling awal sampai dengan index tertentu, baru masukkan data yang baru.
50: Method generateNGram(), method yang akan digunakan untuk membentuk suatu Array yang berisi KeyData2x yang unik dan sudah dihitung frequensinya. Untuk detailnya akan dijabarkan lebih lanjut:
53: nGramFreq, nah ini dia array yang saya sebutkan di atas, ini nanti akan di return oleh method generateNGram()
52: nGramList, array yang menyimpan pattern2x hasil ekstraksi dari data, bedanya dengan nGramFreq yaitu di sini data tidak unik dan tentu saja belum dihitung frequensinya.
56: dataLength, index yang digunakan untuk menentukan sampai di mana loop berakhir. Karena data dibagi sesuai dengan nilai nLength, maka tentu saja index terakhir dari loop adalah dataLength-(nLength-1). Kenapa ada –1, karena index dimulai dari 0.
Jadi misal datanya adalah PRPPPRPSPR, dengan nLength=3, maka index terakhirnya adalah pada index ke 6 atau 3 dari belakang yaitu data dengan value S.
Dengan begitu maka akan didapatkan pattern yang mempunyai length yang sama dengan nilai nLength, yaitu dengan length 3. Dengan pattern terakhir yaitu SPR.
100: LastData, array untuk menyimpan sampel terakhir dari data yang akan diprediksi, bagi yang lupa, sampel adalah n-1 data terakhir dari sebuah sequence, misal RRPSPPP dengan nLength 3 maka LastData nya adalah PP.
102: cek jika panjang data kurang dari nilai nLength, return null, karena sampel data tidak memungkinkan untuk dilakukan prediksi
Untuk membantu, dibuat temporary array dengan nama nGramArrayPattern, yang juga menangkap n-1 data dari KeyData yang tersimpan di nGramArray, sehingga bisa dicocokkan dengan pattern pada lastData.
Karena data yang diprediksi adalah data terakhir pada bestAction, maka kita melakukan slicing dari index array ke-key.length – 1, misal panjang Key 3: RRP, maka data yang diambil adalah data dengan index –> length(3) – 1 = 2, yaitu P.
Kalau code nya dipersingkat + dibikin lebih efisien kayanya masih bisa, tapi untuk sementara gini dulu deh. Silahkan saja kalau ada yang mau memperbaiki...
Dan juga harus gw akui implementasi N-Gram yang saya buat ini juga gak efisien karena setiap akan memprediksi, AI akan melakukan step2x dari awal lagi dari membuat potongan pattern, meng-generate N-Gram nya dan seterusnya.
Padahal kalau diamati, untuk memotong2x data, kita bisa melakukan pemotongan data untuk data yang baru dimasukkan, jadi tidak perlu mengulang prosesnya dari awal lagi. Dan juga untuk data N-Gram nya kita bisa saja pakai yang sudah ada. Jika ada data baru, jika dia sudah ada dalam N-Gram berarti cukup tambahkan frequensinya saja, dan jika belum ada tinggal memasukkan key baru. Dengan begitu proses pada tiap prediksi gak akan terlalu berat, terutama ketika jumlah trial juga sudah cukup banyak & data yang diproses juga sudah terlalu besar.
Kalau dilihat ya cuma if-else doank. If dia memprediksi player akan mengeluarkan R maka dia akan mengeluarkan aksi P, dan seterusnya. Kalau prediksinya masih null, dia akan melakukan random throw.