Penyelesaian Permainan “Pacman” yang disederhanakan dengan Algoritma
Backtracking
oleh : Anis Istiqomah
Pacman adalah video game terpopuler
sepanjang masa. Game ini dimainkan di lebih dari
100.000 arkade (mesin game berbasis koin) pada tahun
pertama rilisnya dan menghasilkan pendapatan
sebesar satu miliar dolar A.S. Ide pembuatan game ini
sebetulnya sangat sederhana. Karena melihat sepotong
pizza yang hilang dalam loyangnya, programmer Toru
Iwatani terpikir untuk mengembangkan game pacman
yang karakternya mengacu pada pizza di loyangnya.
Pada perkembangannya, budaya pacman,
yang selanjutnya dikenal sebagai wabah "Pacmania",
semakin menjalar. Pasalnya ini adalah game pertama
yang menggunakan tokoh sentral. Setelah itu,
karakter pacman muncul di mana-mana. Mulai dari
acara televisi, mainan, bungkus makanan, t-shirt,
sampai lagu Pacman Fever ciptaan Jerry Buckner dan
Gary Garcia pun jadi hit.
Masalah dalam permainan pacman dapat
diselesaika dengan berbagai cara. Salah satunya
adalah dengan algoritma backtracking. Algoritma ini
dipakai agar pacman berhasil memakan semua
makanan dalam game.
METODE
Untuk menyelesaikan masalah ini, digunakan
algoritma backtracking. Pacman akan berjalan di dalam
labirin. Jika menemui jalan buntu atau jalan yang akan
dilalui sudah tidak memiliki makanan, maka pacman akan
melakukan backtracking ke langkah sebelumnya sampai
ditemukan jalan yang belum dilalui. Hal ini terus
dilakukan sampai pacman memakan semua makanan yang
ada di sepanjang labirin.
selengkapnya...
Selasa, 17 Maret 2009
jurnal 3
Aplikasi struktur data The Minimax Game Tree pada permainan catur
oleh :
Abdul Gapur
Departemen Teknik Informatika.
Institut Teknologi Bandung
Abstrak
Permasalahan yang timbul selalu diharapkan mempunyai solusi yang bagus. Walaupun sebenarnya algoritma
selalu berkembang untuk suatu permasalahan-permasalahan yang berbeda. Perkembangan algoritma sesuai
dengan kebutuhannya pada dunia intelijensi buatan. Permainan yang berbasis pada giliran pemain. Salah satu
algoritma yang cukup mangkus pada saat ini adalah Branch and Bound yang diimplementasikan pada struktur
data The Minimax Game Tree. Dengan konsep utama terletak pada semua kemungkinan yang bisa ditelusuri
pada permainan. Dalam hal ini, permainan catur dapat menggunakan algoritma ini karena permainan dapat di
implementasikan dalam sebuah pohon. Pohon yang mempunyai cabang yang terdiri dari simpul-simpul yang
menyatakan status-status yang nantinya digunakan untuk menentukan langkah dalam pencarian tujuan
permainanan.
Kesimpulan
Algoritma ini dapat dimanfaatkan sebagai otak dari
permainan dalam intelijensi buatan. Dengan adanya
algoritma ini. Salah satu dari jenis permasalan yang
melibatkan pencarian (searhing) akan lebih mudah
dan lebih efisien dibandingkan beberapa algoritma
yang sejenis yang menggunakan pohon seperti DFS
atau BFS.
Masih terdapat kekurangan pada algoritma The
Minimax Game Tree ini. Seperti yang terdapat pada
pembahasan yang telah dipaparkan diatas. Tetapi
walaupun pada saat ini The Minimax Game Tree
merupakan salah satu algoritma yang mangkus
untuk menyelesaikan permainan yang berbasis
selengkapnya...click disini
