Analisa Game
1.) Analisa pada Game Maze (Labirin)
1.) Analisa pada Game Maze (Labirin)
Teknikal
Game Maze (Labirin) menggunakan algoritma
backtrack (runut balik)
di mana computer juga dapat menemukan jalur
yang tepat untuk mencapai tujuan.
Dalam proses penentuan jalur,
jika komputer mencapai tujuan
yang tidak sesuai
maka komputer
akan melakukan backtrack
(runut balik) hingga dapat mencapai tujuan yang sesuai.
Maze (Labirin)
merupakan game yang template-nya berbentuk
persegi yang
ukurannya dapat
diatur sesuai dengan
keinginan user. Di dalamnya
terdapat
serangkaian jalur
berupa labirin yang bercabang.
Namun, tidak setiap
cabang
mencapai tujuan yang
diinginkan.
Analisa Algoritma
Kemampuan algoritma
dalam menyelesaikan masalah game
Maze (Labirin) ini
menunjukkan
bahwa algoritma backtrack (runut
balik) cukup efektif
untuk
mendapatkan
solusi persoalan tersebut.
Sistem kerja algoritma backtrack yang
sistematis dan
ciri khasnya yang
hanya memeriksa kemungkinan solusi
yang
memang
dapat dipertimbangkan untuk menjadi
solusi akhir, diperkirakan untuk
menjadi solusi
yang efektif dan efisien untuk persoalan ini.
Kesimpulan
Algoritma backtrack
merupakan algoritma yang cukup
mangkus untuk menyelesaikan
berbagai persoalan. Hal
ini disebabkan karena
pada prinsipnya, kita tidak
perlu
memeriksa
semua kemungkinan solusi yang
ada. Pencarian hanya mengarah pada
solusi
yang dipertimbangkan saja. Oleh
karena algoritma ini
cukup efektif, maka
algoritma
backtrack banyak diterapkan
dalam berbagai program game
dan persoalan
yang
berkaitan dengan kecerdasan
buatan (artificial intelligence).
Sebenarnya sebagai sesuatu yang
cukup baru, penyelesaian persoalan
game Maze (Labirin)
ini belum
dapat
dianalisis untuk berbagai
algoritma. Namun melalui beberapa
analisis yang
penulis lakukan, penulis berpendapat bahwa
algoritma backtrack cukup efektif
untuk
menyelesaikan persoalan ini. Agar
lebih menarik, game
ini dapat ditambahkan aturan
main, misalnya terdapat pilihan level permainan,
batasan waktu permainan,
dan
batasan
jalur yang dilewati.
Selain itu, dari
sisi tampilan agar dapat
lebih menarik,
perlu
adanya visualisasi penelusuran jalur,
misalnya pemain atau
komputer
dilambangkan
sebagai objek yang
dapat bergerak ketika melakukan penelusuran jalur.
2.) Analisa pada Game Football Manager 2014
Teknikal
Football
Manager sendiri baru benar-benar 'lahir' pada tahun 2005, dimana pada tanggal
12 Februari 2004, setelah membelah dari penerbit Eidos Interactive , diumumkan
bahwa Sports Interactive, pengembang Manager permainan Championship, telah
mempertahankan hak untuk kode sumber tapi tidak hak untuk Championship Manager
judul, yang memegang oleh Eidos (yang sebelumnya memperoleh hak merek dari
Domark setelah merger pada tahun 1995). Perkembangan ini menyebabkan pengumuman
lebih lanjut bahwa game manajemen sepakbola Sports Interactive masa depan akan
dirilis dengan merk Football Manager. Sementara seri Manajer Championship akan
pergi, Eidos tidak lagi punya kode sumber, atau, memang tidak punya pengembang
untuk Championship Manager. Sampai saat ini sudah ada 10 versi Football Manager
dari tahun 2005 sampai yang terbaru 2014 ini.
Untuk pertama kalinya dalam
sejarah, game Football Manager 2014 akan dirilis untuk tiga platform sekaligus,
yaitu Linux, PC, dan Mac. Karena bisa dimainkan di berbagai sistem operasi
tersebut, maka Sport Interactive juga menyematkan fitur cloud save di dalamnya
sehingga para pemain dapat menyimpan game ini pada satu komputer dan kemudian
memainkannya lagi di komputer yang lain. Selain itu, pemain juga tidak perlu
khawatir game yang disimpan akan hilang atau rusak karena sudah disimpan dalam
cloud storage.
Gameplay
FM14
memiliki modul transfer berbeda di mana klub lawan dan manajer mengadopsi
pendekatan yang lebih realistis ketika membuat atau menanggapi transfer
penawaran. Selain itu, sejumlah klausul baru seperti pada dunia nyata telah
ditambahkan, seperti kemampuan untuk pinjaman pemain kembali ke klub yang baru
saja dibeli dari dan pilihan untuk menawarkan kombinasi kas dan pinjaman
pemain, serta klausul kontrak baru seperti biaya penampilan pemain
pengganti.
Interaksi
antara pemain, manajer, lawan dan media telah diperbaiki. Misalnya, anggota
staf pelatih sekarang menawarkan umpan balik tentang bagaimana pemain cadangan
dan tim muda berkinerja. Manajer juga dapat meminta pemain kunci untuk
mengucapkan sebuah kata dengan anggota skuad agar tetap bahagia, sedangkan
pengenalan pertemuan akhir musim memungkinkan manajer untuk membiarkan
skuad tahu bagaimana mereka akan melakukan dan menetapkan target untuk musim
mendatang. Negosiasi kontrak lebih realistis dalam permainan, sebagai manajer
dan dewan klub sekarang dapat membuat tuntutan dan memberikan visi mereka untuk
klub di wawancara pekerjaan awal dan diskusi perpanjangan kontrak.
Fitur
pertandingan memiliki perbaikan yang luas, termasuk peningkatan AI,
meningkatkan pencahayaan dan animasi pemain, karakter individu pemain dan model
kit, reaksi pemain yang lebih realistis untuk insiden di lapangan dan berbagai
optimisations. Penciptaan taktik, pemilihan dan pelaksanaan dengan peran pemain
dan strategi tim, definisi peran pemain untuk beberapa posisi, peran pemain
baru dan instruksi dan perbaikan manajer lawan 'AI telah dirombak sehingga para
manager dapat beradaptasi dengan mudah untuk merombak taktik dari waktu ke
waktu.
Awalnya
ada total 51 negara dimainkan dan 117 liga dimainkan. Dengan adanya editor
memungkinkan pemain untuk menambahkan liga ke tingkat yang paling rendah, serta
penciptaan liga baru.
Analisa Algoritma
Football
Manager merupakan game berjenis sport-strategy khususnya sepakbola yang bisa
dimainkan oleh berbagai kalangan. Game ini menarik karena mampu menggabungkan
hobi terhadap sepakbola dengan skill manajerisasi suatu tim. Mayoritas saat
ini, orang-orang yang gemar terhadap sepakbola hobi pula dalam bermain game.
Tentunya, sebagai manajer tim sepakbola, terdapat banyak tugas yang dapat
dikerjakan, seperti pemilihan skuad tim, pembelian dan penjualan pemain,
pemilihan formasi, pemilihan jadwal bertanding maupun pemilihan starting
line-up tiap pertandingan.
Dalam
terminologi pemilihan, pastilah manajer tersebut menginginkan hasil yang
optimal, yaitu yang terbaik untuk tim yang dilatihnya. Dalam pemilihan pemain
maupun formasi yang akan dipakai dalam setiap pertandingan, manajer dapat
menggunakan algoritma greedy untuk mencapai bentuk yang optimal tersebut.
Prinsip dari greedy yaitu “take what you can get now” mampu diaplikasikan dalam
pemilihan skuad tim maupun formasi. Dengan penggunaan algoritma greedy ini,
manajer mampu merancang skuad yang terbaik saat itu, meski bukan merupakan yang
optimal.
Pada
permainan Football Manager terdapat beberapa persoalan yang dapat diselesaikan
dengan metode greedy. Persoalan tersebut adalah penentuan skuad tim serta
pemilihan formasi. Dalam penentuan skuad tim, strategi greedy yang dapat
dilakukan adalah greedy by price dan greedy by skill. Sedangkan dalam persoalan
penentuan formasi, strategi greedy yang dapat dipakai adalah greedy by skill,
greedy by mood dan greedy by stamina. Pemakaian masing-masing strategi greedy
tidak menjamin skuad serta formasi yang paling optimal, namun dapat menjadi optimal
lokal saat itu serta sebagai konsiderasi untuk pemilihan selanjutnya bagi
manajer.
3.) Analisa pada Game Pacman
Teknikal
Pacman adalah
sebuah permainan video arkade yang cukup terkenal. Cara bermainnya mudah yaitu
pemain (pacman) diharuskan memakan makanan (berbentuk titik-titik kecil) dan
sebuah bulatan besar (energizer) sampai habis di dalam sebuah labirin yang
berliku-liku. Tidak hanya menghabiskan makanan tersebut, pemain juga harus
menghindari 4 ‘hantu’ yang berkeliaran secara random untuk menangkap pemain.
Jika pemain bertemu dengan hantu-hantu tersebut maka pemain dinyatakan gagal
dan harus mengulangi dari awal lagi. Tetapi pemain bisa mengalahkan hantu
tersebut dengan memakan energizer yang terdapat di pojokkan labirin. Jika
pemain memakan titik besar tersebut, maka para hantu akan ketakutan
dan berusaha menjauh dari pemain. Dalam hal ini pemain bisa memakan hantu
tersebut dan mendapatkan bonus yang besar, tetapi para hantu yang termakan
tidak mati begitu saja,mereka kembali ke posisi semula dan kembali mengejar
pemain. Pemain dinyatakan menang jika semua makanan habis tak tersisa dan
pemain akan memasuki level berikutnya.
Pergerakan
para hantu ini dipengaruhi oleh kecerdasan buatan atau
Artificialintelligence (AI), dimana para hantu diberi kecerdasan untuk
menentukan langkah dan mengambil keputusan akan bergerak kemana dengan
menentukan rute yang paling pendek (minimum), tujuannya adalah menangkap
pemain. Setiap hantu harus memiliki pemikiran berbeda dan memiliki kemampuan
bekerja sama untuk mengejar pemain, sehingga permainan akan tampak lebih
menarik. Persoalan mendekati karakter Pacman ini dapat diselesaikan dengan
berbagai macam cara, salah satunya dengan menggunakan algoritma
greedy. Untuk melakukan hal ini, kita harus memberikan prioritas yang
berbeda-beda pada masing-masing musuh, maka dengan sendirinya dia akan
bergerak ke arah yang berbeda.
Analisa Algoritma
Kami
akan menjelaskan cara kerja dari karakter musuh pacman tersebut dengan
memberikan salah satu contoh keadaan dalam permainan pacman. Pada
contoh kasus ini diasumsikan bahwa karakter Pacman tidak bergerak
(diam saja di tempat), untuk menentukan apakah rute yang
dipilih dari hasil algoritma greedy merupakan yang paling
optimum atau tidak. Berikut tampilannya :
Misal
fungsi seleksi gerakkanMusuh diterapkan pada musuh Pacman yang
berwarna oranye (gambar yang dilingkari). Posisi karakter musuh oranye berada
di sebelah kiri karakterPacman yang berwarna kuning, maka karakter musuh
oranye seharusnya bergerak ke kanan, namun karena adanya dinding yang
menghalangi, maka dilakukan pengecekan lagi terhadap perbandingan posisi Y dan
didapati posisi karakter musuh oranye berada di sebelah atas
karakter Pacman dan tidak ada dinding maupun karakter musuh lain yang
menghalangi di atasnya, maka karakter musuh oranye dipindahkan ke atas. Hasil
pergerakan pertama adalah sebagai berikut :
Setelah
itu, diterapkan lagi algoritma greedy untuk kedua kalinya,
posisi karakter oranye sekarang ada di sebelah kiri
karakter Pacman dan tidak ada yang menghalangi di sebelah kanannya,
jadi karakter musuh bisa bergerak ke kanan, seperti tampilan berikut
ini :
Setelah
bergerak ke kanan, algoritma greedy diterapkan lagi dan karakter
musuh berada di atas Pacman, maka karakter musuh digerakkan ke bawah
sampai bertemu dengan karakter Pacman : jarak yang ditempuh untuk
menemukan Pacman adalah jarak yang paling pendek. Untuk kasus ini,
algoritma greedy menghasilkan solusi yang optimal. Namun sesuai
dengan dasar teori, algoritma greedy tidak selalu dapat menghasilkan
solusi yang optimal karena algoritma greedy tidak memeriksa semua
kemungkinan.
Contoh
kasus berikut adalah kasus lain dari permainan pacman yang ternyata
tidak dapat diselesaikan secara optimum oleh algoritma greedy seperti
contoh kasus pertama di atas, namun solusi yang dihasilkan tidak terlalu buruk.
Pada
contoh kasus yang kedua, tetap diasumsikan bahwa karakter Pacman tidak
bergerak, selain itu, karakter musuh juga tidak ikut bergerak. Misal fungsi
seleksi diterapkan pada karakter musuh warna oranye. Pada gambar 5, karena
musuh oranye ada di sebelah kiri posisi Pacman, maka musuh digerakkan ke
kanan. Hasil pergerakan pertama sebagai berikut :
Setelah
digerakkan ke kanan, posisi karakter musuh masih tetap di sebelah kiriPacman,
namun musuh tidak bisa bergerak ke kanan lagi karena terhalang
dinding, setelah dicek, ternyata karakter musuh berada di sebelah
atas Pacman, maka sesuai dengan algoritmagreedy yang telah
ditetapkan, karakter musuh digerakkan ke bawah. Hasil pergerakan
kedua sebagai berikut :
Setelah
digerakkan ke bawah, posisi karakter musuh oranye ada di sebelah kiri dan di
bawah Pacman. Algoritma greedy diterapkan sekali lagi dan
karakter musuh seharusnya digerakkan ke kanan, namun karena ada karakter musuh
lainnya di sana, maka karakter musuh oranye digerakkan ke bawah sekali
lagi. Hasil pergerakan ketiga seperti berikut :
Pada
hasil pergerakan ketiga diatas, karakter oranye bergerak ke bawah sekali lagi,
dan dari sini terlihat bahwa rute yang ditempuh oleh karakter musuh oranye
sudah tidak mungkin menjadi optimal lagi jika dibandingkan dengan solusi
optimal (rute terpendek) seperti contoh kasus pertama. Berikut
tampilannya :
Kesimpulan
Solusi
yang telah dicapai oleh algoritma greedy hingga pada gambar 8 di atas
menunjukkan bahwa algoritma greedy yang dipilih ternyata tidak selalu
menghasilkan solusi yang paling optimal. Namun demikian, karena objektif dari
karakter musuh Pacman ini tidak harus selalu bergerak pada rute yang
merupakan solusi paling optimum, maka algoritmagreedy cukup baik
untuk mendapatkan hampiran-hampiran yang mendekati solusi paling optimum
tersebut.
4.)Analisa pada Game Tetris
Teknikal
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.
Analisa Algoritma
Pemain dapat mengontrol balok tetris yang jatuh melalui 4 tombol
arah panah untuk menggeser ke kanan atau ke kiri dan tombol arah panah ke bawah
untuk mempercepat jatuhnya balok tetris. Satu kendali yang lain adalah untuk
memutar bentuk balok tetris 90ยบ’
Algoritma yang gunakan untuk mencari solusi dari permainan
tetris adalah algoritma yang menggunakan konsep-konsep yang ada dalam algoritma
Greedy dan Algoritma BruteForce.Algoritma Greedy merupakan metode yang paling
umum digunakan untuk memecahkan masalah optimasi.Algoritma ini sederhana dan
sesuai dengan tujuan yang ada.
Algoritma
Greedy memecahkan masalah langkah per langkah, 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 bahwa dengan memilih optimum local pada setiap langkah akan berakhir dengan optimum global Brute force adalah sebuah pendekatan yang sesuai (straightforward) untuk memecahkan 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 sollusi yang paling menguntungkan. Prioritas keuntungan yang tersusun terdiri dari:
1. Membentuk
satu atau lebih baris paling penuh
2. Membentuk satu
atau lebih baris paling mendekati penuh
3. Tidak
membentuk ruang kosong pada susunan tumpukan balok
4. 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.
Algoritma
ini akan mencari penempatan yang sesuai dengan prioritas di atas. Pencarian
solusi diantara susunan tumpukan balok akan dilakukan secara Brute
Force. Algoritma ini akan mencari solusi paling menguntungkan untuk
setiap sisi balok yang sedang jatuh. Pencarian solusi untuk setiap sisi
dilakukan secar Brute Force. Apabila pada skala prioritas tertinggi
memiliki lebih dari satu solusi terbaik yang sama, maka diantara solusi
tersebut akan dibandingkan satu sama lain untuk mencari yang paling
menguntungkan dengan standard prioritas selanjutnya, dan begitu selanjutnya.
Apabila pada skala prioritas tertinggi tidak memiliki solusi, maka akan mencari
solusi paling menguntungkan dengan skala prioritas selnjutnya, dan begitu
selanjutnya. Apabila pada skala prioritas tertinggi hanya memiliki satu solusi
paling menguntungkan, maka akan dibandingkan dengan solusi dari
hasil pencarian solusi untuk sisi balok yang lain. Diantara setiap solusi sisi
balok, dicari solusi yang paling menguntungkan sesuai skala prioritas di atas.
Dan balok akan ditempatkan pada ruang tersebut.
Apabila
ada kasus seperti diatas, maka algoritma tersebut akan mencari solusi yang
paling menguntungkan untuk menempatkan balok tersebut ke ruang di antara
susunan tumpukan balok. Pencarian dicari secara brute force dari kiri ke kanan
untuk sisi yang pertama kali keluar.Dapat dilihat seperti gambar berikut, bahwa
lgoritma seakan-akan menempatkan balok tersebut dari kiri ke kanan untuk balok
dengan sisi tersebut.
Apabila
ada kasus seperti diatas, maka algoritma kami akan mencari solusi yang paling
menguntungkan untuk menempatkan balok tersebut ke ruang di antara susunan
tumpukan balok. Pencarian dicari secara brute force dari kiri ke kanan untuk
sisi yang pertama kali keluar.Dapat dilihat seperti gambar berikut, bahwa lgoritma
seakan-akan menempatkan balok tersebut dari kiri ke kanan untuk balok dengan
sisi tersebut.
Setelah
algoritma ini mancari solusi sampai paling kanan, maka algoritma ini akan
menyimpan satu solusi terbaik yang ada. Apabila ada beberapa solusi yang sama baiknya,
maka akan diambil penempatan paling kiri, seperti dilihat dibawah ini.
Setelah
menyimpan solusi terbaik untuk sisi tersebut, maka algoritma ini akan mulai
mencari solusi optimum untuk sisi berikutnya. Tampak di bawah, algoritma in
seakan-akan memutar balok untuk memulai pencarian sisi berikutnya.Sisi berikut
yang kami maksud disini adalah sisi dimana balok yang sedang jatuh diputar 900
searah jarum jam.
Setelah
itu, algoritma ini akan menyimpan solusi dari setiap sisi berikutnya, seperti
terlihat pada tiga gambar berikut ini.
Diantara
setiap solusi sisi balok, dicari solusi yang paling menguntungkan sesuai skala
prioritas di atas. Dan balok akan ditempatkan pada ruang tersebut. Seperti
terlihat pada gambar berikut, algoritma ini telah menemukan solusi terbaik, dan
menempatkan balok pada ruang tersebut.
Penggunaan Matriks dalam pembuatan Tetris
Pada
game tetris, terdapat blok-blok yang akan kita susun secara horizontal ataupun vertikal
blok-blok tersebut dinamakan dengan grid. Jumlah tiap baris grid tergantung
pada si pembuat tetris, kalo contoh yang kami gunakan berjumlah 15 grid.Grid
tersebut pada pemrograman kita buat dengan menggunakan matriks berdimensi 2.
Contoh
:
___________________
o o o o
o o o o
o o o o
__________________
Sebagai contoh gambar diatas adalah
matriks ukuran 4x3 (4 kolom, 3 baris).Begitu pula pada tetris juga memiliki
ukuran kolom x baris (m x n). Pada kolom 1 baris 1, memiliki index[0,0]. Pada
kolom 1 baris 2, memiliki indexnya[0,1]. Pada kolom 1 baris 3, memiliki
index[0,2]. Pada kolom 2 baris 1, itu indexnya[1,0]. Pada kolom 2 baris 2,
itu indexnya[1,1] dan s seterusnya. Di sini kami anggap
susunannya terlihat seperti pada matriks dibawah ini :
[0,0] [0,1] [0,2] [0,3]
[1,0] [1,1] [1,2] [1,3]
[2,0] [2,1] [2,2] [2,3]
Baris paling atas pada
tetris (baris 1) memiliki index [0,n] sampai [0,n+1]. Sehingga dapat
kita anggap ukuran layar tetris [m,n]. Setiap ada blok yang turun atau
berjatuhan kita definisikan sebagai, m+1 dan setiap bergeser kekanan n+1 dan
setiap kekiri n-1
Pada permainan tetris ini apabila
blok yang berjatuhan telah melampaui batas dari layar tetris [m,n] maka
permainan akan berakhir (game over) sehingga apabila ada baris yang penuh
(sesuai dengan syarat) maka baris tersebut akan dihapus.
5.)Analisa pada Game Tic Tic Toe
Teknikal
Perkembangan teknologi dalam dunia komputer semakin hari semakin lebih maju, komputer yang dulunya berfungsi sebagai alat hitung dan pengolah data, seiring perkembangan teknologi komputer saat ini tidak hanya bertindak sebagai mesin yang hanya disuruh namun mampu berfikir memberikan respon bagi pengguna, sehingga muncul istilah ArtificialIntellegence (AI) atau Kecerdasan Buatan. Methohe Minimax merupakan salah satu contoh dari method yang digunakan dalam kecerdasan buatan, minimax adalah suatu algoritmayang menggunakan teknik pencarian Depth-First Search dengan kedalaman terbatas. Adapun media yangcocok untuk penerapan algoritma minimax adalah permainan Tic-Tac-Toe, beberapa alasan mengapa Tic-Tac-Toe digunakan sebagai media penerapan kecerdasan buatan antara lain Tic-Tac-Toe sangat mudahmenentukan ukuran kesuksesan atau kegagalan, sangat mungkin untuk dibandingkan dengan kemampuan manusia, mudah dimainkan.
Permainan tic-tac-toe merupakan permainan berjenis board-game berukuran 3x3. Pemain harus mengisi sel-sel, sehingga karakter yang dimasukkan pemain tersebut dapat membentuk suatu garis lurus horizontal, vertikal, ataupun juga diagonal. Permainan ini biasanya dimainkan oleh 2 orang pemain, tapi pada versi permainan komputer, pemain lawan dapat digantikan oleh komputer. Hasil permainan berupa menang, kalah, ataupun seri.
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 ini 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 yang paling membuat komputer itu sendiri mendapatkan keuntungan maksimum. Dalam penentuan keputusan pada algorima minimax digunakan sebuah fungsi heurisitic untuk mengevaluasi nilai sebagainilai 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 pohon permainan yang akan dipilih, tentunya simpul yang akan dipilih tersebut adalah simpul dengan nilai heuristicyang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer.
Perkembangan teknologi dalam dunia komputer semakin hari semakin lebih maju, komputer yang dulunya berfungsi sebagai alat hitung dan pengolah data, seiring perkembangan teknologi komputer saat ini tidak hanya bertindak sebagai mesin yang hanya disuruh namun mampu berfikir memberikan respon bagi pengguna, sehingga muncul istilah ArtificialIntellegence (AI) atau Kecerdasan Buatan. Methohe Minimax merupakan salah satu contoh dari method yang digunakan dalam kecerdasan buatan, minimax adalah suatu algoritmayang menggunakan teknik pencarian Depth-First Search dengan kedalaman terbatas. Adapun media yangcocok untuk penerapan algoritma minimax adalah permainan Tic-Tac-Toe, beberapa alasan mengapa Tic-Tac-Toe digunakan sebagai media penerapan kecerdasan buatan antara lain Tic-Tac-Toe sangat mudahmenentukan ukuran kesuksesan atau kegagalan, sangat mungkin untuk dibandingkan dengan kemampuan manusia, mudah dimainkan.
Permainan tic-tac-toe merupakan permainan berjenis board-game berukuran 3x3. Pemain harus mengisi sel-sel, sehingga karakter yang dimasukkan pemain tersebut dapat membentuk suatu garis lurus horizontal, vertikal, ataupun juga diagonal. Permainan ini biasanya dimainkan oleh 2 orang pemain, tapi pada versi permainan komputer, pemain lawan dapat digantikan oleh komputer. Hasil permainan berupa menang, kalah, ataupun seri.
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 ini 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 yang paling membuat komputer itu sendiri mendapatkan keuntungan maksimum. Dalam penentuan keputusan pada algorima minimax digunakan sebuah fungsi heurisitic untuk mengevaluasi nilai sebagainilai 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 pohon permainan yang akan dipilih, tentunya simpul yang akan dipilih tersebut adalah simpul dengan nilai heuristicyang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer.
Garis besar algoritma minimax secara umum
"If ada langkah kemenangan Then pilih langkah tersebut.
Else Ifl awan mempunyai 2 spot terisi dalam satu garis dengan spot ketiga masih kosong Then tutup langkah tersebut (isi spot kosong ketiga tersebut).
Else melangkah ke state yang mempunyai kemungkinan menang tertinggi (berdasarkan nilai heuristic yang dibangkitkan)"
Algoritma umum diatas untuk permainan tic-tac-toe
"Mencari langkah dengan nilai maksimum
If langkah tersebut merupakan langkah kemenangan Then pilih lagkah tersebut.
Else
Foreach kemungkinan langkah yang ada
Cari langkah lawan yang bernilai minimum.
Return nilai dari langkah tersebut.
Pilih langkah yang bernilai maksimum darilangkah-langkah tersebut. "
Analisa Algoritma
Analisis dalam kasus ini, pada permainan tic-tac-toe menggunakan algoritma minimax, dimana AI akan menelusuri semua kemugkinan langkah yang akan dilakukan oleh pemain. SehinggaAI akan selalu mengetahui kemungkinan pemain untuk menang dan memblok semua langkah kemenangan pemain.
Dengan demikian permainan akan selalu seri apabila pemain cukup teliti dalam menentukan langkah. Namun jika pemain melakukan langkah yang salah, maka AI akan langsung menggunakan kesempatan tersebut untuk mengambil langkah yang akan mengarahkannya ke hasil akhir berupa kemenangan atau seri.
Berikut adalah langkah atau cara memainkan permainan tic–tac-toedengan metode minimax.
Kesimpulan
Penerapan algoritma minimax cukup bagus dan cocok untuk pengambilan
keputusan oleh AI, terutama dalam permainan player. Algoritma minimax menggunakan konsep Dept First Search dalam pembentukan pohon solusi. Pohon solusi dibentuk dari awal permainan sampai akhir permainan. Semakin akurat fungsi dari heuristic yang digunakan, semakin baik pula pengambilan keputusan yang dilakukan oleh AI. Dengan menggunakan algoritma minimax untuk AI dalam permainan tic-tac-toe, pemain kemungkinan sangat kecil untuk menang melawan AI tersebut.
Sumber :
Munir,
Rinaldi.2006. “Strategi Algoritmik”. Program Studi Informatika, Institut
Teknologi Bandung. Kevin McGee, 2005. “Advance Game Programming : AI”.
Khoirush Sholih, 2010. Jurnal Implementasi Teori Minimax pada Tic Tac Toe. Teknik Informatika. Institut Teknologi Bandung.
Wikimedia Foundation, Inc. “Depht First Search”. http://en.wikipedia.org/wiki/DFS_search_algorithm.
Khoirush Sholih, 2010. Jurnal Implementasi Teori Minimax pada Tic Tac Toe. Teknik Informatika. Institut Teknologi Bandung.
Wikimedia Foundation, Inc. “Depht First Search”. http://en.wikipedia.org/wiki/DFS_search_algorithm.
Birch,
Chad (2010), Understanding Pac-Man Ghost Behaviour (http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior)
Pittman,
jamey (2010), Pac-Man Dossier (http://home.comcast.net/~jpittman2/pacman/pacmandossier.html)
Nugroho
Chandra, Timotius (2010), Aplikasi Algoritma Greedy untuk
Pergerakan Musuhpada Pac-Man, Institut Teknologi Bandung, Bandung .
http://en.wikipedia.org/wiki/Football_Manager_2014
http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2012-2013/Makalah2012/Makalah-IF3051-2012-072.pdf
