BAB 2
LANDASAN TEORI
2.1 Kecerdasan Buatan
Kecerdasan buatan atau Artificial Intelligence adalah bagian dari ilmu pengetahuan komputer yang khusus ditujukan dalam perancangan otomatisasi tingkah laku cerdas dalam sistem kecerdasan komputer. Sistem memperlihatkan sifat-sifat khas yang dihubungkan dengan kecerdasan dalam kelakukan atau tindak-tanduk yang sepenuhnya bisa menirukan beberapa fungsi otak manusia, seperti pengertian bahasa, pengetahuan, pemikiran, pemecahan masalah dan lain sebagainya (Kristanto, 2004). Pengertian Artificial Intelligence dapat ditinjau dari dua pendekatan (Charniack dan McDermott, 1985):
1. Pendekatan Ilmiah (A Scientific Approach) Pendekatan dasar ilmiah timbul sebelum invansi ke komputer, ini tidak sama dengan kasus mesin uap. Pendekatan ilmiah melihat batas sementara dari komputer, dan dapat diatasi dengan perkembangan teknologi lanjutan. Mereka tidak mengakibatkan tingkatan pada konsep.
2. Pendekatan Teknik (An Engineering Approach) Usaha untuk menghindari definisi AI, tetapi ingin mengatasi atau memecahkan persoalan dunia nyata (real world problem).
Pada Gambar 2.1, penjelasan mengenai defenisi kecerdasan buatan adalah, AI dapat membuat sebuah sistem komputer berpikir seperti manusia dan sistem komputer dapat berpikir secara rasional (masuk akal). AI dapat membuat sistem komputer
Universitas Sumatera Utara
7 bertingkah laku seperti manusia dan sistem komputer dapat bertingkah laku yang diterima logika/masuk akal kita.
What is AI? Systems that think like humans
Systems that think rationally
Systems that act like humans
Systems that act rationally
Gambar 2.1 Definisi kecerdasan buatan dalam 4 kategori (Russell, et al, 2010)
Kecerdasan buatan dilihat dari berbagai sudut pandang, antara lain:
1. Sudut pandang kecerdasan Mesin menjadi cerdas (mampu berbuat apa yang dilakukan oleh manusia).
2. Sudut pandang penelitian Studi tentang bagaimana membuat agar komputer dapat melakukan sesuatu sebaik yang dilakukan manusia. Domain penelitian/tugas
yang sering dibahas oleh para peneliti dapat
dikelompokkan menjadi 3 yaitu (Rich dan Knight, 1991):
a. Mundane task 1. Persepsi (vision & speech) 2. Bahasa alami (understanding, generation & translation) 3. Pemikiran yang bersifat commonsense 4. Robot control
b. Formal task 1. Permainan (games) 2. Matematika (geometri, logika, kalkulus, integral, pembuktian)
c. Expert task 1. Analisis finansial 2. Diagnosa medis
Universitas Sumatera Utara
8 3. Analisis ilmu pengetahuan 4. Rekayasa (desain, pencarian, kegagalan, perencanaan, manufaktur)
3. Sudut pandang bisnis Kumpulan peralatan yang sangat powerful dan metodologis dalam menyelesaikan masalah-masalah bisnis.
4. Sudut pandang pemrograman Studi tentang pemrograman simbolik, penyelesaian masalah (problem solving) dan pencarian (searching).
Maksud dari 3 kelompok tugas yang diklasifikasikan oleh Rich dan Knight di atas antara lain (Siswanto, 2010):
1. Tugas biasa/keduniaan (Mundane Tasks) Contoh tugas biasa yang merupakan kebisaaan kita, yaitu sebagai dosen, mahasiswa, pegawai, karyawan, customer service, teller atau pekerjaan makan, di mana kita dalam menyelesaikan pekerjaan harus memahami (menyamakan persepsi yang kita lihat (vision) atau yang diucapkan (speech), disamping itu kita harus mengerti atau menerjemahkan atau memunculkan bahasa alami yang biasa kita pakai dalam pekerjaan serta harus dikendalikan dengan pertimbangan berdasarkan pikiran yang sehat. Kita tidak dapat mengerjakan tugas bila diperintahkan oleh pemberi pekerjaan: objeknya tidak terlihat, tidak ada yang diucapkan/menyuruh serta tidak mengerti bahasa pengantarnya dan pikiran lagi tidak sehat).
2. Tugas formil (Formal Tasks) Contoh tugas formil yang dapat selesai bila aturan formalnya terpenuhi, yaitu: Atlet Nasional, Pilot, Polisi, Tentara TNI, Programmer, Debugger, yang kesemuanya membutuhkan kemampuan logika terbaik.
3. Tugas ahli (Expert Tasks) Contoh tugas yang dapat diselesaikan bila ahlinya ada, yaitu: tenaga ahli di berbagai bidang, dokter spesialis, montir ahli, peneliti senior, dan sebagainya.
Universitas Sumatera Utara
9 Seperti pada bidang sains lainnya, kecerdasan juga memiliki beberapa sub-disiplin ilmu. Beberapa macam bidang terapan utama kecerdasan buatan antara lain (Setiawan, 1993):
1. Sistem Pakar Sistem pakar dibuat dengan mendapatkan pengetahuan dari seorang manusia yang pakar dan mengodekannya ke dalam bentuk yang dapat digunakan oleh komputer bila komputer menghadapi persoalan sejenis. Sifat utama sistem pakar adalah ketergantungan sistem ini pada pengetahuan manusia yang pakar dalam suatu bidang dalam menyusun strategi pemecahan persoalan yang dihadapi oleh sistem.
2. Perencanaan (Planning) dan Robotik Perencanaan merupakan sebuah aspek penting dalam usaha merancang robot yang mampu melaksanakan tugasnya sampai suatu derajat keluwesan dan keresposifan tertentu. Mengatur rencana yang memungkinkan adanya respon terhadap kondisi lingkungan merupakan salah satu problema besar dalam hal perencanaan. Salah satu cara yang kita gunakan dalam perencanaan adalah dengan komposisi problema secara hirarki.
3. Pemodelan Kinerja (Performance) Manusia Pemodelan kinerja manusia telah terbukti merupakan alat yang sangat bermanfaat dalam merumuskan dan menguji teori-teori penerapan inderawi manusia.
4. Bahasa Alamiah (Natural Language), Pemodelan Semantik, dan Mesin yang Dapat Belajar (Learning Machine) Salah satu tujuan jangka panjang kecerdasan buatan adalah pembuatan program yang memiliki kemampuan untuk memahami bahasa manusia. Tidak hanya kemampuan komputer dalam memahami bahasa alamiah saja yang tampaknya merupakan salah satu aspek dasar dari kecerdasan manusia, namun otomasi yang berhasil darinya juga memiliki pengaruh yang sangat besar pada kemampuan penggunaannya dan keefektifannya.
Universitas Sumatera Utara
10 5. Permainan (Games) Kebanyakan permainan dilakukan dengan menggunakan sekumpulan peraturan. Dalam permainan digunakan apa yang disebut dengan pencarian ruang keadaan (state space search). Teknik untuk menentukan alternatif dalam menyimak problema ruang merupakan sesuatu yang rumit. Teknik yang menggeluti hal ini disebut dengan heuristic. Dalam studi heuristic, permainan merupakan bidang yang sangat menarik.
2.2 Permainan Pergeseran Angka
Permainan (games) merupakan satu dari banyak area dalam kecerdasan buatan yang paling menarik dan dipublikasikan dengan baik. Dengan keberhasilan Deep Blue tahun 1997, sebuah landmark dicapai, yaitu sebuah program komputer yang bisa mengalahkan pemain catur terbaik dunia (Coppin, 2004). Ide games pertama kali dimunculkan oleh Claude Shannon tahun 1950 yang menulis paper tentang mekanisme pembuatan program permainan catur. Beberapa tahun kemudian, Alan Turing menjelaskan program permainan catur walaupun ia sendiri belum pernah membuat rancangan program. Baru pada awal tahun 1960-an Arthur Samuel mencoba untuk membuat program catur tersebut (Sigiro, 2011). Gameplay merupakan alat dan aturan-aturan yang mendeskripsikan konteks keseluruhan permainan sehingga pada saat gilirannya, menghasilkan keterampilan, strategi, dan kesempatan (Bakri, 2010). Salah satu jenis Gameplay adalah permainan pergeseran angka. Permainan pergeseran angka biasanya dimainkan dalam kotak berbentuk persegi atau persegi panjang. Jika dalam kotak berbentuk persegi maka permainan ini dikenal dengan nama N-Puzzle. N-Puzzle merupakan permainan teka-teki untuk mencari langkah agar puzzle yang berisi sekumpulan angka dapat terurut. N-Puzzle dengan jumlah ubin 3x3 juga dikenal dengan nama 8-puzzle. Sesuai namanya, 8puzzle terdiri dari 8 kotak dan 1 tempat kosong yang bisa digerakkan dengan aturan tertentu. Aturan pergerakannya hanya berupa empat arah pergerakan, yaitu atas, bawah, kanan, dan kiri. Permainan ini merupakan contoh kasus terkemuka untuk mengukur kinerja algoritma pencarian heuristik (Gaschnig, 1979; Nilsson, 1980;
Universitas Sumatera Utara
11 Pearl, 1984; Russel, 1992). Contoh pada permainan 8-puzzle dengan keadaan awal (initial state) dan keadaan tujuan (goal state) yang ingin dicapai pada Gambar 2.2.
Gambar 2.2 8-puzzle (Russel, 1992)
2.3 Permainan Pergeseran Angka Pada Bentuk Bintang
Permainan pergeseran angka pada bentuk bintang mirip dengan permainan pergeseran angka dalam kotak berbentuk persegi. Perbedaannya adalah bentuk wadah yang digunakan dalam permainan ini berbentuk bintang (star polygon). Setiap titik perpotongan dalam bintang merupakan titik (node) penempatan angka. Seperti halnya, permainan pergeseran angka lainnya, dalam permainan ini juga disediakan satu tempat kosong sebagai ruang untuk menggeser posisi angka. Aturan permainannya adalah sebagai berikut: 1. Tentukan keadaan awal (initial state) pada bintang. 2. Tentukan keadaan tujuan (goal state) pada bintang. 3. Aturan pergeseran: setiap angka dalam bintang hanya dapat digeser ke suatu titik yang kosong atau tidak ditempati. 4. Setiap angka hanya dapat digeser mengikuti jalur yang sudah ada sesuai dengan bentuk bintang yang digunakan.
Universitas Sumatera Utara
12 3
2
4
7
1
6 5
9
8
Gambar 2.3 (a) Bentuk bintang berkaki 5 (Bigg, 2001)
7
1
8
2
6
3
11
5
4
10
9
Gambar 2.3 (b) Bentuk bintang berkaki 6 (Bigg, 2001)
Permasalahan dari permainan ini adalah bagaimana mencapai goal state dari initial state dengan mengikuti aturan pergeseran yang telah ditetapkan. Pada bintang berkaki lima yang memiliki 10 buah titik, tersedia 9 buah titik yang memuat angka dan 1 buah titik kosong, sedangkan pada bintang berkaki enam yang memiliki 12 buah titik, tersedia 11 buah titik yang memuat angka dan 1 buah titik kosong seperti pada Gambar 2.3 di atas.
2.4 Teknik Dasar Pencarian
Keberhasilan suatu sistem salah satunya ditentukan oleh kesuksesan dalam pencarian dan pencocokan. Pencarian adalah proses mencari solusi dari suatu permasalahan
Universitas Sumatera Utara
13 melalui sekumpulan kemungkinan ruang keadaan (state space). Ada beberapa aplikasi yang menggunakan teknik pencarian, yaitu:
1. Papan game dan puzzle (tic tac-toe, catur, menara hanoi). 2. Penjadwalan dan masalah routing (travelling salesman problem). 3. Parsing bahasa dan interpretasinya (pencarian struktur dan arti). 4. Logika pemrograman (pencarian fakta dan implikasinya). 5. Computer vision dan pengenalan pola. 6. Sistem pakar berbasis kaidah (rule based expert system).
Pencarian atau pelacakan merupakan salah satu teknik untuk menyelesaikan permasalahan AI. Teknik pencarian terbagi atas dua teknik, yaitu pencarian buta (blind search) dan pencarian heuristik (heuristic search).
2.5 Pencarian Heuristik (Heuristic Search)
Kata heuristic berasal dari sebuah kata kerja bahasa Yunani, heuriskein, yang berarti mencari atau menemukan (Kusumadewi, 2007). Pencarian heuristik merupakan pencarian yang penelusurannya dimulai dengan adanya informasi awal yang digunakan dalam proses pencarian. Pencarian terbimbing (heuristic search) dibutuhkan karena pencarian buta (blind search) tidak selalu dapat diterapkan dengan baik, hal ini dikarenakan waktu aksesnya yang cukup lama serta besarnya memori yang diperlukan. Kelemahan ini dapat diatasi jika ada informasi tambahan (fungsi heuristik) dari domain yang bersangkutan. Dalam pencarian ruang keadaan, heuristik dinyatakan sebagai aturan untuk melakukan pemilihan cabang-cabang dalam ruang keadaan yang paling tepat agar tercapai solusi permasalahan yang bisa diterima. Pada pencarian heuristik, sebuah fungsi heuristik digunakan untuk mengevaluasi keadaan permasalahan tersendiri dan menentukan bagaimana fungsi ini diperlukan dalam memecahkan suatu permasalahan. Sebuah fungsi heuristik adalah sebuah fungsi yang memetakan keadaan permasalahan, yang menjelaskan daya tarik dan digambarkan dalam sebuah angka (Pearl, 1984). Tujuan dari sebuah fungsi heuristik adalah untuk memandu proses pencarian tujuan yang menguntungkan dengan menganjurkan jalur mana yang harus diikuti
Universitas Sumatera Utara
14 pertama kali ketika tersedia lebih dari satu tujuan. Game playing dan pemecahan teorema (theorem solving) adalah dua aplikasi paling tua dari AI, kedua-duanya memerlukan heuristik untuk memangkas ruang dari solusi yang mungkin. Beberapa heuristik lebih baik dari pada heuristik lainnya, dan semakin baik suatu heuristik, maka semakin sedikit node yang diperlukan untuk diperiksa dalam pohon pencarian untuk menemukan solusi. Oleh karena itu, seperti memilih representasi yang tepat, memilih heuristik yang tepat dapat membuat perbedaan yang signifikan dalam membantu kita untuk memecahkan masalah (Coppin, 2004). Dalam tugas akhir ini, fungsi heuristik yang akan dipakai sebagai fungsi evaluasi untuk menuntun arah pencarian solusi, adalah Gaschnig’s heuristic. Gaschnig’s heuristic mengukur jumlah pergeseran (swap) dengan tempat/ubin kosong untuk menghasilkan keadaan tujuan (goal state). Skenario kasus terburuk adalah ketika semua angka berada pada posisi yang salah, maka tempat kosong perlu ditukar sebanyak 10 kali dengan ubin yang berisi angka untuk menghasilkan keadaan tujuan. Jenis-jenis pencarian heuristik, yaitu: 1.
Generate and Test
2.
Hill Climbing
3.
Best First Search
4.
Alpha Beta Prunning
5.
Means-End-Analysis
6.
Constraint Satisfaction
2.6 Algoritma Best First Search
Algoritma best first search merupakan kombinasi dari algoritma depth first search dengan algoritma breadth first search dengan mengambil kelebihan dari kedua algoritma tersebut. Apabila pada pencarian dengan algoritma hill climbing tidak diperbolehkan untuk kembali ke node pada level yang lebih rendah meskipun node di level yang lebih rendah tersebut memiliki nilai heuristik yang lebih baik, lain halnya pada algoritma best first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node di level yang lebih tinggi memiliki nilai heuristik yang lebih buruk (Kusumadewi, 2003).
Universitas Sumatera Utara
15 Setiap sebuah node dikembangkan, algoritma akan menyimpan setiap successor node n sekaligus dengan harga (cost) dan petunjuk pendahulunya (parent). Algoritma akan berakhir pada node tujuan, dan tidak ada lagi pengembangan node. “Best first” mengacu pada algoritma mengeksplorasi node dengan "nilai" terbaik pertama. Sebuah fungsi evaluasi digunakan untuk menetapkan nilai untuk setiap calon node. Dalam algoritma ini, ruang pencarian dievaluasi menurut fungsi heuristik yang dinyatakan dengan persamaan berikut:
f(n) = h(n)
(1.1)
dimana: f(n) = fungsi heuristik h(n)= fungsi evaluasi yang dipakai untuk mengestimasi seberapa baik setiap node dibangkitkan.
Untuk mengimplementasikan algoritma pencarian ini, diperlukan dua buah senarai (list), yaitu: OPEN untuk mengelola nodes yang pernah dibangkitkan tetapi belum dievaluasi dan CLOSE untuk mengelola nodes yang pernah dibangkitkan dan sudah dievaluasi. Algoritma best first search adalah sebagai berikut:
1. Masukkan simpul awal ke dalam OPEN 2. OPEN berisi simpul awal dan CLOSE masih kosong 3. Masukkan simpul awal ke CLOSE dan suksesornya pada OPEN list 4. Ulangi langkah berikut sampai goal ditemukan dan tidak ada lagi node yang akan dikembangkan: a. Hitung nilai f nodes yang ada pada OPEN, ambil node terbaik (f terkecil) b. Jika node tersebut sama dengan node tujuan, maka sukses c. Jika tidak, masukkan node tersebut ke dalam CLOSE d. Bangkitkan semua successor dari node tersebut e. Untuk setiap successor kerjakan: 1. Jika successor tersebut belum pernah dibangkitkan, evaluasi successor tersebut, tambahkan ke OPEN, dan catat parent-nya. 2. Jika successor tersebut sudah pernah dibangkitkan sebelumnya, ubah parent-nya jika lintasan baru lebih menjanjikan atau jalur melalui parent
Universitas Sumatera Utara
16 ini lebih baik daripada jalur melalui parent yang sebelumnya. Selanjutnya, perbarui biaya untuk successor tersebut dan nodes lain yang berada di level bawahnya.
Contoh proses best first search dapat dilihat pada Gambar 2.4 berikut:
Gambar 2.4 Langkah-langkah yang dilakukan oleh algoritma Best First Search
Pertama kali, dibangkitkan node A. Kemudian semua successor A dibangkitan, dan dicari harga paling minimal. Pada langkah 2, node B terpilih karena harganya paling rendah, yakni 2. Langkah 3, semua successor B dibangkitkan, kemudian harganya akan dibandingkan dengan harga node C dan D. Ternyata harga node D paling kecil dibandingkan harga node C, E, dan F. Sehingga D terpilih dan selanjutnya akan dibangkitkan semua successor D pada langkah 4. Harga node H paling kecil dibandingkan harga node C, E, F, dan G. Maka semua successor H dibangkitkan. Demikian seterusnya sampai ditemukan node tujuan.
Universitas Sumatera Utara
17 2.7 Penelitian Sebelumnya
Beberapa penelitian yang pernah dilakukan dengan menggunakan algoritma best first search antara lain untuk membangun permainan ular tangga modifikasi (Zi, 2011) dan penyelesaian permainan minesweeper (Sigiro, 2011). Penelitian yang pernah dilakukan mengenai permainan pergeseran angka dalam bentuk bintang yaitu dengan menggunakan algoritma breadth first search (Naif, 2009). Zi (2011) menggunakan konsep kecerdasan buatan dengan algoritma best first search untuk membangun sebuah permainan ular tangga modifikasi. Permainan ular tangga merupakan board game yang dimainkan oleh 2 orang atau lebih. Papan permainan dibagi dalam kotak-kotak kecil dan di beberapa kotak digambar sejumlah "tangga" atau "ular" yang menghubungkannya dengan kotak lain. Pada penelitian ini, algoritma best first search dapat diterapkan dengan baik ke dalam permainan untuk mencari jalan tercepat melalui angka dadu untuk mencapai finish. Sigiro (2011) menggunakan algoritma best first search dalam penelitiannya tentang penyelesaian permainan minesweeper. Minesweeper adalah permainan komputer untuk satu pemain. Tujuan permainan ini adalah untuk membersihkan lahan permainan tanpa mengenai ranjau. Pada penelitian tersebut sistem dengan implementasi algoritma best first search yang dibangun dapat menemukan solusi dengan menggunakan kotak seleksi berukuran 4x4. Naif (2009) menggunakan algoritma breadth first search dalam menyelesaikan permainan pergeseran angka pada bentuk bintang. Penggunaan algoritma ini mampu menemukan semua solusi namun keadaan awal yang semakin berbeda atau kompleks dengan keadaan akhir, akan membutuhkan waktu yang lama dan tingkat (level) pencarian yang panjang untuk menemukan suatu solusi x.
Universitas Sumatera Utara
18 Tabel 2.1 Penelitian Sebelumnya No Judul 1. Implementasi Konsep Kecerdasan Buatan Dengan Metode Best First Search (BFS) Untuk Pembuatan Game Ular Tangga Modifikasi 2. Analisis dan Implementasi Penyelesaian Game Minesweeper Menggunakan Algoritma Greedy Best First Search 3. Penyelesaian Permainan Pergeseran Angka Pada Bintang Dengan Algoritma Breadth First Search
Pengarang Tahun Kelebihan Nurulliana Zi 2011 pencarian angka dadu selanjutnya yang dibutuhkan dengan metode ini mampu mendapatkan jalan tercepat untuk mencapai finish. Irma Y N Sigiro
Maryanti Naif
2011
2009
Kekurangan
penyelesaian game minesweeper dapat diperoleh dengan baik menerapkan algoritma greedy best first search.
selalu menemukan solusi
kurang efektif karena membutuhkan waktu yang lama dan langkah pencarian yang panjang dalam pencarian solusi
Universitas Sumatera Utara
