Dasar Pemikiran Pembuatan Game : Konsep utama dalam menentukan keberhasilan sistem yang berlandaskan AI adalah kesuksesan dalam melakukan dan mengembangkan pencarian. Pencarian atau pelacakan merupakan salah satu teknik untuk menyelesaikan permasalahan AI. Keberhasilan suatu sistem, salah satunya ditentukan oleh kesuksesan dalam pencarian dan pencocokan. Teknik dasar pencarian memberikan suatu kunci bagi banyak sejarah penyelesaian yang penting dalam bidang AI. Ada beberapa aplikasi yang menggunakan teknik pencarian ini, yaitu:
1. Papan game dan puzzle (tic-tac-toe, catur)
2. Penjadwalan dan masalah routing (travelling salesman problem)
3. Parsing bahasa dan interpretasinya (pencarian struktur dan arti)
4. Logika pemograman (pencarian fakta dan implikasinya)
5. Computer vision dan pengenalan pola
6. Sistem pakar berbasis kaidah (rule based expert system)
Konsep pencarian untuk suatu solusi dalam ruang keadaan (state space) merupakan pusat AI yang menjadikan AI lebih unggul dalam bidang ilmu komputer dibandingkan dengan yang lainnya, dan prinsip kontribusi AI untuk ilmu pengetahuan dari pencarian ini merupakan konsep basis pengetahuan (knowledge based) heuristik untuk pembatasan dan pencarian berarah (directing search). Pada dasarnya, ada dua teknik pencarian dan pelacakan yaitu:
1. Pencarian buta (blind search), terdiri atas:
a. Pencarian melebar pertama (Breadth First Search)
b. Pencarian mendalam pertama (Depth First Search)
1. Papan game dan puzzle (tic-tac-toe, catur)
2. Penjadwalan dan masalah routing (travelling salesman problem)
3. Parsing bahasa dan interpretasinya (pencarian struktur dan arti)
4. Logika pemograman (pencarian fakta dan implikasinya)
5. Computer vision dan pengenalan pola
6. Sistem pakar berbasis kaidah (rule based expert system)
Konsep pencarian untuk suatu solusi dalam ruang keadaan (state space) merupakan pusat AI yang menjadikan AI lebih unggul dalam bidang ilmu komputer dibandingkan dengan yang lainnya, dan prinsip kontribusi AI untuk ilmu pengetahuan dari pencarian ini merupakan konsep basis pengetahuan (knowledge based) heuristik untuk pembatasan dan pencarian berarah (directing search). Pada dasarnya, ada dua teknik pencarian dan pelacakan yaitu:
1. Pencarian buta (blind search), terdiri atas:
a. Pencarian melebar pertama (Breadth First Search)
b. Pencarian mendalam pertama (Depth First Search)
2. Pencarian terbimbing (heuristic search).
Pencarian Melebar Pertama (Breadth First Search)
Pada metode pencarian ini, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya.
Karena proses breadth first search mengamati setiap node di setiap level graf sebelum bergerak menuju ruang yang lebih dalam, maka mula-mula semua keadaan akan dicapai lewat lintasan yang terpendek dari keadaan awal. Oleh sebab itu, proses ini menjamin ditemukannya lintasan terpendek dari keadaan awal ke keadaan tujuan. Lebih jauh karena mula-mula semua keadaan ditemukan melalui lintasan terpendek sehingga setiap keadaan yang ditemui pada kali kedua didapati pada sepanjang sebuah lintasan yang sama atau lebih panjang. Kemudian, jika tidak ada kesempatan ditemukannya keadaan yang identik pada sepanjang lintasan yang lebih baik maka algoritma akan menghapusnya, sehingga keuntungan dari metode pencarian ini adalah:
1. Tidak akan menemui jalan buntu.
2. Jika ada satu solusi, maka breadth-first search akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.
Namun demikian, ada tiga persoalan utama berkenaan dengan metode pencarian ini, yaitu:
1. Membutuhkan memori yang besar, karena menyimpan semua node dalam satu pohon. Jumlah node di setiap tingkat dari pohon bertambah secara eksponensial terhadap jumlah tingkat, dan semuanya ini harus disimpan sekaligus.
2. Membutuhkan sejumlah besar pekerjaan, khususnya jika lintasan solusi terpendek cukup panjang, karena jumlah node yang perlu diperiksa bertambah secara eksponensial terhadap panjang lintasan.
3. Tidak relevannya operator akan menambah jumlah node yang harus diperiksa sangat besar.
4. Relatif membutuhkan waktu yang cukup lama, karena akan menguji semua node pada level ke-n untuk mendapatkan solusi pada level ke- (n + 1).
Pencarian Melebar Pertama (Breadth First Search)
Pada metode pencarian ini, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya.
Karena proses breadth first search mengamati setiap node di setiap level graf sebelum bergerak menuju ruang yang lebih dalam, maka mula-mula semua keadaan akan dicapai lewat lintasan yang terpendek dari keadaan awal. Oleh sebab itu, proses ini menjamin ditemukannya lintasan terpendek dari keadaan awal ke keadaan tujuan. Lebih jauh karena mula-mula semua keadaan ditemukan melalui lintasan terpendek sehingga setiap keadaan yang ditemui pada kali kedua didapati pada sepanjang sebuah lintasan yang sama atau lebih panjang. Kemudian, jika tidak ada kesempatan ditemukannya keadaan yang identik pada sepanjang lintasan yang lebih baik maka algoritma akan menghapusnya, sehingga keuntungan dari metode pencarian ini adalah:
1. Tidak akan menemui jalan buntu.
2. Jika ada satu solusi, maka breadth-first search akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.
Namun demikian, ada tiga persoalan utama berkenaan dengan metode pencarian ini, yaitu:
1. Membutuhkan memori yang besar, karena menyimpan semua node dalam satu pohon. Jumlah node di setiap tingkat dari pohon bertambah secara eksponensial terhadap jumlah tingkat, dan semuanya ini harus disimpan sekaligus.
2. Membutuhkan sejumlah besar pekerjaan, khususnya jika lintasan solusi terpendek cukup panjang, karena jumlah node yang perlu diperiksa bertambah secara eksponensial terhadap panjang lintasan.
3. Tidak relevannya operator akan menambah jumlah node yang harus diperiksa sangat besar.
4. Relatif membutuhkan waktu yang cukup lama, karena akan menguji semua node pada level ke-n untuk mendapatkan solusi pada level ke- (n + 1).
Pencarian Mendalam Pertama (Depth First Search)
Pencarian dengan metode Depth First Search (DFS) dilakukan dari node awal secara mendalam hingga yang paling akhir (dead-end) atau sampai ditemukan. Dengan kata lain, simpul cabang atau anak yang terlebih dahulu dikunjungi. Sebagai ilustrasinya dapat dilihat pada gambar 2.4.
Berdasarkan gambar 2.4, proses pencarian dilakukan dengan mengunjungi cabang terlebih dahulu hingga tiba di simpul terakhir. Jika tujuan yang diinginkan belum tercapai maka pencarian dilanjutkan ke cabang sebelumnya, turun ke bawah jika memang masih ada cabangnya. Begitu seterusnya hingga diperoleh tujuan (goal). Operasi semacam ini dikenal dengan sebutan backtracking.
Keuntungan dari metode DFS:
1. Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.
2. Secara kebetulan, metode DFS akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan, sehingga tidak memboros waktu untuk melakukan sejumlah besar keadaan ‘dangkal’ dalam permasalahan graf/pohon.
Kelemahan dari metode DFS:
1. Memungkinkan tidak ditemukannya tujuan yang diharapkan.
2. Hanya akan mendapatkan satu solusi pada setiap pencarian.
Pencarian dengan metode Depth First Search (DFS) dilakukan dari node awal secara mendalam hingga yang paling akhir (dead-end) atau sampai ditemukan. Dengan kata lain, simpul cabang atau anak yang terlebih dahulu dikunjungi. Sebagai ilustrasinya dapat dilihat pada gambar 2.4.
Berdasarkan gambar 2.4, proses pencarian dilakukan dengan mengunjungi cabang terlebih dahulu hingga tiba di simpul terakhir. Jika tujuan yang diinginkan belum tercapai maka pencarian dilanjutkan ke cabang sebelumnya, turun ke bawah jika memang masih ada cabangnya. Begitu seterusnya hingga diperoleh tujuan (goal). Operasi semacam ini dikenal dengan sebutan backtracking.
Keuntungan dari metode DFS:
1. Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.
2. Secara kebetulan, metode DFS akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan, sehingga tidak memboros waktu untuk melakukan sejumlah besar keadaan ‘dangkal’ dalam permasalahan graf/pohon.
Kelemahan dari metode DFS:
1. Memungkinkan tidak ditemukannya tujuan yang diharapkan.
2. Hanya akan mendapatkan satu solusi pada setiap pencarian.
0 komentar:
Post a Comment
Silahkan masukkan saran, komentar saudara, dengan ikhlas saya akan meresponnya.