Kelompok
Abyantama El AP
Dwiko Darmawan
Gilang Agung H
Laurentius Elno B
Raymond Dwipa G
3KA15
Kecerdasan buatan
Kecerdasan
Buatan atau kecerdasan yang ditambahkan kepada suatu sistem yang bisa diatur
dalam konteks ilmiah atau Intelegensi Artifisial (bahasa Inggris: Artificial
Intelligence atau hanya disingkat AI) didefinisikan sebagai kecerdasan entitas
ilmiah. Sistem seperti ini umumnya dianggap komputer. Kecerdasan diciptakan dan
dimasukkan ke dalam suatu mesin (komputer) agar dapat melakukan pekerjaan
seperti yang dapat dilakukan manusia. Beberapa macam bidang yang menggunakan
kecerdasan buatan antara lain sistem pakar, permainan komputer (games),
logika fuzzy, jaringan syaraf tiruan dan robotika.
Penelitian
dalam AI menyangkut pembuatan mesin untuk mengotomatisasikan tugas-tugas yang
membutuhkan perilaku cerdas. Termasuk contohnya adalah pengendalian,
perencanaan dan penjadwalan, kemampuan untuk menjawab diagnosa dan pertanyaan
pelanggan, serta pengenalan tulisan tangan, suara dan wajah. Hal-hal seperti
itu telah menjadi disiplin ilmu tersendiri, yang memusatkan perhatian pada
penyediaan solusi masalah kehidupan yang nyata. Sistem AI sekarang ini sering
digunakan dalam bidang ekonomi, obat-obatan, teknik dan militer, seperti yang
telah dibangun dalam beberapa aplikasi perangkat lunak komputer rumah dan video
game.
Sejarah Artificial Intelligence
dalam Game
Pada
tahun 1769, dataran Eropa dikejutkan dengan suatu permainan catur yang dapat
menjawab langkah-langkah permainan catur yang belum ditentukan terlebih dahulu.
Mesin ini disebut dengan Maelzel Chess Automation dan dibuat oleh Wolfgang Von
Kempelan (1734-1804) dari Hungaria. Akan tetapi mesin ini akhirnya terbakar
pada tahun 1854 di Philadelphia Amerika Serikat.banyak orang tidak percaya akan
kemampuan mesin tersebut. Dan seorang penulis dari Amerika Serikat, Edgar Allan
Poe (1809-1849) menulis sanggahan terhadap mesin tersebut, dia dan
kawan-kawannya ternyata benar, bahwa mesin tersebut adalah tipuan, dan
kenyataannya bukanlah aoutomation, tetapi merupakan konstruksi yang sangat baik
yang dikontrol oleh seorang pemain catur handal yang bersembunyi di dalamnya.
Usaha
untuk membuat konstruksi mesin permainan terus dilanjutkan pada tahun 1914, dan
mesin yang pertama kali didemonstrasikan adalah mesin permainan catur. Penemu
mesin ini adalah Leonardo Torres Y Quevedo, direktur dari Laboratorio de
Automatica di Madrid, Spanyol. Beberapa tahun kemudian, ide permainan catur
dikembangkan dan diterapkan di komputer oleh Arthur L. Samuel dari IBM dan
dikembangkan lebih lanjut oleh Claude Shannon.
Artificial
Intelligence dalam Game
Salah
satu unsur yang berperan penting dalam sebuah game adalah kecerdasan buatan.
Dengan kecerdasan buatan, elemen-elemen dalam game dapat berperilaku sealami
mungkin layaknya manusia.
Game
AI adalah aplikasi 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 Character). Peranan kecerdasan
buatan dalam hal interaksi pemain dengan permainan adalah pada penggunaan
interaksi yang bersifat alami yaitu yang biasa digunakan menusia untuk
berinteraksi dengan sesama manusia. Contoh media interaksi ialah:
·
Penglihatan (vision)
·
Suara (voice), ucapan (speech)
·
Gerakan anggota badan ( gesture)
Untuk
pembentukan Artificial Intelligence pada game ternyata digunakan pula algoritma,
yaitu
jenis pohon n-ary untuk suatu struktur. Implementasi pohon (tree) ini
biasa disebut game tree. Berdasarkan game tree inilah sebuah game disusun
algoritma kecerdasan buatannya. Artificial intellegence yang disematkan dalam
sebuah game yang membentuk analisis game tree biasanya merepresentasikan
kondisi atau posisi permainan dari game sebagai suatu node, dan
merepresentasikan langkah yang mungkin dilakukan sebagai sisi berarah yang
menghubungkan node kondisi tersebut ke anak (child) sebagaimana representasi
suatu pohon (tree).
Namun,
biasanya representasi langsung tersebut mempunyai kelemahan, yaitu representasi
data pohon akan menjadi sangat lebar dan banyak. Mungkin bagi sebuah mesin
komputer mampu melakukan kalkulasi sebanyak apapun masalah, namun game tree
yang lebar dan besar memberikan beberapa masalah, antara lain konsumsi proses
memori, kapasitas penyimpanan yang cukup besar dan kinerja yang kurang pada
konsol game berspesifikasi rendah. Karena itu dibentuklah beberapa algoritma
dan penyederhanaan bagi sebuah game tree.
Pada
salah satu contoh game klasik, yaitu tic tac toe, penyederhanaan dapat
dilakukan dengan berbagai metode. Salah satu diantaranya adalah minimax.
Metode ini berhasil diterapkan dan memberikan nilai reduksi yang cukup signifikan.
Dan tidak hanya bisa digunakan secara monoton, minimax juga bisa digunakan
untuk game-game yang lebih rumit seperti catur, tentunya dengan algoritma dan
representasi berbeda. Selain itu ada beberapa metode yang lain yang bisa
dipakai dalam pembuatan games.
Apa itu Algoritma Minimax ?
Minimax
yang merupakan salah satu metode penerapan (implementasi) pohon n-ary pada
suatu game, menandakan bahwa implementasi struktur (pohon khusunya) sangatlah
diperlukan pada pembuatan dan penerapan Artificial Intelligence, dan tidak
menutup kemungkinan ilmu dan metode baru yang lebih canggih akan ditemukan di
masa depan.
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. 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.
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.
Algoritma
minimax merupakan algoritma yang diterapkan dalam game yang melibatkan dua
pemain yang saling bergantian, seperti tic-tac-toe, chess, go, othello dan game
yang menggunakan strategi atau logika lainnya. Persamaan antara semua game
tersebut yaitu semua merupakan game logika dan game dengan informasi yang
lengkap. Ini berarti bahwa game merupakan sekumpulan aturan main dan dasar
pemikiran yang logis. Adanya aturan main dan dasar pemikiran yang logis
tersebut, maka nantinya setiap pemain dapat mengetahui semua langkah yang
mungkin dari pemain lawannya, sehingga pemain bisa tetap “memantau” kondisi
permainan sewaktu game sedang berlangsung .
Algoritma
minimax merupakan salah satu algoritma yang sering digunakan untuk game
kecerdasan buatan yang menggunakan teknik depth first search (DFS) dalam
pencariannya pada pohon dengan kedalaman terbatas. Algoritma minimax digunakan
untuk memilih langkah terbaik, dimana kedua pemain akan saling berusaha
untuk memenangkan permainan. Selain itu,
algoritma minimax ini bekerja secara rekursif dengan mencari langkah yang akan
membuat lawan mengalami kerugian minimum. Algoritma minimax mendeskripsikan
kondisi apabila terdapat pemain yang mengalami keuntungan, pemain lain akan
mengalami kerugian senilai dengan keuntungan yang diperoleh lawan dan
sebaliknya.
Algoritma minimax akan melakukan pengecekan
pada seluruh kemungkinan yang ada, sehingga akan menghasilkan pohon permainan
yang berisi semua kemungkinan permainan. Dengan pohon permainan ini setiap
pemain mengetahui langkah-langkah yang mungkin diberikan pada situasi permainan
saat ini. Sehingga untuk setiap langkah dan semua langkah selanjutnya dapat
diketahui. Dalam repersentasi pohon pada algoritma minimax, terdapat dua jenis
simpul, yaitu simpul min dan simpul max. Max akan memilih langkah dengan nilai
tertinggi dan min akan memilih langkah dengan nilai terendah . Dalam penentuan
keputusan max/min tersebut dibutuhkan suatu nilai yang merepresentasikan kerugian
atau keuntungan yang akan diperoleh jika langkah tersebut dipilih. Untuk itulah
disini digunakan sebuah fungsi heuristik.
Fungsi
heuristik yang digunakan algoritma ini adalah fungsi heuristik statis . Fungsi
heuristik digunakan untuk mengevaluasi nilai sebagai nilai yang
merepresentasikan hasil permainan yang akan terjadi jika langkah tersebut
dipilih. Dari nilai-nilai heuristik inilah komputer akan menentukan simpul mana
dari pohon permainan yang akan dipilih, tentunya simpul yang akan dipilih tersebut
adalah simpul dengan nilai heuristik yang akan menuntun permainan ke hasil
akhir yang menguntungkan bagi komputer. Untuk proses dan cara kerja algoritma
yang lebih jelasnya lagi, dapat dilihat pada Gambar 2.10 yang merepresentasikan
cara kerja algoritma Minimax.Fungsi heuristik yang digunakan algoritma ini
adalah fungsi heuristik statis. Fungsi heuristik digunakan untuk mengevaluasi
nilai sebagai nilai yang merepresentasikan hasil permainan yang akan terjadi
jika langkah tersebut dipilih. Dari nilai-nilai heuristik inilah komputer akan
menentukan simpul mana dari pohon permainan yang akan dipilih, tentunya simpul
yang akan dipilih tersebut adalah simpul dengan nilai heuristik yang akan
menuntun permainan ke hasil akhir yang menguntungkan bagi komputer.
Sumber
http://web.eecs.umich.edu/~akamil/teaching/sp03/minimax.pdf
https://id.wikipedia.org/wiki/Teori_permainan
https://id.wikipedia.org/wiki/Minimax
http://www.catatanfadil.com/2014/03/teori-game.html
http://majalah1000guru.net/2011/07/teori-permainan-game-theory/
https://sutrisnoadityo.wordpress.com/2013/10/12/teori-permainan-game-theory/
http://rinaforall.blogspot.co.id/2013/04/algoritma-minimax.html
https://laskyargiovane.wordpress.com/2016/04/25/artificial-intelligence-kecerdasan-buatan-pada-game/
https://setiyanugroho.wordpress.com/2011/04/12/kecerdasan-buatan-dalam-game/
