Game Minesweeper Menggunakan Strategi Greedy

dan BFS (Best First Search)

Nama Kelompok :

Ilyas Syukur S (10111344)

Rahman Wijaya (1011155)

Steven (10111)

Game Minesweeper

Minesweeper adalah permainan single player paling sukses yang pernah dibuat. Minesweeper diluncurkan pada tahun 1990 sebagai bagian dari windows entertainment pack sebelum di promosikan untuk menjadi fitur standar pada windows 3.1 dan seterusnya. Minesweeper adalah permainan asli Microsoft, dibuat oleh Curt Johnson dan Robert Donner. Asal usul minesweeper berasal dari permainan pada computer mainframe pada tahun 60an – 70an.

Greedy dan BFS (Best First Search)

Greedy

Algoritma greedy membentuk solusi langkah per langkah (step by step). Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh karena itu, pada setiap langkah harus dibuat keputusan terbaik dalam menentukan pilihan.

Greedy dan BFS (Best First Search)

BFS (Best First Search)

Pada teori graf, BFS adalah algoritma pencarian pada graf yang dimulai dari simpul akar dan menelusuri seluruh simpul tetangganya. Kemudian untuk setiap simpul terdekat, algoritma ini menelusuri simpul tetangganya yang belum ditelusuri, dan seterusnya hingga menemukan solusi.

Penyelesaian Game Minesweeper

Pada gambar diatas didalam kotak biru Nilai tengah pada ordo 3x3 itu menentukan berapa banyak ranjau yang adad di daerah ukuran ordo 3x3 . Dalam pencarian ranjau ini algoritma yang digunakan adalah BFS dan di optimasikan menggunakan Greedy.

Penjelasan Procedure Solver

Kompleksitas Procedure Solver

Kesimpulan

Algoritma Greedy dan Algoritma BFS dapat digunakan sebagai bagian dari pemecahan masalah game Minesweeper yaitu untuk menelusuri petak-petak yang ada di papan minesweeper.