Board Game
Game Theory
Teori permainan
adalah disiplin matematika yang berkaitan dengan studi tentang ideologi yang
disarikan. Ini hanya aplikasi yang sangat lemah untuk game komputer real-time,
namun terminologi yang digunakan dalam game berbasis giliran berasal darinya.
Bagian ini akan memperkenalkan teori permainan yang cukup untuk memungkinkan
Anda memahami dan menerapkan AI berbasis giliran, tanpa terjebak dalam poin
matematika yang cerdas.
Algoritma Minimaxing
Algoritma
minimax merupakan basis dari semua permainan berbasis AI. 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.
Algoritma
minimax ini bekerja secara rekursif dengan mencari langkah yang akan membuat
lawan mengalami kerugian minimum. 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.
Transposition Table dan Memori
Tabel
transposisi menyimpan catatan posisi papan dan hasil pencarian dari posisi itu.
Ketika sebuah algoritma diberi posisi papan, pertama-tama periksa apakah papan
itu ada dalam memori dan gunakan nilai yang tersimpan jika benar. Membandingkan
status permainan yang lengkap adalah prosedur yang mahal, karena keadaan
permainan mungkin berisi puluhan atau ratusan item informasi. Membandingkan ini
dengan keadaan tersimpan dalam ingatan akan memakan waktu lama. Untuk
mempercepat pemeriksaan tabel transposisi, nilai hash digunakan.
Memori Tambahan pada Uji Algoritma
Algoritma
memory-enhanced test (MT) bergantung pada adanya tabel transposisi yang efisien
untuk bertindak sebagai algoritma'memory. MT hanyalah sebuah negamax AB
nol-lebar, menggunakan tabel transposisi untuk menghindari duplikat pekerjaan.
Sifat rekursif dari algoritma negamax berarti bahwa ia tidak dapat melompat;
itu harus menggelembung dan recurse down.
Pembukaan buku dan set permainan
Buku pembuka
adalah daftar urutan bergerak, bersama dengan beberapa indikasi seberapa bagus
hasil rata-rata akan menggunakan urutan tersebut. Dengan menggunakan
seperangkat aturan ini, komputer tidak perlu mencari menggunakan minimaxing
untuk menentukan langkah terbaik yang akan dimainkan. Ini hanya bisa memilih
langkah selanjutnya dari urutan, selama titik akhir dari urutan itu bermanfaat
baginya.
Membuka database
buku dapat diunduh untuk beberapa permainan yang berbeda, dan untuk game
terkemuka seperti database komersial Chess tersedia untuk lisensi ke dalam game
baru. Untuk game berbasis giliran asli, buku pembuka (jika berguna) perlu
dibuat secara manual.
Turn Based Strategy Game
Turn-based
strategy (TBS) game adalah turunan dari game dengan genre strategi dimana
pemainnya saling bergiliran pada pengambilan keputusannya dalam bermain. Pada
game jenis ini, player dapat memainkan oleh satu pemain saja (single player)
sedangkan lawannya adalah komputer atau istilah lainnya disebut Non Playable
Character (NPC).
Sumber :
Comments
Post a Comment