ActionScript 3.0: N-Gram Prediction

Hmm, setelah beberapa bulan gak ada postingan baru, sebenernya ada sih, mau ngebahas ttg Fuzzy Logic, tapi setelah nulis beberapa paragraph, tiba2x males karena kyknya bakal lumayan panjang, jadi akhirnya gw simpen dulu aja.

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…

predict



1. Pertama-tama 
Seperti biasa, sebelumnya kita basa-basi dulu…

Apa itu N-Gram? Nyari sendiri aja di google… 

Hehehe, serius, gw gak akan jelasin panjang lebar tentang N-Gram di sini. Yang jelas intinya sih N-Gram itu mengekstrak data2x yang unik  dan menghitung frequensi kemunculannya pada sekumpulan data.

Biasanya digunakan untuk mengetahui 2 atau lebih artikel/tulisan itu mirip atau tidak. Dengan membandingkan hasil ekstraksi data/kata dan frequensi dari kedua atau lebih artikel tsb.
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.


2. The idea
Misal kita ambil kasus pada game RPS(Rock-Paper-Scissors) yang kebetulan sudah gw buat sampelnya juga. Yang simpel2x dulu aja, kalo disuruh buat game fighting, gw bisa muntah darah. Tapi intinya ga jauh2x beda sih, yang jelas kalo untuk game fighting bisa lebih kompleks.
doramon

 Di game tsb kan ada 3 aksi yaitu: Rock, Paper, dan Scissor, nah ketika seorang player bermain, otomatis akan terbentuk suatu sequence. Misal dalam 10 kali throw, akan terbentuk sequence seperti ini: RSRSRSSPRS. Sequence inilah yang akan digunakan oleh AI untuk memprediksi aksi berikutnya dari si player.

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.
Sementara ‘N’ itu sendiri yang digunakan untuk membagi2x sequence tadi, misal n=3, berarti data akan dibagi menjadi: RSR, SRS, RSR, SRS, RSS, SSP, SPR, PRS. Setelah dibagi sesuai nilai n nya, tinggal kita hitung frequensinya:
  • RSR = 2
  • SRS = 2
  • RSS = 1
  • SSP = 1
  • SPR = 1
  • PRS = 1
Tiap data yang telah dibagi dan dihitung frequensinya tsb dinamakan Key.
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.


3. Before We Start
Masih ada dikit lagi sebelum masuk ke code…
.Chili-Fuu

Window Size
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:
ngram

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…

Sequence Length
Intinya, pada awal2x prediksi tidak akan pernah akurat, karena semua possible pattern belum terbentuk, atau mereka mempunyai frequensi yang masih terlalu kecil dan juga nilainya masih sama satu sama lain.

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.

Memory
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.

Hanya saja, tentu drawbacknya akan berpengaruh kepada performa game itu sendiri, gamenya mnjd lebih lambat, memakan memory lebih besar, hang ketika si AI melakukan prediksi, dsb.


4. Into the Code
Kali ini saya gak akan membuat diagram classnya terlebih dahulu karena memang hanya ada 2 class untuk N-Gram nya dan 1 Main Class. 

Sebelumnya, data dalam N-Gram ini bisa direpresentasikan menjadi berupa String, yang RLRLRRRLR tadi kan berupa string dan operasi motong2x string juga udah ada di AS3.0. Namun mnurut saya kok kurang fleksibel terutama kalo data nya udah berupa kata2x misal: “kick”, “punch”, “block” atau berupa integer/number dan tipe data lain. Bisa aja sih pake string tapi kok kayanya malah jadi tambah ribet.

Jadi di sini saya pake Array saja biar enak.

Class KeyData
package com.pzuh.ngram
{
 public class KeyData 
 {
  private var key:Array;
  private var count:int;
  
  public function KeyData(key:Array, count:int) 
  {
   this.key = key;
   this.count = count;
  } 
  
  public function increaseCount():void
  {
   count += 1;
  }
  
  public function removeSelf():void
  {
   for (var i:int = key.length - 1; i > 0; i--)
   {
    key.splice(i, 1);
   }
   
   key.length = 0;
   key = null;
  }
  
  public function getKey():Array
  {
   return key;
  }
  
  public function getCount():int
  {
   return count;
  }
 }
}
 
5: Key, Array untuk menyimpan key

6: Count, menyimpan frequensi kemunculan key tsb
Selebihnya ga perlu saya jelasin karena sudah cukup jelas, dan ga ada operasi yang aneh2x…


Class NGramPredictor
package com.pzuh.ngram
{
 import com.pzuh.Basic;
 
 public class nGramPredictor
 {
  private var data:Array = new Array();
  private var nLength:int;
  private var maxDataNum:int; 
  
  public function nGramPredictor(nLength:int = 4, maxDataNum:int = 1000)
  {
   if ((nLength < 1) || (maxDataNum < 1))
   {
    throw new Error("ERROR: Either nLength and maxData value must be no less than 1");
    return;
   }
   
   this.nLength = nLength;   
   this.maxDataNum = maxDataNum;
  }
  
  public function addSingleData(data:*):void
  {
   if (this.data.length + 1 > maxDataNum) 
   {
    this.data.shift();
   }
   
   this.data.push(data);
  }
  
  public function addMultipleData(data:Array):void
  {
   if (this.data.length + data.length > maxDataNum)
   {
    if (this.data.length < 1) 
    {
     data.splice(0, data.length - maxDataNum);
    }
    else
    {
     this.data.splice(0, data.length);
    }
   }
   
   this.data = this.data.concat(data);
  }
  
  private function generateNGram():Array
  {
   var nGramList:Array = new Array();
   var nGramFreq:Array = new Array();
   
   //extract the data and store them to nGramList array
   var dataLength:int = data.length - (nLength - 1);
   
   for (var dataIndex:int = 0; dataIndex < dataLength; dataIndex++)
   {
    var tempData:Array = data.slice(dataIndex, dataIndex + nLength);    
    nGramList.push(tempData);
    
    //trace("nGramList: " + nGramList[dataIndex]);
   }
   
   //remove duplicate & store to a new array
   var tempArray:Array = Basic.getUniqueArray(nGramList, true);
   
   //create new KeyData from tempArray and store them to nGramFreq array
   var tempArrayLength:int = tempArray.length;
   
   for (var tempIndex:int = 0; tempIndex < tempArrayLength; tempIndex++)
   {
    nGramFreq.push(new KeyData(tempArray[tempIndex], 0));
   }
   
   //count the frequency of each key
   var nGramFreqLength:int = nGramFreq.length;
   var nGramListLength:int = nGramList.length;
   
   for (var i:int = 0; i < nGramFreqLength; i++)
   {
    for (var j:int = 0; j < nGramListLength; j++)
    {
     if (nGramFreq[i].getKey().toString() == nGramList[j].toString())
     {
      nGramFreq[i].increaseCount();
     }
    }
   }   
   
   return nGramFreq;
  }
  
  public function getNextAction():*
  {
   var nGramArray:Array = new Array();
   var actionArray:Array = new Array();
   var bestAction:KeyData;
   var lastData:Array;
   
   if (data.length < nLength)
   {
    return null;
   }
   
   nGramArray = generateNGram();
   
   //get last data pattern
   lastData = data.slice(data.length - (nLength - 1));
   //trace("Last Data: " + lastData);
   
   //insert matching pattern to actionArray
   var nGramLength:int = nGramArray.length;
   
   for (var i:int = 0; i < nGramLength; i++)
   {
    //trace("nGram Key: " + nGramArray[i].getKey() + " || count: " + nGramArray[i].getCount());
    
    var nGramArrayPattern:Array;
    
    nGramArrayPattern = nGramArray[i].getKey().slice(0, nGramArray[i].getKey().length - 1);
    
    if (nGramArrayPattern.toString() == lastData.toString())
    {
     actionArray.push(nGramArray[i]);
    }
   }
   
   //get most frequent pattern from actionArray
   for (var j:int = 0; j < actionArray.length; j++)
   {
    //trace("Action Array: " + actionArray[j].getKey() + " || count: " + actionArray[j].getCount());
    
    if (bestAction == null)
    {
     bestAction = actionArray[j];
    }
    else
    {
     if (bestAction.getCount() < actionArray[j].getCount())
     {
      bestAction = actionArray[j];
     }
     else if (bestAction.getCount() == actionArray[j].getCount())
     {
      var rand:int = Basic.generateRandomSign();
      
      if (rand < 0)
      {
       bestAction = actionArray[j];
      }
     }
    }
   }  
   
   //return the final predicted action
   var predictedAction:Array = new Array();
   
   if (bestAction != null)
   {
    predictedAction = bestAction.getKey().slice(bestAction.getKey().length - 1);
   }
   else
   {
    predictedAction[0] = null;
   }
   
   return predictedAction[0];
  }
  
  public function removeSelf():void
  {
   for (var i:int = data.length - 1; i > 0; i--)
   {
    data.splice(i, 1);
   }
   
   data.length = 0;   
   data = null;
  }
  
  public function setNLength(nLength:int):void
  {
   if (nLength > 0)
   {
    this.nLength = nLength;
   }
  }
  
  public function setMaxDataNum(num:int):void
  {
   if (num > 0)
   {
    maxDataNum = num;
   }
  }
  
  public function getNLength():int
  {
   return nLength;
  }
  
  public function getMaxDataNum():int
  {
   return maxDataNum;
  }
 }
}

7: data, Array untuk menyimpan data mentah input dari Player

8: nLength, sperti yang sudah dijelaskan, untuk menentukan window size dan juga nilai N untuk melakukan pemecahan data

9: maxDataNum, fixed value untuk menentukan jumlah maximum data yang dapat disimpan oleh AI

==================================================================
11: Constructor, akan melakukan checking apakah nilai nLength dan maxData kurang dari 1 atau tidak, jika ya, throw an Error.
Selebihnya, cukup jelas

------------------------------------------------------------------------------------------------------------------------------------
23: Method addSingleData(), digunakan untuk memasukkan data tunggal. Terdapat checking nilai max data, jika melebihi maka data yang paling awal akan dihapus, baru kemudian dimasukkan data yang baru. Untuk memasukkan data cukup dengan addSingleData(“data”)

------------------------------------------------------------------------------------------------------------------------------------
33: Method addMultipleData(), digunakan juga untuk memasukkan data, namun untuk data yang jumlahnya 1 atau lebih. Untuk memasukkan data juga tdk seperti pd method sebelumnya karena parameter yang digunakan adalah berupa array jadi harus seperti ini ketika memasukkan data: addMultipleData([“data1”, ”data2, “data3”]).

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.

----------------------------------------------------------
54: Proses ekstrak pattern dari data ke nGramList

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.

60: tempData, hanya sekedar temporary Array yang digunakan untuk menyimpan hasil potongan2x data tsb sebelum dimasukkan ke nGramList.

Untuk motong datanya, karena berupa array, jadi bisa pake method slice(startIndex, endIndex). Untuk lebih jelasnya tentang method slice ini silakan ke Dokumentasinya AS3.0

endIndex bernilai dataIndex + nLength, gw rasa cukup jelas ya, misal dari index 0 dengan nLength 3 berarti endIndex nya 3.

----------------------------------------------------------
66: Proses menghilangkan pattern yang redundant dan juga memasukkannya ke nGramFreq array

67: tempArray, array yang akan menyimpan pattern2x yang unik yang dari array nGramList. Berhubung itu saya pake bantuan dari salah satu method custom class saya, yaitu method getUniqueArray(), jadi ya ga keliatan prosesnya di sini.  Tapi intinya sih ya cuma menghilangkan data2x duplikat.

72: selanjutnya tinggal ngeloop lagi dan masukkin ke nGramFreq array. Yang perlu dicatat di sini, ketika memasukkan pattern ke nGramFreq array, yang dimasukkan bukan sekedar data dalam tempArray saja, melainkan kita buat sebuah KeyData baru dan memasukkan nilai dalam tempArray ke parameter key di constructornya, serta menentukan nilai frequensi/countnya. Berhubung penghitungan frequensi akan dilakukan pada tahap selanjutnya, maka nilai awal yang dimasukkan ke nilai count pada KeyData tsb adalah 0.

----------------------------------------------------------
77: menghitung frequensi tiap KeyData

81: cukup dengan nested loop antara nGramFreq dan nGramList. Jika sebuah key di nGramFreq ditemukan di nGramList, tambahkan nilai count/frequensinya dengan memanggil method increaseCount()

92: return array nGramFreq

------------------------------------------------------------------------------------------------------------------------------------
93: Method getNextAction(), method yang akan mengembalikan nilai dari hasil prediksi

97: nGramArray, array untuk menyimpan KeyData

98: ActionArray, array untuk menyimpan KeyData2x yang cocok dengan sampel yang diambil

99: BestAction, array untuk menyimpan KeyData yang cocok dengan sampel yang diambil dan juga mempunyai nilai count atau frequensi paling tinggi

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

107: generate nGram dengan memanggil method generateNGram() dan masukkan ke dalam array nGramArray
-
---------------------------------------------------------
114: Cek pattern dari lastData dan nGramArray, jika cocok masukkan ke dalam actionArray

116: Loop nGramArray
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.

----------------------------------------------------------
131: Loop actionArray tadi, dan KeyData yang mempunyai nilai count tertinggi masukkan ke dalam bestAction. Jika ternyata ada KeyData2x tsb punya nilai count yang sama, maka bisa dirandom saja.

----------------------------------------------------------
158: mengembalikan nilai hasil prediksi

Dibuat lagi temporary array yang bernama predicted action. Kenapa array, karena akan ada pemanggilan method slice() terhadap array Key pada KeyData yang tersimpan di bestAction, method tsb mengembalikan nilai berupa array, jadi ya harus ditangkap dengan array juga.

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.
169: selanjutnya tinggal di-return

------------------------------------------------------------------------------------------------------------------------------------
method selanjutnya hanya removeSelf & getter-setter jadi gak perlu dijabarkan lagi

------------------------------------------------------------------------------------------------------------------------------------
Akhirnya…

Kira-kira ya seperti itu lah…. maaf kalo bikin puyeng + kodingannya terlalu bertele2x…. 
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.

Akan tetapi, karena saya udah puyeng pas coba2x bikin sistem yang seperti itu, udah jalan dikit sih sebenernya, tapi bug nya gila2xan, tambal sini, bocor situ, jadi ya utk sementara gw pending dulu dan diputuskan untuk pakai yang sudah ada ini.


Class MainClass
package src 
{
 import com.pzuh.ngram.nGramPredictor;
 import com.pzuh.Basic;
 
 import flash.display.*;
 import flash.events.*;
 
 public class MainClass extends MovieClip 
 {
  private var playerScore:int = 0;
  private var comScore:int = 0;
  private var tieScore:int = 0;
  
  private var myCom:nGramPredictor = new nGramPredictor(4, 50);
  
  public static const ROCK:String = "R";
  public static const PAPER:String = "P";
  public static const SCISSORS:String = "S";
  
  public function MainClass() 
  {
   rockx.addEventListener(MouseEvent.CLICK, buttonClicked, false, 0, true);
   paperx.addEventListener(MouseEvent.CLICK, buttonClicked, false, 0, true);
   scissorsx.addEventListener(MouseEvent.CLICK, buttonClicked, false, 0, true);
   randomx.addEventListener(MouseEvent.CLICK, buttonClicked, false, 0, true);
   nLengthSliderx.addEventListener(Event.CHANGE, sliderMoved, false, 0, true);
   maxDataSliderx.addEventListener(Event.CHANGE, sliderMoved, false, 0, true);
   
   playerScorex.text = String(playerScore);
   comScorex.text = String(comScore);
   tieScorex.text = String(tieScore);
   nLengthx.text = "window size: " + String(myCom.getNLength() - 1);
   maxDatax.text = "max data: " + String(myCom.getMaxDataNum());
  } 
  
  private function sliderMoved(event:Event):void
  {
   var slider:String = event.currentTarget.name;
   
   switch(slider)
   {
    case "nLengthSliderx":
     myCom.setNLength(event.currentTarget.value);
     break;
     
    case "maxDataSliderx":
     myCom.setMaxDataNum(event.currentTarget.value);
     break;
   }
   
   updateDataText();
  }
  
  private function buttonClicked(event:MouseEvent):void
  {
   var button:String = event.currentTarget.name;
   var comAction:String = getComAction();
   //trace("action: " + comAction);
   
   switch(button)
   {
    case "rockx":
     test(ROCK, comAction);
     
     myCom.addSingleData(ROCK);
     
     updateText(ROCK, comAction);
     break;
     
    case "scissorsx":
     test(SCISSORS, comAction);
     
     myCom.addSingleData(SCISSORS);
     
     updateText(SCISSORS, comAction);
     break;
     
    case "paperx":
     test(PAPER, comAction);
     
     myCom.addSingleData(PAPER);
     
     updateText(PAPER, comAction);
     break;
     
    case "randomx":
     var playerAction:String = getRandomAction();
     
     test(playerAction, comAction);
     
     myCom.addSingleData(playerAction);
     
     updateText(playerAction, comAction);
     break;
   }
  }
  
  private function getRandomAction():String
  {
   var rand:int = Math.ceil(Math.random() * 3);
   
   if (rand == 1)
   {
    return ROCK;
   }
   else if (rand == 2)
   {
    return PAPER;
   }
   
   return SCISSORS;
  }
  
  private function updateDataText():void
  {
   nLengthx.text = "window size: " + String(myCom.getNLength() - 1);
   maxDatax.text = "max data: " + String(myCom.getMaxDataNum());
  }
  
  private function updateText(playerAction:String, comAction:String):void
  {
   playerScorex.text = String(playerScore);
   comScorex.text = String(comScore);
   tieScorex.text = String(tieScore);   
   
   if (logx.text.length <= 500) 
   {
    logx.text += "Player action: " + playerAction + " vs COM action: " + comAction + "\n";
   }
   else
   {
    logx.text = "Player action: " + playerAction + " vs COM action: " + comAction + "\n";
   }
   logx.verticalScrollPosition = logx.maxVerticalScrollPosition;
  }
  
  private function getComAction():String
  {
   var predictedAction:String = myCom.getNextAction() as String;
   //trace("predict: " + predictedAction);
   var action:String;
   
   if (predictedAction == ROCK)
   {
    action = PAPER;
   }
   else if (predictedAction == PAPER)
   {
    action = SCISSORS;
   }
   else if (predictedAction == SCISSORS)
   {
    action = ROCK;
   }
   else if (predictedAction == null)
   {
    var rand:int = Math.ceil(Math.random() * 3);
    
    if (rand == 1)
    {
     action = ROCK;
    }
    else if (rand == 2)
    {
     action = PAPER;
    }
    else
    {
     action = SCISSORS;
    }
   }
   
   return action;
  }
  
  private function test(playerInput:String, comInput:String):void
  {
   if (playerInput == ROCK)
   {
    if (comInput == SCISSORS)
    {
     playerScore += 1;
    }
    else if (comInput == PAPER)
    {
     comScore += 1;
    }
   }
   else if (playerInput == PAPER)
   {
    if (comInput == ROCK)
    {
     playerScore += 1;
    }
    else if (comInput == SCISSORS)
    {
     comScore += 1;
    }
   }
   else if (playerInput == SCISSORS)
   {
    if (comInput == PAPER)
    {
     playerScore += 1;
    }
    else if (comInput == ROCK)
    {
     comScore += 1;
    }
   }
   
   if (playerInput == comInput)
   {
    tieScore += 1;
   }
  }
 }
}
 
Untuk class ini ga perlu panjang2x deh, karena isinya ya cuma nampilin game RPS nya.

15: myCom, bikin object AI baru dari si NGramPredictor tadi

138: method getComAction(), ini untuk mendapatkan aksi dari si myCom berdasarkan prediksinya.
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.

177: method test(), test aksi antara player dengan myCom, cek siapa yang menang dan update skor masing2x.

Sekian untuk coding nya….


5. Run Time
Silakan ditest….


cara gampang nyoba AI nya jalan atau tidak, kita cukup pencet tombol yang sama aja, misal tombol Rock dipencet terus2xan. Dijamin anda akan kalah telak. Begitu juga kalo kita sekedar pencet tombol dengan pattern yang sama misal Rock-Paper-Scissors secara terus menerus. 

Untuk mengubah level kecerdasan si COM, cukup atur slider yang di bawah. Seperti yang sudah dibahas, nilai nLength, window size, dan panjang data akan menentukan keakuratan AI dalam memprediksi  


6. Source Code    



7. Referensi
AI for Game 2nd Ed, Ian Millington & John Funge
A Simple N-Gram Calculator, Websense.com
Languange detection with N-Gram, phpir.com

Freelance 2D game artist, occassional game developers, lazy blogger, and professional procrasctinator

11 comments:

  1. huwawh, keren banget nih gan . buatan siapa mas ? buatan agan bukan ?

    ReplyDelete
  2. OM di tunggu fuzzy logicnya lagi butuh banget nih buat game saya tugas akhir.,., sangat sangat di tunggu hahahahha.

    ReplyDelete
    Replies
    1. kalo mau codenya bisa donlot di github: https://github.com/pzUH/FuzzySystem
      cm kalo mau penjelasannya, gw masih males buat nulisnya... ha3x

      Delete
    2. makasih banyak,., yang saya bingung tuh penjelasan implementasi fuzzy logic di game action rpg yang saya buat.,., dari penjelasan yang fsm+dt itu cukup ngerti cuman g bisa di jadiin skripsi.

      Delete
    3. Mungkin baca sendiri aja ya e-book nya: http://www.4shared.com/office/xH4YJ2PN/Programming_Game_AI_By_Example.html

      gw juga referensinya dari sana juga kok...

      Delete
  3. mav mas
    tolong dibuatkan algoritmanya saja buat game fighting ini dengan metode n-gram ini,
    bingung saya bacanya,
    heheh

    ReplyDelete
    Replies
    1. algoritma nya ya kyk gitu...
      kalo disuruh bikin gamenya, ya pegel juga gw bikinnya... ha3x

      Delete
    2. maksudnya dalam bentuk gambar or flowchart mas,

      Delete
  4. Terimakasih artikelnya bermanfaat banget,

    Ingin bisa desain grafis? Tapi bingung minta bantuan siapa? Belajar sendiri aja yuk.. kita lihat tutorialnya di kumpulan tutorial-tutorial gratis

    ReplyDelete
  5. wah keren mas ini penjelasannya detail sekali, kebetulan sy jg lg ngrjakan skripsi pake metode ini....

    ReplyDelete
  6. Terima kasih..

    ReplyDelete