BAB 6 - BOARD GAME dan ALGORITMA MINIMAX

06.29.00 Unknown 1 Comments


PENGERTIAN BOARD GAME

Board game adalah permainan yang dimainkan oleh dua orang atau lebih, berupa papan permainan yang telah di desain sedemikian rupa sesuai jenis permainan, board game bisa menggunakan koin, dadu, pion, kartu atau semacamnya yang digunakan dengan cara tertentu, sesuai dengan peraturan tiap-tiap jenis board game. Contohnya adalah game canddyland, chess, monopoly, scrabble, dan lain sebgainya.


ALGORITMA MINIMAX               

Algoritma minimax merupakan basis dari semua permainan berbasis AI seperti permainan catur misalnya. AI permainan catur tentunya sudah sangat terkenal dimana AI tersebut bahkan dapat mengalahkan juara dunia sekalipun. 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.

Keuntungan yang didapat dengan menggunakan algoritma minimax yaitu algoritma minimax mampu menganalisis segala kemungkinan posisi permainan untuk menghasilkan keputusan yang terbaik karena algoritma minimax ini bekerja secara rekursif dengan mencari langkah yang akan membuat lawan mengalami kerugian minimum. Semua strategi lawan akan dihitung dengan algoritma yang sama dan seterusnya. Ini berarti, 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. Dalam penentuan keputusan tersebut dibutuhkan suatu nilai yang merepresentasikan kerugian atau keuntungan yang akan diperoleh jika langkah tersebut dipilih. Untuk itulah disini digunakan sebuah fungsi heurisitic untuk mengevaluasi nilai sebagai nilai yang merepresentasikan hasil permainan yang akan terjadi jika langkah tersebut dipilih. Biasanya pada permainan tic tac toe ini digunakan nilai 1,0,-1 untuk mewakilkan hasil akhir permainan berupa menang, seri, dan kalah. Dari nilai-nilai heuristic inilah komputer akan menentukan simpul mana dari pohon permainan yang akan dipilih, tentunya simpul yang akan dipilih tersebut adalah simpul dengan nilai heuristic yang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer.            

Algoritma minimax merupakan algoritma yang diterapkan dalam game yang melibatkan dua pemain yang saling bergantian, seperti tic-tac-toe, chess, go, othello dan game yang menggunakan strategi atau logika lainnya (Wijaya, 2010). Persamaan antara semua game tersebut yaitu semua merupakan game logika dan game dengan informasi yang lengkap. Ini berarti bahwa game merupakan sekumpulan aturan main dan dasar pemikiran yang logis. Adanya aturan main dan dasar pemikiran yang logis tersebut, maka nantinya setiap pemain dapat mengetahui semua langkah yang mungkin dari pemain lawannya, sehingga pemain bisa tetap “memantau” kondisi permainan sewaktu game sedang berlangsung (Akbar, 2011).

Algoritma minimax merupakan salah satu algoritma yang sering digunakan untuk game kecerdasan buatan yang menggunakan teknik depth first search (DFS) dalam pencariannya pada pohon dengan kedalaman terbatas (Kusumadewi, 2003). Algoritma minimax digunakan untuk memilih langkah terbaik, dimana kedua pemain akan saling berusaha untuk  memenangkan permainan. Selain itu, algoritma minimax ini bekerja secara rekursif dengan mencari langkah yang akan membuat lawan mengalami kerugian minimum. Algoritma minimax mendeskripsikan kondisi apabila terdapat pemain yang mengalami keuntungan, pemain lain akan mengalami kerugian senilai dengan keuntungan yang diperoleh lawan dan sebaliknya.            

Algoritma minimax akan melakukan pengecekan pada seluruh kemungkinan yang ada, sehingga akan menghasilkan pohon permainan yang berisi semua kemungkinan permainan tersebut (Jannah, 2010). Dengan pohon permainan ini setiap pemain mengetahui langkah-langkah yang mungkin diberikan pada situasi permainan saat ini. Sehingga untuk setiap langkah dan semua langkah selanjutnya dapat diketahui. Dalam repersentasi pohon pada algoritma minimax, terdapat dua jenis simpul, yaitu simpul min dan simpul max. Max akan memilih langkah dengan nilai tertinggi dan min akan memilih langkah dengan nilai terendah (Kusumadewi, 2003). Dalam penentuan keputusan max/min tersebut dibutuhkan suatu nilai yang merepresentasikan kerugian atau keuntungan yang akan diperoleh jika langkah tersebut dipilih. Untuk itulah disini digunakan sebuah fungsi heuristik.

Table Transposition and Memory
Algoritma dapat menggunakan tabel transposisi untuk menghindari melakukan pekerjaan ekstra dalam mencari posisi board yang sama beberapa kali.
  •  Memori kerja posisi board sudah dikenal
  • Menggunakan fungsi hash khusus desiderata: sebarkan posisi-posisi yang mirip seluas mungkin melalui kisaran nilai hash nilai hash yang banyak berubah saat berpindah dari papan bergerak mengalami perubahan yang sangat sedikit.
  • Kunci zobrist adalah sekumpulan bit acak dari fixed-length pola yang tersimpan untuk setiap kemungkinan keadaan dari setiap lokasi yang mungkin ada pada board. Contoh: Catur memiliki 64 kotak, dan masing-masing persegi bisa kosong atau ada 1 dari 6 potongan berbeda di atasnya, masing-masing dua warna mungkin.Zobrist kunci harus seperti berikut : 64 2 (6 + 1) = 832 bit-string yang berbeda.
  • Kunci Zobrist perlu diinisialisasi dengan bit-string acak dengan ukuran yang sesuai.
  • Untuk setiap kotak yang tidak kosong, tombol Zobrist adalah mendongak dan XORed dengan jumlah hash yang berjalan.
  • Zobrist Key dapat diperbarui secara bertahan
  • Tabel hash menyimpan nilai yang terkait dengan posisi board • Gerakan terbaik dari posisi masing-masing board.
  • Kedalaman digunakan untuk menghitung nilai
  • Nilai yang akurat, atau kita dapat juga menyimpan nilai "fail-soft" yang dihasilkan darisebuah cabang yang dipangkas
  • Nilai akurat atau nilai gagal-rendah (alpha pruned), atau nilai gagal-tinggi (beta pruned)


Source:
voice-teacher.blogspot.com › Pengayaan
http://abdulagisni.blogspot.com/2017/11/

1 komentar:

[TULISAN] BAB 5 - TAKTIK dalam PERMAINAN AI

06.25.00 Unknown 0 Comments


TAKTIK dan STRATEGI dalam AI

Taktik Real-time (disingkat RTT sebagai fixed unit real-time strategy) adalah subgenre dari wargames taktis bermain di real-time simulasi pertimbangan dan keadaan perang operasional dan taktik militer.
Taktik turn-based ( TBT ), atau taktis turn-based ( TTB ), adalah genre strategi video game yang melalui stop-tindakan mensimulasikan pertimbangan dan keadaan perang operasional dan taktik militer di umumnya konfrontasi skala kecil dibandingkan dengan pertimbangan yang lebih strategis dari strategi turn-based (TBS) permainan.

Strategi real-time "(RTS) menunjukkan bahwa tindakan dalam permainan kontinu, dan pemain akan harus membuat keputusan dan tindakan mereka dalam latar belakang negara permainan yang terus berubah, dan komputer real-time strategy gameplay ditandai dengan memperoleh sumber daya, membangun pangkalan, meneliti teknologi dan memproduksi unit.

Taktik Real-time (disingkat RTT dan kurang umum disebut sebagai fixed unit real-time strategy) adalah subgenre dari wargames taktis bermain di real-time simulasi pertimbangan dan keadaan perang operasional dan taktik militer.

Turn-Based Game Strategi (TBS) biasanya diperuntukkan bagi strategi permainan komputer tertentu, untuk membedakan mereka dari real-time strategi permainan komputer. Seorang pemain dari permainan turn-based diperbolehkan periode analisis sebelum melakukan aksi game. Contoh genre ini adalah Civilization , Heroes of Might and Magic , Making History , Muka Wars , Master of Orion , dan Worms seri.

Taktik Turn-Based ( TBT ), atau taktis turn-based ( TTB ), adalah genre strategi video game yang melalui stop-tindakan mensimulasikan pertimbangan dan keadaan perang operasional dan taktik militer di umumnya konfrontasi skala kecil dibandingkan dengan pertimbangan yang lebih strategis dari strategi turn-based (TBS) permainan.

PERMAINAN MENGGUNAKAN TAKTIK REAL TIME
Soldiers: Heroes of World War II adalah yang pertama dalam serangkaian taktik video game real-time yang diatur dalam Perang Dunia II, yang dikembangkan oleh atau di bawah pengawasan Ukrainian company Best Way. Pemain dapat mengendalikan pasukan Amerika, Inggris, Soviet, atau Jerman untuk memainkan pertempuran yang diatur dalam Perang Dunia II. Permainan ini terutama permainan strategi, tetapi pemain dapat mengendalikan pasukannya dan mengarahkannya dengan keyboard dan mouse untuk kedalaman kontrol tambahan.

Source:
http://jokomurdiyanto.blogspot.com/2014/04/pengantar-teori-game-tactikal-strategy.html
https://en.wikipedia.org/wiki/Soldiers:_Heroes_of_World_War_II

0 komentar:

[TUGAS] BAB 5 - TAKTIK DALAM PERMAINAN

06.21.00 Unknown 0 Comments


WAYPOINT
Waypoint adalah titik acuan / kumpulan koordinat yang digunakan untuk keperluan navigasi untuk mengidentifikasi sebuah titik di peta. Koordinat-koordinat itu biasanya menyertakan longitude, latitude, dan kadang altitude untuk keperluan navigasi di udara.
Waypoint digunakan di berbagai navigasi yang tidak memiliki jalur yang tampak seperti navigasi di udara dan navigasi di laut, juga navigasi di darat yang tidak memiliki jalur yang jelas. Khusus navigasi di darat yang tidak menggunakan manusia sebagai penentu arah melainkan robot, waypoint digunakan meski terdapat jalur yang jelas. Hal ini penting agar robot tetap memiliki rute.
Waypoint dibagi menjadi dua jenis, yaitu waypoint fly by dan waypoint fly over. Waypoint fly by tidak melewati lokasi di atas way point namun tetap menuju ke arah tujuan, sedangkan waypoint fly over melewati lokasi di atas way point. Setelah satu waypoint terlewati, maka pilot harus menetapkan waypoint berikutnya yang disebut dengan waypoint aktif. Waypoint merupakan kumpulan dari beberapa titik kordinat yang kemudian dijadikan sebagai navigasi pergerakan.
Dalam sebuah game, pergerakan NPC (non playable character) umumnya menggunakan titik arah antara titik kordinat yang satu dengan yang lain ditentukan oleh pencipta game. Waypoint dapat digunakan pada non playable character untuk melakukan patroli di dalam game dengan melintasi titik-titik kordinat yang ditentukan.

ANALISIS TAKTIK
Taktik adalah suatu siasat atau akal yang dirancang dan akan dilaksanakan dalam permainan oleh perorangan, kelompok, maupun tim untuk memenangkan suatu pertandingan secara sportif. Taktik biasanya merujuk bagaimana perorangan atau kelompok yang digunakan dalam permainan tertentu.

PATH FINDING
Path Finding atau pencarian jalur adalah proses pencarian rute atau jalur tedekat dari suatu start menuju tujuan dengan jalur yang memiliki pengahalang – penghalang dari arena tersebut. pathfinding ini pada umumnya adalah untuk mencari jalur paling efisien dengan sebisa mungkin menghindari penghalang yang ada.
Pathfinding dapat diterapkan misalnya dalam membuat AI dari suatu game, misalnya agar AI tersebut dapat mengejar musuh secara efisien dan tanpa menabrak tembok atau menghindari penghalang lain. Terdapat beberapa metode yang dapat diterapkan dalam pathfinding ini, salah satu metode yang sering digunakan adalah A*.


Source:
http://jokomurdiyanto.blogspot.com/2014/04/pengantar-teori-game-tactikal-strategy.html
https://gurusakti.wordpress.com/2013/06/28/mengenal-algoritma-a-untuk-pencarian-jalur-rute-terdekat/

0 komentar:

Langganan: Postingan (Atom)