CHECKERS

Tujuan.

Permainan  checkers  (dalam  bahasa  Inggris  Amerika) atau disebut draughts (dalam bahasa Inggris British)   merupakan permainan yang menggunakan strategi abstrak dimainkan oleh dua pemain dengan menggunakan langkah diagonal token dan menangkap dengan melompati token musuh.

Permainan ini telah dimainkan di Eropa sejak abad ke-16,   dikembangkan   dari   permainan   alquerque. 

Bentuk yang  paling  populer  dari  pemainan  ini  adalah international    draughts,   yang   dimainkan   pada   papan 10x10.  Bentuk  yang  juga  populer  adalah  English draughts,   yang  disebut  American   checkers,   dimainkan pada papan 8x8.

ALGORITMA MINIMAX

Algoritma  Minimax  merupakan  algoritma  yang digunakan untuk menentukan pilihan agar memperkecil kemungkinan kehilangan nilai maksimal. Algoitma ini diterpkan  dalam permainan  yang melibatkan  dua pemain seperti tic tac toe, checkers, go dan permainan yang menggunakan  strategi atau logika lainnya. Hal ini berarti permainan-permainan    tersbut   dapa   dijelaskan   sebagai suatu rangkaian aturan dan premis.

Algoritma   ini  mulai  dikembangkan   dari  teori  game zero-sum. Teori ini mendeskripsikan situasi dimana jika terdapat pemain yang mengalami pendapatan, pemain lain akan mengalami  kehilangan  dengan nilai yang sama dari pendapatan  tersebut,  dan  sebaliknya.  Jumlah  pendapatan dari  pemain  yang  dikurangi  dengan  jumlah  kehilangan akan berjumlah nol. Teori minimax menyatakan :

Untuk  setiap  dua  orang  pemain  dalam  zero-sum  game,

terdapat nilai V dari strategi yang dimiliki pemain seperti :

1.      Stratregi    yang    ditentukan    pemain    kedua    akan menghasilkan     konsekuensi     kemungkinan     untuk pemain pertama, V

2.      Strategi   yang   dutentukan    pemain   pertama   akan menghasilkan     konsekuensi     kemungkinan     untuk pemain pertama, -V

Secara  setara,  strategi  pemain  pertama  akan memastikan suatu nilai V tanpa memperdulikan strategi pemain kedua, dan bersamaan dengan itu pemain kedua akan memastikan dirinya kehilangan nilai sebesar –V.

Algoritma     Minimax     merupakan     algoritma     dasar pencarian   DFS  (Depth-First   Search)  untuk  melakukan

traversal dalam pohon. DFS akan mengekspansi simpul paling dalam terlebih daulu. Setelah simpul akar dibangkitkan,  algoritma  ini akan  membangkitkan  simpul pada tingkat kedua, yang akan dilanjutkan pada tingkat ketiga, dst. Dalam melakukan treversal, misalkan dimulai dari suatu  simpul  i, maka  simpul  selanjutnya  yang  akan dikunjungi adalah simpul tetangga j, yang bertetangga dengan   simpul   k,   selanjutnya   pencarian   dimulai   lagi secara   rekursif   dari   simpul   j.  Ketika   telah   mencapai simpul   m,   dimana   semua   simpul   yang   bertetangga dengannya  telah dikunjungi,  pencarian  akan dirunutbalik ke simpul terakhir yang dikunjungi sebelumnya dan mempunyai  simpul j yang belum dikunjungi.  Selanjutnya pencarian  dimulai  kembali  dari  j.  Ketika  tidak  ada  lagi simpul  yang  belum  dikunjungi  yang  dapat  dicapai  dari simpul yang telah dikunjungi maka pencarian selesai.

Dalam repersentasi pohon dalam algoritma Minimax, terdapat  dua  jenis  node,  yaitu  node  min  dan  node  max. Max  node  akan  memilih  langkah  dengan  nilai  tertinggi dan   min   node   akan   memilih   langkah   dengan   nilai terendah.  Berikut  merupakan  gambar  pohon  untuk algoritma Minimax.

Dalam  algoritma   ini,  langkah  yang  dapat  dilakukan pemain  ditentukan  oleh  langkah  pemain  lawan sebelumnya. Sebagai contoh pada tabel berikut di berikan tabel nilai yang memberitahukan hasil dari pilihan.

Dam-daman

Tujuan

Permainan   dam-daman   merupakan  permainan   tradisional yang berasal dari Indonesia. Dikutip dari http://www.urangkampoeng.com [7] berikut ini adalah peraturan dan petunjuk dalam permainan dam-daman:

1.     Menggunakan  papan  permainan,  berikut  gambar  dari papan permainan dam-daman:

Gambar 1 Papan Permainan Dam-daman [7]

2.     Dalam  sebuah  papan  permainan  dam-daman,  terdapat titik-titik  yang  digunakan pijakan  pada  masing-masing bidak. Diantara tiap-tiap titik terdapat garis horisontal, vertikal dan diagonal yang dijadikan jalur langkah bagi bidak.

3.     Menggunakan bidak permainan. Pemain 1 dan 2 memiliki bidak yang berbeda dengan jumlah 16 bidak untuk masing-masing pemain.

4.     Cara  permaianannya  adalah  dengan  cara  mengerakan bidaknya secara bergantian seperti bermain Catur, ketika pemain A sudah mengerakan bidak maka giliran B, dan seterusnya.

5.     Bidak hanya bisa dijalankan dengan satu langkah dengan bergerak maju atau ke samping mengikuti jalur (garis) papan permainan. Bidak tidak bisa bergerak mundur.

6.     Bagi bidak yang bisa sampai pada kotak segitiga lawan pada baris terakhir, maka bidak itu menjadi bidak raja yang bebas berjalan (maju ataupun mundur), asalkan masih pada satu garis lurus.

7.     Cara mengambil atau memakan bidak lawan dengan cara melompati bidak lawan dengan hanya jarak satu titik, dan berpeluang melompati kemungkinan yang ada dalam satu lompatan.

Gambar 2 Cara permainan Dam-daman

8.     Terdapat  sebuah  aturan  dimana  sebuah  bidak  wajib memakan bidak lawannyaa jika ada peluang, seperti Gambar   diatas, jadi bidak merah harus menggerakkan bidak yang ditengah untuk memakan bidak biru   tidak bisa menggerakkan bidak lainnya.

9.    Pemain yang kalah adalah pemain yang bidaknya sudah habis.

Algoritma Backtracking

Teknik runut balik (backtracking) merupakan salah satu teknik dalam penyelesaian masalah secara umum (General

Problem Solving). Adapun dasar dari teknik ini adalah suatu teknik pencarian (Teknik   Searching). Teknik pencarian ini digunakan dalam rangka mendapatkan himpunan penyelesaian yang mungkin. Dari himpunan penyelesaian yang mungkin ini akan diperoleh solusi optimal atau memuaskan [8].

Runut balik (backtracking) adalah algoritma yang berbasis pada   Depth   First   Search   (DFS)   untuk   mencari   solusi persoalan   secara   lebih   mangkus.       Runut   balik,   yang merupakan perbaikan dari algoritma   brute-force, secara sistematis mencari solusi persoalan di antara semua kemungkinan solusi yang ada. Dengan metode runut balik, kita tidak perlu memeriksa semua kemungkinan solusi yang ada.  Hanya  pencarian  yang  mengarah ke  solusi  saja  yang selalu dipertimbangkan. Akibatnya, waktu pencarian dapat dihemat.   Saat ini algoritma runut   balik banyak diterapkan untuk program permainan seperti permainan   tic-tac-toe, menemukan jalan keluar dalam sebuah labirin, catur, crossword puzzle, sudoku dan masalah-masalah pada bidang kecerdasan buatan (artificial intelligence) [9].

        Dalam penerapan algoritma Backtracking ada beberapa properti yang perlu dipertimbangkan, yaitu properti solusi persoalan, properti komponen vektor solusi dan properti kriteria pembatas.    

Dokkaebi  Shooter

Tujuan

Game  Dokkaebi  Shooter”.  Dalam penelitian  ini,  peneliti  mencoba  membuat  game  dengan  dasar  hiburan  namun  juga  bertujuan sebagai sarana melatih ketangkasan dengan penerapan penerapan algoritma boids pada pergerakan musuhnya dan algoritma collision detection untuk deteksi tabrakan atau serangan musuh . Game ini merupakan tembakan secara vertikal dengan berfokus pada pengumpulan skor dan melawan musuh utama yaitu dokkaebi. Dokkaebi adalah hantu korea berwujud monster.

Algoritma :

Collision Detection

Algoritma collision detection adalah proses pengecekan apakah beberapa buah objek spasial saling bertumpuk atau tidak. Jika ternyata ada paling sedikit dua buah objek yang bertumpuk, maka kedua objek tersebut dikatakan saling bertumpukkan.  Pada ruang spasial dua dimensi.Objek  yang bertumpuk berarti objek spasialnya beririsan (Nugraha, 2013).

Penerapan  algoritma  collision  detection  pada  game  dokkaebi  shooter,  yang menggambarkan alur dari algoritma collision detection, kemudian pengimplementasiannya  ke dalam source code. Source  Code Implementasi  Algoritma  Collision  Detection  Antara Dokkaebi   dan   Panah   Player   dan   implementasinya    dalam   antarmuka . Implementasi Algoritma Collision Detection dalam Antarmuka Aplikasi

Boids

Algoritma boids adalah sebuah algoritma yang merepresentasikan gerak dari sebuah kawanan.Perilaku yang dihasilkan sangat mirip dengan kumpulan ikan atau kawanan burung (Saleh dkk., 2013). Tiap boids memiliki set dari atribut berikut: posisi     , kecepatan     , up-vector     , dan tiga steering forces (separation, cohesion, dan alignment).

GAME LABIRIN

Tujuan

Labirin 2D

Permainan  game  Labirin  adalah  suatu  jenis permainan  yang  terlihat sederhana  namun mempunyai banyak teka-teki logika untuk menyelesaikannya. Dimana tampilannya dua dimensi (panjang dan lebar), hanya dapat dilihat dari satu sudut perspektif. Aplikasi permainan labirin 2D ini bersifat single-user. Tingkatan atau level  bermain pada  game  labirin  2D  ini  terletak pada penelusuran rute perjalanan yang harus dilalui oleh seorang pemain dalam menemukan jalur mana yang  tepat.  Object  digerakkan  dengan menggunakan tombol pada keyboard dengan menekan tombol panah atas untuk menggerakan maju    ke depan, tombol panah bawah untuk menggerakan mundur ke belakang, tombol panah kiri  untuk  menggerakan  belok    ke  kiri,  tombol panah kanan untuk menggerakan belok ke kanan. Hal ini dilakukan sampai object menemukan jalan keluar dan akan naik ke level berikutnya.

Gambar 1 : Game Labirin 2D

Algoritma Backtracking

Runut-balik  (backtracking) adalah  algoritma

yang berbasis pada Depth First Search (DFS) untuk mencari solusi persoalan secara lebih cepat. Runut-

balik,  yang  merupakan  perbaikan  dari  algoritma

brute-force, secara sistematis mencari solusi persoalan di antara semua kemungkinan solusi yang ada. Dengan langkah ini tidak perlu memeriksa semua kemungkinan solusi yang ada. Akibatnya waktu pencarian dapat dihemat. Runut- balik lebih alami  dinyatakan dengan  algoritma rekursif. Kadang disebutkan pula bahwa runut-balik merupakan bentuk tipical dari algoritma rekursif. Runut-balik pertama kali diperkenalkan oleh D. H. Lehmer pada tahun 1950. R.J Walker, Golomb, dan Baumert menyajikan uraian umum tentang runut- balik dan penerapannya pada berbagai persoalan. Saat ini, algoritma runut-balik banyak diterapkan untuk  program  games  (permainan)  menemukan jalan keluar dalam sebuah game labirin, dan masalah-masalah pada bidang kecerdasan buatan (artificial intelligence).

2.3 Pencarian Solusi Algoritma Backtracking

Pencarian      solusi      dengan      menggunakan

algoritma backtracking maka menggunakan pohon ruang  status.  Langkah-langkah  pencarian  solusi

adalah sebagai berikut :

1.  Solusi dicari dengan membentuk lintasan dari akar ke daun. Simpul yang sudah dilahirkan dinamakan simpul hidup dan simpul hidup yang diperluas dinamakan simpul-E (Expand- node).

2. Jika lintasan yang diperoleh dari perluasan simpul-E tidak mengarah ke solusi, maka simpul itu akan menjadi simpul mati dimana simpul itu tidak akan diperluas lagi.

3.  Jika posisi terakhir ada di simpul mati, maka pencarian   dilakukan   dengan   membangkitkan

simpul anak  yang  lainnya dan  jika  tidak  ada simpul  anak  maka  dilakukan backtracking ke simpul orang tua.

4.  Pencarian  dihentikan  jika  telah  menemukan solusi atau tidak ada simpul hidup yang dapat di diperluas.

Battle FireTujuan

Tujuan

permainan battle fire merupakan permainan yang dilakukan oleh dua orang. untuk menuju tahap selanjutya maka pemain harus menang pada tahap pertama. Pada tahap pertama pemain saling menjatuhkan. Permainan ini menggunakan sejata sebagai alatnya.  Pemain akan kalah jika terkena tembakan oleh lawan.

Algoritma
Algoritma pada permainan ini terletak pada ketika musuh mampu membaca pergerakan player dengan menembakkan tembakan dengan tujuan untuk mengalahkan player. Disisi lain player harus menghindari tembakan dan menambah score setinggi mungkin. Taktik permainan diperlukan player agar bisa menghindari tembakan dan menembak musuh dengan tepat untuk mendapatkan hasil skor yang maksimal.