Sebuah software atau hardware disebut cerdas jika memiliki kemampuan untuk searching, reasoning, planning dan learning.

1. Searching

Adalah mekanisme memecahkan suatu masalah dengan teknik pencarian. langkah pertama adalah mendefinisikan ruang masalah, langkah kedua adalah mendefinisikan atauran produksi yang digunakan untuk mengubah suatu state ke state lainnya. langkah terakhir adalah memilih metode pencarian yang tepat sehingga dapat menemukan solusi terbaik dengan usaha minimal. Teknik ini digunakan untuk pencarian rute optimum untuk memandu seseorang di perjalanan. 

Contoh : Penggunaan smartphone atau komputer yang dilengkapi Global Positioning System (GPS).

2. Reasoning

Adalah mekanisme penyelesaian masalah dengan cara mereprentasikan masalah ke dalam basis pengetahuan  atau knowledge base menggunakan logic atau bahasa formal atau bahasa yang dipahami komputer. Teknik ini digunakan untuk melakukan penalaran terhadap suatu masalah yang dialami manusia.

Contoh : Software yang digunakan dalam dunia kedokteran, MedicWare yang digunakan untuk merekam catatan medis pasien.

3. Planning

Adalah mekanisme menyelesaikan masalah – masalah yang dapat di dekomposisi atau decomposable problems. Teknik ini digunakan untuk melakukan perencanaan terhadap suatu masalah yang hendak diselesaikan. 

Contoh : Optimum-AIV adalah suatu planner yang digunakan oleh European Space Agency untuk assembly atau perakitan, integration atau penggabungan dan verification (AIV) pesawat terbang.

4. Learning

Adalah mekanisme yang menggunakan metadata sebagai input dan mengolahnya menggunakan sejumlah lapisan tersembunyi transformasi non liniear dari data masukan untuk menghitung nilai output. Teknik ini digunakan untuk membuat mesin-mesin otomatis melalui proses pembelajaran dan pelatihan sedemikian rupa  hingga bisa menjadi cerdas layaknya manusia. 

Contoh : Speech to Speech Machine Translation (S2SMT), dengan S2SMT, seseorang bisa berbicara dengan orang lain yang menggunakan bahasa berbeda. 

STUDI KASUS

Gambar di bawah ini adalah sebuah graf simetris tak berarah yang menggambarkan kondisi jalan raya di suatu kota. Terdapat 8 simpul yang menyatakan persimpangan jalan dengan posisi – posisi koordinat dua dimensi (x, y). setiap busur memiliki 2 atribut, angka pertama menyatakan Panjang jalan sebenarnya (dalam satuan kilometer), dan angka yang berbeda dalam tanda kurung, menyatakan kecepatan maksimum yang diperbolehkan untuk setiap kendaraan yang melalui jalan tersebut (dalam satuan km/jam). Seorang pimpinan satuan pemadam kebakaran, yang berada di persimpangan S, bermaksud memadamkan api di sebuah Gedung yang terletak di persimpangan G. Dia menggunakan mobil pemadam kebakaran dengan kecepatan maksimum 90km/jam. Bantulah petugas tersebut menemukan rute jalan dengan totoal wakti tercepat dari S ke G dengan menggunakan metode A*.

• 

Menghitung Heuristik

Karena h(n) nya belum diketahui maka kita harus mencari atau menghitung jarak dari dua titik indeks, rumus jarak dua titik adalah sebagai berikut:

Dengan menggunakan rumus di atas, maka perhitungan dari semua titik dapat dilihat sebagai berikut:

Kecerdasan buatan Dea Sunara 1830511098

 

DEPTH LIMITED SEARCH PADA PERMAINAN PEG SOLITAIRE

Abstraksi

Permainan Peg Solitaire adalah permainan single player yang terdiri dari sebuah papan  dan  sejumlah  kelereng.  Papan  permainan  Peg  Solitaire  terdiri  dari  banyak  jenis antara lain papan jenis inggris, eropa, triangular dan masih banyak jenis papan permainan Peg Solitaire yang lain. 

Pemain  permainan  Peg  Solitaire  terkadang  sulit  menentukan  keputusan  langkah yang tepat. Oleh karena itu, disediakan bantuan berupa hint yang membantu pemain saat pemain  menentukan  langkah.  Salah  satu  algoritma yang dapat diterapkan pada hint permainan Peg Solitaire adalah algoritma Depth Limited Search.

Penerapan algoritma Depth Limited Search pada hint permainan Peg Solitaire di papan permainan versi inggris ukuran 3 x 3 dan triangular berukuran 4 x 4, 5 x 5, serta 7 x 7, mampu menemukan solusi yaitu sisa satu kelereng serta mampu menangani apabila tidak menemukan  solusi.  Penerapan  algoritma Depth Limited Search  pun  mampu  menampilkan semua  perpindahan  langkah  hingga ditemukan sisa  1  kelereng.  Hal  ini  dibuktikan  dengan cara menguji 10 soal pada sistem. Dari hasil pengujian 10 soal pada sistem, 9 soal berhasil diselesaikan  dan 1 soal  gagal diselesaikan karena tidak menemukan solusi berupa sisa  1 kelereng.

 

1. Pendahuluan

Peg  solitaire adalah  salah  satu  permainan  komputer.  Permainan Peg  Solitaire adalah  permainan  yang  terdiri  dari  sebuah  papan  permainan  dan  sejumlah  kelereng. Permainan Peg Solitaire ini memiliki tujuan untuk mencari solusi dari kondisi awal menuju kondisi  akhir  yaitu  sisa  satu  kelereng.  Untuk  menentukan  solusi  permainan Peg  Solitaire akan digunakan sebuah algoritma.

 Algoritma  yang  akan  digunakan  untuk  menemukan  solusi  pada  permasalahan permainan Peg Solitaire adalah algoritma Depth Limited Search. Algoritma Depth Limited Search adalah  algoritma blind  search Algoritma  ini  diharapkan  dapat  menemukan  solusi dari  kondisi  awal  menuju  kondisi  akhir  yaitu  menyisakan  satu  kelereng  pada  papan permainan Peg Solitaire versi eropa dan inggris dengan ukuran masing – masing 3 x 3, 5 x 5  ,  dan 7  x  7 serta  versi triangular ukuran  4  x  4,  5  x 5  ,  dan 7  x  7 serta  mampu  menangani kemungkinan solusi tidak ditemukan. Batasan   masalah   dalam   penelitian   ini   antara   lain   papan   permainan   untuk implementasi algoritma hanya papan versi inggris ukuran 3 x 3 dan triangular ukuran 4 x 4, 5 x 5, serta 7 x 7, ada pengembangan soal dan soal random untuk papan versi inggris ingris ukuran  3  x  3  serta triangular 4  x  4,  5  x  5,  dan  7  x  7,  pemain  dapat  memasukkan  jumlah lubang  kosong  dengan  batas  maksimal  setengah  dari  jumlah  total  lubang  papan,  dan algoritma akan diterapkan pada menu hint untuk membantu pemain memilih langkah untuk mencapai sisa satu kelereng.

2. Landasan Teori

2.1.Kecerdasan Buatan

Kecerdasan buatan merupakan cabang teknologi yang relatif baru. Prinsip kecerdasan   buatan   diawali sejak muncul komputer   modern antara tahun 1940-1950. Kecerdasan  buatan  berkembang  pesat  seiring  dengan  berkembangnya  teknologi  komputer yang dari hari ke hari bertambah maju.

Ada 2 bagian utama yang  dibutuhkan untuk aplikasi kecerdasan buatan yaitu basis pengetahuan  atau knowledge  base yang  berisi  fakta-fakta,  teori,  pemikiran  serta  hubungan antara  satu  dengan  lainnya  dan  motor  inferensi  atau inference  engine yaitu  kemampuan menarik  kesimpulan  berdasarkan  pengalaman.  Kecerdasan  buatan  kini  telah  diterapkan pada banyak bidang. 

Salah satu bidang yang menerapkan  kecerdasan buatan adalah  permainan  atau game. Game berasal dari kata bahasa inggris yang memiliki arti dasar permainan.Permainan  dalam  hal  ini  merujuk pada pengertian  kelincahan  intelektual  atau intellectual playability. Game atau  permainan  juga  dapat  dikelompokkan  berdasarkan tipenya  yaitu deterministic  game dan chance.  Permainan  catur,  Othello,  dan Peg  Solitaire Termasuk dalam  jenis  permainan deterministic-perfect  information karena  memiliki  informasi  yang lengkap  mengenai cara mencapai tujuan  atau goal. Sedangkan jenis permainan chance adalah permainan yang memiliki banyak  kemungkinan – kemungkinan secara acak, belum dapat terlihat tujuan akhirnya. 

 

2.2. Algoritma Depth Limited Search

Algoritma Depth  Limited  Search memberikan  batas  kedalaman  pada  algoritma Depth  First  Search (Russel  &  Norvig,  1995).  Dengan algoritma Depth  Limited  Search, penelusuran Depth First Search data dibatasi sehingga tidak melakukan penelusuran terlalu dalam. Algoritma Depth Limited Search Adalah sebagai berikut:

a) Tetapkan node awal dengan kedalaman = 0 dan tentukan batas kedalaman.

b) Cek  apakah  node  adalah  node  tujuan.  Jika  benar  maka proses  berhenti,  jika  tidak maka lanjut ke langkah c.

c) Cek  apakah  kedalaman  node  sama  dengan  batas  kedalaman  yang  telah  ditentukan. Jika  benar,  maka  lanjutkan  proses  dengan  menelusur hanya  node  –  node  yang berada dalam batas kedalaman yang telah ditentukan dan belum dikunjungi dengan kembali kelangkah b. Jika tidak maka lanjutkan ke langkah d.

d) Perluas node dan kembali ke langkah b. 

Gambaran  kerja  algoritma Depth  Limited  Search dapat  digambarkan  dalam  bentuk tree.Tree merupakan sebuah graf tidak berarah dan merupakan jaringan bersambung yang tidak memiliki untai (loop) sehingga dengan demikian dapat disimpulkan bahwa sebuah tree dapat  dibentuk dari graf  sederhana  karena  graf  sederhana  tidak  memiliki self  loop ataupun edge  parallel. Tree terdiri dari  sekumpulan elemen.  Elemen tree adalah  akar atau root dan simpul. Derajat atau degree sebuah simpul menunjukkan jumlah anak pada simpul tersebut.

2.3. Permainan Peg Solitaire

Peg Solitaire merupakan sebuah permainan dengan satu orang pemain. Permainan ini  terdiri  dari  sebuah  papan  permainan  dengan  sejumlah  kelereng.  Papan  permainan tersebut  berisi  sekumpulan  lubang.  Lubang–lubang  tersebut  akan  terisi  penuh  dengan kelereng.  Pada  awal  permainan,  lubang  tengah  pasti dikosongkan. Peg  Solitaire ini dimainkan dengan cara :

• Kelereng akan melompati kelereng lain menuju lubang kosong.

• Kelereng yang telah dilompati akan hilang atau keluar dari permainan.

• Permainan akan dianggap selesai apabila hanya tersisa satu kelereng. 

Strategi  yang  terbaik  yang  dapat  dilakukan  agar  dapat  menemukan  solusi  pada permainan Peg  Solitaire adalah  mengarahkan  kelereng  ke  lubang  bagian  tengah  dan menyelamatkan  kelereng  terisolasi  yang  terdapat  di lubang  –  lubang  bagian  pinggir. Gerakan  kelereng  yang  diperbolehkan  adalah  melangkah  ke  kanan,  melangkah  ke  kiri, melangkah ke atas, dan ke bawah.

KESIMPULAN

1. Algoritma Depth Limited Search yang diterapkan pada sistem  permainan Peg  Solitaire dalam tugas akhir ini mampu menemukan solusi  namun terbatas  hanya  pada  papan inggris ukuran 3 x 3, dan papan triangular dengan ukuran 4 x 4, 5 x 5, serta 7 x 7.

2. Algoritma Depth  Limited  Search yang diterapkan  oleh sistem ini membutuhkan waktu yang singkat untuk kasus – kasus  kecil  dengan  jumlah kelereng  kurang  dari 16 dengan syarat posisi kelereng yang saling berdekatan satu sama lain atau dengan kata lain posisi kelereng tidak tersebar berjauhan namun membutuhkan waktu yang lama dalam kasus – kasus besar yaitu kasus – kasus dengan jumlah kelereng lebih dari 16 dan posisi kelereng yang tersebar berjauhan. Hal ini disebabkan oleh  algoritma Depth Limited Search yang diterapkan pada sistem ini adalah algoritma Depth Limited Search murni dengan metode iteratif.

3. Algoritma Depth Limited Search membatasi kedalaman yaitu jumlah kelereng –1

4. Tanpa ada pembatasan level, solusi tetap dapat ditemukan. Algoritma Depth Limited  Search mampu menangani tidak ditemukannya  solusi dengan cara mendeteksi semua posisi kelereng sehingga apabila posisi kelereng tidak memungkinkan lagi untuk dipindahkan ke posisi lain maka sistem akan berhenti bekerja.

5. Pengujian sistem yang dilakukan dengan menguji 10 soal, 9 soal berhasil diselesaikan dan 1 soal tidak berhasil diselesaikan.

daftar pustaka

https://www.neliti.com/id/publications/66816/implementasi-algoritma-depth-limited-search-pada-permainan-peg-solitaire

.