PERANCANGAN DAN PEMBUATAN APLIKASI WORD GAME SCRAMBLE PADA BOARD DUA DIMENSI

PERANCANGAN DAN PEMBUATAN APLIKASI WORD GAME SCRAMBLE PADA BOARD DUA DIMENSI Oleh : Noswa Sabdifha (1203 109 009) Dosen Pembimbing Tugas Akhir : Prof. DR. Mohammad Isa Irawan, MT

ABSTRAK Banyak metode pembelajaran yang digunakan guru agar murid dapat menangkap apa yang sedang diajarkan, salah satunya adalah dengan permainan. Metode pembelajaran ini mampu menyampaikan tujuan pokok belajar dengan cara yang menyenangkan, sehingga para siswa diharapkan dapat lebih bersemangat dan tertarik terhadap topik pembelajaran. Metode pembelajaran sambil bermain juga dapat diterapkan pada salah satu pelajaran penting di sekolah, yakni pelajaran Bahasa Inggris. Permainan berbahasa Inggris ini dikenal dengan Word Games. Dari sekian banyak macam jenis permainan Word games yang ada, Scramble termasuk salah satu jenis permainan Word games yang populer. Artificial Intelligence (AI) atau kecerdasan buatan merupakan cabang dari ilmu komputer yang berhubungan dengan pengautomatisasi tingkah laku cerdas. Pencarian atau pelacakan merupakan salah satu teknik untuk menyelesaikan permasalahan AI. Terdapat beberapa aplikasi yang menggunakan teknik pencarian, yaitu : Papan game dan puzzle. Pada Tugas Akhir ini, terdapat berbagai macam permasalahan seperti pengacakan huruf-huruf untuk generate board yang dimaksudkan adalah bagaimana pola pengacakannya dapat mempermudah pengguna mencari lebih banyak kata dalam board 4x4, kemudian pencarian kata dengan menerapkan algoritma DepthFirst Search pada board 4x4 oleh komputer berdasarkan pencocokan kata pada kamus sehingga diperoleh seluruh kata yang bisa didapat. Kata Kunci:

Word Games, Scramble Games, Depth-First Search. kemudian pemain mencari kosa kata yang bisa disusun dari huruf –huruf yang diacak. Dalam I. Pendahuluan Belajar adalah salah satu kegiatan utama Tugas Akhir ini jenis scramble yang diterapkan murid di sekolah. Bahasa Inggris merupakan salah adalah memasukkan huruf secara acak pada kotak satu mata pelajaran di kelas. Banyak metode 4x4, kemudian pemain mencari kata yang bisa pembelajaran yang digunakan guru agar murid didapat dengan pola yang bisa disusun secara dapat menangkap apa yang sedang diajarkan. horisontal, vertikal maupun diagonal. Aplikasi ini Namun tidak sedikit murid yang merasa bosan memungkinkan pemain mendapatkan kosakata baru sehingga dapat menghambat proses belajar yang belum pernah didengar atau dilihat setelah mengajar. Permainan adalah salah satu solusi hasil yang diperoleh dibandingkan dengan hasil alternatif untuk pembelajaran murid. Faktanya pencarian oleh komputer. permainan dapat membantu dan menyemangati Pada game ini terdapat berbagai macam banyak murid untuk dapat terus menjaga permasalahan seperti pengacakan huruf-huruf untuk ketertarikan mereka. Terdapat persepsi dasar bahwa generate board yang dimaksudkan adalah pembelajaran seharusnya dengan suasana serius dan bagaimana pola pengacakannya dapat khusuk sehingga jika ada yang bersenang – senang mempermudah pengguna mencari lebih banyak atau tertawa maka tidak dapat dikatakan sebagai kata dalam board 4x4, kemudian pencarian kata sebuah pembelajaran. Hal ini adalah pada board 4x4 oleh komputer berdasarkan kesalahpahaman, karena sangat memungkinkan pencocokan kata pada kamus sehingga diperoleh untuk mempelajari sebuah kosakata bahasa inggris jumlah kata yang bisa didapat, serta tampilan dan bermain disaat yang bersamaan, salah satu cara program yang akan digunakan pemain untuk terbaik melakukannya adalah dengan permainan pencarian kata, juga terdapat sistem penilaian untuk [1]. Banyak macam permainan yang bertujuan setiap kata yang ditemukan oleh komputer menambah wawasan English Vocabulary. Salah pengguna. Sehingga, pada tugas akhir ini akan satunya adalah Word game. dirancang dan diimplementasikan sebuah Dari sekian banyak macam jenis permainan permainan scramble pada board 4x4. Word games yang ada, Scramble termasuk salah satu jenis permainan Word games yang populer. II. TINJAUAN PUSTAKA Dapat disimpulkan bahwa jenis permainan Pencarian boleh jadi merupakan hasil dari Scramble merupakan pengacakan huruf-huruf, suatu solusi ruang keadaan yang mungkin telah

1

terkunjungi semua, tetapi tanpa penyelesaian. Pencarian yang mendalam (Exchausting Search Strategy) mungkin dilakukan dengan menggunakan strategi Depth First Search (Iterative Deepening). Pencarian ini merupakan pencarian buta (blind search).

6. Open = [12, 6, 3, 4]; closed = [19, 11, 5, 2, 1]. 7. Open = [20, 6, 3, 4]; closed = [12, 19, 11, 5, 2, 1].

8. Open = [6, 3, 4]; closed = [20, 12, 19, 11, 5, 2, 1].

9. Open = [13, 3, 4] (karena 12 telah di-closed); closed = [6, 20, 12, 19, 11, 5, 2, 1].

2.1. Algoritma Depth First Search Algoritma Depth First Search (DFS) adalah algoritma traversal di dalam graf dengan menelusuri verteks-verteks yang bertetangga terlebih dahulu. Khusus untuk persoalan ini, graf yang akan ditelusuri berbentuk pohon [4]. Cara tradisional memandang DFS sebagai suatu proses yang secara lepas dapat digambarkan sebagai berikut. Mula-mula, semua verteks dari graph dinyatakan sebagai "unvisited', maka kita memilih satu dan mengeksplorasi sebuah edge yang mengantarkan kepada verteks baru. Sekarang kita mulai pada verteks tersebut dan mengeksplorasi sebuah edge yang mengantarkan kepada verteks baru lagi. Kita meneruskan proses ini dengan cara tersebut sampai kita mencapai sebuah verteks yang tidak punya edges yang mengantar kita ke verteksverteks lain yang belum dikunjungi. Pada saat ini kita kembali dan meneruskan dari verteks terakhir yang mengantarkan kepada verteks yang belum dikunjungi. Akhirnya kita akan mencapai sebuah titik dimana setiap verteks yang 'reachable' dari verteks awal sudah dikunjungi semua. Jika masih ada verteks yang tersisa, kita pilih satu dan memulai pencarian lagi, sampai akhimya setiap verteks sudah dikunjungi sekali, dan setiap edge sudah diuji. Contoh penelusuran algoritma DFS diberikan pada gambar di bawah ini.

10. Open = [3, 4]; closed = [13, 6, 20, 12, 19, 11, 5, 2, 1]. 11. Open = [7, 8, 4]; closed = [3, 13, 6, 20, 12, 19, 11, 5, 2, 1]. 12. Dan seterusnya sampai state 21 diperoleh atau open = []. Penentuan teknik pencarian yang sesuai atau yang tepat untuksebuah kasus khusus penganalisaan suatu ruang permasalahan, menjadi sangat penting dan biasanya dengan melakukan konsultasi dengan para pakar di bidangnya untuk mendapatkan dan mengetahui tingkah laku ruang permasalahan tersebut [7]. 2.2. Word Games Scramble Scramble merupakan pengembangan dari permainan scrabble yang sangat inspiratif, pola permainan ini yang menjadi inspirasi dalam mengerjakan tugas akhir ini. Permainan ini dimulai dengan mengacak huruf alpabet dengan kadar frekuensi setiap huruf berbeda untuk diisi pada board berukuran 4x4, masing-masing grid diisi dengan huruf berbeda atau sama pada setiap isinya. Pemain harus mencari kata yang bisa dibentuk dari huruf yang sudah terisi pada board 4x4, pemain akan dibatasi oleh waktu tiga menit sejak dimulai dan pemain harus mencari kata sebanyak yang bisa didapat. Aturan permainannya, yang harus dicapai pemain adalah mencari kata yang terdapat pada board 4x4 seperti pada gambar 2.2 dengan syarat: Sebuah kata yang didapat terdiri dari 2 huruf atau lebih. Jalan itu ditelusuri oleh huruf-huruf di kata harus terhubung secara horisontal, vertikal, atau diagonal. Pemain tidak dapat melompati grid untuk mendapatkan huruf berikutnya. Setiap grid hanya bisa digunakan satu kali dalam satu kata. Sebagai contoh, pola pada gambar 2.2 mengandung kata P E A C E yang bisa ditunjukkan pada:

Gambar 2.1 Contoh penelusuran DFS Langkah-langkah penelusuran untuk gambar 2.1 tersebut adalah:

1. 2. 3. 4. 5.

Open = [1]; closed = []. Open = [2, 3, 4]; closed = [1]. Open = [5, 6, 3, 4]; closed = [2, 1]. Open = [11, 12, 6, 3, 4]; closed = [5, 2, 1]. Open = [19, 12, 6, 3, 4]; closed = [11, 5, 2, 1].

2

III. METODE PENELITIAN Pembuatan tugas akhir ini dilakukan dengan mengikuti metodologi sebagai berikut : 3.1. Analisa Sistem Tahapan ini dilakukan dengan observasi permasalahan, identifikasi permasalahan, mempelajari hal-hal yang berkaitan dengan kecerdasan buatan. Pembelajaran ini didapat dari buku-buku literatur, paper maupun beberapa artikel di internet. Pada bagian ini akan menganalisa bagaimana sistem perangkat lunak aplikasi scramble menggunakan algoritma depth first search akan berinteraksi dengan user mulai dari proses randomization huruf sampai kemudian proses pencarian kata – kata pada grid yang telah terisi serta proses penghitungan nilai maksimalnya.

Gambar 2.2 Terdapat kata PEACE dalam board. Jalan yang ditunjukkan, sebagaimana yang dimaksud pada gambar 2.2, tidak terdapat kata PLACE, karena sesuai peraturan tidak boleh melompat grid yang tidak terhubung dari huruf P ke L lalu kembali ke huruf A. Sama juga dengan kata POPE, pemain tidak boleh menggunakan huruf yang telah digunakan lebih dari satu kali.

3.2. Desain algoritma Pada tahap ini dilakukan desain algoritma DFS terhadap analisa sistem yang telah ditentukan 3.3. Desain interface Pada tahap ini, didesain seluruh tampilan interface seperti apa yang diinginkan untuk mengakomodasi seluruh objek dan atribut yang telah ditentukan. Selain itu, juga didesain alur-alur yang menghubungkan interface berdasarkan hubungan antar objek dan atribut yang telah ditentukan. Untuk mengetahui gambaran keseluruhan dari proses kerja perangkat lunak aplikasi scramble pada board 4x4 yang akan dibuat diperlukan langkah awal yaitu analisa alur proses kerja pada perangkat lunak yang akan dibuat. Diagram perancangan sistem ini secara global diilustrasikan pada gambar berikut ini :

2.3. Randomization (Alphabet Generator) Proses ini berfungsi sebagai pengacak huruf alfabet yang akan keluar di setiap node. Huruf-huruf pada setiap node diacak sedemikian rupa sehingga huruf-huruf umum muncul lebih sering dan lebih mudah untuk mendapatkan campuran yang baik antara vokal dan konsonan. Dari penelitian yang di lakukan oleh Andrea Krause [3] berdasarkan Hidden Markov Models (HMM) menunjukkan bahwa huruf ”E” adalah huruf yang paling sering keluar dalam 10.000 kata dari Reuters data set. Maka dalam tahap Randomization ini huruf ”E” mendapat porsi lebih besar saat proses pengacakan. Berikut ini sekilas contoh pseudocode tentang alphabet generator untuk pengacakan huruf yang akan digunakan : freq['a'] = 0.2 freq['b'] = 0.01 ... freq['z'] = 0.02 jumlah seluruh frekuensi diatas adalah 1, maka dapat didefinisikan sebuah array dengan interval seperti ini: intr['a'] = [0; 0.2) intr['b'] = [0.2; 0.01) ... intr['z'] = [0.98; 1) kemudian saat proses generalisasi angka acak n pada interval [0; 1) program hanya mencari dalam interval array dan mendapatkan huruf yang terdapat pada interval tersebut. for(huruf = 'a' .. 'z') if n in int[huruf] then return huruf;

3

akan di masukkan dalam daftar kata dan score yang didapat oleh pemain. 4.2. Penentuan Nilai (Scoring) Pada tahap ini kata yang ditemukan oleh pemain mempunyai nilai yang berbeda sesuai dengan jumlah huruf pada kata yang sudah masuk dalam daftar kata yang ditemukan pemain. Dengan nilai – nilainya sebagai berikut: Panjang Kata Nilai 2 1 3 1 4 2 5 3 6 5 7 7 ≥8 11 Tabel 4.1 : Daftar nilai berdasarkan jumlah huruf 4.3. Randomization Pengisian huruf secara acak pada board 4x4 di setiap node-nya akan dilakukan secara acak. Hurufhuruf pada setiap node diacak sedemikian rupa sehingga huruf-huruf umum muncul lebih sering dan lebih mudah untuk mendapatkan campuran yang baik antara vokal dan konsonan. Untuk memenuhi kondisi tersebut diperlukan frekuensi yang berbeda – beda tiap hurufnya, dapat ditunjukkan pada tabel berikut ini: No. Urut Huruf Frekuensi Inisialisasi 1 E 11.1607% 11 2 A 8.4966% 8 3 R 7.5809% 7 4 I 7.5448% 7 5 O 7.1635% 7 6 T 6.9509% 7 7 N 6.6544% 7 8 S 5.7351% 6 9 L 5.4893% 5 10 C 4.5388% 5 11 U 3.6308% 4 12 D 3.3844% 3 13 P 3.1671% 3 14 M 3.0129% 3 15 H 3.0034% 3 16 G 2.4705% 2 17 B 2.0720% 2 18 F 1.8121% 2 19 Y 1.7779% 2 20 W 1.2899% 1 21 K 1.1016% 1 22 V 1.0074% 1 23 X 0.2902% 1 24 Z 0.2722% 1 25 J 0.1965% 1 26 Qu 0.1962% 1 Tabel 4.2 Nilai Frekuensi Huruf yang Akan

Gambar 3.1 : Alur Proses Kerja (Flowchart) Perangkat Lunak IV. PERANCANGAN PERANGKAT LUNAK Dari keadaan sistem yang telah dipaparkan diatas, maka dapat dibuat perancangan perangkat lunak yang sesuai dengan kebutuhan, yaitu permainan word game scramble. 4.1. Aturan Permainan Pada permainan ini, pemain harus mencari kata yang akan di acak pada proses randomization kemudian komputer akan mencocokkan pada kamus apakah kata yang ditemukan oleh pemain valid atau terdapat pada kamus tersebut. Ada pula aturan pada pencarian kata oleh pemain sebagai berikut: Sebuah kata yang didapat terdiri dari 2 huruf atau lebih. Jalan itu ditelusuri oleh huruf-huruf di kata harus terhubung secara horisontal, vertikal, atau diagonal. Pemain tidak dapat melompati grid untuk mendapatkan huruf berikutnya. Setiap grid hanya bisa digunakan satu kali dalam satu kata. Kata yang sudah ditemukan tidak dapat diulangi (walaupun terdapat kata yang sama namun dengan path yang berbeda). Jika salah satu dari kondisi diatas tidak terpenuhi, kata yang sudah didapat atau dalam kasus ini di-accept akan ditolak. Jika terpenuhi

Diacak

4

Berikut ini akan dijelaskan masing-masing tools yang digunakan pada aplikasi word game scramble. Sesuai dengan gambar tampilan utama yang ditampilkan pada gambar 4.1. Tools yang digunakan meliputi Menu Bar, text area, serta button, dan kesemuanya ditampilkan pada Tabel 4.3:

4.4. Implementasi Algoritma Depth First Search Dalam penerapannya pada aplikasi Scramble, prosedur Depth First Search dapat diimplementasikan dengan [7] : Prosedur depth first search Begin Open := [start] Closed := [] While open = [] do Begin Pindahkan verteks paling kiri dari open, namakan x Jika x adalah tujuan maka return SUCCESS; Else Begin Hasilkan cabang dari x; Letakkan x pada closed; Abaikan cabang dari x jika sudah terletak pada open or closed; Menempatkan cabang yang tersisa pada ujung kiri dari open; End; End return FAIL End.

Nama Tools

4.5. Implementasi Antar Muka Tampilan dari perangkat lunak ini terdiri dari Tampilan Utama yang ditampilkan pada Gambar 4.1, Contoh tampilan utama yang sudah terisi huruf secara acak pada gambar 4.2, serta contoh tampilan utama yang sudah selesai pada gambar 4.3. Tampilan pada gambar dibawah ini adalah contoh tampilan utama saat pertama kali di eksekusi. Pemain harus menekan tombol klik pada start button untuk memulai permainan, untuk lebih jelasnya simak tabel 4.1 dibawah ini.

Gambar 4.1 : Tampilan Utama Pada Perangkat Lunak

5

Jenis

File

Menu Bar

Help

Menu Bar

Board

Grid

Mulai

Button

Berhenti

Button

Keterangan Membuka sub menu yang ada didalam game yaitu: Mulai (start), berhenti (stop) dan keluar (exit). Berisi tentang informasi tentang petunjuk penggunaan aplikasi word game scramble. Juga berisi sub menu tentang informasi sang penulis aplikasi. Digunakan untuk menampilkan huruf – huruf yang teracak sebagai papan permainan dalam aplikasi word game scramble. Digunakan untuk memulai permainan. Digunakan untuk menghentikan permainan dan akan menunjukkan kata yang sudah ditemukan komputer.

Check

Button

Reset

Button

TextInput

Text field

Wordlist

Scroll Panel

Terjemahan

Text area

Status

Label

Timer

Status label

pemain untuk bermain dengan cara memilih huruf – huruf yang terlihat pada grid. Contoh tampilan gambar 4.2 dibawah ini menunjukkan huruf C A T telah dipilih dan selanjutnya pemain harus menekan tombol check button untuk mengkonfirmasi pilihan kata yang sudah dimasukkan dalam text input. Pilihan yang sudah dikonfirmasi tersebut akan dicocokkan pada kamus oleh komputer. Terdapat dua kemungkinan yang terjadi pada tahap ini yaitu: Jika ada, maka komputer akan memasukkan pada label status sebagai poin dengan besar nilai 1 angka karena aturan dalam permainannya adalah 1 angka untuk 3 huruf yang bisa di temukan. Jika tidak ada, maka komputer akan memasukkan pada label status sebagai penunjuk bahwa kata tidak terdapat dalam kamus.

Digunakan untuk memeriksa kata pada data apakah kata yang dipilih oleh pemain benar atau salah. Digunakan untuk membersihkan huruf – huruf yang sudah dipilih pada text field permainan. Digunakan untuk menunjukkan huruf yang sudah di pilih oleh pemain. Digunakan untuk menunjukkan seluruh kata yang ditemukan oleh komputer. Digunakan untuk menampilkan hasil terjemahan kata yang sedang di pilih pada Wordlist Digunakan untuk menunjukkan status permainan. Digunakan untuk menunjukkan perhitungan mundur waktu yang tersisa pada game

Gambar 4.2 : Tampilan Utama Saat Permainan Sedang Berlangsung 4.3.3 Tampilan Utama Saat Permainan Selesai Tahap ini akan menunjukkan hasil yang sudah diraih oleh pemain, juga menunjukkan seluruh kata hasil temuan oleh komputer.

Tabel 4.3 : Tabel Petunjuk Tool yang Digunakan Pada Aplikasi Gambar 4.3 : Tampilan Utama Saat Permainan Sudah Selesai

4.3.2

Tampilan Figur Utama Saat Permainan Dimulai Berikut ini adalah tampilan figur utama saat permainan dimulai. Tahap ini memungkinkan

V. PENUTUP

6

[5]

5.1 Kesimpulan Dari hasil uji coba yang telah dilakukan pada aplikasi word game scramble dengan algoritma depth first search (DFS), maka dapat diambil kesimpulan bahwa: 1. Penggunaan algoritma depth first search dapat diaplikasikan pada word game scramble untuk mencari seluruh kata yang terdapat pada board dua dimensi 4x4. 2. Pemain dapat memperkaya vocabulary bahasa inggris. 3. Netbeans IDE 6 dengan bahasa pemrograman Java dapat digunakan untuk membuat programprogram atau perangkat lunak yang membutuhkan kecerdasan buatan seperti DFS. 4. Proses Randomization pada aplikasi word game scramble tidak bisa dikatakan optimal penggunaannya yang mengakibatkan ketidakstabilan untuk jumlah kata yang bisa diperoleh.

[6] [7]

[8]

[9]

5.2.

Saran Saran yang dapat diberikan untuk pengembangan pada tugas akhir ini adalah : 1. Menggunakan Genetic Algorithm untuk proses pengacakan kata agar lebih banyak kata yang bisa diperoleh. 2. Menambahkan animasi atau efek suara pada desain antar muka aplikasi word game scramble dapat menambah minat orang untuk memainkannya. 3. Mengimplementasikan word game scramble kearah yang lebih interaktif seperti web-based, multiplayer dengan menggunakan piranti lunak yang berbeda seperti PHP atau J2ME. VI. DAFTAR PUSTAKA [1] El-Bahri, M. Agus. S. Desember 2008. Teaching English Vocabulary Using Games. (diakses tanggal 16 November 2009) [2] Gozali, Evan. 2008. Penggunaan Depth First Search Dalam Pengambilan Keputusan Pada Klimaks Permainan Scrabble. MAKALAH IF2251 STRATEGI ALGORITMIK TAHUN 2008. Teknik Informatika ITB. [3] Krause, Andreas, dan Zollmann, Andreas. 2002. Not So Randomly Typing Monkeys – Rank-frequency Behavior of Natural and Artificial Languages, Algorithms for Information Networks – Project Report. [4] Maulana I, Dimas and Sidik Sasongko, Priyo. 2009. PENERAPAN ALGORITMA BREADTH FIRST SEARCH DAN DEPTH FIRST SEARCH PADA PERMAINAN SLIDE PUZZLE. Undergraduate thesis, Universitas Diponegoro.

7

Mega, Indra. 2000. Kamus Inggris – Indonesia. Kamus John-EchoLs. Miller, David. Juni 1985. Word Games for Formal Logic. University of Warwick. Munir, Rinaldi, MT. 2005. Diktat kuliah IF2251 Strategi Algoritmik. Teknik Informatika ITB. (diakses tanggal 2 Juli 2010) (diakses tanggal 2 Juli 2010)