ANALISIS GAME

            Permainan atau yang lebih dikenal dengan sebutan game kini sering dimainkan oleh berbagai lapisan masyarakat pada zaman sekarang permainan lebih mudah dan dapat dijumpai di berbagai media-media seperti computer, smartphone, tablet, dan lain-lain. Game yang mencakup didalamnyapun sangat bermacam-macam, contohnya seperti game strategi, game RPG, game race dan masih banyak yang lainnya. Game – game yang diciptakan tentunya mengunakan alat – alat dan aturan – aturan yang wajib aja. Seperti game – game berikut ini diciptakan menggunakan berbagai jenis algoritma baik itu algoritma Greedy, algoritma Backtracking, Minimax dan yang lain – lain.

Algortima – algoritma tersebut dimasukan kedalam suatu wadah yang disebut namanya adalah Artificial Intelligence (AI) atau kecerdasan buatan merupakan salah satu cabang ilmu computer yang mempelajari bagaiman cara membuat mesin cerdas, yaitu mesin yang mempunya belajar dan beradaptasi terhadap ssesuatu. Tujuan dari riset – riset AI adalah bagaimana sebuah mesin bisa berfikir sama halnya denngan manusia yang bisa berfikir. Ai digunakan untuk menjawab problem yang tidak dapat diprediksi dan tidak bersifat algoritmik atau procedural. Sampai saat ini, para peneliti di bidang AI masih bekerja keras untuk kompleksitas penelitian di bidang AI serta factor dukungan teknologi untuk merealisasikannya.

                  

   Labirin adalah salah satu game yang menggunakan algortima, cara permainan game ini adalah mencari jalan keluar dimana dalam perjalanan labirin ini banyak mendapat rintangan atau halangan untuk sampai pada tujuan, dan biasanya di tiap – tiap perjalan terdapat bonus skor yang berbagai macam maksud dari bonus tersebut, ada yang menambah nilai, ada yang menambah waktu permainan dan lain – lain. Juga terdapat bonus skor yang dapat menaikan ke level berikutnya maka untuk mencapai tujuan dibutuhkan sebuah solusi, solusi yang dipakai adalah algoritma backtracking. Algoritma Backtracking (runut balik) merupakan sebuah algoritma yang bisa digunakan untuk membuat aplikasi game labirin. Dengan cara kerjanya yang mecari jalan keluar yang bertujuan untuk menentukan jalan yang tepat untuk mencapai tujuan yang telah ditentukan. Selama proses penentuan jalur tersebut, jika menemui jalan buntu maka akan melakukan proses backtrack sampai kembali menemukan jalur yang tepat untuk mencapai tujuan. Proses mencari jalan keluar permainan labirin dengan cara membentuk lintasan dari akar ke daun dan simpul – simpul yang sudah dilahirkan dinamakan simpul hidup, jika lintasan yang diperluas yang sedang dibentuk tidak mengarah ke solusi, maka simpul tersebut dibunuh sehingga menjai simpul mati (dead node) simpul yang sudah mati ini tidak akan diperluas lagi.

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).

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.

 

Analisa Pencarian Solusi Game Labirin dengan Algoritma Backtracking Algoritma Backtracking mencari solusi persoalan diantara kemungkinan solusi yang ada tidak perlu melalui path yang berulang-ulang sehingga menghemat waktu. Langkah – langkah algoritma backtracking mencari solusi adalah sebagai berikut : 

1. Solusi dicari dengan membentuk lintasan dari akar ke daun. Aturan yang dipakai adalah mengikuti metode depth first search (DFS). Simpul-simpul yang sudah dilahirkan dinamakan simpul hidup dan simpul hidup yang sedang diperluas dinamakan simpul-E.Simpul di nomori 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).

 

   

   Ludo adalah sebuah permainan papan yang dimainkan hampir seluruh belahan dunia. Permainan ini dimenagnkan dengan memindahkan pion-pion yang kita miliki menuju kotak tujuan. Berbagai taktik dapat digunakan untuk mencapai tujuan tersebut. Dengan algoritma greedy kita dapat membuat berbagai taktik untuk dapat memenangkan permainan ini.

Pada makalah ini akan dibahas berbagai taktik greedy yang dapat digunakan untuk memainkan permainan.

 

Greedy

adalah salah satu algoritma yang paling sering digunakan untuk menyelesaikan sebuah persoalan optimasi. Persoalan optimasi adalah persoalan dimana kita mencari suatu solusi yang dapat menyelesaikan persoalan tersebut secara optimum. Persoalan optimasi secara garis besar terbagi dua, yaitu:

1.Persoalan optimasi maksimasi Persoalan optimasi maksimasi adalah persoalan dimana kita mencari solusi untuk memperoleh hasil sebesar mungkin.

2. Persoalan optimasi minimasi. Persoalan optimasi minimasi adalah persoalan dimana kita mencari solusi biasanya dengan membutuhkan biaya sesedikit mungkin.

 

Beberapa persoalan yang biasanya diselesaikan dengan greedy antara lain persoalan knapsack, yaitu persoalan penempatan barang ke dalam sebuah kantung dengan batasan berat namun dapat menghasilkan keuntungan sebesar mungkin atau persoalan penukaran uang, yaitu persoalan menukarkan uang dengan sejumlah koin namun dengan jumlah koin sesedikit mungkin.

 

Algoritma greedy memiliki konsep sesuai dengan namanya greedy yang berarti rakus atau tamak. Algoritma ini akan membentuk solusi langkah per langkah. Pada setiap langkah penyelesaian masalah terdapat banyak pilihan langkah yang dapat kita ambil. Pada algoritma ini kita berusaha mengambil keputusan terbaik yang dapat diambil pada saat ini. Pengambilan langkah terbaik pada saat ini disebut optimum lokal. Dengan mengambil langkah yang memberikan optimum lokal pada setiap langkah diharapkan kita dapat mencapai optimum global.

 

PENERAPAN ALGORITMA GREEDY

Terdapat beberapa taktik yang mengimplementasikan greedy untuk menyelesaikan permainan ludo ini. Setiap taktik berisi cara yang berbeda. Pada bagian ini akan dibahas beberapa cara penyelesaian tersebut. Sebelumnya akan dibahas struktur data permainan ludo ini. Pada permainan ludo ini terdapat kelas pion yang memiliki atribut berupa posisi pion. Kelas pion ini akan dimiliki oleh kelas pemain yang memiliki array yang berisi empat buah pion. Kelas pemin juga memiliki prosedur melangkah yang akan mengubah posisi pion pada kelas papan. Terkahir terdapat kelas dadu yang akan mengacak angka dan dapat diambil oleh kelas lain.

 

A. Greedy by no one left behind

Pada greedy ini, algoritma akan berusaha untuk mengerakkan semua pion menuju titik tujuan bersama-sama. Setiap langkah yang dapat diambil digunakan untuk menggerakkan semua pion agar semakin dekat dengan tujuan. Sebelum melangkah dipilih pion dengan prioritas tertinggi. Pion dengan prioritas tertinggi adalah pion yang paling belakang dan dapat melangkah. Dengan memilih pion paling belakang kita melangkah dengan tujuan seluruh pion bergerak bersama menuju tujuan. Di bawah ini adalah pseudocode greedy by no one left behind.

 

B. Greedy by hitter

Pada greedy ini, algoritma akan berusaha untuk menggerakkan pion agar dapat memukul pion pemain lain. Pemilihan pion yang digerakkan adalah berdasarkan prioritas tergantung kondisi pion saat ini. Prioritas paling tinggi adalah pion yang paling dekat pion lain dan dapat memukul pion pemain lain. Prioritas kedua adalah jika tidak bisa memukul pion lain, pion tersebut akan maju mendekati pion lawan yang terdekat. Jika tidak ada pion yang memungkinkan, maka algoritma akan mencari pion lain yang dapat digerakkan. Di bawah ini adalah pseudocode greedy by hitter.

 

C. Greedy byquick move

Pada greedy ini, algoritma akan berusaha untuk menggerakkan pion secepat mungkin menuju tujuan. Pemilihan pion yang akan digerakkan berdasarkan prioritas. Prioritas tertinggi adalah pion yang dapat bergerak dan berada paling dekat dengan tujuan. Dengan menggerakkan pion yang paling dekat dengan kotak tujuan, kita akan lebih cepat mencapai tujuan. Selama pion yang paling dekat dengan kotak tujuan tidak terhalangi, maka seluruh langkah yang dapat diambil akan digunakan untuk memajukan pion tersebut. Jika tidak ada yang bisa bergerak maka algoritma akan menggerakkan pion lainnya sejumlah angka yang tertera di dau atau sisa langkah yang dapat diambil.

 

D. Greedy by blocking

Pada greedy ini, algoritma akan berusaha untuk menggerakkan pion dengan tujuan menghalangi pemain lain. Prioritas utama dari algoritma ini adalah menggabungkan lebih dari satu pion agar dapat menjadi penghalang. Jika ada pion yang dapat digabung, pion tersebut akan maju ke tempat pion yang ada. Kemudian penghalang tersebut akan tetap diam sampai tidak ada langkah lain yang dapat diambil. Jika tidak ada pion yang dapat digabung, maka algoritma akan memilih salah satu pionselain pion yang menjadi penghalang yang dapat dijalankan sejauh langkah yang tersisa atau angka yang keluar pada dadu.

 

Tic Tac Toe adalah game papan dengan kotak - kotak diatasnya sebagai penanda batas. game ini adalah salah satu game yang menggunakan algoritma minimax. Algoritma minimax adalah suatu algoritma yang menggunakan teknik pencarian Depth-First Search dengan kedalaman terbatas. Adapun media yang cocok untuk penerapan algoritma minimax adalah permainan Tic - Tac - Toe, beberapa alasan mengapa Tic - Tac -  Toe digunakan sebagai media penerapan kecerdasan buatan antara lain Tic - Tac - Toe sangat mudah menentukan ukuran kesuksesan atau kegagalan, sangat mungkin untuk dibandingkan dengan kemampuan manusia, mudah dimainkan.

 

Analisis Algoritma Minimax

Peran komputer sebagai lawan tanding tentunya harus didukung dengan kemampuan yang dimiliki oleh komputer, dengan demikian algoritma minimax yang diterpakan pada algoritma dari bentuk permainan tersebut bertujuan agar komputer memiliki kemampuan tanding yang baik.

 

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.

Othello atau Reversi adalah permainan yang menggunakan papan (board game) dan sejumlah koin yang berwarna gelap (misalnya hitam) dan terang (misalnya putih). Ukuran papan biasanya 8 x 8 kotak (grid) dan jumlah koin gelap dan koin terang masing-masing sebanyak 64 buah. Sisi setiap koin memiliki warna yang berbeda (sisi pertama gelap dan sisi kedua terang). Pada permainan ini kita asumsikan warna hitam dan putih. Jumlah pemain 2 orang.

Dalam permainan ini setiap pemain berusaha mengganti warna koin lawan dengan warna koin miliknya (misalnya dengan membalikkan koin lawan) dengan cara “menjepit” atau memblok koin lawan secara vertikal, horizontal, atau diagonal. Barisan koin lawan yang terletak dalam satu garis lurus yang diapit oleh sepasang koin pemain yang current diubah (reverse) warnanya menjadi warna pemain yang current.

Setiap pemain bergantian meletakkan koinnya. Jika seorang pemain tidak dapat meletakan koin karena tidak ada posisi yang dibolehkan, permainan kembali ke pemain lainnya. Jika kedua pemain tidak bisa lagi meletakkan koin, maka permainan berakhir. Hal ini terjadi jika seluruh kotak telah terisi, atau ketika seorang pemain tidak memiliki koin lagi, atau ketika kedua pemain tidak dapat melakukan penempatan koin lagi. Pemenangnya adalah pemain yang memiliki koin paling banyak di atas papan.

Algoritma Greedy dapat diaplikasikan untuk memenangkan permainan. Algoritma greedy berisi sejumlah langkah untuk melakukan penempatan koin yang menghasilkan jumlah koin maksimal pada akhir permainan. Algoritma Greedy dipakai oleh komputer pada tipe permainan komputer vs manusia.

Dua strategi greedy heuristik: 1.Greedy by jumlah koin Pada setiap langkah, koin pemain menuju koordinat yang menghasilkan sebanyak mungkin koin lawan. Strategi ini berusaha memaksimalkan jumlah koin pada akhir permainan dengan menghasilkan sebanyak-banyaknya koin lawan pada setiap langkah. 2.Greedy by jarak ke tepi Pada setiap langkah, koin pemain menuju ke koordinat yang semakin dekat dengan tepi arena permainan. Strategi ini berusaha memaksimumkan jumlah koin pada akhir permainan dengan menguasai daerah tepi yang sulit untuk dilangkahi koin lawan. Bahkan untuk pojok area yang sulit dilangkahi lawan.  

Greedy by Jumlah Koin 1.Himpunan kandidat Langkah-langkah yang menghasilkan jumlah koin yang diapit. 2.Himpunan solusi Langkah-langkah dari Himpunan kandidat yang memiliki jumlah koin diapit paling besar. 3.Fungsi seleksi Pilih langkah yang memiliki jumlah koin diapit paling besar 4.Fungsi kelayakan Semua langkah adalah layak 5.Fungsi obyektif Maksimumkan jumlah koin lawan.

Checkers

Algoritma greedy merupakan algoritma yang populer untuk memecahkan masalaha optimasi. Algoritma ini sederhana dan lempang. Prinsip dari algoritma greedy adalah “ take what can you get now!”. Algoritma greedy membentuk solusi langkah perlangkah. Pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan dan keputusan yang sudah diambil tidak bisa diubah lagi dan diulang. Algoritma greedy menggunakan pendekatan membuat pilihan yang terlihat seperti solusi terbaik dengan membuat pilihan solusi optimum lokal. Dari solusi itu, untuk setiap langkah yang membawa solusi optimum, diharapkan mampu menjadi solusi optimum global. Persoalan optimasi dalam algoritma greedy disusun oleh elemen-elemen sebagai berikut:

1. Himpunan kandidat, C.

Himpunan ini berisi dari himpunan-himpunan pembentuk solusi.

Pada tiap langkah, satu buah kandidat diambil dari himpunannya.

 

2. Himpunan solusi,S.

Himpunan ini berisi kandidat yang terpilih

sebagai solusi dari persoalan yang diangkat

 

3.Fungsi seleksi.

Fungsi yang ada pada setiap langkah

dalam memilih kandidat yang

paling memungkinkan mencapai solusi optimal.

 

4. Fungsi kelayakan.

Fungsi yang memeriksa apakah kandidat

yang dipilih dapat memberikan

solusi yang layak, yakni kandidat

bersama-sama dengan himpunan

solusi yang terbentuk tidak melanggar kendala yang ada.

 

5. Fungsi obyektif.

Fungsi yang mengoptimumkan

(memaksimalkan atau meminimumkan) nilai solusi.

 

Namun algoritma greedy belum tentu menghasilkan solusi yang optimum global. Hal ini dikarenakan algoritma greedy tidak beroprasi secara menyeluruh terhadap semua alternatif solusi yang ada dan pemilihan fungsi seleksi yang biasanya didasarkan pada fungsi obyektif.

 

Permainan Checkers

Permainan checkers (draughts) merupakan salah satu jenis permaian board games. Dimana jenis permainan ini menggunakan alat bantu papan sebagai alas dan arena bermainnya. Permainan ini dimainkan oleh 2 orang pemain. Satu pemain memainkan koin berwarna terang, dan lainnya memainkan koin berwarna gelap. Pemain dengan koin berwarna gelap memulai langkah awal terlebih dahulu. Beberapa komponen dalam permainan checkers :

 

1.Pemain.

    Permainan ini dimainkan oleh dua orang. Berperan

  sebagai lawan satu sama lain.

 

2.Papan.

      Papan yang digunakan dalam permainan ini mirip

     dengan papan catur. Terdiri dari 8 x 8 kotak-kotak

  kecil warna terang dan gelap.

 

3.Koin.

   Koin yang digunakan berbentuk silinder datar

    seperti koin pada umumnya. Koin yang digunakan

               pada permainan ini berwarna terang dan gelap.

               Pada awalnya, warna terang direpresentasikan

               dengan warna putih dan warna gelap

    direpresentasikan dengan warna merah. Tapi pada

perkembangannya,banyak warna yang digunakan

 untuk menggantikan warna-warna tersebut.

 

4.Posisi awal.

     Masing-masing pemain mempunyai 12 koin

 sewarna yang diletakkan pada 3 baris pertama pada

bidang yang terdekat dengan pemain dan diletakkan

 pada bidang yang berwarna gelap. Pemain yang

 memainkan koin berwarna gelap, memulai langkah

awal terlebih dahulu.

 

5.Cara bergerak.

Koin bergerak secara diagonal mengikuti warna

       bidang yang gelap, satu di tiap langkahnya. Cara

lain adalah dengan melangkahi satu buah koin

      lawan. Keadaan itu mungkin dapat dilakukan jika

  pada diagonal setelah koin lawan, merupakan

   bidang kosong. Jika langkah kedua itu terjadi, koin

     lawan yang dilangkahi mati, dan harus keluar dari

   bidang permainan. Koin dengan pangkat “biasa”

     hanya dapat bergerak maju. Namun, koin dengan

  pangkat “raja”, dapat bergerak maju maupun

  mundur.

 

6.Raja.

    Raja merupakan sebutan untuk koin yang mendapat

perlakuan istimewa. Koin ini adalah koin yang

     bertahan dan berhasil masuk ke ujung baris bidang

lawan. Koin ini didefinisikan sebagai tumpukan

      dari dua koin biasa. Keistimewaan koin ini adalah

  dapat bergerak baik maju maupun mundur.

  

7.Permainan selesai.

  Permainan selesai ditandai oleh habisnya koin

   lawan pada bidang permainan atau koin sudah tidak

   dapat bergerak kemanapun.

 

 

 

 

Daftar Pustaka

[1] Rina Br Sirait. 2013. Perancangan Aplikasi Game Labirin Dengan Menggunakan Algoritma Backtracking.

 [2] Lio Franklyn Kemit. 2012. Penentuan Langkah Dengan Greedy Dalam Permainan Ludo.

 [3] Tami Utiwi Handayani. 2008. Penggunaan Algoritma Greedy Dalam Menyelesaikan Permainan Checker.