PERANCANGAN DAN PEMBUATAN APLIKASI WORD GAME SCRAMBLE PADA BOARD DUA DIMENSI

Seminar Tugas Akhir

PERANCANGAN DAN PEMBUATAN APLIKASI WORD GAME SCRAMBLE PADA BOARD DUA DIMENSI

Noswa Sabdifha 1203 109 009 Dosen Pembimbing Tugas Akhir : Prof. DR. Mohammad Isa Irawan, MT NIP. 196431225 198903 1 001

Institut Teknologi Sepuluh Nopember

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 Depth-First Search pada board 4x4 oleh komputer berdasarkan pencocokan kata pada kamus sehingga diperoleh seluruh kata yang bisa didapat.

20 July 2010

Noswa Sabdifha - Seminar Tugas Akhir : Word Game Scramble Pada Board Dua Dimensi

2

PENDAHULUAN

Latar Belakang • Belajar adalah salah satu kegiatan utama murid di sekolah dengan Bahasa Inggris sebagai salah satu mata pelajaran di kelas. • Banyak metode pembelajaran yang digunakan guru agar murid dapat menangkap apa yang sedang diajarkan. Namun tidak sedikit murid yang merasa bosan sehingga dapat menghambat proses belajar mengajar. Permainan adalah salah satu solusi alternatif untuk pembelajaran murid. Faktanya permainan dapat membantu dan menyemangati banyak murid untuk dapat terus menjaga ketertarikan mereka, sehingga murid mampu mempelajari sebuah kosakata bahasa inggris dan bermain disaat yang bersamaan [1]. • Banyak macam permainan yang bertujuan menambah wawasan English Vocabulary. Salah satunya adalah Word game. Scramble termasuk salah satu jenis permainan Word games yang populer, yang terbentuk dari susunan board. • Terdapat berbagai macam permasalahan dalam pembuatan seperti pengacakan huruf-huruf untuk generate board, pencarian kata pada board 4x4 oleh komputer, dan pencocokan kata pada kamus beserta sistem penilaiannya.

20 July 2010


3

PENDAHULUAN

Rumusan Masalah • Bagaimana mengacak huruf-huruf dalam board 4x4 sehingga lebih banyak kata yang bisa didapat. • Bagaimana pemain dapat mencari kosa kata bahasa Inggris dalam board 4x4. • Bagaimana Komputer dapat mencari seluruh kata dalam board 4x4 dengan menggunakan algoritma Depth-First Search. • Bagaimana kata yang sudah ditemukan oleh pemain atau komputer bisa diketahui terjemahannya dalam bahasa Indonesia.

20 July 2010


4

PENDAHULUAN

Batasan Masalah • • • •

20 July 2010

Board yang digunakan berukuran 4x4. Kata – kata yang digunakan berdasar pada kamus John – Echols. Minimal kata yang didapat adalah 2 karakter. Untuk huruf Q selalu berpasangan dengan huruf U (Qu).


5

PENDAHULUAN

Tujuan Penelitian Tujuan yang ingin dicapai pada Tugas Akhir ini adalah: • Membuat sebuah permainan komputer yang dapat digunakan pemain untuk mencari kosakata bahasa Inggris dalam board 4x4 berisi huruf – huruf yang tersusun secara acak. • Menerapkan algoritma Depth-First Search pada proses pencarian kosakata bahasa Inggris yang terdapat pada board 4x4, sehingga mampu mencari sebanyak mungkin kosakata yang terdapat dalam board.

20 July 2010


6

PENDAHULUAN

Manfaat Penelitian Manfaat dari tugas akhir ini adalah dapat memperkaya wacana kosa kata bahasa Inggris beserta terjemahannya pada user (pemain) dalam sebuah permainan.

20 July 2010


7

DASAR-DASAR TEORI

Permainan Komputer (Computer Game) Game yang dibuat dalam Tugas Akhir ini termasuk dalam kategori Casual Games. Dimana Casual Games merupakan kategori elektronik atau permainan komputer yang ditargetkan pada audiens massal, kategori ini mempunyai ciri khas yaitu: aturan yang sederhana, desain game menarik, tidak memerlukan komitmen waktu atau keterampilan khusus dari pengguna akhir serta produksi dan biaya distribusi dari produsen relatif rendah. Berikut adalah fitur-fitur dalam Casual Games, yaitu : • Gameplay sangat sederhana, biasanya terdapat pada permainan puzzle yang dapat dimainkan sepenuhnya menggunakan mouse satu tombol atau tombol ponsel. • Tidak ada plot. • Memiliki kemampuan untuk cepat mencapai tahap akhir atau bisa berlanjut tanpa menyimpan dalam game tersebut. • Hanya terdapat satu karakter, jika ada. Karakter ini (jika saat itu ada) biasanya merupakan pemain, dan sering hanya sebagai hiasan di perbatasan layar permainan, dan tidak memiliki bantalan pada mekanika game. • Sedikit musik, tapi menarik karena ditampilkan dengan efek suara. • 2 dimensi, grafis abstrak • Seringkali gratis, tersedia baik secara gratis untuk bermain dalam sebuah web browser, termasuk untuk gratis dengan sesuatu yang lain (seperti perangkat lunak produktivitas atau perangkat seperti ponsel), atau tersedia sebagai unduhan gratis, biasanya dengan versi "Deluxe" juga tersedia untuk biaya nominal. Casual Games paling populer untuk 2005 adalah: puzzle games, word games, casual action , card games dan board games.

20 July 2010


8

DASAR-DASAR TEORI

Permainan Komputer (Computer Game) - lanjutan Definisi Word Games Word Games sering dirancang untuk menguji kemampuan bahasa atau untuk mengeksplorasi sifat-sifatnya. Word Games umumnya digunakan sebagai sumber hiburan, tetapi telah dibuktikan untuk melayani suatu tujuan pendidikan juga. Misalnya, anak-anak muda bisa menemukan kesenangan bermain game sederhana seperti Hangman yang kompetitif, sementara secara alami mengembangkan keterampilan bahasa yang penting seperti vocabulary dan ejaan. Memecahkan teka-teki silang, yang membutuhkan pengenalan dengan kosakata yang lebih besar, merupakan hobi yang telah lama bahwa orang dewasa juga memainkannya untuk menjaga pikiran mereka tajam. Salah satu contoh Word Games yang sangat populer adalah Scrabble. 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.

20 July 2010


9

DASAR-DASAR TEORI

Randomization (Alphabet Generator) Berfungsi sebagai pengacak huruf alfabet yang akan keluar di setiap node. 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. Berikut ini sekilas contoh pseudocode tentang alphabet generator untuk pengacakan huruf yang akan digunakan :

jumlah seluruh frekuensi diatas adalah 1, maka dapat didefinisikan sebuah array dengan interval seperti ini:

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.

20 July 2010


10

DASAR-DASAR TEORI

Kecerdasan Buatan (Artificial Intelligence) Artificial Intelligence (AI) atau kecerdasan buatan merupakan cabang dari ilmu komputer yang berhubungan dengan pengautomatisasi tingkah laku cerdas. AI dapat dipandang sebagai: • Dari perspektif kecerdasan, AI adalah bagaimana membuat mesin yang cerdas dan dapat melakukan hal-hal yang sebelumnya hanya dapat dilakukan manusia. • Dari perspektif bisnis, AI adalah sekelompok alat bantu (tools) yang berdayaguna dan metodologi yang menggunakan alat-alat bantu tersebut untuk menyelesaikan masalahmasalah bisnis. • Dari perspektif pemrograman, AI meliputi studi tentang pemrograman simbolik, pemecahan masalah, dan proses pencarian (search). • Dari perspektif penelitian: - Riset tentang AI dimulai pada awal tahun 1960-an, percobaan pertama adalah membuat program permainan catur, membuktikan teori, dan general problem solving. - Artificial intelligence adalah nama pada akar dari studi area.

Bidang-bidang Tugas (Task Domain) dari AI

20 July 2010


11

DASAR-DASAR TEORI

Teknik-teknik Dasar Pencarian Pencarian atau pelacakan merupakan salah satu teknik untuk menyelesaikan permasalahan AI. Keberhasilan suatu sistem salah satunya ditentukan oleh kesuksesan dalam pencarian dan pencocokan. Ada beberapa aplikasi yang menggunakan teknik pencarian ini, yaitu : • Papan game dan puzzle (tic-tac-toe, catur, menara hanoi). • Penjadwalan dan masalah routing (travelling salesman problem). • Parsing bahasa dan inteprestasinya (pencarian struktur dan arti). • Logika pemrograman (pencarian fakta dan implikasinya). • Computer vision dan pengenalan pola. • Sistem pakar bebasis kaidah (rule based expert system). Pencarian adalah proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space). Kondisi suatu pencarian meliputi: • Keadaan sekarang atau awal. • Keadaan tujuan-solusi yang dijangkau dan perlu diperiksa apakah telah mencapai sasaran. • Biaya atau nilai yang diperoleh dari solusi. Solusi merupakan suatu lintasan dari keadaan awal sampai keadaan tujuan. Secara umum, proses pencarian dapat dilakukan seperti berikut: • Memeriksa keadaan sekarang atau awal. • Mengeksekusi aksi yang dibolehkan untuk memindahkan ke keadaan berikutnya. • Memeriksa jika keadaan baru merupakan solusinya. Jika tidak, keadaan baru tersebut menjadi keadaan sekarang dan proses ini diulangi sampai solusi ditemukan atau ruang keadaan habis terpakai. 20 July 2010


12

DASAR-DASAR TEORI

Contoh Pencarian Misalkan ada tiga kotak 1, 2, 3 pada sebuah papan. Sebuah kotak dapat dipindahkan jika tidak ada kotak lain di atasnya dan hanya ada satu kotak yang boleh dipindahkan. Secara umum, algoritma pencarian dalam contoh pencarian ini dapat dituliskan seperti berikut: Contoh Permainan yang Menerapkan Pencarian

Penyelesaian untuk masalah permainan pada gambar diatas adalah anggota kumpulan semua lintasan dari keadaan awal hingga tujuan yang lintasannya ditandai dengan huruf a, d, j, dan l. 20 July 2010


13

DASAR-DASAR TEORI

Algoritma Depth first Search (DFS) 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]. Mula-mula, semua verteks dari graf dinyatakan sebagai "unvisited', maka kita memilih satu dan mengeksplorasi sebuah edge yang mengantarkan kepada verteks baru. mengantarkan kepada verteks yang belum dikunjungi. Prosedur Depth First Search dapat diimplementasikan dengan :

20 July 2010


14

DASAR-DASAR TEORI

Algoritma Depth first Search (DFS) - lanjutan Untuk lebih jelasnya, dapat dilihat aplikasi algoritma tersebut untuk gambar dibawah ini dengan state 21 diasumsikan sebagai tujuannya

20 July 2010

Langkah-langkah penelusuran untuk gambar tersebut adalah: • 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]. • Open = [12, 6, 3, 4]; closed = [19, 11, 5, 2, 1]. • Open = [20, 6, 3, 4]; closed = [12, 19, 11, 5, 2, 1]. • Open = [6, 3, 4]; closed = [20, 12, 19, 11, 5, 2, 1]. • Open = [13, 3, 4] (karena 12 telah di-closed); closed = [6, 20, 12, 19, 11, 5, 2, 1]. • Open = [3, 4]; closed = [13, 6, 20, 12, 19, 11, 5, 2, 1]. • Open = [7, 8, 4]; closed = [3, 13, 6, 20, 12, 19, 11, 5, 2, 1]. • Dan seterusnya sampai state 21 diperoleh atau open = [].


15

METODE PENELITIAN

Media yang Digunakan Beberapa jenis media yang digunakan, diantaranya perangkat keras dan perangkat lunak, akan sangat membantu dalam penelitian ini. Perangkat Keras (Hardware) Perangkat keras yang digunakan dalam implementasi penelitian ini diantaranya : 1. Prosesor Intel Core i5 2.67 GHz. 2. Memory DDR3 2 GB RAM. 3. Harddisk 320GB. 4. VGA Card 128 MB. Perangkat Lunak (Software) Perangkat lunak yang digunakan dalam penelitian ini diantaranya : 1. Sistem operasi Microsoft Windows XP Professional. 2. Netbeans IDE 6 dengan bahasa pemrograman Java.

20 July 2010


16

Mulai

Alur kerja pada perangkat lunak 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 :

METODE PENELITIAN

Papan permainan kosong yang terdiri dari board 4x4 Pengisian board permainan dengan huruf random

(Proses 1) Pencarian kata oleh komputer yang mungkin muncul dan sistem scoring

Penyimpanan nilai terbaik, dan total kata temuan

Permainan oleh user

Konfirmasi dengan user ingin main lagi atau tidak

Y a

Tida k Permainan selesai dengan menunjukkan nilai terbaik, kata terpanjang dan total kata temuan 20 July 2010


17

PERANCANGAN DAN IMPLEMENTASI PERANGKAT LUNAK

Aturan Permainan • • • • •

20 July 2010

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 akan di masukkan dalam daftar kata dan score yang didapat oleh pemain.


18


Proses Pengacakan Huruf atau Randomization (Alphabet Generator) 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. Huruf – huruf yang dipilih akan diacak dengan frekuensi sebagai berikut:

Tabel 1 : Distribusi Nilai Frekuensi Huruf yang Akan Diacak 20 July 2010


19


Proses Pengacakan Huruf atau Randomization (Alphabet Generator) - lanjutan Dengan nilai frekuensi yang terdistribusi pada tabel 1 diharapkan dapat memenuhi kondisi dimana campuran yang baik antara huruf vokal dan konsonan sehingga lebih banyak kata yang bisa di temukan dalam board 4x4 pada aplikasi word game scramble. Sedangkan dalam bahasa pemrograman Java dapat ditulis sebagai berikut : public String getCharRnd(int rndNum) { int min = 0,max = prob[0]; int id = 0; for(int i=0;i<26;i++) { if(rndNum>=min && rndNum<max) { id = i; break; } min = max; max = max + prob[i]; } System.out.println(id); return letters.substring(id,id+1); }

20 July 2010


20

Proses Pengacakan Huruf atau Randomization (Alphabet Generator) - lanjutan Dengan proses inisialisasi sebagai berikut: public void init() { prob = new int[26]; for(int i=0;i<26;i++)prob[i] = 1; //letters = new char[26]; /* inisialisasi untuk * Peluang kemunculan huruf * dengan probabilitas yang berbeda * * */

20 July 2010


prob[0] = 8; prob[1] = 2; prob[2] = 5; prob[3] = 3; prob[4] = 11; prob[5] = 2; prob[6] = 2; prob[7] = 3; prob[8] = 7; prob[11] = 5; prob[12] = 3; prob[13] = 7; prob[14] = 7; prob[15] = 3; prob[17] = 7; prob[18] = 6; prob[19] = 7; prob[20] = 4; prob[24] = 2; for(int i=0;i<26;i++) maxRange +=prob[i]; }


21

Implementasi Algoritma Depth First Search (DFS)


Proses ini berfungsi sebagai pencarian kata dalam aplikasai word game scramble yang dilakukan oleh komputer. Penerapan algoritma DFS ditulis dalam bahasa pemrograman Java sebagai berikut :

/** Depth First Search algorithm */ public boolean stringFound(String search) { search = search.toUpperCase(); this.compareLength = 0; char firstLetterOfSearch = search.charAt(0); for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { if (firstLetterOfSearch == this.dice[i][j].getLetter()) if (this.stringFound(search, i, j)) return true; } } return false; }

20 July 2010


22


Implementasi Algoritma Depth First Search (DFS)- lanjutan

private boolean stringFound(String search, int row, int col) { if (row < 0 || row > 3 || col < 0 || col > 3) return false; Die die = this.dice[row][col]; if (die.isMarked()) return false; else if (search.charAt(this.compareLength)!=die.getLetter()) return false; else if ((search.length() - 1) == this.compareLength) return true; else { die.setMarked(true); this.compareLength++;

20 July 2010


23


Implementasi Algoritma Depth First Search (DFS) - lanjutan for (int i = -1; i <= 1; i++) { for (int j = -1; j <= 1; j++) { if (!(i == 0 && j == 0)) { if (this.stringFound(search, row + i, col + j)) { die.setMarked(false); return true; } } } } } die.setMarked(false); this.compareLength--; return false; } }

20 July 2010


24

PENUTUP

Kesimpulan 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 program-program atau perangkat lunak yang membutuhkan kecerdasan buatan seperti DFS. 4. Proses Randomization pada aplikasi word game scramble tidak bisa dikatakan optimal penggunaannya yang mengakibatkan ketidak-stabilan untuk jumlah kata yang bisa diperoleh.

20 July 2010


25

PENUTUP

Saran 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.

20 July 2010


26

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. [5] Mega, Indra. 2000. Kamus Inggris – Indonesia. Kamus John-EchoLs. [6] Miller, David. Juni 1985. Word Games for Formal Logic. University of Warwick. [7] Munir, Rinaldi, MT. 2005. Diktat kuliah IF2251 Strategi Algoritmik. Teknik Informatika ITB. [8] http://en.wikipedia.org/wiki/Word_games. (diakses tanggal 2 Juli 2010) [9] http://en.wikipedia.org/wiki/Casual_game. (diakses tanggal 2 Juli 2010) 20 July 2010


27

Terima Kasih

20 July 2010


28

PERANCANGAN DAN PEMBUATAN APLIKASI WORD GAME SCRAMBLE PADA BOARD DUA DIMENSI

Recommend Documents