Game adalah permainan komputer yang
dibuat dengan teknik dan metode animasi. Permainan game merupakan bidang AI
yang sangat populer berupa permainan antara manusia melawan mesin yang
mempunyai intelektual untuk berpikir. Komputer dapat bereaksi dan menjawab
tindakan-tindakan yang diberikan oleh lawan mainnya.
Salah satu komputer yang ditanamkan
AI untuk game bernama Deep Blue. Deep Blue adalah
sebuah komputer catur buatan
IBM pertama yang memenangkan sebuah permainan catur melawan seorang juara dunia
(Garry Kasparov) dalam waktu standar sebuah turnamen catur. Kemenangan
pertamanya (dalam pertandingan atau babak pertama) terjadi pada 10
Februari 1996, dan merupakan permainan yang sangat
terkenal.
Kini telah banyak berkembang game AI
yang semakin menarik, interaktif, dan dengan grafis yang sangat bagus. Ditambah
dengan kemajuan teknologi jaringan komputer yang semakin cepat, sudah banyak
terdapat game-game AI yang berbasiskan online. Tidak sedikit orang
yang tertarik dengan game saat ini. Mereka memainkan game untuk mengisi
kekosongan waktu mereka atau pun melatih skill mereka dalam berpikir.
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.
1.2 Mode Game AI
Pathfinding
Metode
pathfinding paling mudah ditemui pada game-game bertipe strategi dimana kita
menunjuk satu tokoh untuk digerakkan ke lokasi tertentu dengan mengklik lokasi
yang hendak dituju. Si tokoh akan segera bergerak ke arah yang ditentukan, dan
secara “cerdas” dapat menemukan jalur terpendek ataupun menghindari dari rintangan-rintangan
yang ada. Salah satu algoritma pathfindin yang cukup umum dan yang paling
banyak digunakan utnuk mencari jarak terpendek secara efisien adalah algoritma
A* (baca: A star). Secara umum, algoritma A* adalah mendefinisikan area
pencarian menjadi sekumpulan node-node (tiles). Titik awal dan titik akhir
ditentukan terlebih dulu untuk mulai penelusuran pada tiap-tiap node yang
memungkinkan untuk ditelusuri. Dari sini, akan diperoleh skor yang menunjukkan
besarnya biaya untuk menempuh jalur yang ditemukan, ditambah dengan nilai
heuristik yang merupakan nilai biaya estimasi dari node yang ada menuju tujuan
akhir. Iterasi akan dilakukan hingga akhirnya mencapai target yang dituju.
Jaringan
saraf tiruan (neural network)
Neural
network cukup baik ketika diterapkan pada kasus-kasus yang sifatnya non-linier
atau mengambil keputusan yang tidak dapat dilakukan dengan metode tradisional.
Penerapannya seringkali pada game-game yang memerlukan kemampuan adaptif atau
belajar dari pengalaman. Sebagai contoh, jika suatau ketika terjadi pertempuran
antar player dengan unit komputer, dan unit komputer mengalami kekalahan, maka
pada kesempatan lain yang serupa, komputer akan memilih untuk tidak bertempur.
Semakin banyak pengalaman yang dialami komputer, maka komputer menjadi semakin
cerdas. Prinsip dasar dari jaringan saraf tiruan ini adalah perbaikan bobot
secara terus menerus agar output yang dihasilkan menjadi semakin akurat
(semakin cerdas).
Algoritma
Genetis (genetic algorithm)
Algoritma
genetis sedikit banyak dipengaruhi oleh teori evolusi yang dicetuskan Darwin,
yaitu bahwa spesies akan terus menerus beradaptasi dengan lingkungannya dan
ciri khasnya yang terletak pada kromosom, akan diturunkan pada generasi
berikutnya. Generasi turunan ini menerima gabungan kromosom dari kedua
induknya, yang disebut dengan crossover. Pada algoritma genetis, akan
diterapkan langkah ranking fitness untuk melakukan seleksi terhadap langkah
ranking fitness untuk melakukan seleksi terhadap generasi turunan yang terbaik.
Pada game berbasis algorima genetis, turunan terbaik inilah yang dilibatkan ke
dalam game, dimana akan digunakan oleh komputer untuk merespons
perubahan-perubahan tingkah laku user.
sebenarnya bukan hanya 3 teknik
kecerdasan buatan di atas yang dapat digunakan dalam sebuah game berbasis
kecerdasan buatan masih banyak lagi teknik yang lain.
1.3 Algoritma,
Struktur Data dan Representasi
Beberapa
algoritma yang digunakan dalam game, mungkin salah satunya adalah algoritma
yang digunakan dalam game pacman tersebut.
1. Decision tree
Decision
Tree adalah salah satu metode klasifikasi yang paling populer karena mudah
untuk diinterpretasi oleh manusia. Decision tree adalah model prediksi
menggunakan struktur pohon atau struktur berhirarki. Konsep dari decision tree
adalah mengubah data menjadi pohon keputusan dan aturan-aturan keputusan.
Manfaat utama dari penggunaan decision tree adalah kemampuannya untuk mem-break
down proses pengambilan keputusan yang kompleks menjadi lebih simpel sehingga
pengambil keputusan akan lebih menginterpretasikan solusi dari permasalahan.
Kelebihan
Daerah
pengambilan keputusan yang sbelumnya kompleks dan sangat global, dapat diubah
menjadi lebih simpel dan spesifik.
Eliminasi
perhitungan-perhitungan yang tidak diperlukan, karena ketika menggunakan metode
decision tree maka sample diuji hanya berdasarkan criteria atau kelas tertentu.
Fleksibel
untuk memilih features dari internal nodes yang berbeda, feature yang terpilih
akan membedakan suatu criteria dibandingkan criteria yang lain dalam node yang
sama. Kefleksibelan metode decision tree ini meningkatkan kualitas keputusan
yang dihasilkan jika dibandingkan ketika menggunakan metode penghitungan satu
tahap yang lebih konvensional.
Dalam
analisis multivariat, dengan kriteria dan kelas yang jumlahnya sangat banyak,
seorang penguji biasanya perlu untuk mengestimasikan baik itu distribusi
dimensi tinggi ataupun parameter tertentu dari distribusi kelas tersebut.
Metode decision tree dapat menghindari munculnya permasalahan ini dengan
menggunakan criteria yang jumlahnya lebih sedikit pada setiap node internal
tanpa banyak mengurangi kualitas keputusan yang dihasilkan.
Kekurangan
Terjadi
overlap terutama ketika kelas-kelas dan criteria yang digunakan jumlahnya
sangat banyak. Hal tersebut juga dapat menyebabkan meningkatnya waktu
pengambilan keputusan dan jumlah memory yang diperlukan.
Pengakumulasian
jumlah error dari setiap level dalam sebuah pohon keputusan yang besar.
Kesulitan
dalam mendesain decision tree yang optimal. Hasil kualitas keputusan yang
didapatkan dari metode decision tree sangat tergantung pada bagaimana pohon
tersebut didesain.
2.
Finite State Machines (FSM)
FSM
adalah sebuah metodologi perancangan sistem kontrol yang menggambarkan tingkah
laku atau prinsip kerja sistem dengan menggunakan tiga hal berikut: State
(Keadaan), Event (kejadian) dan Action (aksi). Pada satu saat dalam periode
waktu yang cukup signifikan, sistem akan berada pada salah satu state yang
aktif. Sistem dapat beralih atau bertransisi menuju state lain jika mendapatkan
masukan atau event tertentu, baik yang berasal dari perangkat luar atau
komponen dalam sistemnya itu sendiri (misal interupsi timer). Transisi keadaan
ini umumnya juga disertai oleh aksi yang dilakukan oleh sistem ketika
menanggapi masukan yang terjadi. Aksi yang dilakukan tersebut dapat berupa aksi
yang sederhana atau melibatkan rangkaian proses yang relative kompleks.
Berdasarkan sifatnya, metode FSM ini sangat cocok digunakan sebagai basis
perancangan perangkat lunak pengendalian yang bersifat reaktif dan real time.
Salah satu keuntungan nyata penggunaan FSM adalah kemampuannya dalam
mendekomposisi aplikasi yang relative besar dengan hanya menggunakan sejumlah
kecil item state. Selain untuk bidang kontrol, Penggunaan metode ini pada
kenyataannya juga umum digunakan sebagai basis untuk perancangan
protokol-protokol komunikasi, perancangan perangkat lunak game, aplikasi WEB
dan sebagainya.
Dalam
bahasa pemrograman prosedural seperti bahasa C, FSM ini umumnya direalisasikan
dengan menggunakan statemen kontrol switch case atau/dan if..then. Dengan
menggunakan statemen-statemen kontrol ini, aliran program secara praktis akan
mudah dipahami dan dilacak jika terjadi kesalahan logika.
Finite
State Machine di dunia AI Game Programming, merupakan salah satu teknik yang
paling sering digunakan.
Kelebihan
Implementasinya
mudah dan cepat
Memudahkan
proses debugging. Karena telah dipecah menjadi kepingan yang lebih kecil,
proses debugging kalau terjadi behavoiur yang tidak semestinya, menjadi lebih
mudah
Proses
komputasi yg minimal, karena sejatinya FSM hanyalah conditional statement yang
dikemas dalam bentuk yang lebih elegan.
Fleksibel,
dapat dikombinasikan dengan teknik AI lain misalnya fuzzy logic dan neural
network.
Kekurangan
Behaviour
dari agen mudah diprediksi, karena tidak ada searching dan atau learning di
dalam agen tersebut
Karena
mudah diimplementasi, kadang programmer langsung tembak di eksekusi tanpa
melakukan desain FSM terlbih dahulu. Biasanya akan terjadi FSM yang
terfragmentasi
Timbul
apa yang dinamakan dengan State Oscillation yaitu ketika batasan antara dua
buah state terlalu tipis
3.
Sistem berbasis aturan (Rule Based System)
adalah
suatu program komputer yang memproses informasi yang terdapat di dalam working
memory dengan sekumpulan aturan yang terdapat di dalam basis pengetahuan
menggunakan mesin inferensi untuk menghasilkan informasi baru.
Sebuah
Rule-Based System dapat dibentuk dengan menggunakan sebuah assertions set, yang
secara kolektif membentuk working memory, dan sebuah rule set yang menentukan
aksi pada assertions set. RBS secara relatif adalah model sederhana yang
bisa diadaptasi ke banyak masalah. Namun, jika ada terlalu banyak peraturan,
pemeliharaan sistem akan rumit dan terdapat banyak failure dalam kerjanya.
Kelebihan
Availability-bertambah,
intelligent tutor, intelligent dB, danger-reduced, performance
multiple
expertise, reability-bertambah, explanation steady, unemotional and complete
response
Kekurangan
Jika
terlalu banyak aturan, sistem menjadi sulit dalam me-maintain performance dan
Keterbatasan dalam memutuskan teknik yang digunakan untuk suatu masalah.
4.
Algoritma A*
Menyelesaikan
masalah yang menggunakan graf untuk perluasan ruang statusnya. Dengan
menerapkan suatu heuristik, algoritma ini membuang langkah-langkah yang tidak
perlu dengan pertimbangan bahwa langkah-langkah yang dibuang sudah pasti
merupakan langkah yang tidak akan mencapai solusi yang diinginkan. Algoritma A*
membangkitkan simpul yang paling mendekati solusi. Simpul ini kemudian disimpan
suksesornya ke dalam list sesuai dengan urutan yang paling mendekati solusi
terbaik. Kemudian, simpul pertama pada list diambil, dibangkitkan suksesornya
dan kemudian suksesor ini disimpan ke dalam list sesuai dengan urutan yang
terbaik untuk solusi.
Algoritma
ini akan mengunjungi secara mendalam (mirip DFS) selama simpul tersebut
merupakan simpul yang terbaik. Jika simpul yang sedang dikunjungi ternyata
tidak mengarah kepada solusi yang diinginkan, maka akan melakukan runut balik
ke arah simpul akar untuk mencari simpul anak lainnya yang lebih menjanjikan
dari pada simpul yang terakhir dikunjungi. Bila tidak ada juga, maka akan terus
mengulang mencari ke arah simpul akar sampai ditemukan simpul yang lebih baik
untuk dibangkitkan suksesornya. Strategi ini berkebalikan dengan algoritma DFS
yang mencari sampai kedalaman yang terdalam sampai tidak ada lagi suksesor yang
bisa dibangkitkan sebelum melakukan runut balik, dan BFS yang tidak akan
melakukan pencarian secara mendalam sebelum pencarian secara melebar selesai.
A* baru berhenti ketika mendapatkan solusi yang dianggap solusi terbaik.
Algoritma
A* menggabungkan jarak estimasi/heuristik [h(n)] dan jarak sesungguhnya/cost
[g(n)] dalam membantu penyelesaian persoalan. Heuristik adalah nilai yang
memberi harga pada tiap simpul yang memandu A* mendapatkan solusi yang
diinginkan. Dengan heuristik, maka A* pasti akan mendapatkan solusi (jika
memang ada solusinya). Dengan kata lain, heuristik adalah fungsi optimasi yang
menjadikan algoritma A* lebih baik dari pada algoritma lainnya. Namun heuristik
masih merupakan estimasi/perkiraan biasa saja. Sama sekali tidak ada rumus
khususnya. Artinya, setiap kasus memiliki fungsi heuristik yang berbeda-beda.
5.
Algoritma Dijkstra
Algoritma
Dijkstra adalah sebuah algoritma rakus (greedy algorithm) yang
dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem)
untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge
weights) yang bernilai tak negatif.
Misalnya,
bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge
weights) melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra
dapat digunakan untuk menemukan jarak terpendek antara dua kota. Input
algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed
graph)
Tujuan
Algoritma Dijkstra yaitu untuk menemukan jalur terpendek berdasarkan bobot
terkecil dari satu titik ke titik lainnya.
Kelemahan
algoritma ini adalah semakin banyak titik akan semakin memakan waktu proses.
Jumlah
titik menentukan tingkat efektifitas dari algoritma djikstra.
Urutan
Logika Algoritma Dijkstra
-Beri
nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada
node awal dan
nilai tak hingga terhadap node
lain (yang belum terisi).
-Set semua node “Belum terjamah” dan set node awal sebagai
“Node keberangkatan”.
-Dari
node keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung
jaraknya dari titik keberangkatan.
-Setelah selesai mempertimbangkan setiap jarak terhadap node
tetangga, tandai node
yang telah terjamah sebagai “Node
terjamah”. Node terjamah tidak akan pernah di cek
kembali, jarak yang disimpan
adalah jarak terakhir dan yang paling minimal bobotnya.
-Set “Node belum terjamah” dengan jarak terkecil (dari node
keberangkatan) sebagai
“Node Keberangkatan” selanjutnya
dan lanjutkan dengan kembali ke step 3.
Dari
beberapa algoritma AI diatas mungkin kita sekarang dapat mengerti bagaimana AI
dalam game bekerja, atau malah kita bingung dan tidak mengerti. Ada banyak
proses rumit yang jika dikerjakan terlihat akan sangat memakan waktu, sedangkan
saat kita bermain game, semuanya terjadi begitu cepat dalam hitungan detik.
Tetapi tu semua mungkin karena adanya komputer sebagai alat pemprosesan yang
dapat mengerjakannya dalam hitungan detik.
1.4 Kompleksitas
Kesalahan
Dalam konteks kecerdasan buatan
dalam permainan video, kecurangan mengacu pada programmer agen memberikan akses
ke informasi yang tersedia kepada pemain. Dalam sebuah contoh sederhana, jika
agen ingin tahu apakah pemain dekatnya mereka dapat menjadi diberikan kompleks,
manusia seperti sensor (melihat, mendengar, dll), atau mereka bisa menipu
dengan hanya meminta mesin permainan untuk posisi pemain. Penggunaan kecurangan
dalam AI menunjukkan keterbatasan "kecerdasan" dicapai artifisial,
secara umum, dalam permainan di mana kreativitas strategis sangat penting, manusia
dengan mudah bisa mengalahkan AI setelah minimal trial and error jika bukan
untuk keuntungan ini. Kecurangan sering diimplementasikan untuk alasan kinerja
di mana dalam banyak kasus mungkin dianggap dapat diterima sepanjang
pengaruhnya tidak jelas bagi pemain. Sedangkan kecurangan hanya merujuk hak
istimewa yang diberikan secara khusus untuk AI itu tidak termasuk kecepatan
tidak manusiawi dan presisi alami untuk pemain-komputer mungkin panggilan
keuntungan yang melekat komputer "kecurangan" jika mereka menghasilkan
agen bertindak tidak seperti pemain manusia.
Kecurangan
AI adalah aspek yang terkenal dari seri Peradaban Sid Meyer, dalam pertandingan
tersebut, pemain harus membangun kerajaan dari awal, sedangkan kerajaan
komputer menerima unit tambahan tanpa biaya dan dibebaskan dari pembatasan
sumber daya.
1.5 Jenis Game AI
RTS (Real Time Strategy)
Game
ini biasanya bersifat turn based ataupun bisa dimainkan secara bersamaan,
identik dengan bermain melawan human intelegent (manusia vs manusia) yang
biasanya menggunakan LAN ataupun Internet. Game ini bisa dikatakan game
perang-perangan. Contoh game RTS adalah (DOTA, StarCraft, Civilization).
RPG
(Role Playing Game)
Game
ini memiliki unsur yang unik, karena biasanya tidak ada tamat dalam game
seperti ini (Kalaupun tamat, hanya ceritanya saja, dan kalian masih bisa
leveling atau grinding sesuka hati). Kalian akan menjalankan sebuah main
character yang bisa kalian costumize, mencari uang, membangun koneksi dengan
NPC (non playable player) dan sebagainya. Contoh dari game RPG adalah (KOA,
Skyrim, The Witcher).
FPS
(First Person Shooter)
FPS
adalah game Tembak-tembakan, pukul-pukulan, tusuk-tusukan yang menggunakan
sudut pandang orang pertama. Biasanya kita hanya bisa melihat tangan dari
character kita. Contoh game ini FPS adalah (Call of Duty, Counter Strike, Far
Cry 3).
TPS
(Third Person Shooter)
TPS
sama definisinya dengan FPS. Hanya saja sudut pandangnya yang berbeda. Di TPS
kita memakai sudut pandang orang ketiga. Kita bisa melihat keseluruhan
character dari belakang (punggung). Contoh game TPS adalah (Dark Souls, Dark
Siders, Assassins Creed).
Sand
Box
Game
yang bersetting disuatu daerah, jadi kita bertualang pada suatu map yang sudah
disediakan, dan kita bebas menjelajahinya tanpa harus loading ketika berpindah
kesuatu daerah, biasanya game-game yang seperti ini game yang paling banyak
peminatnya apalagi kita biasanya disuguhkan dengan "kebebasan"
didalam game seperti ini. Contoh game Sand Box (GTA, Saints Row, Sleeping
Dogs).
1.6
Kecepatan dan Memori
Kebanyakan program AI menuntut
memori yang besar dan kecepatan yang tinggi.
Referensi :
Link PPT : Kecerdasan Buatan dan Permainan
Tidak ada komentar:
Posting Komentar