KECERDASAN BUATAN UNTUK MENYELESAIKAN RUBIK’S CUBE DENGAN ALGORITMA IDA* Ardhan Wahyu R1 , Purwanto2 , dan Susy Kuspambudi A3 Universitas Negeri Malang E-mail:
[email protected];
[email protected];
[email protected]
ABSTRAK: Tujuan dari penelitian ini adalah untuk (1) mengetahui cara merepresentasikan masalah pada rubik’s cube agar dapat diselesaikan dengan algoritma IDA*, (2) mengetahui cara kerja algoritma IDA* untuk menyelesaikan rubik’s cube yang telah direpresentasi, (3) membuat sebuah program kecerdasan buatan terkait menggunakan bahasa Java. Dalam hal ini rubik’s cube direpresentasikan ke dalam bentuk 2 dimensi. Hasil dari penelitian ini adalah (1) rubik’s cube dapat diselesaikan dengan kecerdasan buatan, (2) langkah-langkah yang terdapat dalam algoritma dapat dibuat dalam bentuk program kecerdasan buatan yang dapat menyelesaikan rubik’s cube, (3) tidak semua keadaan awal dari rubik’s cube dapat diselesaikan dengan program kecerdasan buatan yang telah dikembangkan. Kata kunci: rubik’s cube, algoritma IDA*, Java
Rubik’s cube adalah permainan berjenis teka-teki. Berdasarkan Wikipedia (2013) rubik’s cube dikenalkan pada tahun 1974 oleh profesor berkebangsaan Hungaria bernama Erno Rubik. Rubik’s cube disusun oleh kubus-kubus kecil sebanyak 3 × 3 × 3. Setiap kubus kecil ini memiliki warna yang berbeda. Setiap bagian 3 × 3 × 1 dapat dirotasi 800 , 900 , atau 2700 . Rotasi yang dilakukan mengakibatkan warna dari salah satu sisi berpindah ke sisi yang lain sehingga susunan warna sisinya berubah. Tujuan memainkan rubik’s cube adalah menyusun warna pada sisinya dari kondisi yang acak ke kondisi dimana setiap sisi hanya memiliki satu warna. Masalah yang terdapat pada rubik’s cube adalah bagaiamana caranya agar rubik’s cube dalam keadaan acak dapat kembali pada keadaan yang tersusun. Untuk menyelesaikan masalah tersebut dapat digunakan algoritma Frederich Layer Method, Waterman Method dan Waterman Method yang merupakan algoritma yang dirancang khusus untuk menyelesaikan rubik’s cube. Ketiga algoritma tersebut tidak dapat memberikan langkah terpendek untuk menyelesaikan rubik’s cube. Yang menjadi masalah selanjutnya adalah bagaiamana caranya agar rubik’s cube kembali pada keadaan yang tersusun dengan langkah terpendek. Untuk menjawab permasalahan yang terdapat pada rubik’s cube dapat dikembangkan suatu kecerdasan buatan. Seperti yang dikatakan oleh Kusumadewi (2003:1) bahwa Kecerdasan buatan atau artificial intelligence merupakan salah satu bagian ilmu komputer yang membuat agar mesin (komputer) dapat melakukan pekerjaan seperti dan sebaik yang dilakukan manusia. Kecerdasan buatan yang dikembangkan bertujuan menemukan solusi dari rubik’s cube. 1
Ardhan Wahyu R adalah mahasiswa Jurusan Matematika FMIPA Universitas Negeri Malang Purwanto adalah dosen Jurusan Matematika FMIPA Universitas Negeri Malang 3 Susy Kuspambudi A adalah dosen Jurusan Matematika FMIPA Universitas Negeri Malang 2
Kecerdasan buatan ini menggunakan algoritma IDA* dengan nilai heuristik pattern database. PEMBAHASAN Ada 4 tahapan utama yang dilakukan untuk mengembangkan kecerdasan buatan untuk menyelesaikan rubik’s cube, yaitu: 1. Merepresentasikan bentuk rubik’s cube ke dalam 2 dimensi Russel dan Norvig (2010:108) menyatakan bahwa masalah terdiri dari 5 bagian dan salah satunya adalah model peralihan. Model peralihan bisa juga disebut dengan representasi. Artinya masalah yang awalnya terlihat sangat rumit dapat direpresentasi menjadi yang lebih sederhana dengan bentuk lain (representasi lain). Dalam hal ini rubik’s cube yang sebelumnya berbentuk 3 dimensi direpresentasi ke dalam bentuk 2 dimensi dengan cara membuka sisi-sisinya. Karena bentuk rubik’s cube direpresentasi maka operasi juga harus direpresentasi. Sebelum direpresentasi operasi pada rubik’s cube adalah rotasi terhadap layer. Setelah direpresentasi operasi pada rubik’s cube adalah pemindahan warna. Gambar 1 menunjukkan gambar dari rubik’s cube yang direpresentasikan ke dalam bentuk 2 dimensi.
Gambar 1: Representasi Rubik’s Cube Tabel 1 menunjukkan operasi yang dilakukan pada rubik yang telah direpresentasi. 2. Membangun pattern database yang digunakan sebagai nilai heuristik Suyanto (2011) menyatakan bahwa heuristik adalah suatu proses yang mungkin dapat menyelesaikan suatu masalah tetapi tidak ada jaminan bahwa solusi yang dicari selalu ditemukan. Yang ditekankan adalah tidak adanya jaminan. Sementara itu Poole dan Mackworth (2010:56) menyatakan bahwa fungsi heuristik adalah fungsi untuk menebak arah mana yang akan ditempuh agar mencapai solusi. Fungsi heuristik menghasilkan nilai heuristik yang merupakan nilai yang digunakan untuk menebak arah pencarian. Salah satu yang dapat digunakan sebagai nilai heuristik adalah Pattern database. Culberson dan Schaeffer (1998:321) menyatakan bahwa Pattern database basis data yang berisi keadaan-keadaan yang mungkin yang didapatkan dari hasil permutasi keadaan awal. Pattern database untuk rubik’s cube adalah keadaan-keadaan dari rubik’s cube yang diperoleh dari hasil permutasi keadaan tujuan. Korf (1997) membagi rubik’s cube menjadi 3 pola untuk disimpan dalam basis data. Hal ini dilakukan
Tabel 1 Operasi Rubik’s Cube 2 Dimensi Front Warna Di Ke 1 3 3 9 9 7 7 1 54 16 16 25 25 45 45 54 52 10 10 19 19 43 43 54 2 6 6 8 8 4 4 2 53 13 13 22 22 44 44 53
Back Warna Di Ke 28 30 30 36 36 34 34 28 18 48 48 39 39 27 27 18 12 46 46 37 37 21 21 12 29 33 33 35 35 31 31 29 15 47 47 38 38 24 24 15
Up Warna Di Ke 46 48 48 54 54 52 52 46 36 12 12 3 3 45 45 36 30 10 10 1 1 39 39 30 47 51 51 53 53 49 49 47 33 11 11 2 2 42 42 33
Down Warna Di Ke 19 21 21 27 27 25 25 19 16 28 28 37 37 7 7 16 18 34 34 43 43 9 9 18 20 24 24 26 26 22 22 20 17 31 31 40 40 8 8 17
Right Warna Di Ke 10 12 12 18 18 16 16 10 54 30 30 21 21 9 9 54 48 28 28 29 19 3 3 48 11 15 15 17 17 13 13 11 51 29 29 20 20 6 6 51
Left Warna Di Ke 37 39 39 45 45 43 43 37 34 46 46 1 1 25 25 34 36 52 52 7 7 27 27 36 38 42 42 44 44 40 40 38 35 49 49 4 4 26 26 35
agar pola yang disimpan tidak terlalu besar. Pembagian tersebut ditunjukkan pada Gambar 2.
Gambar 2: Pembagian pola Pattern database untuk rubik’s cube ini dibangun dengan menggunakan algoritma DLS (Depth Limited Search). Gambar 3 menunjukkan diagram alir dari algoritma DLS untuk membangun pattern database.
Gambar 3: Diagram Alir untuk Membangung Pattern Database Jika proses membangun pattern database telah selesai maka akan didapatkan suatu basis data yang berisi keadaan dari rubik’s cube beserta nilainya. Table 2 menunjukkan contoh dari basis data dengan nilai 1. Tabel 2 Pola 1 Dengan Nilai 1 Keadaan untuk pola 1 MMMMOOOOPBPBHHKKPPHHBKBK PPMMOKOKOOPPKMKMHHHHBBBB MMKKPOPOPPMMOKOKHHHHBBBB MBMBHHOOPPPPKKKKHMHMOOBB HMHMOOBBPPPPKKKKOHOHBBMM MMMMOOOOBPBPKKHHHHPPKBKB MMMMOOOOPHPHBBKKKKHHBPBP KKMMOPOPMMPPKOKOHHHHBBBB MMPPKOKOPPOOMKMKHHHHBBBB MHMHBBOOPPPPKKKKHOHOMMBB BMBMOOHHPPPPKKKKMHMHBBOO MMMMOOOOKPKPKKPPHHBBHBHB MMMMOOOOPKPKPPKKBBHHBHBH MOMOMMOOPPPPKKKKHBHBHHBB
Nilai (kedalaman) 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3. Mencari solusi dengan menggunakan algoritma IDA* Algoritma IDA* merupakan salah satu algoritma yang termasuk dalam kategori pencarian terbimbing sehingga pencarian yang dilakukan dengan menggunakan algoritma IDA* bergantung dari nilai heuristik. Yang digunakan sebagai nilai heuristik adalah nilai yang terdapat pada pattern database. Gambar 4 menunjukkan diagram alir dari algoritma IDA* untuk mencari solusi dari rubik’s cube.
Gambar 4: Diagram Alir Algoritma IDA* Diagram alir pada Gambar 4 menggunakan DFS CONTOUR. Diagram alir dari DFS CONTOUR ditunjukkan pada Gambar 5.
Gambar 5: Diagram Alir DFS CONTOUR Algoritma IDA* ini menerima masukkan berupa keadaan rubik’s cube yang acak dan mengembalikan solusi dari rubik’s cube. 4. Membuat program kecerdasan buatan dengan bahasa Java Tahap terakhir adalah mengembangkan suatu program kecerdasan buatan menggunakan bahasa pemrograman Java. ”Bahasa Java merupakan karya Sun Microsystem 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 orang berpikir. Cara mengembangkan program kecerdasan buatan dengan bahasa Java adalah dengan membangun kelas-kelas yang dibutuhkan. Tabel 3 menunjukkan kelas-kelas yang dibangun beserta kegunaanya.
Tabel 3 Kelas-kelas Dalam Program Kecerdasan Buatan Nama Kelas Rubik.java BangunHeuristik.java IDAstar.java Stack.java Koneksi.java
FUtama.java FHeuristik.java FInput.java Gambar.java FPencarian.java
Kegunaan Merepresentasikan obyek rubik’s cube ke dalam sebuah kelas. Membangun pattern database untuk rubik’s cube. Mencari solusi dari rubik’s cube. Kelas yang berfungsi sebagai tipe data tumpukan (stack ). Menghubungkan program dengan basis data. Kelas ini memanfaatkan pustaka dari MySQL Connector/J yang berfungsi menghubungkan program dengan basis data MySQL. Tampilan utama dari program. Tampilan untuk memasukkan heuristik dan melihat kedalamanya. Membuat keadaan awal dari rubik’s cube yang ingin dicari solusinya. Tampilan gambar untuk rubik’s cube 2 dimensi. Menampilkan hasil pencarian solusi.
Dari penelitian ini dihasilkan sebuah program kecerdasan buatan yang dapat menyelesaikan rubik’s cube. Gambar 6 menunjukkan antar muka dari program.
Gambar 6: Antar Muka Program Kecerdasan Buatan Program kecerdasan buatan ini mampu menemukan solusi terpendek untuk menyelesaikan rubik’s cube, akan tetapi tidak semua keadaan dapat diselesaikan dengan program ini. Keadaan yang mampu diselesaikan oleh program ini adalah keadaan rubik’s cube yang diacak dengan menggunakan maksimal 6 operasi. Table 4 menunjukkan beberapa contoh keadaan dari rubik’s cube yang solusinya ditemukan.
Tabel 4 Pengujian Beberapa Keadaan Awal Keadaan Awal
Titik
Waktu (mili detik)
Solusi
19
1674
L−1
34
1219
U −1 F −1
83
1068
B −1 U −1 F −1
79
894
D−1 B −1 U −1 F −1 R−1 U
PENUTUP Kesimpulan Kecerdasan buatan dengan algoritma IDA* dapat menemukan solusi dari rubik’s cube yang sebelumnya telah direpresentasi ke dalam bentuk 2 dimensi. Untuk dapat menemukan solusi, algoritma memanfaatkan pattern database sebagai nilai heuristik. Semakin banyak data yang tersimpan pada patttern database maka akan semakin baik pencarian yang dilakukan oleh kecerdasan buatan ini. Akan tetapi, basis data yang digunakan pada kecerdasan buatan ini tidak sanggup menyimpan data sebanyak yang ditargetkan.
Saran Berdasarkan kesimpulan di atas, maka disarankan untuk mencoba mencari alternatif basis data yang dapat digunakan untuk menyimpan data lebih banyak karena basis data yang digunakan pada kecerdasan buatan ini hanya mampu menyimpan semua data dengan maksimal 6 operasi. Dengan data yang lebih banyak, kecerdasan buatan ini akan bekerja dengan lebih baik.
DAFTAR RUJUKAN Culberson, 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 Rubik’s Cube Using Pattern Databases, (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 of Computational 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 and Learning. Bandung: Informatika. Wikipedia. 2013. Rubik’s Cube, (Online), (http://en.wikipedia.org/Rubik’s Cube), diakses 22 Juli 2013.
