BAB I
PENDAHULUAN
1.1
Latar Belakang
Bermain game merupakan salah satu aktifitas yang sangat
disukai oleh sebagian besar masyarakat di dunia ini. Alasan mereka bermain game
tentunya berbeda-beda, ada yang untuk melepas lelah, ada juga yang memang suka
atau hobi bermain game. Dengan berkembangnya teknologi sekarang ini, game –
game ini tidak hanya dapat kita jumpai pada kehidupan nyata, tapi juga dapat
kita jumpai d idalam dunia maya. Jenis nya pun semakin banyak dan bervariasi.
Salah satu yang cukup menarik perhatian adalah permainan komputer.
Permainan-permainan berbasis komputer ini juga bermacam-macam. Salah satu
kelebihannya adalah kita tidak harus mencari orang untuk menjadi lawan tanding
jika ingin bermain karena permainan berbasis komputer ini sudah mendukung
single-player mode dimana kita dapat bermain sendiri melawan komputer yang
dirancang untuk dapat berlaku seperti pemain manusia atau yang sering dikenal
dengan Artificial Inteligince (AI). Contoh – contoh permainan yang menggunakan
AI adalah permainan catur, go, othello, checkers, bridge, tic-tac-toe dan lain
sebagainya. Untuk membuat pemain merasa seperti melawan pemain manusia lainnya,
diperlukan suatu algoritma yang dapat membuat AI ini mampu mengambil keputusan
yang terbaik agar dapat mengalahkan pemain atau setidaknya menghalau pemain
menang. Algoritma minimax ini merupakan algoritma yang sangat sering dipakai
untuk permasalah tersebut. Dan permainan tic-tac-toe merupakan salah satu
contoh yang baik dan cukup sederhana untuk kita mengerti bagaimana cara kerja
dan efeknya.
1.2
Identifikasi Masalah
Algoritma minimax merupakan algoritma yang cukup terkenal
dalam bidang kecerdasan buatan. Dimana dengan algoritma tersebut komputer dapat
mengambil keputusan terbaik untuk menyelesaikan masalah. Masalah yang akan
diangkat disini adalah AI untuk permainan tic-tac-toe , dimana AI tersebut
tidak akan pernah kalah. Dengan algoritma minimax ini, pohon solusi akan dibuat
dari awal permainan sampai akhir permainan dimana semua kemungkinan kondisi
dijadikan simpul dari pohon solusi, sehingga AI tinggal memilih langkah yang
akan menuntunnya ke hasil akhir berupa kemenangan atau setidaknya seri.
1.3
Batasan Masalah
Linkup permasalahan yang akan dibahas pada makalah ini
adalah penggunaan algoritma minimax untuk membuat AI yang dapat mencari dan
menentukan keputusan terbaik dalam permainan tic-tac-toe sedemikian sehingga AI
tersebut tidak akan pernah kalah.
1.4
Maksud dan Tujuan Penelitian
Adapun
maksud dari penelitian ini adalah mengetahui penggunaan algoritma minimax untuk
membuat AI yang dapat mencari dan menentukan keputusan terbaik. Dan tujuan dari
penelitian ini adalah dengan menggunakan algoritma minimax diharapkan dapat menentukan
keputusan terbaik dalam permainan tic-tac-toe sedemikian sehingga AI tersebut
tidak akan pernah kalah.
1.5
Metode Penelitian
Metode penelitian merupakan suatu mekanisme,
teknik atau cara untuk mencari, memperoleh, mengumpulkan, atau mencatat data
yang dapat digunakan untuk menyusun karya ilmiah atau penelitian dengan
prosedur yang didasarkan pada suatu struktur logis yang terdiri dari beberapa
tahapan kerja dan kemudian menganalisa faktor-faktor yang berhubungan dengan
pokok-pokok permasalahan sehingga akan didapat suatu kebenaran atas data yang
diperoleh. Penyusunan makalah ini menggunakan metode deskriptif, yaitu
mengumpulkan data kemudian menganalisanya serta memaparkan hasil penelitian.
1.6
Sistematika Penulisan
Sistematika
Penulisan laporan skripsi terdiri dari VI BAB dengan perincian sebagai berikut
:
BAB I Pendahuluan
Pada bab ini menguraikan
tentang gambaran umum dari makalah yaitu latar belakang, identifikasi masalah,
batasan masalah, maksud dan tujuan penelitian, metode penelitian, serta
sistematika penulisan.
BAB II Landasan
Teori
Pada bab ini memaparkan teori-teori dan
landasan pengetahuan yang relevan dengan makalah ini. Berisikan teori Game
AI, Permainan tic-tac-toe serta
teori-teori yang berhubungan dengan permasalahan yang dibahas.
BAB III Algoritma Minimax
Pada bab ini akan diuraikan
mengenai algoritma minimax, bagaimana algoritma minimax dalam aplikasi
permainan tic-tac-toe.
BAB IV Implementasi Algoritma Minimax
Pada bab ini membahas bagaimana algoritma
minimax diimplementasikan ke dalam permainan tic-tac-toe..dan hasil analisis
dari algoritma minimax dalam permainan tic-tac-toe.
BAB V Hasil Analisis
Pada
bab ini berisi tentang hasil analisis dari algoritma minimax terhadap permainan
tic-tac-toe.
BAB VI Kesimpulan dan Saran
Pada bab ini berisi
tentang kesimpulan dan saran yang diajukan agar dapat menjadi bahan
pertimbangan.
BAB II
LANDASAN TEORI
2.1 Game AI
Game AI adalah aplikasi IB untuk memodelkan
karakter yang terlibat dalam permainan baik sebagai lawan, ataupun karakter
pendukung yang merupakan bagian dari permainan tetapi tidak 'ikut bermain' (NPC
~ Non Playable Characters). Ada beberapa karakter dalam game AI yaitu:
1. Karakter antagonis (Opponent AI)
Karakter antagonis adalah karakter yang dalam permainan
memiliki tujuan yang sama dengan pemain yaitu memenangkan permainan. untuk
mewujudkan tujuan ini karakter tersebut dapat melakukan aksi kepada pemain dan
sebaliknya pemain dapat melakukan aksi kepada karakter lawan yang sesuai dengan
aturan permainan. contoh sederhana dari karakter antagonis adalah dalam
permainan pertarungan (fighting). karakter lawan adalah karakter yang harus
'dikalahkan' oleh pemain dengan melakukan aksi (serangan). fungsi IB pada
karakter antagonis adalah melakukan aksi-aksi yang dapat memperbesar peluang
karakter tersebut untuk menang.
2. Karakter Pendukung (NPC AI)
karakter pendukung (NPC ~ Non-Playable Characters)
merupakan karakter yang terlibat dalam permainan tetapi tidak memiliki tujuan
untuk memenangkan permainan melainkan melakukan peran yang mendukung
pemain/lawan untuk memenangkan permainan. contoh sederhana dari NPC AI adalah pada
game RPG. Karakter NPC pada permainan bergenre RPG pada umumnya memberikan
informasi implisit kepada karakter tentang hal-hal yang berkaitan dengan cerita
dalam permainan ataupun panduan bagi pemain mengenai tujuan permainan. fungsi
IB pada karakter pendukung adalah menentukan dialog dengan pemain sedemikian
rupa sehingga seolah-olah karakter tersebut tampak nyata bagi pemain (life-like).
Peranan IB dalam hal interaksi pemain dengan permainan
adalah pada penggunaan interaksi yang bersifat alami yaitu yang biasa digunakan
manusia untuk berinteraksi dengan sesama manusia. contoh-contoh media interaksi
antara lain :
a. penglihatan (Vision)
Untuk menggunakan informasi penglihatan biasanya
menggunakan kamera sebagai perangkat untuk mendapatkan data. data yang
ditangkap adalah berupa gambar / citra yang merupakan matriks dua dimensi.
matriks tersebut dianalisa sesuai dengan kebutuhan aplikasi sehingga didapatkan
informasi yang diinginkan (misal pembentukan wajah, deteksi gerakan,
rekonstruksi ruang).
b. suara (voice) atau ucapan
(speech)
Informasi suara didapatkan dari microphone yang
menghasilkan informasi dalam bentuk deretan angka (disebut sebagai sample).
Persoalan utama dari suara adalah informasi yang dikandung memiliki variasi
yang sangat besar yang disebabkan oleh faktor alat dan faktor manusia (vokal,
intonasi, intensitas, dll). Penerapan interaksi dengan menggunakan suara
misalnya untuk permainan bergenre RTS (wargames) yang menterjemahkan perintah
dari pemain untuk menggerakkan unit. Contoh lainnya adalah permainan balap
kendaraan yang menentukan akselerasi dari suara pemain yang menirukan suara
mesin.
c. gerakan anggota badan
(gesture)
Gesture adalah gerakan sebagian anggota badan yang
memiliki makna tertentu (disebut juga sebagai body language). Informasi gesture
dapat diakuisisi dengan berbagai cara, diantaranya :
1. video (vision)
informasi deretan koordinat
(gerakan) dihasilkan dari analisis terhadap rangkaian gambar terurut (video).
2. sensor jarak (range)
informasi deretan koordinat
diukur dengan menggunakan sensor jarak.
3. sensor posisi yang menempel
pada pemain
akhir-akhir ini beberapa
produsen konsol memanfaatkan pengendali (controller) yang dapat menghasilkan
informasi posisi /perubahan posisi pengendali pada ruang tiga dimensi. Salah
satu contoh konsol yang menggunakan ini adalah Nintendo Wii.
2.2 Permainan Tic-Tac-Toe
Permainana tic-tac-toe merupakan permainan
berjenis board-game berukuran 3x3. Pemain harus mengisi sel-sel tersebut
sedemikian 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. Dalam permainan ini hasilnya dapat
berupa
menang,kalah, ataupun seri.
Disini dengan adanya AI yang mampu meminimalisir
kemungkinan untuk pemain menang, permainan ini akan menjadi sangat sulit untuk
dimenangkan oleh pemain. Bahkan kemungkinan terbaik untuk pemain hanyalah seri.
Dengan kata lain dengan menggunakan algoritma minimax ini, komputer tidak akah
pernah kalah.
Berikut contoh permainan tic-tac-toe :
Gambar 2.1 Contoh
kondisi menang pada permainan tic-tac-toe
Gambar 2.2 Contoh kondisi seri pada permainan
tic-tac-toe
BAB III
ALGORITMA MINIMAX
Algoritma minimax merupakan basis dari semua permainan
berbasis AI seperti permainan catur misalnya. AI permainan catur tentunya sudah
sangat terkenal dimana AI tersebut bahkan dapat mengalahkan juara dunia
sekalipun. 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.
Berbeda dengan permainan catur, permainan tic-tac-toe ini
mempunyai lebih sedikit kemungkinan solusi, sehingga kita akan mempunyai cukup
komputasi untuk memainkan setiap kombinasi langkah dari setiap posisi dan
kondisi. Namun hal ini dapat dihindari dengan membatasi sejauh mana komputer
akan menganalisis hasil dari langkahlangkah yang mungkin (menentukan kedalaman
pohon). Tetapi dengan hal ini, kita harus menambah kedalaman pohon tersebut
setiap langkahnya agar kedalaman pohon pada state tersebut sama dengan state
sebelumnya.
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. Untuk itulah disini digunakan sebuah fungsi
heurisitic untuk mengevaluasi nilai sebagai nilai yang merepresentasikan hasil
permainan yang akan terjadi jika langkah tersebut dipilih. Biasanya 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 heuristic
yang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer.
Dilihat dari algoritma diatas,
nilai heuristic yang dibangkitkan akan sangat mempengaruhi analisis dari AI
tersebut. Oleh karena itu, semakin bagus fungsi heuristic maka semakin bagus
pula analisis AI tersebut, dan semakin sulit pula AI untuk dikalahkan.
BAB IV
IMPLEMENTASI ALGORITMA MINIMAX
Anggaplah ada 2 pemain A dan B. Jika pemain A bisa menang
dalam 1 langkah, maka langkah tersebut adalah langkah kemenangannya. Jika
pemain B mengetahui bahwa langkah tersebut akan mengarahkan ke hasil akhir
dimana pemain A akan menang, dan di lain kondisi ada langkah lain yang akan
mengarahkan ke hasil akhir seri, maka langkah terbaik untuk pemain B adalah
langkah yang akan mengarahkan hasil akhir permainan ke hasil seri. Di setiap
tahap algoritma ini mengasumsikan bahwa pemain A mencoba untuk memaksimalisasi
peluang menang. Di lain pihak, pada giliran berikutnya pemain B akan mencoba
meminimalisir peluang menang untuk pemain A. Oleh karena itu, A disebut juga
maximizing player (MAX) dan B disebut juga minimizing player
(MIN).
Pembentukan pohon pencarian solusi digunakan dengan
menggunakan konsep depth-first, dimulai dari awal permainan sampai akhir
permainan. Setelah itu, posisi akhir permainan dievaluasi melalui sudut pandang
MAX seperti gambar dibawah ini :
Gambar
3.1. Representasi pohon pencarian pada algoritma minimax.
Setelah itu nilai dari setiap simpul diisi dari bawah ke
atas dengan nilai yang sudah dievaluasi oleh fungsi heuristic. Simpul milik
pemain A (MAX) menerima nilai maksimum dari simpul-simpul anaknya. Simpul milik
pemain B (MIN) akan memilih nilai minimum dari simpul anak-anaknya. 5 Berikut
pseudocode dari algoritma yang digunakan :
MinMax
(GamePosition game) {
return MaxMove
(game);
}
MaxMove (GamePosition
game) {
if
(GameEnded(game)) {
return
EvalGameState(game);
}
else {
best_move < -
{};
moves <-
GenerateMoves(game);
ForEach moves {
move <-
MinMove(ApplyMove(game));
if (Value(move)
> Value(best_move)){
best_move < -
move;
}
}
return best_move;
}
}
MinMove
(GamePosition game) {
best_move <-
{};
moves <-
GenerateMoves(game);
ForEach moves {
move <-
MaxMove(ApplyMove(game));
if (Value(move)
> Value(best_move)){
best_move < -
move;
}
}
return best_move;
}
Values disini merepresentasikan sebagaimana bagusnya
suatu langkah dalam permainan. Jadi, pemain A (MAX) akan memilih langkah dengan
nilai paling tinggi diakhir. Di sisi lain, pemain B (MIN) akan melakukan
serangan balik dengan memilih langkah yang terbaik untuknya, yakni
meminimalisir hasil dari langkah yang dipilih pemain A.
BAB V
HASIL ANALISIS
AI akan selalu
memilih langkah yang dapat meminimalisir kemungkinan pemain (manusia) 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.
BAB VI
KESIMPULAN DAN SARAN
1.
Algoritma
minimax merupakan algoritma yang sangat bagus dan cocok untuk pengambilan keputusan
oleh AI, terutama dalam permainan nplayer (n>=2).
2.
Algoritma
minimax menggunakan konsep DFS dalam pembentukan pohon solusi.
3.
Pohon
solusi dibentuk dari awal permainan sampai akhir permainan.
4.
Untuk
permainan yang terbilang cukup kompleks seperti permainan catur, pembentukan
pohon solusi dari awal permainan sampai akhir permainan akan sulit
direalisasikan berhubung kemungkinan yang ada sangat besar.
5.
Oleh
karena itu, kita dapat membatasi dalamnya pohon solusi pada suatu tahap untuk
mempercepat kinerja pengambilan keputusan.
6.
Semakin
akurat fungsi heuristic yang digunakan, semakin baik pula pengambilan keputusan
yang dilakukan oleh AI.
7.
Dengan
menggunakan algoritma minimax untuk AI dalam permainan tic-tac-toe, pemain
(manusia) tidak akan pernah menang melawan AI tersebut.
DAFTAR PUSTAKA
Munir,
Rinaldi.2006. “Strategi Algoritmik”. Program Studi Informatika, Institut Teknologi Bandung.
Kevin McGee, “Advance Game
Programming : AI”, Desember 9, 2005.
Wikimedia Foundation, Inc. “A *
Search Algorithm”. http://en.wikipedia.org/wiki/Astar_search_algorithm.
www.stancford.edu~msirotasocominimax.html
http://ai-depot.com/articles/minimaxa-explained/1/
Untuk download Makalahnya anda bisa download di bawah ini :
Post a Comment