Game AI yang Menggunakan Algoritma Greedy

AI (Artificial Intelligence) atau kecerdasan buatan merupakan salah satu cabang ilmu komputer yang mempelajari bagaimana cara membuat mesin cerdas, yaitu mesin yang mempunyai kemampuan untuk belajar dan beradaptasi terhadap sesuatu. Atau dapat juga diartikan membuat suatu mesin dapat melakukan pekerjaan seperti yang dilakukan oleh manusia, ataupun memasukan pikiran manusia ke dalam sebuah mesin agar mesin tersebut dapat berpikir layaknya manusia. Dalam permainan Ludo ini juga menerapkan konsep AI, yaitu dengan menggunakan komputer sebagai lawan dari pemain dalam memainkan permainan ini.

          Dalam penerapannya, permainan Ludo menggunakan algoritma Greedy. Algoritma Greedy merupakan satu algoritma yang paling sering digunakan dalam mencari solusi dari persoalan optimasi. Atau persoalan dimana kita mencari suatu solusi yang dapat menyelesaikan masalah secara optimal. Algoritma greedy akan membentuk solusi langkah per langkah. Pada setiap langkah penyelesaian masalah terdapat banyak pilihan langkah yang dapat diambil. Algoritma ini berusaha mengambil keputusan terbaik yang dapat diambil pada saat ini.

          Pada permainan Ludo terdapat kelas pion yang memiliki atribut berupa posisi pion. Kelas pion akan dimiliki oleh kelas pemain yang memiliki array yang berisi empat buah pion. Kelas pemain juga memiliki prosedur melangkah yang akan mengubah posisi pion pada kelas papan. Juga terdapat kelas dadu yang berisi angka yang dapat diambil oleh kelas lain.

          Dalam penerapan algoritma greedy pada permainan Ludo terdapat beberapa algoritma greedy yang dapat digunakan, diantaranya :

1.     Greedy By No One Left Behind

Algoritma ini akan berusaha untuk menggerakkan semua pion menuju titik tujuan bersama – sama. Semua langkah yang dapat diambil digunakan untuk menggerakan semua pion agar semakin dekat dengan tujuan dengan memilih pion dengan prioritas tertinggi yaitu pion yang berada paling belakang.

2.    Greedy By Hitter

Algoritma ini berusaha untuk menggerakan pion agar dapat memukul pion lawan. Pemilihan pion yang digerakkan berdasarkan prioritas posisi pion. Pion yang berada lebih dekat dengan pion lawan, maka pion tersebut yang akan digerakkan.

3.    Greedy By Quick Move

Algoritma ini berusaha untuk menggerakkan pion secepat mungkin menuju tujuan. Pergerakkan pion didasarkan pada pion dengan prioritas tertinggi, yaitu pion yang berada paling dekat dengan tujuan.

Referensi :

http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2011-2012/Makalah2011/MakalahIF3051-2011-040.pdf

http://edisugiarto.blogspot.com/2010/07/konsep-artificial-intelligence.html

PERT Diagram

Teknik penjadwalan proyek dalam system informasi terdapat 2 metode yaitu, Bagan Gantt Chart dan Metode PERT. Bagan Gantt Chart merupakan suatu bagan yang menampilkan setiap tugas atau kegiatan dalam bentuk kotak – kotak. Untuk lama waktu dari setiap kegiatan akan bergantung pada panjang dari kotak –kotak yang mewakili setiap kegiatan.

Metode PERT atau sering disebut sebagai diagram jaringan, merupakan sebuah program yang menggambarkan suatu kegiatan menggunakan jaring simpul dan arah panah yang kemudian dievaluasi untuk kemudian menentukan kegiatan terpenting dari keseluruhan sebuah proyek.

Dalam Metode PERT atau diagram jaringan setiap kejadian akan diwakilkan oleh sebuah simpul. Sedangkan untuk sebuah kejadian akan diwakilkan oleh anak panah.

Jalur Kritis dalam Diagram PERT merupakan jalur yang menunjukkan kegiatan dari awal diagram jaringan sampai dengan kegiatan akhir dari diagram jaringan, yang waktu pengerjaannya tidak dapat ditunda. Karena jika pengerjaanya ditunda maka akan mempengaruhi waktu pengerjaan proyek.

Untuk menentukan jalur kritis dari sebuah proyek dapat menggunakan Algoritma Jalur Kritis. Dengan melakukan pengitungan waktu mulai tercepat ( Earliest Start Time / ES) untuk masing – masing kegiatan dan waktu selesai terlama ( Latest Finish Time / LF). Perhitungan Earliest Start (ES) dan Latest Finish (LF) menggunakan 2 cara, yaitu :

      

Forward Pass, untuk menghitung waktu mulai tercepat (ES).

Untuk menghitung ES digunakan rumus [Waktu Mulai Tercepat (ES) + Waktu Kegiatan)

Bila terdapat 2 kegiatan yang dilakukan atau lebih dalam 1 simpul, maka pilih kegiatan dengan waktu terbesar diantara kegiatan – kegiatan tersebut.

      Backward Pass, untuk menghitung waktu selesai terlama (LF).

Untuk menghitung LF digunakan rumus [Waktu Selesai terlama (LF) - Waktu Kegiatan)

Bila terdapat 2 kegiatan yang dilakukan atau lebih dalam 1 simpul, maka pilih kegiatan dengan waktu terkecil diantara kegiatan – kegiatan tersebut.

Menghitung ES :

·         Kejadian 1 : Karena kegiatan awal/waktu mulai tercepat 0

ES1 = 0

·         Kejadian 2 : ES2 = ES1 + waktu kejadian A

ES₂ = 0 + 10 = 10

·         Kejadian 3: ES3 = ES1 + waktu kejadian B

ES₃ = 0 + 2 = 8

·         Kejadian 4: ES4 = ES1 + waktu kegiatan C

ES₄ = 0 + 12 = 12

ES4 = ES3 + Kegiatan D1

ES₄ = 8 + 0 = 8

ES4 = 12 (nilai terbesar)

·         Dan seterusnya menggunaka rumus yang sama sampai dengan kegiatan 8.

Menghitung LF

·         Kegiatan 8 : waktu selesai terlamanya sama dengan waktu mulai tercepat.

LF₈ = ES8 = 50

·         Kejadian 7 = LF₇ = LF₈ – Waktu kejadian J

LF₇ = 50 – 15 = 35

·         Kejadian 6 = LF₆ = LF₈ – waktu kegiatan I

LF₆ = 50 – 20 = 30

·         Kejadian 5 = LF₅ = LF₈ – waktu kejadian H

LF₅ = 50 – 8 = 42

LF₅ = LF₇ – waktu kejadian D2

LF₅ = 35 – 0 = 35 (paling minimal)

·         Dan seterusnya menggunaka rumus yang sama sampai dengan kegiatan 1.

Jadi jalur kritis terjadi jika memiliki ES dan LF yang sama.

Slack menunjukan waktu dari sebuah kegiatan yang dapat ditunda waktu pengerjaanyan karena tidak akan mempengaruhi waktu penyelesaian dari seluruh proyek. Dalam perhitungan besar Slack memerlukan Waktu Mulai Terlama (Latest Start / LS) dan Waktu Selesai Tercepat (Earliest Finist / EF).

Referensi : Analisis dan Desain Sistem Informasi : Pendekatan Terstruktur (JOGIYANTO HM).

ERD

ERD ( Entity Relational Diagram) merupakan diagram yang menggambarkan salah satu metode pemodelan basis data yang digunakan untuk menghasilkan skema konseptual untuk jenis/model data semantik sistem. Dimana sistem  seringkali memiliki basis data relasional, dan ketentuannya bersifat top-down. Diagram untuk menggambarkan model Entitiy-Relationship ini disebut Entitiy-Relationship diagram, ER diagram, atau ERD.

Notasi-notasi simbolik yang digunakan dalam Entity Relationship Diagram adalah sebagai berikut :

• Entitas, Adalah segala sesuatu yang dapat digambarkan oleh data. Entitas juga dapat diartikan sebagai individu yang mewakili sesuatu yang nyata dan dapat dibedakan dari sesuatu yang lain 

• Atribut, Atribut merupakan pendeskripsian karakteristik dari entitas. Atribut digambarkan dalam bentuk lingkaran atau elips. Atribut yang menjadi kunci entitas atau key diberi garis bawah.

• Relasi atau Hubungan, Relasi menunjukkan adanya hubungan diantara sejumlah entitas yang berasal dari himpunan entitas yang berbeda.
• Penghubung antara himpunan relasi dengan himpunan entitas dan himpunan entitas dengan atribut dinyatakan dalam bentuk garis.

Dibawah ini merupakan contoh ERD dari sebuah Apartemen.

Pada diagram ERD di atas dapat disimpulkan bahwa kardinalitas dari diagram ERD tersebut adalah M : 1. Atau Many to One, yang berarti banyak penghuni dapat memiliki 1 apartemen. Jadi setiap penghuni dapat memiliki 1 apartemen, tetapi untuk kamar pada apartemen dapat dimiliki banyak penghuni ataupun 1 penghuni dan banyak kamar dapat dimiliki oleh 1 penghuni ataupun banyak penghuni.

Sedangkan untuk derajat dari diagram ERD diatas berderajat 4 atau N-ary. Karena memiliki 4 buah entitas dari keseluruhan diagram ERD tersebut. 

Pada diagram ERD di atas setiap entitas memiliki atribut key sebagai atribut yang akan digunakan untuk menentukan suatu entity secara unik. Perusahaan di atas menggunakan Oracle sebagai aplikasi database yang digunakan. ERD di atas menjelaskan database dari sebuah apartmene yang menjelaskan hubungan antara Pegawai dengan Apartemen. Apartemen dengan penghuni. Dan Penghubi dengan Penyewa.