BAB II LANDASAN TEORI
2.1. Kecerdasan Buatan Kecerdasan buatan atau Artificial Intelligence (AI) adalah suatu bidang ilmu yang mempelajari tentang bagaimana membangun sistem komputer yang menerapkan kecerdasan dalam beberapa cara. Kecerdasan buatan telah banyak menghasilkan banyak terobosan dalam ilmu komputer. Banyak topik penelitian dalam ilmu komputer hari ini merupakan hasil dari penelitian tentang kecerdasan buatan. Sebagai contoh, jaringan saraf tiruan, komputasi evolusioner, machine learning, natural language processing, pemrograman berorientasi objek, dan lainnya. Dalam banyak kasus, fokus utama dari topik penelitian ini bukan lagi pengembangan kecerdasan buatan, mereka menjadi disiplin ilmu sendiri, dan pada beberapa kasus, bukan lagi berhubungan dengan kecerdasan buatan. Kecerdasan buatan sendiri terus berkembang menciptakan terobosan baru yang masih dibutuhkan (Teahan, 2010). Kecerdasan buatan merupakan 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 kelakuan atau tindak-tanduk yang sepenuhnya bisa menirukan beberapa fungsi otak manusia, seperti pengertian bahasa, pengetahuan, pemikiran, pemecahan masalah dan lain-lain (Kristianto, 2004). Manusia bisa menjadi pandai dalam menyelesaikan segala permasalahan di dunia ini karena manusia mempunyai pengetahuan dan pengalaman. Namun bekal pengetahuan saja tidak cukup, manusia juga diberi akal untuk melakukan penalaran, mengambil kesimpulan berdasarkan pengetahuan dan pengalaman yang mereka miliki. Agar komputer bisa bertindak seperti dan sebaik manusia, maka komputer juga harus diberi bekal pengetahuan, dan mempunyai kemampuan untuk menalar. Untuk itu pada artificial intelligence, akan mencoba untuk memberikan beberapa metode untuk
6
membekali komputer dengan kedua komponen tersebut agar komputer bisa menjadi mesin yang pintar. Lebih detailnya, pengertian kecerdasan buatan dapat dipandang dari berbagai sudut pandang, antara lain: 1. Sudut pandang kecerdasan. Kecerdasan Buatan akan membuat mesin menjadi ‘cerdas’ (mampu berbuat seperti apa yang dilakukan oleh manusia). 2. Sudut pandang penelitian. Kecerdasan Buatan adalah suatu studi bagaimana membuat agar komputer dapat melakukan sesuatu sebaik yang dikerjakan oleh manusia. Domain yang sering dibahas oleh para peneliti meliputi: a. Mundane task -
Persepsi (vision & speech).
-
Bahasa alami (understanding, generation & translation).
-
Pemikiran yang bersifat commonsense.
-
Robot control.
b. Formal task -
Permainan/games.
-
Matematika (geometri, logika, kalkulus integral, pembuktian).
c. Expert task -
Analisis finansial.
-
Analisis medikal.
-
Analisis ilmu pengetahuan.
-
Rekayasa (desain, pencarian kegagalan, perencanaan manufaktur).
3. Sudut pandang bisnis. Kecerdasan buatan adalah kumpulan peralatan yang sangat powerful dan metodologis dalam menyelesaikan masalah-masalah bisnis. 4. Sudut pandang pemrograman. Kecerdasan buatan meliputi studi tentang pemrograman simbolik, penyelesaian masalah (problem solving) dan pencarian (searching). Untuk melakukan aplikasi kecerdasan buatan ada 2 bagian utama yang sangat dibutuhkan (Gambar 2.1), yaitu: a. Basis Pengetahuan (Knowledge Base), berisi fakta-fakta, teori, pemikiran dan hubungan antara satu dengan lainnya.
7
b. Motor Inferensi
(Inference
Engine),
yaitu
kemampuan
menarik
kesimpulan berdasarkan pengalaman.
Komputer Input:
Basis
Motor
masalah,
Pengetahuan
Inferensi
pertanyaan,
Output: jawaban, solusi, dll
Gambar 2.1 Penerapan Konsep Kecerdasan Buatan di Komputer Kecerdasan buatan tidak hanya dominan di bidang ilmu komputer (informatika), namun juga sudah merambah di berbagai disiplin ilmu yang lain. Interseksi antara psikologi dan kecerdasan buatan melahirkan sebuah area yang dikenal dengan nama cognition & psycolinguistics. Interseksi antara teknik elektro dengan kecerdasan buatan melahirkan berbagai ilmu seperti: pengolahan citra, teori kendali, pengenalan pola dan robotika. Secara garis besar bidang ilmu yang dipelajari dalam bidang AI bisa dilihat pada Gambar 2.2 berikut ini :
Gambar 2.2 Domain Area
8
1. Natural Language Processing (NLP) NLP mempelajari bagaimana bahasa alami itu diolah sedemikian hingga user dapat berkomunikasi dengan komputer. Konsentrasi ilmu ini adalah interaksi antara komputer dengan bahasa natural yang digunakan manusia, yakni bagaimana komputer melakukan ekstraksi informasi dari input yang berupa natural language dan atau menghasilkan output yang juga berupa natural language. 2. Computer Vision Cabang ilmu ini erat kaitannya dengan pembangunan arti/makna dari image ke obyek secara fisik. Yang dibutuhkan di dalamnya adalah metode-metode untuk memperoleh, melakukan proses, menganalisis dan memahami image. Apabila cabang ilmu ini dikombinasikan dengan Artificial Intelligence secara umum akan mampu menghasilkan sebuah visual intelligence system. 3. Robotika dan Sistem Navigasi Bidang ilmu inilah yang mempelajari bagaimana merancang robot yang berguna bagi industri dan mampu membantu manusia, bahkan yang nantinya bisa menggantikan fungsi manusia. Robot mampu melakukan beberapa task dengan berinteraksi dengan lingkungan sekitar. Untuk melakukan hal tersebut, robot diperlengkapi dengan actuator seperti lengan, roda, kaki, dll. 4. Game Playing Game biasanya memiliki karakter yang dikontrol oleh user, dan karakter lawan yang dikontrol oleh game itu sendiri. Di mana kita harus merancang aturanaturan yang nantinya akan dikerjakan oleh karakter lawan. Game akan menjadi menarik apabila karakter lawan (non-player) bereaksi dengan baik terhadap apa yang dilakukan oleh player. Hal ini akan memancing penasaran user dan membuat game menarik untuk dimainkan. Tujuan intinya adalah membuat nonplayer memiliki strategi yang cerdas untuk mengalahkan player. Pada bidang ini, AI dibutuhkan, yaitu untuk merancang dan menghasilkan game yang fun serta antarmuka antara man-machine yang cerdas dan menarik untuk dimainkan. 5. Sistem Pakar Bidang ilmu ini mempelajari bagaimana membangun sistem atau komputer yang memiliki keahlian untuk memecahkan masalah dan menggunakan penalaran dengan meniru atau mengadopsi keahlian yang dimiliki oleh pakar.
9
Dengan sistem ini, permasalahan yang seharusnya hanya bisa diselesaikan oleh para pakar/ahli, dapat diselesaikan oleh orang biasa/awam. Sedangkan, untuk para ahli, sistem pakar juga akan membantu aktivitas mereka sebagai asisten yang seolah-olah sudah mempunyai banyak pengalaman (Budiharto, 2012).
2.2. Algoritma Greedy Algoritma greedy merupakan metode yang paling populer untuk memecahkan masalah optimasi. Secara harfiah, greedy berarti tamak atau rakus. Prinsip dari algoritma greedy adalah mengambil setiap kesempatan yang ada saat itu juga, tanpa memperhatikan konsekuensi ke depannya. Algoritma greedy tidak selalu memperoleh solusi optimum untuk keseluruhan permasalahan yang ditangani, dikarenakan algoritma greedy tidak melakukan operasi secara exhaustive kepada semua data, dan sering kali tidak mementingkan solusi optimum global. Akan tetapi, algoritma greedy merupakan solusi yang baik digunakan dikarenakan algoritma greedy bekerja dengan cepat dan sering memberikan perkiraan nilai optimum yang baik di setiap langkahnya. Dan tidak jarang dapat menghasilkan solusi optimum global pada suatu permasalahan dari pengambilan solusi optimum lokal di setiap langkahnya. Akan tetapi algoritma greedy cukup kuat dan bekerja dengan baik untuk berbagai masalah (Putra, 2009). Elemen-elemen algoritma greedy dalam persoalan optimasi adalah sebagai berikut: 1. Himpunan kandidat. Himpunan ini berisi elemen-elemen pembentuk solusi. 2. Himpunan solusi. Himpunan ini berisi kandidat-kandidat yang terpilih sebagai
solusi
persoalan. Himpunan solusi merupakan himpunan bagian dari himpunan kandidat. 3. Fungsi seleksi. Fungsi seleksi dinyatakan sebagai predikat seleksi merupakan fungsi yang pada setiap langkah memilih kandidat yang paling mungkin untuk mendapatkan solusi optimal. 4. Fungsi kelayakan.
10
Fungsi kelayakan dinyatakan sebagai predikat layak merupakan fungsi yang memeriksa apakah suatu kandidat yang dipilih dapat memberikan solusi yang layak, yaitu kandidat tersebut tidak melanggar aturan yang ada. 5. Fungsi objektif. Fungsi
objektif
merupakan
fungsi
yang memaksimumkan atau
meminimalkan nilai solusi. Pseudo-code algoritma greedy adalah sebagai berikut (Chen, 2008) : Procedure Greedy (partial solution S, sub-problem P) Begin generate all candidate choices as list L for current subproblem P; while (L is not empty OR other finish condition is not met) compute the fitness value of each choice in L; modify S and P by taking the choice with highest fitness value; update L according to S and P; end while; return the quality of the resulting complete solution; End
2.3. Permainan (Game) Games merupakan salah satu bidang terapan dalam kecerdasan buatan. Penyelesaian games dilakukan dengan cara menelusuri pohon permainan (game tree). Pohon permainan adalah sebuah graf yang memperlihatkan semua kemungkinan keadaan dalam permainan yang dilakukan oleh pemain. Pohon permainan melukiskan node dan jalan yang mengarah dari keadaan awal menuju tujuan atau keadaan saat game dimenangkan. Ada beberapa alasan mengapa games merupakan domain yang baik untuk dieksplor dalam bidang kecerdasan buatan (Kusumadewi, 2003), yaitu : 1. Sangat mudah untuk menentukan ukuran kesuksesan dan kegagalannya (menang atau kalah). 2. Tidak membutuhkan terlalu banyak pengetahuan. Permainan dapat diselesaikan dengan melakukan pencarian dari arah start sampai posisi menang. 3. Ruang keadaannya mudah direpresentasikan. 4. Operator-operator yang digunakan tidak terlalu banyak.
11
5. Sebagian besar game dapat dimodelkan dengan mudah. 6. Sangat mungkin untuk dibandingkan dengan kemampuan manusia.
2.4. Game Summy Summy merupakan sebuah board game yang dibuat oleh Cwali (Corné van Moorsel) dan merupakan sejenis game Scrable untuk penjumlahan, pengurangan, perkalian atau pembagian. Pemain akan mendapatkan poin dengan membuat penjumlahan, pengurangan, perkalian atau pembagian pada gilirannya. Penjumlahan, pengurangan, perkalian atau pembagian ini dibuat dengan menyusun angka dan operator numerik pada papan permainan. Pemain hanya dapat membuat penjumlahan, pengurangan, perkalian atau pembagian yang valid untuk memperoleh poin dengan kotak yang mereka miliki dan dikombinasikan dengan kotak yang telah ada pada papan permainan. Pemain tidak dapat memindahkan kotak yang telah ada pada papan permainan (Moorsel, 2014).
Gambar 2.3 Game Summy Berikut ini merupakan penjumlahan, pengurangan, perkalian atau pembagian yang valid pada game Summy : 1. Harus terdapat satu ‘=’ pada setiap penjumlahan, pengurangan, perkalian atau pembagian. 2. Di depan ‘=’ harus ada minimal dua angka dan satu operator aritmetika dan di belakang ‘=’ harus terdapat satu angka dan tidak ada operator aritmetika. 3. Bilangan dapat terdiri dari lebih dari satu digit angka.
12
4. Sebuah bilangan yang terdiri lebih dari dua digit angka tidak boleh diawali dengan ‘0’ 5. Dalam satu penjumlahan, pengurangan, perkalian atau pembagian bisa terdapat beberapa operator aritmetika pada setiap di antara dua angka. 6. Operator perkalian dan pembagian lebih dahulu diutamakan daripada operator penambahan dan pengurangan. 7. Perkalian dan pembagian dijalankan sesuai urutan pembacaan, begitu pula dengan penambahan dan pengurangan.
Gambar 2.4 Penjumlahan, Pengurangan, Perkalian atau Pembagian Valid pada Summy Untuk menghitung poin pada game Summy dapat dilakukan dengan menjumlahkan semua digit (0-9) dari penjumlahan, pengurangan, perkalian atau pembagian valid yang dilakukan. Poin dari penjumlahan, pengurangan, perkalian atau pembagian valid tersebut diperoleh dari digit kotak yang pemain letakkan dan semua kotak yang telah ada pada papan permainan. Untuk lebih jelas dapat dilihat pada Gambar 2.5.
Gambar 2.5 Memperoleh Score pada Summy
13
2.6. Penelitian Terdahulu Penelitian mengenai aplikasi game Summy sebelumnya belum ada, karena game ini merupakan varian dari game Scrabble dan tidak dikenal luas. Namun beberapa penelitian yang pernah dilakukan berkaitan dengan menyelesaikan permasalahan dari suatu game (permainan) dengan menggunakan algotitma greedy antara lain untuk permainan Mill (Simanjuntak, 2015), permainan Kartu Remi (Putra, 2014) dan permainan Fill-In Number (Pawardita, 2015).
Tabel 2.1 Penelitian Terdahulu No.
Nama
1
Simanjuntak, 2015
Judul Penelitian Penerapan Algoritma Greedy Pada Permainan Mill Berbasis Android
Ringkasan Pada penelitian ini algoritma greedy digunakan pada pencarian langkah optimum dalam permainan Mill. Permainan Mill adalah pengembangan dari penggabungan konsep permainan Tic Tac Toe dan permainan Twelve Men's Morris. Permainan Mill menggunakan aturan dan konsep permainan Tic Tac Toe yang bertujuan menempatkan 3 bidak masing-masing pemain dalam suatu garis lurus yang dapat berupa garis horizontal, vertikal, ataupun diagonal. Dengan algortima greedy akan ditentukan titik mana yang akan diletakkan bidak oleh komputer berdasarkan prioritas nilai path tertinggi yang didapatkan dari fungsi prioritas.
14
Tabel 2.2 Penelitian Terdahulu (Lanjutan) 2
Putra, 2014
Analisis Perbandingan Algoritma Greedy Dan Brute Force Dalam Percarian Kartu Tertinggi Pada Kartu Remi
Pada penelitian ini algoritma greedy digunakan pada pencarian kartu tertinggi pada permainan Remi. Algoritma greedy digunakan pada pemilihan kartu tertinggi berdasarkan nilai dan coraknya. Pemilihan nilai kartu tertinggi dimulai dari As, K, Q,...2. Sedangkan pada corak dimulai dai sekop, hati, keriting dan wajik.
3
Pawardita, 2015
Aplikasi Permainan Fill-In Numbers Pada Platform Android
Pada penelitian ini algoritma greedy digunakan pada pencarian solusi pada permainan Fill-In Number. Fill-In Numbers dikenal juga sebagai crusadex atau cruzadex ini merupakan suatu permainan puzzle dari varian teka-teki silang (crossword). Permainan ini dilengkapi dengan grid dan daftar lengkap dari angka-angka yang akan dimasukkan dalam grid tersebut. Dengan algoritma greedy akan dipilih simpul yang paling besar dari grid-grid yang ada pada papan permainan untuk diisi angka-angka yang akan dimasukkan pada grid tersebut.
