Board Game

11.1 Game Theory

    Teori permainan adalah disiplin matematika yang berkaitan dengan studi tentang ideologi yang disarikan. Ini hanya aplikasi yang sangat lemah untuk game komputer real-time, namun terminologi yang digunakan dalam game berbasis giliran berasal darinya. Bagian ini akan memperkenalkan teori permainan yang cukup untuk memungkinkan Anda memahami dan menerapkan AI berbasis giliran, tanpa terjebak dalam poin matematika yang cerdas.

Types Of Game

   Teori permainan mengklasifikasikan permainan sesuai dengan jumlah pemain, jenis sasaran yang dimiliki pemain tersebut, dan informasi yang dimiliki setiap pemain tentang permainan tersebut.

1.Number Of Players

    Permainan papan yang mengilhami algoritma AI berbasis giliran hampir semuanya memiliki dua pemain. Sebagian besar algoritma populer dibatasi oleh dua pemain dalam bentuknya yang paling dasar. Mereka dapat disesuaikan untuk digunakan dengan jumlah yang lebih besar, namun jarang menemukan deskripsi tentang algoritma untuk hal lain selain dua pemain.

2.The Goal of the Game

  Dalam kebanyakan game strategi, tujuannya adalah untuk menang. Sebagai pemain, Anda menang jika semua lawan Anda kalah. Ini dikenal sebagai permainan zero-sum: kemenangan Anda adalah kehilangan lawan. Jika Anda mencetak 1 poin untuk menang, maka akan sama dengan skor-1 karena kalah. Ini tidak akan terjadi, misalnya, dalam permainan kasino, saat Anda semua bisa keluar lebih buruk.

  Dalam permainan zero-sum tidak masalah jika Anda mencoba untuk menang atau jika Anda mencoba membuat lawan kalah; thecomeisthesame.Foranon-zero-sumgame, di mana Anda bisa menemukan semua yang Anda inginkan, Anda ingin melakukan fokus pada kemenangan Anda, mengumpulkankan semua hasil akhir (kecuali jika Anda ada orang lain)

   Untuk game dengan lebih dari dua pemain, semuanya lebih kompleks. Bahkan dalam permainan zero-sum, strategi terbaik tidak selalu membuat lawan masing-masing kalah. Mungkin lebih baik untuk mengeroyok lawan terkuat, memberi keuntungan pada lawan yang lebih lemah dan berharap bisa menjemput mereka nanti.

3.Information

    Dalam game seperti Chess, Drafts, Go, dan Reversi, kedua pemain mengetahui segala hal yang perlu diketahui tentang kemungkinan terjadinya hal tersebut. Mereka mengetahui berapa banyak yang harus dilakukan pada setiap kesempatan dan kesempatan untuk melakukan langkah selanjutnya. Mereka tahu semua ini sejak awal permainan. Game semacam ini disebut "informasi yang sempurna." Meskipun Anda tidak tahu mana yang akan dipilih lawan Anda, Anda memiliki pengetahuan lengkap tentang setiap gerakan yang mungkin bisa dilakukan lawan dan efek yang dimilikinya.

4. Applying Algorithms

   Algoritma yang paling dikenal dan paling maju untuk game berbasis giliran dirancang untuk bekerja dengan permainan informasi dua pemain, zero-sum, sempurna. Jika Anda menulis AI bermain catur, maka ini adalah implementasi yang Anda butuhkan. Tapi banyak game komputer berbasis turn over lebih rumit, melibatkan lebih banyak pemain dan informasi yang tidak sempurna.

11.2 Algoritma Minimaxing

   Sebuah komputer memainkan permainan berbasis giliran dengan melihat tindakan yang ada pada gerakan ini dan memilihnya daripadanya. Untuk memilih salah satu dari mereka, dibutuhkan stok sekarang apa yang bergerak lebih baik daripada yang lain. Pengetahuan ini diberikan ke komputer oleh programmer menggunakan heuristik yang disebut fungsi evaluasi statis.

11.3 Transposition Tables anda Memory

   Sejauh ini algoritma yang kita lihat mengasumsikan bahwa setiap gerakan mengarah ke posisi papan yang unik. Seperti yang kita lihat sebelumnya, posisi dewan yang sama dapat terjadi sebagai hasil kombinasi gerakan yang berbeda. Dalam banyak game posisi board yang sama bahkan bisa terjadi beberapa kali dalam game yang sama. Agar pekerjaan ekstra mencari posisi dewan yang sama beberapa kali, algoritma dapat menggunakan tabel transposisi. Meskipun tabel transposisi dirancang untuk menghindari duplikasi pekerjaan pada transposisi, namun tabel tersebut memiliki manfaat tambahan. Beberapa algoritma mengandalkan tabel transposisi sebagai memori kerja posisi papan yang telah dipertimbangkan. Teknik seperti tes yang ditingkatkan memori, pendalaman berulang, dan berpikir pada giliran lawan Anda semua menggunakan tabel transposisi yang sama (dan semua diperkenalkan di bab ini). Tabel transposisi menyimpan catatan posisi papan dan hasil pencarian dari posisi itu. Ketika sebuah algoritma diberi posisi papan, pertama-tama periksa apakah papan itu ada dalam memori dan gunakan nilai yang tersimpan jika benar. Membandingkan status permainan yang lengkap adalah prosedur yang mahal, karena keadaan permainan mungkin berisi puluhan atau ratusan item informasi. Membandingkan ini dengan keadaan tersimpan dalam ingatan akan memakan waktu lama. Untuk mempercepat pemeriksaan tabel transposisi, nilai hash digunakan.

11.4 . Memori tambahan pda uji algoritma

    Algoritma memory-enhanced test (MT) bergantung pada adanya tabel transposisi yang efisien untuk bertindak sebagai algoritma'memory. MT hanyalah sebuah negamax AB nol-lebar, menggunakan tabel transposisi untuk menghindari duplikat pekerjaan. Keberadaan memori memungkinkan algoritma melompati pohon pencarian melihat gerakan yang paling menjanjikan terlebih dahulu. Sifat rekursif dari algoritma negamax berarti bahwa ia tidak dapat melompat; itu harus menggelembung dan recurse down.

11.5 Pembukaan buku dan set permainan

   Dalam banyak permainan, selama bertahun-tahun, pemain ahli telah membangun sebuah pengalaman tentang pergerakan mana yang lebih baik daripada yang lain di awal permainan. Tempat ini lebih jelas daripada di buku pembuka Catur. Pakar ahli mempelajari database besar kombinasi pembuka tetap, belajar tanggapan terbaik untuk bergerak. Hal ini tidak biasa untuk 20 sampai 30 langkah pertama dari permainan Catur Grandmaster yang akan direncanakan sebelumnya. Buku pembuka adalah daftar urutan bergerak, bersama dengan beberapa indikasi seberapa bagus hasil rata-rata akan menggunakan urutan tersebut. Dengan menggunakan seperangkat aturan ini, komputer tidak perlu mencari menggunakan minimaxing untuk menentukan langkah terbaik yang akan dimainkan. Ini hanya bisa memilih langkah selanjutnya dari urutan, selama titik akhir dari urutan itu bermanfaat baginya.

    Membuka database buku dapat diunduh untuk beberapa permainan yang berbeda, dan untuk game terkemuka seperti database komersial Chess tersedia untuk lisensi ke dalam game baru. Untuk game berbasis giliran asli, buku pembuka (jika berguna) perlu dibuat secara manual.

11.6 Optimisasi

    Meskipun dasar permainan-bermain algoritma masing-masing relatif sederhana, mereka memiliki array membingungkan optimasi yang berbeda. Beberapa pengoptimalan ini, seperti pemangkasan dan tabel transposisiAB, sangat penting untuk kinerja yang baik. Pengoptimalan lainnya cukup memanfaatkan sebagian besar kinerja. Bagian ini membahas beberapa pengoptimalan lainnya yang digunakan untuk turn-basedAI. Tidak ada cukup ruang untuk mencakup detail pelaksanaan untuk sebagian besar dari mereka. Lampiran memberi petunjuk lebih jauh informasi tentang pelaksanaannya Selain itu, optimasi khusus yang digunakan hanya dalam jumlah yang relatif kecil dari permainan papan tidak disertakan. Catur, khususnya, memiliki keseluruhan rakit pengoptimalan khusus yang hanya berguna dalam sejumlah kecil skenario lainnya.

11.7 Turn Base strategy game

    Bab ini memusatkan perhatian pada game board AI. Di hadapannya, game board AI memiliki banyak kemiripan permainan strategi berbasis toturn. Game strategi komersial jarang menggunakan teknik pencarian pohon di bab ini sebagai alat utama mereka. Kompleksitas permainan ini berarti algoritma pencarian macet sebelum mereka dapat membuat keputusan yang masuk akal. Teknik pencarian yang paling sederhana dirancang untuk permainan informasi dua pemain, zero-sum, informasi sempurna, dan banyak pengoptimalan terbaik tidak dapat disesuaikan untuk digunakan dalam permainan strategi umum. Beberapa permainan strategi berbasis turn-turn sederhana dapat langsung diperoleh dari algoritme pencarian pohon di bab ini. Konstruksi penelitian dan konstruksi, gerakan pasukan, dan aksi militer semuanya bisa menjadi bagian dari serangkaian kemungkinan pergerakan. Posisi dewan tetap statis selama sebuah pergantian. Antarmuka permainan yang diberikan di atas dapat, secara teori, diterapkan untuk mencerminkan turn- permainan berbasis Antarmuka yang diterapkan ini kemudian dapat digunakan dengan algoritma pencarian pohon reguler.

Referensi:

Artifical Intelligence For Games

Download ebook: http://lecturer.ukdw.ac.id/~mahas/dossier/gameng_AIFG.pdf

TEKNIK PEMBANGUNAN GAME AI

Movement
Komputer sebagai alat untuk pemindahan data yaitu untuk  pemindahan data yang telah dibuat dan akan bisa membuka kembali file yang telah kita buat dengan cara mengcopy paste file yang telah kita buat. Contohnya dari keyboard ke layar monitor. Dalam game, movement adalah metode yang menekankan konsep gerak tubuh, meliputi konsep kesadaran tubuh, konsep usaha, konsep ruang, dan konsep keterhubungan.

      Pathfinding
Pencarian jalur (pathfinding) merupakan bagian dari medel AI. Algoritma pathfinding menggunakan ‘Directed Non-Negative Weighted Graph’. Algoritma seperti Dijkstra dan A* menggunakan struktur data graf . Graf digunakan untuk menggambarkan jalur yang dapat diambil pada sebuah geometri ruang.


      Pengambilan Keputusan
Pengambilan keputusan adalah suatu proses pemilihan dari berbagai alternatif baik kualitatif maupun kuantitatif untuk mendapat suatu alternatif terbaik guna menjawab masalah atau menyelesaikan konflik (pertentangan).
Proses penurunan suatu keputusan mengandung empat unsur, yaitu :
v  Model : Model menunjukkan gambaran suatu rnasalah secara kuantitatif atau kualitatif.
v   Kriteria: Kriteria yang dirumuskan menunjukkan tujuan dari keputusan yang diambil. Jika terdapat beberapa kriteria yang saling bertentangan, maka pengambilan keputusan harus melalui kompromi (misalnya menambah jasa langganan dan mengurangi persediaan, maka keputusan mana yang diambil perlu kompromi).
v   Pembatas: Faktor-faktor tambahan yang perlu diperhatikan dalam memecahkan masalah pengambilan keputusan. Misalnya dana yang kurang tersedia.
v  Optimalisasi: Apabila masalah keputusan telah diuraikan dengan sejelas jelasnya, maka manajer menentukan apa yang diperlukan (kriteria) dan apa yang diperbolehkan (pembatas). Pada keadaan ini pengambil keputusan siap untuk memilih pemecahan yang terbaik atau yang optimal.

Proses Pengambilan Keputusan

Ø  Penyelidikan: Mempelajari lingkungan atas kondisi yang memerlukan keputusan. Data mentah diperoleh, diolah, dan diuji untuk dijadikan petunjuk yang dapat mengidentifikasi persoalan.
Ø  Perancangan: Mendaftar, mengembangkan, dan menganalisis arah tindakan yang mungkin. Hal ini meliputi proses-proses untuk memahami persoalan, menghasilkan pemecahan, dan menguji kelayakan pemecahan tersebut.
Ø  Pemilihan: Memilih arah tindakan tertentu dari semua yang ada. Pilihan ditentukan dan dilaksanakan.

Jadi, proses keputusan dapat dianggap sebagai sebuah arus dari penyelidikan sampai perancangan dan kemudian pada pemilihan. Tetapi pada setiap tahap hasilnya mungkin dikembalikan ke tahap sebelumnya untuk dimulai lagi. Jadi tahapan tersebut merupakan unsur-unsur sebuah proses yang berkesinambungan.

Teori Pengambilan Keputusan
Teori pengambilan keputusan menekankan bahwa terdapat tujuh langkah yang harus ditempuh, yaitu:

1. Identifikasi permasalahan yang dihadapi
Ada ungkapan yang mengatakan bahwa suatu “permasalahan yang sudah dikenali hakikatnya dengan tepat sesungguhnya sudah separo terpecahkan.” Ungkapan ini mempunyai tiga implikasi, yaitu:
ü  Bahwa mutlak perlu mengenali secara mendasar situasi problematik yang menimbulkan ketidakseimbangan dalam kehidupan organisasi atau perusahaan.
ü  Pengenalan secara mendasar berarti “akar” penyebab timbulnya ketidakseimbangan harus digali sedalam-dalamnya.
ü   Mengambil keputusan tidak boleh puas hanya dengan diagnosis gejala-gejala yang segera tampak. Jika hanya gejala yang diidentifikasikan, sangat mungkin “terapinya” pun hanya mampu menghilangkan gejala tersebut. Padahal yang harus dihilangkan adalah “sumber penyakitnya”.

2. Pengumpulan data
Berangkat dari pandangan bahwa pengambilan keputusan memerlukan dukungan informasi yang lengkap, mutakhir, dapat dipercaya, dan diolah dengan baik. Berarti bahwa dalam pengumpulan data ada tiga hal yang mutlak mendapat perhatian, yaitu:
·         Pentingnya menggali data dari semua sumber yang layak digali, baik secara internal maupun secara eksternal. Dari segi inilah harus dilihat pentingnya akses bagi para pengolah data terhadap semua sumber data.
·         Pentingnya untuk menjamin bahwa data yang dikumpulkan relevan dengan permasalahan yang hendak diatasi.
·         Bahwa mutu data yang dikumpulkan haruslah setinggi mungkin sehingga informasi yang dihasilkan akan bermutu tinggi pula.

3. Analisis data
Analisis data harus mampu menunjukkan berbagai alternatif yang mungkin ditempuh untuk memecahkan masalah. Oleh karena itu, analisis data diarahkan pada pembentukan persepsi yang sama diantara berbagai pihak tentang arti data yang dimiliki, dengan demikian memberikan interpretasi yang sama tentang data tersebut.

 4.Analisis berbagai alternatif
Salah satu tantangan yang dihadapi dalam mengambil keputusan ialah menemukan jawaban yang paling tepat terhadap pertanyaan: Apakah dalam mengambil keputusan harus selalu terdapat berbagai alternatif? Pertanyaan ini penting karena jika seorang pengambil keputusan dihadapkan kepada hanya satu alternatif dan ia memutuskan untuk menggunakan alternatif tersebut, yang bersangkutan sudah mengambil keputusan. Bahkan teori pengambilan keputusan mengatakan bahwa jika seseorang memutuskan untuk tidak mengambil keputusan, tindakannya itu adalah pengambilan keputusan juga.

5.Pemilihan alternatif
Jika dilakukan dengan cermat, analisis berbagai alternatif akan “memberi petunjuk” tentang alternatif yang sebaiknya digunakan karena akan membuahkan solusi yang paling efektif. Alternatif di pilih dengan demikian, merupakan alternatif yang tampaknya paling baik. Pengalaman mengambil keputusan di masa lalu dan keyakinan bahwa keputusan yang diambil adalah keputusan yang terbaik.

6.Implementasi (pelaksanaan)
Apakah alternatif yang dipilih merupakan pilihan yang terbaik atau tidak diuji pada waktu digunakan dalam arti mampu tidaknya menghilangkan situasi permasalahan dan apakah permasalahan yang dihadapi tersebut dapat dipecahkan secara efektif atau tidak.

7.Evaluasi (penilaian)
Hasil pelaksanaan memerlukan penilaian yang objektif, rasional dan berdasarkan tolok ukur yang baku. Seperti dimaklumi, hasil penilaian dapat menunjukkan bahwa hasil yang di capai melampaui harapan, sekedar sesuia dengan sasaran atau kurang dari sasaran. Kesemuanya itu menjadi bahan penting dalam mengelola organisasi atau perusahaan di masa depan.

      Taktik dan strategi AI
AI dalam game biasanya memiliki kecepatan dalam taktik bermain sehingga mengharuskan pemain untuk berfikir lebih cepat untuk menyusun strategi terbaik agar dapat memperoleh skor yang maksimal. Kecerdasan buatan merupakan kecerdasan yang ditujukan oleh suatu entitas buatan, yang diciptakan dan diterapkan kedalam sebuah mesin (komputer) sehingga dapat melakukan perbuatan seperti manusia. Strategi dalma gamepun bervariasi. Salah satunya adalah dalam game Othello yaitu strategi bermain reversy, sperti jumlah pin, penguasaan sudut/x-square/c-square, jumlah pin stabil, mobility, jumlah pin tepi, parity, dan pola sisi/sudut.

Pembelajaran
Machine learning adalah teknik AI yang berkaitan dengan pembelajaran data dan menggunakannya untuk memprediksi informasi yang ada di dunia.
Machine learning dibangun dengan menggunakan algoritma. Rangkaian instruksi ini akan menyelesaikan suatu permasalahan. Contoh algoritma yang dimaksud adalah decision tree learning dan association rule learning.
Namun, algoritma machine learning yang berperan dalam kehidupan di dunia adalah jaringan saraf buatan, suatu teknik yang terinspirasi oleh cara kerja neuron otak manusia.
Sederhananya begini: suatu jaringan saraf terdiri dari beberapa lapisan neuron. Input masuk melalui lapisan pertama. Tiap neuronnya menerima input, sehingga setiap neuron memiliki muatan, dan menghasilkan output berdasarkan muatan mereka. Output dari lapisan pertama kemudian didistribusikan ke lapisan kedua untuk diproses, dan begitu seterusnya hingga output akhir dapat dihasilkan.
Kemudian hal menarik pun terjadi. Siapapun yang menjalankan jaringan dapat mendefinisikan seperti apa output akhir yang “benar” seharusnya. Setiap kali data didistribusikan melalui jaringan tersebut, hasil akhirnya dibandingkan dengan hasil yang “benar”, dan sejumlah penyempurnaan akan dilakukan hingga tercipta outputakhir yang benar. Dengan kata lain, jaringan tersebut mampu melatih dirinya sendiri.
Otak buatan ini dapat mempelajari bagaimana cara mengidentifikasi banyak hal. Misalnya kursi dalam sebuah foto,. Seiring berjalannya waktu, ia dapat mempelajari karakteristik kursi tersebut, dan meningkatkan kemampuannya dalam mengidentifikasi benda tersebut.

Referensi:
http://web.cecs.pdx.edu/~mperkows/CLASS_479/2017_ZZ_00/02__GOOD_Russel=Norvig=Artificial%20Intelligence%20A%20Modern%20Approach%20(3rd%20Edition).pdf

Kecerdasan Buatan dan Permainan (AI and Games)

DEFINISI KECERDASAN BUATAN

•H. A. Simon [1987] :
“ Kecerdasan buatan (artificial intelligence ) merupakan kawasan
penelitian, aplikasi dan instruksi yang terkait dengan pemrograman
komputer untuk melakukan sesuatu hal yang -dalam pandangan
manusia adalah- cerdas ”

•Rich and Knight[1991]:
“Kecerdasan Buatan (AI) merupakan sebuah studi tentang bagaimana
membuat komputer melakukan hal-hal yang pada saat ini dapat
dilakukan lebih baik oleh manusia.”

•Encyclopedia  Britannica:
“Kecerdasan Buatan (AI) merupakan cabang dari ilmu komputer yang
dalam merepresentasi pengetahuan lebih banyak menggunakan bentuk
simbol-simbol daripada bilangan, dan memproses informasi berdasarkan
metode heuristic atau dengan berdasarkan sejumlah aturan”

Pengertian Game

Salah satu program yang bisa berjalan di dalam perangkat berbasis komputer adalah program game atau program permainan. Kita dapat dengan mudah mendapatkan game untuk dijalankan pada komputer atau smartphone. Secara garis besar game terbagi kepada dua jenis, yang pertama adalah game offline dan yang kedua adalah game online. Game offline maksudnya adalah game yang bisa digunakan pada komputer atau smartphone tanpa harus terhubung ke internet. Hal tersebut dimungkinkan untuk dilakukan karena semua perintah dan data game sudah terpasang di dalam komputer. Sedangkan game online ini sifatnya terpusat pada suatu server. Sehingga untuk menjalankannya dibutuhkan akses ke server tersebut melalui jaringan internet.

Mode Game AI

Banyak macam mode pada game AI. Setiap game memiliki mode yang berbeda-beda, contohnya seperti kita melawan ai dalam suatu pertempuran.

Algoritma, Struktur Data dan Representasi

•MINIMAX, Sebuah prosedur pencarian yg melihat kedepan, memperhatikan apa yg akan terjadi, kemudian yang digunakan untuk memilih langkah berikutnya.
•ALPHA-BETA PRUNING, Algoritma ini merupakan improvisasi dari algoritma minimax. Algoritma ini untuk meningkatkan efisiensi fungsi minimax dalam hal pencarian, kemudian fungsi evaluasi ditambahkan sepasang nilai alpha dan beta.

•FUZZY, Logika fuzzy merupakan pengembangan dari logika boolean. Sistem fuzzy atau logika fuzzy adalah salah satu bahasa soft computing yang memiliki karakteristik dan keunggulan dalam menangani permasalahan yang bersifat ketidakpastian dan kebenaran parsial. Logika fuzzy merupakan pengembangan dari logika boolean yang hanya memiliki nilai true (1) atau false (0).

•ALGORITMA GENETIKA, Algoritma genetika adalah algoritma yang berusaha menerapkan pemahaman mengenai evolusi alamiah pada tugas-tugas pemecahanmasalah (problem solving). Pendekatan yang diambil oleh algoritma ini adalah dengan menggabungkan secara acak berbagai pilihan solusi terbaik di dalam suatu kumpulan (populasi) untuk mendapatkan generasi solusi terbaik berikutnya yaitu pada suatu kondisi yang memaksimalkan kecocokannya atau lazim disebut fitness.

•ALGORITMA AI (ARTIFICIAL INTELEGENCE), Kecerdasan Buatan (Artificial Intelligence) merupakan cabang terpenting dalam dunia computer yang membuat agar mesin (computer) dapat melakukan pekerjaan seperti dan sebaik yang dilakukan manusia. Pada awalnya diciptakan computer hanya berfungsi sebagai alat hitung. Tapi sekarang peran computer makin mendominasi kehidupan manusia. Komputer di harapkan data diberdayakan untuk mengerjakan segala sesuatu yang biasa dikerjakan oleh manusia.

Kompleksitas Kesalahan
Dalam konteks kecerdasan buatan dalam permainan video, kecurangan mengacu pada programmer agen memberikan akses ke informasi yang tersedia kepada pemain. Penggunaan kecurangan dalam AI menunjukkan keterbatasan “kecerdasan” dicapai artifisial, secara umum, dalam permainan di mana kreativitas strategis sangat penting, manusia dengan mudah bisa mengalahkan AI setelah minimal trial and error jika bukan untuk keuntungan ini


Jenis Game AI

•Role Playing Game (RPG)
RPG adalah salah satu game yg mengandung unsur experience (EXP) atau leveling dalam gameplay nya. Para pemain biasanya dapat membuat/menjadi karakter yang diinginkan. Kemampuan karakter tersebut ditentukan berdasarkan jumlah EXP atau level karakter. Semakin tinggi karakter, akan membuka kemampuan-kemampuan yang baru yang dapat membuat suasana game menjadi semakin menarik. Biasanya dalam game ini kita memiliki kebebasan untuk menjelajah dunia game tersebut, dan kadang kala dalam beberapa game, kita dapat menentukan ending dari game tersebut.

•First Person Shooting (FPS)
FPS adalah genre game dimana para pemainnya saling tembak menembak. Genre game ini memiliki ciri utama yaitu penggunaan sudut pandang orang pertama yang membuat kita dibelakang senjata.

•Strategy
Sesuai dengan namanya, game bergenre strategy adalah genre game yg memiliki gameplay untuk mengatur suatu unit atau pasukan untuk menyerang markas musuh dalam rangka memenangkan permainan. Biasanya di dalam game Strategy, kita diharuskan membangun pasukan dari berbagai sumber daya yang diberikan seperti wood, gold, meat, dan lain sebagainya.

•Simulation
Adalah genre yang mementingkan realisme. Segala faktor pada game ini sangat diperhatikan agar semirip didunia nyata. Segala nilai, material, referensi, dan faktor lainnya didasarkan pada dunia nyata. Cara memainkannya juga berbeda, karena biasanya kontrol yang dimiliki cukup rumit. Genre simulasi meliputi game racing, flight, sampai militer.

•Arcade
Arcade game adalah genre game yang tidak terfokus pada cerita dan bahkan hanya dimainkan “just for fun”.

•Action Adventure
Action Adventure adalah genre game petualangan dengan salah seorang karakter yg penuh dengan penuh aksi yg akan terus ada hingga game tersebut tamat.

•Fighting Game
Fighting adalah genre game bertarung. Seperti dalam arcade, pemain dapat mengeluarkan jurus-jurus ampuh dalam pertarungannya (biasanya berupa serangan kombo atau jurus andalan tiap karakter). Genre fighting biasanya one vs one dalam sebuah arena yang sempit.

•Sport
Adalah genre bertema permainan olahraga. Sistem permainan baik gameplay dan peraturannya akan berbeda-beda tergantung jenis olahraga yang menjadi tema game tersebut.

Keceptan dan Memori
Memori yang besar dan memiliki kecepatan yang besar dapat mempengaruhi kinerja program.

referensi

http://www.mandalamaya.com/pengertian-game-menurut-para-ahli/
wsilfi.staff.gunadarma.ac.id/Downloads/files/4338/1-AI.pdf
https://www.kreasitekno.com/ini-dia-jenis-jenis-game-yang-wajib-kalian-ketahui-sebagai-gamer/

Pembelajaran / Learning

Nama : Ananto Dwicahyo
NPM : 10115651
Kelas : 3KA10
Dosen : Essy Malays Sari Sakti

 Setiap komponen agen dapat ditingkatkan dengan belajar dari data.

 Perbaikan, dan teknik yang digunakan untuk membuatnya, bergantung pada empat faktor utama:


• Komponen mana yang harus diperbaiki?

• Apa pengetahuan sebelumnya yang dimiliki agen.

• Representasi apa yang digunakan untuk data dan komponennya.

• Umpan balik apa yang tersedia untuk dipelajari.



Komponen yang dipelajari

Komponen dari agen ini meliputi:

1. Pemetaan langsung dari kondisi pada keadaan saat ini terhadap tindakan.
2. Suatu cara untuk menyimpulkan sifat-sifat yang relevan dari dunia dari urutan percept.
3. Informasi tentang cara dunia berkembang dan tentang hasil tindakan yang mungkin dilakukan agen.
4. Informasi utilitas yang menunjukkan keinginan negara-negara dunia.
5. Action-value information yang menunjukkan keinginan tindakan.
6. Sasaran yang menggambarkan kelas-kelas negara yang prestasinya memaksimalkan utiliti agen. Masing-masing komponen ini bisa dipelajari. Anggap saja, misalnya, pelatihan anaerobik adalah sopir taksi. Setiap kali instruktur berteriak "Brake!" Agen bisa mempelajari peraturan tindakan-kondisi untuk kapan harus mengerem (komponen 1); agen juga belajar setiap kali instruktur tidak berteriak. Dengan melihat banyak gambar kamera yang diberi tahu berisi bus, ia bisa belajar mengenali mereka (2). Dengan mencoba tindakan dan mengamati hasilnya-misalnya, mengerem keras di jalan yang basah-ia dapat mempelajari efek dari tindakannya (3). Kemudian, ketika tidak mendapat tip dari penumpang yang benar-benar terguncang selama perjalanan, ia dapat mempelajari komponen yang berguna dari keseluruhan fungsi utilitasnya (4).





Pembelajaran Induktif

    Dimungkinkan untuk membangun sistem pakar menggunakan Artificial Neural System. Sebagai contoh sebuah sistem pakar medis. ANS adalah knowledge base yang dibangun berdasarkan pelatihan data pengobatan penyakit. Sistem pakar ini mencoba mengklarifikasi penyakit dari gejalanya yang diketahui dengan cara pelatihan. Inference engine MACIE (Matrix Controlled Inference Engine) dirancang menggunakan ANS knowledge base. Sistem ini menggunakan metode forward chaining untuk melakukan inferensi dan metode backward chaining untuk query data tambahan yang diperlukan terhadap user. Meskipun ANS tidak dapat menjelaskan proses yang dilakukannya seperti mengapa sebuah neuron memiliki bobot tertentu, namun MACIE dapat menginterpretasikan ANS dan menghasilkan aturan IF-THEN untuk menjelaskannya.

    Sebuah sistem pakar dengan ANS menggunakan metode pembelajaran induktif, yaitu sistem menghasilkan informasi yang termuat di knowledge-base berdasarkan contoh yang diberikan. Induksi adalah proses inferensi kasus yang umum dari kasus khusus. Tujuan pembelajaran induktif adalah mengurangi atau mengeliminasi masalah kemacetan perolehan knowledge.

Pohon Keputusan Pembelajaran


    Pohon keputusan adalah salah satu bentuk pembelajaran mesin yang paling sederhana namun paling

berhasil. Kami pertama-tama menggambarkan representasi tersebut - ruang hipotesis - dan kemudian

menunjukkan bagaimana cara mempelajari hipotesis yang baik.


Representasi pohon keputusan

    Pohon keputusan mewakili fungsi yang mengambil sebagai masukan sebuah vektor nilai atribut

dan mengembalikan sebuah "keputusan" - sebuah nilai keluaran tunggal. Nilai input dan output

dapat diskrit atau kontinyu. Untuk saat ini kita akan berkonsentrasi pada masalah dimana input

memiliki nilai diskrit dan hasilnya memiliki dua nilai yang tepat; Ini adalah klasifikasi Boolean,

di mana setiap masukan contoh akan diklasifikasikan sebagai benar (contoh positif) atau salah

(contoh negatif). Pohon keputusan mencapai keputusannya dengan melakukan serangkaian tes.

Setiap simpul internal di pohon sesuai dengan uji nilai salah satu atribut input, Ai, dan cabang

 dari nodus diberi label dengan nilai atribut yang mungkin, Ai = vik. Setiap simpul daun di pohon

menentukan nilai yang akan dikembalikan oleh fungsinya. Representasi pohon keputusan itu alami

bagi manusia; Memang, banyak manual "Cara" (mis., untuk perbaikan mobil) seluruhnya ditulis

sebagai pohon keputusan tunggal yang terbentang di ratusan halaman. Sebagai contoh, kita akan

membuat pohon keputusan untuk memutuskan apakah akan menunggu meja di restoran.

Tujuannya di sini adalah untuk mempelajari definisi predikat predikat WillWait.

Daftar pertama atribut yang akan kita pertimbangkan sebagai bagian dari masukan:


1. Alternatif: apakah ada alternatif restoran yang sesuai di dekatnya.

2. Bar: apakah restoran memiliki area bar yang nyaman untuk ditunggu.

3. Fri / Sat: benar pada hari Jumat dan Sabtu.

4. Lapar: apakah kita lapar?

5. Pelindung: berapa banyak orang yang ada di restoran (nilainya tidak ada, beberapa, dan penuh).

6. Harga: kisaran harga restoran ($, $$, $$$).

7. Hujan: apakah sedang hujan di luar.

8. Reservasi: apakah kami melakukan reservasi.

9. Tipe: jenis restoran (Prancis, Italia, Thailand, atau burger).

10. WaitEstimate: menunggu diperkirakan oleh host (0-10 menit, 10-30, 30-60, atau> 60).






Pembelajaran Ensemble


    Sejauh ini kita telah melihat metode pembelajaran di mana hipotesis tunggal, yang dipilih dari ruang hipotesis, digunakan untuk membuat prediksi. Gagasan metode pembelajaran ensemble adalah memilih koleksi, atau ansambel, dari hipotesis dari ruang hipotesis dan menggabungkan prediksi mereka. Misalnya, selama validasi silang kita bisa menghasilkan dua puluh pohon keputusan yang berbeda, dan mintalah mereka memberikan suara pada klasifikasi terbaik untuk contoh baru.Motivasi belajar ensemble itu sederhana. Pertimbangkan sebuah ensemble K = 5hypotheses dan anggaplah wecombine theirpredictions menggunakan voting mayoritas sederhana. Forthe ansambel untuk salah mengartikan contoh baru, setidaknya tiga dari lima hipotesis harus salah mengartikannya. Harapannya adalah bahwa ini jauh lebih kecil kemungkinannya daripada klasifikasi yang salah oleh hipotesis tunggal. Misalkan kita asumsikan bahwa setiap hipotesis hk dalam ansambel memiliki kesalahan p-yaitu probabilitas bahwa contoh yang dipilih secara acak salah dikelompokkan oleh hk adalah hal. Selanjutnya, anggaplah kita mengetahui bahwa kesalahan yang dibuat oleh hipotesis adalah independen. Dalam kasus ini, jika p kecil, maka kemungkinan sejumlah besar kesalahan klasifikasi terjadi sangat kecil. Sebagai contoh, perhitungan sederhana (Latihan 18.18) menunjukkan bahwa menggunakan ensemble fibroadypotheses mengurangi tingkat kesalahan 1 dari 10 sampai tingkat kesalahan kurang dari 1 dari 100. Sekarang, jelas asumsi independensi tidak masuk akal, karena hipotesis cenderung disesatkan dengan cara yang sama oleh aspek data pelatihan yang menyesatkan. Tetapi jika hipotesis paling sedikit sedikit berbeda, sehingga mengurangi korelasi antara theerrors, maka ensemble pembelajaran bisa sangat bermanfaat.

Referensi:

http://web.cecs.pdx.edu/~mperkows/CLASS_479/2017_ZZ_00/02__GOOD_Russel=Norvig=Artificial%20Intelligence%20A%20Modern%20Approach%20(3rd%20Edition).pdf

Ketidakpastian (Uncertainty) dan Penalaran Probabilitas

Nama : Ananto Dwicahyo
NPM : 10115651
Kelas : 3KA10
Dosen : Essy Malays Sari Sakti
 
Ketidakpastian  dapat  dianggap  sebagai  suatu kekurangan  informasi  yang  memadai  untuk
membuat suatu keputusan. Ketidakpastian  merupakan  suatu  permasalahan karena  mungkin  menghalangi  kita  membuat suatu keputusan yang terbaik.

TEORI PROBABILITAS

- Teori formal probabilitas dibuat dengan menggunakan 3 aksioma
- Teori aksiomatik disebut juga objective theory of probability
diperkenalkan oleh Kolmogorov, sedangkan teori aksiomatik probabiliti kondisional
dibuat oleh Renyi
- Tiga aksioma probabilistik :
1. 0 < P(E) < 1
Aksioma ini menjelaskan bahwa jangkauan
probabilitas berada antar 0 dan 1. Jika suatu
kejadian itu pasti terjadi maka nilai probabilitasnya
adalah 1, dan jika kejadiannya tidak mungkin
terjadi nilai probabilitasnya adalah 0
2. E P(Ei) = 1
Aksioma ini menyatakan jumlah semua kejadian
tidak memberikan pengaruh dengan lainnya, maka
disebut mutually exclusive events yaitu 1.
Corollary dari aksioma ini adalah :
 P(E) + P(E’) = 1
3. P(E1 U E2) = P(E1) + P(E2)
Dimana E1 dan E2 adalah kejadian mutually
exclusive. Aksioma ini mempunyai makna bahwa
jika E1 dan E2 keduanya tidak dapat terjadi secara
simultan, maka probabilitas dari satu atau kejadian
lainnya adalah jumlah dari masing-masing
probabilitasnya.

Theorema Bayes

Ditemukan oleh Thomas Bayes Teorema  Bayes  kebalikan  dari  probabilitas  kondisional
P(A|B) atau  disebut posteriori  probability,  dimana  dalamteorema  Bayes  : state  probabilitas  dari  kejadian  awal diberikan untuk melihat kejadian yang mungkin akan terjadi kemudian.

Representasi Ketidakpastian

Tiga metode dasar untuk merepresentasikan ketidakpastian adalah
1. numeric,
2. grafik, dan
3. simbolik.

TEORI DEMPSTER-SHAFER

                Dempster shafer adalah suatu teori matematika untuk pembuktian berdasarkan belief functions and reasoning (Fungsi kepercayaan dan pemikiran yang masuk akal), yang digunakan untuk mengkombinasikan potongan informasi yang terpisah (bukti) untuk mengkalkulasi kemungkinan dari suatu peristiwa. Teori ini dikembangkan oleh Arthur P.Dempster dan Glenn shafer.

Secara umum teori Dempster-Shafer ditulis dalam suatu interval :
[Belief, Plausibility]
Belief (Bel) adalah ukuran kekuatan evidence dalam mendukung suatu himpunan proposisi.
Jika bernilai 0 mengindikasikan bahwa tidak ada evidence, dan Plausibility (Pl) jika bernilai
1 menunjukkan adanya kepastian.
Plausibility dinotasikan sebagai :
Pl(s) = 1 – Bel(Øs)

referensi

http://rudity.staff.gunadarma.ac.id/Downloads/files/36676/5-Uncertainity.pdf

Representasi Pengetahuan

Representasi dimaksudkan untuk menangkap sifat-sifat penting problema dan membuat informasi tsb. Dapat di akses oleh prosedur pemecahan permasalahan.Bahasa repsentasi harusa dapat membuat seorang pemrogram mampu mengekspresikan pengetauan yang di pelukan untuk mendapatkan solusi permasalahan.


1.          Rekayasa ontologi


Teknik ontologi dalam ilmu komputer dan ilmu informasi adalah bidang yang mempelajari metode dan metodologi untuk membangun ontologi: representasi formal dari sekumpulan konsep dalam domain dan hubungan antara konsep-konsep tersebut. Representasi konsep abstrak berskala besar seperti tindakan, waktu, objek fisik dan kepercayaan akan menjadi contoh teknik ontologis.


2.          Pengkategorian dan Objek


Pengorganisasian objek ke dalam kategori adalah bagian penting dari representasi pengetahuan. Meskipun interaksi dengan dunia terjadi pada tingkat objek individual, banyak penalaran terjadi pada tingkat kategori. Misalnya, pembelanja biasanya memiliki tujuan membeli bola basket, bukan bola basket tertentu seperti BB9. Kategori juga berfungsi untuk membuat prediksi tentang objek begitu mereka diklasifikasikan. Seseorang menyimpulkan adanya objek tertentu dari input perseptual, kategori kategori dari kategori yang dirasakan dari objek, dan kemudian menggunakan informasi kategori untuk membuat prediksi tentang objek.


Pengkategorian dan objek terdiri dari :

-               Komposisi fisik

-               Pengukuran

-               Substansi dan objek


3.          Aksi, Situasi dan Kejadian/Event

-               Aksi

Adalah tindakan yang dilakukan berdasarkan suatu kejadian.


-               Situasi

Keadaan sekitar yang sedang berlangsung.


-               Kejadian/event

Sesuatu yang sedang terjadi di sebuah lingkungan dimana terjadi pada waktu yang sedang berlangsung maupun yang telah terjadi.


4.  Mental Event dan Mental Objek: Pengetahuan dan Kepercayaan, Pengetahuan Waktu dan Aksi.


Pengetahuan dan Kepercayaan


Pengetahuan adalah informasi yang diketahui atau disadari oleh manusia, atau pengetahuan adalah berbagai gejala yang ditemui dan diperoleh manusia melalui pengamatan indrawi. Pengetahuan akan muncul ketika orang menggunakan akal atau indranya untuk mengenali benda atau peristiwa tertentu yang belum pernah dilihat atau dirasakan. Misalnya, saat pertama kali orang makan cabai maka Dia akan tahu bagaimana rasa cabai itu, bentuknya, warnanya, atau bahkan akan bertanya-tanya apa zat-zat apa yang dikandungnya.


Pengetahuan empiris menekankan pada pengamatan dan pengalaman indrawi, sedangkan pengetahuan rasional didapatkan melalui akal budi. Misalnya, orang mengetahui bahwa cabai rasanya pedas karena dia pernah memakannya. Tidak mungkin hanya dengan dipikir-pikir orang itu akan mengetahui bahwa rasa cabai adalah pedas. Nemun, pernyataan 1+1=2 adalah hasil dari pemikiran (akal) manusia, bukan merupakan suatu pengamatan empiris.


Keyakinan adalah suatu sikap yang ditunjukkan manusia saat dia merasa cukup tahu dan menyimpulkan bahwa dirinya telah mencapai kebenaran. Maksudnya adalah orang akan merasa yakin kalau apa yang mereka ketahui adalah benar. Jadi, keyakinan terjadi setelah orang percaya adanya suatu kebenaran.


Menurut teori kebenaran sebagai kesesuaian, keyakinan adalah suatu pernyataan yang tidak disertai bukti yang nyata. Misalnya, petir disebabkan oleh amukan para dewa. Pernyataan ini tidak bisa dibuktikan, sehingga hanya bisa dikatakan sebagai suatu keyakinan. Sementara pernyataan petir disebabkan kerena adanya tabrakan antara awan yang bermuatan positif dan negative adalah suatu kebenaran, karena dapat dibuktikan. Sehingga pernyataan ini disebut sebagai pengetahuan.



Ada dua istilah yang berhubungan dengan keyakinan dan pengetahuan.


1.           Magic power- (kekuatan magis) –> fenomena kekuatan gaib. Orang yang lebih percaya pada sesuatu yang aneh(karena tidak tahu sebabnya) sebagai kekuatan magis.


2.              Naturalisme, berarti sesuatu yang alami.


3.       Sistem Penalaran untuk Pengkategorian : Jaringan Semantik , Logika Deskripsi


Jaringan semantik


Jaringan semantik adalah gambaran pengetahuan grafis yang menunjukkan hubungan antar berbagai objek, terdiri dari lingkaran-lingkaran yang dihubungkan dengan anak panah yang menunjukkan objek dan informasi tentang objek-objek tersebut.


Dalam mata kuliah Pengantar Kecerdasan Buatan script merupakan representasi pengetahuan berdasarkan karakteristik yang sudah dikenal sebagai pengalaman-pengalaman yang menggambarkan urutan peristiwa.


Terdapat enam elemen script, yaitu :


1.            Kondisi input, merupakan kondisi yang harus dipenuhi sebelum terjadi.

2.            Track, yaitu variasi kemungkinan yang terjadi.

3.            Prop, yaitu objek yang digunakan dalam suatu peristiwa.

4.            Role, yaitu peran dalam suatu peristiwa.

5.            Scene, yaitu adegan dalam suatu peristiwa.

6.            Hasil, yaitu kondisi setelah terjadinya urutan peristiwa.


Deskripsi logika


Deskripsi logika (deskripsi jamak logika) (logika) Salah satu keluarga bahasa representasi pengetahuan yang dapat digunakan untuk mewakili definisi konsep domain aplikasi (dikenal sebagai pengetahuan terminologi) dalam cara yang terstruktur dan formal dipahami dengan baik.


6.          Penalaran Dengan Informasi Default


Manusia memecahkan masalah melalui kombinasi antara fakta dan pengetahuan (knowledge). Penalaran (reasoning) adalah proses yang berhubungan dengan pengetahuan, fakta, dan strategi pemecahan masalah (problem solving) untuk mendapatkan konklusi/penyelesaian. Berbagai metode penalaran yang lazim adalah deduksi, induksi, abduktip, analogi, dan akal sehat, berikut ini penjelasan singkatnya.



Deduksi (Deduction)


Manusia menggunakan deduksi untuk mendapatkan informasi baru dari informasi yang sudah diketahui (pengetahuan) yang ada relasinya. Penalaran deduksi menggunakan fakta-fakta dari masalah yang ada dan pengetahuan umum yang sesuai yang pada umumnya berbentuk aturan (rules) atau implikasi (implications), jadi dari hal yang umum, dikenakan pada hal yang khusus, model deduksi adalah:



Fakta + Rule -> Efek dengan rule dalam bentuk:


If <cause/premise> then <effect/conclusion>


Jika <sebab/premis> Maka <akibat/konklusi>


Sebagai contoh:


Aturan/implikasi: Jika saya berdiri di hujan, maka saya akan basah.


Fakta/premis : Saya berdiri di hujan.


Konklusi : Saya akan basah.


Penalaran deduksi sangat menarik secara logika dan merupakan teknik solusi masalah yang paling umum digunakan oleh manusia. Aturan inferensi (penyimpulan) yang disebut modus ponens adalah bentuk dasar dari penalaran deduksi dengan formula sbb.: Jika A adalah benar, dan Jika A maka B adalah benar, maka B adalah benar.



Induksi (Induction)

Manusia menggunakan induksi untuk mendapatkan kesimpulan umum (general conclusion) dari sekumpulan/himpunan fakta melalui proses generalisasi. Ini bagaikan transisi dari jumlah sedikit ke semua. Model induksi adalah:

Cause + Effect -> Rule


Proses induksi dijelaskan oleh Firebaugh (1988) sbb.:


Untuk suatu himpunan objek X = {a,b,c,d, …}, jika sifat P adalah benar untuk a, dan jika sifat P adalah benar untuk b, dan jika sifat P adalah benar untuk c, …, maka sifat P adalah benar untuk semua X.


Sebagai contoh:


Fakta/premis : aluminium dipanaskan memuai

Fakta/premis : besi dipanaskan memuai

Fakta/premis : tembaga dipanaskan memuai


Konklusi : secara umum, semua besi bila dipanaskan akan memuai



Abduktip (Abductive)

Abduktip adalah bentuk deduksi yang memungkinkan menarik kesimpulan yang bersifat “plausible”. Plausible (masuk akal) adalah konklusi yang ditarik dari informasi yang tersedia, namun ada kemungkinan konklusi itu salah, jadi model abduktip adalah:


Jika B adalah benar, dan Jika A maka B adalah benar, maka A adalah benar?


Atau effect + rule -> cause


Sebagai contoh:


Aturan : Tanah basah jika hari hujan.


Fakta : Tanah basah.


Konklusi : Hari hujan?


Jadi, diberikan fakta satu-satunya bahwa tanah basah, penyimpulan plausible menghasilkan konklusi hari hujan. Padahal, konklusi ini bisa salah, karena ada banyak hal yang menyebabkan tanah basah, misalnya seseorang siram-siram tanaman. Abduktip, sebagai salah satu metode penalaran, sering dipakai oleh dokter dalam mendiagnose pasien, maka diagnose dapat saja salah.



Analogi


Manusia membentuk model mental tentang konsep melalui pengalaman. Manusia menggunakan model ini melalui penalaran analogi untuk membantu memahami suatu masalah/situasi. Mereka lalu menarik analogi diantara masalah dan model, mencari kesamaan dan perbedaan untuk dapat menyimpulkan.


Sebagai contoh:


Misalkan seorang dokter yang sudah puluhan tahun praktek, maka pengalamannya dalam bentuk kasus-kasus sudah sedemikian banyaknya. Bila kasus-kasus tersebut dapat disimpan secara cerdik dalam database kasus, maka dapat dipergunakan untuk menyelesaikan masalah baru bagi pasien baru tanpa dokter itu hadir (otomasi). Pasien baru memasukan karakter berikut data-data (keluhan) dari sakitnya, kemudian sistem mencari kasus pasien lama yang serupa keluhannya untuk ditampilkan solusinya, yaitu obat beserta dosisnya. Pengalaman adalah guru terbaik, maka pengalaman perlu disimpan secara cerdik untuk memecahkan persoalan baru yang mirip!



Akal Sehat (Common-Sense)


Lewat pengalaman, manusia belajar memecahkan persoalan secara effisien. Mereka menggunakan akal sehat untuk dengan cepat menarik kesimpulan. Akal sehat lebih cenderung berdasar pada kebijakan-kebijakan (judgments) yang baik daripada logika yang eksak. Contoh akal sehat adalah: Di suatu bengkel ditemukan suara klik-klik-klik dalam mesin sepeda motor, seorang montir yang berpengalaman, tanpa membongkar mesinnya, langsung dapat menyimpulkan bahwa ring piston pada silinder mesin itu perlu diganti. Pengetahuan akal sehat ini diperoleh dari pengalamannya mengerjakan banyak sepeda motor selama bertahun-tahun. Jenis pengetahuan seperti ini disebut sebagai heuristik (heuristic) atau rule-of-thumb. Akal sehat tidak menjamin ditemukannya solusi, namun ia menjamin kecepatan menemukan solusi.



Penalaran Tidak Monoton (Non-Monotonic)


Penalaran pada suatu masalah pada umumnya menggunakan informasi yang statis, artinya selama melakukan penyelesaian masalah, keadaan (nilai benar atau salah) bermacam fakta dianggap tetap konstan. Penalaran semacam ini disebut sebagai penalaran monoton (monotonic reasoning). Dalam beberapa masalah, ditemukan bahwa keadaan beberapa fakta (variabel) bersifat dinamis, sebagai ilustrasi adalah aturan sbb.:



IF Angin berhembus


THEN Kursi goyang akan berayun


Kemudian coba amati kejadian berikut, lalu apa yang terjadi dengan aturan diatas:


Hei, ada angin topan! -> ada Angin berhembus -> Kursi berayun


Seiring berlalunya angin topan, kita berharap kursi berayun. Namun, saat angin topan telah berlalu, kita berharap bahwa kursi sudah berhenti berayun. Namun sistem yang menggunakan penalaran monoton akan tetap menganggap bahwa kursi tetap berayun!


Manusia dengan ke enam inderanya tidak merasa sulit untuk mengikuti perubahan status informasi variabel yang dinamis. Bila terjadi perubahan yang dinamis, mereka dengan mudah menyesuaikan diri. Gaya penalaran semacam ini disebut penalaran yang tidak monoton. Untuk bidang AI, seperti expert system, dibutuhkan suatu sistem untuk memelihara kebenaran yang dinamis bila ingin melakukan penalaran yang tidak monoton.


Referensi:

http://web.cecs.pdx.edu/~mperkows/CLASS_479/2017_ZZ_00/02__GOOD_Russel=Norvig=Artificial%20Intelligence%20A%20Modern%20Approach%20(3rd%20Edition).pdf

http://entin.lecturer.pens.ac.id/Kecerdasan%20Buatan/Buku/Bab%202%20Representasi%20Pengetahuan.pdf

Logika Orde Pertama (First-Order Logic)

Nama : Ananto Dwicahyo
NPM : 10115651
Kelas : 3KA10
Dosen : Essy Malays Sari Sakti

Logika orde pertama yang juga dikenal sebagai kalkulus predikat orde pertama dan predikat logika adalah kumpulan sistem formal yang digunakan dalam matematika, filsafat, linguistik, dan ilmu komputer. Logika orde pertama menggunakan variabel terukur daripada objek non-logis dan memungkinkan penggunaan kalimat yang mengandung variabel, sehingga daripada proposisi seperti Socrates adalah orang dapat memiliki ungkapan dalam bentuk "ada X sedemikian rupa sehingga X adalah Socrates dan X adalah seorang pria "dan ada ada quantifier sementara X adalah variabel.
Komponen-komponen penting yang ada pada first order logic yaitu :

Objects : merupakan sesuatu yang dikenai logika-logika yang memiliki identitas untuk masing-masing individual (komputer, rumah, mobil, ...).

a.       Properties : sifat yang dimiliki oleh objek dan merupakan pembeda dengan objek lainnya (merah, besar, lingkaran, ...).

b.      Relations : aksi atau aktifitas yang menjadi penghubung antar objek dalam berelasi (saudara dari, lebih tinggi dari, bagian dari).

c.       Functions : merupakan relation yang memiliki satu nilai (ayah dari, teman baik,...).
 Sintaks First Order Logic

Tata bahasa pada first order logic meliputi :

1. Terms
Merupakan ekspresi logika yang mengacu pada sebuah objek. Terms bisa berupa constant, variable, atau function.

2. Atomic sentences
Merupakan komponen yang dapat terbentuk dari Predicate(Term, ...) atau Term=Term. Atomic sentence merupakan kalimat paling sederhana dan belum memiliki komponen logika lainnya.
3. Complex sentences
Merupakan kalimat kompleks yang tersusun dari beberapa atomic sentence yang saling terhubung berdasarkan logika dengan menggunakan connective.

Semantik First Order Logic
Pada first order logic sama halnya dengan propositional logic sebuah kalimat first order logic dikatakan true terhadap sebuah model, artinya kalimat first order logic memiliki nilai kebenaran tertentu sehingga dianggap true atau false. Satu kalimat dalam first order logic dapat diinterpretasikan banyak cara dalam sebuah model. Model dalam first order logic terdiri dari :
1.Objects : elemen-elemen yang nyata ada pada permasalahan (domain elements)
2.Relations : hubungan antara elemen-elemen / objek-objek tertentu.

Quantifiers
Universal quantifiers Universal menyatakan logika yang digunakan untuk menunjuk sesuatu yang bersifat umum. Simbol
∀
 yang memiliki makna "untuk semua atau setiap" atau "for all" terhadap sebuah variabel x yang disimbolkan dengan∀x berarti bahwa kalimat tersebut  berlaku untuk setiap objek x. Contoh permasalahan pada first order logic yang menggunakan Universal Quantifiers adalah sebagai berikut : Misalkan ada kalimat "Ikhsan adalah anak kecil", kalimat ini akan dinyatakan sebagai AnakKecil(Ikhsan), dan ada kalimat "Andi suka permen" dinyatakan sebagai Suka(Andi,Permen). Jika kita ingin membuat kalimat "Untuk setiap objek x, jika x adalah anak kecil maka x suka  permen". Maka kalimat dapat kita tuliskan pada bentuk first order logic sebagai:∀x AnakKecil(x)⇒Suka(x,Permen) kalimat tersebut akan bernilai benar jika dan hanya  jika semua kalimat di bawah ini benar. AnakKecil(Budi)⇒Suka(Budi,Permen)∧AnakKecil(Rahmad)⇒Suka(Rahmad,Permen)∧
 AnakKecil(Anton)⇒Suka(Anton,Permen)∧

Existential menyatakan logika yang digunakan untuk menunjuk sesuatu yang bersifat khusus. Artinya hanya beberapa bagian atau sebagian saja dari keseluruhan himpunan.Logika ini merupakan kebalikan dari logika Universal. Logika ini disimbolkan dengan∃ yang memiliki makna "There Exist" atau (ada satu atau beberapa). Kita dapat menyatakan kalimat "Ada objek x, jika x adalah anak kecil maka x suka permen" menjadi first order logic sebagai berikut:∃
x AnakKecil(x)∧SukaPermen(x).

Equality merupakan pembandingan terhadap dua kalimat atau term yang memiliki nilai logika true atau false. Kedua kalimat dianggap sama jika memiliki nilai logika yang sama. Term1 =Term2 akan diinterpretasikan benar jika dan hanya jika memiliki nilai yang sama.

Mengubah Logika Order Pertama Menjadi Logika Proposisi
Representasi 4 kategori silogisme menggunakan logika predikat

 

Kaidah Universal Instatiation merupakan state dasar, dimana suatu individual dapat digantikan (disubsitusi) ke dalam sifat universal.

Contoh :
Misal, φ merupakan fungsi proposisi :
(∀ x) φ(x)
∴ φ(a)
merupakan bentuk yang valid, dimana a menunjukkan spesifik individual, sedangkan x adalah suatu variabel yang berada dalam jangkauan semua individu (universal)

Contoh lain : (∀ x) H(x)
∴ H(Socrates)
• Berikut ini adalah contoh pembuktian formal silogisme
All men are mortal
Socrates is a man
Therefore, Socrates is mortal
Misal : H = man, M = mortal, s = Socrates
1. (∀ x) (H (x) -> M(x))
2. H(s) / ∴ M(s)
3. H(s) -> M(s) 1 Universal Instatiation
4. M(s) 2,3 Modus Ponens

Rekayasa pengetahuan pada logika orde pertama

1.      Identify the task.

2.      Assemble the relevant knowledge.

3.      Decide on a vocabulary of predicates, functions, and constants.

4.      Encode general knowledge about the domain

5.      Encode a description of the specific problem instance.

6.      Pose queries to the inference procedure and get answers.

7.      Debug the knowledge base.

Unifikasi adalah usaha untuk mencoba membuat dua ekspresi menjadi identik (mempersatukan keduanya) dengan mencari substitusi-substitusi tertentu untuk mengikuti peubah-peubah dalam ekspresi mereka tersebut. Unifikasi merupakan suatu prosedur sistematik untuk memperoleh peubah-peubah instan dalam wffs. Ketika nilai kebenaran predikat adalah sebuah fungsi dari nilai-nilai yang diasumsikan dengan argumen mereka, keinstanan terkontrol dari nilai-nilai selanjutnya yang menyediakan cara memvalidasi nilai-nilai kebenaran pernyataan yang berisi predikat. Unifikasi merupakan dasar atas kebanyakan strategi inferensi dalam Kecerdasan Buatan. Sedangkan dasar dari unifikasi adalah substitusi.

Suatu substitusi (substitution) adalah suatu himpunan penetapan istilah-istilah kepada peubah, tanpa ada peubah yang ditetapkan lebih dari satu istilah. Sebagai pengetahuan jantung dari eksekusi Prolog, adalah mekanisme unifikasi.

Aturan-aturan unifikasi :

Dua atom (konstanta atau peubah) adalah identik.
Dua daftar identik, atau ekspresi dikonversi ke dalam satu buah daftar.
Sebuah konstanta dan satu peubah terikat dipersatukan, sehingga peubah menjadi terikat kepada konstanta.
Sebuah peubah tak terikat dipersatukan dengan sebuah peubah terikat.
Sebuah peubah terikat dipersatukan dengan sebuah konstanta jika pengikatan pada peubah terikat dengan konstanta tidak ada konflik.
Dua peubah tidak terikat disatukan. Jika peubah yang satu lainnya menjadi terikat dalam upa-urutan langkah unifikasi, yang lainnya juga menjadi terikat ke atom yang sama (peubah atau konstanta).
Dua peubah terikat disatukan jika keduanya terikat (mungkin melalui pengikatan tengah) ke atom yang sama (peubah atau konstanta).

Cara backward chaining
Pada backward chaining, kita memulai pengecekan dengan menggunakan pertanyaan tadi sebagai awal chain. Lalu dilakukan chaining dengan premis-premis lain hingga menghasilkan nilai null.

Cara proof by resolution

Proof by resolution menggunakan teknik kontradiksi, dimana kita menggunakan premis yang berlawanan nilainya untuk membuktikan sesuatu.
Untuk melakukan proof by resolution, semua premis harus dibuat menjadi clause normal form (CNF) terlebih dahulu. Dalam CNF, semua premis tidak boleh menggunakan kuantor,  implikasi (jika X maka Y) dan biimplikasi (X jika dan hanya jika Y). Lalu, jawaban dari pertanyaan dianggap salah dan dijadikan premis. Premis baru ini dijadikan awal dari pembuktian.

Referensi
Ebook Artifical Intelligence A Modern Approach(3rd Edition)
https://id.scribd.com/document/356627886/Bab-6-First-Order-Logic
http://www.binus.ac.id

Agen Logika

Nama : Ananto Dwicahyo
NPM : 10115651
Kelas : 3KA10
Dosen : Essy Malays Sari Sakti

PENGENALAN LOGICAL AGENT







Agen logika merupakan agen yang memiliki kemampuan bernalar secara logika. Ketika beberapa solusi tidak secara eksplisit diketahui, maka diperlukan suatu agen berbasis logika. Logika sebagai Bahasa Representasi Pengetahuan memiliki kemampuan untuk merepresentasikan fakta sedemikian sehingga dapat menarik kesimpulan (fakta baru, jawaban). Sedangkan pengetahuan merupakan komponen yang penting, sehingga terdapat perbedaan jika diterapkan pada dua agent, yakni problem solving agent dan knowledge-based agent.Agen Berbasis Pengetahuan atau Knowledge Base (KB) merupakan Himpunan representasi fakta yang diketahui tentang lingkungannya. Tiap fakta disebut sebagai sentence. Fakta tersebut dinyatakan dalam bahasa formal sehingga bisa diolah, menambahkan sentence baru ke KB. Inference Engine merupakan menentukan fakta baru yang dapat diturunkan dari pengetahuan yang sudah ada dalam KB. Agen Berbasis Pengetahuan dalam representasi, agent dapat dipandang dari knowledge level. Apa saja informasi yang diketahui? Misal sebuah robot “mengetahui” bahwa gedung B di antara gedung A dan gedung C. Agent dapat dipandang dari implementation level Bagaimana representasi informasi yang diketahuinya? Logical sentence di_antara(gdB, gdA, gdC). Natural language “Gedung B ada di antara gedung A dan gedung C”. Agen Berbasis Pengetahuan, pilihan representasi berpengaruh terhadap apa yang bisa dilakukan inference engine. Pada pendekatan deklaratif programmer memberitahu agent informasi tentang environment. Kalau informasi kurang, agen bisa melengkapinya sendiri. Jika dibandingkan dengan pendekatan prosedural programmer secara eksplisit memrogram agen untuk bertindak. Sehingga bagaimana jika program tidak benar, maka akan besar kemungkinan menyebabkan kesalahan.Agen Berbasis Pengetahuan, permasalahannya adalah bagaimana representasi yang tepat, sehingga ada dua hal yang harus diperhatikan expressive bisa menyatakan fakta tentang environment, Tractable bisa mengolah/ memproses inference engine (dengan cepat). Knowledge merupakan power atau kekuatan dari pemrograman secara deklaratif. Representasi dan penalaran membentuk suatu Intelligence.







1. KNOWLADGE BASE AGENT



Agen Berbasis Pengetahuan, Knowledge Base (KB) menyatakan apa yang “diketahui” oleh si agent Pendekatan deklaratif membangun agent: “beritahu” informasi yang relevan, simpan dalam KB. Agen dapat ditanya (atau bertanya diri sendiri) apa yang sebaiknya dilakukan berdasarkan KB. Maka sebuah agen berbasis pengetahuan harus bisa mereprentasikan world, state, action, dst. Menerima informasi baru (dan meng-update representasinya). Menyimpulkan pengetahuan lain yang tidak eksplisit (hidden property). q Menyimpulkan action apa yang perlu diambil.Agen Berbasis Pengetahuan atau Knowledge Base (KB) merupakan Himpunan representasi fakta yang diketahui tentang lingkungannya. Tiap fakta disebut sebagai sentence. Fakta tersebut dinyatakan dalam bahasa formal sehingga bisa diolah, menambahkan sentence baru ke KB. Inference Engine merupakan menentukan fakta baru yang dapat diturunkan dari pengetahuan yang sudah ada dalam KB.



2.WUMPUSWORLD



Aturan main Wumpus :

Performance measure: emas +1000, mati -1000, gerak -1, panah -10

Environment: Matriks 4×4 kamar. Initial state [1,1]. Ada gold, wumpus dan pit yang lokasinya dipilih secara acak.

Percept:

Breeze: kamar di samping lubang jebakan ada hembusan angin

Glitter: kamar di mana ada emas ada kilauan/sinar

Smell: kamar di samping Wumpus berbau busuk

Action: maju, belok kiri 90◦ , kanan 90◦ , tembak panah (hanya 1!), ambil benda

Sifat Wumpus :

(Fully) observable? Tidak, hanya bisa persepsi local

Deterministic? Ya, hasil tindakan jelas & pasti

Episodic? Tidak, tergantung action sequence

Static? Ya, gold, wumpus, pit tidak bergerak

Discrete? Ya

Single agent? Tidak

3.LOGIC IN GENERAL-MODELS AND ENTAILMENT



Logic adalah bahasa formal untuk merepresentasikan informasi sedemikian hingga kesimpulan dapat dibuat dalam pembuatan kesimpulan pasti harus menggunakan bahasa yg benar dalam pembuatan bahasa yang tepat Syntax mendefinisikan kalimat-kalimat pada bahasa kemudian Semantics mendefinisikan arti kalimat; misal, mendefinisikan kebenaran sebuah kalimat. Entailment berarti sesuatu fakta bisa disimpulkan dari (kumpulan) fakta lain Entailment dapat juga berarti sebuah hubungan antar kalimat ( syntax) yang didasarkan pada semantics kemudian Model adalah sebuah “dunia” di mana kebenaran suatu sentence bisa diuji.



Propositionan logic: Syntax



Propositional logic adalah logika paling sederhana menggambarkan ide dasar,symbol proposisi P1,P2 dll adalah sebuah kalimat.











Logika Propositional : Semantics



Tiap model menspesifikasikan true/false untuk setiap symbol proposisi.















Tabel Kebenaran untuk Inference











Logical equivalence



Dua kalimat adalah logically equivalent if bernilai true pada model yang sama: α ≡ ß iff α╞ β and β╞ α



Validity dan satisfiability



Sebuah kalimat adalah valid jika bernilai true pada semua model.

Validity dihubungkan ke inference melalui Deduction Theorem: KB ╞ α if and only if (KB  α) is valid

Sebuah kalimat adalah satisfiable jika bernilai true pada beberapa model.

Sebuah kalimat adalah unsatisfiable jika bernilai salah pada semua model.

Satisfiability dihubungkan ke inference melalui : KB ╞ α if and only if (KB α) is unsatisfiable



Resolution



Conjunctive Normal Form (CNF)

conjunction of disjunctions of literals

clauses





Resolution inference rule (for CNF):



Forward chaining



Diberikan suatu himpunan fakta dalam workingmemory, gunakan rules untuk membangkitkan fakta baru sampai goaldicapai.



•Langkah-langkah:



1)Cocokkan bagian IF dari setiap ruleterhadap fakta-fakta dalam working memory.



2)Jika ada lebih dari satu ruleyang dapat digunakan(lebih dari satu rule yang berjalan), pilih satu yang akan diaplikasikan dengan menggunakan resolusi konflik.



3)Berlakukan ruletersebut. Jika fakta baru diperoleh, tambahkan ke working memory.



4)Stop (atau exit) ketika kesimpulan ditambahkan ke working memory atau jika ada rule yang menetapkan proses berhenti.



Backward chaining



Mesin inferensi menjelajah secara mundur (backward) rantai inferesi (chain) dimulai dari tujuan (goal) dalam working memory.



•Terdiri dari 3 langkah utama:

1. Pilih rulesyang konklusi-nya sesuai dengan goal.

2. Ganti goal dengan premis dari ruleterpilih. Jadikan sebagai sub-goals.

3. Kerjakan backwardssampai semua sub-goalsbernilai true. Ini dicapai dengan:



–Ditemukannya fakta (dalam working memory) atau



–Pengguna menyediakan informasi tersebut.



Ide: bekerja backwards dari query q: membuktikan q dengan BC,

cek jika q sudah diketahui, atau

buktikan dengan BC semua premise pada beberapa rule concluding q

Avoid loops: chek jika subgoal baru sudah siap pada stack tujuan

Avoid repeated work: check if new subgoal telah terbukti benar, atau telah gagal



Logika Proposisi



Proposisi

Logika adalah metode atau teknik yang diciptakan untukmeneliti ketepatan penalaran

serta mengkaji prinsip-prinsip penalaran yang benar dan penarikan kesimpulanyang

absah.Ilmu logika berhubungan dengan kalimat-kalimat(argumen) dan hubungan yang

ada diantara kalimat-kalimat tersebut.



Referensi :

http://share.its.ac.id/pluginfile.php/1369/mod_resource/content/1/8._Propotional_Logic.pdf

Pencarian Berbentuk /heuristik search dan Eksplorasi

Nama : Ananto Dwicahyo
NPM : 10115651
Kelas : 3KA10

1.1 Pencarian
Pencarian merupakan kegiatan mendefinisikan ruang masalah untuk
masalah yang dihadapi. Ruang masalah ini dapat digambarkan sebagai himpunan
keadaan (state) atau bisa juga sebagai himpunan rute dari keadaan awal (initial
state) menuju keadaan tujuan (goal state). Langkah kedua adalah mendefinisikan
aturan 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 yang minimal.
Metode-metode pencarian pada teknik searching diantaranya[8] :
1. Pencarian tidak berbekal informasi / buta (Blind/Un-informed Search)
a. Breadth-First Search (BFS)
b. Depth-First Search (DFS)
c. Depth-Limited Search (DLS)
d. Uniform Cost Search (USC)
e. Iterative-Deepening Search (IDS)
f. Bi-Directional Search (BDS)

2. Pencarian berbekal informasi (Heuristik)
a. Generate-and-Test
b. Hill Climbing
c. Simulated Annealing
d. Best-First Search (BFS)
e. Greedy Best-First Search
f. A* (A star)

1.2 Metode Pencarian Heuristic
Kata Heuristic berasal dari sebuah kata kerja Yunani, heuriskein, yang
berarti „mencari‟ atau „menemukan‟. Dalam dunia pemrograman, sebagian orang
menggunakan kata heuristic sebagai lawan kata dari algoritmik, di mana kata
heuristic ini diartikan sebagai suatu proses yang mungkin dapat menyelesaikan  suatu masalah tetapi tidak ada jaminan bahwa solusi yang dicari selalu dapat
ditemukan. Heuristic memperbaiki proses pencarian solusi walaupun tidak harus
sampai mengatasi kasus terburuk (worst case scenario). Heuristik ini
mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan
mengorbankan kelengkapan (completeness). Algoritma ini biasanya mencari
solusi yang dekat dengan solusi terbaik dan proses pencariannya cepat dan mudah.
Terkadang algoritma ini dapat menjadi akurat dan menemukan solusi terbaik,
tetapi algoritma ini tetap disebut heuristic hingga solusi terbaik itu terbukti untuk
menjadi yang terbaik. Fungsi heuristic h(n) adalah perkiraan biaya termurah dari
node n ke node tujuan. Fungsi heuristic melambangkan cost yang akan
dikeluarkan agent jika memilih node tertentu.

1.3 Metode A* Heuristic
Metode A* dikembangkan oleh Peter Hart, Nils Nilsson, dan Bertram
Raphael, mereka juga menyebut metode tersebut dengan sebutan algoritma A,
dengan menggunakan metode ini dan dengan heuristic yang tepat menghasilkan
sebuah hasil yang optimal, yaitu A*. Secara umum, depth-first search (DFS) dan
breadth-first search (BFS) adalah dua kasus spesial dari metode A*. Algoritma
Djikstra‟s merupakan kasus yang paling special dari A*, di mana h(x) = 0 untuk
semua x [8].
Metode A* tanpa fungsi heuristic yang baik akan memperlambat pencarian
dan dapat menghasilkan rute yang tidak tepat. Fungsi heuristic yang sempurna
akan membuat metode A* langsung menuju final node tanpa harus mencari
kearah lain. Sehingga jika fungsi heuristicnya terlalu underestimate akan
menyebabkan algoritma ini beranggapan bahwa ada rute lain yang lebih baik.
Untuk fungsi heuristic yang underestimate, bila nilainya terlalu rendah akan
menyebabkan algoritma ini seperti algortima Djikstra’s yang mencari ke segala
arah yang mungkin. Hal ini dikarenakan tidak ada informasi yang cukup
mengenai masalah yang dihadapi, sehingga menyebabkan metode A* melakukan
pencarian lebih banyak dan lebih lama.

Berdasarkan ilmu komputer, A* (disebut “A star”) adalah sebuah graph
atau metode tree search yang digunakan untuk mencari jalan dari sebuah node
awal ke node tujuan (goal node) yang telah ditentukan, metode ini menggunakan
“estimasi heuristic” h(x) pada setiap node untuk mengurutkan setiap node x
berdasarkan estimasi rute terbaik yang melalu node tersebut. Dalam prosesnya
metode ini akan mengunjungi setiap node berdasarkan urutan yang dihasilkan dari
estimasi heuristic ini. Metode A* adalah salah satu contoh dari metode best-first
search.
Masalah pencarian rute di mana metode A* sering digunakan, A* secara
bertahap membangun semua rute yang mengarah mulai dari titik awal sampai
akhirnya mencapai titik akhir. Metode A* hanya membangun rute yang mungkin
digunakan untuk mencapai tujuan. Untuk mengetahui rute mana yang
memungkinkan mengarah ke titik akhir, A* menggunakan estimasi heuristic jarak
dari sembarang node ke node tujuan. Dalam kasus pencarian rute, ini bisa jadi
sama dengan jarak lurus antara dua titik, di mana biasanya merupakan perkiraan
dari jarak jalan.

Hubungan antara heuristic dengan algoritma A* [8]:
1. Apabila h(n) selalu bernilai 0, maka hanya g(n) yang akan berperan, dan
A* berubah menjadi Algoritma Dijkstra, yang menjamin selalu akan
menemukan jalur terpendek.
2. Apabila h(n) selalu lebih rendah atau sama dengan ongkos perpindahan
dari titik n ke tujuan, maka A* dijamin akan selalu menemukan jalur
terpendek. Semakin rendah nilai h(n), semakin banyak titik-titik yang
diperiksa A*, membuatnya semakin lambat.
3. Apabila h(n) tepat sama dengan ongkos perpindahan dari n ke tujuan,
maka A* hanya akan mengikuti jalur terbaik dan tidak pernah memeriksa
satupun titik lainnya, membuatnya sangat cepat. Walaupun hal ini belum
tentu bisa diaplikasikan ke semua kasus, ada beberapa kasus khusus yang
dapat menggunakannya.
4. Apabila h(n) kadangkala lebih besar dari ongkos perpindahan dari n ke
tujuan, maka A* tidak menjamin ditemukannya jalur terpendek, tapi
prosesnya cepat.
5. Apabila h(n) secara relatif jauh lebih besar dari g(n), maka hanya h(n)
yang memainkan peran, dan A* berubah menjadi BFS.

1.4 Aplikasi Metode A* Heuristic
Metode A* biasanya diaplikasikan dalam kasus pathfinding. Terdapat
beberapa hal yang perlu didefinisikan terlebih dahulu dalam kasus pathfinding
dengan penerapan algoritma A*. Adapun istilah-istilah yang akan dibahas yaitu
path, open list, closed list, nilai f, g dan n.
Algoritma ini menggunakan dua senarai yaitu open dan closed. open
adalah senarai (list) yang digunakan untuk menyimpan simpul-simpul yang
pernah dibangkitkan dan nilai heuristiknya telah dihitung tetapi belum terpilih
sebagai simpul terbaik (best node) dengan kata lain, open berisi simpul-simpul
masih memiliki peluang untuk terpilih sebagai simpul terbaik, sedangkan closed
adalah senarai untuk menyimpan simpul-simpul yang sudah pernah dibangkitkan
dan sudah pernah terpilih sebagai simpul terbaik. Artinya, closed berisi simpulsimpul
yang tidak mungkin terpilih sebagai simpul terbaik (peluang untuk terpilih
sudah tertutup).
1. Open list adalah list yang menyimpan kemungkinan path yang akan
diperiksa. Open list dibuat terurut berdasarkan nilai f. Open list digunakan
untuk menentukan secara selektif (berdasarkan nilai f) jalan yang dikira
lebih dekat menuju pada path tujuan. Open berisi simpul-simpul yang
masih memiliki peluang untuk terpilih sebagai simpul terbaik (best node).
2. Closed adalah senarai (list) untuk menyimpan simpul-simpul yang sudah
pernah dibangkitkan dan sudah pernah terpilih sebagai simpul terbaik (best
node) atau senarai yang menyimpan jalan yang sudah diperiksa dari open
list. Artinya, closed berisi simpul-simpul yang tidak mungkin terpilih
sebagai simpul terbaik (peluang untuk terpilih sudah tertutup). Kedua list
(open list dan closed list) ini bertujuan juga untuk menghindari
penelusuran jalan (rute) berulangkali yang memang sudah diidentifikasi
agar tidak masuk kembali ke dalam open list.
3. Nilai F adalah cost perkiraan suatu path yang teridentifikasi. Nilai F
merupakan hasil dari f(n).
4. Nilai G hasil dari fungsi g(n), adalah banyaknya langkah yang diperlukan
untuk menuju ke path sekarang.
5. Nilai N untuk setiap simpul (node) harus memiliki informasi nilai h(n),
yaitu estimasi harga simpul tersebut dihitung dari simpul tujuan yang
hasilnya menjadi nilai H.
Fungsi f sebagai estimasi fungsi evaluasi terhadap node n, dapat dituliskan
[8] :
f(n) = g(n) + h(n)….[2.1]
dengan :
f(n) = fungsi evaluasi ( jumlah g(n) dengan h(n) )
g(n) = biaya (cost) yang dikeluarkan dari keadaan awal sampai keadaan n
h(n) = estimasi biaya untuk sampai pada suatu tujuan mulai dari n
Pergerakan diagonal diperbolehkan, maka digunakan fungsi heuristic
Non-Manhattan Distance. Maka fungsi heuristic yang digunakan adalah sebagai
berikut :
h_diagonal(n) = – (abs(n.x-goal.x) + abs(n.y-goal.y))….[2.2]
h_orthogonal(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))….[2.3]
h(n) = h_diagonal(n) + (h_orthogonal (n) – (2 * h_diagonal(n)))….[2.4]
dengan :
x = representasi titik absis
y = representasi titik ordinat
2.3.3.4 Metode Simplified Memory-Bounded A* (SMA*)
Simplified Memory-Bounded A* (SMA*) merupakan pengembangan dari
algoritma A*. Algoritma SMA* merupakan penggabungan dari greedy search
yang meminimalisir perkiraan pencarian harga dan uniform cost search yang
meminimalisir harga sampai selesai [8].

Algoritma SMA* bersifat admissible. Ini berarti apabila solusi ada, solusi
yang ditemukan pertama adalah solusi yang optimal. SMA* bersifat admissible
bila memenuhi syarat-syarat, yaitu: di dalam graph state space setiap node
memiliki successor yang terbatas, setiap arc pada graph memiliki biaya yang
lebih besar dari 0, dan heuristic untuk setiap node n, h(n) < h*(n). SMA *
dikatakan complete dan optimal dengan mengasumsikan sebuah heuristic yang
admissible dan konsisten.
Simplified Memory-Bounded A* ini dikembangkan karena algoritma A*
menggunakan banyak memory sehingga menghabiskan memory untuk pencarian.
Algoritma ini menjalankan best first search selama memory masih tersedia,
apabila memory penuh maka node dengan nilai terburuk dibuang, namun nilai
terbaik disimpan pada node atasnya. Jika ruang memory mencukupi untuk semua
node pada tree dalam jalur pencarian, maka repeated states tidak akan diulang
sehingga pencarian akan menjadi optimal.
Aturan-aturan SMA* [8]:
1. Jika mempunyai lebih dari satu simpul, maka pilih salah satu yang
mempunyai f-cost terkecil. Jangan hapus dulu simpul tersebut sebelum
mengeceknya terlebih dahulu, karena bisa jadi simpul tersebut akan
dipakai dulu oleh simpul yang lain.
2. Jika hasil f-cost dari suksesor baru yang telah dibangkitkan hasilnya lebih
kecil, maka suksesor-suksesor sebelumnya dihapus. Tetapi jika lebih
besar, maka lanjutkan dulu pencarian ke suksesor yang lebih kecil,
sebelum menghapus suksesor yang lebih besar tersebut.
3. Jika menemukan state di level yang lebih dangkal, dan mmpunyai f-cost
lebih besar, maka state tersebut juga harus dihapus.

REFERENSI : http://elib.unikom.ac.id/files/disk1/623/jbptunikompp-gdl-aerajatras-31102-10-13.unik-2.pdf