analisis penggunaan algoritma greedy pada …if.binadarma.ac.id/sipi/jurnal/jurnal-ginonggom...

1

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

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.

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.

Masalah optimasi merupakan hal

yang sering kita jumpai dalam pekerjaan sehari-hari. Menyelesaikan masalah

mailto:[email protected]

2

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.

2. METODOLOGI 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).

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.

Gambar 1 Metode Grounded Research

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

2.1 Metode Pengambilan Data

Dalam pengumpulan data untuk

penelitian ini, digunakan beberapa cara

yaitu:

3

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

tanda 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

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.

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.

4

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

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

5. 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 lain-

lain.

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

masing 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,

5

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.

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. LANDASAN TEORI 3.1 Percobaan Awal 3.1.1 Pengamatan Fenomena

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.

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





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.3 Gerakan

Mulai

Apakah Ada?

Ya

Selesai

Beri label pada buah

catur

Tidak

Mencari titik terpendek berikutnya

dengan membandingkan jarak bidak

dan papan catur yang telah memiliki

label permanen

Menghapus dari

daftar inisialisasi

buah catur

Menentukan jarak

sementara antara bidak

dan papan catur

Inisialisasi

Papan Catur

Beri label pada papan

catur

Menghapus dari

daftar inisialisasi

papan catur

Gambar 2 Flowchart Gerakan Catur

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





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 Rokade

Rokade (dalam bahasa Inggris,

castling) merupakan gerakan khusus dalam

6

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 petak-

petak 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

Mulai

Apakah Ada?

Ya

Selesai

Beri label pada bidak

raja dan benteng

Tidak

Melaukan proses rokade

Menghapus dari

daftar inisialisasi

buah catur

Menentukan Bidak dan

pergerakan

Inisialisasi

Rokade


catur

Menghapus dari

daftar inisialisasi

papan catur

Gambar 3 Flowchart Rokade

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

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

Apakah Ada?

Ya

Selesai


pion

Tidak

Melaukan proses Enpassent

Menghapus dari

daftar inisialisasi

buah catur


pergerakan

Inisialisasi En

Passant


catur

Menghapus dari

daftar inisialisasi

papan catur

Gambar 4 Flowchart En passant


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


7

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

Apakah Ada?

Ya

Selesai


Raja

Tidak

Melaukan proses Skak

Menghapus dari

daftar inisialisasi

buah catur


posisi skak

Inisialisasi

Skak


catur

Menghapus dari

daftar inisialisasi

papan catur

Gambar 5 Flowchart Skak


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




3.1.5 Buah Catur

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

dinginkan oleh pemain.

Gambar 6 Buah Pion

8

Mulai

Apakah Ada?

Ya

Selesai

Beri label pada pion

Tidak




label permanen

Menghapus dari

daftar inisialisasi

buah catur

Menentukan jarak


dan papan catur

Inisialisasi

Pion


catur

Menghapus dari

daftar inisialisasi

papan catur

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.


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

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 8 Buah Kuda

Mulai

Apakah Ada?

Ya

Selesai

Beri label pada Kuda

Tidak




label permanen

Menghapus dari

daftar inisialisasi

buah catur

Menentukan jarak


dan papan catur

Inisialisasi

Kuda


catur

Menghapus dari

daftar inisialisasi

papan catur

Gambar 9 Flowchart Kuda

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

Gambar 10 Buah Ratu

9

Mulai

Apakah Ada?

Ya

Selesai

Beri label pada Ratu

Tidak




label permanen

Menghapus dari

daftar inisialisasi

buah catur

Menentukan jarak


dan papan catur

Inisialisasi

Ratu


catur

Menghapus dari

daftar inisialisasi

papan catur

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.



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




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").

Gambar 12 Buah Gajah

Mulai

Apakah Ada?

Ya

Selesai

Beri label pada Gajah

Tidak




label permanen

Menghapus dari

daftar inisialisasi

buah catur

Menentukan jarak


dan papan catur

Inisialisasi

Gajah


catur

Menghapus dari

daftar inisialisasi

papan catur

Gambar 13 Flowchart Gajah

Berikut ini Algoritma Greedy pada Gajah

yaitu :

10

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.








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.

Gambar 14 Buah Gajah

Mulai

Apakah Ada?

Ya

Selesai

Beri label pada

Benteng

Tidak




label permanen

Menghapus dari

daftar inisialisasi

buah catur

Menentukan jarak


dan papan catur

Inisialisasi

Benteng


catur

Menghapus dari

daftar inisialisasi

papan catur

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.


mundur. 3. Prioritas ketiga : samping kiri.


maju samping kiri.

4. Prioritas keempat : samping kanan.


maju samping kanan.

5. Prioritas kelima : Menangkap Lawan.


menangkap lawan.


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




6. Raja

Raja adalah buah catur yang paling

berharga. Permainan akan berakhir apabila raja dalam posisi di serang dan tidak ada jalan untuk membebaskannya.

11

Gambar 16 Buah Raja

Mulai

Apakah Ada?

Ya

Selesai

Beri label pada Raja

Tidak




label permanen

Menghapus dari

daftar inisialisasi

buah catur

Menentukan jarak


dan papan catur

Inisialisasi

Raja


catur

Menghapus dari

daftar inisialisasi

papan catur

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

untuk mundur 1 langkah samping

kanan.

7. Prioritas ketujuh : Menangkap Lawan.

Menggerakkan bidak raja untuk

menangkap lawan.







himpunan solusi, S adalah salah satu dari himpunan kandidat (arrayP[i] yang dapat


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 :

1. Bidak Pion

Memiliki 5 prioritas yaitu maju 1

langkah, maju 2 langkah, menangkap

lawan, promosi dan pilihan strategi.

2. Bidak kuda

3. Memiliki 3 prioritas yaitu bergerak,

menangkap lawan dan strategi 4. 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.

5. Bidak Gajah

Memiliki 6 prioritas yaitu langkah kiri,

langkah kanan, langkah belakang kiri,

langkah belakang kanan, menangkap,

strategi, 6. Bidak Benteng

7. Memiliki yaitu 6 prioritas maju,

mundur, samping kiri, samping kanan,

strategi,

8. Bidak Raja

Memiliki 9 prioritas yaitu maju 1

langkah, mundur 1 langkah, 1 langkah

12

kiri,1 langkah kanan, 1 langkah

belakang kiri, 1 langkah belakang

kanan, menangkap, strategi.

9. Nilai

Nilai untuk setiap bidak yaitu raja=6,

ratu=5, benteng=4, kuda=3, gajah=2,

dan pion=1.

4.2 Pembahasan Penerapan algoritma greedy pada

permainan catur diataranya yaitu sebagai

berikut :

1. Kondisi Pion Hitam

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;

5. Fungsi objektif digambarkan dalam

sebuah script berikut ini

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.

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

13

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

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

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.

4. Community, eWolf. 2012.

“Panduan Internet Paling

Gampang”.Yogyakarta:Cakrawal

5. Departemen Pendidikan dan

Kebudayaan.2002. ”Kamus

http://www.blogrankings.com/

http://www.blogrankings.com/

14

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.

analisis penggunaan algoritma greedy pada …if.binadarma.ac.id/sipi/jurnal/jurnal-ginonggom...

Documents