BOARD
GAME
1. THEORY GAME
Teori game adalah suatu model matematika yang
diterapkan untuk menganalisa situasi persaingan dan konflik antara berbagai
kepentingan sehingga dapat mengambil suatu keputusan. Teori permainan ini
awalnya dikembangkan oleh seorang ahli matematika perancis yang bernama Emile
Borel pada tahun 1921. Yang selanjutnya dikembangkan lebih lanjut oleh John Van
Neemann dan Oskar Morgenstern sebagai alat untuk merumuskan perilaku ekonomi
yang bersaing. John Van Neemann dan Oskar Morgenstern mengungkapkan bahwa, “Permainan
terdiri atas sekumpulan peraturan yang membangun situasi bersaing dari dua
sampai beberapa orang atau kelompok dengan memilih strategi yang dibangun untuk
memaksimalkan kemenangan sendiri atau pun untuk meminimalkan kemenangan lawan.
Peraturan-peraturan menentukan kemungkinan tindakan untuk setiap pemain,
sejumlah keterangan diterima setiap pemain sebagai kemajuan bermain, dan
sejumlah kemenangan atau kekalahan dalam berbagai situasi.”
Dari pengertian diatas dapat disimpulkan bahwa,
teori bermain adalah merupakan suatu teori yang mengedepankan konsep konsep
dalam suatu permainan sebagai landasan. Dimana didalam permainan terdapat
peraturan, yang secara langsung mampu menciptakan situasi bersaing dan digunakan
untuk mencari strategi terbaik dalam suatu aktivitas, dimana setiap pemain
didalamnya sama-sama mencapai utilitas tertinggi.
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.
SUMBER:
EmoticonEmoticon