PENGANTAR TEKNOLOGI SISTEM CERDAS
Disusun Oleh:
Syifa Alya Nabila
16115777
3KA12
Universitas Gunadarma
TEKNIK PEMBANGUNAN GAME AI
Di dunia akademis, bidang kecerdasan buatan dipelajari secara
serius untuk meningkatkan kualitas hidup manusia. Para peneliti dan mahasiswa
(ilmu komputer atau teknik informatika) terus menerus mengembangkan
teknik-teknik pada bidang ini untuk menghasilkan mesin yang semakin mengerti,
dan memahami kebutuhan manusia. Dalam game berbasis kecerdasan buatan, ada
banyak teknik yang diadaptasi dari bidang kecerdasan buatan untuk diterapkan
pada game.
beberapa diantaranya, yaitu:
1. Mengejar dan Menghindar
Mengejar dan menghindar merupakan teknik dasar yang
diterapkan pada banyak game berbasis kecerdasan buatan dari yang sederhana
sampai yang kompleks. apakah itu space shooters, RPG, atau game strategi.
metode paling umum pada teknik mengejar dan menghindar ini adalah melakukan
pemutakhiran (update) koordinat terhadap objek yang menjadi sasaran. Posisi
relatif dan kecepatan dapat dijadikan sebagai parameter pada algoritma mengejar
dan menghindar. Metode Line-of-sight yang membutuhkan dasar rumus persamaan garis
juga serngkali dijadikan basis metode mengejear dan menghindar.
2. Pola Pergerakan
Pola pergerakan merupakan cara yang sederhana untuk
memberikan ilusi kecerdasan pada sebuah game. Game Galaga adalah contoh klasik
penerapan pola pergerakan ini, dimana pesawat musuh dapat bergerak secara
melingkat atau mengikuti pola garis lurus yang ditentukan. Contoh lain
penerapan pola pergerakan adalah pada game first-person shooter yang
menampilkan monster yang sedang berpatroli pada jalur tertentu, pada game simulasi
pertempuran pesawat dimana pesawat musuh dapat melakukan manuver-manuver di
udara yang menyulitkan kita mengejar, atau karakter-karakter non-player
(figuran) seperti kambing yang sedang berjalan membutuhkan teknik pola
pergerakan ini. Metode standar untuk menerapkan pola pergerakan adalah dengan
cara menyimpan pola tersebut dalam suatu array. Array tersebut terdiri dari
serangkaian koordinat atau perintah pergerakan dengan pola tertentu untuk
mengontrol koordinat dari objek. Dengan metode ini, bisa didapatkan pola-pola
pergerakan seperti melingkar, garis lurus, zig-zag atau bahkan kurva tak
beraturan.
3. Pathfinding
Metode pathfinding paling mudahditemui 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.
4. 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). 5. 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 5 teknik kecerdasan
buatan di atas yang dapat digunakan dalam sebuah game berbasis kecerdasan buatan.
Beberapa teknik lain yang umum digunakan antara lain: finite state machine,
fuzzy logic, ruled-based AI, basic probability,
dan keputusan tak pasti (dengan menggunakan teknik Bayesian) Di
masa-masa mendatang, dengan dukungan teknologi hardware yang semakin baik,
teknik kecerdasan buatan pada game berbasis kecerdasan buatan akan semakin
matang dengan ilusi kecerdasan yang semakin menyerupai manusia. sumber : majalah pc mild 20/2009.
5. Decision Making
Decision Making adalah serangkaian algoritma yang dirancang
dengan memasukan beberapa kemungkinan langkah yang bisa diambil oleh suatu
aplikasi, Pada game ini decision making memberikan kemampuan suatu karakter
untuk menentukan langkah apa yang akan diambil. Decision making dilakukan
dengan cara menentukan satu pilihan dari list yang sudah dibuat pada algoritma
yang dirancang. Algoritma decision making kerap digunakan dalam aplikasi game,
akan tetapi algoritma decision making dapat diimplementasikan pada banyak
aplikasi lain.
Decision Making terbagi menjadi 3 yaitu : Decision Tree,
State Machine dan Rule System
1.
Decision
Tree
Pohon Keputusan (Decision Tree)
merupakan metode klasifikasi dan prediksi yang sangat kuat dan terkenal. Metode
pohon keputusan mengubah fakta yang sangat besar menjadi pohon keputusan yang
merepresentasikan aturan. Aturan dapat dengan mudah dipahami dengan bahasa
alami. Aturan ini juga dapat diekspresikan dalam bentuk bahasa basis data
seperti SQL untuk mencari record pada kategori tertentu. Pohon keputusan juga
berguna untuk mengeksplorasi data, menemukan hubungan tersembunyi antara
sejumlah calon variabel input dengan sebuah variabel target. Karena pohon
keputusan memadukan antara eksplorasi data dan pemodelan, pohon keputusan ini
sangat bagus sebagai langkah awal dalam proses pemodelan bahkan ketika dijadikan
sebagai model akhir dari beberapa teknik lain(J R Quinlan, 1993).
Variabel tujuan biasanya
dikelompokkan dengan pasti dan model pohon keputusan lebih mengarah pada
perhitungan probabilitas dari masing-masing record terhadap kategori-kategori
tersebut, atau untuk mengklasifikasi record dengan mengelompokkannya dalam satu
kelas. Pohon keputusan juga dapat digunakan untuk mengestimasi nilai dari
variabel kontinyu, meskipun ada beberapa teknik yang lebih sesuai untuk kasus
ini.
Kelebihan dari metode pohon keputusan adalah:
Daerah pengambilan keputusan yang sebelumnya kompleks dan
sangat global, dapat diubah menjadi lebih simpel dan spesifik
Eliminasi perhitungan-perhitungan yang tidak diperlukan,
karena ketika menggunakan metode pohon keputusan maka sampel diuji hanya
berdasarkan kriteria atau kelas tertentu
Fleksibel untuk memilih fitur dari
node internal yang berbeda, fitur yang terpilih akan membedakan suatu kriteria
dibandingkan kriteria yang lain dalam node yang sama. Kefleksibelan metode
pohon keputusan ini meningkatkan kualitas keputusan yang dihasilkan jika
dibandingkan ketika menggunakan metode penghitungan satu tahap yang lebih
konvensional
Dalam analisis multivarian, dengan
kriteria dan kelas yang jumlahnya sangat banyak, seorang penguji biasanya perlu
mengestimasikan baik itu distribusi dimensi tinggi ataupun parameter tertentu
dari distribusi kelas tersebut. Metode pohon keputusan dapat menghindari
munculnya permasalahan ini dengan menggunakan kriteria yang jumlahnya lebih
sedikit pada setiap node internal tanpa banyak mengurangi kualitas keputusan
yang dihasilkan.
Kekurangan
pada pohon keputusan adalah:
·
Terjadi
overlapping terutama ketika kelas-kelas dan kriteria yang digunakan jumlahnya
sangat banyak. Hal tersebut juga dapat menyebabkan meningkatnya waktu
pengambilan keputusan dan jumlah memori yang diperlukan
·
Pengakumulasian
jumlah kesalahan dari setiap tingkat dalam sebuah pohon keputusan yang besar Kesulitan
dalam mendesain pohon keputusan yang optimal Hasil kualitas keputusan yang
didapatkan dari metode pohon keputusan sangat tergantung pada bagaimana pohon
tersebut didesain.
Pohon keputusan
adalah model prediksi menggunakan struktur pohon atau struktur berhirarki.
Setiap percabangan menyatakan kondisi yang harus dipenuhi dan tiap ujung pohon
menyatakan kelas data. Contoh pada Gambar diatas adalah identifikasi pembeli komputer.
Dari pohon keputusan tersebut diketahui bahwa salah satu kelompok yang
potensial membeli komputer adalah orang yang berusia di bawah 30 tahun dan juga
pelajar. Setelah sebuah pohon keputusan dibangun maka dapat digunakan untuk
mengklasifikasikan record yang belum ada kelasnya. Dimulai dari node root,
menggunakan tes terhadap atribut dari record yang belum ada kelasnya ini lalu
mengikuti cabang yang sesuai dengan hasil dari tes tersebut, yang akan membawa
kepada internal node (node yang memiliki satu cabang masuk dan dua atau lebih
cabang yang keluar), dengan cara harus melakukan tes lagi terhadap atribut atau
node leaf. Record yang kelasnya tidak diketahui kemudian diberikan kelas yang
sesuai dengan kelas yang ada pada node leaf. Pada pohon keputusan setiap simpul
leaf menandai label kelas. Proses dalam pohon keputusan yaitu mengubah bentuk
data (tabel) menjadi model pohon (tree) kemudian mengubah model pohon tersebut
menjadi aturan (rule) (J R Quinlan, 1993).
Salah satu
algoritma induksi pohon keputusan yaitu ID3 (Iterative Dichotomiser 3). ID3
dikembangkan oleh J. Ross Quinlan. Dalam prosedur algoritma ID3, input berupa
sampel training, label training dan atribut. Algoritma Decision Tree C4.5
merupakan pengembangan dari ID3. Sedangkan pada perangkat lunak open source
WEKA mempunyai versi sendiri dari C4.5 yang dikenal sebagai J48.
2. State Machine
Finite State
Machines (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
keutungan 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.
3. Rule Systems
Rule Based System merupakan metode pengambilan keputusan
berdasarkan pada aturan-aturan tertentu yang telah ditetapkan. RBS dapat
diterapkan pada agen virtual dalam bentuk kecerdasan buatan sehingga dapat
melakukan tindakan tertentu. Tindakan tersebut direpresentasikan oleh set
aturan yaitu penyebab tindakan itu terjadi, proses tindakan dan hasil dari
tindakan tersebut.
Rule Base Systems (RBS) sistem yang
baik untuk mendapat jawaban dari pertanyaan mengenai What (apa), How
(bagaimana) dan Why (mengapa) dari Rule Base (RB) selama proses inferensia.
Jawaban dan penjelasannya dapat disediakan dengan baik. Masalah yang ada dengan
SBP adalah ia tak dapat secara mudah menjalankan proses akuisisi knowledge
(pengetahuan) dan ia tak dapat mengupdate rule (aturan) secara otomatis. Hanya
pakar yang dapat mengupdate Knowledge Base (KB) secara manual dengan dukungan
dari knowledge engineer (insinyur pengetahuan). Lebih jauh kebanyakan peneliti
dalam SBA lebih memperhatikan masalah optimasi pada rule yang sudah ada
daripada pembangkitan rule baru dari rule yang sudah ada. Namun demikian,
optimasi rule tak dapat mengubah hasil dari inferensia secara signifikan, yaitu
dalam hal cakupan pengetahuan.
Ripple Down Rule (RDR) datang untuk
mengatasi permasalahan utama dari sistem pakar: pakar tak perlu lagi selalu
mengkomunikasikan pengetahuan dalam konteks yang spesifik. RDR membolehkan
akuisisi yang cepat dan sederhana secara ekstrim tanpa bantuan dari knowledge
engineer. Pengguna tak perlu menguji RB dalam rangka mendefinisikan rule baru:
pengguna hanya perlu untuk mampu mendefinisikan rule baru yang secara benar
mengklasifikasikan contoh yang diberikan, dan sistem dapat menentukan dimana
suatu rule harus ditempatkan dalam hirarki rulenya. Keterbatasan dari RDR
adalah kekurangan dalam hal inferensia yang berdayaguna. Tak seperti SBA yang
dilengkapi dengan inferensia melalui forward dan backward chaining, RDR
kelihatannya menggunakan Depth First Search (DFS) yang memiliki kekurangan
dalam hal fleksibelitas dalam hal penjawaban pertanyaan dan penjelasan yang
tumbuh dari inferensia yang berdayaguna.
Variable-Centered Intelligent Rule System (VCIRS) merupakan
perkawinan dari SBA dan RDR. Arsitektur sistem diadaptasi dari SBA dan ia
mengambil keuntungan-keuntungan yang ada dari RDR.
untuk meningkatkan kinerja sistem dari pengguna sistem selama
pembangunan pengetahuan (melalui analisis nilai) dan penghalusan pengetahuan
(dengan pembangkitan rule).
Path Finding
Metode Path
Finding seringkali dijumpai pada game yang bergenre strategi, dimana kita
sebagai user menunjuk satu karakter untuk digerakkan ke lokasi tertentu dengan
cara mengklik lokasi yang akan dituju. Maka, si karakter tersebut akan bergerak
ke arah yang telah ditentukan, dan secara “cerdas” dapat menemukan jaur
terpendek ataupun menghindari rintangan yang ada.
Metode pada Path Finding terbagi menjadi 4 bagian yaitu:
1. Waypoints
Merupakan titik
acuan/kumpulan koordinat yang digunakan untuk keperluan navigasi. Maksud dari
keperluan navigasi disini adalah mengidentifikasi sebuah titik dipeta. Disetiap
koordinat biasanya menyertakan longitude, latitude, dan terkadang altitude
untuk keperluan navigasi di udara.
2. A* Searching
Algoritma A*
merupakan yang sering digunakan pada game yang menggunakan metode pathfinding.
Algoritma ini dipilih karena A* sangat mudah untuk diimplementasikan dan sangat
efisien. Dengan menggunakan algoritma A* kita dapat menentukan jalur terpendek.
Pada algotitma ini akan menyeleksi dengan cara membuang langkah yang tidak
perlu dengan mempertimbangkan bahwa langkah yang dibuang dipastikan tidak mencapai
solusi yang diinginkan.
Prinsip dari
algoritma ini yaitu dengan cara mencari jalur terpendek dari sebuah simpul awal
(Starting Point) menuju ke simpul tujuan dengan memperhatikan harga (F)
terkecil. Algoritma A* akan memperhitungkan cost dari current state ke tujuan
dengan fungsi heuristic, selain itu algoritma ini juga mempertimbangkan cost
yang telah ditempuh selama ini dari initial state ke current state. Jadi
maksudnya jika jalan yang telah ditempuh terlalu panjang dan ada jalan lain
yang cost nya lebih kecil tetapi memberikan posisi yang sama jika dilihat dari
goal, maka jalan yang lebih pendeklah yang akan dipilih.
3. Dijkstra
Algoritma
Dijkstra yang dinamai penemunya yakni seorang ilmuwan komputer, Edsger Dijkstra
merupakan sebuah algoritma yang rakus atau biasa dikenal dengan algoritma
greedy. Algoritma ini biasa dipakai dalam memecahkan permasalahan jarak
terpendek (shortest path problem) untuk sebuah graf berarah (directed graph)
dengan bobot-bobot sisi (edge weights) yang bernlai positif.
4. Tactical Pathfinding
Tactical Pathfinding merupakan algoritma
pencarian jalur yang bisa melakukan pencarian jalur terpendek dengan menghitung
bobot ancaman. Implementasi algoritma ini dapat memberikan gerakan taktis pada
non-player character. Algoritma ini dilakukan berdasarkan algoritma pencarian
jalur A* yang ditambah dengan perhitungan bobot.
Tidak ada komentar:
Posting Komentar