Algoritma Dalam Game

Mengenal Algoritma dan Contoh Implementasi Algoritma dalam Pembuatan Game

Tulisan ini mengulas tentang algoritma dalam game, memang tidak lengkap karena saya bukan basik/ahlinya. tetapi sedikit harapan saya semoga dapat bermanfaat...

  

Platform game atau sering disebut paltformer merupakan salah satu genre dalam video game yang dikarakterisasikan dengan melompat antar platform atau obstacle lain. Dibutuhkan pengendalian dari pemain untuk mencegah karakter jatuh dari platform atau salah melompat. Contoh-contoh game ini bervariasi, beberapa mekanisme lompatan di modifikasi dengan bantuan alat-alat tertentu seperti tali pengayun dengan panjang yang telah diatur, atau melompat dari trampoli atau pegas. Dalam platform game mengharuskan pemain mengarahkan suatu obyek dengan melalui berbagai tahap atau tingkatan area untuk menyerang musuh dan menghindar terhadap serangan. Tipe game ini sedikit serupa dengan action game, tetapi aksinya tidak secepat action game. Teknik collision detection sangat sering dimanfaatkan pada tipe game ini, contohnya : Sonic The Hedgehog & Mario Bros. Platform game pada awalnya tercipta pada tahun 1980-an, dengan penerusnya berupa 3D platform yang dipopulerkan pada pertengahan 1990-an. Untuk melakukan lompatan dan gerakan lainnya perlu di terapkannya algoritma. Disini algoritma secara umum mempunyai pengertian serangkaian urutan langkah-langkah yang tepat, logis, terperinci, dan terbatas untuk menyelesaikan suatu masalah yang disusun secara sistematis, dalam kaitannya dengan pembuatan game algoritma sangat dibutuhkan untuk rancangan awal sebuah game.

Pada Pembahasan kali ini akan diuraikan dasar-dasar algoritma dalam pembuatan game. Seperti yang telah diuraikan diatas algoritma digunakan salah satunya untuk melakukan mekanisme lompatan, untuk lebih jelasnya akan di bahas terlebih dahulu mengenai jenis-jenis algoritma dalam pembuatan game.

1. MINIMAX, Sebuah prosedur pencarian yg melihat kedepan, memperhatikan apa yg akan terjadi, kemudian yang digunakan untuk memilih langkah berikutnya.
2. ALPHA-BETA PRUNING, Algoritma ini merupakan improvisasi dari algoritma minimax. Algoritma ini untuk meningkatkan efisiensi fungsi minimax dalam hal pencarian, kemudian fungsi evaluasi ditambahkan sepasang nilai alpha dan beta.
3. FUZZY, Logika fuzzy merupakan pengembangan dari logika boolean. Sistem fuzzy atau logika fuzzy adalah salah satu bahasa soft computing yang memiliki karakteristik dan keunggulan dalam menangani permasalahan yang bersifat ketidakpastian dan kebenaran parsial. Logika fuzzy merupakan pengembangan dari logika boolean yang hanya memiliki nilai true (1) atau false (0).
4. ALGORITMA GENETIKA, Algoritma genetika adalah algoritma yang berusaha menerapkan pemahaman mengenai evolusi alamiah pada tugas-tugas pemecahan masalah (problem solving). Pendekatan yang diambil oleh algoritma ini adalah dengan menggabungkan secara acak berbagai pilihan solusi terbaik di dalam suatu kumpulan (populasi) untuk mendapatkan generasi solusi terbaik berikutnya yaitu pada suatu kondisi yang memaksimalkan kecocokannya atau lazim disebut fitness.
5. ALGORITMA AI (ARTIFICIAL INTELEGENCE), Kecerdasan Buatan (Artificial Intelligence) merupakan cabang terpenting dalam dunia computer yang membuat agar mesin (computer) dapat melakukan pekerjaan seperti dan sebaik yang dilakukan manusia. Pada awalnya diciptakan computer hanya berfungsi sebagai alat hitung. Tapi sekarang peran computer makin mendominasi kehidupan manusia.
6. ALGORITMA A * ( A STAR)
7. ALGORITMA BREADTH FIRST SEARCH
8. ALGORITMA BACKTRACKING
9. ALGORITMA FORWARD CHAINING 
10. ALGORITMA DEPTH-FIRST SEARCH dan ALGORITMA NEGAMAX  

 

Agar kita dapat menggunakan algoritma yang sesuai dengan game yang akan dibuat maka alangkah baiknya kita analisis terlebih dahulu algoritma yang akan di pakai Untuk melihat faktor efisiensi & efektifitas dari algoritma tersebut), dapat dilakukan terhadap suatu algoritma dengan melihat pada:

- Waktu tempu (Running Time) dari suatu algoritma: adalah satuan waktu yang ditempuh atau diperlukan oleh suatu algoritma dalam menyelesaikan suatu masalah. Hal-hal yang dapat mempengaruhi daripada waktu tempuh adalah:

• Banyaknya langkah: Makin banyak langkah atau instruksi yang digunakan dalam menyelesaikan masalah, maka makin lama waktu tempuh yang dibutuhkan dalam proses tersebut
• Besar dan jenis input data: Besar dan jenis input data pada suatu algoritma akan sangat berpengaruh pada proses perhitugan yang terjadi. Jika jenis data adalah tingkat ketelitian tunggal(Single precision), maka waktu tempuh akan menjadi relatif lebih cepat dibandingkan dengan tingkat ketelitian ganda(double precesion)
• Jenis operasi: Waktu tempuh juga dipengaruhi oleh jenis operasi yang digunakan. Jenis operasi tersebut meliputi operasi matematika, nalar atau logika, atau yang lainnya. Sebagai contoh, operasi perkalian atau pembagian akan memakan waktu lebih lama dibandingkan operasi penjumlahan atau pengurangan.
• Komputer dan kompilator: hal terakhir yang mempengaruhi waktu tempuh suatu proses algoritma adalah komputer dan kompilatornya, walaupun sebenarnya faktor ini diluar tahap rancangan atau tahap pembuatan algoritma yang efisien. Algoritma dibuat untuk mencapai waktu tempuh yang seefektif dan seefisien mungkin, tetapi kesemuanya itu akan sangat bergantung pada kemampuan komputer yang tentunya harus sesuai dengan jumlah program atau langkah yang diperlukan oleh algoritma, begitu juga dengan kompilator tersebut, misalnya PC XT 8086 akan kalah cepat dibandingkan 8088 atau dengan AT 80286 atau 80386 atau 80486 dan seterusnya

- Jumlah Memori Yang digunakan: banyaknya langkah yang digunakan dan jenis variabel data yang dipakai dalam suatu algoritma akan sangat mempengaruhi penggunaan memori. Dalm hal ini, diharapkan dapat memperkirakan seberapa banyak kebutuhan memori yang diperlukan selama proses berlangsung hingga proses selesai dikerjakan. Dengan demikian, dapat disiapkan storage yang memadai agar proses suatu algoritma berjalan tanpa ada hambatan atau kekurangan memori.

Selain analisis kita juga dapat melihat sifat umum dari sebuah algoritma, pada umumnya algoritma  memiliki sifat-sifat sebagai berikut :

- Langkah atau instruksi harus jelas: artinya bahwa penulisa setiap langkah yang terdapat didalam sebuah algoritma harus memiliki arti yang khusus atau spesifik sehingga dapat dibedakan antara penulisan langkah untuk komputer (program/pemrograman) dengan penulisan langkah bagi manusia (pesudocode). Manusia akan lebih mudah memahami algoritma yang terdiri atas simbol-simbol (Contoh: pembuatan algoritma dengan diagram alur/flowchart) sedangkan komputer hanya membutuhkan sebuah penulisan algoritma dengan kode-kode yang dituangkan dalam bahasa yang dimengerti oleh komputer itu sendiri (bahasa pemrograman).

-  Banyaknya langkah instruksi harus berhingga: pelaksanaan sebuah algoritma yang terprogram haruslah dapat diakhiri atau diselesaikan melalui sejumlah langkah operasional yang berhingga. Jika tidak demikian, kita tidak akan dapat mengharapkan bahwa pelaksaan algoritma tersebut dapat menghasilkan suatu solusi yang baik.

- Proses harus jelas dan mempunyai batasan: rangkaian suatu proses yang berisi langkah-langkah instruksi dari suatu algoritma yang akan dilaksanakn harus ditetapkan dengna jelas, baik dan pasti sebab sebuah algoritma harus memiliki instruksi dasar tertentu dimana setiap instruksi harus memiliki unsur pelaksana yang berfungsi sebagai pemroses data yang akan dimasukkan dalam sebuah komputer. Dengan demikian, sebuah algoritma harus ditulis dengan jelas tentang batasa-batasan proses yang akan dilaksanakan oleh komputer.

- Efektifitas: instruksi yang diberikan pada komputer agar hanya menjalankan atau melaksanakan proses yang mampu dilaksanakannya. Yang dimaksud mampu adalah bahwa suatu algoritma atau instruksi-instruksi dalam sebuah program hanya akan dapat dilaksanakan jika informasi yang diberikan oleh instruksi-instruksi tersebut lengkap, benar dan jelas.

- Adanya batasan ruang lingkup, sebuah algoritma yang baik adalah hanya ditujukan bagi suatu masalah tertentu saja. Susunana input harus ditentukan lebih dulu sebab susunan tersebut menentukan sifat umum dari algoritma yang bersangkutan.

Dari beberapa pengantar algoritma yang telah dibahas di atas, sekarang kita kembali lagi ke mekanisme lompatan dalam sebuah game. Jika mendengar lompatan, apa yang ada dibenak anda sekalian? daya dorong? gravitasi? persamaan yang rumit? atau yang lain? Sekilas akan sangat rumit jika kita harus mengimplementasikan algoritmanya, dan memang benar akan rumit. Lalu bagaimana para game developer diluar sana mengimplementasikan hal serumit ini? Tentu ada cara lain yang sedikit lebih mudah daripada kita harus menggunakan persamaan tersebut.

Dalam game 2D, koordinat yang digunakan adalah koordinat x dan koordinat y (x,y). Kita sepakati saja bahwa koordinat (0,0) terletak di sudut kiri atas untuk memudahkan pemahaman. Untuk x, ke arah kanan x bernilai positif, dan ke arah kiri x bernilai negatif. Sedangkan untuk y, ke arah bawah y bernilai positif, sedangkan ke arah atas y bernilai negatif. Hal ini memang sedikit asing bagi yang belum pernah belajar pemrograman grafis. Lain halnya dengan game 3D maka titik koordinat yang di pakai adalah (x,y,z).

Setelah disepakati tentang masalah koordinat, selanjutnya kita masuk ke logika berpikir. Karakter kita berdiri pada suatu platform di titik (x,y). Kemudian yang disebut melompat adalah menggeser koordinat y ke arah atas (-y) sampai pada titik tertentu, kemudian setelah mencapai titik tersebut kemudian kita menggeser koordinat y tadi ke arah bawah (y) dan mengembalikan karakter ke titik semula.

Dapat dilihat dari penggalan kode program di bawah ini ;

Jika kode tersebut dijalankan, maka program ini hanya akan menampilkan nilai dari variabel posisi, karena kode tersebut merupakan konsep awal dalam game agar bisa melompat.

Beberapa contoh impelementasi algoritma dalam pembuatan game :

1.    Pembuatan Kecerdasan Buatan untuk Permainan Catur Jawa
Dengan Menggunakan Algoritma MiniMax

Algoritma minimax diaplikasikan pada permainan yang melibatkan dua orang. Permainan-permainan tersebut dapat dideskripsikan dengan sejumlah aturan dan premis. Dengan itu, kita dapat mengetahui, pada titik tertentu permainan, langkah-langkah yang mungkin berikutnya. Permainan tersebut berbagi karakteristik yang sama, yakni “permainan dengan penuh informasi”. Setiap pemain mengetahui semua langkah-langkah yang mungkin dari pemain lawannya.

Sebelum menjelaskan algoritma minimax, pengenalan mengenai pohon pencarian dibutuhkan. Pohon pencarian adalah cara untuk merepresentasikan pencarian. Kotak disebut sebagai simpul dan simpul-simpul tersebut merepresentasikan titik keputusan pada pencarian. Simpul dihubungkan dengan cabang. Pencarian dimulai pada simpul akar, ditunjukkan pada bagian atas pada gambar 1. Pada setiap simpul keputusan, simpul berikutnya yang mungkin untuk pencarian dibangkitkan, sampai tidak ada lagi keputusan yang mungkin. Simpul yang merepresentasikan akhir pencarian disebut sebagai simpul daun.

Pada algoritma ini ada dua pemain yang terlibat, kita asumsikan MAX dan MIN. Pohon pencarian dibangkitkan, depth-first, dimulai dari posisi permainan saat ini sampai pada akhir posisi permainan. Lalu, kondisi permainan final dievaluasi sebagai sudut pandang MAX, seperti tergambar pada gambar 1. Setelah itu, simpul-simpul di atas simpul daun diisi secara bottom up dengan nilai pada simpul anak-anaknya. Simpul yang dimiliki pemain MAX menerima nilai maksimum dari simpul anak-anaknya dan pemain MIN memperoleh nilai minimum dari nilai-nilai yang dimiliki simpul anakanaknya. Berikut gambaran algoritmanya:

  

‘Nilai’ pada algoritma di atas merepresentasikan seberapa baik permainan bergerak. Pemain MAX akan mencoba memilih gerakan dengan nilai maksimum pada akhirnya sedangkan pemain MIN akan memilih gerakan yang lebih baik baginya, karena itu MIN akan meminimkan keluaran dari MAX (minimizing MAX’s outcome). 

Pada pengimplementasian algoritma minimax pada permainan catur jawa ini menggunakan bahasa pemrograman Java. Pada pengimplementasiannya, catur jawa diberi batasan-batasan khusus. Batasan-batasan ini antara lain : lebar papan hanya dibatasi 7 kotak saja dan tinggi papan hanya 6 kotak saja. Permainan juga selalu dimulai dari bawah untuk menyederhanakan persoalan. Pemain akan memulai permainan dengan cara memilih salah satu kolom dari tujuh buah kolom yang tersedia. Pemain akan mendapatkan simbol ‘X’. Komputer pun akan segera melakukan gerakan untuk melawan pemain sesuai dengan algoritma minimax yang diimplementasikan. Demikian selanjutnya sampai salah satu pemain (kita atau komputer) memperoleh 4 simbol yang sama (‘X’ untuk kita dan ‘O’ untuk komputer) pada baris yang sama, pada kolom yang sama, atau pada diagonal yang sama. Method-method yang dipakai dalam mengimpelementasikan algoritma ini pada intinya hanya tiga buah, yakni konstruktor catur jawa, fungsi minimax sebagai algoritma inti pada kecerdasan buatan pada permainan catur jawa ini, dan method FourInARow yang berfungsi untuk menghitung apakah suatu pemain telah memperoleh simbol empat buah yang berurutan. Untuk memperjelas, mari kita lihat algoritmanya. Berikut adalah variabel global yang digunakan:

Berikut adalah Konstruktor caturJawa:

Dan untuk kode program algoritma minimaxnya sebagai berikut :

  

Langkah terakhir adalah untuk kode program fungsi FourInARow:

Pada konstruktor caturJawa, yang dilakukan adalah menunggu masukan user kemudian mengantisipasi masukan user itu dengan memanggil method miniMax dan kemudian membandingkan hasil keluaran method miniMax tersebut. Karena method ini digunakan untuk memaksimalkan langkah komputer, maka yang dicari adalah nilai yang maksimum dari semua keluaran miniMax ini.

Fungsi heuristik pada prosedur miniMax adalah dengan mencari langkah paling cepat menghasilkan akhir permainan. Akhir permainan ini ditentukan dengan menggunakan method FourInARow (jika sudah ada 4 simbol berurutan maka permainan berakhir). Jika sedang berada pada langkah komputer (MAX), algoritma akan mencari nilai minimum yang dihasilkan oleh pemain dan jika berada pada langkah pemain algoritma akan mencari nilai maksimum yang dihasilkan oleh komputer. Fungsi miniMax ini merupakan fungsi rekursif dengan maksimum kedalaman 6. Kedalaman ini dimaksudkan untuk mengoptimasi algoritma miniMax yang dibuat.


 2. Penerapan Algoritma A* (A Star) Pada Game Edukasi The Maze Island Berbasis Android

Game edukasi memiliki kelebihan dibandingkan dengan metode pembelajaran konvensional karena cara pembelajarannya disajikan dengan visualisasi bergerak yang menarik. Namun, game edukasi jarang menerapkan algoritma dalam penyelesaiannya. Alasan inilah yang membuat penulis ingin mencoba untuk menerapkan algoritma A Star (A *) pada game edukasi The Maze Island berbasis Android. Game edukasi ini termasuk dalam game labirin dimana pemain diharuskan untuk mencari jalan keluar dengan rute terpendek. Algoritma A* memberikan solusi terbaik untuk memecahkan masalah ini. Tujuan utama dari permainan ini adalah untuk menerapkan algoritma A* dalam memberikan hasil pencarian untuk menemukan pintu keluar dengan rute terpendek. Game ini juga diharapkan dapat menjadi salah satu media pembelajaran untuk menambah wawasan ilmu pengetahuan dan matematika. Dan game ini dikembangkan pada platform android yang memungkinkan pengguna untuk bermain di mana pun dengan menggunakan smartphone.

Prinsip dari algoritma ini adalah melakukan traversal satu per satu pada tiap simpul untuk memperoleh lintasan terpendek pada suatu graf. Algoritma A* akan menghitung jarak salah satu lintasan, lalu menyimpannya dan kemudian menghitung jarak lintasan lainnya. Ketika seluruh lintasan telah selesai dihitung, algoritma A* akan memilih lintasan yang paling pendek. Algoritma A* menyelesaikan masalah yang menggunakan graf untuk perluasan ruang statusnya.

Heuristik adalah nilai yang memberi nilai pada tiap simpul yang memandu A* mendapatkan solusi yang diinginkan. Dengan heuristik, maka A* pasti akan mendapatkan solusi (jika memang ada solusinya). Dengan kata lain, heuristik adalah fungsi optimasi yang menjadikan algoritma A* lebih baik dari pada algoritma lainnya. Fungsi heuristik yang terdapat pada algortima A* untuk menghitung taksiran nilai dai suatu simpul yang telah dilalui adalah :

F(n) = G(n) + H(n) . . . . . . . . . . . . . . . 1

Dimana :

F(n) = ongkos untuk simpul n

G(n) = ongkos mencapai simpul n dari akar

    H(n) = ongkos mencapai simpul tujuan dari n

 

Pseudocode untuk algoritma A * adalah :

function A*(start,goal)

closedset := the empty set // The set of nodes already evaluated.

openset := {start} // The set of tentative nodes to be evaluated, initially containing the start node

came_from := the empty map // The map of navigated nodes.

g_score[start] := 0 // Cost from start along best known path.

h_score[start] := heuristic_cost_estimate(start, goal)

f_score[start] := g_score[start] + h_score[start] // Estimated total cost from start to goal through y.

while openset is not empty

x := the node in openset having the lowest f_score[] value

if x = goal

return reconstruct_path(came_from, came_from[goal])

remove x from openset

add x to closedset

foreach y in neighbor_nodes(x)

if y in closedset

continue
tentative_g_score := g_score[x] + dist_between(x,y)

if y not in openset

add y to openset

tentative_is_better := true

else if tentative_g_score < g_score[y]

tentative_is_better := true

else

tentative_is_better := false

if tentative_is_better = true

came_from[y] := x

g_score[y] := tentative_g_score

h_score[y] := heuristic_cost_estimate(y, goal)

f_score[y] := g_score[y] + h_score[y]

return failure

function reconstruct_path(came_from, current_node)

if came_from[current_node] is set

p := reconstruct_path(came_from, came_from[current_node])

return (p + current_node)

            else
             return current_node

3. Penggunaan Algoritma Breadth First Search Dalam Konsep Artificial Intellegencia

Artificial Intelligencia merupakan suatu konsep pemetaan suatu bahasa pemrograman yang dapat membuat suatu kesimpulan berdasarkan pemetaan yang telah dilakukan didalam pemrograman. Dalam hal ini, banyak metode yang dapat digunakan dan dimanfaatkan untuk menyelesaikan permasalahan tersebut. Contohnya seperti masalah Teko Air. Permasalahan ini dapat diselesaikan dengan menerapkan konsep AI yaitu dengan bantuan pohon pelacakan dan menerapkan metode pencarian melebar pertama (breadth-first search / BFS). Pencarian solusi dimulai dari kondisi dimana kedua teko kosong (node akar dari pohon pelacakan). Perangkat lunak ini memiliki kemampuan untuk mencari solusi permasalahan teko air dengan 2 buah kendi dan menampilkan semua langkah – langkah yang dapat diambil untuk mendapatkan solusi atau volume air yang diinginkan.Perangkat lunak dapat mencari solusi terpendek dari permasalahan teko air karena menggunakan metode pencarian melebar pertama (breadthfirst search). Pencarian tidak selalu menghasilkan solusi walaupun setelah semua node pada pohon pelacakan diperiksa dan dikembangkan. 

Pada metode pencarian ini, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya. Demikian seterusnya hingga ditemukannya solusi. Gambaran pencarian BFS dapat dilihat pada gambar di bawah ini :

  

Pada gambar di atas terlihat bahwa pencarian dimulai dari keadaan awal (node A). Dari node A dikembangkan dua node baru yang menjadi anaknya, yaitu node B dan node C. Penelusuran dilanjutkan ke node B (menghasilkan node D, E, F) dan node C (menghasilkan node G, H, I). Demikian seterusnya hingga ditemukan solusi. 

Contoh mudahnya dapat di lihat pada game Masalah Teko Air (Water Jug Problem) dapat diilustrasikan seperti berikut, terdapat 2 buah teko air X dan Y, masing – masing berukuran A dan B liter. Salah satu teko tersebut hendak diisi air sebanyak N liter, dengan menggunakan asumsi bahwa sumber air tidak terbatas. Aksi – aksi yang dapat dilakukan, antara lain mengisi teko dengan air hingga penuh, mengosongkan teko dan menuangkan isi teko ke teko yang lain.

  4. Penerapan Algoritma Backracking pada permainan math maze

Permainan Math Maze merupakan game sederhana yang bertujuan menentukan jalur yang tepat untuk mencapai tujuan yang telah di tetapkan. Permainan ini hampir sama dengan permainan labirin (Maze) biasa. Perbedaannya adalah pada Math Maze kita harus menemukan jalur pada labirin denngan angka-angka pada bagian sisi kiri dan sisi atas sebagai indikasi beberapa banyak kotak yang di lewati untuk tiap baris atau tiap kolom dan tidak menggunakan tembok penghalang seperti pada kolom biasa. Pada penelitian ini dilakukan proses untuk membuat papan permainan math maze yang biasa dimainkan oleh pemakai dengan menggunakan algoritma backtracking. Proses pembuatan papan permainan math maze terdiri dari beberapa langkah, yaitu proses pembangkitan sebuah maze, pencarian solusi dari maze yang sudah di bangkitkan, dan membuat papan permainan Math Maze baru dengan memanfaatkan maze yang sudah di ketahui solusinya, permainan math maze dengan menggunakan algoritma backtracking dapat menghasilkan 1 solusi untuk setiap problem yang dibangkitkan dan maze yang dihasilkan dengan algoritma backtracking akan menghasilkan maze yang tidak memiliki loop dan ruang terbuang.

Langkah-langkah pencarian solusi dengan Backtracking adalah sebagai berikut :

1.      Solusi di cari dengan membentuk lintasan dari akar ke daun. Simpul yang sudah dilahirkan dinamakan simpul hidup dan simpul hidup 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 terkahir ada di simpul mati, maka pencarian dilakukan dengan membangkitkan simpul anak yang lainnya dan jika tidak ada simpul child maka di lakukan backtracking ke simpul parent

4.      Pencarian di hentikan jika telah menemukan solusi atau tidak ada simpul hidup yang dapat di diperlukan

Langkah algoritma Backtracking :

a.       Masukan ukuran grid (i x j)

b.      Selama total sel pada grid < sel yang telah dikunjungi lakukan langkah d, e, f

c.       Pilih secara acak sel tetangga (kanan, kiri, atas, bawah)

d.      Cek apakah sel sudah pernah dikunjungi , jika ya kembali ke langkah c, jika tidak lakukan langkah e.

e.       Hapus wall atau pembatas pada sel

f.       Tentukan pintu masuk (start) dan pintu keluar (goal) 

g.    Selesai

Flowchart algoritma backtracking pada pembangkitan maze game math maze

5. Game Chicken Roll dengan Menggunakan Metode Forward Chaining

Metode forward chaining pada umumnya digunakan untuk sistem pendukung keputusan dan sistem pakar. Penelitian ini menggunakan algoritma forward chaining, khususnya untuk proses review dan untuk menentukan apakah seorang pemain game layak melanjutkan ke level berikutnya. Algoritma forward chaining adalah algoritma yang berbasiskan pada fakta-fakta atau premise yang ada sehingga menghasilkan sebuah kesimpulan atau konsekuen. Hasil pengujian menunjukkan bahwa nilai validitas mencapai 100%. Hasil didapat dari komparasi data antara rules dan hasil pengujian yang didapat saat bermain game. 

Kerangka konsep game chicken roll :

Keterangan:

• Garis Putus-Putus : Penelitian yang dikerjakan.
• Baris 1 : Game mempunyai 9 jenis (Edutainment, FPS, RTS, Fighting, Adventure, RPG, Construction and Management Simulation, Vehicle Simulation, Leveling).
• Baris 2 : Penelitian ini berfokus pada pengembangan game untuk desktop.
• Baris 3 : Penelitian ini lebih mengutamakan pengembangan pada bidang AI (Artificial Intelligence) khususnya dengan menggunakan forward chaining. 
•  Baris 4 : Konsep AI dimanfaatkan untuk leveling process. Memanfaatkan forward chaining untuk menentukan seorang user dapat melanjutkan ke level berikutnya atau tidak. 
• Baris 5 : Variabel yang dijadikan acuan sebagai bahan input untuk konsep AI dengan forward chaining.

         Konsep kerja algoritma forward chaining dalam game chicken roll:

6. Rancangan Permainan Othello Berbasis Android Menggunakan Algoritma Depth-First Search

Penerapan kecerdasan buatan menggunakan algoritma DFS (Depth First Search) dengan algoritma Negamax yang dioptimasi dengan Alpha Beta Pruning ini dapat mengurangi ruang pencarian sehingga proses penelusuran dan evaluasi dapat dilakukan lebih cepat. Aplikasi ini dikembangkan dengan menggunakan bahasa pemrograman Java berbasis Eclipse IDE. Hasil yang diperoleh adalah sebuah aplikasi permainan Othello yang dapat diterapkan pada mobile phone berbasis Android.

Dalam permainan Othello pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan.

Untuk mengatasi banyaknya node yang ditelusuri oleh Negamax, perlu dibuat optimasi yang dapat mereduksi kemungkinan yang akan dianalisis. Alpha Beta Pruning merupakan optimasi dari algoritma Negamax yang mengurangi jumlah node yang dievaluasi oleh pohon pencarian. Dengan algoritma ini hasil optimasi dari algoritma Negamax tidak akan berubah. 

Alpha Beta Pruning menelusuri pohon permainan dengan meletakkan 2 nilai pada setiap node, yaitu alpha (α) dan beta (β). Nilai α ditetapkan sama dengan -∞ sedangkan nilai β sama dengan +∞. Jika α < β, maka kesempatan untuk mencari langkah terbaik masih ada dan pencarian akan tetap dilanjutkan. Node akan melakukan maksimalisasi dan memperbaiki nilai α dari nilai anakanaknya, kemudian nilai yang telah memperbaiki nilai α tersebut akan dibandingkan dengan nilai β sementara. Jika α > β, maka evaluasi dihentikan. Beriku adalah salah satu gambar kondisi pada game Othello  dan gambar saat game Othello berlangsung:

     7. PENYELESAIAN PUZZLE SUDOKU MENGGUNAKAN ALGORITMA GENETIKA

Sudoku adalah sebuah permainan puzzle pada papan berukuran 9x9 yang menggunakan angka 1 sampai 9. Target dari permainan ini adalah melengkapi papan dengan mengisi kotak-kotak yang kosong dengan sebuah angka sehingga dalam satu baris, kolom, dan region (kotak 3x3) tidak ada angka yang berulang. Karena itu, dalam sebuah puzzle Sudoku, hanya terdapat 1 solusi yang valid. Penyelesaian permainan ini secara manual akan memakan waktu beberapa lama, sehingga mulai dilakukan penelitian untuk menyelesaikan puzzle Sudoku menggunakan beberapa algoritma yang dalam prosesnya diperlukan banyak iterasi. Dengan Algoritma Genetika, suatu solusi dari puzzle Sudoku direpresentasikan dalam sebuah kromosom atau individu dengan struktur tertentu. Kromosom yang terkumpul dalam populasi mengalami berbagai proses, mulai dari seleksi, pindah silang, mutasi, hingga pergantian generasi. Kromosom yang lolos diharapkan adalah yang terbaik, yang merupakan solusi puzzle. 

Kromosom adalah representasi solusi dari suatu masalah pada Algoritma Genetika. Pada Sudoku, kromosom adalah representasi suatu solusi dari puzzle yang berisi angka-angka yang akan diisikan pada kotak-kotak yang kosong sehingga panjang kromosom adalah sama dengan jumlah kotak yang kosong pada puzzle. Nilai untuk masing-masing gen pada kromosom diambil secara acak dari kandidat-kandidat pada setiap cell. Kandidat nilai untuk setiap kromosom adalah angka 1 hingga 9. Pada pemrograman, kromosom direpresentasikan dengan array of integer (int[]). Contoh bentuk kromosom :

Puzzle yang digunakan untuk percobaan adalah puzzle dengan tingkat kesulitan Very Hard (55 kotak kosong). Puzzle ini disimpan ke dalam file dan di-load pada setiap percobaan. Percobaan yang dilakukan adalah dengan mengubah-ubah konfigurasi Algoritma Genetika, yaitu jumlah individu, generasi maksimum, crossover rate, jumlah titik crossover, dan mutation rate. Untuk setiap konfigurasi, dilakukan 10 percobaan dan diambil nilai rata-ratanya. Hal ini dilakukan karena Algoritma Genetika memberikan hasil yang berbeda-beda untuk konfigurasi yang sama. 

Percobaan jumlah kromosom dilakukan dengan menambah jumlah kromosom untuk dilihat pengaruh pada performa Algoritma Genetika. Hasil percobaan digambarkan pada grafik berikut.

Hasil pembahasan :

1. Dalam proses evolusi menuju nilai fitness yang sempurna, seringkali terjadi stagnasi yang membuang waktu dan menyebabkan waktu evolusi menjadi panjang. Pengulangan proses evolusi dari awal (inisialisasi populasi) dapat memperbaiki waktu evolusi.
2. Inisialisasi populasi di awal proses evolusi sangat menentukan konvergensi proses evolusi.
3. Penambahan jumlah kromosom dalam populasi dapat meningkatkan performa algoritma namun tidak signifikan karena membutuhkan komputasi yang lebih tinggi. 
4. Peningkatan crossover rate dan mutation rate dapat meningkatkan konvergensi.

      *. Pembuatan Game NIM menggunakan Alpha-beta Pruning

Game NIM adalah sebuah game sederhana yang diawali dengan serangkaian batang dengan jumlah tertentu. Kemudian pemain harus memecah serangkaian batang tersebut menjadi dua kumpulan dimana jumlah batang di setiap kumpulan tidak boleh sama dan tidak boleh kosong. Contoh ilustrasi Game NIM dapat dilihat pada gambar di bawah ini :

Telah kita ketahui sebelumnya bahwa algoritma alpha-beta pruning merupakan improvisasi dari algoritma Minimax. Algoritma ini untuk meningkatkan efisiensi fungsi Minimax dalam hal pencarian. Mengurangi jumlah pencarian pada node-node Game NIM yang diexpand. Kemudian fungsi evaluasi ditambahkan sepasang nilai Alpha dan Beta . Dalam Game NIM, metode Alpha-beta Pruning akan diterapkan pohon n-ary yang telah terbentuk. Pada setiap cabang akan memiliki nilai yang bertujuan memaksimalkan pencarian dan meminimalkan waktu pencarian pada pohon n-ary. Sedangkan fungsi evaluasi sendiri adalah inialisasi pertama dalam metode ini sebelum melakukan permainan. Berikut nilai fungsi evaluasi dari metode Alpha-beta Pruning.

• 0 MIN (player) menang
• 1 MAX (komputer) menang

Berikut merupakan aturan untuk Alphabeta Pruning:

1. Pemangkasan Alpha : Pencarian dapat dihentikan untuk simpul turunan selanjutnya jika setiap simpul MIN memiliki nilai beta kurang dari atau sama dengan nilai alpha apapun dari simpul MAX sebelumnya pada induk yang sama. 
2. Pemangkasan Beta : Pencarian dapat dihentikan untuk simpul turunan selanjutnya jika setip simpul MAX memiliki nilai alpha lebih dari atau sama dengan nilai beta apapun dari simpul MIN sebelumnya pada induk yang sama.

 Dengan mengetahui pohon n-ary dari jumlah batang Game NIM, proses selanjutnya adalah dengan melakukan pencarian pada setiap childs sehingga menghasilkan nilai fungsi evaluasi 0 atau 1. Misal pada kondisi batang NIM sebanyak 7, kondisi batang ini memiliki memiliki turunan antara lain 6-1, 5-2, 4-2. Ini sesuai dengan ilustrasi dari Game NIM itu sendiri seperti pada gambar :

Untuk memulai permainan NIM, sistem perlu mengetahui 3 attribut yakni jumlah batang, pemain yang bermain dulu, dan metode yang akan digunakan.

9.  Penerapan Algoritma Fuzzy Mamdani untuk Mengatur Game Scoring pada Game Helitap

Gambar diatas adalah tampilan alur dari poses tampilnya Health pada game yang dibuat. Parameter awal yang akan dipakai sebagai acuan dalam menentukan munculnya Health berupa score pemain. Hal ini dapat menetukan kapan Health dan kecepatan obstacle akan tampil dan berubah. Sehingga nilai score menjadi penentu utama dari tingkat kesulitan permainan semakin tinggi score maka kecepatan dan frekuensi Health yang keluar juga akan berpengaruh. Health disini berfungsi sebagai “nyawa ” dari helicopter yang dimainkan. Dihasilkan 6 rule dari proses yang ada.

1. IF Score is Rendah Then Health is Sering

2. IF Score is Sedang Then Health is Sedang

3. IF Score is Tinggi Then Health is Jarang

4. IF Score is Rendah Then Kecepatan is Biasa

5. IF Score is Sedang Then Kecepatan is Sedang 

6. IF Score is Tinggi Then Kecepatan is Cepat

Berikut merupakan pengolahan yang dilakukan pada matlab R2012 untuk menentukan aturan yang akan dipakai. Inputan score yang akan di gunakan. 

Output untuk menampilkan frekuensi kemunculan dari Health

Hasil dari proses pembuatan dan pemberian metode fuzzy pada permainan menghasilkan hasil yang baik. Health dapat tampil sesuai dengan rule yang telah dibuat sebelumnya. Begitu juga kecepatan yang dapat secara otomatis berubah sesuai dengan kondisi dari pemain. Berikut merupakan screenshot dari permainan yang dihasilkan.

                                                                              a

                                                                                 b

Pada saat pemain memainkan permainan obstacle akan secara otomatis berjalan menuju pemain. Jika pemain dapat melewati obstacle tersebut, maka score akan bertambah sebanyak 1 poin. Item Health yang secara acak akan tampil saat permainan berjalan, akan membantu pemain agar jika pemain menabrak obstacle permainan tidak langsung berakhir. Pemain harus bisa mengambil Item tersebut agar “nyawa” pemain dapat bertambah sebanyak yang didapatkan oleh pemain. Semakin tinggi nilai dari pemain, maka frekuensi kemunculan Item tersebut akan berkurang dan kecepata dari obstacle pun akan bertambah cepat.

                                                                               c

                                                                            d

Semoga bermanfaat