1
PENERAPAN ALGORITMA PENCARIAN SOLUSI MINIMAX DENGAN ALPHA-BETA PRUNING PADA APLIKASI PERMAINAN SEDERHANA
Tugas Akhir Diajukan untuk memenuhi persyaratan guna menyelesaikan Program Studi Strata Satu (S1) Teknik Informatika oleh: DEDY MAEMUDIN NIM 0150212-052
PROGRAM STUDI TEKNIK INFORMATIKA FAKULTAS ILMU KOMPUTER UNIVERSITAS MERCUBUANA JAKARTA 2008
2
LEMBAR PENGESAHAN
Yang bertanda tangan dibawah ini, menyatakan bahwa Laporan Tugas Akhir yang disusun oleh :
Nama
: Dedy Maemudin
N. I. M
: 0150212-052
Program Studi
: Teknik Informatika
Fakultas
: Ilmu Komputer
Judul Tugas Akhir
: Penerapan Algoritma Pencarian Solusi Minimax dengan Alpha-Beta Pruning pada Aplikasi Permainan Sederhana
Telah diperiksa dan disetujui sebagai salah satu syarat untuk mencapai gelar Strata Satu (S1) Program Studi Teknik Informatika, Fakultas Ilmu Komputer, Universitas Mercubuana.
Menyetujui
(Ir Nixon Erzed,MT) Dosen Pembimbing
Mengetahui,
(Abdusy Syarif,ST,MT)
(Raka Yusuf, ST)
Kaprodi Teknik Informatika
Koord. Tugas Akhir
3
LEMBAR PERNYATAAN
Yang bertanda tangan dibawah ini menyatakan bahwa Laporan Tugas Akhir yang disusun oleh : Nama
: DEDY MAEMUDIN
N.I.M
: 0150212-052
Program Studi
: TEKNIK INFORMATIKA
Fakultas
: ILMU KOMPUTER
Benar-benar murni hasil karya dan penelitian sendiri, dan bukan menyalin hasil karya orang lain.
Tangerang, 17 Mei 2008
Penulis
4
ABSTRAK
Teknologi permainan komputer kini berkembang pesat sejalan dengan perkembangan teknologi informasi. Tidak semua permainan komputer hanya mengandalkan ketangkasan pemain dalam mengalahkan lawannya, tetapi butuh kemampuan dan kecerdasan logika pemain untuk menemukan solusi suatu penyelesaian permainan. Seperti halnya permainan catur yang merupakan contoh permainan yang menggunakan kecerdasan buatan. Selain permainan catur, ada banyak permainan lain yang menggunakan prinsip kecerdasan buatan, satu diantaranya yaitu permainan sederhana Deret-4. Permainan Deret-4 adalah suatu permainan papan yang berisi kolom-kolom untuk menyusun bola warna sehingga membuat satu garis lurus tanpa putus secara vertical, horizontal, maupun diagonal. Pemain berjumlah 2 orang yang mempunyai warna bola yang berbeda. Setiap pemain harus memiliki kecerdasan dalam melakukan langkah penyusunan sehingga baik bagi dirinya dan buruk bagi lawan. Permainan Deret-4 ini menggunakan algoritma Minimax dan Alpha-Beta Pruning. Prinsip algoritma tersebut yaitu mendapatkan langkah terbaik tetapi belum tentu terpendek. Algoritma tersebut juga digunakan komputer dalam melakukan langkah bermain apabila memilih lawan bermain dengan komputer.
Kata Kunci : Kecerdasan buatan, permainan komputer, algoritma Minimax dan Alpha-Beta Pruning
5
ABSTRACT
To the present day, the computer games rapidly developed equal with information technological development. Not all of the computer games depending from the players skill to defeat another player but need an ability and logical intelligent from player to find solution to win the game. The chess game one of the example from the artificial intelligence games. Other than the chess game, there is a lot of computer game using an artificial intelligence. One of the simply artificial intelligence games is Deret-4. Deret-4 games is the simply artificial intelligence game with board interface that consist of columns with arrange the colour ball so it will making one straight line vertically, horizontally or diagonally. Deret-4 games can play with two players or against the computer. Each player in this games have a different colour ball in game so that each player must have good intelligent to winning the game. Deret-4 games uses Minimax and Alpha Beta Pruning algorithm . The principle of two algorithms is to finding the best way not the short way from this game. The algorithm also used by computer in doing to step play at if chosening opponent fiddle around with computer.
Keywords: Artificial intellegence ,computer games , Minimax and Alpha Beta Pruning algorithm.
6
KATA PENGANTAR
Dengan mengucapkan Alhamdulillah penulis panjatkan puji syukur kepada Allah Subhanallahu wa Ta ‘ala atas rahmat dan hidayah-Nya serta Shalawat dan salam tercurah senantiasa penulis panjatkan kepada Rosulullah Shalallahu ‘alaihi wa sallam beserta kepada keluarganya, para sahabatnya dan para pengikutnya hingga akhir zaman. Penulis bersyukur dapat menyelesaikan Tugas Akhir ini dengan tema “Penerapan Algoritma Pencarian Solusi Minimax dengan Alpha-Beta Pruning pada Aplikasi Permainan Sederhana” yang disusun guna memenuhi gelar kesarjanaan Strata-1 pada Program Studi Teknik Informatika, Universitas Mercubuana. Dalam penyusunan laporan Tugas Akhir ini banyak pihak yang telah membantu baik secara langsung maupun tidak langsung, Untuk itu perkenankanlah penulis mengucapkan terima kasih kepada: 1. Kedua orang tua penulis yang tak pernah putus untuk selalu mendoakan dan memberikan semangat kepada penulis sehingga penulisan Tugas Akhir ini dapat terselesaikan. Semoga Allah selalu menjagamu. 2. Saudara dan saudari penulis yang telah membantu dalam bentuk dorongan semangat dan mengajarkan ilmu serta pengalamannya (Hendriyana Suhara, Etty Nurhayati, Ferry Hidayat, Nuraeni) dan untuk keponakan-keponakan penulis (Rafadilla, Albar Hilal, Fira Fauziah, Jihan Hasnah) yang selalu menghibur hati penulis.
7
3. Ir.Nixon Erzed, MT selaku dosen pembimbing Tugas Akhir penulis yang telah membimbing penulis dengan sabar hingga laporan ini terselesaikan . 4. Raka Yusuf, ST selaku koordinator Tugas Akhir. 5. Abdusy Syarif, ST, MT, selaku Ketua Jurusan Teknik Informatika Universitas Mercubuana. 6. Segenap para pengajar di Universitas Mercubuana yang telah mengajarkan ilmunya kepada penulis. 7. Rekan-rekan di Info_semu2 (M.Yani, Robby.A, Sukarso, Marjoko, Kurniawan, Halim, Tommy P, Sulfa, dan yang lainnya). 8. Teman-teman mahasiswa di Universitas Mercubuana pada umumnya yang telah memberikan saran dan kritiknya. Serta semua pihak yang tidak dapat penulis sebutkan satu per satu yang telah membantu penulis dalam menyelesaikan pembuatan Laporan Tugas Akhir ini. Dengan segala kerendahan hati, penulis menyadari bahwasanya masih banyak sekali kekurangan pada penulisan laporan ini, karena itu penulis mengharapkan saran dan kritik yang sifatnya membangun guna dapat menyempurnakannya pada penulisan yang lain. Semoga laporan Tugas Akhir ini dapat bermanfaat bagi penulis sendiri maupun bagi pembaca pada umumnya. Jazakumullah Khairan katsiran.
Tangerang, 17 Mei 2008
Dedy Maemudin
8
DAFTAR ISI
Halaman Judul Lembar Pengesahan ...........................................................................................i Lembar Pernyataan.................................................................................... ...........ii Abstrak ..............................................................................................................iii Abstract .............................................................................................................iv Kata Pengantar...................................................................................................v Daftar Isi............................................................................................................vii Daftar Gambar ...................................................................................................xi Daftar Tabel.......................................................................................................xiii Bab I. Pendahuluan 1.1 Latar Belakang.............................................................................................1 1.2 Ide dan Teknik Permainan............................................................................2 1.3 Batasan Masalah ..........................................................................................3 1.4 Metodologi Rekayasa...................................................................................4 1.5 Sistematika Penulisan...................................................................................5 Bab II. Landasan Teori 2.1 Pengantar Intelegensi Buatan .......................................................................7 2.1.1 Apa Intelegensi Buatan itu ?......................................................................7 2.1.2 Tujuan Intelegensi Buatan .........................................................................9 2.1.3 Perkembangan Intelegensi Buatan dan Aplikasinya...................................10 2.2 Metode Pencarian Solusi dan Evaluasi .........................................................11
9
2.2.1 Algoritma Pencarian MINIMAX...............................................................12 2.2.2 Algoritma Pencarian Alpha-Beta Pruning..................................................16 2.3 Penggunaan Diagram Flowchart..................................................................23 2.4 Bahasa Pemodelan Obyek Standar ..............................................................24 2.4.1 Diagram-diagram UML ............................................................................25 2.4.1.1 Diagram Use Case..................................................................................26 2.4.1.2 Diagram Urutan (Sequance Diagram) ....................................................28 2.5 Rekayasa Perangkat Lunak..........................................................................29 2.5.1 Model Sekuensial Linier (Baris Berurutan)................................................29 2.5.2 Teknik dan Strategi Pengujian Software ....................................................32 2.5.2.1 Pengujian Kotak Hitam (Black Box Testing)...........................................32 2.5.2.2 Pengujian GUI (Graphic User Interface)................................................33 Bab III. Analisa dan Perancangan 3.1 Deskripsi Umum Game Sederhana Deret-4 ..................................................34 3.2 Analisa Permainan .......................................................................................36 3.2.1 Alasan Menggunakan Algoritma Minimax dengan Alpha-Beta Pruning ....36 3.2.2 Fungsi Evaluasi.........................................................................................37 3.2.3 Spesifikasi Game Deret-4..........................................................................38 3.2.4 Parameter Keberhasilan ............................................................................39 3.2.5 Pemodelan Kemenangan Permainan .........................................................40 3.2.6 Analisis Sistem .........................................................................................43 3.3 Bahasa Pemograman dan Struktur Data yang digunakan ..............................44 3.4 Beberapa Fungsi yang dilakukan Terhadap Variabel ....................................45 3.4.1 Fungsi Mencocokkan ................................................................................46
10
3.4.2 Fungsi Pengaturan Tingkat Kecerdasan ....................................................46 3.4.3 Fungsi Minimax. .......................................................................................46 3.4.4 Fungsi Minimax dengan AB Prunig ..........................................................47 3.5 Pemodelan dengan UML (Unified Modeling Languange).............................47 3.5.1 Diagram Use Case.....................................................................................47 3.5.2 Diagram Urutan (Sequence Diagram)........................................................49 3.6 Pemodelan dengan Flowchart......................................................................51 3.7 Perancangan Layar dan Antar Muka (Interface) ...........................................52 3.7.1 Form Utama ..............................................................................................52 3.7.2 Form Petunjuk Permainan .........................................................................55 3.7.3 Form Tentang Deret-4...............................................................................56 Bab IV. Implementasi dan Pengujian 4.1 Implementasi ...............................................................................................57 4.1.1 Antarmuka Program ..................................................................................57 4.1.2 Modul-modul Objek yang Ada Dalam Program.........................................64 4.1.2.1 Modul FormActivate ..............................................................................64 4.1.2.2 Modul FormCloseQuery.........................................................................65 4.1.2.3 Modul PemainGrpClick .........................................................................65 4.1.2.4 Modul IQGrpClick .................................................................................66 4.1.2.5 Modul EditKolmChange.........................................................................67 4.1.2.6 Modul EditBarisChange.........................................................................67 4.1.2.7 Modul EditBolaChange..........................................................................67 4.1.2.8 Modul BtnUsulanClick...........................................................................68 4.1.2.9 Modul BtnUlangClick ............................................................................68
11
4.1.2.10 Modul BtnBaruClick ............................................................................69 4.1.2.11 Modul BtnHentiClick ...........................................................................71 4.2 Pengujian Program......................................................................................71 4.2.1 Pengujian Perangkat Lunak dengan BlackBox Testing...............................72 4.2.2 Uji Simulasi Permainan.............................................................................77 4.2.3 Analisis Hasil Pengujian ...........................................................................81 Bab V. Penutup 5.1 Kesimpulan..................................................................................................82 5.2 Saran............................................................................................................83 Daftar Pustaka ...................................................................................................84 Lampiran Lampiran 1 (List Kode Program) .......................................................................85
12
DAFTAR GAMBAR
Gambar 2.1 Penerapan Konsep Kecerdasan Buatan di Komputer ......................9 Gambar 2.2 Pohon Pelacakan Minimax..............................................................14 Gambar 2.3 Pencarian Satu-Lapis ......................................................................14 Gambar 2.4 Pencarian Dua-Lapis.......................................................................15 Gambar 2.5 Backing Up Nilai dalam pencarian 2-Lapis .....................................15 Gambar 2.6 Contoh Gambar Tree Dasar Alpha-Beta Pruning.............................18 Gambar 2.7 Gambar Tree Alpha-Beta Pruning...................................................19 Gambar 2.8 Hasil αβ-pruning.............................................................................20 Gambar 2.9 Flowchart Algoritma Minimax dengan Alpha-beta Pruning ............22 Gambar 2.10 Klasifikasi Jenis Diagram UML ...................................................26 Gambar 2.11 Artifak use case diagram ..............................................................27 Gambar 2.12 Contoh Sequance diagram Deret-4 ...............................................29 Gambar 2.13 Model Sekuensial Linier ..............................................................30 Gambar 3.1 Permainan Deret-4 .........................................................................35 Gambar 3.2 Parameter game tree dari Permainan Deret-4 ..................................41 Gambar 3.3 Contoh Kondisi Menang dan Seri Dalam Deret-4 ...........................43 Gambar 3.4 Diagram Use Case Permainan Deret-4 ............................................48 Gambar 3.5 Sequence diagram dari Permainan Deret-4 .....................................50 Gambar 3.6 Diagram Flowchart Permainan Deret-4 ...........................................51 Gambar 3.7 Rancangan Antarmuka Game Deret-4.............................................52 Gambar 3.8 Rancangan Form Petunjuk Permainan.............................................56
13
Gambar 3.9 Rancangan Form Tentang Deret-4 ..................................................56 Gambar 4.1 Tampilan Antarmuka Permainan Deret-4........................................58 Gambar 4.2 Tampilan Form Petunjuk Permainan ...............................................62 Gambar 4.3 Tampilan Form Tentang Deret-4.....................................................63 Gambar 4.4 Kondisi Awal Papan Permainan.....................................................78 Gambar 4.5 Posisi Permainan ke-1.....................................................................79 Gambar 4.6 Posisi Permainan Ke-2....................................................................80 Gambar 4.7 Posisi Permainan Ke-3....................................................................80 Gambar 4.8 Posisi Permainan Ke-4....................................................................81
14
DAFTAR TABEL
Tabel 2.1 Simbol-simbol Diagram Flowchart.....................................................23 Tabel 2.2 Jenis-jenis Diagram UML...................................................................25 Tabel 2.3 Komponen Use Case ..........................................................................27 Tabel 2.4 Komponen Sequance Diagram ...........................................................28 Tabel 3.1 Kebutuhan Sistem ..............................................................................44 Tabel 4.1 Properti dan Kejadian (event) Pada Form Utama ................................58 Tabel 4.2 Properti dan Kejadian (event) Pada Form Petunjuk Permainan............62 Tabel 4.3 Properti dan Kejadian (event) Pada Form Tentang Deret-4 .................63 Tabel 4.4 Hasil Pengujian Blackbox Testing.......................................................72
15
BAB I PENDAHULUAN
1.1 Latar Belakang Perkembangan aplikasi game saat ini mulai marak, dari game yang mudah dipermainkan sampai game yang tingkat kesulitan lebih tinggi yang bahkan malah membuat pusing, namun adapula yang bermain karena hobi Ada banyak aplikasi game yang dibuat dengan prinsip Intelegensi Buatan atau Artificial Intelligence (AI), seperti halnya game yang disukai oleh masyarakat. Pengembangan game itu sendiri masih banyak dikembangkan oleh para peneliti, programmer, maupun ilmuwan dengan memanfaatkan penggunaan algoritma pemograman. Algoritma pemograman yang digunakan dalam pembuatan sebuah aplikasi game juga mempunyai beberapa jenis macamnya, salah satu diantaranya yaitu algoritma pemograman pencarian solusi seperti: Breadth-First Search, Depth-First Search, algoritma A*, Minimax, Hill climbing, Alpha-Beta Pruning, dll. Adapun contoh game-game yang memuat intelegensi buatan seperti: Tic-Tac-Toe, Checkers, Othello, Catur, Go, Backgammon, Knight Game, Blackjack, dan masih banyak lagi. Untuk itu, penulis mencoba membuat aplikasi game sederhana yang bernama ’Deret- 4’. Algoritma yang penulis gunakan adalah algoritma Minimax dengan Alpha-Beta pruning. Alpha-beta pruning merupakan kelanjutan dari algoritma Minimax. Alpha-Beta pruning akan mengefisienkan pencarian pada Minimax tree. Minimax tree merupakan pusat dari hampir keseluruhan program dari game papan
16
yang ada. Bahasa pemrograman yang penulis pilih adalah Delphi. Pemograman Delphi merupakan bahasa pemrograman yang sudah berbasiskan pemograman berorientasi objek.
1.2 Ide dan Teknik Permainan Tugas akhir ini didasari oleh ide sederhana pada permaianan Tic-Tac-Toe atau lebih dikenal di indonesia yakni catur jawa yang biasa dimainkan oleh anak kecil. Catur jawa pada prinsipnya menggunakan algoritma pencarian solusi Minimax. Teknik permainan catur jawa yakni pemain harus membuat satu garis tanpa putus dalam arah vertikal, horizontal maupun diagonal dengan tanda ”X” dan ”O” untuk mewakili kedua pemain yang tersembunyi didalam kotak bujur sangkar yang tersusun berdampingan (seperti papan catur). Sedangkan untuk permainan Deret-4 ini sedikit agak beda dengan catur jawa karena objek yang dipilih untuk mewakili kedua pemain dibuat bola warna yang berlainan yang harus disusun membuat satu garis kedalam kolom papan permainan dimulai dari urutan bawah hingga keatas. Atas prinsip itu diharapkan permainan akan berlangsung lebih lama tergantung dari jumlah kolom yang terisi. Berikut adalah teknik permainan ’Deret-4’ : a. Pemilihan objek yang digunakan dalam permainan ’Deret-4’ menggunakan bola berwarna yang harus disusun kedalam papan permaianan berkolom mulai dari bawah hingga keatas. b. Permainan dimainkan oleh 2 pemain yang berbeda yang berjalan secara bergiliran yakni pemain pertama dengan warna bola BIRU dan pemain kedua dengan warna bola KUNING atau dengan melawan pemain komputer yang menggerakkan salah satu bola warna.
17
c. Penyusunan bola warna harus tersusun sejajar membentuk garis lurus tanpa putus dengan mengisi kolom yang kosong membentuk garis horizontal, vertikal, maupun diagonal kedalam kolom permaianan sebanyak 4 bola. d. Permainan akan berakhir apabila ada salah satu bola yang telah tersusun dan program akan memberikan pesan keterangan yang memberitahukan siapa pemain telah berhasil menyusun bola dan menjadi pemenangnya. Sedangkan untuk tujuan dari penulisan tugas akhir ini adalah selain perwujudan dari algoritma Minimax dan alpha-beta pruning yang diterapkan kedalam aplikasi game sederhana, aplikasi ini membawa kita akan terbiasa dengan merumuskan suatu masalah sekaligus mencari solusinya guna menyelesaikan masalah yang dihadapi dengan mencari banyak solusi dan mengambil solusi yang tepat sehingga daya kecerdasan kita akan terlatih. Selain itu isi program tersebut memuat prosedur pencarian karena algoritma pencarian merupakan teknik yang bermanfaat untuk membangun sistem kecerdasan buatan.
1.3 Batasan Masalah Agar pembahasan dari topik dalam tugas akhir ini tidak melebar dan tetap fokus, maka penulis hanya memfokuskan penerapan algoritma pencarian solusi Minimax dan Alpha-beta Pruning yang diimplementasikan kedalam aplikasi game sederhana dengan batasan masalah sebagai berikut: a. Penjelasan tentang intelegensi buatan hanya pada algoritma pencarian solusi Minimax dan alpha-beta pruning mengingat algoritma yang digunakan pada aplikasi game sederhana ’Deret 4’ ini adalah algoritma Minimax dan alpha-beta pruning sebagai dasar dari permainan tersebut.
18
b. Permainan hanya bisa dimainkan oleh 2 pemain yang berbeda atau user bermain dengan komputer. c. Penyusunan bola warna berjumlah antara 2-6 bola sejajar secara horizontal, vertikal, maupun diagonal. d. Jumlah kolom dan baris papan permainan hanya dibatasi sampai dengan 10x10. e. Permainan tidak menggunakan batasan waktu dalam berfikir untuk mencari langkah yang tepat bagi setiap pemain.
1.4 Metodologi Rekayasa Metode yang dipergunakan adalah metode baris berurutan yaitu teknik metode pendekatan matematis berurutan didalam pengembangan perangkat lunak. Metode ini terdiri dari empat tahap: 1. Analisis Pada tahap ini penulis mencari dan mendapatkan data dan teori yang diperlukan, menentukan tingkah laku perangkat lunak serta menentukan antar muka yang diperlukan oleh perangkat lunak. 2. Pendesainan Di tahap ini penulis menentukan dan membuat desain dari struktur data yang dibutuhkan, perancangan arsitektur perangkat lunak dan pendesainan antar muka dari aplikasi game ’Deret-4’. 3. Pengkodean Pengkodean dilakukan sebagai terjemahan dari desain-desain yang telah dibuat kedalam instruksi mesin (coding) dengan menggunakan bahasa pemograman Delphi versi 7.0 untuk membuat perangkat lunak yang akan dibuat.
19
4. Pengujian Pada tahap ini dilakukan pengujian terhadap perangkat lunak yang telah dibuat untuk memastikan apakah program dapat dijalankan atau tidak dan apakah program tersebut sudah seperti yang diharapkan atau belum.
1.5 Sistematika Penulisan BAB I
PENDAHULUAN Dalam Bab ini menjelaskan mengenai Latar Belakang Permasalahan yang akan diambil, Ruang Lingkup Kerja, Tujuan Penulisan, Batasan Masalah, dan Sistematika Penelitian.
BAB II
LANDASAN TEORI Dalam Bab ini menjelaskan tentang landasan teori singkat dasar-dasar tentang Intelegensi Buatan, teori dasar Algoritma Pencarian Solusi (Minimax, Alpha-Beta dan penjelasan Alpha-Beta pruning itu sendiri), penggunaan
diagram
flowchart,
bahasa
pemodelan
obyek
standar/UML, dan teori dasar rekayasa perangkat lunak.
BAB III
ANALISA DAN PERANCANGAN Dalam Bab ini penulis menjelaskan ide dari permainan ‘Deret-4’ dan sekaligus menganalisa ide teknik permaianan dalam pencarian solusi dan perancangan program dengan menggunakan bahasa pemodelan objek standar (UML).
20
BAB IV
IMPLEMENTASI DAN PENGUJIAN PROGRAM Dalam Bab ini merupakan implementasi dan pengujian atas aplikasi game sederhana “Deret-4” yang telah dibuat.
BABV
PENUTUP Dalam Bab ini berisikan kesimpulan tentang laporan penulisan dari bab-bab sebelumnya yang dapat diambil garis besarnya serta kritik dan saran untuk kemajuan penulisan-penulisan yang lainnya.
21
BAB II LANDASAN TEORI
2.1 Pengenalan Intelegensi Buatan 2.1.1 Apa Intelegensi Buatan itu? Intelegensi buatan atau biasa yang dikenal dengan kecerdasan buatan atau dalam bahasa Inggrisnya Artificial Intelligence (AI) merupakan cabang terpenting dalam dunia komputer. Akhir-akhir ini teknologi AI telah banyak mempengaruhi kehidupan manusia. AI ialah ilmu dan rekayasa yang membuat mesin mempunyai intelegensi tertentu khususnya program komputer yang ‘cerdas’ (John McCarthy,1995). Intelegensi merupakan bagian kemampuan komputasi untuk mencapai tujuan didalam dunia. Kecerdasan buatan didefinisikan sebagai kecerdasan yang ditunjukkan oleh suatu entitas buatan. Sistem seperti ini umumnya dianggap komputer. Kecerdasan diciptakan dan dimasukkan ke dalam suatu mesin (komputer) agar dapat melakukan pekerjaan seperti yang dapat dilakukan manusia. Beberapa macam bidang yang menggunakan kecerdasan buatan antara lain sistem pakar, permainan komputer (games), logika fuzzy, jaringan syaraf tiruan dan robotika. Banyak hal yang kelihatannya sulit untuk kecerdasan manusia, tetapi untuk Informatika relatif tidak bermasalah. Seperti contoh: mentransformasikan persamaan, menyelesaikan
persamaan
integral,
dan
membuat
permainan
catur
atau
Backgammon. Di sisi lain, hal yang bagi manusia kelihatannya menuntut sedikit kecerdasan, sampai sekarang masih sulit untuk direalisasikan dalam Informatika.
22
Agar komputer bisa bertindak seperti dan sebaik manusia, maka komputer juga harus diberi bekal pengetahuan dan mempunyai kemampuan untuk menalar. Untuk itu pada AI akan mencoba untuk memberikan beberapa metoda untuk membekali komputer dengan kedua komponen tersebut agar komputer bisa menjadi mesin yang pintar. Lebih detailnya, pengertian kecerdasan buatan dapat dipandang dari berbagai sudut pandang, antara lain: 1. Sudut pandang kecerdasan Kecerdasan buatan akan membuat mesin menjadi ‘cerdas’ (mampu berbuat seperti apa yang dilakukan oleh manusia) 2. Sudut pandang penelitian Kecerdasan buatan adalah suatu studi bagaimana membuat agar komputer dapat melakukan sesuatu sebaik yang dikerjakan oleh manusia. 3. Sudut pandang bisnis Kecerdasan buatan adalah kumpulan peralatan yang sangat powerful dan metodologis dalam menyelesaikan masalah-masalah bisnis. 4. Sudut pandang pemograman Kecerdasan buatan meliputi studi tentang pemograman simbolik, penyelesaian masalah ( problem solving ) dan pencarian (searching ). Untuk melakaukan aplikasi kecerdasan buatan ada 2 bagian utama yang sangat dibutuhkan ( Gambar 2.1 ), yaitu: a. Basis Pengetahuan ( Knowledge Base ), berisi fakta-fakta, teori, pemikiran dan hubungan antara satu dengan lainnya.
23
b. Motor Inferensi ( Inference Engine), yaitu kemampuan menarik kesimpulan berdasarkan pengalaman.
KOMPUTER Input masalah
Output Basic Pengetahuan
Motor Inferensi
Pertanyaan, dll
solusi jawaban
Gambar 2.1 Penerapan Konsep Kecerdasan Buatan di Komputer
2.1.2 Tujuan Intelegensi Buatan Menurut Lenat dan Feigenbaum (1992), terdapat sembilan tujuan Intelegensi Buatan yaitu: 1. Memahami kognisi manusia. Untuk mendapatkan pengetahuan ingatan manusia yang mendalam, kemampuan prolem solving, belajar, membuat keputusan, dll. 2. Otomatisasi Biaya dan Efektifitas. Menggantikan manusia dalam tugas-tugas intelegensi. 3. Penguatan Intelegensi Biaya-Efektif. Membangun sistem untuk membantu manusia berpikir lebih baik, lebih cepat, lebih dalam, dll. Contohnya sistem untuk membantu diagnosa penyakit. 4. Intelegensi Manusia Super. Membangun program yang mempunyai kemampuan untuk melebihi intelegensi manusia.
24
5. Problem-solving Umum. Sistem penyelesaian berbagai masalah yang luas. Sistem ini mempunyai kelebihan pikiran. 6. Wacana Koheren. Komunikasi dengan manusia menggunakan bahasa alami. Contohnya dialog cerdas yang ada didalam Turing Test. 7. Otonomi. Mempunyai sistem intelegensi yang beraksi atas inisiatif sendiri, Harus bereaksi dengan dunia nyata. 8. Belajar. Sistem sebaiknya dapat untuk memperoleh data sendiri dan tahu bagaimana memperolehnya. Sistem dapat menyamaratakan, membuat hipotensi, penerapan/pembelajaran secara heuristic, membuat alasan dengan analogi. 9. Informasi. Simpan informasi dan mengetahi dan bagaimana untuk mengambil informasi. Perlu diingat bahwa untuk mencapai tujuan AI diatas diperlukan beberapa strategi. Strategi ini dapat berkembang sesuai dengan kemajuan ilmu dan teknologi yang mendukung AI.
2.1.3 Perkembangan Intelegensi Buatan dan Aplikasinya AI dikembangkan pertama kali pada tahun 1956 ketika John McCarthy dari Massachusets Institute of Technology (MIT) menciptakan bahasa pemograman LISP. Kemudian berkembang dengan dibuat program computer yang berfikir seperti permainan catur dan pembuktian perhitungan
matematis secara komputasi.
Perkembangan bidang kajian AI meliputi penyelesaian masalah, yaitu penyelesaian masalah yang banyak berkaitan erat dengan pencapaian pemikiran. AI juga merupakan proses aktivitas mental dalam mendapatkan penyelesaian terhadap suatu
25
masalah, termasuk menafsirkan dan mengenal pasti masalah, kemudian membuat penganalisaan terhadap masalah yang timbul serta alternative penyelesaiannya. Dalam aplikasi nyata diterapkan dalam banyak hal, misalnya: Pengenalan pola dan analisis citra; Pemahaman bahasa alami; representasi pengetahuan; Pembuktian teorema dan penyelesaian masalah; Permainan Game (catur, game strategi, dll); Pemograman otomatis (sintesa program); Transformasi program; Expert System, Formasi hipotesis dan ramalan; Neural Networks; Daya penglihatan; Mechine Learning ;Algoritma dan pemograman genetika; dan logika Fuzzy.
2.2 Metode Pencarian Solusi dan Evaluasi Ruang
keadaan
dalam
aplikasi
game
dapat
direpresentasikan
dengan
menggunakan pohon pelacakan. Tiap-tiap node pada pohon tersebut berhubungan dengan keadaan yang mungkin dalam permainan tersebut. Setiap gerakan akan membawa perubahan dari keadaan sekarang ( current state ) ke keadaan selanjutnya ( child state ). Permasalahan yang sangat rumit yang dihadapi adalah menentukan child state mana yang terbaik. Untuk mengefektifkan proses pencarian, maka dapat dilakukan dengan 2 cara, yaitu: 1. Membentuk suatu prosedur sedemikian hingga hanya gerakan–gerakan yang baik saja yang dibangkitkan. 2. Membentuk suatu prosedur pengujian sedemikian hingga gerakan (path) yang terbaik yang akan dieksplore pertama kali. Proses
evaluasi juga memegang peranan penting. Evaluasi dapat dilakukan
rekursif atau secara statis, Pada evaluasi rekursif, kita ingin merangking gerakan-
26
gerakan yang mungkin (yang ditunjukkan dengan suatu nilai untuk setiap keadaan). Untuk tiap-tiap gerakan yang mungkin, kita ingin tahu seberapa baik suatu keadaan untuk diikuti (menang atau kalah). Kita dapat mengevaluasi tiap-tiap gerakan dengan mengambil nilai terbaik untuk diikuti. Pada evaluasi fungsi statis, kita mengestimasi seberapa baik suatu node dari pandangan kita. Sebagai contoh: •
Permaianan Tic-Tac-Toe: jumlah baris, kolom atau diagonal yang berisi 2 tanda milik kita .
•
Catur: memberikan bobot pada tiap-tiap bidak (Raja= 1000, Ratu=10, Menteri, Kuda, Benteng =5,dst).
2.2.1 Algoritma Pencarian MINIMAX Salah satu teknik game yang terkenal algoritma MINIMAX. Minimax menggunakan prinsip depth-first-search dengan kedalaman terbatas. Fungsi evaluasi yang digunakan adalah fungsi evaluasi statis, dengan mengasumsikan bahwa lawan akan membuat langkah terbaik yang mungkin dapat diambil. Game untuk dua orang biasanya menggunakan metode MIN dan MAX. MAX berpindah pertama kali kemudian baru MIN dan seterusnya. Prosedur ini menggunakan pencarian minimax. Algoritma minimax adalah pemilihan strategi optimal karena algoritma ini memaksimalkan utilitas dengan asumsi bahwa lawan akan main secara sempurna untuk meminimkannya. Fungsi minimax baik untuk game seperti game catur dan game pemilih dengan strategi optimal didasarkan pada implementasi optimal. Algoritma Minimax berisi lima langkah utama yaitu: 1. Bangkitkan pohon pencarian untuk game yang dibuat
27
2. Pakaikan fungsi utilitas untuk masing-masing terminal daun dalam pohon pencarian untuk mendapatkan nilainya, 3. Gunakan nilai dari angka terminal untuk menentukan node orangtua 4. Mundur ke node orangtua dengan aturan sbb: •
Jika node orangtua adalah node MAX, ambil nilai maksimum dari nilai anak.
•
Jika node orangtua adalah node MIN, ambil nilai minimum dari nilai anak.
5. MIN selalu memilih perpindahan dengan nilai utilitas terendah, MAX tertinggi. MAX harus mengasumsikan bahwa MIN akan bermain untuk memperoleh nilai terendah. Adapun Algoritma MINIMAX dapat ditulis sebagai berikut: Minimax(StatusSaya,Kedalaman,Pemain) IF (Kedalaman==Max) RETURN static (StatusSaya,Pemain) Bangkitkan successor S[1..n] IF (Pemain==Saya) RETURN max of Minimax(S[i],kedalaman+1,Lawan) ElSE RETURN min of Minimax(S[1],kedalaman+1,Saya)
28
Gambar 2.2 menunjukkan pohon pelacakan MINIMAX. A
B
Gerakan LAWAN (Minimum Ply)
E
F
G
H
9
-6
0
0
Gerakan SAYA (Maximum Ply)
C
D
I -2
J
K
-4
-3
Gambar 2.2 Pohon Pelacakan MINIMAX
Pada Minimax kita mengenal adanya istilah ply atau lapisan yaitu gerakan ‘saya’ dan ‘lawan’. Gambar 2.3 berikut menunjukkan games dengan pencarian 1 Lapis, sedangkan Gambar 2.4 menunjukkan games dengan pencarian 2 Lapis.
Saya
A
1 Ply B
C
D
8
3
-2
Gambar 2.3 Pencarian Satu-Lapis
Lawan
29
Saya
A
B
C
E
F
G
H
9
-6
0
0
Lawan
D
I -2
J
K
-4
-3
2 Ply
Saya
Gambar 2.4 Pencarian Dua-Lapis
Pada Minimax ada 2 prosedur yang dijalankan, yaitu : Maksimisasi (dilakukan oleh ’saya’), dan Minimisasi (dilakukan oleh ‘lawan’). Dalam hal ini diperlukan suatu fungsi evaluasi statis yang menyatakan nilai yang mungkin didapat oleh pemain (misalkan nilai tersebut antara -10 sampai +10). Gambar 2.5 menunjukkan backing up nilai yang diperoleh dalam pencarian 2 lapis.
B
-6
A
-2
C
-2
MAKSIMASI
D
-4
MINIMASI E
F
G
H
I
J
K
9
-6
0
0
-2
-4
-3
Gambar 2.5 Backing Up Nilai dalam pencarian 2-Lapis
Pada level pertama ‘saya’ melakukan maksimisasi, sedangkan pada level 2 ‘lawan’ melakukan minimisasi. Lawan memilih nilai yang paling rendah yaitu -6, -2
30
dan -4. Pada saat ‘saya’melakukan maksimisasi, saya akan memilih -2 (nilai terbesar di antara -6, -2 dan -4). Sehingga nilai inilah yang nantinya akan didapat.
2.2.2 Algoritma Pencarian Alpha-Beta Pruning
Algoritma ini merupakan pengembangan dari algoritma sebelumnya yaitu algoritma MINIMAX yang telah dikembangkan oleh John McCarthy tahun 1956 karena beliau beranggapan bahwa pencarian minimax kurang efektif. Masalah utama dengan pencarian minimax adalah kita memperluas setiap node kebawah untuk kedalaman tertentu, dan untuk beberapa kasus pencarian ini akan membuang waktu. Kita dapat menggunakan teknik branch and bound atau batas cabang untuk mengurangi jumlah keadaan yang harus diuji untuk menentukan nilai dari pohon pelacakan. Prinsip dasar seperti yang dipaparkan oleh Russell and Norvig (1995) adalah bahwa algoritma alpha-beta selalu memelihara 2 variabel yaitu α dan β. α diasosiasikan dengan MAX yang tidak pernah turun dan β diasosiasikan dengan MIN yang tidak pernah naik. Adapun bila kita definisikankan pengertian tersebut dapat dijabarkan sebagai berikut: •
Alpha, atau dalam symbol (α) adalah pilihan nilai terbaik dari nilai tertinggi yang kita dapatkan dari banyak pilihan sepanjang lintasan untuk MAX.
•
Beta, atau dalam symbol (β) adalah pilihan nilai terbaik dari nilai terendah yang kita dapatkan dari banyak pilihan sepanjang lintasan untuk MIN.
•
Nilai Alpha dan Beta diperbarui selama pencarian.
31
Salah satu metode yang digunakan untuk memodifikasi algoritma MINIMAX adalah dengan alpha-beta prunig. Alpha-Beta pruning atau pemangkas alpha-beta adalah suatu peningkatan efisiensi yang dapat menghapuskan pencarian banyak anak dari pohon pelacakan. Mengapa dipangkas? Pemangkasan dilakukan untuk mengeliminasi node pencarian yang berpotensi
tidak dapat dicapai dan untuk
mempercepat proses pencarian.
Variabel alpha (α) digunakan sebagai batas bawah node yang akan melakukan maksimisasi. Sedangkan variable beta (β) digunakan sebagai batas atas untuk node yang akan melakukan minimisasi. Pada node-node ayng melakukan minimasi, evaluasi akan dihentikan jika sudah diadapat node anak yang memiliki nilai lebih kecil dibanding dengan batasbawah (α). Sedangkan pada node-node yang melakukan maksimasi, evaluasi akan dihentikan jika sudah didapat node yang memiliki nilai lebih besar dibanding dengan batas atas (β).
Pada akar pohon pencarian, nilai α diset sama dengan -∞ (-“tak terhingga”) sedangkan nilai β diset sama dengan +∞ (+ “tak terhingga). Node-node anak akan memperbaiki nilai α dan β. Node-node yang melakukan maksimasi akan memperbaiki nilai α dari nilai anak-anaknya, sedangkan node-node yang melakukan maksimasi akan memperbaiki nilai β dari nilai anak-anaknya. Jika α > β, maka evaluasi dihentikan.
Tiap-tiap node yang melalui nilai α dan β akan dievaluasi anak-anaknya. Nodenode anak akan memperbaiki nilai α dan β. Node-node yang melakukan minimasi
32
akan memberikan nilai β sesuai dengan nilai nodenya. Sedangkan node-node yang melakukan maksimasi akan memberikan nilai α sesuai dengan nilai nodenya.
Sebagai contoh dapat kita lihat pada gambar 2.6. Setalah menguji node F, maka kita tahu bahwa dijamin ‘Lawan’ akan mendapatkan nilai -5 atau yang lebih rendah ( sebab C akan melakukan minimisasi). Namun kita juga tahu bahwa ‘saya’ akan mendapatkan nilai 3 atau yang lebih besar ( sebab A melakukan maksimisasi). Semua gerakan yang bernilai < 3 akan sangat tidak berguna, sehingga langkah yang dipilih adalah melaui B. Dengan demikian kita tidak perlu mengeksplore C lebih lanjut. Dengan kata lain eksplore ke G tidak diperlukan.
A
B
>3
MAKSIMASI
C
3
<-5 MINIMASI
D
E
F
3
5
-5
G
Gambar 2.6 Contoh Gambar Tree Dasar Alpha-Beta Pruning
33
A MAKSIMASI B
C MINIMASI
D
E
3
5
F
G
H
4 I
J
M
N
5
7
8
MAKSIMASI
MINIMASI K
L
0
7
Gambar 2.7 Gambar Tree Alpha-Beta Pruning
Penggunaan alpha-beta pruning sebagai contoh dapat dilihat pada gambar 2.7. Pada tree ini, andaikan kita bergerak pada subtree dengan akar B, kita akan mendapatkan nilai A minimum 3 (α=3). Apabila nilai α ini kita sampaikan ke F, maka F harus mengeksplore dirinya. Dari sana diperoleh nilai I maksimum adalah 0, dengan demikian F minimum akan memperoleh nilai 0. Nilai ini jauh lebih kecil dari α=3, sehingga cabangan ke I yang lainya tidak dibutuhkan lagi dan harus dipotong (α dilakukan pruning) pada gambar 2.8. Setelah memotong eksplorasi I, J diuji dan didapatkan nilai 5. Hal ini berarti F minimum akan mendapatkan nilai 5, yang juga berarti C maksimum akan mendapatkan nilai 5 (β=5). Hal ini menyebabkan kita harus mengeksplore G.Dari sana G akan mendapatkan nilai 8, dengan demikian C maksimum akan mendapatkan nilai 8. Nilai ini jauh lebih besar dari β=5. Sehingga
34
tidak diperlukan mengeksplore G lebih jauh lagi (β dilakukan pruning) seperti pada gambar 2.8.
4
3
α=3
A
MAKSIMASI
B
C
4
β =5 MINIMASI
α =3 D 3
E
F
5
G
H
7
5
4
I 0
J
M
N
5
7
8
MAKSIMASI
β -pruning
MINIMASI K
L
0
7
α-pruning
Gambar 2.8 Hasil αβ-pruning
Prinsip pemotongan (pruning): •
Setiap node mempunyai 2 variabel yaitu Alpha dan Beta.
•
Bandingkan 2 nilai Alpha dan Beta untuk melakukan pemotongan (pruning). -
Pencarian dapat tidak kontinyu dibawah node MIN yang mempunyai beta < alpha dari orangtua MAX-nya.
-
Pencarian dapat tidak kontinyu dibawah node MAX yang mempunyai alpha > beta dari orangtua MIN-nya.
35
Berikut ini adalah algoritma Minimax dengan Alpha-beta Pruning: Nilai awal α=
dan
β=
Fungsikan alphabeta (n, alpha, beta)
g;
if n = node daun then menghasilkan f(n); else if n= MAX then g:= - ~ ; c:= firstchild (n); while g < β and c ≠ null do f(c)= f(c)+f(n); g:=MAX(g,alphabeta(c,α,β)); α:=MAX(α,g); c:=nextbrother (c); else /* n adalah node */ g:= +~; c:=firstchild(n); while g > α and c ≠ null do f(c)=f(c)+f(n); g:=MIN(g,alphabeta(c,α,β)); β:=MIN(β,g); c:=nextbrother(c); return g;
Adapun apabila algoritma Minimax dengan Alpha-beta Pruning bila digambarkan kedalam gambar diagram flowchart maka seperti gambar berikut:
36
Start
Y
n=leaf?
N N
n=max?
Y g=-~ c= firstchild
N
g
null?
Y f(c) = f(c) + f (n) g=max(g,alphabeta(c,alpha,beta)) alpha=max(alpha,g) c=nextbrother(c)
g=+~ c=firstchild(n)
N
g>alpha & c<>null?
Y f(c) = f(c) + f (n) g=min(g,alphabeta(c,alpha,beta)) beta=min(beta,g) c=nextbrother(c)
Return g
Gambar 2.9 Flowchart Algoritma Minimax dengan Alpha-beta Pruning
37
2.3 Penggunaaan Diagram Flowchart Flowchart adalah representasi grafik dari langkah-langkah yang harus diikuti dalam menyelesaikan suatu permasalahan yang terdiri atas sekumpulan simbol, dimana masing-masing simbol merepresentasikan suatu kegiatan tertentu. Flowchart diawali dengan penerimaan input, pemrosesan input, dan diakhiri dengan penampilan output. Penerimaan input, pemrosesan input, dan penampilan output merupakan kegiatan utama yang membentuk siklus dari semua kegiatan yang dilakukan oleh komputer. Siklus ini disebut dengan siklus I-P-O (Input-Proses-Output).
Tabel 2.1 Simbol-simbol Diagram Flowchart
Simbol
Nama
Fungsi Pembuka atau akhir program
Terminator
Arah aliran Program Garis Alir (flow line)
Proses inisialisasi / pemberian harga awal. Preparation
Proses perhitungan / proses pengelolahan data. Proses
Proses input / output data parameter informasi Input / output data
38
Predefine Proses (sub program
Decision
Permulaan sub program / proses menjalankan sub program.
Perbandingan pernyataan, penyeleksi data memberikan pilihan untuk langkah berikutnya.
On-page Connector
Penghubung bagian-bagian flowchart yang berada pada suatu halaman.
Off-page Connector
Penghubung bagian-bagian flowchart yang berada pada hal berbeda.
2.4 Bahasa Pemodelan Obyek Standar (Unified Multiple language / UML) Bahasa pemodelan grafis telah ada di industri perangkat lunak sejak lama. Pemicu utama dibalik semuanaya adalah bahwa bahasa pemograman berada pada tingkat abstraksi yang tidak terlalu tingggi untuk memfasilitasi diskusi tentang desain. Meskipun faktanya adalah bahasa pemodelan grafis telah ada sejak lama, masih terdapat banyak pertentangan didalam industri perangkat lunak tentang perannya. Pertentangan-pertentangan ini berpengaruh langsung pada bagaimana orang orang memendang peran UML itu sendiri.
UML menjadi penting karena penggunaannya yang luas dan standarisasinya dalam komunitas pengembangan berorientasi obyek ( Object Oriented ). UML tidak hanya menjadi notasi grafis yang dominant dalam dunia Object Oriented tetapi juga merupakan teknik yang popular dilingkungan non object oriented.
39
2.4.1 Diagram–diagram UML
UML versi 2.0 OMG terdiri dari 13 jenis diagram resmi seperti tertulis dalam Tabel 2.1 dan mengklasifikasi mereka seperti pada Gambar 2.10 (Fowler,2005)
Tabel 2.2 Jenis-jenis Diagram UML
DIAGRAM
KEGUNAAN
Aktivitas (activity)
Tingkah laku (behavior) prosedural dan paralel.
Kelas (claas)
Kelas, fitur dan hubungan-hubungan.
Komunikasi (communication)
Interaksi antar obyek; penekanan pada jalur.
Komponen (component) Struktur
komposit
Struktur dan koneksi antar komponen (composite Dekomposisi runtime sebuah kelas.
structure) Penyebaran (deployment) Gambaran
interaksi
Pemindahan artifak ke node. (interaction Campuran
rangkaian
(sequence)
dan
overview)
diagram aktifitas (activity diagram).
Obyek (object)
Contoh konfigurasi dari contoh-contoh.
Paket (package)
Struktur hirarki dari waktu kompilias (compile-time)
Rangkaian/Urutan (sequence)
Interaksi antar obyek; penekanan pada sequence.
Mesin Keadaan (state machine)
Bagaimana even menubah obyek selama aktif.
Pewaktuan (timing)
Interaksi pada obyek; penekanan pada waktu.
Use case
Bagaimana pengguna berinteraksi dengan sebuah sistem.
40
Gambar 2.10 Klasifikasi Jenis Diagram UML
2.4.1.1 Diagram Use Case Use Uase Diagram adalah teknik untuk merekam pensyaratan fungsional sebuah sistem. Use case mendeskripsikan interaksi tipikal antara para pengguna sistem itu sendiri, dengan memberi sebuah narasi tentang bagaimana sistem tersebut digunakan. Dokumen UCD digunakan sebagai rujukan yang benar dalam pengembangan sistem,
41
selain itu juga digunakan oleh user untuk memahami sistem dan mengevaluasi apakah sistem mampu memecahkan masalah yang sedang dihadapi.
Use Case
Actor Use Case
Use Case
Gambar 2.11 Artifak use case diagram
Tabel 2.3 Komponen Use Case
Notasi
Definisi 1. Use Case Urutan langkah-langkah yang secara tindakan saling terkait(scenario), baik terotomatisasi maupun secara manual, untuk tujuan melengkapi satu tugas bisnis tunggal. 2. Aktor Segala sesuatu yang perlu berinteraksi dengan sistem untuk pertukaran informasi.
Sistem
3. Association Hubungan antara pelaku/actor dengan use case dimana terjadi interaksi diantara mereka. 4. Sistem boundary Batasan untuk sistem yang digunakan dalam use case.
42
2.4.1.2 Diagram Urutan (Sequance diagram)
Sequance diagram menggambarkan interaksi antar objek didalam dan disekitar sistem (termasuk pengguna, display,dsb) berupa pesan yang digambarkan terhadap waktu. Berikut beberapa komponen yang biasa digunakan dalam sequensial diagram:
Tabel 2.4 Komponen Sequance Diagram
Notasi
Definisi 1. Lifeline Merepresentasikan keberadaan suatu objek pada suatu waktu 2. Message Komunikasi antara objek yang membawa pesan yang sudah diresult 3. Communication Komunikasi antar objek yang membawa pesan 4. Actifition Bar Untuk menunjukkan saat partisipan masih aktif didalam interaksi.
Diagram urutan terdiri atas dimensi vertical (waktu) dan dimensi horizontal (objek-objek yang terkait). Diagram urutan biasa digunakan untuk menggambarkan scenario atau rangkaian langkah-langkah yang dilakukan sebagai respons dari sebuah kejadian untuk menghasilkan output tertentu. Untuk objek-objek yang memiliki sifat khusus, standar UML mendefinisikan icon khusus untuk objek boundary, controller dan persistent entity. Diawali dari apa yang memicu aktivitas tersebut, proses dan perubahan apa saja yang terjadi secara internal dan output apa yang dihasilkan. Masing-masing objek , termasuk actor, memiliki lifeline vertical. Pesan digambarkan sebagai garis berpanah dari satu objek ke objek lainnya. Pada tahap desain
43
berikutnya, pesan akan dipetakan menjadi operasi/metoda dari kelas. Activation bar menunjukkan lamanya eksekusi sebuah proses, biasanya diawali dengan diterimanya sebuah pesan. Berikut ini adalah contah diagram urutan dari permainan Deret-4.
Pilihan Menu
Input Langkah
Algoritma
Aplikasi Game
Pemain Setting permainan konfigurasi hasil penyettingan Check langkah Tiap pemain Memberitahu hasil algoritma
Informasi pemenang
Gambar 2.12 Contoh Sequance diagram Deret-4
2.5
Rekayasa Perangkat Lunak
2.5.1 Model Sekuensial Linier (Baris Berurutan)
Sekuensial linier mengusulkan sebuah pendekatan kepada perkembangan perangkat lunak yang sistematik dan sekuensial mulai pada tingkat dan kemajuan sistem pada seluruh analisis, desain, kode. pengujian, dan pemeliharaan. Dimodelkan setelah siklus rekayasa konvenional, model sekuensional linier meliputi aktivitasaktivitas sebagai berikut (Pressman, 2002:36-39).
44
Pemodelan sistem informasi Analisi Desain
Kode
tes
Gambar 2.13 Model Sekuensial Linier
a. Rekayasa dan pemodelan sistem /informasi
Karena perangkat lunak selalu merupakan bagian dari sebuah sistem yang lebih besar, kerja dimulai dengan membangun syarat dari semua elemen sistem dan mengalokasikan beberapa subset dari kebutuhan ke perangkat lunak tersebut. Pandangan sistem ini penting ketika perangkat lunak harus berhubungan dengan elemen-elemen yang lain seperti perangkat lunak, manusia, dan basis data.
b. Analisis kebutuhan perangkat lunak
Proses pengumpulan kebutuhan diintensifkan dan difokuskan, khususnya pada perangkat lunak. Untuk memahami sifat program yang dibangun, perekayasa perangkat lunak (analis) harus memahami domain informasi, tingkah laku, unjuk kerja, dan antarmuka yang diperlukan.
c. Desain Desain perangkat lunak sebenarnya adalah proses multi langkah yang berfokus pada empat atribut sebuah program yang berbeda: struktur data, arsitektur perangkat lunak, representasi antarmuka, dan detil (algoritma) procedural. Proses desain
45
menerjemahkan syarat/kebutuhan ke dalam sebuah representasi perangkat lunak yang dapat diperkirakan demi kualitas sebelum dimulai pemunculan kode.
d. Generasi kode Desain harus diterjemahkan kedalam bentuk mesin yang bisa dibaca. Langkah pembuatan kode melakukan tugas ini. Jika desain dilakukan dengan cara yang lengkap, pembuatan kode dapat diselesaikan secara mekanis.
e. Pengujian Sekali kode dibuat, pengujian program dimulai. Proses pengujian berfokus pada logika internal perangkat lunak, memastikan bahwa semua persyaratan sudah diuji, dan pada eksternal fungsional, yaitu mengarahkan pengujian untuk menemukan kesalahan-kesalahan dan memastikan bahwa masukan yang dibatasi akan memberikan hasil actual yang sesuai dengan hasil yang dibutuhkan.
Model sekuensial linier ini adalah paradigma rekayasa perangkat lunak yang paling luas dipakai dan paling tua dipakai. Masalah-masalah yang kadang-kadang terjadi ketika model sekuensial linier diaplikasikan adalah:
1. Jarang sekali proyek nyata mengikuti aliran sekuensial yang dianjurkan oleh model. 2. Kadang–kadang sulit bagi pelanggan untuk menyatakan semua kebutuhan secara ekplisit. 3. Pelanggan harus bersikap sabar. 4. Pengembang sering melakukan penundaan yang tidak perlu.
46
2.5.2 Teknik dan Strategi Pengujian Software
Pengujian menyajikan anomali yang menarik bagi perekayasa perangkat lunak. Pada proses perangkat lunak, perekayasa pertama-tama berusaha membangun perangkat lunak dari konsep abstrak ke implementasi yang dapat dilihat, baru kemudian dilakukan pengujian. Perekayasa menciptakan sederetan tes yang dimaksudkan untuk membongkar perangkat lunak yang sudah dibangun. Pada dasarnya pengujian merupakan suatu langkah dalam proses rekayasa perangkat lunak yang dpat dianggap sebagai hal yang destruktif daripada konstruktif.
2.5.2.1 Pengujian Kotak Hitam (Black Box Testing)
Pengujian kotak hitam berfokus pada persyaratan perangkat lunak. Dengan demikian pengujian kotak hitam memungkinkan perekayasa perangkat lunka mendapatkan serangkaian kondisi masukkan yang sepenuhnya menggunakan semua persyaratan fungsional untuk suatu program. Pengujian kotak hitam bukan merupakan alternative dari teknik kotak putih (White Box), tetapi merupakan pendekatan komplementer yang kemungkinan besar mampu mengungkap kelas kesalahan daripada metode kotak putih.
Pengujian kotak hitam berusaha menemukan kesalahan dalam kategori sebagai berikut (Pressman,2002:551-552):
a. Funsi-fungsi yang tidak benar atau hilang. b. Kesalahan antar muka.
47
c. Kesalahan dalam struktur data atau akses data eksternal. d. Kesalahan kinerja. e. Inisialisasi dan kesalahan terminasi.
2.5.2.2 Pengujian GUI (Graphic User Interface)
GUI menyajikan tantangan menarik bagi para perekayasa. Karena komponen reuseable berfungsi sebagai bagian dari lingkungan pengembangan GUI, pembuatan antarmuka pemakaian telah menjadi hemat waktu dan lebih teliti. Pada saat yang sama, kompleksitas GUI telah berkembang, menimbulkan kesulitan yang lebih besar didalam desain dan eksekusi test case.
Karena GUI modern memiliki bentuk dan citra rasa yang sama, maka dapat dilakukan sederetan pengujian yang standar.
48
BAB III ANALISA DAN PERANCANGAN
3.1 Deskripsi Umum Game Sederhana Deret-4 Deret-4 merupakan suatu permainan berbentuk papan yang mempunyai beberapa kolom yang akan diisikan dengan 2 buah bola warna yang berlainan yakni bola berwarna BIRU dan bola berwarna KUNING untuk mewakili masing-masing pemain untuk disusun ke dalam kolom-kolom tersebut mulai dari dasar kolom sehingga bola warna dapat tersusun. Setiap pemain mendapatkan giliran untuk menyusun bola-bola tersebut. Untuk menyelesaikan permainan ini, haruslah ada salah satu warna bola berjumlah 4 buah yang tersusun sejajar garis lurus secara vertikal, horizontal, maupun diagonal dari kolom-kolom pada papan permainan, maka pemain yang telah menyusun bolanya menjadi 4 deret segaris lurus akan menjadi pemenangnya. Secara spesifik permainan Deret4 ini menitik beratkan pada pencarian tempat untuk menaruh bola warna yang sama sehingga akan terbentuk garis lurus dan lawan akan merasa kesulitan untuk menyusun pula bola warna lainnya. Permainan ini mempunyai standar ukuran papan permaian 7 x 6, tetapi disediakan fasilitas untuk menambah ukuran kolom maupun baris yakni dari ukuran 2 x 2 – 10 x 10. Dalam permainan ini juga disediakan tingkatan-tingkatan dalam menentukan tingkat kecerdasan (IQ) dari masing-masing pemain. Tingkat kecerdasan yang dipilih merupakan kemampuan berfikir untuk menemukan posisi letak bola warna yang tepat dan berfikir untuk melakukan langkah berikutnya. Untuk mendapatkan usulan
49
langkah yang terbaik maka tingkat kecerdasan yang dipilih akan sangat berpengaruh atas keberhasilan memenangkan permainan.Gambar 3.1 adalah ilustrasi permainan.
B
B
B
B
B
B
B
B
Gambar 3.1 Permainan Deret 4
Adapun algoritmanya secara garis besar untuk mendapatkan usulan langkah yang terbaik apabila kita mengalami keraguan atau kesulitan untuk menentukan langkah berikutnya dan dapat menghambat langkah lawan sekaligus memenangkan permainan ini adalah dengan menggunakan bantuan algoritma pemograman pencarian solusi Minimax dengan Alpha-Beta Pruning.
50
3.2 Analisa Permainan Sebelum melangkah pada sub-bab perancangan, penulis melakukan analisa terhadap beberapa hal dalam penggunaan algoritma Minimax dengan Alpha-beta Pruning yang nantinya mencoba menterjemahkan suatu algoritma pencarian solusi tersebut dituangkan kedalam perangkat lunak permainan sederhana yakni dengan nama “Deret-4”.
3.2.1 Alasan Menggunakan Algoritma Minimax dengan Alpha-Beta Pruning Penulis menganalisa pencarian solusi untuk permainan ini menggunakan algoritma Minimax dengan algoritma alpha-beta pruning karena beberapa alasan, antara lain : 1. Algoritma Minimax dengan Alpha-beta pruning telah banyak digunakan oleh para programmer untuk membuat aplikasi game playing. 2. Algoritma Minimax dengan Alpha-beta Pruning mempunyai kemampuan kecerdasan yang mirip dengan kemampuan manusia. 3. Operasi logika dan aritmatika yang digunakan tidak terlalu banyak. 4. Setiap keputusan yang diambil dari pemain itu belum tentu langkah yang terbaik untuk memenangkan permainan. 5. Berusaha mencari langkah terbaik dan mengabaikan langkah yang tidak perlu untuk diambil karena dapat mengurangi waktu untuk langkah pencarian. 6. Dengan menggunakan algoritma alpha-beta pruning ini akan diberikan beberapa pilihan yang ada kemungkinan merupakan solusi untuk mengakhiri permainan. Dengan adanya beberapa alasan tersebut maka penggunaan algoritma Minimax dengan alpha-beta pruning pada pohon permainan dipakai untuk menentukan
51
langkah yang akan diambil oleh komputer. Dari setiap kondisi papan komputer akan mendapatkan suatu nilai tertentu. Nilai itu akan menjadi node pada Algoritma AphaBeta Pruning. Dengan mengevaluasi segala kemungkinan pergerakan lawan berdasarkan kondisi papan saat itu, akan diperoleh node-node baru sehingga membentuk struktur tree. Berdasarkan nilai-nilai node yang telah terbentuk pada tree, Algoritma Minimax dengan Alpha-Beta Pruning dapat memilih langkah terbaik yang harus diambil. Langkah ini mempercepat pencarian karena adanya pemotongan cabang jika diketahui cabang tersebut tidak perlu dievaluasi lebih lanjut.
3.2.2 Fungsi Evaluasi Ada beberapa hal yang dilakukukan dalam mengevaluasi fungsi dari nilai-nilai posisi yang baik. •
Fungsi evaluasi digunakan untuk menilai "seberapa baik" konfigurasi suatu game.
•
Pada game playing fungsi evaluasinya memberikan estimasi tentang kualitas papan permainan dalam mengarahkan seorang pemain untuk memenangkan permainan (static evaluation function) atau disebut juga dengan: Static Board Evaluator, f(n). Tidak seperti heuristic search yang fungsi evaluasinya adalah sebuah bilangan non-negatif, sebagai estimasi biaya dari start-state menuju goal-state. Pada game playing setiap branch nodes: Jika f(n) bilangan positif besar, artinya konfigurasi papan dengan pemilihan node n "baik untuk saya dan buruk untukmu" Jika f(n) bilangan negatif besar, artinya konfigurasi papan dengan pemilihan node n "buruk untuk saya dan baik untukmu"
52
Jika f(n) dekat dengan 0, artinya papan dalam keadaan netral atau seri. •
Pada leaf nodes: Jika f(n) = + "tak terhingga", artinya kondisi saya memenangkan pertandingan. Jika f(n) = - "tak terhingga", artinya kondisi lawan memenangkan pertandingan.
•
Evaluasi papan static (Static Board Evaluator) tidak selalu mudah untuk ditulis.
•
Banyak fungsi evaluasi game playing yang dispesifikasikan sebagai "jumlah berbobot dari featuresnya": (w1*feature1) + (w2*feature2) + (w3*feature3) + ... (wn*feature n). Sebagai contoh pada Deep Blue (program catur yang "imbang" saat menghadapi Gary Kasparov) memiliki tidak kurang dari 6000 kemungkinan dalam fungsi evaluasinya.
•
Untuk fungsi evaluasi yang digunakan pada game Deret-4 adalah: F(n): = cocokan(kolm,baris,-1,0,pemain)+cocokan(kolm,baris,+1,0,pemain)-1
•
Seperti contoh pada permainan Tic-Tac-Toe untuk static evaluation function: f(n) = [jumlah 3-length yang terbuka untuk saya] - [jumlah 3-length yang terbuka untukmu]
3.2.3 Spesifikasi Game Deret-4 . Spesifikasi permainan Deret-4 ini akan memerlukan suatu bidang kerja yakni guna menterjemahkan algoritma pencarian solusi Minimax dengan Alpha-beta
53
Pruning kedalam perangkat lunak. Untuk itu dibutuhkan beberapa komponen yang diperlukan dalam pembuatan program. a. Objek permainan Objek yang digunakan dalam permainan Deret-4 yaitu 2 buah bola warna yang masing-masing bola mempunyai warna berbeda yakni Biru dan Kuning yang menandakan sekaligus mewakili 2 orang pemain. Dalam algoritma yang dipakai, kedua bola ini mewakili nilai MAX dan nilai MIN pada setiap node. b. Papan Permainan Papan permainan yang digunakan dalam permainan ini berupa papan yang didalamnya terdapat sejumlah kolom-kolom yang fungsinya untuk menaruh bola warna agar tersusun dari dasar kolom hingga terisi penuh keatas. Pada prinsipnya papan permainan ini berisikan 42 ruang tempat untuk menaruh bola warna apabila keadaan papan dengan 7 kolom x 6 baris. c. Media Input Media atau alat input yang digunakan dalam permainan ini yaitu perangkat keras mouse yang fungsinya untuk menggerakkan atau menggeser objek bola dengan prinsip drag and drop agar dapat memilih kolom yang tepat baginya dalam menyusun Deret-4. Selain itu juga untuk mengatur menu permainan dengan memberi tanda pada setiap menu.
3.2.4
Parameter Keberhasilan
Parameter keberhasilan yang ingin dicapai dari permainan Deret-4 ini yang sesuai dengan pengimplementasian algoritma Minimax dan Alpha-Beta Pruning akan dianggap sukses jika meliputi hal-hal berikut:
54
a. Permainan dilakukan dengan pilihan lawan yaitu Manusia VS Komputer, sehingga pemilihan setiap langkah yang dilakukan oleh komputer adalah berdasarkan algoritma Minimax dan Alpha-beta pruning yang dipakai dalam aplikasi game. b. Komputer akan memiliki banyak peluang untuk memenangkan permainan karena setiap langkah user akan selalu dicek potensi keberhasilannya oleh komputer melalui algoritmanya. c. Tingkat keberhasilan komputer akan sangat berpengaruh dari tingkat IQ yang dipilih. Semakin tinggi tingkat IQ yang dipilih maka keberhasilan komputer akan semakin besar.
3.2.5 Pemodelan Kemenangan Permainan Dalam pemodelan permainan Deret-4, Ada 7 pemodelan kemenangan yang diilustrasikan berdasarkan kondisi papan permainan. Ketujuh pemodelan tersebut dibuat menjadi game tree (pohon permainan) dengan kondisi awal dari sebuah keadaan akan didapatkan hasil dengan metode Alpha-Beta Pruning dengan mengacu pada gambar 3.2.
55
Level 1 Max Level 1 Max
Level 2 Min
Level 3 Max
Level 4 Min
……
…….
…….
……..
……..
……..
…….. +1
0
-1
Terminal Utilitas
Gambar 3.2 Parameter game tree dari Permainan Deret-4 Keterangan:
………
56
f(n)= +1 jika posisi adalah pemenang untuk bola “Hitam” f(n)= -1 jika posisi adalah pemenang untuk bola “Putih” f(n)= 0 jika posisi adalah “Seri” Pada gambar 3.2 diatas, maka kita bisa mendefinisikan keadaan yang terjadi dalam gambar tersebut. Kita sebut saja Pemain A (bola warna HITAM) mempunyai lawan dengan Pemain B (bola warna PUTIH). Pemain A disebut sebagai MAX dan Pemain B sebagai MIN. Masing-masing node permainan diberi status game tree dengan diberikan suatu nilai evaluasi yang diperoleh dari permulaan node dan diikuti dengan masing-masing kombinasi yang tepat dari gerakan berurutan hingga nodenode dapat dicapai. Permainan Deret-4 ini mempunyai dasar papan permainan dengan ukuran 7 x 6 (7 kolom dan 6 baris). Untuk kemungkinan posisi keadaan menang terdapat 69 posisi yang terdiri dari 24 posisi untuk membentuk garis lurus Horizontal, 21 posisi untuk membentuk garis Vertical dan 24 posisi untuk membentuk garis Diagonal. Dengan suatu bentuk wujud konfigurasi papan, masing-masing dari 69 bentuk posisi menang ini diberi suatu nilai dengan cara berikut: 1. Jika suatu ruang ditempati oleh Max, maka diberi nilai 1 2. Jika suatu ruang ditempati oleh Min, maka diberi nilai -1 3. Jika suatu ruang kosong, maka diberi nilai 0 Pemain dikatakan menang jika berhasil menyusun bola warna yang sama sehingga membentuk satu garis lurus tanpa putus baik secara dalam satu kolom, maupun secara horizontal dan diagonal dari beberapa kolom lainnya. Gambar 3.3 adalah contoh kondisi “menang” dan Kondisi “Seri” dalam permainan Deret4.
57
Secara Vertikal
Secara Horizontal
Secara Diagonal
Kondisi Seri
Gambar 3.3 Contoh Kondisi Menang dan Seri Dalam Deret-4
3.2.6 Analisis Sistem Analisis sistem adalah menganalisa kebutuhan-kebutuhan dari sistem untuk membangun sebuah aplikasi permainan Deret-4 yang terdiri dari spesifikasi perangkat lunak dan spesifikasi perangkat kerasnya. Spesifikasi perangkat keras yang penulis gunakan dan menjadi anjuran untuk dapat membuat dan memainkan game Deret-4 ini tidak perlu membutuhkan spesifikasi komputer yang tinggi karena program permainan ini sudah menjadi atau dijadikan extensinya dari bahasa pemograman yang digunakan ini yaitu Borland
58
Delphi 7.0 dengan cukup baik dengan level yang ideal. Tabel 3.1 adalah rincian kedua analisis sistem yang penulis ajukan:
Tabel 3.1 Kebutuhan Sistem
Perangkat Keras
Perangkat Lunak
Prosesor Intel Pentium III 733 Mhz
Microsoft Windows XP Professional
Memory 256 MB
Harddisk berkapasitas 40 GB
Borland Delphi Versi 7.0
Monitor bertipe VGA
Komponen – komponen pendukung
Keyboard dan mouse Standart PS/2
(SP2)
Borland Delphi versi 7.0
Komputer portable seperti laptop juga dapat memainkan permainan Deret 4 ini asalkan sistem tersebut sudah bisa memenuhi tampilan GUI berbasiskan Windows.
3.3 Bahasa Pemograman dan Struktur Data yang digunakan Bahasa pemograman yang digunakan dalam pembuatan program game Deret-4 ini adalah Borland Delphi yakni bahasa pemograman yang sudah berorientasi pada object (OOP), mengingat dewasa ini hampir semua program sudah menggunakan Windows family sebagai base-nya. Untuk struktur data yang digunakan dalam penulisan program, penulis menggunakan beberapa struktur data dan tipe data seperti berikut: 1. Tipe data Integer
59
Tipe data ini dipakai untuk beberapa variabel yang membutuhkan nilai yang tidak mempunyai titik decimal dan tidak ada karakter lain misalnya koma. Selain itu juga tipe data ini bisa menggunakan tanda plus dan minus. Ada 3 tipe data integer yang digunakan pada penulisan program yakni: Integer, byte, dan longint. 2. Tipe data Boolean Tipe data boolean dipakai untuk variabel yang membutuhkan keputusan dalam coding program. Mempunyai 2 nilai,yakni: benar dan salah (True dan False). Tipe data ini bisa menggunakan operasi and, or, atau not yang dapat membentuk ungkapan Boolean yang lebih rumit. 3. Tipe Larik (array) Larik atau array digunakan untuk variabel yang membutuhkan proses yang terstruktur yang mempunyai komponen dalam jumlah yang tetap dan tipe datanya tetap sama. Contoh bentuk tipe larik pada program game Deret4: GerakanMax:array[1..3] of integer; 7. Konstanta Bertipe Konstanta bertipe dipakai untuk variabel yang membutuhkan konstanta yang ditunjukkan nilainya juga dinyatakan tipe datanya. 8. Operator Aritmatika dan Operator Logika Operator
aritmatika
yang
digunakan
dalam
penulisan
program
yaitu:
Penjumlahan (+), Pengurangan (-), Perkalian (*), Pembagian (div) dan sisa pembagian (mod). Untuk operator logikanya yang digunakan adalah: not, and, dan or.
3.4 Beberapa Fungsi yang dilakukan Terhadap Variabel
60
Untuk efisiensi dan kejelasan pada program yang telah jadi, maka program terdiri dari beberapa fungsi yang pokok yaitu suatu prosedur yang dibuat untuk mendapatkan nilai tertentu, prosedur seperti ini disebut dengan fungsi (function). Dalam pembuatan aplikasi permainan Deret-4, terdapat 5 fungsi yang pokok dan saling berhubungan dalam mengfungsikan terhadap variabel-variabel maupun tipe data yang digunakan. Fungsi yang saling berhubungan tersebut adalah sebagai berikut:
3.4.1 Fungsi Mencocokkan Fungsi ini digunakan untuk memeriksa tanda bola pada papan yang telah membentuk garis lurus. Fungsi ini berisi nilai-nilai: kolm, baris, dk dan db. Fungsi ini akan membentuk garis horizontal, vertikal dan diagonal dari tanda bola warna. Berikut adalah fungsinya: Function cocokan(kolm,baris,dk,db:int; var cekpemain:int):int;
3.4.2 Fungsi Pengaturan Tingkat Kecerdasan Fungsi ini digunakan untuk mendapatkan tingkat kedalaman dan kemungkinan keberhasilan mendapatkan keputusan yang terbaik dimana setiap tingkatan kecerdasan dimulai dari 1-4 berisikan masing-masing angka yang berbeda. Makin besar nilai yang dipilih maka makin besar nilai kedalaman pencarian. Function SetIQ(n:integer):integer;
3.4.3 Fungsi Minimax
61
Fungsi ini digunakan untuk melakukan perkiraan langkah berikutnya. Fungsi ini dipakai juga oleh prosedur gerakan usulan dan prosedur gerakan komputer yang masing-masing prosedur saling berkaitan. Function Minimax(pemain,carilevel:int ;grkterakhir:TPoint):int;
3.4.4 Fungsi Minimax AB Pruning Fungsi Minimax dengan Alpha-Beta Pruning ini untuk mereduksi jumlah node yang diexpand. Kepada fungsi minimax ditambahkan sepasang nilai, a dan byang berarti masing-masing nilai berungsur nilai alpha dan beta. Function MinimaxAB(pemain, carilevel:int; alpha, beta:int; grkterakhir:TPoint):int;
3.5
Pemodelan Dengan UML (Unified Modeling Languange)
Pemodelan untuk membuat game Deret 4 ini menggukan UML (Unified modeling language) karena pemodelan ini sudah mulai sering dipakai oleh para programmer untuk merancang suatu perangkat lunak dan UML menjadi penting karena penggunaannya yang luas dan standarisasinya dalam komunitas pengembangan pemograman orientasi objek.
3.5.1 Diagram Use Case Dalam Use case diagram menggambarkan fungsionalitas yang diharapkan dari sebuah sistem. Yang ditekankan adalah “apa” yang diperbuat sistem, dan bukan “bagaimana” sistem ini melakukannya. Pada gambar 3.4. menunjukkan sebuah use
62
case merepresentasikan sebuah interaksi antara pemain dengan sistem yakni dengan game Deret-4.
Deret-4 Games
Memilih lawan bermain
Memilih tingkat kecerdasan
Mensetting papan permainan
Pemain Permaianan Deret4 Memainkan permainan
Memilih tombol permainan
Gambar 3.4 Diagram Use Case Permainan Deret-4 Penjelasan Gambar 3.4: Pemain pertama-tama melakukan pemilihan lawan untuk bermain dimana didalam menu “Pilih Lawan” terdapat pilihan lawan yaitu : manusia vs manusia dan manusia vs komputer, maka sistem akan menyimpan pilihan tersebut. Lalu pemain menentukan “Tingkat Kecerdasan” yang nantinya akan menghasilkan usulan langkah yang terbaik untuk membantu pemain disaat pemain merasa kesulitan untuk memilih langkah dengan menekan tombol “Usulan” disaat permainan berlangsung. Dalam
63
permainan Deret-4 ini pemain dapat mensetting ukuran papan berdasarkan jumlah kolom, baris maupun jumlah bola menang. Setelah semua pilihan menu telah tersetting dan telah mengkonfigurasikannya kedalam program, program dapat dimainkan. Pada saat berlangsungnya permainan, telah terdapat beberapa tompol pilihan yang masing-masing tombol mempunyai fungsi yang berbeda satu sama lain. Permainan akan berakhir apabila salah satu pemain telah menyusun garis lurus dengan warna bola yang sama atau permainan akan berakhir apabila tidak ada warna bola dari kedua pemain yang tersusun walaupun keadaan papan permainan telah terisi penuh .
3.5.2 Diagram Urutan (Sequence Diagram) Untuk menggambarkan interaksi antar objek dalam sistem dan skenario atau rangkaian langkah-langkah yang dilakukan sebagai respon dari sebuah kejadian dalam sistem digunakan Sequence Diagram yang berisi sekumpulan message yang digambarkan terhadap dimensi waktu (vertical) dan dimensi objek-objek yang terkait (horizontal). Actor dalam permainan Deret-4 ini dilakukan oleh pemain (user) yang mengendalikan permainan sekaligus men Pada gambar 3.5 menggambarkan keadaan permainan dengan sequence diagram yang merepresentasikan proses-proses yang berlangsung antara pemain sistem yakni dengan game Deret-4.
dengan
64
Pilihan Menu
Input Langkah
Algoritma
Aplikasi Game
Pemain Setting permainan konfigurasi hasil penyettingan Check langkah Tiap pemain Memberitahu hasil algoritma
Informasi pemenang
Gambar 3.5 Sequence diagram dari Permainan Deret-4
Penjelasan gambar 3.5: Gambar Sequence Diagram diatas menceritakan bahwa pada saat setelah pemain melakukan
pengaturan
terhadap
menu
permainan
maka
sistem
akan
mengkonfigurasikannya guna menghasilkan pengaturan yang diinginkan. Kemudian pemain bisa memulai permainan dengan menginput langkah. Inputan langkah yang dilakukan oleh masing-masing pemain akan dicek melalui algoritma yang digunakan apakah langkah-langkah tersebut berpotensi untuk membentuk satu garis lurus. Dari hasil pengecekan maka sistem memberitahukan hasil perhitungan langkah dan susunan bola yang sudah tersususn menjadi garis lurus kepada program dan program memberikan informasi hasil akhir dari permainan dengan kotak pesan yang muncul.
65
3.6 Pemodelan dengan Flowchart Melalui gambar diagram flowchart maka akan memebentuk siklus dari semua kegiatan komputer mulai dari pemasukan input, proses algoritma, sampai mendapatkan output atas penyelesaian pemainan Deret-4. Gambar 3.6 adalah gambar diagram flowchart dari permainan Deret-4.
Mulai
Setting Permainan Setting Permainan
Input Langkah gerakan
Hitung Langkah dan Susunan Bola dengan Algoritma
N
Cocokkah Susunan Bola?
Y Output Keberhasilan
Selesai
Gambar 3.6 Diagram Flowchart Permainan Deret-4
66
3.7 Perancangan Layar dan Antar Muka (Interface) Aspek penting mengenai sebuah aplikasi yang berkualitas dapat dilihat dari desain perangkat lunak it u sendiri. Sebuah perangkat lunak dapat terwujud dengan adanya perancangan desain yang merupakan penjabaran dari pengkodean dan algoritma permograman yang digunakan. Rancangan tampilan dari game sederhana Deret 4 dapat dilihat pada Gambar 3.7.
3.7.1 Form Utama
Judul Form
Papan Permainan
Kotak Menu
Deret 4 Games
7 6
Usulan
Ulang Langkah
Mulai Baru
Berhenti
Tombol-tombol
Gambar 3.7 Rancangan Antarmuka Game Deret-4
4
67
Pada rancangan form utama terdapat beberapa komponen yang diantaranya: a. Judul Form Utama Judul form utama ini terdapat Nama Judul Form dan ikon program dan terdapat juga ikon tombol form (minimalisasi, maksimalisasi, dan tutup form). Kedua hal ini menerangkan form dianggap sebagai sebuah window. b. Desain Papan Permainan Papan permainan didesain sedemikian rupa dengan menggunakan gambar bola sebagai objek yang memepunyai 2 buah warna yang berbeda yaitu merah dan biru yang fungsinya dapat mewakili masing-masing pemain agar setiap pemain memainkan bola warna yang ia miliki. Dalam desain papan ini juga dibuat kolom-kolom untuk menempatkan bola warna yang jumlah kolom dan barisnya dapat diatur oleh pemain dengan ukuran mulai dari 2x2 sampai 10x10. c. Kotak Menu Pendesainan kotak menu terdiri dari 4 sub menu yang disediakan untuk mensetting permainan Deret 4 yang terdiri dari: i.
Modul pemilihan lawan pemain Menu ini akan memberi pilihan untuk lawan bermain yakni: Manusia VS Manusia dan Manusia VS Komputer.
ii. Modul tingkat kecerdasan Pada menu ini terdapat 2 bagian menu yang disediakan untuk masing-masing pemain yakni tingkat kecerdasan untuk pemain pertama dan tingkat kecerdasan untuk pemain kedua.Tiap-tiap pemain disediakan 4 tingkatan kecerdasan mulai dari level 1 sampai 4. Tingkat kecerdasan ini berfungsi untuk kemampuan komputer memberikan usulan langkah yang terbaik dalam
68
memilih kolom kepada pemain apabila menghadapi kesulitan untuk mengalahkan lawan. iii. Modul Hasil Skor permainan Hasil kemenangan setiap permainan yang sudah berlangsung akan ditampilkan berupa skor angka ysng selalu bertambah untuk setiap pemain yang berhasil memenangkan permainan yang sesuai dengan keadaan akhir permainan. iv. Modul Setting Papan Permainan Papan permainan dalam Deret 4 ini bisa diatur sesuai dengan keinginan tetapi pada prinsipnya papan ukuran dasarnya adalah 7 kolom x 6 baris untuk bermain. Papan bisa diatur berdasarkan jumlah kolom maupun baris dengan ukuran mulai dari 2x2 sampai 10x10. Pengaturan jumlah kolom dan baris biasanya dipertimbangkan berdasarkan waktu lamanya bermain nantinya maupun tingkat kesulitan bagi permainan karena semakin banyak jumlah kolom dan baris maka semakin lama dan sulitnya untuk menyusun bola warna yang sama dalam satu garis yang sejajar. Penambahan atau pengurangan jumlah kolom dan baris harus di imbangi dengan penambahan atau pengurangan jumlah bola yang harus disusun. Penentuan jumlah bola warna kemenangan bisa diatur mulai dengan jumlah 2 – 6 buah bola. v. Tombol-tombol Pada papan permainan Deret 4 ini juga disediakan beberapa tombol-tombol yang masing-masing tombol mempunyai fungsi yang berbeda-beda. Adapaun tombol-tombol tersebut terdiri dari :
69
Tombol Usulan Digunakan untuk mendapatkan usulan langkah yang terbaik dalam menentukan letak bola apabila sedang mengalami kesulitan mencegah lawan atau memenangkah permainan.
Tombol Ulang Langkah Tombol ini digunakan untuk mengulang kembali gerakan bola apabila letak posisi bola dianggap kurang tepat.
Tombol Mulai Baru Tombol ini berfungsi untuk menata kembali permainan seperti sedia kala apabila permainan telah berakhir dan ingin memulai permainan dari awal kembali.
Tombol Berhenti Tombol berhenti apabila diklik maka permainan akan dihentikan dan menandakan bahwa permainan harus di Reset ulang.
3.7.2 Form Petunjuk Permainan Pada Rancangan Form Petunjuk Permainan ini mempunyai tujuan yaitu untuk memberitahukan kepada pemain tentang cara bermain permainan Deret 4. Untuk rancangannya dapat dilihat pada Gambar 3.8.
70
Judul Form
Isi Petunjuk
OK
Gambar 3.8 Rancangan Form Petunjuk Permainan 3.7.3 Form Tentang Deret 4 Pada Rancangan Form Tentang Deret-4 ini untuk memberitahukan kepada pengguna tentang identitas pembuat program . Sketsa gambarnya seperti berikut:
Judul Form
Deret 4 Games Dedy Maemudin
OK
Gambar 3.9 Rancangan Form Tentang Deret-4
71
BAB IV IMPLEMENTASI DAN PENGUJIAN
4.1 Implementasi Pada bab ini penulis mengimplementasikan apa yang sudah dilakukan dalam penganalisaan dan perancangan pada bab sebelumnya yaitu pada bab ini berisikan tampilan layar antarmuka dari program, file-file unit yang digunakan, dan file-file projek dengan propertisnya dari program.
4.1.1 Antarmuka Program Program game Deret 4 ini dibuat dengan mengunakan Borland Delphi versi 7 yang merupakan Bahasa Pemograman yang berorientasi pada object. Berikut adalah beberapa objek-objek yang dipakai dalam pembuatan program: 1. Form Utama Sebagai antarmuka utama dari program dimana disinilah tempat objek-objek lainnya diletakkan. Berikut ini adalah tampilan antarmuka program game Deret 4 dengan objek-objek didalamnya .
72
Gambar 4.1 Tampilan Antarmuka Permainan Deret-4
Properti dan kejadian (event) setiap objek yang ada di Form utama dapat dilihat pada table 4.1 berikut ini:
Tabel 4.1 Properti dan Kejadian (event) Pada Form Utama No 1
Objek
Properti
Form
Name
: Form1
(TForm)
Caption : Deret 4 Games
2
Kejadian
Keterangan
MainMenu,
Form dapat
FormActivete,
diaktifkan dan
FormCloseQuery.
ditutup
MainMenu
Name
: MainMenu1 Tidak ada
Objek ini
(TMainMenu)
Items
: Petunjuk
berisikan
Permainan,
menu untuk
Tentang
melihat form
Deret 4
lain.
73
3
Label
Name
: LblTunjuk
(TLabel)
Caption : Tidak ada
Tidak ada
Label ini akan memberi petunjuk /instruksi dalam bermain.
4
Image
Name
: Image1
(Timage)
Picture : (None)
Tidak ada
Objek ini akan menampilkan papan permainan yang berisi kolom-kolom.
5
Panel
Name
: Panel1
(TPanel)
Caption : Tidak ada
Tidak ada
Merupakan tempat untuk meletakkan gambar papan permainan.
6
Shape
Name
: BolaWrn
TandaTurunMouse
(TShape)
Shape
: stCircle
TandaGerakMouse merupakan TandaNaikMouse
Objek ini
objek inti dalam permainan.
7
GroupBox
Name : MenuGroup
(TGroupBox)
Caption : Pilihan
Tidak ada
Berisikan grup-grup
Menu
menu permainan
8
RadioGroup
Name : PemainGrp
(TRadioGroup
Caption : Pilih lawan
)
PemainGrpClick
yang Menulainnnya. memilih lawan untuk bermain.
74
9
RadioGroup
Name
(TRadioGroup
Caption : IQ
IQGrpClick
RadioGroup
Name : IQGrp2
(TRadioGroup
Caption : IQ
tingkat IQGrpClick
kecerdasan Menu ini untuk memilih tingkat
Pemain2
)
Menu ini untuk memilih
Pemain1
) 10
: IQGrp1
kecerdasan Pemain 2. 11
Edit1,Edit2
Name : Edit1, Edit2
(TEdit)
Enable : True
Tidak ada
Objek ini untuk mengisi hasil akhir dari setiap permainan berupa skor untuk setiap pemain.
12
GoupBox
Name
: GroupBox2 Tidak ada
Berisikan
(TGroupBox)
Caption: Atur
menu
permainan
mengubah ukuran papan dan jumlah bola.
13
SpinEdit
Name
: EditKolm
EditKolmChange
Objek ini
(TSpinEdit)
MinValue : 2
untuk
MaxValue : 10
mengedit jumlah kolom papan.
14
: EditBaris
EditBarisChange
Objek ini
SpinEdit
Name
(TSpinEdit)
MinValue : 2
untuk
MaxValue : 10
mengedit jumlah baris
75
15
EditBolaChange
Objek ini
SpinEdit
Name
(TSpinEdit)
MinValue : 2
untuk
Maxvalue : 6
mengedit
: EditBola
jumlah bola menang. 16
Button
Name : BtnUsulan
(TButton)
Caption : Usulan
BtnUsulanClick
Tombol untuk mendapatkan usulan langkah.
17
Button
Name : BtnUlang
(TButton)
Caption : Ulang
BtnUlangClick
Tombol untuk mengulang
Langkah
langkah sebelumnya.
18
Button
Name : BtnBaru
(TButton)
Caption : Mulai
BtnBaruClick
Tombol untuk memulai permainan
Baru
baru. 19
Button
Name : BtnHenti
(TButton)
Caption : Berhenti
BtnHentiClick
Tombol untuk menghentikan permainan.
2. Form Petunjuk Permainan Form ini berisikan tentang petunjuk cara bermain permainan Deret 4. Pada form ini hanya menggunakan sedikit objek-objek. Lihat Gambar 4.2 berikut ini:
76
Gambar 4.2 Tampilan Form Petunjuk Permainan
Properti dan kejadian (event) setiap objek yang ada di Form Petunjuk Permainan dapat dilihat pada table 4.2 berikut ini:
Tabel 4.2 Properti dan Kejadian (event) Pada Form Petunjuk Permainan No 1
Objek
Properti
Form
Name
: IntroDlg
(TForm)
Caption : Petunjuk
Kejadian Tidak ada
Image
Name
: Image1
(Timage)
Picture : (TJPEGImage)
Form dapat diaktifkan dan ditutup
Permainan 2
Keterangan
Tidak ada
menampilkan gambar permainan Deret 4.
3
Memo
Name
: Memo1
(TMemo)
Color
: clWhite
Tidak ada
Berisikan tulisan tentang petunjuk permainan.
77
4
Button
Name
: OKBtn
(TButton)
Caption : OK
Tidak ada
Tombol untuk mengembalikan tampilan ke form utama.
1. Form Tentang Deret 4 Form ini berisi tentang identitas pembuat program dan pemodifikasi permainan Deret 4. Lihat Gambar 4.3 berikut ini:
Gambar 4.3 Tampilan Form Tentang Deret-4
Properti dan kejadian (event) setiap objek yang ada di Form Tentang Deret 4 dapat dilihat pada table 4.3 berikut ini: Tabel 4.3 Properti dan Kejadian (event) Pada Form Tentang Deret-4 No 1
Objek
Properti
Form
Name
: Form2
(TForm)
Caption : Tentang Deret 4
Kejadian Tidak ada
Keterangan Form dapat diaktifkan dan ditutup
78
2
Panel
Name : Panel1
Tidak ada
(TPanel)
Objek ini untuk menaruh tempat objeck lainnya.
3
Image
Name
: Image1
(Timage)
Picture : (TJPEGImage)
Tidak ada
menampilkan gambar permainan Deret 4.
4
Label
Name
: Label1
(TTabel)
Caption : Deret 4 Games
Tidak ada
Berisikan tulisan tentang Nama permainan.
5
Button
Name
: OKBtn
(TButton)
Caption : OK
Tidak ada
Tombol untuk mengembalikan tampilan ke form utama.
4.1.2 Modul-modul Objek yang Ada Dalam Program Modul-modul (event) pada tiap-tiap objek yang ada pada program permainan Deret 4 ini berisikan kejadian-kejadian yang dijalankan oleh program pada objekobjek program yang dipakai dan akan mengeset beberapa properti dari objek tersebut. Berikut ini adalah beberapa modul yang berhubungan dengan event suatu objek maupun yang tidak berhubungan. Sedangkan untuk listing program sepenuhnya dapat dilihat pada Lampiran.
4.1.2.1 Modul FormActivate Modul ini berisi prosedur untuk mengatifkan form utama yang didalamnya mengandung beberapa prosedur lainnya Berikut adalah kode programnya.
79
procedure TForm1.FormActivate(Sender: TObject); begin lbrawal:=panel1.width; tinggiawal:=panel1.height; Initialize; panel1.DoubleBuffered:=true; randomize; end;
4.1.2.2 Modul FormCloseQuery Modul ini berfungsi untuk keluar dari program. Kodenya seperti berikut: procedure TForm1.FormCloseQuery(Sender: TObject); var CanClose: Boolean begin tag:=1; canclose:=true; end;
4.1.2.3 Modul PemainGrpClick Modul ini berisi perintah untuk melakukan pemilihan lawan bermain dan mengaktifkan menu tingkat kecerdasan untuk masing-masing pemain. Kodenya programnya seperti berikut: procedure TForm1.PemainGrpClick(Sender: TObject); var i:integer; begin if pemaingrp.itemindex>=0 then with pemaingrp do
80
begin i:=itemindex; if i=1 then begin jmlpemain:=2; IQgrp1.visible:=true; IQgrp2.visible:=true; BtnUsulan.enabled:=true; end; initialize; end; end;
4.1.2.4 Modul IQGrpClick Modul ini berfungsi untuk mengeset tingkat kecerdasan (IQ) dari masing-masing pemain dan menentukan kedalaman dari pencarian pada pohon tree. Berikut adalah kode prosedurnya: procedure TForm1.IQGrpClick(Sender: TObject); begin if sender=IqGrp1 then lookaheads[1]:=Setiq(IQGrp1.itemindex) else if sender=IQGrp2 then lookaheads[2]:=Setiq(IQGrp2.itemindex) end;
81
4.1.2.5 Modul EditKolmChange Modul ini berfungsi untuk mengedit jumlah kolom pada papan permainan sesuai keinginan pemain. Kodenya seperti berikut: procedure TForm1.EditKolmChange(Sender: TObject); begin jmlkolm:=editkolm.value; initialize; end;
4.1.2.6 Modul EditBarisChange Modul ini berfungsi untuk mengedit jumlah baris pada papan permainan. Kodenya seperti berikut: procedure TForm1.EditBarisChange(Sender: TObject); begin jmlbrs:=editbaris.Value; initialize end;
4.1.2.7 Modul EditBolaChange Modul ini berfungsi untuk mengedit jumlah bola untuk menang sesuai keinginan pemain. Berikut adalah kodenya: procedure TForm1.EditBolaChange(Sender: TObject); begin jmlmenang:=editbola.value; initialize;
82
end;
4.1.2.8 Modul BtnUsulanClick Modul ini berfungsi untuk mendapatkan usulan langkah dalam bermain yakni apabila pemain merasa kesulitan untuk memenangkan permainan. Kodenya seperti berikut: procedure TForm1.BtnUsulanClick(Sender: TObject); begin If pikiran then exit; pikiran:=true; gerakanusul; pikiran:=false; end;
4.1.2.9 Modul BtnUlangClick Modul ini berfungsi untuk mengulang langkah atau gerakan yang sudah dilakukan dengan mengembalikan bola sebelum dilakukan langkah yang dipilih. Kode programnya adalah sebagai berikut: procedure TForm1.BtnUlangClick(Sender: TObject); var
L,T:integer;
begin if pikiran then exit; If jmlgerakan>0 then begin with gerakan[jmlgerakan], image1.canvas do begin
83
papan[x,y]:=0; brush.color:=clBlack; L:=lbrpapan+(x)*(lbrbola+lbrpapan); T:=lbrbola*(y+1); fillrect(rect(L,T,L+lbrbola,T+lbrbola)); end; bolabaru(lbrbola div 2); dec(jmlgerakan); akhirgame:=false; pilihpemain; end; end;
4.1.2.10 Modul BtnBaruClick Modul ini akan mereset papan maupun bola dalam keadaan awal permainan untuk memulai permainan baru. Berikut adalah kodenya. procedure TForm1.BtnBaruClick(Sender: TObject); begin btnhenticlick(sender); initialize; end;
Modul BtnbaruClick ini akan memanggil prosedur lainnya yakni prosedur Initialize dan prosedur lokal Papan Baru. Kodenya seperti dibawah ini: procedure TForm1.initialize; procedure papanbaru;
84
var i,hinc:integer; c1,c2:integer; begin with image1, canvas do begin panel1.width:=lbrawal; panel1.height:=tinggiawal; c1:=(panel1.width-(jmlkolm+1)*lbrpapan)div jmlkolm; c2:=(panel1.height-lbrpapan) div (jmlbrs+1); if c1>c2 then lbrbola:=c2 else lbrbola:=c1; panel1.width:=jmlkolm*(lbrbola+lbrpapan)+lbrpapan+2; panel1.height:=(jmlbrs+1)*lbrbola+lbrpapan+2; picture.bitmap.width:=width; picture.bitmap.height:=height; brush.color:=clBlack; fillrect(clientrect); brush.color:=wrnpapan; pen.color:=wrnpapan; rectangle(rect(0,height-lbrpapan,width,height)); hinc:=(width-10) div jmlkolm; for
i:=
0
to
jmlkolm
do
rectangle(rect(i*hinc,lbrbola,
i*hinc+lbrpapan,height-lbrpapan)); end; end;
85
4.1.2.11 Modul BtnHentiClick Modul ini berfungsi untuk menghentikan permainan dengan sengaja baik langkah pemain maupu perhitungan tanda bola. Kodenya seperti berikut: procedure TForm1.BtnHentiClick(Sender: TObject); begin tag:=1; lbltunjuk.caption:='Game dihentikan, Klik Mulai Baru untuk permainan baru'; grkbola:=false; Bolawrn.Enabled:=false; Gameberakhir:=false; berpikir:=false; end;
4.2 Pengujian Program Pada tahap ini penulis melakukan pengujian program dengan 2 tahap. Tahap pertama pengujian dilakukakan dengan membuat blackbox testing yaitu pengujian terhadap perangkat lunak yang telah dibuat dan dilakukan oleh pengguna (user) dari aplikasi tersebut. Isi blackbox testing itu sendiri biasanya berupa kumpulan kuisoner. Tahap yang kedua yaitu dengan menguji simulasi permainan dengan maksud untuk memeriksa seberapa baik peran Algoritma Minimax dengan Alpha-beta Pruning dengan pencarian kedalam pada program permainan Deret-4 dengan melakukan pengujian atas tingkat kecerdasan yang diubah secara berbeda-beda untuk masingmasing pemain dari setiap awal permainan.yang diatur melalui program.
86
4.2.1 Pengujian Perangkat Lunak dengan Blackbox Testing Pengujian blackbox testing dilakukan untuk menguji kelayakan program yang dibuat sesuai target yang diinginkan. Pengujian ini berisikan kumpulan kuisoner atas serangkaian test case yang memenuhi kriteria. Hasil pengujian yang dihasilkan dalam bentuk tabel pengujian yang merupakan ringkasan yang didapat dari kuisoner yang diberikan pada pengguna aplikasi. Berikut ini tabel pengujian dari blackbox testing.
Tabel 4.4 Hasil Pengujian Blackbox Testing
No
Pengujian Keadaan
Hasil Harapan
Hasil Keluaran
1
Pemain menggerakkan
Bola warna bisa
Pergeseran bola warna
objek bola warna
digerakan kekanan dan
baik dan turunnya bola
kekanan secara drag
apabila klik mouse
kedalam kolom juga baik.
and drop dengan
dilepas maka objek
Kecepatan gerakan bola
menggunakan mouse.
akan turun kebawah.
dapat diatur dengan perubahan kode program pada prosedur Tanda Gerak Mouse sebagai berikut: tandagerakMouse (self,[],HalfC+10,0 )
Hasil:Sesuai harapan
87
2
Pemain memilih lawan
Pemain pilih lawan
Pemilihan menu “Pilih
untuk bermain pada
=Manusia, gerakan
Lawan” bekerja baik.
menu “Pilih Lawan”
bola lawan tidak
Tetapi terjadi kesalahan
dilakukan oleh
pada saat pilih lawan =
komputer. Pemain
Manusia yakni warna bola
pilih lawan
lawan sama dengan warna
=Komputer, gerakan
bola Pemain. Tindakannya
bola lawan dilakukan
menambahkan kode
oleh komputer
program pada prosedur “Pilih Pemain” sebagai berikut: bolawrn.brush.color := wrnbola[pemainskrg] ;
Hasil: Sesuai harapan. 3
Pemain memilih
Program akan
Komputer mengarahkan
tombol “Usulan” saat
mengarahkan bola
bola pada kolom yang
permainan
pada kolom yang
menurutnya baik bagi
berlangsung.
menurutnya langkah
pemain dan buruk bagi
yang terbaik untuk
lawan. Baik tidaknya
pemain.
usulan yang diberikan tergantung dari tingkat kecerdasan yang dipilih
88
oleh pemain. Hasil : Sesuai harapan. 4
Pemain memilih
Program akan
Pengembalian bola tidak
tombol “Ulang
mengembalikan posisi
ada masalah tetapi saat
Langkah” saat
bola sebelum
pengulangan gerakan
permainan
digerakkan.
tempat bola yang semula
berlangsung.
meninggalkan bekas putih pada papan.Tindakannya merubah warna papan setelah terjadi pengulangan langkah dengan merubah warna sesuai dengan warna papan. Pengubahan kode warna papan diubah pada prosedur BtnUlangClick: brush.color:=clblac k;
Hasil:Sesuai harapan 5
Pemain memilih
Program akan mereset
tombol
ulang papan permainan “Mulai Baru”, maka isi
“Mulai Baru” setelah
ke kondisi awal.
permainan berakhir.
User memilih tombol
papan permainan ke kondisi awal.
89
6
Pemain memilih
Program akan
Keadaaan bola setelah
tombol “Berhenti” saat
menghentikan
tombol “Berhenti”dipilih
permainan
permainan yang
tetap bisa digerakan
berlangsung.
sedang berlangsung.
karena posisi bola masih enable. Tindakannya pada prosedur BtnHentiClick disisipkan kode sebagai berikut: Bolawrn.Enabled:=fa lse;
Dan pada prosedur BtnBaruClick ditambahkan Kode: Bolawrn.Enabled:=Tr ue;
Untuk dapat mengerakkan kembali bola warna yang akan dimainkan. Hasil : Sesuai harapan 7
Text petunjuk bermain
Setiap kejadian
Program telah
pada bagian atas.
program memberi
memunculkan text sesuai
petunjuk melalui text
dengan event yang sedang
yang ada dibagian atas. belangsung.
90
8
Pesan yang
MessageBox Program memberikan muncul
program.
dari pesan MessageBox
MessageBox informasi pemenang bola biru dan
diakhir permainan
kuning sudah ada dan
untuk informasi
sudah aktif, tetapi
pemenang.
Messagebox untuk keadaan permainan seri belum ada sehingga apabila keadaan permainan berakhir seri, program tidak memberikan informasi. Tindakannya menambahkan MessageBox untuk keadaan permainan seri pada program. if deret4(kolm,baris) then begin if pemainskrg=1 then showmessage('BIRU Menang!klik Mulai Baru untuk permainan baru') else if
91
pemainskrg=2 then showmessage('KUNING Menang!klik Mulai Baru untuk permainan baru') else end else showmessage('Permai nan Seri'); gameberakhir:=true; bolawrn.visible:=fa lse; end; end;
4.2.2 Uji Simulasi Permainan Pengujian ini lebih terkonsentrasi pada simulasi jalannnya permainan Deret-4 yang dilakukan antara Manusia melawan Komputer (metode 1 pemain). Pemain 1 menyusun bola berwarna BIRU sedangkan lawannya Pemain 2 menyusun bola berwarna KUNING. Untuk uji permainan ini, dimensi ukuran papan yang dipakai adalah 7 kolom X 6 baris dengan jumlah tempat yang dapat diisi oleh bola adalah 42 tempat. Jumlah bola yang harus disusun untuk mencapai kemenangan adalah 4 bola. Penulis ingin melihat bagaimana Pemain 2 yakni komputer menjadi salah satu pemain dalam pemainan. Pengujian ini membandingkan bobot atau keputusan langkah terbaik yang dilakukan komputer dengan menggunakan prinsip algoritma minimax dan alpha-beta pruning guna melakukan langkahnya sesuai dengan pengaturan tingkat kecerdasan yang diberikan dan hasil skor kemenangan untuk
92
komputer. Gambar 4.4 dibawah ini adalah kondisi papan permainan dengan mengansumsikan papan menggunakan sumbu kordinat [X,Y].
Y
6
0
0
0
0
0
0
0
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
a
b
c
d
e
f
g
4
X
Gambar 4.4 Kondisi Awal Papan Permainan
Berikut ini adalah tahap-tahap gerakan langkah tiap pemain yang dilakukan disetiap game beserta gambar posisi permainan dengan mengacu pada gambar 4.4. Permainan ke-1 dengan IQ tiap pemain = 1 (Gambar 4.5)
1. a1, d1 2. a2, f1 3. a3, d2 4. a4,
user menang
93
Gambar 4.5 Posisi Permainan Ke-1
Permainan ke-2 dengan IQ tiap pemain = 2 (Gambar 4.6) 1. a1, b1
12. d3, e4
2. a2, g1
13. f2, g4
3. a3, a4
14. f3, c4
4. b2, d1
15. f4, f5
5. b3, d2
16. d4, f6
6. b4, b5
17. d5, d6
7. c1, b6
18. a5, a6
8. c2, c3
19. e5, c5
9. e1, f1
20. c6, e6
10. e2, e3
21. g5, g6
11. g2, g3
Komputer menang
94
Gambar 4.6 Posisi Permainan Ke-2
Permainan ke-3 dengan IQ tiap pemain = 3 (Gambar 4.7) 1. a1, f1 2. a2, e1 3. a3, a4 4. b1, d1 5. c1, g1
Komputer menang
Gambar 4.7 Posisi Permainan Ke-3
Permainan ke-4 dengan IQ tiap pemain = 4 (Gambar 4.8)
95
1. d1, d2 2. c1, e1 3. b1, a1 4. c2, g1 5. c3, c4 6. b2, f1 7. b3, b4 8. a2, d3 9. a3, a4 10. d4, e2
Komputer menang
Gambar 4.8 Posisi Permainan Ke-4
4.2.3 Analisis Hasil Pengujian Dari hasil pengujian simulasi permainan Deret-4 yang telah dilakukan dengan menggunakan tingkat kecerdasan yang sama untuk setiap pemain baik itu untuk user yang bermain maupun untuk komputer sebagai lawan, yakni terlihat bahwa langkah komputer untuk masing-masing tingkatan IQ mengalami perbedaan langkah. Ini bisa
96
kita lihat dari komputer dengan IQ=2 lebih baik daripada IQ=1, IQ=3 lebih baik dari IQ=2 dan IQ=4 lebih baik dengan IQ=3.
97
BAB V PENUTUP
5.1 Kesimpulan Dari hasil penjabaran dan pengujian yang telah dilakukan terhadap aplikasi permainan Deret-4 ini, maka dapat ditarik kesimpulan sebagai berikut: 1. Penerapan algoritma Minimax dengan Alfa-Beta Pruning sebagai algoritma pencarian langkah terbaik terbukti memberikan hasil yang baik dan mangkus. Sifat dari algoritma Minimax dengan Alfa-Beta Pruning yang hanya mengiterasi node yang memiliki bobot tertinggi menyebabkan kemangkusan lebih di tentukan oleh fungsi heuristic. 2. Penggunaan algoritma Minimax dengan Alpha-Beta Pruning dalam aplikasi games Deret 4 tidak selalu membuat komputer selalu memenangkan permainan. Kemungkinan untuk keadaan seri atau kalah untuk komputer tetap ada. 3. Berdasarkan pengujian simulasi permainan, penemuan solusi langkah yang tepat sangat bergantung pada tingkat pencarian kedalaman dan level pencarian (dalam hal ini yaitu tingkah kecerdasan) yang ditentukan karena akan berpengaruh pada kedalaman pencarian dan keberhasilan memenangkan permainan.
98
5.2 Saran Saran-saran yang penulis inginkan untuk kemajuan dari perangkat lunak permainan Deret-4 ini selanjutnya adalah sebagai berikut: 1. Pada permainan Deret-4 ini, bola-bola warna yang telah terbentuk garis lurus diketahui dengan ditandai garis pada bola-bola yang terbentuk tersebut sehingga user mengetahuinya. 2. Media input hardware yang digunakan untuk memainkan permainan Deret-4 ini selain dengan mouse bisa juga menggunakan tombol-tombol keyboard, Sehingga bila user berjumlah 2 orang yang ingin bermain maka user 1 menggunakan mouse dan user 2 menggunakan tombol navigasi keyboard untuk pengendalian permainan. 3. Membuat agar permainan Deret-4 ini bisa dimainkan dalam sebuah jaringan komputer atau berbasiskan web antara user satu dengan yang lainnya walaupun berbeda tempat tetapi telah terhubung jaringan komputer sehingga permainan ini akan lebih menyenangkan. 4. Membuat permainan Deret-4 dapat dimainkan pada telepon seluler yang sudah berbasiskan sistem operasi sehingga game Deret-4 bisa diinstal kedalam ponsel.
99
DAFTAR PUSTAKA
Kusumadewi Sri. 2003. Artificial Intelligence (Teknik dan Aplikasinya), Edisi Pertama, Penerbit Graha Ilmu, Yogyakarta Pressman, Roger S. 1997. Rekayasa Perangkat Lunak Pendekatan Praktis. Buku 1. Terjemahan oleh LN Harnaningrum, dari Software
Engineering: A
Practitioner’s Approach (2002), Penerbit ANDI OFFSET, Yogyakarta Pressman, Roger S. 1997. Rekayasa Perangkat Lunak Pendekatan Praktis. Buku 2. Terjemahan oleh LN Harnaningrum, dari Software Practitioner’s
Approach
(2002-2003),
Penerbit
Engineering: A ANDI
OFFSET,
Yogyakarta Santosa, Insap. 1995. Struktur Data Menggunakan Turbo Pascal 6.0, Penerbit ANDI OFFSET, Yogyakarta Setiawan , Yudha C. 2004. Trik dan Tip Delphi. Edisi Pertama, Penerbit ANDI OFFSET, Yogyakarta Suyoto, Dr 2004. Intelegensi Buatan: Teori dan Pemrograman , Penerbit Gava Media, Yogyakarta Wahana Komputer Semarang. 2003. Panduan Praktis Pemograman Borland Delphi 6.0, Penerbit ANDI OFFSET, Yogyakarta
100
{-------------------------------------------------------Nama Program
: Deret-4 Games
Modifikasi Oleh
: Dedy Maemudin
Algoritma
: Minimax dengan Alpha-Beta Pruning
-------------------------------------------------------}
unit U_Deret4; interface {***$DEFINE
DEBUG}
{remove
***
to
define
DEBUG
and
generate debug code} uses Windows,
Messages,
SysUtils,
Classes,
Graphics,
Controls, Forms, Dialogs, ExtCtrls, StdCtrls, Comctrls, Spin, ShellAPI, Menus;
var skor_b, skor_k : integer; jmlkolm : integer=7; {jumlah kolom} jmlbrs:integer=6; {jumlah baris} jmlblmenang:integer=4; {jumlah bola menang} lbrpapan:integer=10;
{ukuran
maksimal
lebar
baris
papan} jmlpemain:integer; {jumlah pemain} wrnbola:array[1..2]
of
TColor=
(clblue,
clyellow);
{warna bola pemain} Lblpemain:array[1..2] of string= ('Pemain
1:
Gerakkan
dan
lepaskan
bola
BIRU
sesuai kolom yang anda pilih', 'Pemain 2:
Gerakkan dan lepaskan bola KUNING
sesuai kolom yang anda pilih'); wrnpapan:TColor=clred; {warna garis kolom}
101
LookAheads: array [1..3] of integer=(4,4,4);{Tingkatan untuk
melakukan
lookaheads
jika
{Batas perncarian kedalaman}
const winnerval=+100000;
type TPlayerGenus=(Manusia, Komputer); TBaris=array of integer; TForm1 = class(TForm) LblTunjuk: TLabel; Panel1: TPanel; Image1: TImage; BolaWrn: TShape; MenuGroup: TGroupBox; PemainGrp: TRadioGroup; IQGrp1: TRadioGroup; GroupBox2: TGroupBox; EditKolm: TSpinEdit; EditBaris: TSpinEdit; EditBola: TSpinEdit; IQGrp2: TRadioGroup; ABPruning: TCheckBox; Label1: TLabel; Label2: TLabel; Label3: TLabel; Label5: TLabel; Panel2: TPanel; BtnHenti: TButton; BtnBaru: TButton; BtnUlang: TButton;
membuat
angka}
102
BtnUsulan: TButton; MainMenu1: TMainMenu; Help1: TMenuItem; PetunjukPermainan1: TMenuItem; TentangDeret41: TMenuItem; GroupBox1: TGroupBox; Edit1: TEdit; Edit2: TEdit; Label4: TLabel; Label6: TLabel; Panel3: TPanel;
procedure FormActivate(Sender: TObject); procedure FormCloseQuery(Sender: TObject; var CanClose: Boolean); procedure
TandaTurunMouse(Sender:
TObject;
Button:
TMouseButton; Shift: TShiftState; X, Y: Integer); procedure
TandaGerakMouse(Sender:
TObject;
Shift:
TObject;
Button:
TShiftState; X,Y: Integer); procedure
TandaNaikMouse(Sender:
TMouseButton; Shift: TShiftState; X, Y: Integer); procedure BtnUsulanClick(Sender: TObject); procedure BtnBaruClick(Sender: TObject); procedure BtnHentiClick(Sender: TObject); procedure BtnUlangClick(Sender: TObject); procedure IQGrpClick(Sender: TObject); procedure PemainGrpClick(Sender: TObject); procedure EditKolmChange(Sender: TObject); procedure EditBarisChange(Sender: TObject); procedure EditBolaChange(Sender: TObject); procedure PetunjukPermainan1Click(Sender: TObject);
103
procedure TentangDeret41Click(Sender: TObject); procedure FormShow(Sender: TObject);
public { Public declarations }
papan:array of array of integer; {Papan dari permainan, kolom dan baris setiap lubang berisi 0:kosong,1:Pemain A,2:Pemain B} bkbaris:TBaris;
{seluruh array
dari yang rendah membuka
baris untuk masing-masing kolom papan} gerakan:array of TPoint; pemainskrg:byte; {0-255} LbrBola:integer; GrkBola:boolean; Ingatan:integer;{array dari kolom yang terbaik untuk membuat gerakan, kumpulan dari angka fungsi minimax, mengikat untuk skore yang terbaik dari semua masukkan dan hanya satu yang terpilih secara acak} jmlGerakan,
totgerakan:integer;
{yang
sedang
dilakukan
dan perhitungan gerakan max }
Gameberakhir:boolean; berpikir:boolean; {dinyatakan benar selagi mengevaluasi posisi}{mengabaikan turunya mouse atau menarik tanda bola saat komputer sedang berpikir}
lookahead:integer;{dari
gerakan
untuk
pemain yang saat itu sedang jalan}
lookahead
kepada
104
LbrAwal, tinggiawal : integer; {ukuran lebar dan tinggi papan
keadaan
awal,digunakan
bila
melakukan
perubahan
pada kolom atau baris pada papan} GerakanMax:array[1..3] of integer;{gerakan langkah random sewaktu
permainan
dimulai
untuk
masing-masing
pemain
berdasar pada IQ}
procedure initialize; Procedure Bolabaru(x:integer); procedure turunbola(x:integer); function Deret4(kolm,baris:integer):boolean; procedure pilihPemain; function skor(pemain:integer):integer; function Minimax(pemain, carilevel:integer; {$IFDEF DEBUG} Node:TTReeNode; {$ENDIF} grkterakhir:TPoint):integer; function
MinimaxAB(
Alpha,beta:integer;{$IFDEF
pemain,carilevel:integer; DEBUG}
Node:TTReeNode;
{$ENDIF} grkterakhir:TPoint):integer; procedure GerakanTokolm(kolm:integer); function SetIQ(n:integer):integer; procedure gerakankomp; procedure gerakanUsul; function gerakanRandomMax:integer; end;
var
Form1: TForm1;
implementation
{$R *.DFM}
105
Uses
U_Intro , U_About;
var tujuhkolm:array[0..6] of integer=(3,2,4,1,5,0,6); empatkolm:array[0..3] of integer=(2,1,3,0); cobakolm:array of integer; {***************
Mengeset Kecerdasan **************}
function TForm1.SetIQ(n:integer):integer; begin case n of 0: result:=2; 1: result:=3; 2: result:=4; 3: result:=5; else result:=2; {tingkat IQ standart} end; end;
{************** Initialize ************} {Mengeset untuk permainan baru} procedure TForm1.initialize;
{prosedur lokal untuk membuat papan baru} procedure papanbaru;
{menampilkan papan yang bersih} var i,hinc:integer; c1,c2:integer; begin with image1, canvas do begin panel1.width:=lbrawal;
106
panel1.height:=tinggiawal; c1:=(panel1.width-(jmlkolm+1)*lbrpapan)
div
jmlkolm; c2:=(panel1.height-lbrpapan) div (jmlbrs+1); if c1>c2 then lbrbola:=c2 else lbrbola:=c1;
panel1.width:=jmlkolm*(lbrbola+lbrpapan)+lbrpapan+2;{rent etan lebar menurun} panel1.height:=(jmlbrs+1)*lbrbola+lbrpapan+2; picture.bitmap.width:=width; picture.bitmap.height:=height; brush.color:=clBlack; fillrect(clientrect); brush.color:=wrnpapan; pen.color:=wrnpapan; rectangle(rect(0,height-lbrpapan,width,height)); hinc:=(width-10) div jmlkolm; for
i:=
0
to
rectangle(rect(i*hinc,lbrbola,
do
i*hinc+lbrpapan,height-
lbrpapan)); end; bolawrn.width:=lbrbola; bolawrn.height:=lbrbola; pemainskrg:=jmlpemain; pilihpemain; bolabaru(lbrbola div 2); end;{membuat papan baru}
var i,j:integer; begin setlength(papan,jmlkolm,jmlbrs); setlength(gerakan,jmlkolm*jmlbrs+1); setlength(cobakolm,jmlkolm);
jmlkolm
107
totgerakan:=jmlkolm*jmlbrs;
for
i:=0
to
jmlkolm-1
do
for
j:=0
to
jmlbrs-1
do
papan[i,j]:=0;
jmlgerakan:=0; gameberakhir:=false; berpikir:=false; tag:=0; papanbaru; if pemaingrp.itemindex<0 then lbltunjuk.caption:='Untuk
memulai
permainan,
atur
permainan pada kotak sebelah kanan'; Lookaheads[1]:=SetIQ(IQGrp1.itemindex); Lookaheads[2]:=SetIQ(IQGrp2.itemindex); gerakanmax[1]:=IQGrp1.items.count-Iqgrp1.itemindex-1; gerakanmax[2]:=IQGrp2.items.count-IQGrp2.itemindex-1; {memilih
menentukan
-
mencoba
memusat
kolom
yang
dikeluar untuk 4 atau 7 kolom permainan} if
jmlkolm=
7
then
for
i:=0
to
jmlkolm-1
do
cobakolm[i]:=tujuhkolm[i] else
if
jmlkolm=
4
then
for
i:=0
to
jmlkolm-1
do
cobakolm[i]:=empatkolm[i] else for i:=0 to jmlkolm-1 do cobakolm[i]:=i; end;
{*******************Menghidupkan Form******************} procedure TForm1.FormActivate(Sender: TObject); begin lbrawal:=panel1.width; tinggiawal:=panel1.height; Initialize;
108
panel1.DoubleBuffered:=true; randomize; {$IFDEF DEBUG} showdebugbtn.visible:=true;
{$ENDIF}
end;
{************* Memilih Pemain **********} procedure TForm1.PilihPemain; begin bolawrn.Top:=0; inc(pemainskrg); If pemainskrg> jmlpemain then pemainskrg:=1; bolawrn.brush.color:=wrnbola[pemainskrg]; if (not gameberakhir) then lbltunjuk.caption:=lblpemain[pemainskrg]; end;
{************ Membuat Bola Baru **********} procedure TForm1.bolabaru(x:integer); begin bolawrn.left:=x-lbrbola div 2; bolawrn.visible:=true; end;
{************ MENDAPATKAN JUMLAH DERET 4 **************}
function TForm1.Deret4(kolm,baris:integer):boolean; {mengecek jumlah tanda untuk menang didalam setiap baris, nyatakan benar jika begitu}
{Local function ******* Mencocokan *************}
109
function
cocokan(kolm,baris,dk,db:integer;
var
cekpemain:integer):integer; {Menghitung berapa banyak tanda yang memenuhi posisi yang dilewati pindah kearah (dk,db)} var k,b,hitungan:integer; begin cekpemain:=papan[kolm,baris]; k:=kolm+dk;{kolom} b:=baris+db;{baris} hitungan:=1; while
(k>=0)
and
(k<=jmlkolm-1)
and
(b>=0)
and
(b<=jmlbrs-1) and (papan[k,b]=cekpemain) do begin if
(cekpemain=0)
and
(papan[k,b]<>0)
then
cekpemain:=papan[k,b]; inc(k,dk); inc(b,db); inc(hitungan); end; result:=hitungan; end; {mencocokan}
var
n:integer; pemain:integer;
begin {mendapatkan tanda yang berjumlah 4} result:=false; pemain:=papan[kolm,baris]; if pemain=0 then exit; n:=cocokan(kolm,baris,1,0,pemain)+cocokan(kolm,baris,+1,0,pemain)-1; if
n<jmlblmenang
then
n:=cocokan(kolm,baris,0,-
1,pemain)+cocokan(kolm,baris,0,+1,pemain)-1;
110
if
n<jmlblmenang
then
n:=cocokan(kolm,baris,-1,-
1,pemain)+cocokan(kolm,baris,+1,+1,pemain)-1; if
n<jmlblmenang
then
n:=cocokan(kolm,baris,-
1,+1,pemain)+cocokan(kolm,baris,+1,-1,pemain)-1; if n>=jmlblmenang then result:=true; end;
{************** Penurunan Bola *************} procedure TForm1.turunbola(x:integer); {Gerakan bola saat turun samapi selesai pada dasar dari kolom}
var kolm, baris, i:integer;
begin kolm:=x div(lbrbola+lbrpapan) ; bolawrn.left:=lbrpapan+(kolm)*(lbrbola+lbrpapan); baris:=0; while (baris<jmlbrs) and (papan[kolm,baris]=0) do inc(baris); if baris=0 then exit; dec(baris); with bolawrn do for i:=1 to baris+1 do begin top:=i*lbrbola; update; {menunjukkan gambar yang baru} sleep(100); end; papan[kolm,baris]:=pemainskrg; with image1.Canvas do
111
begin brush.color:=BolaWrn.brush.color; with
BolaWrn
do
ellipse(left,top,
left+width,
top+height); end; inc(jmlgerakan); gerakan[jmlgerakan]:=point(kolm,baris); if
(jmlgerakan=jmlkolm*jmlbrs)
or
deret4(kolm,baris)
then begin if deret4(kolm,baris) then begin if pemainskrg=1 then begin showmessage('BIRU
Menang!klik
Mulai
Baru
untuk
permainan baru'); skor_k := skor_k+1; Edit1.Text := IntToStr(skor_k); end else if pemainskrg=2 then begin showmessage('KUNING Menang!klik Mulai Baru untuk permainan baru'); skor_b := skor_b+1; Edit2.Text := IntToStr(skor_b); end else end else showmessage('Permainan Seri'); gameberakhir:=true; bolawrn.visible:=false;
112
end; end;
{*************** GERAKAN KEPADA KOLOM *************} procedure TForm1.Gerakantokolm(kolm:integer); {simulasi gerakkan tanda bola kepada kolom yang dipilih}
var
i:integer; halfc:integer;
begin grkbola:=true; halfc:=lbrbola div 2; for i:= 0 to kolm*(lbrbola+lbrpapan) div 10 do begin tandagerakMouse(self,[],HalfC+10,0);{simulasi gerakan bola= 10 pixels kekanan} bolawrn.update; sleep(10); end; grkbola:=false; end;
{***************** FormCloseQuery ***************} procedure
TForm1.FormCloseQuery(Sender:
TObject;
var
CanClose: Boolean);
{menghentikan
pemecahan
dibiarkan menutup} begin tag:=1; canclose:=true; end;
manapun
dan
aplikasi
yang
113
{***************** KEBERHASILAN ***************} function Tform1.skor(pemain:integer) : longint; {Hasil skor untuk "pemain" untuk yang sekarang di papan}
{Prosedur Lokal ******** Hitungan **************} function
hitungan(pemain:integer;
i,j,di,dj
:
longint) : longint; var c : longint; begin c := 0; while (i<jmlkolm) and (j<jmlbrs)and (i>=0) and (j>=0) and (papan[i,j]=pemain) and (c <jmlblmenang) do begin i := i+di; j := j+dj; inc(c); end; if c = jmlblmenang then hitungan := winnerval else hitungan := c; end;
{prosedur lokal ************ Perincian *************} function hitung(pemain:integer):longint;
{perhitungan tanda yang sejajar untuk setiap pemain} var i,j : longint; total : longint; begin
{hitungan}
total := 0;
114
for i := 0 to jmlkolm-1 do for j := 0 to jmlbrs-1 do if papan[i,j] = pemain then {mengecek 4 petunjuk} begin total
:=
total
+
hitungan(pemain,
i,j,0,1)
+
hitungan(pemain, i,j,1,0) + hitungan(pemain, i,j,1,1) + hitungan(pemain, i,j,1,-1); if total > winnerval then break; end; result := total; end; {hitungan}
var s:integer; begin {skor} s := hitung(pemain mod 2 +1);{mendapatkan jumlah untuk pemain yang lain} if s
>= winnerval then result := -winnerval
{pemain
berikutnya
yang
menang,
membuat skor yang buruk bagi kita} else result := hitung(pemain)-s;
{cara lainnya:
kita dikurang skorenya dia} end; {skor}
{****************ALGORITMA MINIMAX ************** } function tform1.Minimax(pemain, carilevel:integer; {$IFDEF DEBUG} Node:TTreeNode; {$ENDIF} grkterakhir:TPoint):integer; var nilai, temp:integer; i:integer; {$IFDEF DEBUG} nodebaru:TTreeNode; {$ENDIF}
skor
115
k,b:integer; pertama:boolean; menang:boolean; begin application.ProcessMessages; if (tag=1) or (not berpikir)
then begin result:=0;
exit; end; {user menginginkan untuk berhenti} menang:=Deret4(grkterakhir.x, grkterakhir.y); if
(carilevel>=lookahead)
or
menang
or
(jmlgerakan=totgerakan){papan terisi penuh} then begin {menghitung hasil dari daun ini} if carilevel=1 then ingatan:=grkterakhir.x; if menang then result:=-(winnerval-carilevel) {gerakan
terakhir
adalah
yang
menang untuk pemain lain, kita mendapat dapat hal yang besar negatifnya}
else result:=-skor(pemain)+carilevel; {$IFDEF DEBUG} debug.lihatTree.items.addchild(node,'Last Level:'
+inttostr(carilevel)
+'
skor:
'+inttostr(result)); $ENDIF} end else begin pertama:=true;
{untuk pertama kali melalui tombol}
nilai:=winnerval; for i := 0 to jmlkolm-1 do begin
116
k:=cobakolm[i];{barangkali
mencoba
kolom
dari
tengah ke arah tepi dibandingkan dari sebelah kiri ke kanan } if (bkbaris[k] >=0) and (tag=0) then
{ada satu baris yang terbuka baris didalam kolom ini dan berhenti bendera tidak berkumpul}
begin {membuat suatu percobaan gerak untuk mengevaluasi nilainya} b:=bkbaris[k]; papan[k,b] := pemain; dec(bkbaris[k]); {$IFDEF
DEBUG}nodebaru:=
debug.lihatTree.items.addchild(node,'Level:'+inttostr(car ilevel)+', kolm:'+inttostr(k+1)); {$ENDIF} begin {Knuth's "Negmax" minimax variation changes sign at each level} temp:= -Minimax(pemain mod 2+1, carilevel+1, {$IFDEF
DEBUG}
nodebaru,
{$ENDIF}
point(k,b)); if pertama then begin nilai:=temp; pertama:=false; {$IFDEF ',
DEBUG}
nodebaru.text:=nodebaru.text+
skor:'+inttostr(temp)
MinMax:'+inttostr(nilai); {$ENDIF}
+
',
New
117
if carilevel=1 then ingatan:=k; (*application.processmessages; if tag=1
then begin break{result:=nilai; exit;}
end; *) end else if nilai
DEBUG}nodebaru.text:=nodebaru.text+
', skor:'+inttostr(temp) + ', MinMax:'+inttostr(nilai); {$ENDIF} end {$IFDEF
DEBUG}else
nodebaru.text:=nodebaru.text+
',
skor:'+inttostr(temp)
+ ', MinMax: No change';; {$ENDIF} end; inc(bkbaris[k]);
{dan
menandai
baris
ketika
tersedia lagi} papan[k,bkbaris[k]]
:=
0;
{mengulang
dari
gerakan} end; end; result:=nilai; end; end;
{***************** ALGORITMA MINIMAX AB **************} function
tform1.MinimaxAB(pemain,
alpha, beta:integer;
carilevel:integer;
118
{$IFDEF DEBUG} Node:TTreeNode; {$ENDIF} grkterakhir:TPoint):integer; {mengevaluasi payoff untuk "pemain" dengan menggunakan alpha-beta pruning. KembaliKan dalam
pemberian
bidang
imbalan
seluruhnya
"
dan
menetapkan
ingatan"
untuk
kolom
tingkatan
di 1
pemanggil
var temp:integer; i:integer; {$IFDEF DEBUG} nodebaru:TTreeNode; {$ENDIF} k,b:integer; pertama:boolean; menang:boolean; begin application.processmessages; if tag=1 then begin result:=0; exit; end; menang:=Deret4(grkterakhir.x, grkterakhir.y);
{posisi
pemenang?} if
(carilevel>=lookahead)
or
menang
or
(jmlgerakan=totgerakan){papan terisi penuh} then begin if carilevel=1 then ingatan:=grkterakhir.x; if menang then result:=-(winnerval-carilevel) else result:=-(skor(pemain)-carilevel); {$IFDEF
DEBUG}
debug.lihatTree.items.addchild(node,'Leaf:'+inttostr(cari level) +' skor: '+inttostr(result)); {$ENDIF} end
119
else begin pertama:=true;
{first time through switch}
for i := 0 to jmlkolm-1 do begin k:=cobakolm[i]; if (bkbaris[k] >=0) and (tag=0) then begin {make a trial move to evaluate its nilai} b:=bkbaris[k]; papan[k,b] := pemain; dec(bkbaris[k]); {one less baris now available in this column} {$IFDEF
DEBUG}
nodebaru:=debug.lihatTree.items.addchild(node,'Level:' +inttostr(carilevel)+', kolm:'+inttostr(c+1)); {$ENDIF}
{Knuth's "Negmax" minimax variation changes sign at each level, alpha and beta swap roles at each level} temp:= -MinimaxAB(pemain mod 2+1, carilevel+1, beta, -alpha, {$IFDEF DEBUG} nodebaru, {$ENDIF} point(k,b)); if pertama then begin alpha:=temp; pertama:=false; {$IFDEF
DEBUG}
nodebaru.text:=nodebaru.text+
skor:'+inttostr(temp) MinMax:'+inttostr(alpha); {$ENDIF}
+
',
', New
120
if carilevel=1 then ingatan:=k; end else if temp>alpha then begin alpha:=temp; if carilevel=1 then ingatan:=k; {$IFDEF DEBUG}nodebaru.text:=nodebaru.text+ ', skor:'+inttostr(temp)+ ', MinMax:'+inttostr(alpha); {$ENDIF} end {$IFDEF DEBUG}else nodebaru.text:=nodebaru.text+ ', skor:'+inttostr(temp)+ ', MinMax: No change'; {$ELSE} ; {$ENDIF} {Mengulang gerakan} inc(bkbaris[k]); papan[k,bkbaris[k]] := 0;
if alpha>=beta then begin {$IFDEF DEBUG} nodebaru.text:=nodebaru.text+ ', Pruned: A='+ inttostr(alpha) + ', B='+inttostr(beta); {$ENDIF} break; end; end; end; result:=alpha; end; end;
121
function
TForm1.GerakanRandomMax:integer;
{Kembali ke nomor dari gerakan yang diacak bahwa pemain yang sekarang akan memulai start dari permainan - gerakan yang lebih diacak untuk lebih sulit}
{penerapan
untuk
menjaga
permainan
komputer
dari
yang
tepatnya dapat diulang} begin result:=gerakanmax[pemainskrg]; end;
{************* GERAKAN KOMPUTER BERMAIN **************} procedure tform1.gerakankomp;
{Program menemukan suatu gerakan dan mengerjakannya} var
halfc:integer;
begin halfc:=lbrbola div 2; berpikir:=true; gerakanusul; if (tag=0) and berpikir then begin lbltunjuk.caption:='Lawan Bergerak...'; lbltunjuk.update; Tandaturunmouse(image1,
mbLeft,
[],
halfc,0);
{simulasi mouse melepaskan bola kebawah} Tandanaikmouse(image1,mbleft,[],halfC,0); turun} application.processmessages; end;
{tanda
122
berpikir:=false; end;
{***************** Gerakan Usulan *************} procedure TForm1.gerakanusul; { prosedur minimax digunakan untuk melakukan perkiraan langkah berikutnya. dipanggil
oleh
tombol
usulan
dan
prosedur
gerakan
komputer} var i,j,peluangM:integer; {$IFDEF DEBUG}node:TTreenode;{$ENDIF} begin setlength(bkbaris,jmlkolm); if gameberakhir then initialize; tag:=0; {$IFDEF DEBUG} with debug do lihatTree.items.clear; {$ENDIF} screen.cursor:=crhourglass; bolabaru(lbrbola
div
2);
{menampilkan
gambar
baru} for i:=0 to jmlkolm-1 do begin bkbaris[i]:=-1; for j:=jmlbrs-1 downto 0 do if papan[i,j]=0 then begin bkbaris[i]:=j; break; end; end;
tanda
123
{$IFDEF
DEBUG}
node:=debug.LihatTree.items.add(nil,'Game
Tree
Root');
{$ENDIF}
lookahead:=lookaheads[pemainskrg]; peluangM:=gerakanrandomMax; if jmlgerakan div jmlpemain < peluangM then begin berpikir:=true; ingatan:=random(jmlkolm); end else begin if abpruning.checked then Minimaxab(pemainskrg,1,-maxint, maxint, {$IFDEF DEBUG} node, {$ENDIF} point(0,0)) else
Minimax(pemainskrg,1,{$IFDEF
DEBUG}
node,
{$ENDIF} point(0,0));//timer1.enabled:=false; end; if (tag=0) and (berpikir)
then gerakantokolm(ingatan);
screen.cursor:=crdefault; end;
{*********************************************} {
PROSEDUR DARI TOMBOL-TOMBOL
}
{*********************************************}
{************ Penggunaan Tombol Usulan *************} procedure TForm1.BtnUsulanClick(Sender: TObject); begin If berpikir then exit; berpikir:=true;
124
gerakanusul; berpikir:=false; end;
{*********** Penggunaan Tombol Mulai Baru ***********} procedure TForm1.BtnBaruClick(Sender: TObject); begin btnhenticlick(sender); Bolawrn.Enabled:=true; initialize; end;
{************* Penggunaan Tombol Berhenti ************} procedure TForm1.BtnHentiClick(Sender: TObject); begin tag:=0; lbltunjuk.caption:='Game
dihentikan,
Klik
Mulai
Baru
untuk permainan baru'; grkbola:=false; Gameberakhir:=true; berpikir:=false; Bolawrn.Enabled:=false; end;
{*********** Penggunaan Tombol Ulang Langkah **********} procedure TForm1.BtnUlangClick(Sender: TObject); {Take a move var
back}
L,T:integer;
begin if berpikir then exit; If jmlgerakan>0 then begin
125
with gerakan[jmlgerakan], image1.canvas do begin papan[x,y]:=0; brush.color:=clblack; L:=lbrpapan+(x)*(lbrbola+lbrpapan); T:=lbrbola*(y+1); fillrect(rect(L,T,L+lbrbola,T+lbrbola)); end; bolabaru(lbrbola div 2); dec(jmlgerakan); gameberakhir:=false; pilihpemain; end; end;
{***************** Penggunaan Pilihan IQ *************} procedure TForm1.IQGrpClick(Sender: TObject);
begin if sender=IqGrp1 then lookaheads[1]:=Setiq(IQGrp1.itemindex) else if sender=IQGrp2 then lookaheads[2]:=Setiq(IQGrp2.itemindex)
end;
{***************** Modul Menu PemainGrp ***************} procedure TForm1.PemainGrpClick(Sender: TObject);
var i:integer; begin
126
if pemaingrp.itemindex>=0 then {mengabaikan pengaturan kotak(index=-1)} with pemaingrp do begin i:=itemindex; if i=0 then begin jmlpemain:=2; IQgrp1.visible:=true; IQgrp2.visible:=true; BtnUsulan.enabled:=true; end else begin jmlpemain:=2; IQgrp1.visible:=true; IQgrp2.visible:=true; BtnUsulan.enabled:=true; end; initialize; end; end;
{************ Modul Mengantur Kolom ************} procedure TForm1.EditKolmChange(Sender: TObject); {pemain mengatur ukuran papan}
begin jmlkolm:=editkolm.value; initialize; end;
127
{************ Modul Mengatur Baris *************} procedure TForm1.EditBarisChange(Sender: TObject); {User mengubah ukuran papan} begin jmlbrs:=editbaris.Value; initialize; end;
{************ Modul Pilihan JmlBola *************} procedure TForm1.EditBolaChange(Sender: TObject); {Pemain mengubah jumlah bola sampai pada kemenangan}
begin jmlblmenang:=editbola.value; initialize; end;
{**************** Modul Mouse Turun *****************} procedure TForm1.TandaTurunMouse(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer); {Get ready to drag a chip} begin if gameberakhir or berpikir then exit; grkbola:=true; bolawrn.top:=0; bolabaru(bolawrn.left+x); end;
{**************** Modul Mouse Bergerak ****************} procedure TForm1.TandaGerakMouse(Sender: TObject; Shift: TShiftState; X,
128
Y: Integer); {pergeseran bola secara horizontal} begin if grkbola then bolabaru(bolawrn.left+x); end;
{**************** Modul Mouse Naik ********************} procedure TForm1.TandaNaikMouse(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer);
{Meletakan bola dalam
kolom baru dan mengecek apakah ada
kemungkinan untuk menjadi menang} begin if papan [(bolawrn.left+x) div (lbrbola+lbrpapan),0]<>0 then begin bolawrn.left:=0; exit; end; turunbola(bolawrn.left+x); grkbola:=false; pilihpemain; if (tag=0) and (not gameberakhir) then begin bolabaru(lbrbola div 2); if ( (pemainskrg=1) and ((pemaingrp.itemindex =2) or (pemaingrp.itemindex =3))) or ((pemainskrg=2)
and
(pemaingrp.itemindex=2))) then gerakankomp;
((pemaingrp.itemindex
=1)
or
129
end; end;
{procedure TForm1.Timer1Timer(Sender: TObject); begin inc(runtime); end; } {procedure TForm1.FormShow(Sender: TObject); begin IntroDlg.showmodal; end;}
procedure
TForm1.PetunjukPermainan1Click(Sender:
TObject); begin IntroDlg := TIntroDlg.Create(Self); IntroDlg.ShowModal; IntroDlg.Free; end;
procedure TForm1.TentangDeret41Click(Sender: TObject); begin Form2 := TForm2.Create(Self); Form2.ShowModal; Form2.Free; end;
procedure TForm1.FormShow(Sender: TObject); begin skor_k := 0; skor_b := 0;
130
Edit1.Text := '0'; Edit2.Text := '0'; end; end.
