Artificial Intelligent pada Game
Dalam
Video Game, kecerdasan buatan digunakan untuk membuat perilaku cerdas yang
biasanya terletak pada non-player characters ( NPCs), dan seringnya
mensimulasikan seperti kecerdasan manusia. Teknik yang digunakan biasanya
menggambarkan metode keseluruhan dari kecerdasan buatan. Bagaimanapun,
penggunaan kecerdasan buatan pada game biasanya merujuk pada sekumpulan
algoritma yang didalamnya termasuk teknik dari teori kontrol,robotik, grafis
komputer,dan pengetahuan komputer secara umum.
Karena
kecerdasan buatan pada game untuk NPCs dipusatkan pada penunjukkan kecerdasan
dan menampilkan game dengan baik dan terdapat batasan lingkungan, pendekatannya
sangat berbeda dengan kecerdasan buatan tradisional; cara curang dan usaha
ekstra dapat diterima dan, pada beberapa kasus, kemampuan komputer harus
diturunkan untuk membuat manusia merasa adil. Contohnya adalah pada game
first-person shooter, dimana kemampuan NPC yang telah didesain mampu melebihi
kemampuan manusia.
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 :
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).
Dalam
situasi lain kemampuan untuk menjelaskan alasan pengambilan keputusan adalah
sesuatu yang sangat penting. Misalnya pada perusahaan asuransi ada larangan
resmi untuk mendeskriminasi berdasarkan variabel-variabel tertentu. Perusahaan
asuransi dapat mencari sendiri keadaan yang mencerminkan bahwa mereka tidak
menggunakan deskriminasi yang ilegal dalam memutuskan seseorang diterima atau
ditolak. Sebuah pohon keputusan adalah sebuah struktur yang dapat digunakan
untuk membagi kumpulan data yang besar menjadi himpunan-himpunan record yang
lebih kecil dengan menerapkan serangkaian aturan keputusan. Anggota himpunan
hasil menjadi mirip satu dengan yang lain dengan masing-masing rangkaian
pembagian. Sebuah model pohon keputusan terdiri dari sekumpulan aturan untuk
membagi sejumlah populasi yang heterogen menjadi lebih kecil, lebih homogen
dengan memperhatikan pada variabel tujuannya. Sebuah pohon keputusan mungkin
dibangun dengan seksama secara manual, atau dapat tumbuh secara otomatis dengan
menerapkan salah satu atau beberapa algoritma pohon keputusan untuk memodelkan
himpunan data yang belum terklasifikasi (Tan dkk, 2004).
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. Sistem ini mengorganisasi RB dalam struktur spesial sehingga
pembangunan pengetahuan, inferensia pengetahuan yang berdayaguna dan
peningkatan evolusional dari kinerja sistem dapat didapatkan pada waktu yang
sama. Istilah “Intelligent” dalam VCIRS menekankan pada keadaan sistem ini yang
dapat “belajar” untuk meningkatkan kinerja sistem dari pengguna sistem selama
pembangunan pengetahuan (melalui analisis nilai) dan penghalusan pengetahuan
(dengan pembangkitan rule).
Path Finding
Pencarian
jalur atau istilah kerennya adalah pathfinding dalam deskripsi saya adalah
proses pencarian rute/jalur (biasanya rute terdekat) dari suatu arena yang pada
umumnya memiliki penghalang-penghalang dari arena tersebut. Adapun penghalang
dapat berupa tembok, sungai, dsb. Goal dari pathfinding ini pada umumnya adalah
untuk mencari jalur paling efisien dengan sebisa mungkin menghindari penghalang
yang ada.
Pathfinding
dapat diterapkan misalnya dalam membuat AI dari suatu game, misalnya agar AI
tersebut dapat mengejar musuh secara efisien dan tanpa menabrak tembok atau
menghindari penghalang lain. Terdapat beberapa metode yang dapat diterapkan
dalam pathfinding ini, salah satu metode yang sering digunakan adalah A*. Ok,
tanpa berbelit-belit langsung saja kita berkenalan dengan metode yang satu ini.
a. Waypoints
Waypoint
adalah titik acuan / kumpulan koordinat yang digunakan untuk keperluan navigasi
untuk mengidentifikasi sebuah titik di peta. Koordinat-koordinat itu biasanya
menyertakan longitude, latitude, dan kadang altitude untuk keperluan navigasi
di udara. Waypoint digunakan di berbagai navigasi yang tidak memiliki jalur
yang tampak seperti navigasi di udara dan navigasi di laut, juga navigasi di
darat yang tidak memiliki jalur yang jelas. Khusus navigasi di darat yang tidak
menggunakan manusia sebagai penentu arah melainkan robot, waypoint digunakan
meski terdapat jalur yang jelas. Hal ini penting agar robot tetap memiliki
rute.
Waypoint
dibagi menjadi dua jenis, yaitu waypoint fly by dan waypoint fly over. Waypoint
fly by tidak melewati lokasi di atas way point namun tetap menuju ke arah
tujuan, sedangkan waypoint fly over melewati lokasi di atas way point. Setelah
satu waypoint terlewati, maka pilot harus menetapkan waypoint berikutnya yang
disebut dengan waypoint aktif.
b. 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.
c. 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.
d. 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.
http://eprints.dinus.ac.id/13726/1/Semantik-051_Fahrul.pdf
http://www.cs.bham.ac.uk/~mis157/Riset/VCIRS/VCIRS.php
http://blogs.itb.ac.id/aiceware/2012/09/23/algoritma-decision-tree-c4-5/
http://www.elektro.undip.ac.id/iwan/Perancangan%20Software%20Embedded%20System%20Berbasis%20FSM.pdf
http://sigiterwanto.blogspot.com/2017/04/pengertian-ai-descusion-making.html
0 komentar: