KECERDASAN BUATAN UNTUKMENYELESAIKAN RUBIKS CUBE DENGAN

ALGORITMA IDA*

Ardhan Wahyu R1, Purwanto2, dan Susy Kuspambudi A3

Universitas Negeri MalangE-mail: ardhan.matematika@gmail.com; purmatum@yahoo.com; susyka06@yahoo.co.id

ABSTRAK: Tujuan dari penelitian ini adalah untuk (1) mengetahui caramerepresentasikan masalah pada rubiks cube agar dapat diselesaikan dengan algoritmaIDA*, (2) mengetahui cara kerja algoritma IDA* untuk menyelesaikan rubiks cubeyang telah direpresentasi, (3) membuat sebuah program kecerdasan buatan terkaitmenggunakan bahasa Java. Dalam hal ini rubiks cube direpresentasikan ke dalambentuk 2 dimensi. Hasil dari penelitian ini adalah (1) rubiks cube dapat diselesaikandengan kecerdasan buatan, (2) langkah-langkah yang terdapat dalam algoritma dapatdibuat dalam bentuk program kecerdasan buatan yang dapat menyelesaikan rubikscube, (3) tidak semua keadaan awal dari rubiks cube dapat diselesaikan dengan programkecerdasan buatan yang telah dikembangkan.

Kata kunci: rubiks cube, algoritma IDA*, Java

Rubiks cube adalah permainan berjenis teka-teki. Berdasarkan Wikipedia(2013) rubiks cube dikenalkan pada tahun 1974 oleh profesor berkebangsaanHungaria bernama Erno Rubik. Rubiks cube disusun oleh kubus-kubus kecilsebanyak 3 3 3. Setiap kubus kecil ini memiliki warna yang berbeda. Setiapbagian 3 3 1 dapat dirotasi 800, 900, atau 2700. Rotasi yang dilakukanmengakibatkan warna dari salah satu sisi berpindah ke sisi yang lain sehinggasusunan warna sisinya berubah. Tujuan memainkan rubiks cube adalah menyusunwarna pada sisinya dari kondisi yang acak ke kondisi dimana setiap sisi hanyamemiliki satu warna.

Masalah yang terdapat pada rubiks cube adalah bagaiamana caranya agarrubiks cube dalam keadaan acak dapat kembali pada keadaan yang tersusun.Untuk menyelesaikan masalah tersebut dapat digunakan algoritma Frederich LayerMethod, Waterman Method dan Waterman Method yang merupakan algoritmayang dirancang khusus untuk menyelesaikan rubiks cube. Ketiga algoritmatersebut tidak dapat memberikan langkah terpendek untuk menyelesaikan rubikscube. Yang menjadi masalah selanjutnya adalah bagaiamana caranya agar rubikscube kembali pada keadaan yang tersusun dengan langkah terpendek.

Untuk menjawab permasalahan yang terdapat pada rubiks cube dapatdikembangkan suatu kecerdasan buatan. Seperti yang dikatakan oleh Kusumadewi(2003:1) bahwa Kecerdasan buatan atau artificial intelligence merupakan salahsatu bagian ilmu komputer yang membuat agar mesin (komputer) dapatmelakukan pekerjaan seperti dan sebaik yang dilakukan manusia. Kecerdasanbuatan yang dikembangkan bertujuan menemukan solusi dari rubiks cube.

1Ardhan Wahyu R adalah mahasiswa Jurusan Matematika FMIPA Universitas Negeri Malang2Purwanto adalah dosen Jurusan Matematika FMIPA Universitas Negeri Malang3Susy Kuspambudi A adalah dosen Jurusan Matematika FMIPA Universitas Negeri Malang

Kecerdasan buatan ini menggunakan algoritma IDA* dengan nilai heuristikpattern database.

PEMBAHASANAda 4 tahapan utama yang dilakukan untuk mengembangkan kecerdasan

buatan untuk menyelesaikan rubiks cube, yaitu:

1. Merepresentasikan bentuk rubiks cube ke dalam 2 dimensiRussel dan Norvig (2010:108) menyatakan bahwa masalah terdiri dari 5

bagian dan salah satunya adalah model peralihan. Model peralihan bisa jugadisebut dengan representasi. Artinya masalah yang awalnya terlihat sangat rumitdapat direpresentasi menjadi yang lebih sederhana dengan bentuk lain(representasi lain). Dalam hal ini rubiks cube yang sebelumnya berbentuk 3dimensi direpresentasi ke dalam bentuk 2 dimensi dengan cara membukasisi-sisinya. Karena bentuk rubiks cube direpresentasi maka operasi juga harusdirepresentasi. Sebelum direpresentasi operasi pada rubiks cube adalah rotasiterhadap layer. Setelah direpresentasi operasi pada rubiks cube adalahpemindahan warna. Gambar 1 menunjukkan gambar dari rubiks cube yangdirepresentasikan ke dalam bentuk 2 dimensi.

Gambar 1: Representasi Rubiks Cube

Tabel 1 menunjukkan operasi yang dilakukan pada rubik yang telahdirepresentasi.

2. Membangun pattern database yang digunakan sebagai nilai heuristikSuyanto (2011) menyatakan bahwa heuristik adalah suatu proses yang

mungkin dapat menyelesaikan suatu masalah tetapi tidak ada jaminan bahwasolusi yang dicari selalu ditemukan. Yang ditekankan adalah tidak adanyajaminan. Sementara itu Poole dan Mackworth (2010:56) menyatakan bahwa fungsiheuristik adalah fungsi untuk menebak arah mana yang akan ditempuh agarmencapai solusi. Fungsi heuristik menghasilkan nilai heuristik yang merupakannilai yang digunakan untuk menebak arah pencarian. Salah satu yang dapatdigunakan sebagai nilai heuristik adalah Pattern database. Culberson danSchaeffer (1998:321) menyatakan bahwa Pattern database basis data yang berisikeadaan-keadaan yang mungkin yang didapatkan dari hasil permutasi keadaanawal. Pattern database untuk rubiks cube adalah keadaan-keadaan dari rubikscube yang diperoleh dari hasil permutasi keadaan tujuan. Korf (1997) membagirubiks cube menjadi 3 pola untuk disimpan dalam basis data. Hal ini dilakukan

Tabel 1 Operasi Rubiks Cube 2 Dimensi

Front Back Up Down Right Left

Warna Warna Warna Warna Warna Warna

Di Ke Di Ke Di Ke Di Ke Di Ke Di Ke

1 3 28 30 46 48 19 21 10 12 37 39

3 9 30 36 48 54 21 27 12 18 39 45

9 7 36 34 54 52 27 25 18 16 45 43

7 1 34 28 52 46 25 19 16 10 43 37

54 16 18 48 36 12 16 28 54 30 34 46

16 25 48 39 12 3 28 37 30 21 46 1

25 45 39 27 3 45 37 7 21 9 1 25

45 54 27 18 45 36 7 16 9 54 25 34

52 10 12 46 30 10 18 34 48 28 36 52

10 19 46 37 10 1 34 43 28 29 52 7

19 43 37 21 1 39 43 9 19 3 7 27

43 54 21 12 39 30 9 18 3 48 27 36

2 6 29 33 47 51 20 24 11 15 38 42

6 8 33 35 51 53 24 26 15 17 42 44

8 4 35 31 53 49 26 22 17 13 44 40

4 2 31 29 49 47 22 20 13 11 40 38

53 13 15 47 33 11 17 31 51 29 35 49

13 22 47 38 11 2 31 40 29 20 49 4

22 44 38 24 2 42 40 8 20 6 4 26

44 53 24 15 42 33 8 17 6 51 26 35

agar pola yang disimpan tidak terlalu besar. Pembagian tersebut ditunjukkanpada Gambar 2.

Gambar 2: Pembagian pola

Pattern database untuk rubiks cube ini dibangun dengan menggunakanalgoritma DLS (Depth Limited Search). Gambar 3 menunjukkan diagram alir darialgoritma DLS untuk membangun pattern database.

Gambar 3: Diagram Alir untuk Membangung Pattern Database

Jika proses membangun pattern database telah selesai maka akandidapatkan suatu basis data yang berisi keadaan dari rubiks cube beserta nilainya.Table 2 menunjukkan contoh dari basis data dengan nilai 1.

Tabel 2 Pola 1 Dengan Nilai 1

Keadaan untuk pola 1 Nilai (kedalaman)

MMMMOOOOPBPBHHKKPPHHBKBK 1

PPMMOKOKOOPPKMKMHHHHBBBB 1

MMKKPOPOPPMMOKOKHHHHBBBB 1

MBMBHHOOPPPPKKKKHMHMOOBB 1

HMHMOOBBPPPPKKKKOHOHBBMM 1

MMMMOOOOBPBPKKHHHHPPKBKB 1

MMMMOOOOPHPHBBKKKKHHBPBP 1

KKMMOPOPMMPPKOKOHHHHBBBB 1

MMPPKOKOPPOOMKMKHHHHBBBB 1

MHMHBBOOPPPPKKKKHOHOMMBB 1

BMBMOOHHPPPPKKKKMHMHBBOO 1

MMMMOOOOKPKPKKPPHHBBHBHB 1

MMMMOOOOPKPKPPKKBBHHBHBH 1

MOMOMMOOPPPPKKKKHBHBHHBB 1

3. Mencari solusi dengan menggunakan algoritma IDA*Algoritma IDA* merupakan salah satu algoritma yang termasuk dalam

kategori pencarian terbimbing sehingga pencarian yang dilakukan denganmenggunakan algoritma IDA* bergantung dari nilai heuristik. Yang digunakansebagai nilai heuristik adalah nilai yang terdapat pada pattern database. Gambar 4menunjukkan diagram alir dari algoritma IDA* untuk mencari solusi dari rubikscube.

Gambar 4: Diagram Alir Algoritma IDA*

Diagram alir pada Gambar 4 menggunakan DFS CONTOUR. Diagram alir dariDFS CONTOUR ditunjukkan pada Gambar 5.

Gambar 5: Diagram Alir DFS CONTOUR

Algoritma IDA* ini menerima masukkan berupa keadaan rubiks cube yang acakdan mengembalikan solusi dari rubiks cube.

4. Membuat program kecerdasan buatan dengan bahasa JavaTahap terakhir adalah mengembangkan suatu program kecerdasan buatan

menggunakan bahasa pemrograman Java. Bahasa Java merupakan karya SunMicrosystem Inc. Rilis resmi level beta dilakukan pada November 1995(Hariyanto, 2010:1). Bahasa Java adalah bahasa pemrogram berorientasi objek.Eck (2011:169) menyatakan bahwa gaya objek lebih dekat dengan cara orangberpikir. Cara mengembangkan program kecerdasan buatan dengan bahasa Javaadalah dengan membangun kelas-kelas yang dibutuhkan. Tabel 3 menunjukkankelas-kelas yang dibangun beserta kegunaanya.

Tabel 3 Kelas-kelas Dalam Program Kecerdasan Buatan

Nama Kelas Kegunaan

Rubik.java Merepresentasikan obyek rubiks cube ke dalam sebuah kelas.

BangunHeuristik.java Membangun pattern database untuk rubiks cube.

IDAstar.java Mencari solusi dari rubiks cube.

Stack.java Kelas yang berfungsi sebagai tipe data tumpukan (stack).

Koneksi.java Menghubungkan program dengan basis data. Kelas ini memanfaatkanpustaka dari MySQL Connector/J yang berfungsi menghubungkan programdengan basis data MySQL.

FUtama.java Tampilan utama dari program.

FHeuristik.java Tampilan untuk memasukkan heuristik dan melihat kedalamanya.

FInput.java Membuat keadaan awal dari rubiks cube yang ingin dicari solusinya.

Gambar.java Tampilan gambar untuk rubiks cube 2 dimensi.

FPencarian.java Menampilkan hasil pencarian solusi.

Dari penelitian ini dihasilkan sebuah program kecerdasan buatan yang dapatmenyelesaikan rubiks cube. Gambar 6 menunjukkan antar muka dari program.

Gambar 6: Antar Muka Program Kecerdasan Buatan

Program kecerdasan buatan ini mampu menemukan solusi terpendek untukmenyelesaikan rubiks cube, akan tetapi tidak semua keadaan dapat diselesaikandengan program ini. Keadaan yang mampu diselesaikan oleh program ini adalahkeadaan rubiks cube yang diacak dengan menggunakan maksimal 6 operasi. Table4 menunjukkan beberapa contoh keadaan dari rubiks cube yang solusinyaditemukan.

Tabel 4 Pengujian Beberapa Keadaan Awal

Keadaan Awal TitikWaktu(mili detik)

Solusi

19 1674 L1

34 1219 U1F1

83 1068 B1U1F1

79 894 D1B1U1F1R1U

PENUTUPKesimpulan

Kecerdasan buatan dengan algoritma IDA* dapat menemukan solusi darirubiks cube yang sebelumnya telah direpresentasi ke dalam bentuk 2 dimensi.Untuk dapat menemukan solusi, algoritma memanfaatkan pattern database sebagainilai heuristik. Semakin banyak data yang tersimpan pada patttern database makaakan semakin baik pencarian yang dilakukan oleh kecerdasan buatan ini. Akantetapi, basis data yang digunakan pada kecerdasan buatan ini tidak sanggupmenyimpan data sebanyak yang ditargetkan.

SaranBerdasarkan kesimpulan di atas, maka disarankan untuk mencoba mencari

alternatif basis data yang dapat digunakan untuk menyimpan data lebih banyakkarena basis data yang digunakan pada kecerdasan buatan ini hanya mampumenyimpan semua data dengan maksimal 6 operasi. Dengan data yang lebihbanyak, kecerdasan buatan ini akan bekerja dengan lebih baik.

DAFTAR RUJUKANCulberson, Joseph C & Schaeffer, Jonathan. 1998.Pattern Database, (Online),

(http://www.cs.us.es/cursos/ia1-2007/trabajos/trabajos-1/pattern-database.pdf), diakses 6 Mei 2011.

Eck, David J. 2011.Introduction to Programming Using Java, Sixth Edition,(Online), (http://math.hws.edu/eck/cs124/downloads/ javanotes6.pdf),diakses 6 Mei 2011.

Hariyanto, Bambang. 2010. Esensi-Esensi Bahasa Pemrograman Java. Bandung:Informatika.

Korf, Richard E. 1997. Finding Optimal Solutions to Rubiks Cube Using PatternDatabases, (Online), (http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf), diakses 6 Mei 2013.

Kusumadewi, Sri. 2003. Artificial Intelligence: Teknik dan Aplikasinya.Yogjakarta: Graha Ilmu.

Poole, David L & Mackworth, Alan K. 2010. Artificial Intelligence: Foundations ofComputational Agents, Cambridge: Cambridge University Press.

Russell, Stuart & Norvig, Peter. 2010. Artificial Intelligence: A Modern Approach(Third Edition). New Jersey: Prentice Hall.

Suyanto. 2011. Artificial Intelligence: Searching, Reasoning, Planning andLearning. Bandung: Informatika.

Wikipedia. 2013. Rubiks Cube, (Online), (http://en.wikipedia.org/Rubiks Cube),diakses 22 Juli 2013.