Permainan Minesweeper dengan Algoritma BFS dan Optimasi Algoritma Greedy

Permainan Minesweeper dengan Algoritma BFS

dan Optimasi Algoritma Greedy

 

Nama : Ady Mulyono

NIM : 0110214018

Tugas : Kecerdasan Buatan

Minesweeper merupakan salah satu permainan yang sudah terinstall pada sistem operasi Windows. Permasalah pada permainan ini adalah menemukan seluruh ranjau bom pada kumpulan petak yang ada tanpa meledakannya. Cara menemukan ranjau adalah menggunakan petunjuk yang ada pada petak yang terbuka (non ranjau), petak tersebut berisikan angka yang menyatakan banyaknya ranjau yang ada disekitar petak yang berisikan angka tersebut.

1.    Pendahuluan

Minesweeper adalah sebuah permainan single-player. Tujuan dari permainan ini adalah untuk menghapus papan persegi panjang yang tersembunyi, "ranjau adalah jebakan bom yang dipasang" tanpa meledakkan salah satu dari ranjau, dengan bantuan dari petunjuk tentang jumlah tambang tetangga di masing-masing bidang. Permainan berasal dari tahun 1960-an, dan telah ditulis untuk banyak platform komputasi yang digunakan saat ini. Ini memiliki banyak variasi dan cabang. Game Komputer ini menggunakan strategi dan kesempatan.

Breadth-first search (BFS) adalah sebuah algoritma untuk melintasi atau mencari pohon atau grafik struktur data. Dimulai pada akar pohon (atau beberapa simpul sewenang-wenang dari grafik, kadang-kadang disebut sebagai 'kunci pencarian) dan mengeksplorasi tetangga node pertama, sebelum pindah ke tetangga tingkat berikutnya.

BFS diciptakan pada akhir 1950-an oleh E. F. Moore, yang digunakan untuk menemukan jalur terpendek dari labirin,  dan ditemukan secara independen oleh C. Y. Lee sebagai algoritma kawat routing.

2.    Algoritma Greedy dan Implementasinya Pada Program Java

Algoritma greedy merupakan salah satu dari sekian banyak algoritma yang sering di pakai dalam implementasi sebuah system atau program yang menyangkut mengenai pencarian “optimasi”.

Di dalam mencari sebuah solusi (optimasi) algoritma greedy hanya memakai 2 buah macam persoalan Optimasi,yaitu:

1. Maksimasi (maxizimation)

2. Minimasi (minimization)

   Solusi optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin.

Elemen persoalan optimasi:

1. Kendala (constraints)

2. Fungsi objektif (fungsi optiamsi)

   Solusi yang memenuhi semua kendala disebut solusi layak (feasible solution). Solusi layak yang mengoptimumkan fungsi optimasi disebut solusi optimum.

   Algoritma greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi.

Greedy = rakus, tamak, loba, ….

Prinsip greedy adalah: “take what you can get now!”.

Contoh masalah sehari-hari yang menggunakan prinsip greedy:

Permainan Minesweeper

Memilih beberapa jenis investasi (penanaman modal)

Mencari jalur tersingkat dari Bandung ke Surabaya

Memilih jurusan di Perguruan Tinggi

   Pendekatan yang digunakan di dalam algoritma greedy adalah membuat pilihan yang “tampaknya” memberikan perolehan terbaik yaitu dengan membuat pilihan optimum lokal (local optimum) pada setiap langkah dengan harapan bahwa sisanya  mengarah ke solusi optimum global (global optimm).

   Algoritma greedy adalah algoritma yang memecahkan masalah langkah per langkah pada setiap langkah:

Mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”)

Berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.

   Pada setiap langkah diperoleh optimum lokal. Bila algoritma berakhir, kita berharap optimum lokal menjadi optimum global.

3.    Skema Umum Algoritma Greedy

Algoritma greedy disusun oleh elemen-elemen berikut:

1. Himpunan kandidat berisi elemen-elemen pembentuk solusi.

2. Himpunan solusi berisi kandidat-kandidat yang terpilih sebagai solusi  persoalan.

3. Fungsi seleksi (selection function) memilih kandidat yang paling memungkinkan mencapai solusi optimal. Kandidat yang sudah dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya.

4. Fungsi kelayakan (feasible) memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak, yakni kandidat tersebut bersama-sama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala (constraints) yang ada. Kandidat yang layak dimasukkan ke dalam himpunan solusi, sedangkan kandidat yang tidak layak dibuang dan tidak pernah dipertimbangkan lagi.

5. Fungsi obyektif yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi (misalnya panjang lintasan, keuntungan, dan lain-lain).

4.    Flow Chart

5.    Implementasi

6.    Screan Shout

7.    Kesimpulan