BOARD GAME

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:

http://www.catatanfadil.com/2014/03/teori-game.html
http://www.tentik.com/10-board-games-seru-yang-wajib-dimainkan-bareng-sahabat-monopoli-mah-lewat/ 
https://kummara.com/media-coverage/kummara-pionir-board-game-indonesia 

Teknik pembangunan game AI

Teknik Pembangunan Game AI

10.1. Movement

        Movement mengarah pada algoritma yang mengubah keputusan menjadi sebuah gerakan. Movement adalah salah satu konsep penanaman AI pada sebuah objek atau karakter untuk dapat melakukan sebuah gerakan otomatis, dimana AI yang ditanamkan berupa sebuah algoritma movement. Algoritma movement pada dasarnya memiliki bentuk dasar yang sama, yaitu mengambil data geometris tentang keberadaannya dan dunia, kemudian menghasilkan output berupa data geometris dari pergerakan yang akan dilakukan (Ian Millington, 2006).

Pergerakan atau movement sebuah karakter biasanya telah diatur oleh developer game tersebut, dengan melakukan penanaman AI yang dapat memperhitungkan rute yang tepat untuk mencapai tujuan. Rutenya harus masuk akal, pendek dan cepat. Inilah yang disebut pathfinding atau pencarian jalur. Algoritma yang biasa digunakan dalam metode pathfinding ini adalah Algoritma A*.

                        M illingt on dan Funge (2009, p 8) member ikan suatu model untuk menjelaskan AI dalam game. Dalam model t ersebut , mereka membagi tugas AI menjadi movement, decision making, dan strategy. Dua tugas pertama beker ja pada tiap – tiap karakter  yang dikendalikan o leh AI, sedangkan tugas yang terakhir bekerja pada sekelompok karakter yang merup akan satu grup .

 Movement atau  pergerakan mengubah pilihan yang diambil oleh AI ke dalam gerakan. Contoh dasarnya dalam beberapa game ketika musuh ingin menyerang pemain, dia pertama – tama harus mendekati pemain dan ketika sudah cukup dekat akan menyerang 48 pemain. Seringkali pergerakan yang dilakukan tidak sesederhana itu. Dalam banyak kasus, karakter musuh dihadapi pada berbagai halangan seperti tembok atau sungai dan diharuskan melakukan pilihan yang tepat untuk melewatinya.

Decision making atau pengambilan keputusan meliputi menentukan apa yang akan dilakukan berikutnya oleh karakter. Biasanya karakter memiliki beragam kegiatan yang dapat dilakukan, seperti menyerang, melompat, diam, atau bersembunyi. Sistem pengambilan keputusan menentukan tindakan apa yang paling tepat untuk dilakukan dalam suatu waktu. Setelah keputusan didapat, tindakan tersebut kemudian akan dilakukan menggunakan AI pergerakan, memainkan animasi, atau hanya men gubah suatu data tanpa umpan balik visual.

Strategy atau strategi adalah suatu pendekatan yang dilakukan oleh sekelompok karakter. Meskipun banyak game yang dapat dibuat hanya dengan pergerakan dan pengambilan keputusan, namun strategi dibutuhkan apabila ingin mengkoordinasi sekelompok karakter. AI startegi tidak hanya mengontrol satu karakter, namun mempengaruhi tindakan sekelompok karakter. Masing – masing karakter masih memiliki pergerakan dan pengambilan keputusan sendiri, namun secara keseluruhan semua keputusan dan tindakan yang diambil dipengaruhi oleh strategi kelompok. 

10.2. Pathfinding

                    Metode Path Finding seringkali dijumpai pada game yang bergenre strategi, dimana kita sebagai user menunjuk satu karakter untuk digerakkan ke lokasi tertentu dengan cara mengklik lokasi yang akan dituju. Maka, si karakter tersebut akan bergerak ke arah yang telah ditentukan, dan secara “cerdas” dapat menemukan jaur terpendek ataupun menghindari rintangan yang ada.

Metode pada Path Finding terbagi menjadi 4 bagian yakni:

1. Waypoints

Merupakan titik acuan/kumpulan koordinat yang digunakan untuk keperluan navigasi. Maksud dari keperluan navigasi disini adalah mengidentifikasi sebuah titik dipeta. Disetiap koordinat biasanya menyertakan longitude, latitude, dan terkadang altitude untuk keperluan navigasi di udara.

2. A* Searching

Algoritma A* merupakan yang sering digunakan pada game yang menggunakan metode pathfinding. Algoritma ini dipilih karena A* sangat mudah untuk diimplementasikan dan sangat efisien. Dengan menggunakan algoritma A* kita dapat menentukan jalur terpendek. Pada algotitma ini akan menyeleksi dengan cara membuang langkah yang tidak perlu dengan mempertimbangkan bahwa langkah yang dibuang dipastikan tidak mencapai solusi yang diinginkan.

Prinsip dari algoritma ini yaitu dengan cara mencari jalur terpendek dari sebuah simpul awal (Starting Point) menuju ke simpul tujuan dengan memperhatikan harga (F) terkecil. Algoritma A* akan memperhitungkan cost dari current state ke tujuan dengan fungsi heuristic, selain itu algoritma ini juga mempertimbangkan cost yang telah ditempuh selama ini dari initial state ke current state. Jadi maksudnya jika jalan yang telah ditempuh terlalu panjang dan ada jalan lain yang cost nya lebih kecil tetapi memberikan posisi yang sama jika dilihat dari goal, maka jalan yang lebih pendeklah yang akan dipilih.

3. Dijkstra

Algoritma Dijkstra yang dinamai penemunya yakni seorang ilmuwan komputer, Edsger Dijkstra merupakan sebuah algoritma yang rakus atau biasa dikenal dengan algoritma greedy. Algoritma ini biasa dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernlai positif.

4. Tactical Pathfinding

Tactical Pathfinding merupakan algoritma pencarian jalur yang bisa melakukan pencarian jalur terpendek dengan menghitung bobot ancaman. Implementasi algoritma ini dapat memberikan gerakan taktis pada non-player character. Algoritma ini dilakukan berdasarkan algoritma pencarian jalur A* yang ditambah dengan perhitungan bobot.

10.3. Pengambilan Keputusan

Decision Making adalah serangkaian algoritma yang dirancang dengan memasukan beberapa kemungkinan langkah yang bisa diambil oleh suatu aplikasi, Pada game ini decision makingmemberikan kemampuan suatu karakter untuk menentukan langkah apa yang akan diambil. Decision making dilakukan dengan cara menentukan satu pilihan dari list yang sudah dibuat pada algoritma yang dirancang. Decision Making dibagi menjadi 3, yaitu :
1. Decision Tree
Pohon Keputusan (Decision Tree) merupakan metode klasifikasi dan prediksi yang sangat kuat dan terkenal. Metode pohon keputusan mengubah fakta yang sangat besar menjadi pohon keputusan yang merepresentasikan aturan. Aturan dapat dengan mudah dipahami dengan bahasa alami. Aturan ini juga dapat diekspresikan dalam bentuk bahasa basis data seperti SQL untuk mencari record pada kategori tertentu. Pohon keputusan juga berguna untuk mengeksplorasi data, menemukan hubungan tersembunyi antara sejumlah calon variabel input dengan sebuah variabel target. Karena pohon keputusan memadukan antara eksplorasi data dan pemodelan, pohon keputusan ini sangat bagus sebagai langkah awal dalam proses pemodelan bahkan ketika dijadikan sebagai model akhir dari beberapa teknik lain (J R Quinlan, 1993).

2. State Machine
Finite State Machines (FSM) adalah sebuah metodologi perancangan sistem kontrol yang menggambarkan tingkah laku atau prinsip kerja sistem dengan menggunakan tiga hal berikut: State (Keadaan), Event (kejadian) dan action (aksi). Pada satu saat dalam periode waktu yang cukup signifikan, sistem akan berada pada salah satu state yang aktif. Sistem dapat beralih atau bertransisi menuju state lain jika mendapatkan masukan atau event tertentu, baik yang berasal dari perangkat luar atau komponen dalam sistemnya itu sendiri (misal interupsi timer). Transisi keadaan ini umumnya juga disertai oleh aksi yang dilakukan oleh sistem ketika menanggapi masukan yang terjadi. Aksi yang dilakukan tersebut dapat berupa aksi yang sederhana atau melibatkan rangkaian proses yang relative kompleks.

3. Rule System
Rule Based System merupakan metode pengambilan keputusan berdasarkan pada aturan-aturan tertentu yang telah ditetapkan. RBS dapat diterapkan pada agen virtual dalam bentuk kecerdasan buatan sehingga dapat melakukan tindakan tertentu. Tindakan tersebut direpresentasikan oleh set aturan yaitu penyebab tindakan itu terjadi, proses tindakan dan hasil dari tindakan tersebut.

10.4. Taktik dan strategi AI

                    Strategy adalah Jenis game yang mengharuskan pemainnya menggunakan taktik dan strategi untuk jeli dalam melihat setiap peluang, kelemahan musuh dan bijaksana dalam menggunakan sumber daya yang ada untuk mengatur suatu unit atau pasukan untuk menyerang markas musuh dalam rangka memenangkan permainan. biasanya di dalam game Strategy, kita dituntut untuk mencari uang, emas, poin atau semua yang berfungsi untuk untuk membiayai pasukan kita. Games Strategy dibagi 2 :

Real Time Strategy (RTS)

Pada game jenis ini, kita dapat mengendalikan pasukan secara langsung, dari mencari sumber daya, hingga menghancurkan musuh. Semua pertempuran ini dapat kita saksikan secara langsung.

Turn Based Strategy (TBS)

Game Jenis ini adalah game yang di jalankan secara bergiliran, saat kita mengambil keputusan dan menggerakan pasukan, saat itu pihak lawan harus menunggu, begitu pula sebaliknya, layaknya catur.

10.5. Pembelajaran

          Artificial Intelligence (AI) atau Kecerdasan Buatan 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)

Dalam video game, kecerdasan buatan digunakan untuk menghasilkan perilaku cerdas terutama dalam karakter non-pemain (NPC), sering simulasi kecerdasan manusia-seperti. Teknik yang digunakan biasanya memanfaatkan metode yang ada dari bidang kecerdasan buatan (AI). Namun, permainan istilah AI sering digunakan untuk merujuk kepada serangkaian luas algoritma yang juga mencakup teknik dari teori kontrol, robotika, komputer grafis dan ilmu komputer pada umumnya.

Orang-orang mengeluh bahwa "AI" dalam istilah "permainan AI" melebih-lebihkan nilainya, karena permainan AI bukan tentang kecerdasan melainkan beberapa tujuan dari bidang akademik AI. Sedangkan "nyata" AI membahas bidang pembelajaran mesin, pengambilan keputusan berdasarkan input data sewenang-wenang, dan bahkan tujuan akhir dari AI kuat yang dapat alasan, "permainan AI" sering terdiri dari setengah lusin aturan praktis, atau heuristik yang hanya cukup untuk memberikan pengalaman gameplay yang baik. Secara historis, akademis proyek game-AI telah relatif terpisah dari produk komersial karena pendekatan akademis cenderung sederhana dan non-scalable. Commercial permainan AI telah mengembangkan menetapkan sendiri alat, yang sudah cukup untuk memberikan kinerja yang baik dalam banyak kasus.

Meningkatnya kesadaran pengembang game AI akademik dan minat yang tumbuh dalam permainan komputer oleh masyarakat akademik yang menyebabkan definisi apa yang dianggap sebagai AI dalam game menjadi kurang istimewa. Namun demikian, perbedaan yang signifikan antara domain aplikasi yang berbeda dari AI berarti bahwa permainan AI masih dapat dilihat sebagai subfield berbeda AI. Secara khusus, kemampuan untuk secara sah memecahkan beberapa masalah AI di game oleh kecurangan menciptakan perbedaan penting. Misalnya, menyimpulkan posisi obyek tak terlihat dari pengamatan masa lalu bisa menjadi masalah sulit ketika AI diterapkan untuk robotika, tetapi dalam permainan komputer NPC hanya dapat mencari posisi di permainan adegan grafik. kecurangan tersebut dapat menyebabkan perilaku yang tidak realistis dan tidak selalu diinginkan. Tapi kemungkinan yang berfungsi untuk membedakan permainan AI dan menyebabkan masalah baru untuk memecahkan, seperti kapan dan bagaimana menggunakan kecurangan.

Keterbatasan utama untuk AI yang kuat adalah kedalaman melekat berpikir dan kompleksitas ekstrim dari proses pengambilan keputusan. Ini berarti bahwa meskipun akan maka secara teoritis mungkin untuk membuat "pintar" AI, pengambilan masalah akan mengambil keputusan pemrosesan yang cukup rumit.

 SUMBER:

http://thesis.binus.ac.id/Doc/Bab2/2012-1-00265-IF%20Bab%202.pdf 

https://septianbudiuntoro.wordpress.com/2016/04/19/artificial-intelligence/ 

http://hanifarazanadini.blogspot.co.id/2016/04/artificial-intelligence-pada-game.html 

http://mutiasulisetyani.blogspot.co.id/2016/04/ai-artificial-intelligence-pada-game.html