Board Game

Pertemuan 11

Board Game

Nama : Bella Alysha Vira

NPM : 11115319

Kelas : 3KA10

Dosen : Essy Malays Sari Sakti

1.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.

1.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.

1.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.

1.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.

1.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.

1.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.

1.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:

Download ebook: http://lecturer.ukdw.ac.id/~mahas/dossier/gameng_AIFG.pdf