Analisis & Algoritma 5 Game
Game Stich Toe
Permainan Stitch Toe menggunakan sebuah
bidang papan 2 dimensi yang berukuran 5x5 dimana akan digunakan sebagai arena
bermain antara user dan AI (computer). User menggunakan icon “stitch” berwarna
pink dan AI atau computer menggunakan icon “stitch” berwarna biru sebagai
identitas di dalam permainan. User dan AI mempunyai peraturan yang sama di mana
mereka dapat saling menutup jalan lawan menuju goal ataupun memenangkan
pertandingan dengan membuat icon mereka berbaris vertical, horizontal, atau diagonal.
Tidak ada mengulangi jalan yang sudah di ambil di dalam game ini. Jadi apabila
terjadi kesalahan dan user mengalami kekalahan, user harus mengulang game ini
dari awal.
Algoritma
Pada permainan Stitch Toe algoritma yang
di gunakan yaitu algoritma minimax, Algoritma minimax merupakan basis dari
semua permainan berbasis AI. Pada algoritma minimax, pengecekan akan seluruh
kemungkinan yang ada sampai akhir permainan dilakukan. Pengecekan tersebut akan
menghasilkan pohon permainan yang berisi semua kemungkinan tersebut. Keuntungan
yang didapat dengan menggunakan algoritma minimax yaitu algoritma minimax mampu
menganalisis segala kemungkinan posisi permainan untuk menghasilkan keputusan
yang terbaik karena algoritma minimax ini bekerja secara rekursif dengan
mencari langkah yang akan membuat lawan mengalami kerugian minimum. Semua
strategi lawan akan dihitung dengan algoritma yang sama dan seterusnya. Ini
berarti, pada langkah pertama komputer akan menganalisis seluruh pohon
permainan. Dan untuk setiap langkahnya, komputer akan memilih langkah yang
paling membuat lawan mendapatkan keuntungan minimum, dan yang paling membuat
komputer itu sendiri mendapatkan keuntungan maksimum. Dalam penentuan keputusan
tersebut dibutuhkan suatu nilai yang merepresentasikan kerugian atau keuntungan
yang akan diperoleh jika langkah tersebut dipilih.
Game Sudoku
Permainan Sudoku merupakan permainan
logika yang sangat populer, permainan ini sangat sederhana yaitu mengisi suatu
matriks yang berukuran 9x9 sehingga pada setia kolom , setiap baris dan setiap
dari kotak yang berukuran 3x3 mengandung digit angka dari 1 sampai 9 dan pada
setiap baris, kolom dan kotak yang berukuran 3x3 tersebut tidak dapat dua atau
lebih kemunculan angka yang sama. daya tarik dari permainan sudoku ini adalah
aturan permainan yang sederhana tetapi penalaran yang dibutuhkan untuk
menyelesaikan permainan ini dapat saja berubah menjadi kompleks.
Algoritma
Pada permainan Sudoku menggunakan
algoritma Backtracking, Algoritma Backtracking merupakan algoritma yang
berbasiskan pada algoritma DFS (Depth First Search) untuk mencari solusi
persoalan lebih mangkus.Kalau dilihat secara lebih teliti,algoritma
Backtracking ini sebenarnya merupakan modifikasi algoritma Bruteforce. Modifikasi
ini menyebabkan algoritma Backtracking dapat secara sistematis mencari solusi persoalan
tanpa harus memeriksa seluruh kemungkian solusi yang ada. Hanya pencarian yang
mengarah ke solusi saja yang dipertimbangkan oleh algoritma ini,sedangkan
pencarian yang tidak mengarah ke sebuah solusi tidak dilanjutkan.Hal ini
menyebabkan waktu komputasi algoritma Backtracking jauh lebih baik.
Penerapan algoritma Backtracking pada
permainan sudoku adalah sebagai berikut :
- Algoritma dimulai pada elemen matris baris kesatu dan kolom ke satu
- Periksa seluruh kemungkinan angka yang dapat dimiliki oleh baris tersebut
- Jika terdapat angka yang valid dengan constraint permainan sudoku maka lanjutkan pemeriksaan ke elemen selanjutnya dari matriks
- Jika tidak terdapat angka yang valid maka backtrack ke elemen matriks sebelumya
- Algoritma ini akan berhenti jika sudah ditemukan suatu solusi atau jika tidak terdapat kemungkinan adanya solusi
Game Word Search
Permainan Wordsearch puzzle adalah
sebuah permainan kata dengan banyak huruf diletakkan pada sebuah papan yang biasanya
memiliki bentuk persegi atau persegi panjang. Tujuan dari permainan puzzle ini
adalah untuk menemukan dan menandai semua kata-kata yang tersembunyi di dalam
papan. Kata-kata tersebut dapat tersusun secara horizontal, vertikal, atau
diagonal.Biasanya terdapat daftar kata tersembunyi yang harus dicari. Tetapi
terdapat variasi permainan wordsearch yang tidak memberikan daftar kata
sehingga lebih menantang bagi pemain untuk menemukan semua kata-kata yang ada. Variasi
lainnya dari permainan ini adalah adanya tema untuk kata-kata maupun tampilan
yang sesuai dengan temanya.
Algoritma
Pada permainan Wordsearch algoritma yang
digunakan adalah algoritma DFS, algoritma DFS atau Depth First Search yaitu
algoritma yang lebih mangkus dalam pencarian kata. Hal ini dikarenakan pada
algoritma DFS pencarian dapat berhenti langsung jika sudah menemukan huruf yang
diinginkan sedangkan pada BFS diharuskan mencari huruf-huruf selanjutnya yang
masih berada pada tingkat yang sama. Biarpun pada kasus terburuk, DFS dapat menghasilkan
jumlah perbandingan yang sama dengan BFS. Pada penyelesaian ini, prioritas arah
secara berurutan adalah kiri, kiri-atas, atas, kanan-atas, kanan, kanan-bawah,
bawah, dan kiri-bawah. Asumsi lainnya adalah pencarian pada arah yang
bersangkutan akan dihentikan ketika huruf sudah tidak sama lagi.
Game Fanorona
Permainan Fanorona dimainkan oleh dua
orang pemain. Setiap pemain bebas mengontrol 22 bidaknya. Total seluruh bidak
yang digunakan dalam permainan Fanorona berjumlah 44 bidak dengan dua warna
yang berbeda, biasanya berwarna hitam dan putih. Pemain yang mengontrol bidak
berwarna putih diperkenankan untuk jalan terlebih dahulu. Seluruh bidak
diletakkan di papan permainan disetiap titik perpotongan empat atau lebih Untuk
memenangkan pertandingan, pemain harus merebut (capture) seluruh bidak lawan
seperti pada permainan papan checkers, atau memaksa lawan berada di posisi
dimana lawan tidak bisa lagi menggerakkan bidaknya. Jika kedua pemain tidak ada
yang bisa memenuhi kondisi menang tersebut, maka permainan berakhir dengan
hasil seri.
Algoritma
Pada permainan Fanorona algoritma yang
digunakan adalah Algoritma branch and bound. Algoritma branch and bound yaitu
sebuah teknik algoritma yang secara khusus mempelajari bagaimana caranya
memperkecil Search Tree menjadi sekecil mungkin.
Algoritma ini dapat diterapkan pada permainan
papan Fanorona untuk menentukan langkah pemain setiap mendapatkan giliran
jalan. Jika pemain ingin merebut bidak lawan sebanyak-banyaknya setiap pemain
tersebut mendapatkan giliran jalan, maka setiap kemungkinan langkah yang dapat
dilakukan saat itu dapat dijadikan sebuah pohon ruang status permasalahan
dengan akar (root) dari pohon tersebut adalah kondisi papan permainan saat tiba
giliran pemain untuk jalan. Dalam permainan Fanorona pemain diharuskan merebut
bidak lawan sebanyak-banyaknya untuk memenangkan pertandingan, maka queue
tersebut akan terurut mengecil sehingga akan dilakukan ekspansi dari simpul
hidup yang memiliki nilai ongkos terbesar setiap langkahnya. Jika telah sampai
pada tahap dimana simpul hidup yang harus diekspansi ternyata berupa daun dari pohon
ruang status, maka simpul tersebut merupakan simpul solusi (goal node) dari
permasalahan ini dan pemain akan memindahkan bidaknya sesuai dengan langkah
pada penelusuran solusi (menelusuri dari goal node ke root). Setelah lawan
menyelesaikan gilirannya, pemain dapat melangkah lagi dengan kembali menerapkan
algoritma branch and bound dengan membentuk pohon
ruang
status baru dengan root-nya adalah kondisi papan permainan saat itu
Game Domino
permainan domino dimainkan dengan
meletakkan kartu domino yang bernilai paling kecil terlebih dahulu yaitu kartu
kosong, kemudian diikuti oleh pemain lain dengan menyambung kartu domino dengan
nilai yang bersesuaian sehingga membentuk suatu pola yang tidak terputus.
Permainan ini pada umumnya dimainkan oleh 4 orang dan dapat dimainkan lebih
dari 4 orang. Dalam permainan domino, memilih kartu solusi yang tepat untuk
dibuang merupakan salah satu faktor yang sangat menentukan untuk memenangkan
permainan ini. Permainan berakhir jika terdapat pemain yang dominonya telah
habis atau semua pemain tidak dapat lagi menyambungkan balok-balok itu lagi. Pemain
dengan nilai angka yang paling sedikit adalah pemenangnya.
Algoritma
Pada permainan domino algoritma yang
digunakan adalah Algoritma Brute Forc, Algoritma brute force yaitu algoritma
yang memecahkan masalah dengan sangat sederhana, langsung dan dengan cara yang
jelas (obvious way). Algoritma brute force seringkali lebih mudah
diimplementasikan daripada algoritma yang lebih canggih, dan karena
kesederhanaannya, kadang-kadang algoritma brute force dapat lebih mangkus
(ditinjau dari segi implementasi).. Ada 3 tingkat kecerdasan atau level yang
akan digunakan untuk penerapan algoritma Brute Force dalam permainan domino
ini. Pada setiap level akan diberikan strategi bermain yang berbeda. Penerapan
algoritma Brute Force dengan menambahkan beberapa strategi. Terlihat proses
rekursif terjadi karena pemasukan kartu akan dilanjutkan terus hingga kartu
kita habis atau permainan telah berakhir. Jika bertemu dengan persimpangan maka
keluarkan kartu apapun yang masih bisa dikeluarkan, tanpa memperhatikan nilai
dari kartu tersebut. Demikian algoritma brute force bekerja pada permainan
domino ini. Walaupun terlihat biasa saja tapi algoritma ini dapat menyelesaikan
permasalahan permainan domino ini dengan pasti.
Sumber:
- Yulianti, Miarinda.2015. Project game PKB “Stich Toe”.Depok.
- http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2006-2007/Makalah_2007/MakalahSTMIK2007-013.pdf
- http://www.dreamstime.com/royalty-free-stock-images-word-search-game-animals-image25745689
- http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2012-2013/Makalah2012/Makalah-IF3051-2012-100.pdf
- https://maharrhanni.wordpress.com/2014/12/27/paper-perancangan-dan-analisis-algoritma/
Tidak ada komentar:
Posting Komentar