TUGAS PENG. TEKNOLOGI SISTEM CERDAS
Nama :Inka Riesty
Gunadi
Npm :13115384
Kelas :3KA10
Dosen :Essy Malays Sari Sakti
UNIVERSITAS GUNADARMA
2017
11.1 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.
Types Of Game
Teori permainan mengklasifikasikan
permainan sesuai dengan jumlah pemain, jenis sasaran yang dimiliki pemain
tersebut, dan informasi yang dimiliki setiap pemain tentang permainan tersebut.
1.Number Of Players
Permainan papan yang mengilhami algoritma
AI berbasis giliran hampir semuanya memiliki dua pemain. Sebagian besar
algoritma populer dibatasi oleh dua pemain dalam bentuknya yang paling dasar.
Mereka dapat disesuaikan untuk digunakan dengan jumlah yang lebih besar, namun
jarang menemukan deskripsi tentang algoritma untuk hal lain selain dua pemain.
2.The Goal of the Game
Dalam kebanyakan game strategi, tujuannya
adalah untuk menang. Sebagai pemain, Anda menang jika semua lawan Anda kalah.
Ini dikenal sebagai permainan zero-sum: kemenangan Anda adalah kehilangan
lawan. Jika Anda mencetak 1 poin untuk menang, maka akan sama dengan skor-1
karena kalah. Ini tidak akan terjadi, misalnya, dalam permainan kasino, saat
Anda semua bisa keluar lebih buruk.
Dalam permainan zero-sum tidak masalah jika
Anda mencoba untuk menang atau jika Anda mencoba membuat lawan kalah;
thecomeisthesame.Foranon-zero-sumgame, di mana Anda bisa menemukan semua yang
Anda inginkan, Anda ingin melakukan fokus pada kemenangan Anda, mengumpulkankan
semua hasil akhir (kecuali jika Anda ada orang lain)
Untuk game dengan lebih dari dua pemain,
semuanya lebih kompleks. Bahkan dalam permainan zero-sum, strategi terbaik
tidak selalu membuat lawan masing-masing kalah. Mungkin lebih baik untuk
mengeroyok lawan terkuat, memberi keuntungan pada lawan yang lebih lemah dan
berharap bisa menjemput mereka nanti.
3.Information
Dalam game seperti Chess, Drafts, Go, dan
Reversi, kedua pemain mengetahui segala hal yang perlu diketahui tentang
kemungkinan terjadinya hal tersebut. Mereka mengetahui berapa banyak yang harus
dilakukan pada setiap kesempatan dan kesempatan untuk melakukan langkah
selanjutnya. Mereka tahu semua ini sejak awal permainan. Game semacam ini
disebut "informasi yang sempurna." Meskipun Anda tidak tahu mana yang
akan dipilih lawan Anda, Anda memiliki pengetahuan lengkap tentang setiap
gerakan yang mungkin bisa dilakukan lawan dan efek yang dimilikinya.
4. Applying Algorithms
Algoritma yang paling dikenal dan paling
maju untuk game berbasis giliran dirancang untuk bekerja dengan permainan
informasi dua pemain, zero-sum, sempurna. Jika Anda menulis AI bermain catur,
maka ini adalah implementasi yang Anda butuhkan. Tapi banyak game komputer
berbasis turn over lebih rumit, melibatkan lebih banyak pemain dan informasi
yang tidak sempurna.
11.2 Algoritma Minimaxing
Sebuah komputer memainkan permainan
berbasis giliran dengan melihat tindakan yang ada pada gerakan ini dan
memilihnya daripadanya. Untuk memilih salah satu dari mereka, dibutuhkan stok
sekarang apa yang bergerak lebih baik daripada yang lain. Pengetahuan ini
diberikan ke komputer oleh programmer menggunakan heuristik yang disebut fungsi
evaluasi statis.
11.3 Transposition Tables anda Memory
Sejauh ini algoritma yang kita lihat
mengasumsikan bahwa setiap gerakan mengarah ke posisi papan yang unik. Seperti
yang kita lihat sebelumnya, posisi dewan yang sama dapat terjadi sebagai hasil kombinasi
gerakan yang berbeda. Dalam banyak game posisi board yang sama bahkan bisa
terjadi beberapa kali dalam game yang sama. Agar pekerjaan ekstra mencari
posisi dewan yang sama beberapa kali, algoritma dapat menggunakan tabel
transposisi. Meskipun tabel transposisi dirancang untuk menghindari duplikasi
pekerjaan pada transposisi, namun tabel tersebut memiliki manfaat tambahan.
Beberapa algoritma mengandalkan tabel transposisi sebagai memori kerja posisi
papan yang telah dipertimbangkan. Teknik seperti tes yang ditingkatkan memori,
pendalaman berulang, dan berpikir pada giliran lawan Anda semua menggunakan
tabel transposisi yang sama (dan semua diperkenalkan di bab ini). 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.
11.4 . Memori tambahan pda 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. Keberadaan memori
memungkinkan algoritma melompati pohon pencarian melihat gerakan yang paling
menjanjikan terlebih dahulu. Sifat rekursif dari algoritma negamax berarti
bahwa ia tidak dapat melompat; itu harus menggelembung dan recurse down.
11.5 Pembukaan buku dan set permainan
Dalam banyak permainan, selama
bertahun-tahun, pemain ahli telah membangun sebuah pengalaman tentang
pergerakan mana yang lebih baik daripada yang lain di awal permainan. Tempat
ini lebih jelas daripada di buku pembuka Catur. Pakar ahli mempelajari database
besar kombinasi pembuka tetap, belajar tanggapan terbaik untuk bergerak. Hal
ini tidak biasa untuk 20 sampai 30 langkah pertama dari permainan Catur
Grandmaster yang akan direncanakan sebelumnya. 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.
11.6 Optimisasi
Meskipun dasar permainan-bermain algoritma
masing-masing relatif sederhana, mereka memiliki array membingungkan optimasi
yang berbeda. Beberapa pengoptimalan ini, seperti pemangkasan dan tabel
transposisiAB, sangat penting untuk kinerja yang baik. Pengoptimalan lainnya
cukup memanfaatkan sebagian besar kinerja. Bagian ini membahas beberapa pengoptimalan
lainnya yang digunakan untuk turn-basedAI. Tidak ada cukup ruang untuk mencakup
detail pelaksanaan untuk sebagian besar dari mereka. Lampiran memberi petunjuk
lebih jauh
informasi tentang pelaksanaannya Selain
itu, optimasi khusus yang digunakan hanya dalam jumlah yang relatif kecil dari
permainan papan tidak disertakan. Catur, khususnya, memiliki keseluruhan rakit
pengoptimalan khusus yang hanya berguna dalam sejumlah kecil skenario lainnya.
11.7 Turn Base strategy game
Bab ini memusatkan perhatian pada game
board AI. Di hadapannya, game board AI memiliki banyak kemiripan permainan
strategi berbasis toturn. Game strategi komersial jarang menggunakan teknik
pencarian pohon di bab ini sebagai alat utama mereka. Kompleksitas permainan
ini berarti algoritma pencarian macet sebelum mereka dapat membuat keputusan
yang masuk akal. Teknik pencarian yang paling sederhana dirancang untuk
permainan informasi dua pemain, zero-sum, informasi sempurna, dan banyak
pengoptimalan terbaik tidak dapat disesuaikan untuk digunakan dalam permainan
strategi umum. Beberapa permainan strategi berbasis turn-turn sederhana dapat
langsung diperoleh dari algoritme pencarian pohon di bab ini. Konstruksi
penelitian dan konstruksi, gerakan pasukan, dan aksi militer semuanya bisa
menjadi bagian dari serangkaian kemungkinan pergerakan. Posisi dewan tetap
statis selama sebuah pergantian. Antarmuka permainan yang diberikan di atas
dapat, secara teori, diterapkan untuk mencerminkan turn- permainan berbasis
Antarmuka yang diterapkan ini kemudian dapat digunakan dengan algoritma
pencarian pohon reguler.
Referensi:
Artifical Intelligence For Games
Download ebook: http://lecturer.ukdw.ac.id/~mahas/dossier/gameng_AIFG.pdf
Tidak ada komentar:
Posting Komentar