UNIVERSITAS BINA NUSANTARA Jurusan Teknik Informatika Skripsi Sarjana Komputer Semester Ganjil tahun 2006/2007 ANALISIS DAN DISAIN PERMAINAN SCRABBLE TINGKAT MAHIR DENGAN PENDEKATAN INTELEJENSIA SEMU
Jeffry Nathaniel Sherriff Randy Kelas / Kelompok :
0700720896 0700723576 0700724130 07PBT / 01
Abstrak Permainan Scrabble yang belum banyak didalami dalam dunia AI memiliki banyak celah yang dapat dikembangkan lebih lanjut. Tidak seperti permainan catur yang telah menghasilkan AI dengan kaliber melebihi juara dunia, permainan Scrabble dalam komputer masih sangat sederhana dalam memperhitungkan AI-nya. Fasilitas yang diberikan pada program-program tersebut pun sangat minim. Mereka hanya memberikan lawan permainan (AI) tanpa solusi bagi pihak pemain. Untuk meningkatkan kemampuan AI dan interaktifitas pembelajaran, beberapa metode yang teruji seperti pada catur digabungkan dan kekurangan dari program yang sudah ada dianalisis. AI yang dihasilkan memiliki kaliber tinggi (Expert-Calibre) dan menyediakan sebuah Analysis Tool yang dapat digunakan bagi pengguna tingkat pemula hingga mahir untuk melakukan pembelajaran maupun evaluasi permainan. Representasi kamus dalam pencarian (searching) cepat dengan memori yang minim dilakukan dengan menerapkan Directed Acyclic Graph (DAG), pencarian langkah dipercepat menggunakan Backtracking, dan peningkatan AI dilakukan dengan melakukan evaluasi terhadap langkah serta penggunaan simulasi MINIMAX seperti pada catur yang digabungkan dengan teorema probabilitas. Hasil dari aplikasi yang disertai dengan evaluasi menggunakan kuesioner kepada para pemain Scrabble menunjukkan hasil keseluruhan yang hampir sempurna baik dalam tingkat kecerdasan AI maupun interaktifitasnya. Sebuah AI tak terkalahkan yang bertaraf melebihi pemain Scrabble dunia (Expert-Calibre) pun terpenuhi. Respon yang sangat positif juga diterima dari para pengguna dalam hal kelayakan aplikasi ini sebagai sarana pembelajaran dan peningkatan motivasi para penggunanya dalam dunia Scrabble. Kata Kunci Scrabble, AI (Artificial Intelligence), Analysis Tool, Searching, Directed Acyclic Graph (DAG), Backtracking, MINIMAX, teorema probabilitas
iii
PRAKATA
Puji syukur kepada Tuhan Yang Maha Esa, karena atas rahmat dan karunia-Nya penulis dapat menyelesaikan penulisan skripsi dengan judul “Design and Analysis of Expert-Calibre Scrabble Game Using Artificial Intelligence Approach”. Skripsi ini diajukan sebagai salah satu syarat kelulusan yang harus dipenuhi dalam menyelesaikan jenjang studi Strata-1 (S1) di Fakultas Ilmu Komputer Universitas Bina Nusantara, Jakarta. Dalam penyusunan skripsi ini penulis menyadari tidak luputnya kekurangan, baik dalam teknik penulisan, penguraian, maupun dalam analisa dan pembahasan secara ilmiah. Oleh sebab itu, penulis mengharapkan saran-saran dan tanggapan yang membangun dari para pembca maupun pihak-pihak yang terkait dalam usaha penyempurnaan materi dan cara penulisan skripsi ini. Meskipun demikian, sesungguhnya penulis telah berusaha semaksimal mungkin sesuai dengan kemampuan yang ada dan berdasarkan data dan evaluasi yang didapat guna menghasilkan skripsi yang sebaikbaiknya. Dalam penyusunan skripsi ini penulis banyak menerima bantuan-bantuan serta dukungan-dukungan dari berbagai pihak, baik secara langsung maupun secara tidak langsung, sehingga dapat menyelesaikan penulisan skripsi ini dengan sebaik-baiknya. Untuk itu, dengan kerendahan dan ketulusan hati penulis ingin menyampaikan rasa terima kasih, kepada: •
Bapak Prof. Dr. Gerardus Polla, M.APP.Sc, Selaku Rektor Universitas Bina Nusantara.
iv
•
Bapak H. Mohammad Subekti, BE, M.Sc, Selaku Kepala Jurusan Teknik Informatika, Universitas Bina Nusantara.
•
Bapak Fredy Purnomo, S.Kom., M.Kom. selaku Sekretaris Jurusan Teknik Informatika.
•
Bapak Diaz D. Santika, Ir., Msc, selaku dosen pembibing yang telah banyak meluangkan waktu dan dengan sabar membimbing penulis dalam menyelesaikan skripsi.
•
Orang tua dan keluarga serta saudara-saudara penulis yang telah memberikan semangat dan dukungan moril sehingga penulis dapat menyelesaikan skripsi ini.
•
Para dosen Universitas Bina Nusantara yang telah memberikan materi dan saran dalam penulisan skripsi ini dan yang telah mendidik penulis dalam menempuh ilmu di Universitas Bina Nusantara.
•
Kepada para pemain Scrabble yang telah meluangkan waktunya untuk mencoba aplikasi skripsi ini sehingga skripsi ini dapat diselesaikan dengan lengkap.
•
Dan kepada semua pihak yang telah membantu secara langsung maupun tidak dalam penulisan skripsi ini yang tidak mungkin penulis sebutkan satu persatu.
Akhir kata penulis mengharapkan skripsi ini dapat bermanfaat bagi Anda semua, serta dapat berfungsi sebagai sarana hiburan dan pelatihan bagi masyarakat umum.
Jakarta, 2007
Penulis
v
DAFTAR ISI Halaman Judul Dalam ……………………………………………………………………..i Abstrak …………………………………………………………………………………..ii Prakata ………………………………………………………………………………….iii Daftar Isi
………………………………………………………………………….....v
Daftar Gambar
………………………………………………………………….....x
Daftar Tabel …………………………………………………………………………...xii Daftar Lampiran BAB I
…………………………………………………………………..xiii
PENDAHULUAN ……………………………………………………………..1 1.1
Latar Belakang 1.1.1
……………………………………………………..1
Rumusan Masalah ……………………………………………..6
1.2
Ruang Lingkup
……………………………………………………..7
1.3
Tujuan dan Manfaat ……………………………………………………..8
1.4
Metodologi
1.5
Sistematika Penulisan ……………………………………………………11
……………………………………………………………10
BAB II LANDASAN TEORI 2.1
Algoritma
2.2
Intelegensia Semu
……………………………………………………13
……………………………………………………………13 ……………………………………………………17
2.2.1
Kecerdasan Buatan dan Kecerdasan Alami
2.2.2
Sejarah Kecerdasan Buatan
2.2.3
Lingkup Kecerdasan Buatan Pada Aplikasi Komersial ……20
2.3
Data
2.4
Informasi
……………17
……………………………19
……………………………………………………………………23 ……………………………………………………………23
vi
2.5
2.6
2.7
Database
……………………………………………………………24
2.5.1
Definisi Database ……………………………………………24
2.5.2
List Database
Representasi Data
……………………………………………24
……………………………………………………25
2.6.1
Graph
2.6.2
Directed Acyclic Graph ……………………………………26
Algoritma Sorting
……………………………………………………25
……………………………………………………27
2.7.1
Selection Sort
……………………………………………28
2.7.2
Insertion Sort
……………………………………………29
2.8
Algoritma Searching ……………………………………………………31
2.9
Simulasi
……………………………………………………………32
2.9.1
MINIMAX
……………………………………………32
2.9.2
Nega-Max Function
……………………………………33
2.9.3
Alpha Beta Cutoff
……………………………………33
2.10 Backtracking ……………………………………………………………34 2.11 Anagram
……………………………………………………………35
2.12 Probabilitas
……………………………………………………………36
2.12.1 Permutasi ……………………………………………………37 2.12.2 Kombinasi ……………………………………………………37 BAB III ANALISIS DAN DESAIN APLIKASI ……………………………………39 3.1
Gambaran Umum
……………………………………………………39
3.2
Sejarah Scrabble
……………………………………………………40
3.3
Game Detail ……………………………………………………………41
vii
3.3.1
Notation System ……………………………………………42
3.3.2
Sequence of Play ……………………………………………43
3.3.3
Scoring
3.3.4
Acceptable Word ……………………………………………47
3.3.5
Challenges ……………………………………………………49
……………………………………………………46
3.4
Club and Tournament Play
……………………………………………50
3.5
Taktik dan Strategi
3.6
ZINGY (Computer Artificial Intelligence) dalam Scrabble ……………57
……………………………………………………52
3.6.1
Kosa Kata Kamus (Vocabulary) ……………………………57
3.6.2
Penentuan Langkah (Move Generation) ……………………58
3.6.3
Evaluasi Rack
3.6.4
Simulasi
……………………………………………59
……………………………………………………60
3.7
Pengumpulan dan Pengolahan Data ……………………………………61
3.8
Membuat DAWG 3.8.1
3.9
……………………………………………………66
Format File DAWG
Move Generator
……………………………………69
……………………………………………………70
3.9.1
Move Generator Empty Board
……………………………73
3.9.2
Move Generator Not Empty Board
3.9.3
Pemberian Flag
3.9.4
Blanks
3.9.5
Mengapa Bisa Cepat?
3.9.6
Pseudocode dari Move Generator ……………………………77
……………………73
……………………………………………74
……………………………………………………75 ……………………………………76
3.10 Simulasi Langkah Dengan MINIMAX
viii
……………………………80
3.10.1 MINIMAX
……………………………………………80
3.10.2 Pseudocode dan Bagaimana MINIMAX Bekerja ……………81 3.10.3 Fungsi NegaMax ……………………………………………83 3.11 Prediksi Tiles ……………………………………………………………84 3.11.1 Pseudocode Prediksi Tiles
……………………………86
3.12 Hirearki Menu ……………………………………………………………87 3.13 State Transition Diagram 3.14 Rancangan Layar
……………………………………………91
……………………………………………………92
BAB IV IMPLEMENTASI DAN EVALUASI 4.1
Spesifikasi Sistem
……………………………………94
……………………………………………………94
4.1.1
Spesifikasi Kebutuhan Perangkat Keras ……………………94
4.1.2
Spesifikasi Kebutuhan Piranti Lunak
4.2
Pengoperasian Aplikasi
4.3
Evaluasi
4.4
Kelebihan dan Kekurangan Sistem
……………………94
……………………………………………95
…………………………………………………………..111 …………………………………..113
4.4.1
Kelebihan Sistem …………………………………………..113
4.4.2
Kekurangan Sistem
BAB V SIMPULAN DAN SARAN
…………………………………..114
…………………………………………..115
5.1
Simpulan
5.2
Saran …………………………………………………………………..116
DAFTAR PUSTAKA
…………………………………………………………..115
………………………………………………………....…xv
RIWAYAT HIDUP ………………………………………………………………….xvii LAMPIRAN-LAMPIRAN
ix
DAFTAR GAMBAR Gambar 2.1 Graph
……………………………………………………………………25
Gambar 2.2 Undirected Graph
……………………………………………………26
Gambar 2.3 Directed Graph ……………………………………………………………26 Gambar 2.4 DAWG ……………………………………………………………………27 Gambar 3.1 Scrabble ……………………………………………………………………40 Gambar 3.2 Scrabble Tiles
……………………………………………………………46
Gambar 3.3 Sebuah Lexicon menggunakan trie
……………………………………64
Gambar 3.4 DAWG ……………………………………………………………………65 Gambar 3.5 MiniMax ……………………………………………………………………81 Gambar 3.6 Hirearki Menu
……………………………………………………………87
Gambar 3.7 State Transistion Diagram
……………………………………………91
Gambar 3.8 Form Loading Program ……………………………………………………92 Gambar 3.9 Form Utama dengan Tab History
……………………………………92
Gambar 3.10 Form Utama dengan Tab Choices
……………………………………93
Gambar 3.11 Form Utama dengan Tab Dictionary ……………………………………93 Gambar 4.1 Pemilihan Kamus
……………………………………………………95
Gambar 4.2 Form Loading Program ……………………………………………………96 Gambar 4.3 Form Utama ZINGY
……………………………………………………96
Gambar 4.4 Form Komputer vs Komputer
……………………………………………98
Gambar 4.5 Form Utama dengan Bonus Square Label
……………………………98
Gambar 4.6 Tampilan “Generate All Move” …………………………………………..100 Gambar 4.7 Tampilan “Generate Valuated Move”
x
…………………………………..101
Gambar 4.8 Tiles dipasang diatas papan
…………………………………………..102
Gambar 4.9 Pemilihan “Top Scored Move” …………………………………………..103 Gambar 4.10 Pemilihan “Top Valuated Move”
…………………………………..104
Gambar 4.11 “Next Movement” pada AI vs AI
…………………………………..106
Gambar 4.12 Tampilan dengan tab History terisi
…………………………………..107
Gambar 4.13 Tampilan “Generate Choices” …………………………………………..108 Gambar 4.14 Evaluasi langkah/mentor pada ZINGY Gambar 4.15 Tampilan tab “Dictionary”
…………………………..109
…………………………………………..110
xi
DAFTAR TABEL Tabel 3.1 Petak Flag …………………………………………………………………….75 Tabel 4.1 Spesifikasi Kebutuhan Perangkat Keras …………………………………….. 94 Tabel 4.2 Penyajian data evaluasi dengan responden berjumlah 30 orang …………….112
xii
DAFTAR LAMPIRAN KUESIONER …………………………………………………………………………...L1 GAMBAR PENDUKUNG EXPERT-CALIBRE SCRABBLE AI LISTING PROGRAM
…………………………………………………………...L4
frmChooseDictionary frmLoadProgram
…………………...L2
…………………………………………………...L4
........……………………………………………………...L5
frmScrabble …………………………………………………………………...L6 frmSimulation
………………………………………………………….L39
frmChooseAI
..………………………………………………………...L42
frmAbout
………………………………………………………………….L44
mdlAdditionalFunction mdlBag
………………………………………………….L45
………………………………………………………………….L53
mdlFlexGridScroll ………………………………………………………….L57 mdlGenerate ………………………………………………………………….L62 mdlInitialiseObject ………………………………………………………….L63 mdlKibitz
………………………………………………………………….L68
mdlKillApp ………………………………………………………………….L84 mdlLoad
………………………………………………………………….L87
mdlMoveGenerator ………………………………………………………….L89 mdlMovement
………………………………………………………….L94
mdlPlayNewGame ………………………………………………………...L109 mdlPublic
………………………………………………………………...L120
mdlRack
………………………………………………………………...L123
xiii
mdlRandomRack
………………………………………………………...L128
mdlRefreshBoard
………………………………………………………...L135
mdlSave
………………………………………………………………...L140
mdlScorePrio
………………………………………………………...L141
mdlSearching
………………………………………………………...L147
mdlSimulator
………………………………………………………...L148
mdlSound
………………………………………………………………...L157
mdlStatus
………………………………………………………………...L159
mdlWord
………………………………………………………………...L162
clsBoard
………………………………………………………………...L166
clsNode
………………………………………………………………...L181
clsRack
………………………………………………………………...L189
clsWord
………………………………………………………………...L191
xiv
