## PENERAPAN ALGORITMA BACKTRACKING PADA  PERMAINAN CAPSA BANTING

## Bambang Fahrudin
Mahasiswa Teknik Informatika STMIK Budi Darma Medan Jl. Sisingamangaraja No.338 Simpang Limun Medan

## ABSTRAK
Permainan  Kartu  yang  bernama  Capsa  ini  termasuk  salah  satu  permainan  kartu  yang  paling  digemari  oleh  remaja. Permainan ini memiliki cukup banyak kemiripan dengan permainan kartu lainnya, yaitu Poker. Objektif dari permainan ini adalah  berusaha  menghabiskan  kartu  lebih  cepat  dari  lawan  dengan  menerapkan  strategi  yang  baik  untuk  memperoleh kemenangan.  Bahkan,  permainan  kartu  ini  telah  dibuat  versi  Softwarenya  oleh  berbagai  game  developer  dengan  nama NetBig2,Chinese  Poker,  dll.  Persoalan  optimasi  adalah  persoalan  yang  tidak  hanya  mencari  solusi,  tetapi  mencari  solusi terbaik. Solusi terbaik adalah solusi yang bernilai maksimum atau minimum dari sekumpulan solusi yang mungkin. Namun, adanya  hal-hal  tersebut  sering  dianggap  oleh  sebagian  pengguna  sebagai  kelemahan  yang  membuat  permainan  tersebut menjadi kurang variatif dan terkesan membosankan. Algoritma yang dapat digunakan untuk menyelesaikan masalah dalam permainan  capsa  adalah  Algoritma  Backtracking.  Algoritma  ini  digunakan  dalam  rangka  mendapatkan  himpunan penyelesaian  yang  mungkin  dan  akan  diperoleh  solusi  optimal.  Algoritma  Backtracking  akan  mencari  solusi  berdasarkan ruang solusi yang ada secara sistematis namun tidak semua ruang solusi akan diperiksa, hanya pencarian ynag mengarah kepada solusi ynag diperoses.
Kata Kunci : Algoritma Bactracking, Solusi Terbaik, Permainan Capsa Banting

## I. PENDAHULUAN
Komputer  yang  saat  ini  sudah  menjadi barang  kebutuhan  pokok  bagi  masyarakat  modern, menyebabkan banyaknya permainan kartu dan kasino yang  diciptakan  dalam  versi  komputer.  Sebut  saja Hearts,  Free  cell,  Solitaire,  Poker  dan  Black  Jack , game-game tersebut  sudah  cukup  terkenal  di masyarakat dan tersebar di berbagai sumber.
Capsa  Banting merupakan  salah  satu  permainan kartu yang cukup terkenal dikalangan remaja maupun orang  dewasa  di  indonesia.  Permainan  kartu  ini menggunakan  kartu  remi  sebagai  medianya,  kartu remi  adalah  sekumpulan  kartu  yang  berisi  simbol wajik,  keriting,  hati,  dan  sekop.  Dalam  capsa  ada urutan nilai yaitu dimulai dari 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A,dan yang paling tinggi adalah 2. Ada sebuah
constaint yaitu  pemain  tidak  bisa  memainkan  kartu yang nilainya lebih rendah dari kartu yang dimainkan oleh pemain sebelumnya.
Permainan capsa banting merupakan permainan yang membutuhkan logika serta perhitungan  untuk  menentukan  kombinasi  apa  yang mungkin  pada  13  kartu  yang  didapat  saat  ini. Permainan capsa  banting pada  dasarnya  dimainkan oleh  4  pemain,  dimana  setiap  pemain  mendapatkan 13 kartu. Permainan  ini  membutuhkan strategi untuk memperkirakan  kartu  apa  yang  ada  di  tangan  musuh atau  apa  yang  diperlukan  musuh  dengan  melihat pergerakkannya  dalam  mengambil  dan  membuang kartu.  Melalui  strategi  dan  perkiraan  yang  tepat, semakin besar pula kemungkinannya untuk menang.

## II. TEORITIS A. Penerapan
Menurut  Kamus  Besar  Bahasa  Indonesia (KBBI), pengertian penerapan adalah suatu perbuatan mempraktekkan  suatu  teori,  metode,  dan  hal  lain untuk  mencapai  tujuan  tertentu  dan  untuk  satu kepentingan  yang  diinginkan  oleh  suatu  kelompok atau  golongan  yang  telah  terencana  dan  tersusun sebelumnya.

## B. Algoritma
Menurut  Suarga,  dalam  bukunya  yang berjudul  Algoritma  Pemrograman  mengemukakan definisi algoritma sebagai berikut:
1. Algoritma merupakan teknik penyusunan langkah-langkah  penyelesaian  masalah  dalam bentuk  kalimat  dengan  jumlah  kata  terbatas, tetapi tersusun secara logis dan sistematis.
2. Algoritma merupakan suatu prosedur yang jelas untuk  menyelesaikan  suatu  persoalan  dengan
menggunakan  langkah-langkah  tertentu  dan terbatas jumlahnya.

## C. Capsa Bating
Capsa  adalah  permainan  kartu  yang  artinya tiga  belas.  Permainan  ini  juga  disebut Big  Two (karena  kartu  tetingginya  kartu  2)  atau Thirteen. Umumnya,    permainan  ini  dimainkan  oleh  empat orang.  Jadi    jika  dimainkan,  setiap  peserta  akan mendapatkan  13  kartu  (karena  jumlah  kartu  remi adalah  52).  Sementara  cara  bermain Capsa  banting lebih  menarik.  Disebut Capsa  Banting karena  setiap mengeluarkan  kartu  biasanya  dibanting.  Di Capsa Banting ini  bisa  dapat  pemenangnya  jika  bisa menghabiskan kartu paling pertama. Urutan kembang yang  tertinggi  hingga  terendah  adalah  dimulai  dari kembang yang paling tinggi adalah sekop diikuti hati, keriting, dan yang terakhir wajik.
Hirarki  kombinasi  kartu  pada  permainan Capsa Banting yaitu sebagai berikut :
1. Satuan  adalah  Kartu  yang  dikeluarkan  sendiri. Tanpa kartu lain.
2. Pasangan  ( Pair )  adalah  Kartu  yang  dikeluarkan sepasang  sekaligus.  Syarat  mengeluarkan  pair adalah  kedua  kartu  harus  memiliki  angka  yang sama.
3. Threes  adalah Kartu  yang  dikeluarkan  tiga sekaligus.  Syaratnya  adalah  ketiga  kartu  harus memiliki angka yang sama.
4. Straight /Seri  adalah  Merupakan  kombinasi dengan  angka  berurutan.  Misalnya  3-4-5-6-7, atau 9-10-J-Q-K.
5. Flush  adalah Merupakan  kombinasi  dengan kembang yang sama. Nama flush ditentukan dari kembangnya.
6. Fullhouse/Polo  adalah Merupakan  kombinasi antara pair dan threes .  Nama  polo  ditentukan dari threes nya.
7. Four  of  a  kind/  Piting  adalah Merupakan kombinasi empat kartu berangka sama dengan 1 kartu acak (bebas).
8. Straight flush/ Seri kembang adalah Merupakan kombinasi  5  kartu  berurutan.  Tapi  kembangnya juga  sama.  Misalnya  5 -6 -7 -8 -9 dengan bunga bercorak hati.
9. Capsa  atau  Dragon    adalah Seorang  pemain yang  mendapat capsa atau dragon (dalam Bahasa  Inggris)  akan  langsung  dinyatakan menang.

## D. Algoritma Backtracking
Algoritma runut balik pertama kali diperkenalkan  oleh  D.H  Lehmer  pada  tahun  1950. Algoritma ini cukup mangkus untuk digunakan dalam beberapa  penyelesaian  masalah  dan  juga  untuk memberikan kecerdasan buatan dalam game . Beberapa game populer  semisal  Sudoku,  Labirin, Catur juga bisa diimplementasikan dengan menggunakan algoritma runut balik. Algoritma runut balik  berbasis  pada  DFS  ( Depth  First  Search ) sehingga  aturan  pencariannya  akan  mengikut  kepada aturan  pencarian  DFS  yaitu  dengan  mencari  solusi dari akar ke daun (dalam pohon ruang solusi) dengan pencarian  mendalam.  Simpul-simpul  yang  sudah dilahirkan  (diperiksa)  dinamakan  simpul  hidup  ( live node ).  Simpul  hidup  yang  sedang  diperluas dinamakan simpul-E atau Expand Node.
Properti
Umum
Metode
Runut
Balik ( Backtracking ) Untuk  menerapkan  metode  runut-balik, properti berikut didefinisikan:
1.  Solusi persoalan. Solusi dinyatakan sebagai vektor n-tuple:
X=(x1, x2, ..., xn), xi anggota himpunan berhingga Si
Mungkin saja S1 = S2 = ... = Sn.
Contoh: Si = {0,1} Si = 0 atau 1
1. Fungsi pembangkit nilai xk
Dinyatakan sebagai:
T(k)
T(k) membangkitkan nilai untuk xk, yang merupakan komponen vektor solusi
1. Fungsi Pembatas (fungsi kriteria)
Dinyatakan sebagai:
B(x1, x2, ..., xk)
Fungsi pembatas  menentukan apakah (x1, x2, ..., xk) mengarah ke solusi. Jika ya, maka pembangkitan nilai untuk  xk+1  dilanjutkan,  tetapi  jika  tidak,  maka  (x1, x2,  ...,  xk)  dibuang  dan  tidak  dipertimbangkan  lagi dalam pencarian solusi.

## Pengorganisasian Solusi
Semua  kemungkinan  solusi  dari  persoalan disebut ruang  solusi ( solution space ).  Jika x i  S i , maka S 1  S 2  …  S n disebut ruang solusi. Jumlah anggota di dalam ruang solusi adalah | S 1 |  | S 2 |  …  | S n |.  Tinjau  persoalan Knapsack 0/1  untuk n =  3. Solusi persoalan dinyatakan sebagai vektor ( x 1 , x 2 , x 3 ) dengan x i  {0,1}.  Ruang solusinya adalah {0,1}  {0,1}  {0,1} = {(0, 0, 0),  (0, 1, 0), (0, 0, 1),
(1, 0, 0), (1, 1, 0), (1, 0, 1),
(0, 1, 1), (1, 1, 1)}.
Pada  persoalan Knapsack 0/1  dengan n =  3  terdapat 2 n = 2 3 = 8 kemungkinan solusi,  yaitu:
(0, 0, 0), (0, 1, 0), (0, 0, 1), (1, 0, 0), (1, 1, 0), (1, 0, 1),  (0,  1,  1),  dan  (1,  1,  1).  Penyelesaian  secara exhaustive  search adalah  dengan  menguji  setiap kemungkinan  solusi.    Ruang  solusi  diorganisasikan ke  dalam  struktur  pohon.  Tiap  simpul  pohon menyatakan  status  ( state )  persoalan,  sedangkan  sisi (cabang)  dilabeli  dengan  nilai-nilai x i .  Lintasan  dari akar  ke  daun  menyatakan  solusi  yang  mungkin. Seluruh lintasan dari akar ke daun membentuk ruang solusi.  Pengorganisasian  pohon  ruang  solusi  diacu sebagai pohon ruang  status ( state space tree ). Tinjau kembali persoalan Knapsack 1/0 untuk n = 3.
Gambar 1: Tree solusi
Langkah-langkah pencarian solusi denagn algoritma Backtracking adalah sebagai berikut:
1. Solusi dicari dengan membentuk lintasan dari akar ke  daun.  Aturan  yang  dipakai  adalah  mengikuti metode  pencarian  mendalam  (DFS).  Simpul- simpul  yang  sudah  dilahirkan  dinamakan  simpul hidupm  dan  simpul  hidup  yang  sedang  diperluas dinamakan  simpul-E.  Simpul  dinomori  dari  atas ke bawah sesuai dengan kelahirannya.
2.  Jika  lintasan  yang  diperluas  yang  sedang  dibentuk tidak mengarah ke solusi, maka simpul-E tersebut “dibunuh”  sehingga  menjadi  simpul  mati  ( dead node ).  Simpul  yang  sudah  mati  ini  tidak  akan diperluas lagi.
3.  Jika  pembentukan  lintasan  berakhir  dengan  simpul mati,  maka  proses  pencarian  diteruskan  dengan membangkitkan  simpul  anak  lainnya.  Bila  tidak ada  lagi  simpul  anak  yang  dibangkitkan,  maka pencarian  solusi  dilanjutkan  dengan  melakukan runut-balik  ( backtracking )  ke  simpul  hidup terdekat. Selanjutnya simpul ini menjadi simpul-E yang terbaru.
4.  Pencarian  dihentikan  bila  telah  ditemukan  solusi atau tidak ada lagi simpul hidup untuk runut balik
( backtracking ).

## III. ANALISA DAN PEMBAHASAN
Untuk  sebuah game dibuat  langkah  dalam menyelesaikan  permainan  dan  dapat  memecahkan permainan  tersebut.  Untuk  mengembangkan  ilmu pengetahuan tentang kecerdasan buatan atau Artifitical  intelligence (AI)  pada game dan  dapat digunakan dalam prinsip-prinsip bidang yang mampu memberikan penyelesaian langkah-langkah permainan  dengan  baik  dan  mampu  mengambil keputusan  yang  terbaik  agar  dapat  mengalahkan pemain  atau  setidaknya  menghalau  pemain  menang. Berdasarkan  analisa  diatas  maka  penulis  ingin menggunakan algoritma backtracking untuk menyelesaikan  permainan capsa  banting .  Algoritma backtracking digunakan  dalam  rangka  mendapatkan himpunan  penyelsaian  yang  mungkin  dan  akan diperoleh  solusi  optimal  atau  memuaskan.  Dalam suatu  permainan  yang  berbasis  giliran( turn  based game ),  untuk  melihat  kondisi  permainan  dan memberikan nilai dari sudut pandang pemain.

## Penerapan Algoritma Backtracking
Algoritma  runut  balik  ( backtracking )  berbasis pada  DFS  ( Depth  First  Search )  sehingga  aturan pencariannya  akan  mengikut  kepada  pencarian  DFS yaitu dengan mencari solusi dari akar ke daun (dalam pohon ruang solusi) dengan pencarian mendalam.
Dalam  permainan  Capsah  Banting  ini  dibagi menjadi  2  yaitu, first  turn (giliran  pertama)  dan second  turn  /  not  first  turn (bukan  giliran  pertama). Kondisi first  turn dan second  turn memiliki perbedaan  besar,  dalam first turn pemain  bebas mengeluarkan  kartu  apa  saja  (asalkan  memenuhi syarat),  sedangkan  dalam second  turn pemain  harus mengeluarkan  kategori  kartu  seseuai  kartu  yang sudah  berada  di  meja  (kartu  yang  telah  dikeluarkan lawan).
Contoh  Kasus  Pohon  Solusi  untuk  menentukan prediksi  strategi  permainan  yang  menggunakan algoritma backtracking sebagai langkah penyelesaian pencarian solusi pada permainan Capsa Banting .
1. Diasumsikan kondisi permainan Sekumpulan kartu awal yang terjadi setelah di acak, maka
akan mencari keputusan terbaik menggunakan pohon keputusan.
Tabel 1: Kartu Random yang terjadi dalam permainan
Pohon keputusan pencarian kartu terbaik.
Gambar 2: pohon keputusan
Tabel 2: Tabel Kemungkinan yang terjadi apabila keputusan sementara 9♣ 2♣ K ♥ 4 ♥ 4 ♦ J ♦ 2♣ K ♥ 4 ♥ 4 ♦ Q ♦ 2♣ K ♥ 4 ♥ 4 ♦ 2♠ 2♣ K ♥ 4 ♥ 4 ♦ 5 ♦ 5♠ K ♥ 4 ♥ 4 ♦ 5 ♦ 5♠ K ♥ K♣ 4 ♦ 5 ♦ 5♠ K ♥ K♣ Q ♦
Hasil pencarian keputusan 5 kartu terbaik adalah Two pair

## Tabel 3: Tabel Kemungkinan yang terjadi apabila Keputusan Terbaik
2. Diasumsikan  kondisi  permainan  sekumpulan dari  sisa  kartu  yang  tertinggal  dari  giliran pertama.  maka  akan  mencari  keputusan  terbaik menggunakan pohon keputusan.
Tabel 4: Sisa Kartu Pencarian
Pohon keputusan pencarian kartu terbaik.
Gambar 3: Pohon Keputusan 5 ♦ 5 ♠ K ♥ K ♣ Q ♦
Tabel 5: Tabel Kemungkinan yang terjadi apabila Keputusan Sementara 9♣ 2♣ 4 ♥ 4 ♦ 2♠ J♠ 2♣ 4 ♥ 4 ♦ 2♠ 9♣ 9 ♥ 4 ♥ 4 ♦ 2♠ 9♣ 9 ♥ 4 ♥ 4 ♦ J♠
Hasil pencarian keputusan 5 kartu terbaik adalah Two pair
Tabel 6: Tabel Kemungkinan yang terjadi apabila Keputusan Terbaik

## V. IMPLEMENTASI
Tampilan Menu Utama Gambar 4: Form Menu utama
Tampilan Form Game
Gambar 5: Form game memulai permainan
Tampilan Form Options Gambar 6: Form Options

## V. KESIMPULAN
Setelah menerapkan dan mengaplikasikan kedalam perangkat lunak permainan Capsa banting menggunakan algoritma backtracking maka dapat diambil kesimpulan bahwa :
1. Permainan  kartu  capsa  banting  ini  melibatkan faktor  peluang,  dalam  langkah-langkah  untuk penyelesaiannya  harus  memiliki  kesempatan untuk  seorang  pemain  mendapatkan  kartu bernilai  tinggi  atau  rendah  ketika  kartu dibagikan  pada  awal  permainan.  Karena  itu sebaik  apapun  algoritma  yang  digunakan  tetap memiliki  peluang  kekalahan  yang  besar  jika kartu yang dimiliki bernilai rendah.
2. Dengan  menerapkan  algoritma  backtracking, diharapkan  mampu  menyelesaikan  masalah pada  permainan  capsa  banting,  yaitu  adanya memiliki  kesempatan  pemain  mendapatkan kartu bernilai tinggi atau bernilai rendah.

## VI. DAFTAR PUSTAKA
[1]. Dikse  I  Wayan  dan  Sundika  I  Putu,  “ Animasi  Dengan Flash 8 ” , Graha Ilmu,Yogyakarta 2011.
[2]. Kadir  Abdul,” Algoritma  Dan  Pemrograman ”,  Penerbit
Andi, Yogyakarta, 2012.
[3]. Nugroho  Adi ,” Rekayasa  Perangkat  Lunak  Berorientasi Objek ”, Penerbit Andi,  Yogyakarta,2010. [4]. Suyanto,” Artificial  Intelligence ”, Informatika  Bandung, 2014.
[5]. Rahmad  Nasution  (2014),  ” Penerapan Algoritma Backtracking  Pada  Permainan  Math  maze ”, Volume  :
VII, Nomor: 3, Agustus 2014  ISSN : 2301-9425. [6]. Rina  Br  Sirait  (2013),  ” Perancangan  Aplikasi  Game Labirin Dengan Menggunakan Algoritma Backtracking ”, Volume  :  V,  Nomor:  2,  Desember  2013 ISSN : 2301-9425.
[7]. http://www.big-2.net/permainan-kartu-capsa-di- indonesia.html , diakses 20 April 2015.
[8]. http://www.pagat.com/climbing/bigtwo.html, Rules of card games: Big Two , diakses Juli 2015 [9]. http://kbbi.web.id , diakses 30 April 2015.