I. PENDAHULUAN
Tebak kata
merupakan sebuah permainan sederhana dengan kesulitan yang rumit. Inti dari
permainan tebak kata ini hanya menebak kata apa yang dimaksudkan oleh computer dengan
cara mengisi kata-kata yang kosong dengan pilihan satu dari beberapa huruf yang
ada.
Dalam
implementasinya, algoritma string digunakan sebagai pencocokkan sidik jari,
juga untuk semua hal yang berhubungan dengan recognition atau
pencocokkan.
Dalam
implementasi sebenarnya, pemecahan masalah tebak kata tidak hanya menggunakan
algoritma pencocokkan string, tapi beragam algoritma juga digunakan, seperti
algoritma bruteforce yang nanti akan digunakan untuk menghitung jumlah kata. Pencocokkan
string merupakan sebuah masalah yang sering diketemukan dalam kehidupan
sehari-hari. Beberapa aplikasi yang menggunakan algoritma ini ialah text
editor, web search engine, ataupun image analysis.
String merupakan
sekumpulan karakter yang tergabung menjadi satu. Substring S[i..j] dari S
merupakan bagian dari string antara indeks i sampai j. Sebuah prefiks S
merupakan substring dari indeks 0 sampai i. Sedangkan sebuah sufiks S adalah
substring antara indeks i sampai indeks terakhir pada string.
II. ALGORITMA
BRUTE FORCE
Algoritma brute
force adalah sebuah algoritma dengan pendekatan yang lempang untuk memecahkan
suatu masalah. Biasanya algoritma ini didasarkan pada pernyataan masalah, dan
definisi konsep yang dilibatkan. Algoritma brute force memecahkan masalah
dengan sangat sederhana, langsung, dan jelas.
Dalam makalah
ini, algoritma brute force yang akan digunakan ialah dengan algoritma pencarian
beruntun (Sequential Search). Sebagai contoh permasalahan ialah : Diberikan
sebuah list yang berisi n buah bilangan bulat (a1, a2, ….,an). Carilah nilai x
di dalam list tersebut. Jika x ditemukan, maka keluarannya adalah indeks elemen
senarai, jika x tidak ditemukan maka keluarannya adalah 0.
Dengan algoritma
brute force (sequential search), setiap elemen list dibandingan dengan x.
Pencarian selesai jika ditemukan atau elemen list sudah habis diperiksa. Kompleksitas
algoritma brute force untuk sequential search
ialah O(n).
III. PERMAINAN
TEBAK KATA
A.
Deskripsi Permasalahan
Tebak kata pada
dasarnya merupakan sebuah permainan kertas dan pensil sederhana untuk dua atau
lebih pemain. Seorang memikirkan huruf untuk ditebak dan yang lain mencoba
menebak kata apa yang dipikirkan si pembuat soal. Namun dewasa ini, permainan tebak
kata berkembang menjadi permainan yang menggunakan desktop sebagai media utama
permainan. Dengan computer sebagai pembuat soal yang di-generate secara random
dan pemain yang berusaha menebak kata yang di-generate.
Kata yang akan
di tebak diberi clue agar pemain bisa menebak hal apa saja yang berhubungan
dengan clue yang diberikan. Kata tempat untuk kata yang akan dimasukkan di representasikan
dengan titik. Jika penebak menebak sebuah huruf yang berada dalam kata yang
dimaksud, maka huruf tersebut dituliskan menggantikan titik dalam kata. Jika
ternyata huruf yang ditebak tidak terdapat pada kata yang dimaksud, maka akan
dituliskan disebelah kanan layar, jika huruf yang kita tebak sudah pernah di
tebak maka akan muncul pemberitahuan. Pemain diberikan sepuluh kesempatan bagi
penebak untuk salah, dan jika kita berhasil menebak maka akan diberikan score
mulai dari 10 dan bertambah 10, jika gagal maka scorenya 0.
B.
Strategi
Dalam Bahasa
Indonesia, setiap huruf pasti mempunyai huruf vokal, a, i, u, e, dan o.
Sehingga menebak salah satu dari huruf tersebut memperbesar kemungkinan kita
untuk menebak jawaban dari kata yang dimaksud. Ketika kira-kira sudah tertebak
satu atau dua huruf vokal, kita dapat melanjutkan dengan menebak huruf konsonan
yang banyak digunakan seperti n,m,s,t,r,p, Kemudian kita dapat mengikuti pola
dari kata untuk menebak apa kata yang dimaksud.
C. Contoh
Permainan
Berikut ini ialah contoh permainan
tebak kata dimulai dari awal hingga selesai.
Awalnya diberikan clue, Sebutkan kata apa saja yang
berhubungan dengan computer !
kemudian
perintah tekan ESC jika kita
ingin berhenti bermain.
1. Langkah
pertama kita tebak huruf vocal
Titik- titik tadi sekarang
tergantikan oleh huruf vocal yang kita masukkan tadi , itu berarti huruf yang
kita msukkan itu benar.
2.
Langkah kedua kita tebak huruf
konsonan
Disebelah kanan layar muncul pesan Bukan : n
Artinya huruf yang dita masukkan salah, maka tidak akan
dicetak pada titik-titik yang ada disebelah kiri.
Sehingga kesempatan kita menjawab salah berkurang menjadi 9.
3.
Setelah itu kita menebak lagi
konsonan yang banyak di pakai yaitu p dan dilanjutkan dengan r
huruf r dicetak dua kali karena ada kesamaan
huruf, meskipun kita hanya mengetikannya sekali saja.
Di sebelah kana nada peringatan
! artinya kita mengulang huruf
yang sama dengan yang sebelumnya pernah di jawab.
4.
Lalu kita lanjutkan lagi menebak
huruf konsonan yang banyak dipakai, yaitu m.
5.
Sekarang kita menebak huruf apa yang
akan kita masukan untuk melengkapi clue yang diminta yaitu kata apa yang
berhubungan dengan computer, maka kita jawab g.
Setelah berhasil menebak maka kita akan diberikan score, yaitu
untuk pertama 10.
6.
Selanjutnya jika kita ingin bermain
lagi kita lanjutkan menebak kata.
Disini saya tidak bisa menebak kata
yang diminta, maka score saya 0 dan saya main lagi.
Score saya menjadi 10 dan terus
bertambah menjadi 20 setelah berhasil menebak yang selanjutnya.
IV. IMPLEMENTASI ALGORITMA
Pada
permulaan, kita membutuhkan sebuah kamus yang berisi dengan kata-kata. Kita
juga membutuhkan sebuah array untuk menampung kata-kata.
Sebelum
kita masuk pada penjelasan algoritma yang akan dipakai dalam pemecahan masalah tebak
kata, kita membutuhkan sebuah prosedur untuk mencari nilai rata-rata kemunculan
karakter pada setiap string. Prosedur ini dapat di-generate dengan menggunakan
algoritma brute force sequential search.
Prosedur ini akan mengembalikan karakter
dengan kemunculan rata-rata tertinggi untuk setiap stringnya. Pemecahan masalah
dimulai dengan membandingkan jumlah panjang string yang akan ditebak dengan
jumlah string dalam kamus.
Pertama
kita menebak kata pertama dengan huruf yang didapatkan. Hal ini bertujuan
memperbesar kemungkinan penebakkan kata pertama yang mendekati solusi akhir.
Ada dua kondisi yang dapat terjadi :
1.
Kata
yang dimaksud tidak terdapat pada solusi akhir,
2.
Kata
yang dimaksud ada pada solusi akhir.
Jika
kita mendapatkan hasil seperti pada nomor 1, maka kita lanjutkan dengan
pemilihan kata dengan urutan kemunculan rata-rata tertinggi nomor dua, dan bila
gagal lagi, dilakukan dengan kata ketiga, keempat, dan seterusnya.
Jika
kita mendapatkan hasil seperti pada nomor 2, fungsi rekursif kembali dilanjutkan dengan melakukan
pencocokkan string dari pola solusi akhir yang telah didapat dengan sisa string
pada array. Hasil yang didapatkan dimasukkan kedalam array. Fungsi rekursif ini
dilakukan hingga jawaban didapat, atau kesempatan menebak sudah habis.
Algoritma
pencocokkan string yang digunakan berdasarkan penggunaan algoritma brute force
dirasa cukup dalam pemecahan masalah ini.
V. KESIMPULAN
Kesimpulan
dari makalah ini ialah dengan algoritma pencocokkan string, permainan hangman
dapat dengan mudah diselesaikan, walaupun kemungkinan gagal menebak juga ada
dikarenakan terlalu banyak kemungkinan yang harus dieliminasi. Algoritma Brute
Force sederhana dirasa cukup dalam pengimplementasian program hangman solver
ini.
Daftar pustaka
240-301
Comp. Eng. Lab III (Software), Pattern Matching
