Penerapan Algoritma Minimax Pada permainan TIC-TAC-TOE

Latar Belakang

Perkembangan teknologi dalam dunia komputer semakin hari semakin lebih maju, komputer yang dulunya berfungsi sebagai alat hitung dan pengolah data, seiring perkembangan teknologi modern komputer saat ini tidak hanya bertindak sebagai mesin yang hanya disuruh namun mampu berfikir memberikan respon bagi pengguna. Kecerdasan buatan dimanfaatkan dalam pembuatan game salah satunya adalah TIC-TAC-TOE, alasannya adalah sebagai berikut :

a. Cukup mudah untuk menentukan ukuran kemenangan atau kegagalan.

b.Memungkinkan untuk dibandingkan dengan kemampuan manusia.

c.Pola peraturan permainan TIC-TAC-TOE cukup dikenal dan mudah untuk dimainkan

Permainan TIC-TAC-TOE

Permainan tic-tac-toe merupakan permainan berjenis board-game berukuran 3x3 ataupun lebih. Pemain harus mengisi sel-sel, sehingga karakter yang dimasukan pemain tersebut dapat membentuk suatu garis lurus horizontal, vertikal, atau diagonal. Biasanya karakter tersebut berupa tanda “X” dan “O” untuk membedakan antar pemain. Permainan ini biasanya dimainkan ileh 2 orang, tetapi pada versi permainan komputer, pemain lawan dapat digantikan oleh komputer. Hasil permaian dapat menang, kalah, atau seri.

Algoritma Minimax

Algoritma minimax merupakan basis dari semua permainan berbasis AI. Pada algoritma minimax, pengecekan akan seluruh kemungkinan yang ada sampai akhir permainan dilakukan. Pengecekan tersebut akan menghasilkan pohon permainan yang berisi semua kemungkinan tersebut. Tentunya dibutuhkan resource yang berskala besar untuk menangani komputasi pencarian pohon solusi tersebut berhubung kombinasi kemungkinan sangat banyak sekali. Pada langkah pertama komputer akan menganalisi seluruh pohon permainan, dan setiap langkahnya komputer akan memilih langkah yang akan membuat lawan mendapatkan keuntungan minimum dan komputer itu sendiri mendapatkan keuntungan maksimum. Pada permainan tic-tac-toe ini digunakan nilai 1,0,-1 untuk mewakili hasil akhir permainan yaitu menang, seri, kalah. Dari nilai-nilai heuristic inilah komputer akan menentukan simpul mana dari pohon permainan yang akan dipilih. Garis besar algoritma minimax secara umum:

“If ada langkah kemenangan Then pilih langkah tersebut

Else if lawan mempunyai 2 spot terisi dalam satu garis dengan spot ketiga masih kosong Then tutup langkah tersebut.

Else melangkah ke state yang mempunyai kemungkinan menang tertinggi”.

Analisis

Pada permainan tic-tac-toe menggunakan algoritma minimax, dimana AI akan menelusuri semua kemungkinan langkah yang akan dilakukan oleh pemain. Sehingga AI akan selalu mengetahui kemungkinan pemain untuk menang dan memblok semua langkah kemenangan pemain. Dengan demikian permainan akan selalu seri apabila pemain cukup teliti dalam menentukan langkah. Namun apabila pemain melakukan langkah yang salah, maka AI akan langsung mengambil langkah yang mengarahkannya ke hasil akhir berupa kemenangan atau seri.   

Berikut adalah contoh permainannya :

Saya memilih karakter"X", dan mendapat giliran pertama. Disini saya akan mengumpamakan "a" itu baris dan "b" itu kolom, jadi (a(baris),b(kolom)). Pertama saya memilih (a2,b2) dan komputer memilih (a2,b1).

Pada giliran berikutnya saya memilih (a1,b2) dan komputer memilih (a3,b2). komputer memilih (a3,b2) dikarenakan komputer mengetahui bahwa langkah kemenangan saya ada di (a3,b2).

Berikutnya saya memilih (a1,b1) dan disini saya memiliki 2 langkah kemenangan yaitu di (a1,b3) dan (a3,b3). komputer memilih (a3,b3) dan berarti langkah kemenangan saya ada di (a1,b3).

Karena disini saya memilih level kesulitan medium, maka tingkat ketelitian komputer masih rendah. Namun semakin tinggi level kesulitan yang kita mainkan makin sulit pula untuk kita memenangkan game ini.

Kesimpulan : 

- Penerapan algoritma minimax cukup bagus dan cocok untuk pengambilan keputusan oleh AI, terutama dalam permainan non-player.

- Algoritma minimax menggunakan konsep Dept First Search dalam pembentukan pohon solusi.

-  Pohon solusi dibentuk dari awal permainan sampai akhir permainan.

- Dengan menggnakan algoritma minimax untuk AI dalam permainan tic-tac-toe sangat kecil kemungkinan pemain untuk dapat menang  melawan AI tersebut.

Sumber :

- Khoirus Sholih, 2010.Jurnal Implementasi Teori Minimax pada Tic Tac Toe.Teknik Informatika. Institut Teknologi Bandung.

- http://elib.unikom.ac.id/files/disk1/317/jbptunikompp-gdl-dickyherma-15803-6-jurnal.pdf

https://www.academia.edu/9991470/PAPER_IMPLEMENTASI_ALGORITMA_MINIMAX_PADA_PERMAINAN_TIC_TAC_TOE_5X5

Read More

Representasi Pengetahuan : Logika Predikat(M8)

Logika Predikat
Logika Predikat adalah perluasan dari logika proposisi dimana objek yang dibicarakan dapat berupa anggota kelompok. z logika proposisi (ingat kembali) menganggap proposisi sederhana (kalimat) sebagai entitas tunggal Sebaliknya, logika predikat membedakan subjek dan predikat dalam sebuah kalimat.

Penerapan Logika Predikat merupakan notasi formal untuk menuliskan secara sempurna definisi, aksioma,  teorema matematika dengan jelas, tepat dan tidak ambigu pada semua cabang matematika. Logika predikat dengan simbol-simbol fungsi, operator “=”, dan beberapa aturan pembuktian cukup untuk mendefinisikan sistem matematika apapun, dan juga cukup untuk membuktikan apapun yang dapat dibuktikan pada sistem tersebut.

Subjek dan Predikat

Pada kalimat “Kucing itu sedang tidur”:

frase “kucing itu” merupakan subjek kalimat frase “sedang tidur” merupakan predikat kalimat- suatu properti yang bernilai TRUE untuk si subjek (objek pelaku) dalam logika predikat, predikat dimodelkan sebagai sebuah fungsi P(·) dari objek ke proposisi. P(x) = “x sedang tidur” (x adalah sembarang objek). Predikat Konvensi: varibel huruf kecil x, y, z... Menyatakan objek/entitas; variabel huruf besar P, Q, R… menyatakan fungsi proposisi (predikat). Perhatikan bahwa hasil dari menerapkan sebuah predikat P kepada objek x adalah sebuah proposisi P(x). Tapi predikat P sendiri (e.g. P=“sedang tidur”) bukan sebuah proposisi

Ekspresi Quantifier

z Quantifiers merupakan notasi yang memungkinkan kita untuk mengkuantifikasi (menghitung) seberapa banyak objek di semesta pembicaraan yang memenuhi suatu predikat.

z “∀” berarti FOR∀LL (semua) atau universal quantifier.

∀x P(x) berarti untuk semua x di semesta pembicaraan, P berlaku.

z “∃” berarti ∃XISTS (terdapat) atau existential quantifier. ∃x P(x) berarti terdapat x di semesta pembicaraan. (bias 1 atau lebih) dimana P(x) berlaku.

Predikat & Kuantifier Pernyataan “x > 3” punya 2 bagian, yakni “x” sebagai subjek dan “ adalah lebih besar 3” sebagai predikat P. Kita dpt simbolkan pernyataan “x > 3” dengan P(x).  Sehingga kita dapat mengevaluasi nilai kebenaran dari P(4) dan P(1). Subyek dari suatu pernyataan dapat berjumlah lebih dari satu.

Misalkan Q(x,y): x - 2y > x + y

Resolusi pada logika predikat pada dasarnya sama dengan reolusi pada logika proporsi, hanya saja ditambah dengan unufikasi. Pada logika predikat, prosedur untuk membuktikan pernyataan P dengan beberapa penyataan F yang telah diketahui dengan menggunakan resolusi, dapat dilakukan melalui algoritma sebaga berikut.

1.konversi semua proporsi F ke bentuk klausa

2.negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa. Tambahkan ke himpunan klausa yang telah ada pada langkah 1.

3.kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan.

a.seleksi 2 klausa sebagai klausa parent.

b.bandingkan secara bersama-sama. Klause hasil resolve tersebut dinamakan resolvent. Jika ada pasangan literal T1 dan T2 disebut sebagai complementary literal. Jika ada lebih dari 1 complementary literal, maka hanya sepasang yang dapat meninggalkan resolvent.

c.jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan kalusa yang telah ada.

Contoh :

Misalkan terdapat pernyataan-pernyataan sebagai berikut :

1. Andi adalah seorang mahasiswa.

2. Andi masuk jurusan elektro

3. Setiap mahasiswa elektro pasti mahasiswa teknik.

4. Kalkulus adalah matakuliah yang sulit.

5.Setiap mahasiswa teknik pasti akan suka kalkulus atau akan membencinya.

6. Setiap mahasiswa pasti akan suka terhadap suatu mata kuliah.

7. Mahasiswa yang tidak pernah hadir pada matakuliah sulit, maka mereka pasti akan tidak suka pada matakuliah tersebut

8. Andi tidak pernah hadir kuliah matakuliah kalkulus.

Kedelapan pernyataan diatas dapat dibawa ke bentuk logika predikat, dengan menggunakan operator-operator logika predikat, sebagai berikut:

•          Mahasiswa(Andi).
•          ∀ x:Elektro(x)->Teknik(x).
•         Sulit(Kalkulus).
•         x:Teknik(x)->suka(x,Kalkulus) V benci,(x,Kalkulus).
•         ∀x:y:suka(x,y).
•         ∀x:∀y:mahasiswa(x)sulit(y) Ʌ¬hadir(x,y)->¬suka(x,y).
•         ¬ hadir(Andi,Kalkulus).

Kita dapat membawa pernyataan-pernyataan yang ada menjadi bentuk klausa (CNF) sebagai berikut :

•          Mahasiswa(Andi).
•         Elektro(Andi).
•        ¬Elektro(x1) V Teknik(x1).
•        Sulit(Kalkulus).
•        ¬Teknik(x2) V suka(x2,Kalkulus) V benci(x2,Kalkulus).
•        Suka(x3,fl(x3).
•        ¬Mahasiswa(x4) V ¬sulit(y1) v hadir(x4,y1) V ¬suka(x4,y1).
•        ¬Hadir(Andi,Kalkulus).

      Sumber :

      

  - http://sandimcs.blogspot.co.id/2014/05/logika-predikat.html

  - http://pakarbelajar.blogspot.co.id/2009/08/5-fungsi-predikat-dan-kalimat.html

 -http://queenfreak992.blogspot.co.id/2015/06/representasi-pengetahuan_25.html

Read More

Representasi Pengetahuan : Logika Proposisi (M7)

Logika dan Set

 Representasi pengetahuan dengan symbol logika merupakan bagian dari penalaran eksak.Bagian yang paling penting dalam penalaran adalah mengambil kesimpulan dari premis. Logika dikembangkan oleh filusuf Yunani, Aristoteles (abad ke 4 SM) didasarkan pada silogisme, dengan dua premis dan satu konklusi.

Contoh :

Premis   : Semua laki-laki adalah makhluk hidup

Premis   : Socrates adalah laki-laki

Konklusi : Socrates adalah makhluk hidup

Operator Logika

Proposisi (pernyataan) : suatu kalimat deklaratif yang bernilai benar saja atau salah saja, tetapi tidak sekaligus benar dan salah. Dilambangkan dengan huruf kecil p, q, r,… dan disebut sebagai proposisi atomik.

Dua atau lebih proposisi dapat digabung menggunakan operator logika sebagai berikut :

Konjungsi : Ù (and)

Disjungsi : Ú (or)

Negasi : Ø (not)

Implikasi : à (if-then)

Ekuivalensi : Û (jika dan hanya jika)

Untuk setiap : "

Terdapat    : $

Tautologi

selalu benar untuk semua kemungkinan nilai kebenaran dari pernyataan-pernyataan komponennya. Sebuah Tautologi yang memuat pernyataan Implikasi disebut Implikasi Logis. Untuk membuktikan apakah suatu pernyataan Tautologi, maka ada dua cara yang digunakan. Cara pertama dengan menggunakan tabel kebenaran, yaitu jika semua pilihan bernilai B (benar) maka disebut Tautologi, dan cara kedua yaitu dengan melakukan penjabaran atau penurunan dengan menerapkan sebagian dari 12 hukum-hukum Ekuivalensi Logika.

Kontradiksi

 Untuk membuktikan apakah suatu pernyataan tersebut kontradiksi, maka ada dua cara yang digunakan. Cara pertama dengan menggunakan tabel kebenaran, yaitu jika semua pilihan bernilai F atau salah maka disebut kontradiksi, dan cara kedua yaitu dengan melakukan penjabaran atau penurunan dengan menerapkan sebagian dari 12 hukum-hukum Ekuivalensi Logika.

Contingent

Pernyataan yang bukan Tautologi maupun Kontradiksi

Resolusi Logika Preposisi 

Suatu aturan untuk melakukan inferensi yang dapat berjalan secara efisien dalam suatu bentuk khusus, conjunctive normal form (CNF). Logika yang menangani atau memproses penarikan kesimpulan secara logis dari proposisi-proposisi.







Sumber :

- http://s3.amazonaws.com/ppt-download/ai-3-130109012017-phpapp01.pptx?response-content-disposition=attachment&Signature=KauHRvx2OFCXqzsTR6MjjJC%2FrCQ%3D&Expires=1479007396&AWSAccessKeyId=AKIAJ6D6SEMXSASXHDAQ

- https://rakata89.files.wordpress.com/2012/04/ai_5.pptx

Read More

Representasi Pengetahuan(M6)

Representasi Pengetahuan

Representasi pengetahuan adalah suatu teknik untuk merepresentasikan basis pengetahuan yang diperoleh ke dalam suatu skema/diagram tertentu sehingga dapat diketahui relasi/keterhubungan antara suatu data dengan data yang lain sehingga dapat diuji kebenaran penalarannya. Representasi pengetahuan biasanya digunakan untuk pembuatan sistem pakar di mana computer dirancang untuk dapat mengambil keputusan seperti manusia agar dapat menyelesaikan masalah.

Contoh fakta sederhana yang direpresentasikan secara logika :

Persia adalah kucing

Fakta direpresentasikan secara logika yaitu:

Kucing(Persia)

Kita juga merepresentasikan secara logika bahwa semua kucing berekor

Kucing(a)->berekor(a)

Dari penalaran logika, kita mendapatkan representasi baru:

Berekor(kucing)

Dengan menggunakan fungsi mapping secara backward,kita dapat men-generate yaitu:

Persia berekor.

Sistem produksi memiliki struktur seperti proses pencarian (search). Secara umum, sistem produksi terdiri dari komponen-komponen :
1. Ruang Keadaan
2. Memori Aktif
3. Strategi Kontrol

Ruang Keadaan berisi keadaan awal, tujuan dan kumpulan aturan yang digunakan untuk mencapai tujuan.

Memori Aktif berisi deskripsi keadaan semesta pembicaraan saat ini dalam proses penalaran.

Strategi Kontrol berguna untuk mengarahkan bagaimana proses pencarian akan berlangsung dan mengendalikan arah eksplorasi.

Jaringan Semantik merupakan gambaran pengetahuan grafis yang menunjukan hubungan antar berbagai objek menunjukan sejumlah lingkaran yang menggambarkan objek dan informasi deskriptif tentang objek-objek. Objek tersebut bisa merupakan objek fisik. Sedangkan node bisa merupakan pikiran, kejadian atau tindakan.

Triple Obyek-Atribut-Nilai

Ada 3 hal yaitu  Objek, Atribute, Value , triplet yang sering digunakan untuk membangun jaringan semantik.

Object   : dapat berupa fisik / konsepsi
Atribute : karakteristik objek
Value    : ukuran spesifik dari atribut dalam situasi tertentu

Contoh :

Triplet OAV secara khusus digunakan untuk mempresentasikan fakta dan pola guna menyesuaikan fakta dalam aturan yang antecendent. jaringan semantik untuk beberapa sistem terdiri dari node untuk objek atribute dan nilai yang dihubungkan dengan IS A dan HAS A.

Frame

frame berupa kumpulan slot-slot yang merupakan atribut untuk mendeskripsikan pengetahuan berupa kejadian, lokasi, situasi ataupun elemen lain.

Contoh : 

Frame Pohon

Spesialisasi dari : Tumbuhan

Jumlah batang   : integer (default 1)

Jenis kulit          : halus

Model daun        : jenis pohon jarum, berganti daun

Bentuk daun       : sederhana, berlekuk, campuran

Frame Pohon Perdu

Spesialisasi dari  : Pohon

Jumlah batang     : 3

Jenis kulit           : halus

Model daun         : berganti daun

Bentuk daun       : sederhana, berlekuk

Script

Script menggambarkan urutan peristiwa, dalam menggambarkan urutan perisitiwa script menggunakan serangkaian slot yang berisi informasi tentang orang, objek dan tindakan-tindakan yang terjadi.

Sumber :

http://lecturer.ukdw.ac.id/anton/download/AI/Representasi%20Pengetahuan.ppt

https://serdiwansyahna.files.wordpress.com/2011/12/ai_6.pptx

http://bs-unity.blogspot.co.id/2010/10/jaringan-semantik-script-pada-ai.html

http://www.slideshare.net/bungpoetra/representasi-pengetahuan-11140673

Read More

Metode Pencarian dan Pelacakan 2 (Heuristik)(M5)

Heuristic search merupakan metode pencarian yang memperhatikan nilai heuristic (nilai perkiraan). Teknik pencarian heuristic merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang bodoh dan memboroskan waktu. Heuristic adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan.

Best First Search

Best first search merupakan kombinasi dari algoritma depth first search dengan algoritma breadth first search dengan mengambil kelebihan dari kedua algoritma tersebut. Apabila pada pencarian dengan algoritma hill climbing tidak diperbolehkan untuk kembali ke node pada level pada yang lebih rendah meskipun memiliki nilai heuristic yang lebih baik, lain halnya pada algoritma best first search pencarian diperbolehkan mengunjungi node yang ada dilevel lebih rendah, jika ternyata node di level yang lebih tinggi memiliki nilai heuristic yang buruk. 

Problem Reduction 

Problem reduction adalah dasar teknik pemecahan masalah AI dimana dilakukan dengan cara mengurangi masalah dalam satu set sub masalah yang lebih mudah pemecahannya. Intinya adalah berusaha mengurangi masalah dengan harapan masalah yang bersangkutan menjadi lebih mudah diselesaikan. Ide utama teknik problem reduction adalah mendekomposisi masalah ke dalam skala yang lebih kecil.

Problem Reduction dibagi dalam dua metode yaitu:

1. Graf AND OR

Graf AND OR atau tree merupakan graf yang digunakan untuk memperlihatkan solusi dari permasalahan yang dapat diselesaikan dengan cara mendekomposisikan masalah tersebut menjadi sekumpulan masalah yang lebih kecil, dimana semuanya harus dapat diselesaikan. Pereduksian ini membangkitkan arc(busur) AND. Satu busur AND akan menghasilkan beberapa nomor dari simpul setelahnya dimana semua simpul harus diselesaikan supaya pancaran menghasilkan solusi. Hanya saja pada graf OR banyak pancaran akan muncul dari beberapa node, mengindikasikan beberapa jalan yang dapat menyelesaikan masalah.
                         

                         

2. Graf AO*(Algorithm Optimized)

 Algoritma AO* menggunakan struktur Graph dimana tiap-tiap node pada graph tersebut akan memiliki nilai h’ yang merupakan biaya estimasi jalur dari node itu sendiri sampai suatu solusi.
               

constraint satisfaction adalah proses menemukan solusi untuk satu set kendala yang memaksakan kondisi bahwa variabel harus memuaskan. Solusi Oleh karena itu vektor dari variabel yang memenuhi semua kendala.

Teknik yang digunakan dalam constraint satisfaction tergantung pada jenis kendala yang dipertimbangkan. Sering digunakan adalah kendala pada domain yang terbatas, ke titik yang kendala masalah kepuasan biasanya diidentifikasi dengan masalah berdasarkan kendala pada domain yang terbatas.
Masalah seperti ini biasanya dipecahkan melalui pencarian, khususnya bentuk kemunduran atau pencarian lokal. Kendala propagasi metode lain digunakanpada masalah tersebut, kebanyakan dari mereka tidak lengkap pada umumnya, yaitu, mereka dapat memecahkan masalah atau membuktikannya unsatisfiable, tetapi tidak selalu. Kendala metode propagasi juga digunakan dalam hubungannya dengan pencarian untuk membuat soal yang diberikan sederhana untuk memecahkan.
Jenis lain dianggap kendala berada pada bilangan real atau rasional; pemecahan masalah pada kendala-kendala dilakukan melalui eliminasi variabel atau algoritma simpleks

permasalahan pada Constraint satisfaction
Sebagai awalnya didefinisikan dalam kecerdasan buatan, kendala menghitung nilai yang mungkin satu set variabel dapat mengambil. Informal, domain terbatas adalah himpunan berhingga elemen sewenang-wenang. Sebuah kepuasan kendala masalah pada domain seperti berisi satu set variabel yang nilainya hanya dapat diambil dari domain, dan satu set kendala, kendala masing-masing menetapkan nilai diperbolehkan untuk sekelompok variabel. Sebuah solusi untuk masalah ini adalah evaluasi dari variabel-variabel yang memenuhi semua kendala. Dengan kata lain, solusi adalah cara untuk menetapkan nilai untuk setiap variabel sedemikian rupa sehingga semua kendala dipenuhi oleh nilai-nilai ini. 

Strategi Means-Ends Analysis

Metode Means-Ends Analysis merupakan strategi pemecahan masalah yang dalam hal ini membagi masalah ke dalam masalah yang lebih sederhana, atau dari masalah yang khusus ke masalah yang lebih umum. Sehingga dengan begitu akan mendapatkan kesimpulan atau tujuan pembelajaran yang lebih dipahami dan dimengerti.

Means-Ends Analysis terdiri dari tiga unsur kata yakni; Mean, End dan Analysis. Mean menurut bahasa yakni berarti, banyaknya cara. Sedangkan End adalah akhir atau tujuan, dan Analysis berarti analisa atau penyelidikan secara sistematis. Jadi, Means-Ends Analysis adalah strategi belajar mengajar yang menganalisa suatu masalah dengan bermacam cara sehingga mendapatkan hasil atau tujuan akhir. Means-Ends Analysis pertama kali diperkenalkan oleh Newell dan Simon (wikipedia, 2007) dalam General Problem Solving (GPS), yang menyatakan bahwa Means-Ends Analysis adalah suatu teknik pemecahan masalah di mana pernyataan sekarang dibandingkan dengan tujuan, dan perbedaan di antaranya dibagi ke dalam sub-subtujuan untuk memperoleh tujuan dengan menggunakan operator yang sesuai.

 

Sumber :

 

http://blognyacomel.blogspot.co.id/2013/11/best-first-search.html

http://nailil-hidayah.blogspot.co.id/2013/11/kecerdasan-buatan.html

http://saefulnugroho.blogspot.co.id/2011/10/constraint-satisfaction.html

https://www.academia.edu/4698026/MAKALAH_MEANS-END_ANALYSIS_oleh_ROSTINTYA_DARMAYA_PERTIWI_10120098_B?auto=download

Read More