ANALISIS PENGGUNAAN ALGORITMA GREEDY PADA PERMAINAN CATUR

ANALISIS PENGGUNAAN ALGORITMA GREEDY PADA PERMAINAN CATUR Ginonggom1, Marlindawati2, Ari Muzakir3 Program Studi Teknik Informatika, Fakultas Ilmu Komputer, Universitas Bina Darma Palembang, Indonesia E-mail : [email protected], [email protected], [email protected]

Abstract : Greedy algorithm is one of the algorithms used to solve optimization problems, which in essence is to take the best option available at each stage of a process . The game of chess is a popular sport that is a simulation -based educational game designed to simulate a strategy . In this stimulating researchers to apply artificial intelligence or artificial intelligence ( AI ), which is an area of research , application and instructions related to programming the computer to do something intelligent . This study will discuss the results of applying greedy algorithm to determine the next step . The study discusses about the game of chess . This research also covers the basic principles greedy algorithm , greedy algorithm implementation on chess can be used for computer artificial intelligence to determine priorities for checks on the 6th chess . Key Word : Chess games , Greedy Algorithms , Artificial Intelligence. Abstrak : Algoritma greedy adalah salah satu algoritma yang digunakan untuk menyelesaikan masalah optimasi, yang intinya adalah mengambil pilihan terbaik yang ada pada setiap tahap dalam suatu proses. Permainan catur adalah sebuah cabang olahraga yang populer yang merupakan game edukasi berbasis simulasi yang didesain untuk mensimulasikan sebuah strategi. Dalam menstimulasi ini peneliti menerapkan kecerdasan buatan atau Artificial Intelligence (AI) yang merupakan kawasan penelitian, aplikasi dan instruksi yang terkait dengan pemrograman komputer untuk melakukan sesuatu hal yang cerdas. Penelitian ini akan membahas hasil penerapan algoritma greedy untuk menentukan langkah kedepan. Penelitian membahas tentang permainan catur. Dalam penelitian ini juga membahas prinsip dasar algoritma greedy, penerapan algoritma greedy pada permainan catur dapat dimanfaatkan untuk kecerdasan buatan komputer dengan menentukan prioritas untuk melakukan pengecekan pada 6 bidak catur.

Kata kunci: Permainan Catur, Algoritma Greedy, Artificial Intelligence Permainan catur merupakan salah satu jenis permainan olahraga yang mengasah otak yang telah menjadi olahraga yang sangat popular di Indonesia dan dunia. Permainan catur merupakan permainan olahraga yang menggunakan taktik dan strategi. Permainan catur ini merupakan game edukasi berbasis simulasi yang didesain untuk mensimulasikan sebuah strategi. Dalam menstimulasi ini peneliti menerapkan kecerdasan buatan atau Artificial Intelligence (AI) yang merupakan kawasan penelitian, aplikasi dan instruksi yang terkait dengan pemrograman komputer untuk melakukan sesuatu hal yang cerdas.

1. PENDAHULUAN Game adalah permainan yang menggunakan media elektronik, merupakan sebuah hiburan berbentuk multimedia yang dibuat semenarik mungkin agar pemain bisa mendapatkan sesuatu sehingga adanya kepuasan batin. Dengan adanya game ini diharapkan dapat berguna bagi edukasi. Pada zaman sekarang perkembangan game semakin meningkat pesat dan populer seiring dengan majunya perkembangan teknologi informasi. Dengan perkembangan teknologi ini banyak permainan yang biasa dilakukan secara konvensional mulai diterapkan diperangkat teknologi seperti laptop, smartphone dan tablet, salah satu permainan ini yaitu permainan catur.

Masalah optimasi merupakan hal yang sering kita jumpai dalam pekerjaan sehari-hari. Menyelesaikan masalah 1

Grounded research merupakan lawan dari penelitian secara verifikasi. Metode penelitian yang dicetuskan oleh Glaser dan Strauss (Nazir, 2005:74) ini merupakan suatu metode yang mendasarkan diri pada fakta dan menggunakan analisis perbandingan yang bertujuan untuk mengadakan generalisasi empiris, menetapkan konsep-konsep, membuktikan teori dan mengembangkan teori dimana pengumpulan data dan analisis data berjalan pada waktu yang bersamaan. Data yang diperoleh dapat dibandingkan melalui kategori-kategori. Nazir (2005: 75) menyatakan, tujuan dari grounded research adalah untuk mengadakan generalisasi empiris, menetapkan konsep-konsep, membuktikan teori, dan mengembangkan teori. Penelitian bertujuan untuk menspesifikasikan konsep. Akan menjelaskan unsur-unsur baru khas dari kasus yang sedang dipelajari. Ciri yang paling pokok dari grounded research adalah menggunakan data sebagai sumber teori, sehingga teori yang dibangun berdasarkan logika tidak ada tempatnya dalam penganut grounded research.

optimasi ini dapat dilakukan dengan berbagai macam strategi, diantaranya adalah menggunakan algoritma greedy. Algoritma greedy adalah algoritma yang paling populer diantara strategi algoritma yang lainnya, dikarenakan kesederhanaannya dan kemudahan penerapannya. Strategi algoritma greedy sering digunakan karena berguna untuk menghasilkan solusi yang menghampiri optimum. Dengan mengambil solusi optimum lokal pada setiap langkah, diharapkan dari solusi optimum lokal tersebut didapatkan solusi global (solusi akhir) yang optimum. Analisis performansi algoritma dilakukan agar diketahui efisiensi dan kelayakan algoritma pada kasus yang sedang diuji. Tanpa dilakukannya analisis algoritma maka akan terjadi masalah terhadap pengimplementasian algoritma pada kebutuhan dan masalah yang dihadapi. Algoritma yang akan digunakan diharapkan tepat dan cocok. Berdasarkan uraian diatas, maka penulis tertarik untuk melakukan penelitian untuk menganalisa penggunaan algoritma greedy terhadap permasalahan tersebut dengan mengajukan judul skripsi “Analisis Penggunaan Algoritma Greedy Pada Permainan Catur” yang digunakan untuk memberikan masukkan dan informasi mengenai penggunaan algoritma greedy.

Gambar 1 Metode Grounded Research

2. METODOLOGI PENELITIAN

Dasar analisis dari grounded research adalah sifat-sifat yang ditemukan, untuk kemudian dikelompokkan berdasarkan kategori. Kategori dalam pengertian grounded research adalah k onsep-konsep melalui mana data dapat diperbandingkan. Adapun langkah-langkah Grounded Research yang harus dilaksanakan adalah sebagai berikut: 1. Menentukan masalah yang ingin diteliti 2. Mengumpulkan data untuk memperoleh data yang sesuai dengan penelitian. 3. Kajilah pertanyaan-pertanyaan 4. Menganalisis dan menjelaskan data 5. Membuat laporan penelitian

Metode penelitian merupakan suatu cara yang dapat digunakan untuk mencapai tujuan yang diharapkan melalui suatu penelitian dengan teknik-teknik dan alat-alat tertentu. Metode penelitian merupakan suatu cara yang dapat digunakan untuk mencapai tujuan yang diharapkan melalui suatu penelitian dengan teknik-teknik dan alat-alat tertentu. Adapun metode yang digunakan dalam penelitian ini yaitu metode development research suatu kegiatan penelitian yang bertujuan dan berusaha mengembangkan atau melengkapi pengetahuan yang sudah ada atau diketahui. Permasalahan manusia dan lingkungan alamnya selalu berkembang yang kesemuanya ini harus memperoleh jawaban yang simbang (Supardi, 2005 : 25).

2.1 Metode Pengambilan Data Dalam pengumpulan data untuk penelitian ini, digunakan beberapa cara yaitu: 2

saat ini manusia dapat mengerjakannya dengan baik (E.Rich, 1983). Tujuan dari kecerdasan buatan menurut Winston dan Prendergast : 1. Membuat mesin menjadi lebih pintar (tujuan utama) 2. Memahami apa itu kecerdasan (tujuan ilmiah) 3. Membuat mesin lebih bermanfaat (tujuan entrepreneurial) Dua bagian utama yang dibutuhkan untuk aplikasi kecerdasarn buatan adalah : a. Basis Pengetahuan (Khowledge Base) berisi fakta-fakta, teori, pemikiran dan hubungan antara satu dengan lainnya. b. Motor Inferensi (Inference Engine) adalah kemampuan menarik kesimpulan berdasarkan pengalaman.

1). Kepustakaan Mengumpulkan data dengan cara mencari dan mempelajari data-data dari buku-buku ataupun dari referensi lain yang berhubungan dengan penulisan laporan penelitian proposal. Buku yang digunakan penulis sebagai referensi, adapun metode yang digunakan penulis dalam merancang dan mengembangkan dapat dilihat pada daftar pustaka. 2). Observasi Metode ini dilakukan dengan cara mengamati langsung keadaan dan kegiatan dalam permainan catur sebagai objek guna mendapatkan keterangan yang akurat.

2.2 Tinjauan Pustaka

2.2.3 Algoritma Greedy Algoritma Greedy adalah salah satu algoritma yang membentuk solusi langkah per langkah. Ada banyak langkah yang harus dieksplorasi pada setiap solusinya. Oleh karena itu, pada setiap langkah harus mengambil keputusan yang terbaik dari setiap pilihan. Dan keputusan yang telah diambil tidak dapat diubah lagi pada langkah selanjutnya. Pendekatan algoritma greedy adalah mengambil keputusan yang tampaknya terbaik. Dengan mengambil solusi optimum lokal pada setiap langkah, diharapkan dari solusi optimum lokal tersebut didapatkan solusi global (solusi akhir) yang optimum. Algoritma greedy adalah algoritma yang memecahkan masalah langkah per langkah dengan mengambil pilihan yang terbaik yang dapat diperoleh saat itu tana memperhatikan konsekuensi ke depan, prinsip dari algoritma ini adalah “take the best what you can get now!”. Dan berharap bahwa dengan memilih solusi optimum lokal pada setiap langkah akan berakhir dengan optimum global. Elemen-elemen dalam persoalan optimasi algoritma greedy : 1. Himpunan kandidat, C. Himpunan ini berisi elemen pembentuk solusi. 2. Himpunan solusi, S. Berisi kandidat yang terpilih sebagai solusi persoalan. Dengan kata lain, himpunan solusi adalah himpunan bagian dari setiap himpunan kandidat.

2.2.1 Analisis Menurut Kamus Besar Bahasa Indonesia (2002:43), Analisis adalah penguraian suatu pokok atau berbagai bagiannya dan penelaahan bagian itu sendiri serta hubungan antar bagian untuk memperoleh pengertian yang tepat dan pemahaman arti keseluruhan. Menurut Komaruddin (2001:53), Analisis adalah kegiatan berfikir untuk menguraikan suatu keselundian menjadi komponen sehingga dapat mengenal tandatanda komponen, hubungannya, satu sama lain dan fungsi masing-masing dalam satu keseluruhan yang terpadu. Dari penjelasan antara analisa dan analis penulis dapat menarik kesimpulan bahwa seseorang yang memilliki kemampuan, melakukan sebuah penelitian mengenai suatu peristiwa untuk dapat mengetahui keadaan yang sebenarnya dengan tujuan dapat menjadi ilmu atau suatu pengetahuan baru. 2.2.2 Artificial Intelligence Definisi Artificial Intelligence yang terkenal adalah tindakan mesin yang apabila dilakukan oleh manusia disebut kecerdasan atau intelligence (Efraim Turban, 1992). Definisi lain tentang Artificial Intelligence merupakan ilmu yang mempelajari bagaimana cara membuat komputer dapat melakukan pekerjaan-pekerjaan yang untuk 3

3.

4.

5.

Fungsi seleksi Fungsi yang pada setiap langkah memilih pilihan paling memungkinkan mencapai solusi yang paling optimal. Pilihan yang sudah dipilih, tidak pernah dipertimbangkan lagi pada masalah selanjutnya. Biasanya setiap kandidat x menunjuk sebuah nilai numerik, dan fungsi seleksi memilih x yang mempunyai nilai terbesar atau memilih nilai x yang memiliki nilai terkecil. Fungsi kelayakan Fungsi yang memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak, yakni kandidat tersebut bersama-sama dengan himpunan solusi yang sudah terbentuk dan tidak melanggar kendala yang ada. Kandidat yang layak dimasukkan ke dalam himpunan solusi, sedangkan kandidat yang tidak layak dibuang dan tidak pernah dipertimbangkan lagi. Fungsi objektif Fungsi yang memaksimumkan atau meminimumkan nilai solusi. Dengan kata lain, persoalan optimasi yang diselesaikan dalam algoritma greedy melibatkan pencarian sebuah himpunan bagian S, dari himpunan kandidat C, yang dalam hal ini, S harus memenuhi beberapa kriteria yang ditentukan, yaitu menyatakan suatu solusi dan S dioptimasi oleh fungsi objektif. Secara umum, skema algoritma greedy dirumuskan: a. Inisialisasi S dengan kosong b. Pilih kandidat dari C (dengan fungsi seleksi). c. Kurangi c dengan kandidat yang sudah dipilih dari langkah 2. d. Periksa apakah kandidat yang dipilih tersebut bersama-sama dengan himpunan solusi membentuk solusi yang layak. Jika ya, masukan kandidat tersebut kedalam himpunan solusi; jika tidak, buang kandidat tersebut dan tidak perlu dipertimbangkan lagi. e. Periksa apakah himpunan solusi sudah memberikan solusi yang lengkap dengan menggunakan fungsi solusi. Jika ya, berhenti; jika tidak, ulangi langkah 2. Algoritma greedy tidak selalu memberikan solusi yang optimal pada setiap

masalah. Namun pada beberapa permasalahan optimasi, algoritma greedy terbukti selalu memberikan solusi yang optimal contohnya: pengaturan jadwal, permasalahan knapsack yang fraksional, dan lainlain. 2.2.4 Permainan Catur Menurut Magethi (2009:12), permainan catur merupakan permainan di atas papan berisi 8 x 8 petak atau 64 petak ini berasal dari India sejak 500 Masehi, kemudian menyebar ke Persia dan masyarakat Arab. Chess atau catur menyebar ke Eropa ketika kekuasaan Islam pada awal abad pertengahan memasuki Eropa dari selatan Spanyol. Bentuk buah catur sempat berubah. Awalnya bentuk buah catur mirip manusia, kini berubah menjadi abstrak. Ketika memasuki Eropa, buah catur kembali mengambil bentuk menyerupai manusia. Buah-buah catur mewakili sejumlah golongan pada abad pertengahan yaitu : 1. Buah Pion mewakili budak yang kala itu selalu mengorbankan jiwa dan raga. 2. Buah Benteng mewakili rumah dan tempat berlindung. 3. Buah Kuda mewakili ksatria yang senantiasa melindungi negara. 4. Buah Peluncur mewakili gereja yang menjadi lambang keagamaan di abad pertengahan. 5. Buah Ratu atau Ster mewakili Ratu yang merupakan wanita paling berkuasa pada masa itu. 6. Buah Raja mewakili Raja yang merupakan pucuk pimpinan dan menentukan kalah menang pertarungan. Catur dimainkan dua orang. Masingmasing pemain memegang buah catur putih melawan buah catur hitam. Yang menjadi pemenang dalam catur adalah pemain yang berhasil men-skak (membuat Raja tidak bisa melangkah kemana pun) atau mematikan Raja. Masing-masing buah catur memiliki pola pergerakan yang berbeda. Pion hanya boleh berjalan satu kotak ke depan, kecuali langkah pertamanya, boleh dua kotak ke depan. Pion tidak boleh jalan mundur, namun Pion memakan musuhnya dengan langkah diagonal kiri atau kanan. Benteng berjalan lurus secara vertikal dan horizontal, 4

sementara Menteri atau Peluncur berjalan maju mundur secara diagonal sesuai warna petak. Cara jalan Ratu merupakan kombinasi cara jalan Benteng dan Menteri. Kuda bisa melompati halangan di depannya, asalkan alur jalannya menyerupai huruf “L” sebanyak 4 kotak. Untuk Raja bisa berjalan ke segala arah sebanyak satu kotak.

masing-masing pihak, yang disusun berbaris secara khusus pada masing-masing sisi papan catur secara berhadap-hadapan. Satu buah hanya bisa menempati satu petak. Pada bagian terdepan masing-masing barisan terdapat 8 pion, diikuti di belakangnya dua benteng, dua kuda (dalam bahasa Inggris disebut knight-ksatria), dua gajah (dalam bahasa Inggris disebut bishop-uskup), satu menteri atau ratu atau ster, serta satu raja.

2.2.5 Ketentuan Permainan Catur Permainan dilangsungkan di atas papan yang terdiri dari 8 kolom dan 8 baris kotak atau petak berwarna hitam dan putih (terang dan gelap) secara berselang seling. Permainan dimulai dengan 16 buah pada masing-masing pihak, yang disusun berbaris secara khusus pada masing-masing sisi papan catur secara berhadap-hadapan. Satu buah hanya bisa menempati satu petak. Pada bagian terdepan masing-masing barisan terdapat 8 Pion, diikuti di belakangnya dua Benteng, dua Kuda (dalam bahasa Inggris disebut knight atau ksatria), dua Menteri atau Peluncur (dalam bahasa Inggris disebut bishop atau uskup), Ratu atau ster, serta satu Raja. (Magethi, 2009:25).

3.1.3 Gerakan

Mulai

Inisialisasi Papan Catur

Beri label pada buah catur

Menghapus dari daftar inisialisasi buah catur

Beri label pada papan catur

Tidak Menghapus dari daftar inisialisasi papan catur Menentukan jarak sementara antara bidak dan papan catur Mencari titik terpendek berikutnya dengan membandingkan jarak bidak dan papan catur yang telah memiliki label permanen

Apakah Ada?

3. LANDASAN TEORI

Ya

3.1 Percobaan Awal

Selesai

3.1.1 Pengamatan Fenomena

Gambar 2 Flowchart Gerakan Catur

Catur adalah permainan pikiran yang dimainkan oleh dua orang. Pecatur adalah orang yang memainkan catur, baik dalam pertandingan satu lawan satu maupun satu melawan banyak orang (dalam keadaan informal). Sebelum bertanding, pecatur memilih biji catur yang akan ia mainkan. Terdapat dua warna yang membedakan bidak atau biji catur, yaitu hitam dan putih. Pemegang buah putih memulai langkah pertama, yang selanjutnya diikuti oleh pemegang buah hitam secara bergantian sampai permainan selesai.

Permainan dilangsungkan di atas papan yang terdiri dari 8 lajur dan 8 baris kotak/petak berwarna hitam dan putih (atau terang dan gelap) secara berselang seling. Permainan dimulai dengan 16 buah pada masing-masing pihak, yang disusun berbaris secara khusus pada masing-masing sisi papan catur secara berhadap-hadapan. Satu buah hanya bisa menempati satu petak. Pada bagian terdepan masing-masing barisan terdapat 8 pion, diikuti di belakangnya dua benteng, dua kuda (dalam bahasa Inggris disebut knight-ksatria), dua gajah (dalam bahasa Inggris disebut bishop-uskup), satu menteri atau ratu atau ster, serta satu raja.

3.1.2 Pengaturan Permainan dilangsungkan di atas papan yang terdiri dari 8 lajur dan 8 baris kotak/petak berwarna hitam dan putih (atau terang dan gelap) secara berselang seling. Permainan dimulai dengan 16 buah pada

3.1.2 Rokade Rokade (dalam bahasa Inggris, castling) merupakan gerakan khusus dalam 5

catur di mana Raja bergerak dua petak menuju Benteng di baris pertamanya, kemudian meletakkan Benteng pada petak terakhir yang dilalui Raja. Persyaratan rokade adalah sebagai berikut: a. Bidak Raja dan Benteng yang akan dilibatkan dalam rokade harus belum pernah bergerak. b. Tidak ada bidak lain di antara Raja dan Benteng. c. Raja tidak sedang di-skak, dan petakpetak yang dilalui Raja tidak sedang diserang oleh bidak lawan. Hal-hal berikut ini merupakan kesalah pengertian dalam rokade, yang semestinya tidak berlaku: a. Bidak benteng yang terlibat rokade sedang diserang Jika benteng yang dilibatkan berada di sisi Ratu, petak yang berada persis di samping Benteng tersebut tidak boleh dalam serangan

strategi memindahkan raja kekanan, kekiri atau kedepan “(arrayP[i] 0, untuk i =1..16)” dan himpunan solusi, S adalah salah satu dari himpunan kandidat (arrayP[i] yang dapat memberikan solusi maksimal). 3.1.3 En passant Ketika pion bergerak dua petak maju dan ada pion lawan yang berada satu petak dalam baris tujuan, maka pion lawan dapat menangkap dan menempati petak yang baru saja dilalui pion tersebut (seolah-olah pion tersebut bergerak satu petak maju). Namun, gerakan ini hanya dapat dilakukan sesaat setelah gerakan pion maju dua petak, atau hak lawan untuk melakukan gerakan en passant ini hilang. Mulai

Inisialisasi En Passant

Mulai

Beri label pada bidak raja dan benteng


Inisialisasi Rokade

Beri label pada bidak pion



Tidak Menghapus dari daftar inisialisasi papan catur


Menentukan Bidak dan pergerakan

Tidak Menghapus dari daftar inisialisasi papan catur Menentukan Bidak dan pergerakan

Melaukan proses Enpassent

Melaukan proses rokade

Apakah Ada? Apakah Ada?

Ya Ya

Selesai

Selesai

Gambar 3 Flowchart Rokade

Gambar 4 Flowchart En passant Berikut ini Algoritma Greedy pada proses En passant yaitu : 1. Prioritas pertama : pion kedepan 1 langkah. Menggerakkan pion kedepan 1 langkah. 2. Prioritas kedua : pion kedepan 2 langkah. Menggerakkan pion kedepan 2 langkah. Bila tidak terdapat pilihan strategi yang memberikan solusi prioritas pertama dan kedua. Maka jalankan prioritas ketiga yaitu langkah untuk mengatur strategi posisi diam. “(arrayP[i] 0, untuk i =1..16)”. dan himpunan solusi, S adalah salah satu dari himpunan kandidat (arrayP[i] yang dapat memberikan solusi maksimal).

Berikut ini Algoritma Greedy pada proses Rokade yaitu : 1. Prioritas pertama : memilih posisi yang dapat melakukan rokade. Menggerakkan Raja kesamping untuk melakukan pertukaran dengan benteng samping kanan. 2. Prioritas kedua : memilih posisi yang dapat melakukan rokade. Menggerakkan Raja kesamping untuk melakukan pertukaran dengan benteng samping kiri. 3. Bila tidak terdapat pilihan strategi yang memberikan solusi prioritas pertama dan kedua. Maka jalankan prioritas ketiga yaitu langkah untuk mengatur 6

Berikut ini beberapa buah catur yang terdiri dari buah catur hitam dan buah catur putih : 1. Pion Pion adalah salah satu dari enam bidak catur. Dalam seluruh buah catur, terdapat masing-masing delapan pion yang warnanya putih dan hitam, ditempatkan di garis depan dari bidak lainnya. Pion hanya bisa berjalan selangkah ke depan, yang berarti ke arah barisan lawan, dan tidak menyerang bidak lawan dalam arah ini. Dalam langkah pertama, pion dapat maju 2 kotak dan tidak ada yang menghambat jalan ini. Untuk memakan, pion harus mengambil arah diagonal sekali. Di samping itu, pion dapat menyerang menurut gerakan khusus en passant atau menyilang. Ketika pion mencapai kotak terakhir di sisi lawan, pion dapat memilih bidak yang sudah lebih dulu dimatikan lawan, kecuali raja. Pada tahun 1700-an, pecatur Prancis Andre Philidor menyebut pion sebagai 'jiwa permainan catur'. Ia menyadari bahwa meskipun Pion memiliki kemampuan terbatas, pion sering dapat menentukan sifat dan hasil permainan. Pion juga memiliki kemampuan promosi. Bila ia dapat mencapai baris terakhir dari lawan, maka ia dapat berubah sesuai yang

3.1.4 Skak Ketika Raja sedang diserang oleh satu atau lebih bidak lawan, keadaan ini disebut dengan skak. Pemain yang Rajanya diskak harus menggerakkan Rajanya supaya tidak terserang. Hal ini dapat dilakukan dengan menangkap bidak lawan yang menyerang, menutup serangan lawan dengan menempatkan sebuah bidak di antaranya (apabila yang menyerang Ratu, Benteng, atau Gajah dan ada petak kosong di antara Raja dan bidak lawan), atau memindahkan Raja ke petak yang tidak sedang diserang. Rokade tidak diijinkan apabila Raja sedang diskak.

Mulai

Beri label pada bidak Raja


Inisialisasi Skak


Tidak Menghapus dari daftar inisialisasi papan catur Menentukan Bidak dan posisi skak

Melaukan proses Skak

dinginkan oleh pemain. Apakah Ada?

Ya

Selesai

Gambar 5 Flowchart Skak Berikut ini Algoritma Greedy pada proses Skak yaitu : 1. Prioritas pertama : menggerakkan raja. Menggerakkan raja supaya tidak dimakan. 2. Prioritas kedua : menutup serangan. Menggerakkan pion kedepan 2 langkah. Bila tidak terdapat pilihan menangkap bidak lawan. Maka jalankan prioritas ketiga yaitu langkah untuk menangkap bidak lawan. “(arrayP[i] 0, untuk i =1..16)”. dan himpunan solusi, S adalah salah satu dari himpunan kandidat (arrayP[i] yang dapat memberikan solusi maksimal).

Gambar 6 Buah Pion

3.1.5 Buah Catur

7

Mulai Beri label pada pion

Inisialisasi Pion




Gambar 8 Buah Kuda

Menentukan jarak sementara antara bidak dan papan catur Mencari titik terpendek berikutnya dengan membandingkan jarak bidak dan papan catur yang telah memiliki label permanen

Mulai Beri label pada Kuda

Inisialisasi Kuda

Apakah Ada?


Ya Beri label pada papan catur

Selesai


Gambar 7 Flowchart Pion Berikut ini Algoritma Greedy pada Bidak Pion yaitu : 1. Prioritas pertama : Maju 1 langkah. Menggerakkan bidak pion untuk maju 1 langkah. 2. Prioritas kedua : Maju 2 langkah. Menggerakkan bidak pion untuk maju 2 langkah. 3. Prioritas ketiga : menangkap lawan. Menggerakkan bidak pion menangkap lawan. 4. Prioritas keempat : promosi. Menggerakkan bidak pion sampai di area lawan. Bila tidak terdapat pilihan strategi yang memberikan solusi prioritas pertama, kedua, ketiga dan keempat. Maka jalankan prioritas kelima yaitu langkah untuk mengatur strategi posisi diam. “(arrayP[i] 0, untuk i =1..16)”. dan himpunan solusi, S adalah salah satu dari himpunan kandidat (arrayP[i] yang dapat memberikan solusi maksimal).


Apakah Ada?

Ya

Selesai

Gambar 9 Flowchart Kuda Ratu Ratu atau menteri dalam catur adalah buah catur yang paling kuat. Ratu dapat bergerak baik vertikal, horisontal ataupun diagonal ke segala arah. Pada awal permainan masing masing pemain memiliki satu buah ratu yang terletak di samping raja. Ratu putih terletak di kotak putih, dan ratu hitam terletak di kotak hitam. 3.

2.

Kuda Kuda adalah buah catur yang memiliki gerak unik dengan membentuk huruf (L), baik ketika bergerak maupun ketika menangkap buah catur lawan. Pada awal permainan catur, setiap pemain memiliki dua buah kuda disebelah posisi Benteng (catur).

Gambar 10 Buah Ratu

8

4.

Gajah Gajah adalah salah satu jenis bidak catur dalam permainan papan catur. Tiap pemain memulai permainan dengan dua gajah. Satu gajah diletakkan di antara kuda raja dan raja. sedangkan gajah lainnya diletakkan di antara kuda ratu dan ratu. Dalam notasi aljabar, kotak awal untuk gajah putih adalah c1 dan f1, sedangkan untuk gajah hitam adalah c8 dan f8. Istilah "gajah" telah dipakai dalam permainan catur kuna. Dalam permainan catur kuna Persia, bidak yang bergerak semacam ini dinamakan fil ("gajah"). Dalam bahasa Rusia bidak ini dinamakan слон (slon), "gajah". Dalam bahasa Inggris bidak ini disebut sebagai Bishop ("uskup") dan dalam bahasa Belanda disebut sebagai loper ("pelari", "kurir", "utusan").

Mulai Beri label pada Ratu


Inisialisasi Ratu



Apakah Ada?

Ya

Selesai

Gambar 11 Flowchart Ratu Berikut ini Algoritma Greedy pada Ratu yaitu : 1. Prioritas pertama : Maju kedepan. Menggerakkan bidak ratu untuk maju kedepan. 2. Prioritas kedua : Mundur kebelakang. Menggerakkan bidak ratu untuk mundur. 3. Prioritas ketiga : Maju samping kiri. Menggerakkan bidak ratu untuk maju samping kiri. 4. Prioritas keempat : Maju samping kanan. Menggerakkan bidak pion untuk langkah samping kanan. 5. Prioritas kelima : Mundur kebelakang kiri. Menggerakkan bidak ratu untuk mundur samping kiri. 6. Prioritas keenam : Mundur kebelakang kanan. Menggerakkan bidak untuk mundur samping kanan. 7. Prioritas ketujuh : Menangkap Lawan. Menggerakkan bidak Ratu untuk menangkap lawan. Bila tidak terdapat pilihan strategi yang memberikan solusi prioritas pertama, kedua, ketiga dan keempat, kelima, keenam dan ketujuh. Maka jalankan prioritas kedelapan yaitu langkah untuk mengatur strategi posisi diam. “(arrayP[i] 0, untuk i =1..16)”. dan himpunan solusi, S adalah salah satu dari himpunan kandidat (arrayP[i] yang dapat memberikan solusi maksimal).

Gambar 12 Buah Gajah Mulai Beri label pada Gajah


Inisialisasi Gajah



Apakah Ada?

Ya

Selesai

Gambar 13 Flowchart Gajah Berikut ini Algoritma Greedy pada Gajah yaitu : 9

1.

Prioritas Kesatu : Maju samping kiri. Menggerakkan bidak gajah untuk maju samping kiri. 2. Prioritas Kedua : Maju samping kanan. Menggerakkan bidak gajah untuk maju samping kanan. 3. Prioritas Ketiga : Mundur kebelakang kiri. Menggerakkan bidak gajah untuk mundur samping kiri. 4. Prioritas Keempat : Mundur kebelakang kanan. Menggerakkan bidak gajah untuk mundur samping kanan. 5. Prioritas Kelima : Menangkap Lawan. Menggerakkan bidak gajah untuk menangkap lawan. Bila tidak terdapat pilihan strategi yang memberikan solusi prioritas pertama, kedua, ketiga dan keempat, kelima, keenam dan ketujuh. Maka jalankan prioritas kedelapan yaitu langkah untuk mengatur strategi posisi diam. “(arrayP[i] 0, untuk i =1..16)”. dan himpunan solusi, S adalah salah satu dari himpunan kandidat (arrayP[i] yang dapat memberikan solusi maksimal).

Mulai

Inisialisasi Benteng

Beri label pada Benteng




Apakah Ada?

Ya

Selesai

Gambar 15 Flowchart Benteng Berikut ini Algoritma Greedy pada Benteng yaitu : 1. Prioritas pertama : Maju kedepan. Menggerakkan bidak benteng untuk maju kedepan. 2. Prioritas kedua : Mundur kebelakang. Menggerakkan bidak benteng untuk mundur. 3. Prioritas ketiga : samping kiri. Menggerakkan bidak benteng untuk maju samping kiri. 4. Prioritas keempat : samping kanan. Menggerakkan bidak benteng untuk maju samping kanan. 5. Prioritas kelima : Menangkap Lawan. Menggerakkan bidak benteng untuk menangkap lawan. Bila tidak terdapat pilihan strategi yang memberikan solusi prioritas pertama, kedua, ketiga dan keempat dan kelima. Maka jalankan prioritas keenam yaitu langkah untuk mengatur strategi posisi diam. “(arrayP[i] 0, untuk i =1..16)”. dan himpunan solusi, S adalah salah satu dari himpunan kandidat (arrayP[i] yang dapat memberikan solusi maksimal).

5.

Benteng Benteng adalah bidak catur yang memiliki gerak lurus, baik ketika bergerak maupun ketika menangkap buah catur lawan. Benteng memiliki gerakan istimewa, yaitu rokade. Setiap pemain catur memiliki dua benteng di setiap sudut permainan ketika memulai bermain. Pada awal permainan benteng tidak dapat bergerak karena terhalangi buah catur lainnya. Benteng baru dapat bergerak ketika medan permainan sudah terbuka. Benteng bisa melangkah lurus sepanjang baris dan lajur di papan kecuali bila ada buah catur lain yang menghalanginya. Benteng tidak dapat melompati buah catur lainnya kecuali saat melakukan rokade.

6.

Raja

Raja adalah buah catur yang paling berharga. Permainan akan berakhir apabila raja dalam posisi di serang dan tidak ada Gambar 14 Buah Gajah

jalan untuk membebaskannya. 10

untuk mundur 1 langkah samping kanan. 7. Prioritas ketujuh : Menangkap Lawan. Menggerakkan bidak raja untuk menangkap lawan. Bila tidak terdapat pilihan strategi yang memberikan solusi prioritas pertama, kedua, ketiga dan keempat, kelima, keenam dan ketujuh. Maka jalankan prioritas kedelapan yaitu langkah untuk mengatur strategi posisi diam. “(arrayP[i] 0, untuk i =1..16)”. dan himpunan solusi, S adalah salah satu dari himpunan kandidat (arrayP[i] yang dapat memberikan solusi maksimal).

Gambar 16 Buah Raja Mulai Beri label pada Raja


Inisialisasi Raja

4. HASIL 4.1


Hasil


Setelah melakukan analisa algoritma greedy maka hasil yang dicapai oleh penulis adalah penerapan algoritma greedy pada 6 bidak catur yang dapat diterapkan pada studi kasus permainan catur, sehingga menghasilkan sebuah artificial inteligence, adapun prioritas tersebut sebagai berkut ini :


Apakah Ada?

Ya

Selesai

1. Gambar 15 Flowchart Raja Berikut ini Algoritma Greedy pada Raja yaitu : 1. Prioritas pertama : Maju 1 langkah kedepan. Menggerakkan bidak raja untuk maju 1 langkah kedepan. 2. Prioritas kedua : Mundur 1 langkah kebelakang. Menggerakkan bidak raja untuk mundur 1 langkah. 3. Prioritas ketiga : Maju 1 langkah samping kiri. Menggerakkan bidak raja untuk maju 1 langkah samping kiri. 4. Prioritas keempat : Maju 1 langkah samping kanan. Menggerakkan bidak raja untuk maju 1 langkah samping kanan. 5. Prioritas kelima : Mundur 1 langkah kebelakang kiri. Menggerakkan bidak raja untuk mundur 1 langkah samping kiri. 6. Prioritas keenam : Mundur 1 langkah kebelakang kanan. Menggerakkan bidak

2. 3. 4.

5.

6. 7. 8.

11

Bidak Pion Memiliki 5 prioritas yaitu maju 1 langkah, maju 2 langkah, menangkap lawan, promosi dan pilihan strategi. Bidak kuda Memiliki 3 prioritas yaitu bergerak, menangkap lawan dan strategi Bidak Ratu Memiliki 9 prioritas diantaranya maju 1 langkah, mundur 1 langkah, 1 langkah kiri, 1 langkah kanan, 1 langkah belakang kiri, 1 langkah belakang kanan, menangkap, strategi. Bidak Gajah Memiliki 6 prioritas yaitu langkah kiri, langkah kanan, langkah belakang kiri, langkah belakang kanan, menangkap, strategi, Bidak Benteng Memiliki yaitu 6 prioritas maju, mundur, samping kiri, samping kanan, strategi, Bidak Raja Memiliki 9 prioritas yaitu maju 1 langkah, mundur 1 langkah, 1 langkah

9.

4.2

kiri,1 langkah kanan, 1 langkah belakang kiri, 1 langkah belakang kanan, menangkap, strategi. Nilai Nilai untuk setiap bidak yaitu raja=6, ratu=5, benteng=4, kuda=3, gajah=2, dan pion=1.

5. Fungsi objektif digambarkan dalam sebuah script berikut ini

Pembahasan

Penerapan algoritma greedy pada permainan catur diataranya yaitu sebagai berikut : 1. Kondisi Pion Hitam

Script 1 Algoritma Greedy Kondisi Pion Hitam Berikut ini penjelasan algoritma greedy diatas yaitu tahap pertama menentukan fungsi yang diberinama greedy kondisi pion hitam, kemudian dilanjutkan dengan mendeklarasikan variabel menggerakkan pion, menangkap lawan dan type nilai dari variabel. Tahap berikutnya memasukkan logika yang dipilih. Dari logika C1 menangkap lawan menghasilkan nilai 0, sedangkan dari logika C2 menangkap lawan menghasilkan nilai 0. Dalam proses menghemat waktu maka solusi yang baik adalah logika C2.

Gambar 16 Kondisi Pion Hitam Berikut ini skema dalam Algoritma Greedy 1. Himpunan kandidat C yaitu C1 dan C2 2. Inisialiasi S Pemain pada permainanan catur a. Inisialiasi pada c1 C1= Menangkap lawan, dengan nilai=1 b. Inisialiasi pada C2 C2= Maju 1 Langkah, dengan nilai=0 3. Fungsi seleksi a. Menggerakkan pion kedepan, Nilai = 0 b. Menangkap lawan, Nilai = 1 4. Fungsi kelayakan a. Hasil dari C1 C1 --> menangkap lawan nilai = 1; C1 --> ditangkap lawan nilai = -1; C1 --> nilai = 0; b. Hasil dari C2 C2 --> maju 1 langkah = 0; C2 --> nilai = 0;

2.

Kondisi Kuda Hitam

Gambar 17 Kondisi Kuda Hitam Berikut ini skema dalam Algoritma Greedy 1. Himpunan kandidat C yaitu C1,C2 dan C3 2. Inisialiasi S Pemain pada permainanan catur a. Inisialiasi pada c1 12

C1= melakukan skak kanan, dengan nilai=1 b. Inisialiasi pada C2 C2= Maju 1 Langkah, dengan nilai=0 c. Inisialiasi pada c3 C3= melakukan skak kiri, dengan nilai=1 3. Fungsi seleksi Menggerakkan kuda kedepan, Nilai = 0 a. Melakukan skak, Nilai = 1 4. Fungsi kelayakan a. Hasil dari C1 C1 --> melakukan skak nilai = 1; C1 --> ditangkap lawan nilai = -1; C1 --> nilai = 0; b. Hasil dari C2 C2 --> maju 1 langkah = 0; C2 --> nilai = 0; c. Hasil dari C3 C3 --> melakukan skak nilai = 1; C3 --> nilai = 1; 5. Fungsi objektif digambarkan dalam sebuah script berikut ini

menghasilkan nilai 0, sedangkan dari logika C3 menangkap lawan menghasilkan nilai 1. Dalam proses perbandingan nilai maka solusi yang baik adalah logika C3.

5. KESIMPULAN Berdasarkan hasil penelitian penulis yang dilakukan dalam menggunakan algoritma greedy maka dapat diambil kesimpulan bahwa : 1. Algoritma greedy adalah algoritma yang sederhana yang dapat menyelesaikan permasalahan optimasi dengan baik pada beberapa kasus. 2. Penerapan algoritma greedy pada permainan catur dapat dimanfaatkan untuk kecerdasan buatan komputer 3. Prioritas untuk penerapan algoritma greedy sangat berpengaruh untuk melakukan pengecekan.

DAFTAR PUSTAKA 1. Asrofudin. 2010. Kegiatan Belajar Mengajar . www.blogrankings.com /../ 2982 html. 25 februari 2013 2. Alvin, Hasan Dalam. 2006 Kamus Istilah Teknologi Informasi. Yogyakarta : Andi 3. Komaruddin,2001, Ensiklopedia Manajemen, Edisi ke5, Jakarta : Bumi Aksara.

Script 2 Algoritma Greedy Kondisi Kuda Hitam Berikut ini penjelasan algoritma greedy diatas yaitu tahap pertama menentukan fungsi yang diberinama greedy kondisi pion hitam, kemudian dilanjutkan dengan mendeklarasikan variabel menggerakkan kuda, skak kanan, skak kiri dan type nilai dari variabel. Tahap berikutnya memasukkan logika yang dipilih. Dari logika C1 melakukan skak menghasilkan nilai 0, logika C2 melakukan skak

4. Community, eWolf. 2012. “Panduan Internet Paling Gampang”.Yogyakarta:Cakrawal 5. Departemen Pendidikan dan Kebudayaan.2002. ”Kamus

13

Besar Bahasa Indonesia”. Jakarta : Balai Pustaka. 6. Hendrayudi.2009. Pemrograman Borland Delphi 8.0. Andi : Yogyakarta 7. Magethi, Bey. 2009. Bagaimana memahami permainan catur. Bandung : Pionir Jaya. 8. Magethi, Bey. 2009. Pedoman bermain catur. Bandung : Pionir Jaya. 9. Perkins, E. J. 1974. The Biology of Estuaries and Coastal Water.Academi Press Co. New York. 10. Sutabri, Tata. 2012. “Analisis Sistem Informasi”. Yogyakarta: Andi Offset. 11. Sommerville, Ian, (2011), Software Engineering, 9th edition, Addison-Wesley, Boston, Massachusetts 12. Supardi. 2005. “Metodologi Penelitian Ekonomi & Bisnis”. Yogyakarta : UII Press.

14

ANALISIS PENGGUNAAN ALGORITMA GREEDY PADA PERMAINAN CATUR

Recommend Documents