OTHELLO
Tujuan
Othello
merupakan suatu permianan yang menggunakan konsep Artificial Intelligence atau kecerdasan buatan. AI pada permainan
ini terletak pada komputer yang akan bertindak sebagai lawan. Komputer akan selalu
berusaha mengalahkan user dengan cara menutup langkah pemain untuk membentuk
sebuah garis, komputer dapat menyusun strateginya sendiri agar menjadi
pemenang. Othello menjelaskan tentang permainan dua buah benda lingkaran yang
memiliki 2 warna yang berbeda. Inti dari permainan ini ialah memenangkan
perlawanan dari komputer dengan menjadikan satu baris horizontal, vertical, dan
diagonal berturut-turut dengan warna yang sama.
Pada permainan
ini terdapat kotak yang terdiri dari baris dan kolom yang dapat diisi bergantian
antara pemain dan lawan dengan cara meletakkan pin milik pemain disamping
pemain milik lawan yang berfungsi untuk menutupi ruang gerak milik lawan. Jika salah
satu dari pemain memperoleh jumlah terbanyak dari pin yang dimiliki maka pemain
itulah yang dijadikan pemenang.
Algoritma
Greedy
Algoritma greedy
merupakan metode yang paling popular untuk memecahkan masalah optimassi. Algorita
greedy membentuk solusi langkah
perlangkah. Pendekatan digunakan didalam algoritma greedy adalah membuat pilihan yang tampak memberi perolehan
terbaik, yaitu dengan membuat pilihan optimum local pada setiap langkah dengan
harapan akan mengarah ke solusi optimum global. Prinsip algoritma greedy pada setiap langkah ialah
mengambil pilihan terbaik yang dapat diperoleh saat itu tanpa memperhatikan
konsekuensi ke depan, dan berharap bahwa dengan memilih optimum local pada
setiap langkah akan menghasilkan optimum global pada akhir proses.
TIC TAC TOE
Tujuan
Permainan
tic-tac-toe merupakan permainan berjenis board-game berukuran 3x3. Sekilas sama
seperti permainan Othello, karena dalam permainan tic-tac-toe ini pemain harus
mengisi sel-sel, sehingga karakter yang dimasukkan pemain tersebut dapat
membentuk suatu garis lurus horizontal, vertical, ataupun diagonal. Pemain ini
juga dimainkan oleh 2 orang pemain, yaitu user dan komputer. Namun dalam
permainan ini, pemenang tidak ditentukan oleh banyaknya pin yang diisi dalam
sel, melainkan dari siapa yang terlebih dahulu membentuk suatu garis lurus. Hasil
permainan berupa menang, kalah, dan seri.
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. Tentunya dibutuhkan resource yang berskala besar untuk menangani komputasi pencarian
pohon solusi tersebut berhubung kombinasi kemungkinan untuk sebuah permainan
catur pada setiap geraknya sangat banyak sekali.
Algoritma minimax
bekerja secara rekursif dengan mencari langkah yang akan membuat lawan
mengalami kerugian minimum. 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 paling
membuat komputer itu sendiri mendapatkan keuntungan maksimum.
Dalam penentuan keputusan pada algoritma minimax
digunakan sebuah fungsi heuristic untuk mengevaluasi nilai sebagai nilai yang
merepresentasikan hasil permainan yang akan terjadi jika langkah tersebut
dipilih. Pada permainan tic-tac-toe ini digunakan nilai 1, 0, -1 untuk
mewakilkan hasil akhir permainan berupa menang, seri, dan kalah. Dari nilai-nilai
heuristic inilah komputer akan menentukan simpul mana dari pohom permainan yang
akan dipilih, tentunya simpul yang akan dipilih tersebut adalah simpul dengan
nilai heuristic yang akan menuntun permainan ke hasil akhir yang menguntungkan
bagi komputer.
SNAKE
Tujuan
Permainan snake
merupakan permainan populer dalam telepon selular beberapa tahun yang lalu. Inti
dari permainan ini adalah agar snake yang kita control mendapatkan
sebanyak-banyaknya makanan tanpa membentuk dinding atau bagian tubuhnya
sendiri. Semakin banyak maknan yang snake dapatkan, tubuhnya akan tumbuh
semakin panjang.
Permainan ini
merupakan permainan yang dimainkan sendiri (single
player). Dalam permainan ini komputer hanya memunculkan makanan secara acak
dilayar untuk dimakan. Kesuksesan permainan ini bergantung kepada kecepatan dan
perhitungan sang pemain agar ular yang dikontrolnya tidak terjebak dinding atau
bagian tubuhnya sendiri.
Algoritma
Branch and Bound
Algoritma yang
digunakan dalam pemodelan ini adalah algoritma branch and bound. Algoritma ini sebenarnya adalah algoritma
pencarian solusi dengan pencarian melebar atau breadth first search (BFS). Dalam algoritma BFS solusi dicari
dengan membentuk pohon ruang status yang merupakan pohon dinamis.
Simpul-simpul di dalam pohon diinamis yang memenuhi
kendala menyatakan status persoalan. Suatu operator mentransformasikan
persoalan dari sebuah status ke status yang lani. Solusi persoalan dinyatakan
dengan satu atau lebih status yang disebut status solusi. Status solusi yang
merupakan simpul daun disebut status tujuan. Himpunan semua status solusi
disebut ruang solusi. Seluruh simpul di dalam pohon dinamis disebut ruang status.
Dan pohonnya dinamakan juga pohon ruang status. Akar pada pohon ruang status
menyatakan status awal sedangkan daun menyatakan status solusi.
BFS
mencari solusi persoalan pada pohon ruang status yang dibentuk secara dinamis
dengan cara semua simpul pada aras d dibangkitkan terlebih dahulu
sebelum simpul-simpul pada aras d+1. Simpul BFS memerlukan sebuah
antrian untuk menyimpan simpul-simpul yang akan dibangkitkan. Simpul-simpul
yang dibangkitkan disimpan di belakang antrian.
TETRIS
Tujuan
Tetris adalah permainan teka-teki yang
disusun dan diprogram oleh sepasang programmer berkebangsaan Rusia. Dalam permainan
tetris, balok-balok tetris berjatuhan ke area permainan dalam waktu konstan. Balok
tetris selalu terdiri dari 4 balok kecil yang membentuk 7 macam rupa.
Algoritma Greedy dan Brute Force
Algoritma greedy memecahkan masalah langkah
perlangkah, pada setiap langkah :
- Mengambil
pilihan yang terbaik, yang dapat diperoleh pada saat itu tanpa memperhatikan
konsekuensi ke depan (prinsip: “take what you can get now!”)
- Berharap
dengan memilih optimum local pada setiap langkah akan berakhir dengan optimum
global brute force adalah sebuah pendekatan yang sesuai (straight forward) untuk memecahlan suatu masalah. Biasanya didasarkan
pada pernyataan masalah (problem
statement) dan definisi konsep yang dilibatkan.
Algoritma brute
force memecahkan masalah dengan sangat sederhana, langsung dan dengan
cara yang jelas (obvious way). Algoritma yang digunakan untuk
mendapatkan susunan tumpukan balok yang paling baik dengan menempatkan balok ke
tempat yang tepat. Algoritma ini menggunakan prinsip Greedy dalam mencari
langkah solusi yang paling menguntungkan. Prioritas keuntungan yang tersusun
terdiri dari:
- Membentuk
satu atau lebih baris paling penuh
- Membentuk
satu atau lebih baris paling mendekati penuh
- Tidak
membentuk ruang kosong pada susunan tumpukan balok
Balok
dapat masuk ke dalam susunan tumpukan balok paling dalam Algoritma yang kami
kemukakan akan mencari penempatan balok yang jatuh ke ruang yang paling tepat
sesuai prioritas keuntungan di atas diantara susunan tumpukan balok.
Pencarian ini akan dilakukan secara brute force. Balok yang jatuh
akan dicoba untuk ditempatkan ke ruang di antara susunan tumpukan balok
dibawah.
TEKA-TEKI
SILANG
Tujuan
Teka-teki
silang atau disingkat TTS merupakan suatu permainan yang selain bertujuan
untuk hiburan, dapat juga mengasah otak yang memainkannya. Teka teki silang
adalah permainan di mana kita harus mengisi ruang-ruang kosong (berbentuk kotak
putih) dengan huruf-huruf yang membentuk sebuah kata berdasarkan petunjuk yang diberikan. Petunjuknya biasa
dibagi ke dalam kategori 'mendatar' dan 'menurun' tergantung arah kata-kata
yang harus diisi.
Algoritma Back Tracking
Algoritma back tracking
merupakan algoritma yang digunakan untuk mencari solusi persoalan secara lebih
praktis daripada menggunakan algoritma brute force. Algoritma ini akan mencari
solusi berdasarkan ruang solusi yang ada secara sistematis namun tidak semua
ruang solusi akan diperiksa, hanya pencarian yang mengarah kepada solusi yang
akan di proses.
Algoritma back tracking
berbasis pada Depth First Search
(DFS) sehingga aturan pencariannya akan mengikut kepada aturan pencarian DFS
yaitu dengan mencari solusi dari akar ke daun (dalam pohon ruang solusi) dengan
pencarian ke dalam. Simpul-simpul yang sudah diperiksa dinamakan sipmup hidup (live node). Simpul hidup yang sedang
diperluas dinamakan simpul-E atau Expand
Node.
Algoritma back tracking dalam permainan ini akan digunakan untuk mengisi
kotak-kotak permainan yang sebelumnya telah dibuat. Kotak-kotak ini biasa
direpresentasikan dengan struktur data matriks sehingga setiap kotak akan
memiliki indeks. Indeks ini akan digunakan untuk melakukan pencarian kata yang
cocok pada pengisian kata kedalam kotak-kotak. Pertama program akan menentukan
deretan kotak awal yang akan diisi. Program akan menghitung jumlah kotak pada
deretan kotak tersebut kemudian akan mencari kata didalam database yang terdiri
atas kumpulan kata (jawaban) yang memiliki jumlah karakter sama dengan jumlah
kotak tersebut.
Referensi :
Situmorang, Indra Soaloon. __, Pemodelan AI
dalam Permainan Snake dengan Algoritma Branch and Bound, [pdf], (http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2006-2007/Makalah_2007/MakalahSTMIK2007-109.pdf)
No comments:
Post a Comment