Dalam studi master saya semester ini, salah satu mata kuliah yang saya ambil adalah Application of Computational Intelligence in Engineering. Mata kuliah yang menarik dan diajar oleh instruktur yang berpengalaman di bidang kecerdasan komputasional, yaitu: Prof. I-Tung Yang. Salah satu syarat kelulusan mata kuliah ini adalah membuat sebuah final project yang mengimplementasikan salah satu dari beberapa teknik metaheuristik yang diajarkan seperti: Genetic Algorithm, Particle Swarm Organization, Multi-objective Optimization, Simulated Annealing, Tabu Search, Ant Colony Optimization, Differential Evolution, Artificial Immune System, atau algoritma lainnya pada kasus nyata di bidang engineering. Setelah melalui proses studi literatur dari paper berikut:

Verma, Millan A., and Peter W. McOwan. 2005. An Adaptive Methodology for Synthesizing Mobile Phone Games using Genetic Algorithms. The 2005 IEEE Congress on Evolutionary Computation.

Akhirnya saya dan rekan saya memutuskan untuk mengambil topik serupa dengan judul, Dynamic Difficulty Balancing in Mobile Phone Games using Genetic Algorithm.

Latar Belakang

Berdasarkan data dari Microsoft Tag (2011), telepon seluler telah berkembang dengan sangat cepat dari tahun ke tahun hingga mencapai 4 milyar. Ternyata 61% orang tersebut menggunakan telepon selulernya untuk bermain game. Saat ini, game ponsel tidak secara akurat mengatasi bervariasinya kemampuan pemain. Jika pemain tidak terampil maka pemain dapat menjadi stres, sebaliknya apabila pemain sangat terampil tentunya pemain dapat cepat bosan. Oleh karena itu, pendekatan yang lebih adaptif untuk mengubah tingkat kesulitan game secara dinamis amatlah dibutuhkan.

Definisi Masalah

Studi kasus pada proyek ini adalah sebuah game action yang simpel dengan cara bermain yang mudah, yaitu: cukup dengan menggerakkan ponsel dengan Windows Phone OS ke kiri dan kanan karena memanfaatkan sensor accelerometer. Objektif dari game ini adalah untuk memperoleh skor tertinggi dengan mengambil balon dan koin serta menghindari bintang-bintang yang bertebaran. Selain itu, pemain juga akan diganggu oleh angin yang akan otomatis menggerakkan karakter secara horizontal berdasarkan arah dan kecepatan angin tersebut.

In Game Screenshot - Up!

Algoritma

Elemen-elemen terkait dalam game ini yang dapat mempengaruhi tingkat kesulitan permainan dijabarkan dalam diagram berikut:

Genetic Algorithm Elements - Up!

Elemen-elemen tersebut di-encode menjadi kromosom-kromosom dalam genetic algorithm yang salah satu contoh solusinya seperti gambar berikut:

Encoded Solution - Up!

Karena proyek ini menggunakan genetic algorithm, tentu saja beberapa tuning parameters wajib ditentukan terlebih dahulu sebelum program dijalankan. Berdasarkan hasil trial and error sebelumnya, maka tuning parameters yang digunakan adalah:

  • Population: 4
  • Max. Generation: 5
  • Mutation Rate: 0.06
  • Crossover Rate: 0.8

Implementasi

Untuk mengimplementasikan genetic algorithm dalam permainan, langkah-langkah yang dilakukan adalah:

  1. Membuat opsi bagi pemain untuk bermain dengantingkat kesulitan berdasarkan chromosome generation yang acak.
  2. Implementasi 1

  3. Membuat tingkat kesulitan permainan yang adaptif selama permainan berdasarkan respon dari pemain. Permainan tersebut akan memperbarui Lookup Table yang berisi fitness value sesuai dengan nilai pemain.
  4. Implementasi 2

Agar memperoleh bayangan mengenai jalannya algoritma ini, flowchart pengimplementasian algoritma tersebut dapat dilihat pada gambar berikut:

Flowchart - Up!

Salah satu contoh hasil dari Lookup Table yang akan digunakan untuk mengatur tingkat kesulitan permainan setelah game ini dijalankan dan memperoleh respon dair pemain adalah sebagai berikut:

Lookup Table Result - Up!

Evaluasi

Pengaturan elemen-elemen permainan pada kromosom genetic algorithm tidak berdampak secara langsung terhadap fitness value. Oleh karena itu, proses evaluasi algoritma ini memerlukan respon dari pemain tentang seberapa baik sistem ini bekerja.

Pertanyaan pertama dari proses evaluasi ini adalah apakah permainan yang dimainkan sesuai dengan permintaan pemain untuk tingkat kesulitan yang lebih tinggi dan rendah. Berikut adalah pie chart hasil evaluasi terhadap pemain:

image

Pertanyaan kedua adalah game manakah yang lebih disukai antara Random Game dan GA Game. Berikut adalah pie chart hasil evaluasi terhadap pemain:

image

Kesimpulan

Dari proyek ini, beberapa kesimpulan yang dapat ditarik antara lain:

  • Genetic algorithm dapat diimplementasikan pada sebuah game yang bertujuan untuk mengatur tingkat kesulitan permainan.
  • Beberapa peningkatan yang dapat dilakukan antara lain: menghasilkan jumlah populasi dan generasi yang lebih banyak, menambahkan lebih banyak obstacle,  dan mengintegrasikan proses chromosome generation dan chromosome update secara bersamaan.

Semoga tulisan yang “sedikit” akademis ini dapat bermanfaat!

Leave a Reply