Artificial
Intelligence pada Game
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.
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.
Mengetahui bagaimana untuk
mendapatkan dari titik A ke titik B adalah sesuatu yang banyak game
membutuhkan. Apakah Anda sedang merancang sebuah turn-based dalam taktik
strategi RPG atau permainan puzzle sederhana, navigasi dunia permainan Anda
sering membutuhkan kecerdasan lebih dari karakter permainan Anda dari sekedar
menunjuk ke arah tujuan dan bergerak dalam garis lurus.
Anda tidak ingin unit dalam
permainan Anda berjalan melalui dinding. Pemain juga akan mengizinkan unit
untuk bertemu dinding dan terjebak ketika jalan di sekitar hambatan terlihat
jelas. Tidak ada yang lebih frustrasi daripada unit waktu nyata strategi
permainan tidak mampu untuk membuat jalan mereka ke lokasi target.
Di sinilah algoritma pathfinding
datang. Perintis adalah blok bangunan dasar dari sebagian besar permainan AI
(kecerdasan buatan), dan dengan sedikit bantuan dari kode yang tepat permainan
Anda akan jauh lebih pintar untuk itu.
Untuk sampai ke tujuan mereka,
entitas permainan Anda mungkin harus berjalan sekitar hambatan, menemukan jalan
mereka meskipun labirin penjara atau berkeliling jalan-jalan kota. Hal ini
tidak cukup untuk akhirnya tiba di tempat tujuan melalui beberapa
jalur putus asa memutar - rute yang mereka ambil harus mungkin
rute terpendek.
Memecahkan masalah ini bukan
tugas sepele, tapi itu adalah layak usaha. Musuh yang memilih dengan bijak
sering dapat muncul hampir cerdas. Pemain Anda akan menghargai bahwa hal
"hanya bekerja" dan akan dapat fokus pada strategi dan taktik
bukannya mencemaskan memiliki mengasuh rusak AI.
Metode standar yang mayoritas
game digunakan untuk merintis jalan disebut A *, yang diucapkan "bintang".
Asal Usul Perintis AI: Algoritma Dijkstra
Pada tahun lima puluhan, seorang
ahli matematika bernama
Edsger
Dijkstra bekerja metode untuk menghitung rute yang efisien yang dapat
diterapkan untuk setiap situasi hypethetical membutuhkan pilihan otomatis
antara banyak langkah mungkin.
Hal ini sering digunakan dalam
contoh truk pergi dari stop untuk menghentikan jarak jauh, ketika pengiriman
harus dijemput dari berbagai lokasi di sepanjang jalan. Memilih rute yang
paling efisien akan menghemat uang.
Animasi di atas adalah contoh
khas dalam tindakan. Perhatikan bahwa setiap node tidak diatur pada grid
permainan seperti tapi bisa jika kita ingin. Ini adalah contoh sempurna
dari apa yang ingin kita lakukan: kita menambahkan "biaya" dari
setiap rute dan memilih salah satu yang biaya sedikit. Biaya, dalam hal
permainan merintis jalan, adalah jarak yang ditempuh.
Jika Anda menonton animasi di
atas, Anda akan melihat bahwa setiap kali kita sampai pada node baru di
sepanjang jalan, kami menambahkan biaya setiap kemungkinan rute dari sana dan
melanjutkan ke salah satu yang biaya sedikit.
Masalah Dengan Algoritma Dijkstra
Algoritma Dijkstra karya besar,
tetapi memiliki kelemahan yang naif dilaksanakan - itu tidak menggunakan
heuristik khusus untuk memilih calon yang paling mungkin pertama, sehingga solusinya
hanya diketahui setelah setiap lokasi yang mungkin diuji.
Dalam animasi di atas, Anda dapat
melihat bahwa setiap "sel" atau "node" dalam grafik sedang
diuji. Tiba di hasil yang tepat, tetapi programmer komputer di Anda
mungkin berpikir, "perlu dioptimalkan!"
A-Bintang merintis jalan untuk menyelamatkan!
Sebuah bintang adalah versi lebih
cepat dan lebih efisien dari algoritma Dijkstra.
WikiPedia
mendefinisikan A-bintang sebagai "best-pertama, grafik algoritma
pencarian yang menemukan jalur penerbangan setidaknya dari node awal yang
diberikan ke satu node tujuan".
Dengan kata lain, A-bintang
melintasi grafik simpul (koleksi poin dalam ruang yang terhubung) dan menemukan
jalan yang biaya sedikit (adalah terpendek) tanpa harus mengunjungi setiap node
tunggal di seluruh grafik. Dalam kasus videgame, ini "simpul
grafik" adalah dunia permainan; peta unit kami bergerak di sekitar.
Dalam animasi di atas, Anda dapat
melihat bahwa dunia game yang sama disajikan seperti yang terlihat pada contoh
Dijkstra sebelumnya, tapi kali ini lebih sedikit node diperiksa. Hasil ini
heuristik mengoptimalkan adalah bahwa fungsi akan berjalan lebih
cepat. Dalam game, ini selalu preferrable.
Gamedevs Cinta Optimization
Dengan beberapa optimasi yang
lebih, kita bisa berbuat lebih banyak lagi menebak dan karena itu melakukan
perhitungan lebih sedikit. Dengan menetapkan bobot untuk node yang
dikunjungi sepanjang jalan, kita bisa memprediksi arah kita harus mencoba berikutnya.
Apa yang kita maksud dengan ini,
adalah bahwa dengan menggunakan beberapa heuristik yang lebih agresif, kita
dapat memprediksi apa arah yang paling mungkin terbaik untuk memindahkan adalah
dan mencobanya pertama.
Dalam animasi di atas kita
melihat contoh yang sangat efisien algoritma Bintang-yang mencoba untuk menebak
rute terbaik sepanjang jalan bukannya mulai dari awal setiap kali rute tersebut
akan diblokir.Lebih geometri yang kompleks akan membuat ini kurang jelas, tapi
secara keseluruhan Anda dapat melihat bahwa ini adalah cara yang baik untuk
melanjutkan.
Ini adalah apa yang paling
dibutuhkan game untuk musuh mereka AI. Kemampuan untuk menemukan rute
terpendek dari titik A ke titik B, dan mesin permainan yang bisa menghitung ini
cukup cepat untuk berjalan lancar.
Sumber :