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.