Pembahasan dari soal GSLC 1

1. Apa yang dimaksud Adversarial Search & Constraint Satisfaction Problems ? Berikan contoh.
2. Apa itu Propositional Logic ? Berikan contoh.

Jawab :

1. Secara sederhana, adversarial search lebih dikenal sebagai sebuah game (permainan) yangg umumnya diaplikasikan dalam permainan-permainan dimana membutuhkan dua pihak yang akan saling mengalahkan satu sama lain. Umumnya, permainan yang dititikberatkan disini adalah permainan yang melibatkan 2 orang atau lebih dan secara bergiliran mengambil keputusan.
Permainan yang dimaksud disini bisa dikategorikan ke permainan bersifat deterministik dan permainan berdasarkan kesempatan. Untuk masing-masing kategori, bisa memiliki sifat perfect information (kedua pemain sama-sama tahu keadaan yang pasti) dan imperfect information (kedua pemain memiliki informasi terbatas yang tergantung pada langkah yang diambil). Contohnya catur (deterministik-perfect information), monopoly (kesempatan-perfect information), bridge (deterministik-imperfect information), dan poker (kesempatan-imperfect information).
Sebuah game dapat didefinisikan melalui initial state (status awal permainan/bagaimana set awal sebelum permainan dimulai), legal actions (tindakan2 sah), hasil tiap tindakan, terminal test (status ketika permainan dinyatakan selesai), dan sebuah utility function (pemberi hasil numerik) yang dijalankan ketika permainan selesai.
Dalam penerapannya, adversarial search umumnya menggunakan pencarian minimax dan alpha-betha pruning (pemangkasan alpha-beta).
Constrain Satisfaction Problem merupakan sebuah masalah khusus yang memenuhi beberapa sifat tambahan diluar persyaratan dasar dari masalah secara umum. Pada CSP, tahap/state didefinisikan sebaga nilai dari himpunan variabel dan tahap goal mewakili himpunan pembatas/constrain dimana nilai-nilai yang ada harus berpatokan pada pembatas ini.
Sebagai contoh, pada n-queen problem, dapat dilihat sebagai CSP dimana variabel adalah lokasi dari ratu-ratu yang ada (sebanyak n ratu), dan pembatas menegaskan bahwa tidak boleh ada 2 ratu yang berada pada kolom, baris, atau posisi diagonal yang sama. Solusi dari CSP ini adalah nilai dari variabel yang memenuhi batasan yang ada, dan juga tujuan yang dimaksud tercapai.
Contoh masalah lain yang dapat dilihat dengan sudut pandang CSP adalah teka-teki silang, kriptografi, dan map coloring.

2. Proporsitional Logic umumnya kita kenal sebagai logika matematika. Proporsitional Logic membahas mengenai hubungan dari 2 atau lebih pernyataan dalam kata-kata, namun tetap berdasarkan asas-asas logika yang jelas.
Komponen-komponen dari proporsitional logic antara lain syntax, semantic, dan evaluation. Syntax membahas mengenai istilah-istilah yang digunakan, semantic adalah aturan-aturan penggunaannya, dan evaluasi mengenai hasil akhir.

Penerapan dari proporsitional logic salah satunya adalah untuk menentukan apakah sebuah pernyataan yang merupakan hasil hubungan dari 2 atau lebih pernyataan bernilai valid terhadap pernyataan-pernyataan tersebut dengan menggunakan tabel kebenaran.

Sumber :
http://web.cs.swarthmore.edu/~meeden/cs63/f11/russell-norvig-ch5.pdf
http://www.cs.sfu.ca/CourseCentral/310/oschulte/mychapter5.pdf
http://www.ics.uci.edu/~smyth/courses/cs271/topic6_adversarial_search.ppt
http://logic.stanford.edu/classes/cs157/2007/notes/chap02.html
http://www.iep.utm.edu/prop-log/#SH3a
Artificial Intelligence – A Modern Approach – Russel, Peter And Norvig, Stuart