PEMODELAN DAN SOLUSI GAME MATE IN ONE PUZZLE DENGAN REPRESENTASI LOGIKA ANSWER SET PROGRAMMING RAHMAN SUJATMAN

PEMODELAN DAN SOLUSI GAME MATE IN ONE PUZZLE DENGAN REPRESENTASI LOGIKA ANSWER SET PROGRAMMING

RAHMAN SUJATMAN

DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012

ii

PEMODELAN DAN SOLUSI GAME MATE IN ONE PUZZLE DENGAN REPRESENTASI LOGIKA ANSWER SET PROGRAMMING

RAHMAN SUJATMAN

Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Departemen Ilmu Komputer

DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012

ABSTRACT RAHMAN SUJATMAN. Modeling and Solving Mate In One Puzzles Using Answer Set Programming. Supervised by MUSHTHOFA. Since the beginning of AI, mind games, such as Chess, have been studied as application fields for AI. Several variation of chess related problems have been shown to be NP-complete. This research deals with the problem of Mate in One Puzzles. We employ Answer Set Programming (ASP) to tackle this problem. ASP has been, in the last decade, the subject of active research in the field of logic programming, knowledge representation, and reasoning. ASP allows for an intuitive representation of computationally hard problems as well as efficient solving using state-of-the-art solvers, such as DLV. In this research, a representation of Mate In One Puzzles has been formulated and a prototype application system written using PHP and DLV has also been implemented. Experimental results show that the system is capable of generating solutions for Mate in One problem efficiently. However, the representation is still not efficient enough to be used for more difficult class of problems such as Mate in Two and Mate in Three. Keywords: answer set programming, chess, DLV, logic representation, mate in one, stable model

ii

Judul Skripsi : Pemodelan dan Solusi Game Mate In One Puzzle dengan Representasi Logika Answer Set Programming Nama : Rahman Sujatman NRP : G64070046

Menyetujui: Pembimbing,

Mushthofa, S.Kom, M.Sc NIP. 19820325 200912 1 003

Mengetahui: Ketua Departemen Ilmu Komputer,

Dr. Ir. Agus Buono, M.Si, M.Kom NIP. 19660702 199302 1 001

Tanggal Lulus:

RIWAYAT HIDUP Penulis dilahirkan di Sukabumi, Jawa Barat pada tanggal 04 Maret 1989 dari ayah yang bernama Oding Solehudin S.Pd dan ibu yang bernama Esin Susilahadiyanti. Penulis merupakan anak pertama dari tiga bersaudara. Anak kedua bernama Isep Wahyudin, dan anak ketiga bernama Dinur Saptiadi. Penulis memulai masa pendidikan formal pada tahun 1995 di SDN Cigaronggong 1, kemudian melanjutkan pendidikan sekolah menengah pertama di SLTPN 2 Jampangkulon, dan melanjutkan pendidikan sekolah menengah atas di SMAN 1 Jampangkulon, Sukabumi, Jawa Barat. Pada tahun 2007, penulis lulus sekolah menengah dan melanjutkan pendidikan di Institut Pertanian Bogor.

iv

PRAKATA Puji dan syukur penulis panjatkan kepada Allah atas segala curahan rahmat dan karuniaNya sehingga skripsi ini dapat diselesaikan. Skripsi yang berjudul Pemodelan dan Solusi Game Mate In One Puzzles dengan Representasi Logika Answer Set Programming ini merupakan hasil penelitian yang dilakukan oleh penulis yang dimulai dari bulan Mei 2011 sampai bulan Mei 2012. Penulis mengucapkan terima kasih kepada Bapak Mushthofa, S.Kom, M.Sc sebagai pembimbing yang telah memberi saran, masukan, dan ide-ide kepada penulis dalam menyusun skripsi ini. Penulis juga mengucapkan terima kasih kepada seluruh staf pengajar Departemen Ilmu Komputer atas ilmu yang telah diberikan, serta tidak lupa kepada staf tata usaha yang membantu administrasi selama kuliah di Institut Pertanian Bogor. Penulis berterima kasih setulus-tulusnya kepada orang tua yang telah memberikan kasih sayang, perhatian, doa, dan semangat selama kuliah di IPB, serta dukungannya dalam bentuk moral maupun material. Terima kasih yang sebesar-besarnya kepada teman-teman terbaik dari Ilkomerz 44 yang memberikan dukungan, bantuan, dan saran kepada penulis selama kuliah sampai penulis menyusun skripsi. Kepada semua pihak lainnya yang telah memberikan kontribusi yang besar selama pengerjaan penelitian ini yang tidak dapat disebutkan satu per satu, penulis ucapkan terima kasih banyak. Semoga penelitian ini dapat memberikan manfaat kepada pembaca sebagai referensi penelitian lanjutan dan pengembangan ilmu pengetahuan.

Bogor, Oktober 2012

Rahman Sujatman

DAFTAR ISI Halaman DAFTAR GAMBAR ....................................................................................................................... vi DAFTAR LAMPIRAN ...................................................................................................................vii PENDAHULUAN Latar Belakang .............................................................................................................................. 1 Tujuan Penelitian .......................................................................................................................... 1 Ruang Lingkup Penelitian ............................................................................................................. 1 TINJAUAN PUSTAKA Logic Programming ...................................................................................................................... 1 Answer Set Programming ............................................................................................................. 2 Syntax............................................................................................................................................ 2 Answer Set Semantics ................................................................................................................... 2 Reasoning Task ............................................................................................................................. 4 DLV .............................................................................................................................................. 4 METODE PENELITIAN Studi Literatur ............................................................................................................................... 6 Pengumpulan Kasus ...................................................................................................................... 6 Identifikasi Kasus ......................................................................................................................... 6 Identifikasi Aturan Catur .............................................................................................................. 6 Representasi Logika ASP dari Game Mate in One Puzzles .......................................................... 6 Pembuatan Back-ends ................................................................................................................... 6 Pembuatan Front-ends .................................................................................................................. 7 Pengujian dan Analisis .................................................................................................................. 7 HASIL DAN PEMBAHASAN Identifikasi Aturan Catur .............................................................................................................. 7 Representasi Logika ASP dari Game Mate in One Puzzles ........................................................ 11 Pembuatan Back-ends ................................................................................................................. 11 Pembuatan Front-ends ................................................................................................................ 17 Pengujian dan Analisis ................................................................................................................ 18 KESIMPULAN DAN SARAN Kesimpulan ................................................................................................................................. 21 Saran ........................................................................................................................................... 21 DAFTAR PUSTAKA ..................................................................................................................... 21 LAMPIRAN .................................................................................................................................... 22

v

vi

DAFTAR TABEL Halaman 1 Hubungan antara banyak anak catur dan waktu ........................................................................ 20 2 Hubungan antara ruang gerak anak catur dan waktu ................................................................. 20

DAFTAR GAMBAR Halaman 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

Problem solving in ASP .............................................................................................................. 2 Semua interpretasi I terhadap program P .................................................................................... 3 Pewarnaan Peta Australia ............................................................................................................ 4 4-Queen dan kotak papan catur 4x4 ............................................................................................ 5 Ilustrasi answer set pertama pada kasus tambahan pertama. ....................................................... 5 Ilustrasi answer set pertama pada kasus tambahan kedua. .......................................................... 6 Diagram proses penyelesaian game Mate In One Puzzles dengan answer set programming ..... 6 Posisi papan catur awal ............................................................................................................... 7 Pergerakan Menteri ..................................................................................................................... 7 Pergerakan makan dan terhalang pada Menteri ........................................................................... 8 Pergerakan Benteng..................................................................................................................... 8 Pergerakan Gajah ........................................................................................................................ 8 Pergerakan Kuda ......................................................................................................................... 8 Pergerakan Kuda makan.............................................................................................................. 9 Pergerakan Bidak ........................................................................................................................ 9 Pergerakan Bidak setelah dijalankan ........................................................................................... 9 Pergerakan Bidak makan ........................................................................................................... 10 Pergerakan Raja ........................................................................................................................ 10 Pergerakan Raja makan dan terhalang ...................................................................................... 10 Keadaan sekak ........................................................................................................................... 10 Cara menghindari sekak pertama .............................................................................................. 11 Cara menghindari sekak kedua.................................................................................................. 11 Cara menghindari sekak ketiga ................................................................................................. 11 Papan pergerakan Queen ........................................................................................................... 12 Papan pergerakan White Knight ................................................................................................ 12 Papan pergerakan makan Knight ............................................................................................... 13 Papan pergerakan makan Pawn ................................................................................................. 13 Kondisi terhalang pada Queen .................................................................................................. 14 Posisi Black King dalam keadaan disekak oleh White Queen ................................................... 14 Arsitektur sistem ....................................................................................................................... 17 Antarmuka halaman utama........................................................................................................ 17 Antarmuka halaman kasus ........................................................................................................ 17 Antarmuka halaman hasil pengkodean ...................................................................................... 18 Antarmuka halaman hasil akhir ................................................................................................. 18 Grafik hubungan antara banyak anak catur dan waktu .............................................................. 19 Grafik hubungan antara banyak anak catur dan waktu .............................................................. 19 Jenis dan ruang gerak anak catur pada kasus 7 ......................................................................... 19 Jenis dan ruang gerak anak catur pada kasus 27 ....................................................................... 19 Jenis dan ruang gerak anak catur pada kasus 47 ....................................................................... 20 Jenis dan ruang gerak anak catur pada kasus 3 ......................................................................... 20

vi

DAFTAR LAMPIRAN Halaman 1 Kode rule_utama.dl. ..................................................................................................................... 23 2 Kode lakukan_langkah.dl ............................................................................................................. 27 3 Kode periksa_sekakmate.dl .......................................................................................................... 28 4 Tabel hubungan antara banyak anak catur dan waktu .................................................................. 29 5 Tabel hubungan antara ruang gerak anak catur dan waktu........................................................... 30

vii

1

PENDAHULUAN Latar Belakang Catur dikategorikan sebagai permainan dan olahraga mental untuk mengimbangi olahraga fisik. Catur juga merupakan salah satu bidang yang menjadi domain permasalahan dan menjadi tolok ukur dalam bidang AI (Shannon 1950). Salah satu contoh permasalahan permainan catur ialah game Mate In One Puzzles. Mate In One merupakan langkah pertama dalam membuat sebuah permainan catur karena pada dasarnya permainan catur itu adalah Mate in N. Pada permasalahan Mate In One, secara komputasi algoritme yang dapat digunakan untuk memecahkan masalah tersebut cukup sulit karena tetap membutuhkan kaidah-kaidah permainan catur walaupun hanya untuk mematikan satu langkah. Answer Set Programming merupakan teknik pemrograman dengan paradigma deklaratif. Pemrograman deklaratif lebih singkat untuk mendapatkan penyelesaian suatu permasalahan daripada pemrograman imperatif (Lifschitz 2008). Pemrograman deklaratif hanya perlu memberikan ekpresi logika untuk mendapatkan penyelesaian suatu permasalahan. Ekpresi logika yang diberikan dapat berupa aturan (rule) dan fakta (fact). Pada pemrograman dengan paradigma imperatif harus diberikan perintah-perintah komputasi yang harus dilakukan oleh komputer untuk permasalahan yang sama. Hal ini memungkinkan kompleksitas pemrograman deklaratif menjadi lebih rendah daripada pemrograman imperatif. Saat ini, Answer Set Programming menjadi sangat marak digunakan. Pada beberapa dekade terakhir, Answer Set Programming (ASP) sendiri berkembang dengan pesat sebagai salah satu metode yang powerful dan menarik untuk menyelesaikan masalah dan representasi pengetahuan deklaratif, sehingga memungkinkan membentuk deklarasi untuk suatu representasi masalah dan penyelesaiannya. ASP memiliki semantics yang mudah dimengerti. DLV merupakan salah satu sistem yang menerapkan Answer Set Programming. DLV memiliki kinerja yang baik dan populer digunakan sebagai sistem penyelesaian ASP saat ini. DLV mampu memecahkan banyak masalah sulit dalam kehidupan nyata (Leone et al. 2006).

Oleh karena itu, pada penelitian ini akan diterapkan Answer Set Programming untuk merepresentasikan dan menyelesaikan permasalahan Mate In One Puzzle sehingga dapat menjadi rujukan penerapan Answer Set Programming pada domain permasalahan catur. Tujuan Penelitian Penelitian ini bertujuan merancang dan mengimplementasikan pengodean permasalahan dan solusi dari Mate In One Puzzles, serta menguji keefektifan dari encoding atau pengkodean yang didapatkan pada beberapa kasus uji game Mate In One Puzzles dengan menggunakan logika Answer Set Programming. Ruang Lingkup Penelitian Pada penelitian ini, kasus-kasus yang terdapat dalam game Mate In One Puzzles diperoleh dari sebuah game Kasparov Chessmate dari ebook Chess: 5334 Problems, Combinations, and Games serta dari website maetinone.com dengan sedikit modifikasi. Selain itu, beberapa kasus ada yang dibuat sendiri. Total kasus yang diuji ialah 75 kasus. Solver yang digunakan untuk eksekusi Answer Set Programming ini adalah DLV dan kemudian ditampilkan dengan menggunakan bahasa pemrograman PHP. Pengujian yang dilakukan ada 3 jenis: pertama kasus dengan tidak ada solusi sebanyak 25, kedua kasus dengan satu solusi sebanyak 25, dan ketiga kasus dengan solusi lebih dari satu sebanyak 25.

TINJAUAN PUSTAKA Logic Programming Logic programming merupakan bagian dari cara pendekatan pemrograman. Teknik pemrograman dengan paradigma deklaratif. tersusun secara jelas perintah-perintah komputasi yang diterima komputer. Namun, terdapat juga paradigma pemrograman komputer yang lain, seperti paradigma imperative programming dan functional programming (Pfenning 2006). Logic programming adalah sebuah teknik pemrograman dengan paradigma deklaratif yang dikodekan dalam bentuk aturan (rule) dan fakta (fact) (Naik 2010). Kowalski (1979) menyatakan bahwa sebuah algoritme A terdiri atas komponen logika L dan komponen kontrol C. Komponen logika L merupakan komponen yang menjelaskan logika algoritme

2

dan komponen kontrol C merupakan komponen yang menentukan cara yang digunakan. Secara simbolis, hal tersebut ditulis dengan persamaan berikut: A=L+C Kowalski (1979) menambahkan bahwa efisiensi dari sebuah algoritme dapat ditingkatkan dengan meningkatkan efisiensi dari komponen kontrol tanpa mengganti komponen logika dan tanpa mengubah arti algoritme tersebut. Answer Set Programming Answer set programming (ASP) merupakan pemrograman dari permasalahan komputasional dan kemudian memberikan sebuah penyelesaian untuk dijadikan solver pencarian solusi permasalahan. Answer Set Programming (ASP) juga diawali dengan diperkenalkannya stable model semantic oleh Gelfond & Lifschitz (1988). ASP membuka paradigma baru terhadap pemrograman logika dengan meningkatkan semantik dari pemrograman berbasis Prolog tradisional. Selanjutnya, terdapat penambahan fitur-fitur baru seperti classical negation dan disjungsi pada bagian head (Gelfond & Lifschitz 1988). ASP menggunakan masalah pencarian untuk komputasi dengan model, stable model, dan answer set solver yang digunakan untuk masalah pencarian (Lifschitz 2000). Permrograman menggunakan ASP tidak perlu menuliskan algoritme seperti halnya pemrograman imperatif. Hal yang harus dilakukan ialah menuliskan aturan-aturan yang bersesuaian untuk mendapatkan solusi dari masalah yang dikerjakan. Karena seperti yang telah dikemukakan oleh Kowalski (1979), Algoritme = Logika + Kontrol. Problem

Solution(s)

Modelling

Interpretation

Logic Program

Answer set(s) Computation

Gambar 1 Problem solving in ASP. Telah banyak pengembangan pada Answer Set Programming dibandingkan dengan pemrograman logika berbasis Prolog. Prolog tidaklah murni deklaratif. Semantik pada Prolog masih bergantung pada aspek prosedural, seperti urutan pada body literal

pada sebuah aturan (rule) dan urutan klausaklausa dalam program tersebut. Adanya operator cut pada Prolog (“!”) juga merupakan bukti properti prosedural Prolog (Mushthofa 2010). Syntax Pada Answer Set Programming terdefinisi penggunaan tiga buah simbol yaitu, predikat (p), konstanta (k), dan variabel (ν). Predikat adalah simbol yang diawali dengan huruf kecil sedangkan variabel adalah simbol yang diawali dengan huruf besar. Sebuah simbol konstanta bisa bernilai numerik. Sebuah term bisa berupa konstanta atau variabel. Suatu rule terdiri atas pasangan: Head ← Body Head (H) dan Body (B) adalah kumpulan finite rule dari elemen. Suatu rule disebut contraint jika Head = ∅ (Lifschitz 2000). Sebagai contoh: A0 ← A1, …, Am, Am+1, not Am+1, …, not An dengan n ≥ m ≥ 0, dan setiap Ai (0 ≤ i ≤ n) adalah Atom dan A merupakan normal rule (r) seperti urutan pasangan di atas. H(r) = {A0}, B(r) = {A1, …, Am, Am+1, not Am+1, …, not An}, B+(r) = {A1, …, Am} B-(r) = {Am+1,…, An} Bentuk aturan tanpa kepala (k = 0) disebut integrity constraint atau hard constraint. Aturan dengan minimal satu buah kepala (k = 1) disebut normal rule. Bentuk aturan dengan k > 1 disebut disjunctive rule. Jika bagian tubuh (body) kosong (m = n = 0), aturan disebut fakta (fact). Dalam penulisannya, simbol “ ” biasanya dihilangkan. Himpunan dari aturan-aturan tersebut disebut dengan extended disjunctive logic program (EDLP) atau biasa disebut program P. Answer Set Semantics Semantics adalah aturan untuk membentuk stable models dari kumpulan model. Kumpulan model didapatkan dari suatu logika proposional yang dibuat pemodelan berdasarkan aturan-aturan yang telah diberikan sebelumnya, kemudian diperiksa semua kemungkinan dari atom merupakan model atau bukan. Setelah didapatkan model-model dari logika proporsional tersebut, dengan mencari fact dari aturan-aturan tersebut dan dengan cara semantics yaitu menggunakan GL-Transform

3

akan didapatkan stables model dari formula proposionalnya (Lifschitz 2008). Semantik dari program didefinisikan untuk program yang telah bebas dari variabel. Program yang sudah tidak mengandung variabel dapat dikatakan sebagai program ground. Dengan demikian, pertama kali dilakukan ground instantiation pada program , yaitu menghilangkan semua variabel di dalam program . Herbrand Universe dari program yang dinotasikan dengan HUp merupakan himpunan semua simbol konstanta yang muncul di . Jika tidak terdapat simbol kontanta di maka HUp = {a}, dengan a merupakan simbol konstanta yang diambil sembarang dari , dengan adalah himpunan semua konstanta. Herbrand Base (HBp) dari program adalah himpunan semua literal ground yang dibangun dari simbol predikat yang muncul di dan simbol konstanta di . Sebuah ground instance pada aturan , dinotasikan dengan Ground(r) yang diperoleh dengan mengganti variabel yang terjadi di dengan simbol konstanta di HUp. Himpunan semua ground instance dari aturan dinotasikan dengan Ground(P) Semantik dari program harus mempertimbangkan program ground positif. Sebuah himpunan dari literal L ⊆ HBp dikatakan konsisten jika dan hanya jika setiap atom a ∈ HBp memenuhi {a,¬a} ⊈ L. Sebuah interpretasi I pada program P adalah sebuah himpunan bagian konsisten dari HBp. Sebuah himpunan dari literal memenuhi sebuah aturan r jika dan hanya jika H(r) ∩ S ≠ ∅ dengan B+(r) ⊆ S dan B+(r) ⊆ S ∅. Sebuah himpunan memenuhi program jika dan hanya jika literal memenuhi semua aturanaturan di dalam . Sebuah model dari program merupakan sebuah interpretasi I ⊆ HBp dengan memenuhi . Sebuah answer set dari program positif ground merupakan merupakan minimal model dari .

a Menghapus semua aturan r yang mempunyai literal negatif B- pada tubuh aturan tersebut dengan B ϵ I. b Menghapus semua literal negatif dari semua aturan yang tersisa. Sebuah answer set dari program P adalah I (dengan I ⊆ HBp), jika I adalah answer set dari . Semua himpunan answer set dari program dinotasikan dengan ANS(P). Program dikatakan konsisten jika mempunyai paling tidak satu answer set (ANS(P) ≠ ∅) dan selainnya dikatakan tidak konsisten. Pada kasus khusus untuk program definite Horn (k = 1 ,m = n), diketahui hanya memiliki satu answer set yang dapat ditemukan dengan mencari fixpoint terhadap program . Fixpoint terhadap disebut juga immediate consequence dan dinotasikan dengan Tp. didefinisikan sebagai interpretasi dari program definite Horn. Operator immediate consequence didefinisikan sebagai Tp (I) = {H(r) | B(r) ⊆ I, r ∈ P}. Selanjutnya Ii, dengan i ≥ 0 didefinisikan sebagai Io = ∅ dan Ii = Tp (Ii-1). Ii monoton dan mempunyai satu least fixpoint, dinotasikan dengan FP(PI). Sebagai contoh, di bawah ini adalah sebuah program : a ← p,not b b ← p,not a c←a c←b p← Kemungkinan model-model yang sesuai untuk program di atas dapat dilihat dari interpretasi pada Gambar 2 di bawah ini: a, b, c, p

a,b,c

a,b

Untuk memperluas definisi semantik pada program dengan negasi, dikenal transformasi Gelfond-Lifschitz (transformasi GL) untuk membebaskan negasi pada program . Pada transformasi GL dari program P, interpretasi I adalah atom dari program P. Transformasi GL ini dilambangkan dengan , yang dilakukan dengan:

a,b,p

a,c

a

a,c,p

a,p

b,c

b

c

b,c,p

b,p

c,p

p

Ø

Gambar 2

Semua interpretasi I terhadap program P.

Dari program tersebut diketahui bahwa p berupa fakta dan selalu bernilai benar serta

4

harus selalu muncul dalam setiap model. Untuk menentukan stable model dilakukan transformasi GL dan mengecek interpretasi I = FP(PI) atau dinotasikan I = Tp (P,I). Selanjutnya dipilih I1 = {p}, I2 = {a,p}, I3 = {b,p}, I4 = {c,p}, I5 = {a,b,p}, I6 = {a,c,p}, I7 = {b,c,p}, dan I8 = {a,b,c,p}. Pada I1 = {p}, dilakukan transformasi GL terhadap program P sehingga diperoleh :

Contoh penerapan Answer Set dalam Pewarnaan territorial peta Australia pada Gambar 3 berikut: vertex(WA) ← edge(WA,NT) ←

C(I)

vertex(NT) ← edge(NT,Q) ← vertex(Q) ← edge(Q,NSW) ← vertex(NSW) ← edge(NSW,V) ←

a←p b←p c←a c←b p← Fixpoint dari (FP( )) adalah {a,b,c,p}, sehingga diperoleh I1 FP( ). Hal ini berarti bahwa I1 bukan merupakan stable model, sedangkan untuk I6 {a,c,p} diperoleh :

vertex(V) ← edge(V,SA) ← vertex(SA) ← edge(SA,WA) ← vertex(T)

C(P)

← edge(V,U), colored(V,C), colored(U,C), color(C)

a←p c←a c←b p← Selanjutnya, diperoleh FP( ) = {a,c,p}, {a,c,p} sehingga I6 FP( ). Jadi I6 merupakan stable model.

colored(V,r) v colored(V,b) v colored(V,g) ← vertex(V)

Answer set

Dengan cara yang sama, untuk semua interpretasi I, diperoleh {a,c,p} dan {b,c,p} sebagai stable model dari program P dan juga merupakan answer set dari program P dan juga merupakan answer set dari program P.

{ colored(WA,r), colored(NT,g), colored(Q,r), colored(NSW,g), colored(V,r), colored(SA,b), colored(T,r)}

Reasoning Task Answer set semantic memiliki reasoning task, di antaranya (Musthofa 2010): 1 Answer set existence: hanya memberikan satu answer set yaitu benar atau salah yang sudah dilakukan stable model. 2 Brave reasoning: untuk menentukan ada 1 answer set yang mengandung suatu konfigurasi yang ditentukan jadi asalkan ada yang menyatakan x itu benar maka x brave reasoning. 3 Cautious reasoning: untuk menentukan terdapat suatu jawaban konfigurasi di semua answer set. Jadi, x benar dalam konfigurasi tersebut jika hasil pemodelan dan answer set x ada di semua konfigurasi. 4 Generate all answer : untuk menghasilkan semua answer set yang diterima rule setelah brave reasoning dan cautious reasoning diketahui.

Gambar 3 Pewarnaan peta Australia. DLV DLV adalah salah satu answer set solver yang mengimplementasikan Disjunctive Logic Program. Berawal dari sebuah penelitian pada 1996 di Austria, DLV hingga kini dikembangkan oleh kerja sama tim dari University of Calabria dan Technical University Wien (Leone et al. 2003). Menurut Eiter et al. (2006), Disjunctive Logic Programming (DLP) adalah formalisme canggih untuk representasi pengetahuan dan penalaran (knowledge representation and reasoning) yang sangat ekspresif dalam arti matematis. DLV merupakan sebuah sistem

5

KRR (Knowledge Representation and Reasoning) yang didasarkan pada Disjunctive Logic Programming (DLP) di bawah stable model semantic (disebut juga Answer Set Programming). Mengikuti ketentuan Prolog, string yang dimulai dengan huruf besar menunjukkan variabel, sedangkan string yang dimulai dengan huruf kecil adalah konstanta. Selain itu, DLV juga mendukung konstanta bilangan bulat positif dan konstanta string. Sebuah term adalah variabel atau konstanta. Bahasa DLV diperluas dengan adanya weak constraint. Eiter et al. (2006) menyatakan bahwa weak constraint sebagai varian dari integrity constraint. Untuk membedakan secara jelas, weak constraint menggunakan simbol “:~” bukan “:-”. Sebagai contoh, ASP digunakan untuk menyelesaikan permasalahan n-Queens. Misalnya terdapat empat Queen dan empat Queen tersebut ingin ditempatkan dalam kotak papan catur 4x4 dan penempatan Queen tersebut satu sama lain tidak saling makan. Ilustrasi permasalahan terdapat pada Gambar 4 dan 5,

Gambar 4 4-Queen dan kotak papan catur 4x4. Dalam kode DLV, permasalahan tersebut dituliskan seperti di bawah ini: baris(1..4). kolom(1..4). n(1..4). kotak(X,Y):-baris(X),kolom(Y). in(X,Y) v out(X,Y) :- kotak(X,Y). :- in(X1,Y), in(X2,Y), X1 != X2. :- in(X,Y1), in(X,Y2), Y1 != Y2. ok :in(X1,1),in(X2,2),in(X3,3),in(X4,4). :- not ok. :- in(X1,Y),in(X2,Y),X1<>X2. :- in(X1,Y1), in(X2,Y2), X2=X1+N, Y2=Y1+N, n(N),baris(X1),kolom(Y1). :- in(X1,Y1), in(X2,Y2), X2=X1+N, Y1=Y2+N, n(N),baris(X1),kolom(Y2).

Answer set yang dibentuk sebanyak 2 answer set. Answer set tersebut sebagai berikut: {in(1,2), in(2,4), in(3,1), in(4,3), ok}

{in(1,3), in(2,1), in(3,4), in(4,2), ok}

Answer set pertama menunjukkan bahwa Queen pertama terletak pada baris 1 kolom 2, Queen kedua terletak pada baris 2 kolom 4, Queen ketiga terletak pada baris 3 kolom 1, dan Queen keempat terletak pada baris 4 kolom 3.

Gambar 5 Ilustrasi answer set pertama pada kasus tambahan pertama. Kemudian, kasusnya sekarang yaitu ada delapan Queen yang ingin diletakkan dalam kotak papan catur 8x8. Maka kode program di atas ditambahkan dalam kode DLV seperti di bawah ini: baris(1..8). kolom(1..8). n(1..8). kotak(X,Y):-baris(X),kolom(Y). in(X,Y) v out(X,Y) :- kotak(X,Y). :- in(X1,Y), in(X2,Y), X1 != X2. :- in(X,Y1), in(X,Y2), Y1 != Y2. ok :in(X1,1),in(X2,2),in(X3,3),in(X4,4),in (X5,5),in(X6,6),in(X7,7),in(X8,8). :- not ok. :- in(X1,Y),in(X2,Y),X1<>X2. :- in(X1,Y1), in(X2,Y2), X2=X1+N, Y2=Y1+N, n(N),baris(X1),kolom(Y1). :- in(X1,Y1), in(X2,Y2), X2=X1+N, Y1=Y2+N, n(N),baris(X1),kolom(Y2).

Answer set yang sesuai dengan kendala di atas ada sebanyak 92. Answer set tersebut adalah sebagai berikut: {in(1,7), in(2,3), in(3,8), in(4,2), in(5,5), in(6,1), in(7,6), in(8,4),ok} . . . {in(1,4), in(2,1), in(3,5), in(4,8), in(5,6), in(6,3), in(7,7), in(8,2),ok}

Answer set pertama menunjukkan bahwa Queen pertama terletak pada baris 1 kolom 7, Queen kedua terletak pada baris 2 kolom 3, Queen ketiga terletak pada baris 3 kolom 8, Queen keempat terletak pada baris 4 kolom 2, Queen kelima terletak pada baris 5 kolom 5, Queen keenam terletak pada baris 6 kolom 1, Queen ketujuh terletak pada baris 7 kolom 6, dan Queen kedelapan terletak pada baris 8 kolom 4. Ilustrasi ada pada Gambar 6.

6

Studi Literatur Studi literatur dilakukan untuk memperoleh informasi yang dibutuhkan selama penelitian serta memahami tahapan yang harus dilakukan dalam metode penelitian. Informasi yang harus diketahui ialah Chess, Answer Set Programming, dan informasi lainnya yang dibutuhkan dalam penelitian ini. Gambar 6 Ilustrasi answer set pertama pada kasus tambahan kedua.

METODE PENELITIAN Pada penelitian ini dilakukan beberapa tahap dalam proses penyelesaian game Chess Puzzles dengan Answer Set Programming pada studi kasus game Mate In one Puzzles. Pada tahap awal, permasalahan direpresentasikan terlebih dahulu ke dalam logika Answer Set Programming untuk kemudian dibuat pengodean menggunakan DLV. Diagram proses penelitian dapat dilihat pada Gambar 7. Studi Literatur

Pengumpulan Kasus

Satu Solusi

Banyak Solusi

Identifikasi Aturan Catur

Aturan Gerak dan Terhalang

Aturan Makan

Pengumpulan kasus dilakukan dengan cara memindai kasus-kasus yang dikumpulkan dari berbagai sumber untuk selanjutnya dilihat dari jumlah anak catur serta kondisi permasalahan catur tersebut. Pada penelitian ini, kasus yang akan dimasukkan hanya kasus-kasus yang tingkat kesulitannya tinggi. Identifikasi Kasus Pada tahap identifikasi kasus, setelah kasus dikumpulkan, kasus dibedakan menjadi 3 jenis kategori. Pertama kasus dengan tidak ada solusi sebanyak 25, kedua kasus dengan satu solusi sebanyak 25, dan ketiga kasus dengan solusi lebih dari satu sebanyak 25. Identifikasi Aturan Catur

Identifikasi Kasus

Tidak Ada Solusi

Pengumpulan Kasus

Aturan Skak dan Skak-Mat

Representasi Logika ASP dari game Mate In One

Pembuatan Backends

Pembuatan Frontends

Identifikasi aturan peraturan catur mengacu pada aturan internasional permainan catur yang dirilis oleh FIDE. Pada penelitian ini, aturan yang akan diidentifikasi yaitu aturan gerakan masing-masing perwira catur beserta aturan jika pergerakan catur tersebut terhalang, kemudian aturan makan tiap anak catur, serta aturan kondisi sekak (check) dan sekakmat (check-mate). Representasi Logika ASP dari Game Mate in One Puzzles Pada tahap ini dituliskan syarat secara logika game Mate in One Puzzles yang kemudian diterjemahkan solver ke dalam sebuah programming. Logika tersebut dituliskan dalam sistem DLV. Tahap ini berguna untuk tahap selanjutnya yaitu merancang back-ends. Pembuatan Back-ends

Pengujian dan Analisis

Gambar 7 Diagram proses penyelesaian game Mate In One Puzzles dengan answer set programming.

Pada tahap pembuatan back-ends, representasi logika yang telah dibuat kemudian dituliskan dalam DLV dengan aturan-aturan yang sudah sesuai dengan game Mate in One Puzzles atau aturan dasar catur yang kemudian diintegrasikan dalam bahasa

7

pemrograman tertentu. Jadi, back-ends membuat gabungan pemrograman biasa ditambah DLV yang bisa dipanggil langsung dari pemrograman biasa yang pada penelitian ini menggunakan PHP.

dari petak d4 Menteri dapat menjangkau 27 petak lain. Representasi pergerakan Menteri pada petak d4 tersebut dapat dilihat pada Gambar 9.

Pembuatan Front-ends Pada tahap pembuatan Front-ends, dirancang arsitektur dan desain tampilan depan dari program yang dibuat berdasarkan back-ends di atas yang telah dipanggil dan diintegrasikan ke dalam bahasa pemrograman PHP. Pengujian dan Analisis Tahap pengujian dan analisis dilakukan dengan menjalankan program logika yang telah dibuat untuk 75 percobaan, kemudian dihitung waktunya dan dianalisis jumlah yang benar dan sesuai dan lama waktu komputasinya untuk kemudian dihitung akurasinya terhadap game Mate In One Puzzles.

HASIL DAN PEMBAHASAN Identifikasi Aturan Catur Permainan catur yang akan dibahas dalam penelitian ini menggunakan kaidah papan catur seperti pada Gambar 8, yaitu baris papan catur berawal dari 1 sampai dengan 8, sedangkan kolom berawal dari A sampai dengan H.

Gambar 8 Posisi papan catur awal. Aturan permainan catur yang akan dibahas dalam penelitian ini terdiri atas: 1 Menteri(Queen) Menteri merupakan buah catur yang dapat bergerak ke banyak petak. Gerakan Menteri bisa melangkah secara vertikal, horizontal, dan diagonal. Jika tidak terdapat penghalang,

Gambar 9 Pergerakan Menteri. Posisi Menteri pada Gambar 9 jika diasumsikan dalam baris X dan kolom Y, maka baris posisi Menteri tersebut berada di baris 4 dan kolom 4, sedangkan semua posisi yang dapat dicapai oleh Menteri dirumuskan menjadi:  (X,Y1), dengan: Y1=Y+K, Menteri bergerak horizontal ke kanan sebanyak K langkah, dan Y1=Y-K, Menteri bergerak horizontal ke kiri sebanyak K langkah.  (X1,Y), dengan: X1=X+K, Menteri bergerak vertikal ke atas sebanyak K langkah, dan X1=X-K, Menteri bergerak vertikal ke bawah sebanyak K langkah.  (X1,Y1), dengan: X1=X+K, Y1=Y+K, Menteri bergerak diagonal kanan atas sebanyak K langkah, X1=X+K, Y1=Y-K, Menteri bergerak diagonal kiri atas sebanyak K langkah, X1=X-K, Y1=Y-K, Menteri bergerak diagonal kiri bawah sebanyak K langkah, dan X1=X-K, Y1=Y+K, Menteri bergerak diagonal kanan bawah sebanyak K langkah. Menteri di d4 akan terhalang jika terdapat anak catur lain pada petak pergerakannya. Jika Menteri terhalang, Menteri tidak boleh melewati atau melompati buah catur lain yang menghalanginya. Kondisi terhalang tersebut akan dirumuskan dalam pembahasan aturan terhalang. Jika anak catur lain itu kepunyaan lawan, maka Menteri boleh memakan anak catur tersebut dan juga menduduki petak tempat buah lawan tersebut. Kondisi ini dirumuskan atau direpresentasikan dalam pembahasan aturan makan. Representasi keadaan makan dan terhalang pada Menteri di d4 tersebut dapat dilihat pada Gambar 10.

8

di petak putih tidak mungkin beralih ke petak hitam. Sebaliknya, Gajah pada petak hitam tidak bisa melangkah ke petak putih Representasi pergerakan Gajah tersebut dapat dilihat pada Gambar 12.

Gambar 10 Pergerakan makan dan terhalang pada Menteri. 2 Benteng (Rook) Benteng merupakan anak catur yang dapat bergerak secara vertikal dan horizontal. Jika posisi benteng yang berada pada petak e4 diasumsikan dalam baris X dan kolom Y, benteng berada pada baris 4 dan kolom 5. Semua posisi yang dapat dicapai oleh Menteri dirumuskan menjadi:  (X,Y1), dengan: Y1=Y+K, Benteng bergerak horizontal ke kanan sebanyak K langkah, dan Y1=Y-K, Benteng bergerak horizontal ke kiri sebanyak K langkah.  (X1,Y), dengan: X1=X+K, Benteng bergerak vertikal ke atas sebanyak K langkah, dan X1=X-K, Benteng gerak vertikal ke bawah sebanyak K langkah. Representasi pergerakan Benteng pada petak e4 tersebut dapat dilihat pada Gambar 11.

Gambar 12 Pergerakan Gajah.

Pada Gambar 12, jika posisi Gajah tersebut diasumsikan dalam baris X dan Y, Gajah putih berada pada baris 4 dan kolom 5. Semua posisi yang dapat dicapai oleh Gajah dirumuskan menjadi:  (X1,Y1), dengan: X1=X+K, Y1=Y+K, Gajah putih bergerak diagonal kanan atas sebanyak K langkah, X1=X+K, Y1=Y-K, Gajah putih bergerak diagonal kiri atas sebanyak K langkah, X1=X-K, Y1=Y-K, Gajah putih bergerak diagonal kiri bawah sebanyak K langkah, dan X1=X-K, Y1=Y+K, Gajah putih bergerak diagonal kanan bawah sebanyak K langkah. Cara memakan anak catur lawan juga sama dengan Menteri, tetapi terbatas sepanjang diagonal saja. Jika tidak terdapat penghalang, maka Gajah dapat menjangkau 13 petak lain. 4 Kuda (Knight) Pada pergerakan Kuda, Kuda bergerak sebanyak dua petak menurut kolom dan kemudian satu petak lagi ke samping kolom atau baris sehingga membentuk huruf L. Representasi pergerakan Kuda tersebut dapat dilihat pada Gambar 13.

Gambar 11 Pergerakan Benteng. Cara memakan buah catur lawan pada Benteng sama dengan Menteri, tetapi terbatas sepanjang kolom dan baris yang dikuasainya. Terdapat 14 petak yang dapat dikuasai Benteng jika Benteng dalam keadaan terbuka tanpa terhalang anak catur lain. 3 Gajah (Bishop) Gajah merupakan anak catur yang dapat bergerak secara diagonal. Gajah yang berada

Gambar 13 Pergerakan Kuda.

9

Kuda yang berada di petak hitam hanya dapat bergerak atau memakan buah lawan pada petak putih. Sebaliknya, jika Kuda itu berada di petak putih, Kuda tersebut hanya bisa bergerak atau memakan ke petak hitam. Posisi kuda pada Gambar 13 jika diasumsikan dalam baris X dan kolom Y, Kuda tersebut berada pada baris 4, kolom 4. Semua posisi yang dapat dicapai oleh Kuda dirumuskan menjadi:  (X1,Y1), dengan: X1=X+1, Y1=Y-2. Kuda bergerak ke kiri atas, baris bertambah 1 dan kolom berkurang 2, X1=X+1, Y1=Y+2. Kuda bergerak ke kanan atas, baris bertambah 1 dan kolom bertambah 2, X1=X-1, Y1=Y-2. Kuda bergerak ke kiri bawah baris berkurang 1 dan kolom bekurang 2, X1=X-1, Y1=Y+2. Kuda bergerak ke kanan bawah baris berkurang 1 dan kolom bertambah 2, X1=X+2, Y1=Y-1. Kuda bergerak ke kiri atas baris bertambah 2 dan kolom berkurang 1, X1=X+2, Y1=Y+1. Kuda bergerak ke kanan atas, baris bertambah 2 dan kolom bertambah 1, X1=X-2, Y1=Y-1. Kuda bergerak ke kiri bawah baris berkurang 2 dan kolom berkurang 1, dan X1=X-2, Y1=Y+1. Kuda bergerak ke kanan bawah baris berkurang 2 dan kolom bertambah 1.

masih pada posisi asalnya, setiap bidak boleh melangkah maju ke depan sejauh dua petak atau satu petak. Representasi petak pergerakan Bidak tersebut dapat dilihat pada Gambar 15.

Gambar 15 Pergerakan Bidak.

Gambar 15 memperlihatkan kedudukan asal semua bidak. Dari kedudukan ini, setiap bidak boleh dimajukan satu petak atau dua petak sekaligus. Posisi kedua bidak tersebut jika diasumsikan dalam baris X dan kolom Y, bidak putih berada pada baris 2 dan kolom 1 sampai dengan 8, sedangkan bidak hitam berada pada baris 7, kolom 1 sampai dengan 8. Semua posisi yang dapat dicapai oleh Bidak dirumuskan menjadi:  (X1,Y), dengan: X1=X+1. Bidak putih maju satu langkah, X1=X+2,X=2. Bidak putih maju dua langkah, X1=X-1. Bidak hitam maju satu langkah, dan X1=X-2,X=7. Bidak hitam maju dua langkah.

Kuda dapat bergerak melompati buah catur lain yang ada di sekelilingnya sehingga Kuda tidak dapat dihalangi baik oleh buah lawan ataupun buah sendiri. Representasi pergerakan Kuda dalam keadaan terhalang dapat dilihat pada Gambar 14. Gambar 16 Pergerakan Bidak setelah dijalankan

Gambar 14 Pergerakan Kuda makan. 5 Bidak atau Pion (Pawn) Bidak atau pion merupakan buah catur yang pergerakannya hanya bergerak maju dan tidak boleh mundur. Jika kedudukan bidak

Gambar 16 memperlihatkan bidak putih maupun hitam yang sebagian sudah dijalankan. Bidak yang sudah bergerak dari kedudukan asal hanya boleh melangkah maju satu petak saja. Jika di depan bidak ada buah sendiri atau buah lawan, bidak itu tidak bisa maju atau terhalang. Cara bidak memakan miring ke depan (arah diagonal). Jadi, cara memakan bidak hampir sama seperti Gajah, hanya saja terbatas satu petak langkah pergerakan memakannya. Representasi petak pergerakan

10

makan Bidak tersebut dapat dilihat pada Gambar 17.

X1=X+1, Y1=Y-1, Raja bergerak diagonal ke kiri atas satu langkah, X1=X-1, Y1=Y-1, Raja bergerak diagonal ke kiri bawah satu langkah, dan X1=X-1, Y1=Y+1, Raja gerak diagonal ke kanan bawah satu langkah. Representasi petak pergerakan makan Raja dapat dilihat pada Gambar 19.

Gambar 17 Pergerakan Bidak Makan. 6 Raja (King) Raja merupakan anak catur terpenting dalam sebuah permainan catur. Jika Raja sudah dalam keadaan sekakmat, permainan dianggap sudah berakhir. Cara Raja melangkah atau memakan sama seperti Menteri, tetapi terbatas hanya satu petak. Representasi petak pergerakan Raja dapat dilihat pada Gambar 18.

Gambar 19 Pergerakan Raja makan dan terhalang. Raja dapat memakan anak catur lawan jika anak catur lawan tersebut tidak dalam keadaan dilindungi oleh anak catur lawan yang lain. Raja pada Gambar 19 dapat memakan Kuda di f5, tetapi tidak dapat memakan bidak di d4 dan f4. Bidak d4 dipertahankan oleh Gajah e5 dan Kuda f5, sedangkan bidak f4 dijaga oleh Gajah e5 dan Kuda d5. 7 Sekak (Check)

Gambar 18 Pergerakan Raja. Raja putih di e4 tersebut dapat bergerak ke semua petak yang mengelilinginya. Jumlah petak yang dapat dicapai sebanyak delapan petak. Posisi Raja tersebut jika diasumsikan dalam baris X dan kolom Y, Raja tersebut berada di baris 4 dan kolom 5. Semua posisi yang dapat dicapai oleh Raja dirumuskan menjadi:  (X,Y1), dengan: Y1=Y+1, Raja bergerak horizontal ke kanan satu langkah, dan Y1=Y-1, Raja bergerak horizontal ke kiri satu langkah,  (X1,Y), dengan: X1=X+1, Raja bergerak vertikal ke atas satu langkah, dan X1=X-1, Raja bergerak vertikal ke bawah satu langkah.  (X1,Y1), dengan: X1=X+1, Y1=Y+1, Raja bergerak diagonal ke kanan atas satu langkah,

Sekak merupakan peringatan bahwa Raja dalam keadaan diserang. Agar Raja tersebut tidak terkena sekakmat, Raja harus menghindari sekak tersebut. Misalkan Raja Putih terkena sekak, maka ada tiga cara untuk menghindari sekak terhadap Raja Putih, yaitu:  Anak catur putih memakan anak catur hitam yang menyebabkan sekak.  Raja putih bergerak untuk menghindari arah serangan anak catur hitam.  Anak catur putih menutup arah serangan anak catur hitam. Representasi petak kondisi sekak terhadap Raja Putih dapat dilihat pada Gambar 20.

Gambar 20 Keadaan sekak.

11

Raja putih dalam posisi sekak oleh Benteng hitam dari g7. Untuk menghindarinya, dapat dilakukan dengan cara memakan anak lawan yang melakukan sekak itu dengan anak catur sendiri. Representasi cara menghindari sekak pertama dapat dilihat pada Gambar 21.

Representasi Logika ASP dari Game Mate in One Puzzles Vocabulary adalah predikat-predikat atau atoms yang terdapat dalam merepresentasikan logika permasalahan Mate in One Puzzles ke dalam logika ASP. Vocabulary ini terdiri atas posisi dan gerakan-gerakan anak catur yaitu Pawn (Bidak), Rook (Benteng), Knight (Kuda), Bishop (Gajah), Queen (Menteri), dan King (Raja), kondisi terhalang, Check (Sekak), dan Check-Mate (Sekakmat). Pada penjelasan pergerakan akan dicontohkan dengan Queen dan Knight. Untuk lebih lengkapnya, logika pergerakan setiap anak catur terdapat pada Lampiran 1. 1

Gambar 21 Cara menghindari sekak pertama. Pada Gambar 21 ditunjukkan cara mengindari sekak, yaitu Gajah putih memakan Benteng hitam yang melakukan sekak terhadap Raja Putih.

Gambar 22 Cara menghindari sekak kedua. Pada Gambar 22 ditunjukkan cara menghindari sekak, yang kedua yaitu Raja putih bergerak untuk menghindari arah serangan Benteng hitam.

posisi(queen,putih,0,4,4).

Predikat posisi merupakan predikat yang digunakan untuk merepresentasikan posisi setiap anak catur yang dimasukkan dalam setiap kasus. Predikat ini mempunyai 5 argumen. Argumen pertama adalah jenis anak catur yang dicontohkan dengan queen, argumen kedua yaitu warna anak catur yang dicontohkan dengan warna putih, argumen ketiga yaitu waktu dengan contoh waktu di sini 0 karena queen belum melakukan pergerakan, argumen keempat adalah baris yaitu pada logika diatas berada pada baris 4, dan argumen terakhir adalah kolom. Pada contoh lain, misalkan terdapat white knight yang berada f6, maka representasi logikanya posisi(kuda, putih1,0,6,6). Argumen putih1 tersebut digunakan untuk membedakan antara kuda pertama dan kedua, sedangkan argumen lain sama seperti penjelasan posisi queen sebelumnya. 2

gerak_queen_putih(queen, putih,T1,X1,Y1).

Predikat gerak_queen_putih merupakan predikat untuk mendapatkan petak pergerakan yang dapat dicapai oleh queen. Predikat tersebut mempunyai 5 argumen, yang pertama yaitu jenis anak catur, kedua warna, ketiga adalah variabel T1 yang berarti waktu, keempat X1 yang berarti baris, dan kelima Y1 yang berarti kolom. 3 Gambar 23 Cara menghindari sekak ketiga. Pada Gambar 23 ditunjukkan cara menghindari sekak yang ketiga, yaitu Benteng putih menutup arah serangan Benteng hitam sehingga arah serangan Benteng hitam terhadap Raja Putih tertutup oleh Benteng putih tersebut.

terhalang_queen_putih(queen,puti h,T,X1,Y1).

Predikat terhalang_queen_putih merupakan predikat untuk menangani jika pergerakan queen dalam kondisi terhalang oleh anak catur lain, predikat tersebut mempunyai 5 argumen, yang pertama yaitu jenis anak catur, kedua warna, ketiga adalah variabel T yang berarti waktu, keempat X1

12

yang berarti baris, dan kelima Y1 yang berarti kolom. 4

sekak_raja_hitam_oleh_1langkah(b enteng,putih1,1,X,Y).

Predikat

yang

keempat

yaitu artinya kondisi saat king sedang dalam keadaan disekak oleh rook, predikat tersebut mempunyai 5 argumen, yang pertama yaitu jenis anak catur yang membuat sekak, kedua warna, ketiga adalah konstanta 1 yang berarti waktu kesatu, keempat X yang berarti baris tempat king terkena sekak oleh rook, dan kelima Y yang berarti kolom tempat king terkena sekak oleh rook.

pergerakan anak catur lain hampir sama dengan pergerakan queen, hanya saja petak pencapaiannya lebih sedikit dan terbatas. Ilustrasi pergerakan Queen dapat dilihat pada Gambar 24.

sekak_raja_hitam_oleh_1langkah,

5

sekakmate:-tidakaman_gerak(_). sekakmate?

Predikat sekakmate tersebut merupakan predikat yang digunakan untuk memeriksa keadaan permasalahan sebuah kasus sekakmat atau tidak. Untuk memeriksa keadaan tersebut, perlu ada tambahan query yaitu dengan menggunakan cautious reasoning yang akan dijelaskan lebih lanjut pada pembahasan aturan sekakmat (Check-Mate). Pembuatan Back-ends Pembentukan kode DLV pada penelitian ini sesuai dengan aturan kode DLV oleh Eiter et al. (2006). Program DLV terdiri atas faktafakta (facts), aturan-aturan (rules) dan kendala-kendala (constraints). Data yang sudah dibentuk akan dilanjutkan dengan pembentukan fakta-fakta dan aturan-aturan. Selanjutnya dibentuk kendala-kendala yang diperoleh dari persyaratan permainan catur. Semua logika yang berupa fakta, aturan, dan kendala-kendala yang dibentuk dalam penelitian ini terdapat dalam Lampiran 1, Lampiran 2, dan Lampiran 3. Aturan pergerakan catur yang direpresentasikan hanya terdiri atas aturan dasar, yaitu gerak, makan, terhalang, sekak (check), dan sekakmat (check-mate). Aturanaturan istimewa seperti promosi bidak (pawn promotion), tusuk silang (en passant), dan rokade (castling) tidak dimasukkan karena batasan permasalahan hanya pada kasus Mate in One. Dengan demikian, aturan-aturan tersebut belum diperlukan karena hanya akan menambah waktu komputasi tanpa bisa terpakai.

Gambar 24 Papan pergerakan Queen. Logika pergerakan queen direpresentasikan dalam kode DLV seperti berikut: gerak_queen_putihtanpapenghalang(queen ,putih,T1,X1,Y1):posisi(queen,putih,T,X,Y), tetangga_queen(X1,Y1,X,Y),T1>0,T=T11,waktu(T1). tetangga_queen(X,Y1,X,Y):baris(X),baris(X),kolom(Y1),kolom(Y), Y1=Y+K,k(K).%queen geser ke kanan satu s/d tujuh delapan langkah . . . tetangga_queen(X1,Y1,X,Y):baris(X),baris(X1),kolom(Y1),kolom(Y), X1=X-K, Y1=Y+K,k(K).%queen geser diagonal kanan bawah satu s/d tujuh langkah

Logika pergerakan queen sebagai berikut. Jika terdapat posisi posisi queen pada baris X dan kolom Y dan mempunyai tetangga baris X1 dan kolom Y1, queen dapat bergerak ke petak X1, Y1. Predikat tetangga_queen artinya predikat yang merepresentasikan semua petak yang dapat dijangkau oleh pergerakan queen. Knight mempunyai pergerakan yang berbeda dengan anak catur yang lainnya. Pergerakannya dapat dilihat pada Gambar 25.

Aturan Gerak Aturan gerak akan dicontohkan dengan pergerakan queen dan knight karena

Gambar 25 Papan pergerakan White Knight.

13

Logika pergerakan knight direpresentasikan dalam kode DLV seperti berikut: gerak_kuda_putih1tanpapenghalang(kuda, putih1,T1,X1,Y1):posisi(kuda,putih1,T,X,Y), tetangga_kuda(X1,Y1,X,Y),T1>0,T=T11,waktu(T1). %tetangga kuda tetangga_kuda(X1,Y1,X,Y):baris(X),baris(X1),kolom(Y),kolom(Y1), X1=X+1, Y1=Y-2.%kuda geser kiri atas membentuk huruf L tetangga_kuda(X1,Y1,X,Y):baris(X),baris(X1),kolom(Y),kolom(Y1), X1=X-2, Y1=Y+1.%kuda geser kanan bawah membentuk huruf L

Logika pencarian pergerakan knight sama halnya dengan queen, yaitu jika terdapat posisi posisi knight pada baris X kolom Y dan mempunyai tetangga baris X1 kolom Y1 maka knight dapat bergerak ke petak X1, Y1. Predikat tetangga_kuda artinya predikat yang merepresentasikan semua petak yang dapat dijangkau oleh pergerakan knight. Aturan Makan Aturan makan akan dicontohkan dengan aturan makan knight dan pawn. Pada dasarnya, setiap anak catur hanya memakan anak catur lawannya. Ketika sebuah anak catur memakan anak catur lawan maka anak catur tersebut bergerak ke tempat anak catur tersebut memakan anak catur lawannya, sedangkan anak catur yang dimakan akan hilang dari petak papan catur tempat anak catur itu dimakan karena petak itu sudah dikuasai oleh anak catur yang memakannya. Pergerakan makan setiap anak catur sama dengan pergerakan anak catur itu sendiri kecuali pada Pawn yang memiliki cara bergerak dan makan berbeda. Ilustrasi pergerakan makan anak catur dapat dilihat pada Gambar 26.

Gambar 26 Papan pergerakan makan Knight. Logika pergerakan makan knight direpresentasikan dalam kode DLV seperti berikut:

%kuda makan kuda_putih1_makan(pion,hitam1,T1,XM,YM ):gerak_kuda_p1(kuda,putih1,T1,X,Y),posi si(pion,hitam1,T,X,Y),XM=X,YM=Y,T1>0,T =T1-1,waktu(T1),baris(XM),kolom(YM). . . . kuda_putih1_makan(pion,hitam1,T1,XM,YM ):gerak_kuda_p1(kuda,putih1,T1,X,Y),posi si(pion,hitam1,T,X,Y),XM=X,YM=Y,T1>0,T =T1-1,waktu(T1),baris(XM),kolom(YM).

Logika knight makan yaitu jika pergerakan knight putih pada waktu T1 ke baris X kolom Y dan posisi pawn pada waktu T berada pada baris X kolom Y, knight dapat memakan pawn tersebut pada baris XM kolom YM, XM sama dengan X dan YM sama dengan Y. Pawn mempunyai cara makan yang berbeda dengan pergerakan makan anak catur yang lain, yaitu pergerakan makan pada pawn yaitu satu langkah diagonal kiri dan kanan depan pawn tersebut. Ilustrasi pergerakan makan pawn yaitu seperti pada Gambar 27.

Gambar 27 Papan pergerakan makan Pawn. Logika pergerakan makan pawn direpresentasikan dalam kode DLV seperti berikut: %pion makan pion_putih1_makan(benteng,hitam1,T1,XM ,YM):pion_putih1_gerakmakan(pion,putih1,T1, X,Y),posisi(benteng,hitam1,T,X,Y),not pion_putih1_janganmakan(pion,putih1,T1 ,XM,YM),XM=X,YM=Y,T1>0,T=T11,waktu(T1),baris(XM),kolom(YM). . . . pion_putih1_gerakmakan(pion,putih1,T1, X1,Y1):-posisi(pion,putih1,T,X,Y), tetangga_pion_putihmakan(X1,Y1,X,Y),T1 >0,T=T1-1,waktu(T1). tetangga_pion_putihmakan(X1,Y1,X,Y):baris(X),baris(X1),kolom(Y),kolom(Y1), X1=X+1, Y1=Y+1.%pion geser satu langkah ke diagonal kanan atas . . .

14

tetangga_pion_putihmakan(X1,Y1,X,Y):baris(X),baris(X1),kolom(Y),kolom(Y1), X1=X+1, Y1=Y-1.%pion geser satu langkah ke diagonal kiri atas

Pawn putih dapat memakan pawn hitam jika pergerakan makan pawn putih pada waktu T1 ke baris X kolom Y dan posisi pawn hitam pada waktu T berada pada baris X kolom Y, pawn putih dapat memakan pawn hitam tersebut pada baris XM dan kolom YM, XM sama dengan X dan YM sama dengan Y. Aturan Terhalang Aturan terhalang merupakan aturan yang merepresentasikan keadaan sebuah anak catur jika pergerakannya terhalang oleh anak catur lain. Semua anak catur mempunyai kemungkinan terhalang kecuali knight. Misalkan posisi queen berada pada d4, maka queen akan terhalang jika terdapat anak catur lain di petak pergerakan queen tersebut. Jika anak catur tersebut mempunyai warna yang sama dengan queen, petak yang ditempati anak catur tersebut dan setelahnya tidak dapat ditempati queen. Sementara itu, untuk warna yang berbeda hanya petak setelahnya saja yang dapat ditempati queen, karena petak yang ditempati anak catur lawan bisa dikuasai dengan memakannya. Ilustrasi aturan terhalang pada queen dapat dilihat seperti pada Gambar 28.

Queen putih terhalang horizontal kanan jika terdapat posisi anak catur apapun pada baris yang sama dengan queen dengan kolom yang lebih besar daripada kolom tempat queen tersebut. Pada Gambar 28, posisi queen pada d4 sedangkan white pawn pada f4. Dengan demikian, dari f4 sampai h4 queen terhalang dan tidak dapat ditempati queen tersebut.

Pada predikat terhalang makan diartikan seperti pada posisi queen dan black pawn, sehingga kondisi tersebut dapat tertangani. Hal yang membedakan dengan predikat sebelumnya hanya pada variabel M dan N yang berarti jarak baris atau kolom anak catur yang menghalangi pergerakan anak catur yang terhalang. Untuk predikat terhalang, M lebih besar sama dengan N, sedangkan terhalang makan M lebih dari N karena untuk M sama dengan N masih dapat dijangkau dengan memakan anak catur yang menghalanginya tersebut. Dengan demikian, pada kasus ketika queen terhalang di vertikal atas oleh black pawn maka petak pergerakan queen termasuk petak black pawn tersebut. Aturan Sekak (Check) Pada aturan sekak, logikanya sama seperti pergerakan makan karena pada dasarnya sekak terjadi jika terdapat king di petak pergerakan lawan dari king tersebut, kecuali oleh king yang lain yang berlawanan karena tidak mungkin king melakukan sekak terhadap king. Sebagai contoh, misalkan terdapat black king di d7 dan white queen di d4, maka black king tersebut dalam keadaan sekak (check) oleh white queen seperti pada Gambar 29.

Gambar 28 Kondisi terhalang pada Queen. Logika aturan terhalang queen direpresentasikan dalam kode DLV seperti berikut: terhalang_horizontal_kanan_queenputih( queen,putih,T,X,YP):posisi(queen,putih,T,X,Y),posisi(_,_,T ,X,YK),YK=Y+N,YP=Y+M,M>=N,m(M),n(N),ba ris(XP),kolom(YP). . . . terhalang_makan_horizontal_kanan_queen putih(queen,putih,T,XN,YN):posisi(queen,putih,T,X,Y),posisi(_,_,T ,XK,YK),XK=X+N,YK=Y+N,XN=X+M,YN=Y+M,M> N,m(M),n(N),baris(XN),kolom(YN).

Gambar 29 Posisi Black King dalam keadaan di sekak oleh White Queen. Logika sekak (check) direpresentasikan dalam kode DLV seperti berikut: queen_putih_sekak(raja,hitam,T1,XM,YM) :gerak_queen_putihtanpapenghalang(queen ,putih,T1,X,Y),posisi(raja,hitam,T,X,Y ),not queen_putih_jangan_makan(queen,putih,T

15

,XM,YM),XM=X,YM=Y,T1>0,T=T11,waktu(T1),baris(XM),kolom(YM).

King hitam sekak oleh queen jika terdapat pergerakan dari queen ke baris X kolom Y pada waktu T1, dan posisi king hitam pada waktu T berada di baris X kolom Y.

Aturan Sekakmat (Check-Mate) Sekakmat (Check-Mate) merupakan tujuan utama dalam sebuah permainan catur, karena jika itu terjadi maka artinya permainan berakhir. Check-Mate yaitu kondisi king dalam keadaan diserang atau terancam oleh sekak (check) dan tidak ada jalan atau langkah yang dapat membebaskan king tersebut baik langkah king itu sendiri atau anak catur lain yang dapat menutup atau memakan anak catur lawan yang membuat sekak tersebut. Untuk mendapatkan langkah yang menyebabkan check-mate, dalam sistem ini harus dilalui beberapa alur logika. Pertama, karena pada batasan masalah hanya ada satu gerakan anak catur putih untuk menghasilkan check-mate, maka sistem akan mencari pergerakan anak catur putih yang menyebabkan sekak terhadap black king. Logika untuk mendapatkan pergerakan tersebut direpresentasikan dalam Kode DLV seperti berikut: lakukan_gerak(queen,putih,1,X1,Y1) v nlakukan_gerak(queen,putih,1,X1,Y1):gerak_queen_putih(queen,putih,1,X1,Y1) . :-lakukan_gerak(queen,putih,T,X1,Y1), lakukan_gerak(queen,putih,T,X2,Y2), X1!=X2. :lakukan_gerak(queen,putih,T,X1,Y1),lak ukan_gerak(queen,putih,T,X2,Y2),Y1!=Y2 . . . sekak(1):sekak_raja_hitam_oleh_1langkah(_,_,_,_ ,_). tidaksekak(1):-not sekak(1). :-lakukan_gerak(_,_,_,_,_), tidaksekak(1). . . . :-lakukan_gerak(queen,putih,1,X1,Y1), lakukan_gerak(pion,putih1,1,X2,Y2). . . . sekak_raja_hitam_oleh_1langkah(benteng ,putih1,1,X,Y):benteng_putih1_sekak(raja,hitam,2,X,Y) ,posisi(raja,hitam,1,X,Y).

Pada kode tersebut dijelaskan bahwa predikat lakukan_gerak hanya diambil satu. lakukan_gerak didapatkan dari setiap

pergerakan anak catur putih yang pada kode tersebut dicontohkan dengan lakukan gerak queen. Kemudian, pada logika pencarian lakukan_gerak tersebut terdapat dua constraint atau kendala yang artinya lakukan_gerak hanya satu kali untuk setiap setiap answer set. Dengan

demikian, pada satu itu terdapat satu gerakan rook, knight, bishop, queen, atau pawn, bergantung pada anak catur yang ada dalam kasus, sedangkan king tidak dihitung karena dalam Mate In One Puzzles tidak ada gerakan raja yang membuat satu langkah mati. Semua lakukan gerak tersebut menjadi satu kesatuan dalam sebuah answer set. Setelah itu, terdapat predikat sekak yang artinya gerakan anak catur putih menyebabkan sekak raja hitam setelah melangkah satu langkah. Sementara itu, predikat tidaksekak yaitu jika gerakan anak catur putih tersebut tidak menyebabkan sekak. lakukan_gerak

Kemudian jika diketahui lakukan_gerak putih dan tidaksekak maka dibuang lakukan_gerak anak catur putih tersebut melalui predikat atau constraint lakukan_gerak dan tidaksekak. Setelah semua aturan itu dijalankan maka akan terjadi perubahan posisi untuk anak catur yang bergerak dan atau yang dimakan. dalam kode DLV, aturan tersebut seperti berikut: posisi(benteng,hitam1,1,X,Y):posisi(benteng,hitam1,0,X,Y),lakukan_g erak(_,_,1,X1,Y1),not raja_putih_makan(benteng,hitam1,1,X1,Y 1),. . .,not pion_putih8_makan(benteng,hitam1,1,X1, Y1). . . . posisi(benteng,putih1,1,X,Y):posisi(benteng,putih1,0,X,Y),not lakukan_gerak(benteng,putih1,1,X1,Y1), lakukan_gerak(_,_,1,X1,Y1). posisi(benteng,putih1,1,X1,Y1):posisi(benteng,putih1,0,X,Y),lakukan_g erak(benteng,putih1,1,X1,Y1). . . .

Pada kode di atas terdapat 3 predikat, yang pertama posisi benteng (rook) hitam yang posisinya tetap sama di baris X kolom Y jika tidak dimakan oleh salah satu perwira putih, tetapi jika dimakan maka posisi benteng (rook) hitam tersebut hilang atau tidak ada dalam petak. Sementara itu, pada perwira putih ada dua kemungkinan, pertama benteng (rook) putih akan berada tetap di baris X kolom Y jika tidak ada pergerakan yang

16

dilakukan oleh benteng (rook) tersebut, sedangkan jika terjadi pergerakan akan berubah posisi menjadi baris X1, Y1 yang didapat dari predikat lakukan_gerak. Pengecekan ini dilakukan dengan menggunakan frame axiom. Frame axiom ini digunakan karena dalam hasil posisi yang baru tidak semua berubah (hanya yang ada gerakan) serta yang dimakan yang posisinya berubah, sedangkan selain keduanya maka posisi tetap. Kedua, setelah pergerakan putih dilakukan maka sekak yang dilakukan putih belum bisa dipastikan menimbulkan sekakmat (checkmate) atau tidak. Oleh karena itu, perlu dilakukan percobaan berbagai kombinasi gerakan dengan anak catur hitam untuk memeriksa pergerakan hitam yang dapat mencegah terjadinya sekakmat dengan tiga cara mencegah sekak yang sudah dijelaskan pada bahasan sebelumnya. Keadaan tersebut dapat direpresentasikan dalam kode DLV seperti berikut: sekak_raja_hitam_oleh(benteng,putih1,0 ,X,Y):benteng_putih1_sekak(raja,hitam,1,X,Y) ,posisi(raja,hitam,0,X,Y). . . . coba_sekak_raja_hitam_oleh(benteng,put ih1,1,X,Y):benteng_putih1_sekak(raja,hitam,2,X,Y) ,posisi(raja,hitam,1,X,Y). . . . coba_gerak(raja,hitam,1,X1,Y1) v ncoba_gerak(raja,hitam,1,X1,Y1):gerak_raja_hitam(raja,hitam,1,X1,Y1). :-coba_gerak(raja,hitam,T,X1,Y1), coba_gerak(raja,hitam,T,X2,Y2),X1!=X2. :- coba_gerak(raja,hitam,T,X1,Y1), coba_gerak(raja,hitam,T,X2,Y2),Y1!=Y2. . . . :-coba_gerak(raja,hitam,1,X1,Y1), coba_gerak(pion,hitam1,1,X2,Y2). . . .

Logika di atas pertama kali diperiksa keadaan sebelumnya sudah terjadi sekak atau belum. Hal ini terlihat dari predikat sekak_raja_hitam_oleh. Setelah diketahui dalam keadaan sekak, dilakukan percobaan gerakan melalui predikat coba_gerak, sama halnya dengan lakukan_gerak hanya ada satu coba_gerak yang diujikan dalam setiap

answer set. Setelah percobaan gerak dilakukan maka diperiksa kembali agar dapat diketahui kondisi selanjutnya tetap dalam keadaan sekak atau tidak, yaitu pada predikat coba_sekak_raja_hitam_oleh. Tahap berikutnya yaitu melakukan percobaan posisi untuk memeriksa posisi selanjutnya masih dalam keadaan sekak atau tidak, sehingga dari semua percobaan posisi tersebut dapat ditemukan percobaan posisi yang dalam keadaan sekakmat. Jika percobaan posisi yang sekakmat sudah diketahui, dapat diketahui lakukan_gerak yang menyebabkan percobaan posisi tersebut, sehingga gerakan anak catur putih yang menyebabkan satu langkah mati terhadap anak catur hitam dapat didapatkan. Logika tersebut direpresentasikan dalam kode DLV seperti berikut: posisi(benteng,putih1,1,X,Y):posisi(benteng,putih1,0,X,Y),coba_gera k(_,_,1,X1,Y1),not raja_hitam_makan(benteng,putih1,1,X1,Y 1),. . .,not pion_hitam8_makan(benteng,putih1,1,X1, Y1). . . . posisi(benteng,hitam1,1,X,Y):posisi(benteng,hitam1,0,X,Y),not coba_gerak(benteng,hitam1,1,X1,Y1),cob a_gerak(_,_,1,X1,Y1). posisi(benteng,hitam1,1,X1,Y1):posisi(benteng,hitam1,0,X,Y),coba_gera k(benteng,hitam1,1,X1,Y1).

Setiap answer set akan menghasilkan percobaan posisi yang berbeda-beda. Oleh karena itu, dibuat predikat percobaan posisi dengan menggunakan metode frame axiom. Jadi, posisi anak catur hitam akan berubah jika ada pergerakan tetapi anak catur hitam yang tidak bergerak akan tetap pada posisi semula. Sementara itu, putih akan tetap pada posisi semula jika tidak dimakan oleh anak catur yang hitam. Pada proses yang terakhir diperiksa pergerakan putih yang menimbulkan sekakmat (check-mate) terhadap anak catur hitam. Proses ini direpresentasikan dalam kode DLV seperti berikut: tidakaman_gerak(1):coba_gerak(raja,hitam,1,X1,Y1),coba_se kak_raja_hitam_oleh(_,_,1,X2,Y2),sekak _raja_hitam_oleh(_,_,0,X,Y). . . . aman_gerak(1):-not tidakaman_gerak(1). sekakmate:-tidakaman_gerak(_). sekakmate?

17

Predikat

atau dilakukan untuk mendapatkan pergerakan putih yang menyebabkan sekakmat. tidak_aman_gerak terjadi jika coba_gerak anak catur hitam pada waktu ke-1 dan terdapat percobaan sekak terhadap raja hitam pada waktu ke-1, serta terdapat sekak terhadap raja hitam pada waktu ke-0. Sementara itu, aman_gerak jika tidak terdapat tidakaman_gerak. Predikat terakhir yaitu sekakmate terjadi jika tidakaman_gerak dan untuk memastikan dalam setiap answer set dalam satu kali eksekusi kode DLV semua terdapat tidakaman_gerak. Perhitungan ini dilakukan dengan menggunakan query yaitu cautious reasoning. aman_gerak

tidakaman_gerak

Pembuatan Front-ends 1 Arsitektur Arsitektur atau diagram alir yang digunakan dalam penelitian ini tercantum pada Gambar 30.

ditampilkan hasil eksekusi dari masukan kasus tersebut sehingga didapatkan tampilan hasil eksekusi permasalahan tersebut. Keluaran sistem ini bisa terdapat satu solusi, banyak solusi, tetapi bisa juga tidak terdapat solusi. 2 Tampilan Tampilan pertama yaitu halaman utama seperti pada Gambar 31. Pada halaman ini, terdapat dua buah jenis masukan serta papan catur yang masih tersusun rapi sesuai posisi awal permainan catur. Dua buah masukan ini terdiri atas masukan manual yang berarti kasus yang ingin dimasukkan diketikkan terlebih dahulu dengan format posisi (anak catur, warna, waktu, baris, kolom) dan diakhiri tanda titik kemudian posisi berikutnya dituliskan pada basris selanjutnya. Sementara itu masukan kedua dari pilihan scroll bar yang terdiri atas kasus-kasus yang pernah dimasukkan.

Mulai

Input/ Output Data

Sistem

Kode DLV

Gambar 31 Antarmuka halaman utama.

Gambar 30 Arsitektur system.

Kasus yang dimasukkan manual akan masuk ke dalam scroll bar dan jumlah kasus pada scroll bar bertambah, sedangkan jika dipilih dari scroll bar maka jumlah kasus tetap. Setelah itu, akan ditampilkan halaman tampilan kasus pada Gambar 32.

Alur dari proses pencarian langkah anak catur putih ini dimulai dengan memasukan kasus ke dalam sistem. Kemudian, sistem diterjemahkan ke dalam kode DLV serta ditampilkan menjadi sebuah kasus yang terdapat tampilan gambar dari kasus tersebut. Setelah masukan kasus tersebut menjadi kode DLV, masukan akan dieksekusi dengan kode DLV untuk mencari langkah yang putih untuk kemudian diperiksa langkah tersebut agar bisa ditemukan terdapat solusi dari masukan kasus tersebut atau tidak. Setelah eksekusi selesai, hasil akan keluar sebagai kode DLV kembali dan kemudian dikirim ke sistem untuk

Gambar 32 Antarmuka halaman kasus

Eksekusi Kode DLV

18

Halaman tampilan kasus ini merupakan gambaran kasus sesuai yang dimasukkan pada halaman utama baik kasus yang dimasukkan manual ataupun dari scroll bar. Pada halaman ini terdapat button cari solusi yaitu untuk mendapatkan hasil pengodean DLV. Sistem akan menjalankan kode DLV yang sudah dimasukkan atau dipilih untuk kemudian dieksekusi dengan solver DLV. Setelah eksekusi selesai, akan ditampilkan halaman hasil pengodean pada Gambar 33.

yang dipakai dalam sistem ini yaitu notasi pendek karena sistem permainan catur pada umumnya banyak menggunakan notasi pendek. Ilustrasi dapat dilihat pada Gambar 34.

Gambar 34 Antarmuka halaman hasil akhir.

Gambar 33 Antarmuka halaman hasil pengkodean. Pada halaman ini terdapat papan catur sesuai dengan kasus yang dimasukkan dan di sebelah kanan terdapat pengodean DLV yang berisi posisi-posisi anak catur sesuai dengan kaidah pengkodean DLV. Di bawah pengodean terdapat answer set, yaitu solusi permasalahan setelah eksekusi namun masih dalam format kode DLV. Selain itu, terdapat waktu komputasi yaitu menghitung lama proses pencarian gerakan sampai ditemukan answer set yang diinginkan. Kemungkinan sekak yaitu semua gerakan anak catur putih yang menyebabkan sekak raja hitam untuk melihat kemungkinan yang menjadi answer set kasus tersebut, dan yang terakhir solusi sekakmat (check-mate) yaitu hasil gerakan yang diinginkan. Namun, disesuaikan dengan notasi catur internasional yang dirilis FIDE (Fédération Internationale Des Éches). Dalam aturan catur internasional terdapat dua notasi yaitu notasi panjang dan notasi pendek. Notasi

Halaman terakhir menampilkan papan catur hasil akhir dari semua proses dalam sistem. Pada bagian solusi sekakmat bisa dipilih solusi yang muncul untuk melihat pergerakannya. Pergerakan solusi di-highlight dengan blur warna kuning. Pengujian dan Analisis Proses pengujian pada setiap kasus dengan menggunakan 75 kasus. Penyelesaian dengan answer set programming ini dilakukan untuk mendapatkan waktu komputasi serta parameter-parameter yang memengaruhi waktu komputasi tersebut yang terdapat pada Lampiran 4. Banyak solusi dari masingmasing kasus ini terbagi menjadi 3, yaitu: 1 Tidak ada solusi Kasus yang menghasilkan tidak ada solusi answer set berjumlah 25 kasus. Tiap-tiap kasus tidak ada langkah yang menyebabkan checkmate. Pada kasus seperti ini, kemungkinan sekak tetap bisa terjadi, namun kemungkinan sekak tersebut belum membuat anak catur hitam checkmate. Hal ini disebabkan masih terdapat pergerakan anak catur hitam yang dapat menghindari sekak tersebut.

19

2 Satu solusi Kasus yang menghasilkan solusi sama dengan satu answer set ini berjumlah 25 kasus. Pada masing-masing kasus terdapat satu langkah yang menyebabkan checkmate. Pada kasus seperti ini, kemungkinan sekak bisa banyak. Namun, dari semua kemungkinan sekak tersebut, hanya ada satu yang membuat anak catur hitam checkmate. 3 Lebih dari satu solusi Kasus yang menghasilkan solusi lebih satu answer set ini berjumlah 25 kasus. Pada masing-masing kasus terdapat banyak solusi langkah yang dapat menyebabkan checkmate. Pada kasus seperti ini, kemungkinan sekak selalu lebih dari satu. Dari semua kemungkinan sekak tersebut, ada lebih dari satu kemungkinan yang dapat membuat anak catur hitam checkmate. Hubungan antara banyaknya anak catur dan lama waktu pencarian solusi dapat dilihat pada Gambar 35, sedangkan ilustrasi hubungan antara banyaknya anak catur dengan lama waktu pencarian dapat dilihat pada Gambar 35. Perhitungan lama waktu terhadap banyak anak catur untuk setiap kasus permasalahan Mate In One lebih lengkapnya terdapat pada Lampiran 4.

Gambar 36 Grafik hubungan antara banyak anak catur dengan waktu. Pada Gambar 36 terlihat bahwa untuk kasus dengan ruang gerak yang sedikit, didapatkan waktu pencarian sangat cepat, sedangkan untuk kasus dengan ruang gerak yang sangat banyak maka waktu pencariannya sangat lama. Pada kasus 3 dengan ruang gerak sebanyak 15, waktu pencariannya hanya membutuhkan 0.85 detik, sedangkan pada kasus 7 dengan ruang gerak sebanyak 802 memiliki waktu pencarian selama 59.96 detik. Perhitungan lama waktu terhadap ruang gerak anak catur untuk setiap kasus permasalahan Mate In One terdapat pada Lampiran 5.

Gambar 37 Jenis dan ruang gerak anak catur pada kasus 7.

Gambar 35 Grafik hubungan antara banyak anak catur dengan waktu. Pada Gambar 35 dapat dilihat bahwa dengan jumlah anak catur yang sama bisa didapatkan waktu yang berbeda jauh. Pada grafik tersebut terlihat pada kasus 7 dan 47 memiliki banyak anak catur masing-masing hanya 13 dan 18, tetapi waktu pencarian paling lama. Sementara itu, pada kasus 27 dengan banyak anak catur 13, didapatkan waktu pencarian sangat cepat, sehingga dapat diketahui bahwa banyaknya anak catur dalam sebuah kasus permasalahan Mate In One tidak memengaruhi lama pencarian solusi permasalahan.

Pada Gambar 37 dapat dilihat bahwa kasus 7 untuk anak catur putih terdapat Rook, Knight, Bishop, Queen, dan tidak ada Pawn pada kasus tersebut. Begitu pula anak catur hitam dengan perwira Rook, Bishop, dan Queen, sehingga pada kasus ini walaupun anak caturnya hanya 13 tetapi memiliki waktu pencarian paling lama karena ruang geraknya sangat banyak, yaitu sebesar 802.

Gambar 38 Jenis dan ruang gerak anak catur pada kasus 27.

20

Pada kasus 27 seperti pada Gambar 38 dapat dilihat kasus tersebut walaupun mempunyai anak catur sama dengan kasus 7 yaitu sebanyak 13 tetapi ruang gerak anak catur pada kasus 27 sebanyak 87 sedangkan kasus 7 ruang geraknya sebanyak 802. Pada kasus 27 terlihat terdapat banyak Pawn, dan ruang gerak Pawn tersebut banyak terhalang, serta pada perwira White Bishop, Black Knight, dan Black Rook juga mempunyai ruang gerak terbatas karena banyak terhalang oleh perwira yang lain.

Gambar 39 Jenis dan ruang gerak anak catur pada kasus 47. Kasus 47 merupakan kasus dengan waktu pencarian solusi terlama kedua. Pada kasus 47 seperti pada Gambar 39 terlihat jenis anak catur yang terdapat pada kasus tersebut mempunyai perwira dengan ruang gerak sangat banyak dan juga mempunyai kemungkinan sekak sangat banyak yaitu sebanyak 16 serta mempunyai solusi terbanyak yaitu sebanyak 9. Kombinasi gerakan anak catur hitam untuk menghindari serangan anak catur putih sangat banyak, sehingga ruang gerak kasus tersebut sangat banyak yaitu sebanyak 729.

hitam tidak perlu ada percobaan gerakan karena tidak gerakan anak catur putih yang menyebabkan sekak, sehingga tidak perlu ada percobaan gerak dari anak catur hitam. Dengan demikian, waktu pencariannya juga berjalan sangat cepat. Tabel 1 Hubungan antara banyak anak catur dengan waktu No Kasus

Banyak Anak Catur

Waktu (detik)

3

9

0.85

70

7

2.41

71

6

2.68

62

13

3.41

2

11

3.63

19

23

39.54

31

28

39.98

55

18

43.10

47

18

58.56

7

13

59.96

Pada Tabel 1 dapat dilihat bahwa kasus 3 merupakan kasus dengan pencarian solusi tercepat yaitu dengan lama waktu 0,85 detik, sedangkan kasus 7 merupakan kasus dengan pencarian solusi terlama yaitu dengan lama waktu 59,96 detik. Dapat dilihat bahwa banyak anak catur tidak berpengaruh terhadap lama waktu pencarian. Kasus 7 dan 62 mempunyai banyak anak catur yang sama tetapi waktu pencarian solusi sangat berbeda jauh. Tabel 2 Hubungan ruang gerak anak catur dengan waktu No Kasus

Banyak Ruang Gerak

Waktu (detik)

3

15

0.95

70

21

2.41

71

52

2.68

Gambar 40 Jenis dan ruang gerak anak catur pada kasus 3.

62

47

3.41

2

53

3.63

Kasus 3 seperti pada Gambar 40 merupakan kasus dengan waktu pencarian solusi tercepat. Hal ini disebabkan pada kasus 3 hanya ada 9 perwira, dan setiap perwira mempunyai ruang gerak terbatas yaitu White Rook, White Knight, dan White Pawn, tetapi ruang geraknya hanya sedikit. Selain itu, ruang gerak White Rook juga terbatas atau terhalang oleh perwira lain. Selain itu, perwira

19

349

39.54

31

376

39.98

55

554

43.10

47

729

59.56

7

802

58.96

Pada Tabel 2 dapat dilihat bahwa ruang gerak anak catur dalam setiap kasus sangat

21

berpengaruh terhadap lama pencarian solusi. Pada kasus 3 dengan ruang gerak hanya 15, waktu pencariaannya hanya membutuhkan waktu 0.85 detik, sedangkan kasus 7 dengan ruang gerak sebanyak 802 memiliki waktu pencarian 59.96 detik. Jadi, semakin banyak ruang gerak anak catur dalam sebuah kasus permasalahan Mate In One, maka akan semakin lama waktu pencarian solusi permasalahan kasus Mate In One tersebut.

KESIMPULAN DAN SARAN Kesimpulan 1 Telah dibuat sebuah representasi atau encoding dalam sebuah aturan-aturan permainan catur dari permasalahan Answer Set Programming dengan menggunakan syntax DLV. 2 Semua kasus uji pengodean tersebut mampu menemukan semua solusi dari permasalahan yang telah dimasukkan baik yang tidak terdapat solusi, satu solusi, atau yang memiliki lebih dari satu solusi. 3 Waktu pengujian tercepat sampai ditemukannya solusi dari permasalahan Mate In One yaitu 0.85 detik pada kasus 3, sedangkan waktu terlama yaitu pada kasus 47 dengan waktu eksekusi 59.96 detik. Saran Beberapa hal yang dapat dikembangkan dalam penelitian selanjutnya yaitu: 1 Penambahan ruang lingkup permasalahan menjadi dua, tiga, atau lebih langkah dalam pencarian langkah yang bisa menjadi solusi, karena pada penelitian ini hanya terbatas pada Mate In One. 2 Pengembangan untuk membuat sebuah permainan catur lengkap yaitu dari mulai permainan awal sampai akhir.

DAFTAR PUSTAKA Baral C. 2004. Answer Set Programming: Knowledge Representation, Reasoning, and Declarative Problem Solving Using AnsProlog. Arizona: Departement of Computer Science and Engg, Arizona State University. Eiter T, Faber W, Gottlob G, Leone N, Perri S et al. 2006. The DLV System for Knowledge Representation and Reasoning. Calabria: Departement of Matematics, University of Calabria.

Gelfond M, Lifschitz V. 1988. The Stable Model Semantic for Logic Programming. El Paso: University of Texas. Hauptman A. 2007. Evolution of an Efficient Search Algorithm for the Mate-In-N Problem in Chess. Beer-Sheva: Departement of Computer Science, BenGurion University. Kendal G, Parkes A, Spoerer K. 2004. A Survey of NP-Complete Puzzles. Nottingham: University of Nottingham. Kowalski R. 1979. Algorithm = Logic Control. London: Imperial College.

+

Laszlo P. 1995. Chess: 5334 Problems, Combinations, and Games. Leventhal: Black Dog and Leventhal Publishers. Lifschitz V. 1988. The Stable Model for Logic Programming. Austin: University of Texas. Lifschitz V. 2000. Answer Set Programming and Plan Generation. Austin: University of Texas. Lifschitz V. 2008. What is Answer Set Programming. Austin: University of Texas. Musthofa. 2010. Evaluations of answer set programs with bounded predicate arities [tesis]. Vienna: Faculty of Informatics, Departement of Knowledge Based Systems, Vienna University of Technology, Austria. Pfenning F. 2006. Logic Programming. Carnegie: Carnegie Mellon University. Russell SJ, Norvig P. 1995. Artificial Intelligence: A Modern Approach. Englewood Cliffs: Prentice-Hall. Shannon CE. 1950. Programming a Computer to Play Chess. Murray Hill: Bell Telephone Laboratories, Inc.

22

LAMPIRAN

23

Lampiran 1 rule_utama.dl baris(1..8). kolom(1..8). waktu(0..4). k(1..7). m(1..7). n(1..7). %GERAK BENTENG %gerak benteng putih satu gerak_benteng_putih1(benteng,putih1,T1,X1,Y1):gerak_benteng_p1(benteng,putih1,T1,X1,Y1),T1>0,T=T1-1,waktu(T1). gerak_benteng_putih1(benteng,putih1,T1,X1,Y1):benteng_putih1_makan(_,_,T1,X1,Y1),T1>0,T=T1-1,waktu(T1). gerak_benteng_p1(benteng,putih1,T1,X1,Y1):gerak_benteng_putih1tanpapenghalang(benteng,putih1,T1,X1,Y1),not terhalang_benteng_putih1(benteng,putih1,T,X1,Y1),T1>0,T=T1-1,waktu(T1). gerak_benteng_putih1tanpapenghalang(benteng,putih1,T1,X1,Y1):posisi(benteng,putih1,T,X,Y), tetangga_benteng(X1,Y1,X,Y),T1>0,T=T1-1,waktu(T1). %benteng makan benteng_putih1_makan(benteng,hitam1,T1,XM,YM):gerak_benteng_putih1tanpapenghalang(benteng,putih1,T1,X,Y),posisi(benteng,hitam1,T ,X,Y),not benteng_putih1_jangan_makan(benteng,putih1,T,XM,YM),XM=X,YM=Y,T1>0,T=T11,waktu(T1),baris(XM),kolom(YM). . . . benteng_putih1_jangan_makan(benteng,putih1,T,XN,YN):posisi(benteng,putih1,T,X,Y),posisi(_,_,T,X,YK),YK=Y+N,YN=Y+M,M>N,m(M),n(N),baris( XN),kolom(YN),T<2,waktu(T). . . . terhalang_benteng_putih1(benteng,putih1,T,XP,YP):terhalang_horizontal_kanan_bentengputih1(benteng,putih1,T,X,YP),XP=X,baris(XP),kol om(YP),T<2,waktu(T). . . . %GERAK KUDA %gerak kuda putih satu gerak_kuda_putih1(kuda,putih1,T1,X1,Y1):-gerak_kuda_p1(kuda,putih1,T1,X1,Y1). gerak_kuda_putih1(kuda,putih1,T1,X1,Y1):-kuda_putih1_makan(_,_,T1,X1,Y1). gerak_kuda_p1(kuda,putih1,T1,X1,Y1):gerak_kuda_putih1tanpapenghalang(kuda,putih1,T1,X1,Y1),not terhalang_kuda_putih1(kuda,putih1,T,X1,Y1),T1>0,T=T1-1,waktu(T1). gerak_kuda_putih1tanpapenghalang(kuda,putih1,T1,X1,Y1):-posisi(kuda,putih1,T,X,Y), tetangga_kuda(X1,Y1,X,Y),T1>0,T=T1-1,waktu(T1). terhalang_kuda_putih1(kuda,putih1,T,X1,Y1):gerak_kuda_putih1tanpapenghalang(kuda,putih1,T1,X1,Y1),posisi(_,putih,T,X1,Y1),T1> 0,T=T1-1,waktu(T1),baris(XP),kolom(YP). . . . %kuda makan kuda_putih1_makan(benteng,hitam1,T1,XM,YM):gerak_kuda_p1(kuda,putih1,T1,X,Y),posisi(benteng,hitam1,T,X,Y),XM=X,YM=Y,T1>0,T=T1 -1,waktu(T1),baris(XM),kolom(YM). . . . %GERAK PLUNCUR %gerak pluncur putih satu gerak_pluncur_putih1(pluncur,putih1,T1,X1,Y1):gerak_pluncur_p1(pluncur,putih1,T1,X1,Y1). gerak_pluncur_putih1(pluncur,putih1,T1,X1,Y1):-pluncur_putih1_makan(_,_,T1,X1,Y1).

24

Lanjutan gerak_pluncur_p1(pluncur,putih1,T1,X1,Y1):gerak_pluncur_putih1tanpapenghalang(pluncur,putih1,T1,X1,Y1),not terhalang_pluncur_putih1(pluncur,putih1,T,X1,Y1),T1>0,T=T1-1,waktu(T1). gerak_pluncur_putih1tanpapenghalang(pluncur,putih1,T1,X1,Y1):posisi(pluncur,putih1,T,X,Y), tetangga_pluncur(X1,Y1,X,Y),T1>0,T=T1-1,waktu(T1). %pluncur makan pluncur_putih1_makan(benteng,hitam1,T1,XM,YM):gerak_pluncur_putih1tanpapenghalang(pluncur,putih1,T1,X,Y),posisi(benteng,hitam1,T ,X,Y),not pluncur_putih1_jangan_makan(pluncur,putih1,T,XM,YM),XM=X,YM=Y,T1>0,T=T11,waktu(T1),baris(XM),kolom(YM). . . . pluncur_putih1_jangan_makan(pluncur,putih1,T,XN,YN):posisi(pluncur,putih1,T,X,Y),posisi(_,_,T,XK,YK),XK=X+N,YK=Y+N,XN=X+M,YN=Y+M,M>N,m (M),n(N),baris(XN),kolom(YN). . . . terhalang_pluncur_putih1(pluncur,putih1,T,XP,YP):terhalang_diagonal_kananatas_pluncurputih1(pluncur,putih1,T,XP,YP). . . . %GERAK RAJA %gerak raja putih gerak_raja_putih(raja,putih,T1,X1,Y1):-gerak_raja_p(raja,putih,T1,X1,Y1). gerak_raja_putih(raja,putih,T1,X1,Y1):-raja_putih_makan(_,_,T1,X1,Y1). gerak_raja_p(raja,putih,T1,X1,Y1):gerak_raja_putihtanpapenghalang(raja,putih,T1,X1,Y1),not raja_putih_janganmakan(raja,putih,T,X1,Y1),T1>0,T=T1-1,waktu(T1). gerak_raja_putihtanpapenghalang(raja,putih,T1,X1,Y1):-posisi(raja,putih,T,X,Y), tetangga_raja(X1,Y1,X,Y),T1>0,T=T1-1,waktu(T1). raja_putih_janganmakan(raja,putih,T,X1,Y1):gerak_raja_putihtanpapenghalang(raja,putih,T1,X1,Y1),posisi(_,putih,T,X1,Y1),T1>0, T=T1-1,waktu(T1). . . . %raja makan raja_putih_makan(benteng,hitam1,T1,XM,YM):gerak_raja_putihtanpapenghalang(raja,putih,T1,X,Y),posisi(benteng,hitam1,T,X,Y),XM =X,YM=Y,T1>0,T=T1-1,waktu(T1),baris(XM),kolom(YM),not raja_putih_janganmakan(raja,hitam,T,XM,YM). . . . %GERAK QUEEN %gerak queen putih gerak_queen_putih(queen,putih,T1,X1,Y1):-gerak_queen_p(queen,putih,T1,X1,Y1). gerak_queen_putih(queen,putih,T1,X1,Y1):-queen_putih_makan(_,_,T1,X1,Y1). gerak_queen_p(queen,putih,T1,X1,Y1):gerak_queen_putihtanpapenghalang(queen,putih,T1,X1,Y1),not terhalang_queen_putih(queen,putih,T,X1,Y1),T1>0,T=T1-1,waktu(T1). gerak_queen_putihtanpapenghalang(queen,putih,T1,X1,Y1):-posisi(queen,putih,T,X,Y), tetangga_queen(X1,Y1,X,Y),T1>0,T=T1-1,waktu(T1). %queen makan queen_putih_makan(benteng,hitam1,T1,XM,YM):gerak_queen_putihtanpapenghalang(queen,putih,T1,X,Y),posisi(benten g,hitam1,T,X,Y),not queen_putih_jangan_makan(queen,putih,T,XM,YM),XM=X,YM=Y,T1>0,T=T11,waktu(T1),baris(XM),kolom(YM). queen_putih_jangan_makan(queen,putih,T,XN,YN):terhalang_makan_horizontal_kanan_queenputih(queen,putih,T,XN,YN). . .

25

Lanjutan terhalang_makan_horizontal_kanan_queenputih(queen,putih,T,XN,YN):posisi(queen,putih,T,X,Y),posisi(_,_,T,XK,YK),XK=X+N,YK=Y+N,XN=X+M,YN=Y+M,M>N,m(M) ,n(N),baris(XN),kolom(YN). . . . terhalang_queen_putih(queen,putih,T,XP,YP):terhalang_horizontal_kanan_queenputih(queen,putih,T,X,YP),XP=X,baris(XP),kolom(YP) . . . . terhalang_horizontal_kanan_queenputih(queen,putih,T,X,YP):posisi(queen,putih,T,X,Y),posisi(_,_,T,X,YK),YK=Y+N,YP=Y+M,M>=N,m(M),n(N),baris(XP ),kolom(YP). . . . %GERAK PION %Gerak Pion Putih %gerak pion putih satu gerak_pion_putih1(pion,putih1,T1,X1,Y1):-gerak_pion_p1(pion,putih1,T1,X1,Y1). gerak_pion_putih1(pion,putih1,T1,X1,Y1):-pion_putih1_makan(_,_,T1,X1,Y1). gerak_pion_p1(pion,putih1,T1,X1,Y1):-posisi(pion,putih1,T,X,Y), tetangga_pionputih(X1,Y1,X,Y),not terhalang_pion_putih1(pion,putih1,T,X1,Y1),T1>0,T=T1-1,waktu(T1). terhalang_pion_putih1(pion,putih1,T,XP,YP):terhalang_vertikal_atas_pionputih1(pion,putih1,T,XP,Y),YP=Y,baris(XP),kolom(YP). terhalang_vertikal_atas_pionputih1(pion,putih1,T,XP,Y):posisi(pion,putih1,T,X,Y),posisi(_,_,T,XK,Y),XK=X+O,XP=X+P,P>=O,o(O),p(P),baris(XP ),kolom(YP). %pion makan pion_putih1_makan(benteng,hitam1,T1,XM,YM):pion_putih1_gerakmakan(pion,putih1,T1,X,Y),posisi(benteng,hitam1,T,X,Y),not pion_putih1_janganmakan(pion,putih1,T1,XM,YM),XM=X,YM=Y,T1>0,T=T11,waktu(T1),baris(XM),kolom(YM). . . . pion_putih1_gerakmakan(pion,putih1,T1,X1,Y1):-posisi(pion,putih1,T,X,Y), tetangga_pion_putihmakan(X1,Y1,X,Y),T1>0,T=T1-1,waktu(T1). tetangga_pion_putihmakan(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y),kolom(Y1),X1=X+1, Y1=Y+1.%pion geser satu langkah ke diagonal kanan atas tetangga_pion_putihmakan(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y),kolom(Y1),X1=X+1, Y1=Y-1.%pion geser satu langkah ke diagonal kiri atas pion_putih1_janganmakan(pion,putih1,T1,XM,YM):pion_putih1_gerakmakan(pion,putih1,T1,X1,Y1),posisi(_,putih,T,X,Y),XM=X,YM=Y,T1>0, T=T1-1,waktu(T1),baris(XM),kolom(YM). . . . %tetangga benteng tetangga_benteng(X,Y1,X,Y):-baris(X),baris(X),kolom(Y1),kolom(Y), Y1=Y+K,k(K).%benteng geser ke kanan satu s/d tujuh delapan langkah tetangga_benteng(X,Y1,X,Y):-baris(X),baris(X),kolom(Y1),kolom(Y), Y1=YK,k(K).%benteng geser ke kiri satu s/d tujuh delapanlangkah tetangga_benteng(X1,Y,X,Y):-baris(X1),baris(X),kolom(Y),kolom(Y), X1=X+K,k(K).%benteng maju satu s/d tujuh langkah tetangga_benteng(X1,Y,X,Y):-baris(X1),baris(X),kolom(Y),kolom(Y), X1=XK,k(K).%benteng mundur satu s/d tujuh delapan langkah %tetangga kuda tetangga_kuda(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y),kolom(Y1),X1=X+1, Y1=Y2.%kuda geser kiri atas membentuk huruf L tetangga_kuda(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y),kolom(Y1),X1=X+1, Y1=Y+2.%kuda geser kanan atas membentuk huruf L tetangga_kuda(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y),kolom(Y1),X1=X-1, Y1=Y2.%kuda geser kiri bawah membentuk huruf L

26

Lanjutan tetangga_kuda(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y),kolom(Y1),X1=X-1, Y1=Y+2.%kuda geser kanan bawah membentuk huruf L tetangga_kuda(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y),kolom(Y1),X1=X+2, Y1=Y1.%kuda geser kiri atas membentuk huruf L tetangga_kuda(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y),kolom(Y1),X1=X+2, Y1=Y+1.%kuda geser kanan atas membentuk huruf L tetangga_kuda(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y),kolom(Y1),X1=X-2, Y1=Y1.%kuda geser kiri bawah membentuk huruf L tetangga_kuda(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y),kolom(Y1),X1=X-2, Y1=Y+1.%kuda geser kanan bawah membentuk huruf L %tetangga pluncur tetangga_pluncur(X1,Y1,X,Y):-baris(X1),baris(X),kolom(Y1),kolom(Y), X1=X+K, Y1=Y+K,k(K).%pluncur geser diagonal kanan atas satu s/d tujuh langkah tetangga_pluncur(X1,Y1,X,Y):-baris(X1),baris(X),kolom(Y1),kolom(Y), X1=X+K, Y1=YK,k(K).%pluncur geser diagonal kiri atas satu s/d tujuh langkah tetangga_pluncur(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y1),kolom(Y), X1=X-K, Y1=YK,k(K).%pluncur geser diagonal kiri bawah satu s/d tujuh langkah tetangga_pluncur(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y1),kolom(Y), X1=X-K, Y1=Y+K,k(K).%pluncur geser diagonal kanan bawah satu s/d tujuh langkah %tetangga raja tetangga_raja(X1,Y,X,Y):-baris(X),baris(X1),kolom(Y),kolom(Y),X1=X+1.%raja maju satu langkah tetangga_raja(X1,Y,X,Y):-baris(X),baris(X1),kolom(Y),kolom(Y),X1=X-1.%raja mundur satu langkah tetangga_raja(X,Y1,X,Y):-baris(X),baris(X),kolom(Y),kolom(Y1),Y1=Y+1.%raja geser ke kanan satu langkah tetangga_raja(X,Y1,X,Y):-baris(X),baris(X),kolom(Y),kolom(Y1),Y1=Y-1.%raja geser ke kiri satu langkah tetangga_raja(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y),kolom(Y1),X1=X+1, Y1=Y+1.%raja geser satu langkah ke diagonal kanan atas tetangga_raja(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y),kolom(Y1),X1=X+1, Y1=Y1.%raja geser satu langkah ke diagonal kiri atas tetangga_raja(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y),kolom(Y1),X1=X-1, Y1=Y+1.%raja geser satu langkah ke diagonal kanan bawah tetangga_raja(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y),kolom(Y1),X1=X-1, Y1=Y1.%raja geser satu langkah ke diagonal kiri bawah %tetangga queen tetangga_queen(X,Y1,X,Y):-baris(X),baris(X),kolom(Y1),kolom(Y), Y1=Y+K,k(K).%queen geser ke kanan satu s/d tujuh delapan langkah tetangga_queen(X,Y1,X,Y):-baris(X),baris(X),kolom(Y1),kolom(Y), Y1=Y-K,k(K).%queen geser ke kiri satu s/d tujuh delapanlangkah tetangga_queen(X1,Y,X,Y):-baris(X1),baris(X),kolom(Y),kolom(Y), X1=X+K,k(K).%queen maju satu s/d tujuh langkah tetangga_queen(X1,Y,X,Y):-baris(X1),baris(X),kolom(Y),kolom(Y), X1=X-K,k(K).%queen mundur satu s/d tujuh delapan langkah tetangga_queen(X1,Y1,X,Y):-baris(X1),baris(X),kolom(Y1),kolom(Y), X1=X+K, Y1=Y+K,k(K).%queen geser diagonal kanan atas satu s/d tujuh langkah tetangga_queen(X1,Y1,X,Y):-baris(X1),baris(X),kolom(Y1),kolom(Y), X1=X+K, Y1=YK,k(K).%queen geser diagonal kiri atas satu s/d tujuh langkah tetangga_queen(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y1),kolom(Y), X1=X-K, Y1=YK,k(K).%queen geser diagonal kiri bawah satu s/d tujuh langkah tetangga_queen(X1,Y1,X,Y):-baris(X),baris(X1),kolom(Y1),kolom(Y), X1=X-K, Y1=Y+K,k(K).%queen geser diagonal kanan bawah satu s/d tujuh langkah %tetangga pion putih tetangga_pionputih(X1,Y,X,Y):-baris(X1),baris(X),kolom(Y),kolom(Y),X1=X+1.%pion putih maju ke depan satu langkah tetangga_pionputih(X1,Y,X,Y):baris(X1),baris(X),kolom(Y),kolom(Y),X1=X+2,X=2.%pion putih maju ke depan dua langkah %tetangga pion hitam tetangga_pionhitam(X1,Y,X,Y):-baris(X1),baris(X),kolom(Y),kolom(Y),X1=X-1.%pion hitam maju ke depan satu langkah tetangga_pionhitam(X1,Y,X,Y):-baris(X1),baris(X),kolom(Y),kolom(Y),X1=X2,X=7.%pion hitam maju ke depan dua langkah

27

Lampiran 2 lakukan_langkah.dl lakukan_gerak(queen,putih,1,X1,Y1) v nlakukan_gerak(queen,putih,1,X1,Y1):gerak_queen_putih(queen,putih,1,X1,Y1). :- lakukan_gerak(queen,putih,T,X1,Y1),lakukan_gerak(queen,putih,T,X2,Y2),X1!=X2. :- lakukan_gerak(queen,putih,T,X1,Y1),lakukan_gerak(queen,putih,T,X2,Y2),Y1!=Y2. . . . bergerak(1):-lakukan_gerak(_,_,1,X1,Y1). :-not bergerak(1),nlakukan_gerak(_,_,1,X2,Y2). sekak(1):-sekak_raja_hitam_oleh_1langkah(_,_,_,_,_). tidaksekak(1):-not sekak(1). :-lakukan_gerak(_,_,_,_,_),tidaksekak(1). :-lakukan_gerak(queen,putih,1,X1,Y1),lakukan_gerak(pion,putih1,1,X2,Y2). . . . posisi(benteng,hitam1,1,X,Y):posisi(benteng,hitam1,0,X,Y),lakukan_gerak(_,_,1,X1,Y1),not raja_putih_makan(benteng,hitam1,1,X1,Y1),not queen_putih_makan(benteng,hitam1,1,X1,Y1),not benteng_putih1_makan(benteng,hitam1,1,X1,Y1),not benteng_putih2_makan(benteng,hitam1,1,X1,Y1),not kuda_putih1_makan(benteng,hitam1,1,X1,Y1),not kuda_putih2_makan(benteng,hitam1,1,X1,Y1),not pluncur_putih1_makan(benteng,hitam1,1,X1,Y1),not pluncur_putih2_makan(benteng,hitam1,1,X1,Y1),not pion_putih1_makan(benteng,hitam1,1,X1,Y1),not pion_putih2_makan(benteng,hitam1,1,X1,Y1),not pion_putih3_makan(benteng,hitam1,1,X1,Y1),not pion_putih4_makan(benteng,hitam1,1,X1,Y1),not pion_putih5_makan(benteng,hitam1,1,X1,Y1),not pion_putih6_makan(benteng,hitam1,1,X1,Y1),not pion_putih7_makan(benteng,hitam1,1,X1,Y1),not pion_putih8_makan(benteng,hitam1,1,X1,Y1). . . . posisi(benteng,putih1,1,X,Y):-posisi(benteng,putih1,0,X,Y),not lakukan_gerak(benteng,putih1,1,X1,Y1),lakukan_gerak(_,_,1,X1,Y1). posisi(benteng,putih1,1,X1,Y1):posisi(benteng,putih1,0,X,Y),lakukan_gerak(benteng,putih1,1,X1,Y1). . . . sekak_raja_hitam_oleh_1langkah(benteng,putih1,1,X,Y):benteng_putih1_sekak(raja,hitam,2,X,Y),posisi(raja,hitam,1,X,Y). . . . hasilposisi(benteng,putih1,0,X,Y):-posisi(benteng,putih1,1,X,Y). . . . hasilposisi(pion,hitam8,0,X,Y):-posisi(pion,hitam8,1,X,Y).

28

Lampiran 3 periksa_sekakmate.dl sekak_raja_hitam_oleh(benteng,putih1,0,X,Y):benteng_putih1_sekak(raja,hitam,1,X,Y),posisi(raja,hitam,0,X,Y). . . . coba_sekak_raja_hitam_oleh(benteng,putih1,1,X,Y):benteng_putih1_sekak(raja,hitam,2,X,Y),posisi(raja,hitam,1,X,Y). . . . coba_gerak(raja,hitam,1,X1,Y1) v ncoba_gerak(raja,hitam,1,X1,Y1):gerak_raja_hitam(raja,hitam,1,X1,Y1). :- coba_gerak(raja,hitam,T,X1,Y1),coba_gerak(raja,hitam,T,X2,Y2),X1!=X2. :- coba_gerak(raja,hitam,T,X1,Y1),coba_gerak(raja,hitam,T,X2,Y2),Y1!=Y2. . . . dicek(2):-coba_gerak(_,_,1,X1,Y1). :-not dicek(2),ncoba_gerak(_,_,1,X2,Y2). :-coba_gerak(raja,hitam,1,X1,Y1),coba_gerak(pion,hitam1,1,X2,Y2). . . . posisi(benteng,putih1,1,X,Y):posisi(benteng,putih1,0,X,Y),coba_gerak(_,_,1,X1,Y1),not raja_hitam_makan(benteng,putih1,1,X1,Y1),not queen_hitam_makan(benteng,putih1,1,X1,Y1),not benteng_hitam1_makan(benteng,putih1,1,X1,Y1),not benteng_hitam2_makan(benteng,putih1,1,X1,Y1),not kuda_hitam1_makan(benteng,putih1,1,X1,Y1),not kuda_hitam2_makan(benteng,putih1,1,X1,Y1),not pluncur_hitam1_makan(benteng,putih1,1,X1,Y1),not pluncur_hitam2_makan(benteng,putih1,1,X1,Y1),not pion_hitam1_makan(benteng,putih1,1,X1,Y1),not pion_hitam2_makan(benteng,putih1,1,X1,Y1),not pion_hitam3_makan(benteng,putih1,1,X1,Y1),not pion_hitam4_makan(benteng,putih1,1,X1,Y1),not pion_hitam5_makan(benteng,putih1,1,X1,Y1),not pion_hitam6_makan(benteng,putih1,1,X1,Y1),not pion_hitam7_makan(benteng,putih1,1,X1,Y1),not pion_hitam8_makan(benteng,putih1,1,X1,Y1). . . . posisi(benteng,hitam1,1,X,Y):-posisi(benteng,hitam1,0,X,Y),not coba_gerak(benteng,hitam1,1,X1,Y1),coba_gerak(_,_,1,X1,Y1). posisi(benteng,hitam1,1,X1,Y1):posisi(benteng,hitam1,0,X,Y),coba_gerak(benteng,hitam1,1,X1,Y1). . . . tidakaman_gerak(1):coba_gerak(raja,hitam,1,X1,Y1),coba_sekak_raja_hitam_oleh(_,_,1,X2,Y2),sekak_raja_ hitam_oleh(_,_,0,X,Y). . . . aman_gerak(1):-not tidakaman_gerak(1). sekakmate:-tidakaman_gerak(_). sekakmate?

29

Lampiran 4 Tabel hubungan antara banyak anak catur dan waktu No Kasus

Banyak Anak Catur

Waktu (detik)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

26 11 9 27 25 19 13 22 21 21 29 17 18 10 7 18 11 23 23 31 25 26 23 13 24 24 13 19 17 14 28 15 12 24 25 13 12 14 13 17 16 12

29.50 8.79 15.08 18.88 17.99 6.25 58.56 38.15 31.20 15.07 22.40 28.50 17.04 6.39 5.87 22.26 7.84 35.38 39.54 14.84 36.76 25.40 23.53 5.12 16.75 17.18 4.22 11.30 19.73 9.12 43.10 18.43 11.22 29.57 36.08 22.70 12.20 16.60 9.44 19.62 9.44 28.79

No Kasus

Banyak Anak Catur

Waktu (detik)

43 44 45 46 47 48 49 50 51 52 53 54 55 56

11 17 17 12 18 12 17 21 14 19 16 17 18 9

10.45 19.54 12.61 6.74 59.96 9.69 18.21 28.8 38.79 25.97 7.96 24.21 39.98 5.51

57

8

4.86

58

8

6.87

59

19

35.01

60

16

7.59

61

9

5.50

62

13

3.41

63

11

11.89

64

12

15.31

65

24

22.00

66

11

17.05

67

27

36.36

68

14

8.23

69

7

3.73

70

7

2.41

71

6

2.68

72

6

9.31

73

6

4.38

74

17

15.92

75

10

27.65

30

Lampiran 5 Tabel hubungan antara ruang gerak anak catur dan waktu No Kasus

Banyak Ruang Gerak

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

223 53 15 118 160 98 802 435 371 142 143 380 229 94 144 284 117 313 349 119 347 196 181 57 167 202 87 124 297 269 376 165 221 256 250 316 194 175 185 279 240 359

Waktu (detik) 29.50 3.63 0.95 18.88 17.99 6.25 59.96 38.15 31.20 15.07 22.40 28.50 17.04 6.39 5.87 22.26 7.84 35.38 39.54 14.84 36.76 25.40 23.53 5.12 16.75 17.18 4.22 11.30 19.73 14.94 43.10 18.43 11.22 29.57 36.08 22.70 12.20 16.60 9.44 19.62 13.89 28.79

No Kasus

Banyak Ruang Gerak

43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

139 157 164 164 729 138 193 256 472 387 138 302 554 109 100 79 399 117 66 47 159 227 172 222 281 79 39 21 52 152 52 215 348

Waktu (detik) 10.45 19.54 12.61 6.74 58.56 9.69 18.21 28.80 38.79 25.97 7.96 24.21 39.98 5.51 4.86 6.87 35.01 7.59 5.50 3.41 11.89 15.31 22.00 17.05 36.36 8.23 3.73 2.41 2.68 9.31 4.38 15.92 27.65