Permainan 8Puzzle dan Algoritma Best-First Search

Dalam permainan 8Puzzle terdapat 9 cell 3 x 3 yang berisi 8 kotak (selanjutnya disebut tile, T), dengan penomoran 1 sampai 8 (T1-T8), yang bisa digeser. Satu cell selalu kosong (selanjutnya disebut blank, B), dan tile yang bersebelahan dengan blank dapat digeser ke cell blank tersebut. Bisa juga dikatakan, blank digeser ke arah tile sebelahnya, yang selanjutnya penggeseran blank ini akan digunakan dalam program. Susunan tiles yang unik menunjukkan satu state. Susunan tiles awal disebut state inisial, sedangkan susunan tiles akhir disebut state tujuan. Penggeseran blank berarti menambah satu state baru. Objektif permainan adalah menggeser blank sampai ke state tujuan. Suatu algoritma pencarian diterapkan untuk mencapai objektif tersebut, seperti ditunjukkan dalam Gambar berikut:

Contoh permainan 8puzzle

Ukuran performansi algoritma pencarian yang diimplementasikan adalah sebagai berikut:

  1. Completeness yang menunjukan seberapa lengkap algoritma mengevaluasi state-state solusi yang mungkin. Algoritma yang complete harus bisa menjamin bahwa solusi yang dihasilkan merupakan solusi yang paling optimal;
  2. Tingkat efisiensi yang menunjukkan seberapa efisien resource komputing dan waktu yang diperlukan untuk mencari solusi. Efisiensi ini ditunjukkan dengan space complexity dan time compexity. Space complexity dapat ditunjukkan dengan berapa jumlah node/state yang harus dibangkitkan, sedangkan time complexity ditunjukkan berapa kali ia melakukan evaluasi state untuk menentukan state dengan cost terendah. Semakin sedikit node yang dibangkitkan, dan frekuensi state harus dievaluasi, algoritma dapat dikatakan semakin efisien;

Completeness secara tidak langsung dapat dilihat dari jumlah langkah (step) untuk mencapai objektif. Efisiensi secara langsung dapat dilihat dari jumlah rata-rata opened node saat evaluasi. Optimalitas algoritma dapat dinyatakan sebagai perbandingan antara jumlah langkah terhadap jumlah rata-rata opened node ini.

Algoritma pencarian yang akan digunakan adalah best-first searching, yang merupakan algoritma heuristik yang akan mencari rute melewati state dengan cost terendah menuju state akhirnya.

Suatu state n setidaknya mempunyai 3 macam cost seperti diperlihatkan dalam yaitu:

  1. g(n) : path cost, jarak state n dari state awal. Cost ini menunjukkan tingkat kedalaman pencarian;
  2. h(n) : cost heuristik, jarak state n ke state akhir/tujuan. Untuk 8puzzle, jarak heuristik ini dapat dihitung menggunakan H1 (jumlah tile yang berbeda di state n dan state tujuan) dan H2 (manhattan distance, jumlah jarak tile-tile yang tidak bersesuaian antara state n dan state tujuan);
  3. f(n) : cost total. Cost total ini yang digunakan oleh algoritma untuk menentukan state mana yang akan diambil sebagai rute menuju state akhirnya. Cost mana saja yang akan digunakan untuk menghitung cost total ini menunjukkan algoritma searching yang digunakan, misalnya:
    1. Uniform-cost: f(n) = g(n) ; dengan kata lain h(n) = 0
    2. Greedy: f(n) = h(n) ; dengan kata lain g(n)=0
    3. A*/astar: f(n) = g(n) + h(n) ; g(n) dan h(n) keduanya diperhitungkan

Dengan nilai costnya masing-masing, suatu state dapat dinyatakan sebagai n(g,h). Satu state diwakili oleh satu node.
Algoritma best-first mengambil keunggulan dari breath-first dari sisi completeness, namun tidak semua node/state (opened) yang akan diekspan/dibangkitkan node successornya untuk mencari solusi yang mungkin. Hanya node yang mempunyai cost terendah (sebagai node terbaik) yang akan diekspan. Adapun algoritma best-first search sendiri dapat dinyatakan dalam pseudocode berikut:

 add init_state n0(g,h) to list L;
 set n0(g,h) as opened;
 set initial i=j=0;
 while ( ni(g,h)!= goal_state) {
   nj(g,h)= select_opened_bestnode(L, t_algorithm);
   for each_valid_solution from nj(g,h) { 
     if ni(g,h) found_in_list(L) continue;
     increment node index i++;
    add ni(g,h) to list L; /*will be the head of L*/
     set ni(g,h) as opened;
   }
   set nj(g,h)as closed;
  increment node evaluaion index j++;  
 }

Node yang belum mempunyai node successornya mempunyai status opened, sedangkan yang sudah diekspan diset statusnya sebagai closed. Variabel i akan menunjukkan jumlah node yang dibuat, sedangkan variabel j menunjukkan frekuensi evaluasi node. Untuk 8puzzle, solusi yang valid diperoleh dari pergeseran blank dengan aturan yang dijabarkan dalam subbab 3.2 tentang aturan transisi state.

Jika solusi tersebut telah ada dalam list L, state tidak akan dimasukkan dalam list L. Memang seharusnya state tersebut dibandingkan terlebih dahulu costnya dengan state yang telah ada di list L, dan memilih yang mempunyai cost terendah, dan membuang state yang lebih tinggi. Pertimbangan (rasionale) untuk langsung membuang state yang datang terakhir adalah sebagai berikut: kedua state mempunyai h(n) yang sama, tapi state yang masuk dahulu ke list akan mempunyai g(n) yang lebih kecil atau sama dengan state yang datang belakangan, sehingga state pertama dapat diasumsikan lebih optimal.

Algoritma best-first mengevaluasi node-node dengan status opened dan memilih node terbaik, yaitu dengan cost terendah (di baris select_opened_bestnode). Perbedaan antara uniform cost, greedy dan A* terletak di penentuan node terbaik ini:

  1. Uniform cost memilih node dengan path cost, g(n), yang terkecil. Algoritma ini akan menjamin jalur yang dipilih optimal, namun memiliki kelemahan terhadap efisiensi karena hampir semua node dengan level sama akan mempunyai g(n) yang uniform, sehingga bisa jadi semua node akan diekspan dan ini akan menyerupai breadth-first search;
  2. Greedy memilih node dengan cost heuristik, h(n), terkecil. Algoritma ini mengejar efisiensi dengan memilih node yang lebih dekat ke node tujuan. Harga yang harus dibayar adalah adanya kemungkinan jalur yang dipilih tidak optimal, ada jalur lain yang lebih pendek yang bisa ditempuh tapi terlewatkan (algoritma tidak komplet dalam mengevaluasi node-node) ;
  3. A* memilih node dengan jumlah path cost dan heuristic cost, f(n)=g(n)+h(n), yang terkecil. A* menggabungkan keunggulan dari Uniform-cost dan Greedy, dengan trade-off antara tingkat optimalitas jalur dan efisiensi yang didapatkan. Dalam implementasinya, algoritma A* dapat dibedakan menjadi 4 tipe sebagai berikut:
    1. A* standard. Algoritma ini mengikuti perilaku stack dalam linked list, yang bersifat LIFO (Last In First Out). Suatu node yang ditambahkan ke list L, akan masuk ke head dari list. Dalam mengevaluasi node-node dalam list L, node terakhir yang masuk ke list akan diambil pertama untuk dibandingkan dengan suatu konstanta MAX_COST (misalnya 1000). Jika cost f-nya lebih kecil, node ini akan menjadi kandidat node terbaik. Node berikutnya dibandingkan costnya dengan node pertama ini. Jika lebih kecil, ia diambil sebagai kandidat node terbaik. Jika sama, node dengan cost terendah pertama yang dipilih, bukan yang setelahnya. Demikian seterusnya, sampai semua node yang opened di list L telah dievaluasi. Memilih node terakhir dari list L sebagai pembanding untuk node-node berikutnya akan memiliki kecondongan seperti Greedy, karena kandidat node terbaik tersebut dijamin mempunyai h(n) yang paling rendah;
    2. A* with guaranteed minimum pathcost. Berkebalikan dengan yang standar, algoritma ini akan mengambil node yang mempunyai g(n) yang paling rendah. Artinya, kalau ada beberapa node yang mempunyai nilai cost total, f, yang sama, node yang pertama kali masuk dalam list L lah yang akan dipilih. Algoritma ini memiliki kecondongan seperti Uniform-cost, karena kandidat node terbaik tersebut dijamin memiliki g(n) yang paling rendah;
    3. Conditional A* with g(n), yang selanjutnya akan disebut Optimal Greedy. Dalam algoritma ini, g(n) dan h(n) akan digunakan dalam mengambil keputusan. Hanya saja, hanya h(n) yang digunakan sebagai pembanding utama, jika terdapat beberapa node dengan h(n) sama baru kemudian g(n) digunakan sebagai pengambil keputusan;
    4. Conditional A* with h(n), yang selanjutnya akan disebut Efficient A*. Dalam algoritma ini, g(n) dan h(n) akan digunakan dalam mengambil keputusan. f(n) = g(n) + h(n) digunakan sebagai pembanding utama, jika terdapat beberapa node dengan f(n) sama kemudian h(n) digunakan sebagai pengambil keputusan;

Jadi, terdapat 6 algoritma yang akan digunakan untuk mencari solusi untuk 8puzzle, yaitu

  1. uniform-cost (UNIFORM);
  2. greedy (GREEDY);
  3. A* standar (ASTAR);
  4. A* with guaranteed minimum pathcost (ASTAR_PATH);
  5. optimal greedy (OGREEDY); dan
  6. efficent A* (ASTAR_EFF);

Pseudocode untuk ke-enam algoritma tersebut adalah sebagai berikut:

function select_opened_bestnode(L, t_algorithm) {
  int lcost = MAX_COST; /*initial lowest cost*/
  int pcost = MAX_COST; /*conditional cost*/
  int fn, gn, hn, pn; /*total, path, heur & conditional distance*/
  int oper, coper; /*operand and conditional operand*/
   /* LTE_OPER=”<=” : guaranteed lowest pathcost
      LT_OPER=”<” : guaranteed lowest heuristic cost*/
  p = n; /*get head node of L, the last created node*/
  while ( n!= NULL ) {
    switch (t_algorithm) {
     case UNIFORM: hn=pn=0, gn=n->g; oper=LTE_OPER; coper=LTE_OPER;
     case GREEDY: gn=pn=0, hn=n->h; oper=LT_OPER; coper=LTE_OPER;
     case ASTAR: pn=0, gn=n->g, hn=n->h; oper=LT_OPER; coper=LTE_OPER;
     case ASTAR_PATH: pn=0, gn=n->g, hn=n->h; oper=LTE_OPER; coper=LTE_OPER;
     case OGREEDY: pn=n->g, gn=0, hn=n->h; oper=LTE_OPER; coper=LTE_OPER;
     case ASTAR_EFF: pn=n->h, gn=n->g, hn=n->h; oper=LT_OPER; coper=LTE_OPER;
    }    
    fn = gn + hn;
    if ( fn oper lcost && pn coper pcost ) {
      if (t_algorithm == OGREEDY or ASTAR_EFF) pcost=pn;
	lcost = fn;
      p = n;
    }
    n = n->next;
  }
  return p(g,h);
 }

Algoritma uniform-cost: memilih best g(n)

Algoritma uniform-cost: memilih best g(n)


Algoritma Greedy: memilih best h(n)

Algoritma Greedy: memilih best h(n)


A* with guaranteed minimum pathcost/ASTAR_PATH: memilih best f(n)=g(n)+h(n) dan best g(n)

A* with guaranteed minimum pathcost/ASTAR_PATH: memilih best f(n)=g(n)+h(n) dan best g(n)


Algoritma A* standar/ASTAR: memilih best f(n)=g(n)+h(n)

Algoritma A* standar/ASTAR: memilih best f(n)=g(n)+h(n)


Algoritma Efficient A* /ASTAR_EFF: memilih best f(n)=g(n)+h(n) DAN best h(n)

Algoritma Efficient A* /ASTAR_EFF: memilih best f(n)=g(n)+h(n) DAN best h(n)


Algoritma Optimal Greedy/OGREEDY: memilih best h(n) DAN best g(n)

Algoritma Optimal Greedy/OGREEDY: memilih best h(n) DAN best g(n)

Iklan

3 Komentar to “Permainan 8Puzzle dan Algoritma Best-First Search”

  1. Assalamu ‘alaikum mas.

    Salam kenal yah, saya abis mampir ke Blog mas, dan blog mas sangat bagus dan bermanfaat.

    Dan betapa senangnya saya, apabila mas mau mampir juga ke blog saya, sekalian saling menjalin silaturahmi sesama Blogger.

    Alamat Blog saya: http://bendeddy.wordpress.com

    Salam kenal,
    Dedhy Kasamuddin

  2. Izin copy paste programnya ya untuk tugas akhir….

  3. misi mas saya lagi mengerjakan skripsi tentang permainan puzzle dan kebetulan pakai algoritma best first search tapi saya kesulitan buat koding untuk algoritma nya, saya pakai aplikasi visual basic 6.0 mohon bantuannya. kalau bisa saya boleh minta emailnya? dan ini alamat emailnya saya norhalimah462@yahoo.co.id.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: