Firda Qurrota A


HELLO !!

UNIFORM COST SEARCH PADA SOKOBAN

Sokoban adalah sebuah tipe permaianan puzzle video game, dimana pemain atau agent yang ada di video game mendorong peti atau boks di sekitar gudang, dimana goalnya adalah menaruh peti atau boks tersebut ke tempat penyimpanan.

Permainan atau video game ini sendiri diciptakan pada tahun 1981 oleh Hiroyuki Imabayashi, dan di terbitkan pada December 1982 oleh Thinking Rabbit, sebuah perusahaan software berbasis di Takarazuka,Jepang.

Sedangkan UCS / Uniform Cost Search sendiri merupakan salah satu algoritma terbaik untuk melakukan pencarian yang tidak melibatkan cabang heuristik. Algoritma ini memulai pencarian dari root node, kemudian dilanjutkan ke node-node selanjutnya. Dimana node tersebut dipilih berdasarakan cost atau harga terkecil dari root node. Algortima ini sendiri merupakan modifikasi dari algoritma Breadth First Search. Dalam implementasinya, algoritma ini melibatkan seluruh node yang berhubungan dengan root node, dan memilih node selanjutnya berdasarkan harga yang paling kecil.

Cara kerja algoritma Uniform Cost Search pada Sokoban, mula-mula
Ada dua fungsi biaya yang dipertimbangkan untuk UCS.

Fungsi biaya pertama dilaksanakan dengan memberikan biaya maksimum untuk tindakan mendorong peti keluar dari lokasi target diikuti dengan memindahkan peti dengan jarak/biaya sedikit yang diberikan kepada pergerakan pemain.

Fungsi biaya kedua diambil dengan cara di mana tindakan pertama dan ketiga memiliki biaya yang sama. 

Ketika ini diterapkan, fungsi biaya pertama berjalan dengan baik sedangkan kecepatan pencarian akan menurun untuk fungsi yang kedua. 

Dikarenakan untuk fungsi kedua akan terdapat dua jalur yang memiliki harga yang berbeda untuk pergerakan agent/pemain. 

 


Link : https://youtu.be/D_0gBiTnKHo

Tinggalkan Komentar

Nama :
E-mail :
Web : tanpa http://
Komentar :
Verification Code :