Algoritma Mini-Max

Artificial Intelligence

Kelas

Anggota Kelompok :

Ahmad Izzan Zahrial

Fahmi Herlambang

Fajri Wardana

Algoritma Mini-Max

Algoritma Minimax (juga sering disebut Minmax)adalah sebuah algoritma yang mendasari pola piki rlangkah penyelesaian masalah dalam beberapa jenis permainan komputer, seperti tic-tac-toe, othello,checkers, catur, dll. Pada dasarnya, algoritma Minimax sangat andal untuk menyelesaikan segala masalah dalam pencarian langkah untuk permainan komputer dengan jumlah kemungkinan penyelesaian yang kecil, seperti padapermainan tic-tac-toe. Tetapi, jika algoritma Minimaxdigunakan pada permainan dengan jumlahkemungkinan penyelesaian yang besar seperti pada permainan catur, algoritma Minimax ini memerlukanwaktu yang sangat lama untuk membangun pohonpenyelesaian. Oleh karena itu, beberapa metode optimasi telah dikembangkan untuk membatasi melonjaknya jumlah simpul dalam pembangunan pohon penyelesaian.Berbagai jenis metode telah ditemukan untukmengoptimasi algoritma Minimax, seperti alpha-betasearch, NegaScout, Null Move Search, MTD(f), dll. Dengan menggunakan metode optimasi inilah proseskomputasi penyelesaian masalah pada permaian catur dapat diminimalisasi.

1.1 Dasar Teori

Secara teori, algoritma Minimax didefinisikan sebagai berikut:

Untuk setiap permainan satu-lawan satu, ada sebuah nilai yang bernilai V dan strategi yang dipilih oleh tiap pemain, sehingga: (a), Jika diberikan strategi dari pemain ke-2, maka langkah penyelesaian terbaik dari pemain pertama adalah V. Dan (b), jika diberikan strategi dari pemain pertama, maka langkah penyelesaian terbaik dari pemain kedua adalah V

Singkatnya, pemain pertama memberikan langkah penyelesaian yang bernilai V terhadap permainan pemain kedua, dan sebaliknya, pemain kedua memberikan langkah peyelesaian bernilai V. Pemikiran inilah yang mendasari asal usul penamaan algoritma Minimax, dimana pemain yang satu berjuang untuk mendapat nilai maksimum,sedangkan lawannya berjuang untuk mendapat nilai minimum.

Gambar 1. Gambar pohon yang dibangun dengan

algoritma Minimax. Disini MAX diwakili aras genap,

sedangkan MIN diwakili aras ganjil.

Langkah-langkah membuat algoritma Minimax adalah sebagai berikut:

Misalkan ada 2 pemain yang terlibat, kita namakan MAX dan MIN.

Lalu sebuah pohon pencarian dibangkitkan secara depth-first-search dari posisi awal permainan hingga akhir permainan.

Dari sudut pandang MAX, akan dicari posisi terakhir yang paling menguntungkan bagi MAX.1.2 Implementasi Algoritma Minimax

Untuk lebih jelasnya, kita misalkan ada sebuah permainan sederhana yang dengan hanya ada satu langkah untuk tiap pemain dengan kemungkinan situasi seperti ini:

Pergerakan MAXPergerakan MINNilai Evaluasi

AC12

AD-2

BC5

BD6

Contoh nilai akhir pergerakan MAX dan MIN pada pohon Minimax.

Fungsi evaluasi berlaku untuk posisi akhir papan, yang berupa kombinasi langkah dari MIN dan MAX.

MAX berasumsi jika MIN akan bermain dengan baik. Maka dari itu, MAX tahu jika dia melakukan pergerakan A, maka MIN akan membalasnya dengan melakukan pergerakan D, yang mengakibatkan nilai evaluasi -2 (kemenangan bagi MIN). Bagaimanapun juga, jika MAX melakukan gerakan B, dia pasti akan menang karena pergerakan MIN yang terbaik hanya akan menghasilkan nilai evaluasi terbaik sebesar 5 saja. Jadi, dengan menggunakan algoritma Minimax, MAX akan selalu memilih untuk melakukan langkah B, walaupun dia sebenarnya akan mendapatkan kemenangan yang lebih baik jika melakukan A dan MIN melakukan kesalahan dengan memilih langkah C.

1.3 Kelebihan Algoritma Mini-MaxAdapun kelebihan algoritma ini adalah mampu memberikan pendekatan solusi-solusi yang nantinya diharakan dapat menjadi solusi yang diharapkan sebagai solusi yang baik dari permasalahan. Dengan adanya penambahan algoritma pada pencarian nilai heuristik yang dibuat untuk menentukan status pada setiap simpul pohon, maka akan sangat membantu dalam mengurangi kemungkinan cabang yang ada. Komputer akan mengembangkan simpul yang kira-kira mengarah pada solusi persoalan. Dengan otomatis algoritma ini akan lebih efisien dalam menentukan solusi terbaik.

Sangat baik digunakan untuk permainan yang menggunakan dua pemain yang dapat memainkan permainan secara bergantian.

1.4 Kelemahan Algoritma MiniMax

Dengan membangkitkan pohon pencarian ini, komputer akan selalu mendapatkan penyelesaian terbaik untuk setiap langkahnya. Tetapi, masalah muncul ketika jumlah input yang dimasukkan menjadi banyak.

Bayangkan saja, untuk posisi pertama dalam permainan catur dimana hanya terdapat kemungkinan untuk bergerak bagi 8 pion dan 2 kuda, akan terdapat sebanyak 8*2 + 2*2 = 20 kemungkinan. Hal ini berarti pada simpul awal akan didapatkan 20 sub-simpul sebagai langkah penyelesaian pada aras (level) ke 1. Jika komputer melakukan hal yang sama untuk menganalisis langkah selanjutnya (berarti komputer melakukan pembangkitan pohon untuk simpul pada aras ke 1) maka akan dilakukan 20 pembangkitan dimana pada tiap pembangkita akan dilakukan puluhan pembangkitan lain untuk aras ke 2. Demikian seterusnya hingga algoritma mencapai aras terakhir permainan, skakmat.

Berarti, usaha yang dilakukan akan tumbuh secara dramatis mengikuti:

Jumlah kemungkinan posisi penyelesaian untuk setiap pemain, dinamakan branching factor. Sering dinotasikan sebagai B.

Kedalaman aras pada pembangunan pohon pencarian, sering dinotasikan sebagai d. Biasa disebut juga 'ply', yang berarti sebuah langkah yang dilakukan oleh pemain.

Jika komputer hanya mengandalkan algoritma Minimax ini, proses membangkitkan simpul akan menjadi sangat lama. Kompleksitas dari algoritma Minimax ini adalah eksponensial sebesar O(Bd) [5]. Dengan nilai B untuk catur rata-rata adalah 35, dan jika kita akan menentukan 9 langkah kedepan, diperlukan sekitar 50 juta kemungkinan untuk dieksplorasi. Hal ini tentunya membutuhkan usaha yang sangat keras untuk mengecek seluruh kemungkinan.

Tentu saja diperlukan waktu yang lama untuk menganalisis seluruh kemungkinan ini dalam sebuah permainan catur jika hanya mengandalkan algoritma Minimax.

Constraint Satisfaction Problem (SCP)

2.1 Dasar TeoriConstraint adalah batasan dalam pengertian yang paling sederhana. Constraint adalah relasi logis di antara beberapa variabel, yang masing-masing mengambil sebuah nilai da-lam sebuah domain. Jadi constraint itu membatasi nilai yang dapat diambil oleh variabel tersebut. Dalam contoh guru mengajar kelas sebanyak mungkin asal jangan lebih dari ti-ga untuk hari apa saja, variabelnya adalah jumlah kelas yang diambil guru, domain-nya adalah bilangan asli, batasannya adalah variabel yang bersangkutan tidak boleh lebih dari tiga.Umumnya orang jarang menyelesaikan masalah dengan satu constraint tetapi masalah-masalah yang ada biasanya disertai dengan koleksi constraint yang jarang berkaitan. Hal ini tentu saja memperumit masalah. Sebelumnya penyebutan masalah dengan constraint ini distandarkan.

Untuk menyelesaikan masalah constraint satisfaction problem, diperlukan constraint programming. Constraint programming adalah pembelajaran sistem komputasi berdasar-kan constraint. Ide utama dari constraint programming ini adalah menyelesaikan masalah dengan menyatakan constraint (kondisi, sifat, kebutuhan) yang harus dipenuhi oleh solusi. Dengan kata lain, constraint programming adalah pendekatan alternatif terhadap pemro-graman yang berisikan permodelan suatu masalah sebagai himpunan kebutuhan (constra-int) yang berurutan diselesaikan metode umum ataupun spesifik untuk domain

Definisi Formal Constraint Satisfaction Problem

Berikut adalah definisi formal dari hal-hal yang berhubungan dengan constraint satisfac-tion problem.

Definisi 1.

Sebuah Domain berisikan nilai yang dapat diambil oleh sebuah variabel. Sebuah domain itu bersifat khusus untuk sebuah variabel. Jadi masing-masing variabel itu memiliki domain-nya masing-masing. Kesepakatan umum memberi huruf kapital D untuk menyebut domain. Berikut adalah contoh untuk domain dari variabel x.

(nilai x)

Domain dalam constraint satisfaction problem seringnya memiliki anggota bilangan bulat. Anggota sebuah domain boleh saja bukan numerik. Hal yang dapat menjadi anggota dari sebuah domain adalah simbol. Contoh anggota domain yang bukan numerik adalah nama bulan dalam satu tahun. Anggota domain-nya adalah Januari, Februari, Maret, April, Mei, Juni, Juli, Agustus, September, Oktober, November, dan Desember.

Definisi 2.

Sebuah label adalah pemberian nilai dari domain sebuah variabel ke variabel itu. Jika ingin memberi nilai v ke variabel x digunakan notasi . Tentunya v Dx.

Definisi 3.

Kumpulan label adalah tupel dari label. Kumpulan label digunakan untuk menya-takan pemberian nilai-nilai ke variabel yang jumlahnya lebih dari satu. Digunakan notasi tupel (. . .) untuk menyatakan kumpulan label dari pemberian v1, v2, . . . , vn pada x1, x2, . . . , xn.

Karena kumpulan label adalah tupel, urutan dari label pada representasi ini menjadi tidak signifikan. Dengan kata lain, () dianggap sama seperti kumpulan label (), (), dan lain-lain. Di samping itu, adalah penting untuk mengingat bahwa tupel tidak memiliki anggota yang sama.

Sebuah constraint pada sebuah himpunan variabel membatasi nilai yang dapat diambil secara bersamaan. Menurut konsep, sebuah constraint dapat dilihat sebagai sebuah him-punan yang memiliki semua kumpulan label yang valid pada variabel yang bersangkutan (Edward Tsang, 1996, p7). Walaupun begitu, pada kenyataannya di lapangan, constra-int dapat dinyatakan dengan banyak cara, contohnya, fungsi, pertidaksamaan, matriks, dan lain-lain.

Definisi 4Jika variabel-variabel dari kumpulan label X adalah sama dengan variabel-variabel dari elemen kumpulan label pada constraint C, maka X memenuhi-constraint C jika dan hanya jika X adalah elemen dari C:

memenuhi-constraint( (. . . ), Cx1,x2,...,xk ) (. . . ) Cx1,x2,...,xkMemenuhi constraint juga didefinisikan antara label dan constraint unari.

Definisi 5memenuhi-constraint(, Cx) () CxJika dikatakan kumpulan label L memenuhi constraint C, itu artinya jika C adalah se-buah constraint pada variabel x1, x2, . . . , xk atau subset-nya, maka label pada variabel itu dalam L adalah valid sepanjang C dipenuhi. Untuk contohnya, () memenuhi constraint Cc,d jika dan hanya jika () adalah anggota Cc,d:

Cc,d = . . ., (), . . .

Setelah berbagai hal yang merupakan bagian dari constraint satisfaction problem itu sudah didefinisikan, pekerjaan mendefinisikan constraint satisfaction problem itu menjadi mudah. Sebelumnya untuk menyegarkan ingatan, dalam bahasa umum constraint satis-faction problem adalah sebuah masalah dengan sebuah himpunan variabel dengan jumlah berhingga, masing-masing diasosiasikan dengan sebuah domain dengan jumlah anggota berhingga juga, dan sebuah himpunan constraint yang membatasi nilai yang dapat di-ambil oleh variabel-variabel ini secara bersamaan. Berikut diberikan definisi formal dari constraint satisfaction problem.

Definisi 6.

Sebuah constraint satisfaction problem adalah sebuah himpunan dengan tiga vari-abel:

(Z, D, C)

di mana Z = sebuah himpunan dari variabel-variabel dengan jumlah berhingga x1, x2, . . . , xn;

D = sebuah fungsi yang memetakan setiap variabel pada Z ke sebuah himpunan dari objek-objek:

D : Z himpunan objek-objek dengan jumlah berhingga (jenis apa pun). Di-sebut Dxi sebagai himpunan dari objek-objek yang dipetakan dari xi oleh D. Objek-objek ini adalah nilai-nilai yang mungkin bagi xi dan himpunan Dxi sebagai domain xi;

= sebuah himpunan constraint yang berhingga (yang memiliki kemungkinan ko-song) atas sebuah subset variabel-variabel di Z. Dengan kata lain, C adalah se-buah himpunan atas kumpulan label.

Digunakan csp(P) untuk menyatakan P adalah constraint satisfaction problem.

membatasi himpunan kumpulan label yang x1, x2, . . . , dan xk yang dapat

diambil secara bersamaan. Sebagai contoh, jika variabel x hanya dapat mengambil nilai a, b dan c, maka ditulis Cx = (), (), (). Perhatikan perbedaan antara

Cx dan Dx: Cx adalah sebuah himpunan kumpulan label sementara Dx adalah sebuah himpunan nilai. Nilai x yang mungkin juga harus memenuhi constraint selain Cx. Hal itu berarti walaupun memenuhi Cx, a mungkin bukan nilai yang valid bagi x un-tuk keseluruhan masalah. Untuk mendapatkan label yang valid, mesti memenuhi semua constraint yang mengandung constraint x, contohnya Cx,y, Cx,y,z, dan lain-lain.

Definisi 7.

Sebuah tupel solusi atas sebuah constraint satisfaction problem adalah kumpulan label yang semua anggotanya memenuhi semua constraint:

csp((Z, D, C)): x1, x2, . . . , xn Z:

v1 Dx1 , v2 Dx2 , . . . , vn Dxn :

tupel solusi(( . . . ), (Z, D, C)) ((Z = x1, x2, . . . , xn) (C C: memenuhi-constraint(( . . . ), C)))

Sebuah constraint satisfaction problem disebut memiliki penyelesaian jika memiliki tupel solusi. Tergantung dari kebutuhan aplikasinya, constraint satisfaction problem dapat dikategorikan menjadi beberapa kategori sebagai berikut.

Constraint satisfaction problem di mana yang dicari adalah solusi yang mana saja.

Constraint satisfaction problem di mana yang dicari adalah semua solusi.

Constraint satisfaction problem di mana yang dicari adalah solusi yang optimal, di mana optimal itu didefinisikan menurut kebutuhan pengguna.

Pencarian Sistematis

2.2.1 Generate and Test

Sebenarnya siapa pun dapat menyelesaikan constraint satisfaction problem yang mana pun. Caranya gampang sekali. Mencoba semua kombinasi nilai ke variabel-variabel yang ada. Cari ini dijamin dapat memperoleh sebuah solusi, jika ada, atau membuktikan bahwa masalah ini tidak bisa dipecahkan. Oleh karena itu, algoritma ini dipastikan dapat mencari semua solusi dengan lengkap. Untuk constraint satisfaction problem yang sederhana tentu saja ini tidak menjadi masalah. Tetapi constraint satisfaction problem adalah masalah NP-hard. Artinya seiring dengan meningkatnya jumlah variabel pada constraint satisfaction problem, jumlah kombinasi yang harus dicoba meningkat secara kuadrat. Menghabis-kan waktu yang sangat lama untuk mencoba semua kombinasi bahkan walaupun dibantu komputer dengan spesifikasi yang canggih dalam menghitungnya. Jadi kebanyakan waktu dalam riset constraint programming dihabiskan dalam mencari algoritma pencarian yang efisien. Dari riset ini muncul beberapa algoritma pencarian sistematis. Algoritma generate and test memang tidak efisien tapi algoritma ini menjadi dasar dari pengembangan algori-tma pencarian sistematis lainnya. Oleh karena itu, untuk memahami algoritma pencarian sistematis lainnya, perlu dipahami terlebih dahulu algoritma generate and test.

Sebelum algoritma generate and test ini dibahas, ada baiknya pencarian kombinasi ni-lai ke variabel-variabel itu divisualisasikan ke dalam bentuk pohon. Visualisasi pencarian kombinasi nilai bagi variabel-variabel akan memudahkan pemahaman algoritma pencarian sistematis yang mana pun dalam constraint programming.

Misalnya ada constraint satisfaction problem sebagai berikut. Constraint satisfaction problem ini terdiri dari tiga variabel, a, b, dan c. Da untuk constraint satisfaction pro-blem ini adalah {1, 2, 3} sedangkan Db-nya {1, 2} dan Dc-nya {1, 2}. Dalam gambar 2.2, pencarian solusinya mulai dari variabel a. Karena jumlah anggota Da adalah 3 maka ada 3 jalan dari titik yang paling atas (solusinya mulai dicari dari variabel a). Titik yang ditandai dengan mewakili status pencarian. Artinya dalam konteks gambar ini adalah diputuskan (setidaknya untuk sementara) untuk memberi nilai 1 ke variabel a dan sedang mempertimbangkan nilai apakah yang akan diberikan ke variabel b.

Algoritma generate and test dapat dibayangkan sebagai algoritma depth-first search yang paling dasar. Dalam konteks gambar pohon ini, algoritmanya dimulai dengan nilai a paling kiri yaitu 1, kemudian nilai b paling kiri yaitu 1, kemudian nilai c paling kiri yaitu 1.

Gambar 2.1: Ruang pencarian untuk csp(Z, D, C) dengan urutan (a, b, c) di mana Z =

{a, b, c}, Da = {1, 2, 3}, Db = {1, 2}, dan Dc = {1, 2}

Setelah semua variabel diberi nilai, barulah algoritma ini menguji apakah kombinasi nilai ini memenuhi semua constraint yang ada. Jika tidak, dicoba nilai variabel yang terakhir kali diberi nilai (c) yang lain, yaitu 2 . Ujilah lagi. Jika tidak, karena semua nilai untuk variabel c untuk kumpulan label () sudah dicoba, maka dicoba nilai untuk variabel b berikutnya. Begitu seterusnya. Jumlah kombinasi yang dicoba oleh algoritma ini sama dengan ukuran produk Cartesian semua domain variabel.

Seperti yang sudah dijelaskan, algoritma generate and test ini sangat tidak efisien ka-rena algoritma ini menghasilkan banyak pemberian nilai ke variabel-variabel yang ditolak pada fase uji coba. Sebagai tambahan, generator seakan-akan tidak peduli dengan pembe-rian nilai yang memiliki konflik dan terus memberikan nilai yang lain tanpa memandang konflik. Singkatnya, algoritma ini merupakan generator yang buta. Dapat dipastikan algo-ritma ini tidak berguna pada hampir semua masalah constraint satisfaction problem kare-na kebanyakan masalah constraint satisfaction problem bersifat eksponensial. Contohnya pada masalah pewarnaan tiga warna pada n verteks. Ada 3n kemungkinan pewarnaan. Untuk n lebih besar daripada 20, mengiterasi semua kemungkinan berada di luar jangkau-an. Ada yang dapat dilakukan untuk meningkatkan pendekatan algoritma ini.

2.2.2 Backtracking

Algoritma ini adalah algoritma yang paling umum dan paling banyak dipakai dalam aplikasi penghitungan untuk constraint satisfaction problem. Pada dasarnya back-tracking secara perlahan-lahan mencoba mengembangkan kumpulan label yang ma-sih belum lengkap untuk beberapa variabel, menuju ke kumpulan label yang leng-kap, dengan secara berulang-ulang memilih nilai bagi variabel yang lain yang kon-sisten dengan solusi yang masih belum lengkap ini. Algoritma backtracking ada-lah pendekatan brute-force yang sudah diperbaiki, yang secara sistematik mencari se-buah solusi atas sebuah masalah di antara semua pilihan yang ada.Berikut ini adalah alur algoritma ini. Variabel yang diperiksa sekarang diberi nilai tertentu. Label ini diperiksa kecocokannya dengan semua label yang sudah masuk dalam tupel solusi. Jika label ini tidak cocok dengan label-label yang sudah ada di tupel solusi, maka label ini akan ditolak, dan label yang lain akan dicoba. Pada kasus di mana semua label sudah ditolak, label yang masuk ke tupel solusi terakhir kalinya dianggap tidak co-cok lagi, dan ditolak. Memeriksa label yang masuk ke tupel solusi terakhir kali disebut backtrack. Proses ini berlanjut sampai semua variabel sudah diberi label atau tidak ada la-gi label yang bisa di-backtrack, yakni dalam hal semua label untuk variabel pertama sudah ditolak. Pada kasus terakhir ini, constraint satisfaction problem dianggap tidak memiliki penyelesaian.

Pada backtracking ini, tidak ada usaha untuk menggunakan constraint selain pada saat memeriksa kekonsistenan label untuk variabel yang sedang diperiksa dengan kumpulan label yang sudah ada di dalam tupel solusi. Proses ini adalah pencarian yang sangat me-lelahkan di mana secara sistematis dieksplorasi seluruh ruang pencarian. Proses ini sama dengan generate and test, bersifat lengkap dan semua hasil yang didapatkannya memenuhi

15

constraint. Tidak ada usaha untuk mengurangi sebagian ruang pencarian.

Contoh berikut akan memperjelas algoritma backtracking dan perbedaannya dengan generate and test. Ada sebuah constraint satisfaction problem yang terdiri dari 3 variabel, yaitu a dengan Da = {1, 2, 3, 4}, b dengan Db = {1, 2, 3, 4}, dan c dengan Dc = {4, 5, 6}.

Constraint-nya adalah Ca,b = a < b dan Ca,b,c = a + b = c. Pencarian solusi dimulai dari variabel a. Diberikan nilai 1 untuk a. Pada saat ini label akan diperiksa apa-kah melanggar constraint yang ada. Tapi karena tidak ada constraint unari untuk a maka pencarian bergerak ke tingkat yang lebih dalam, yaitu tingkat di mana variabel b berada. b diberi nilai 1. Pada saat ini label diperiksa apakah konsisten dengan kumpulan label yang sudah ada dalam tupel solusi () dan constraint unari untuk b jika ada. Label tidak konsisten dengan kumpulan label () karena melanggar constraint Ca,b. Maka dicari nilai yang lain untuk b, yaitu 2. Seperti biasa label ini akan diperiksa apakah konsisten dengan kumpulan label (). Hasilnya adalah konsisten. Pencarian pun bergerak ke tingkat yang paling dalam, yaitu tingkat di mana variabel c berada. c diberi nilai, yaitu 4. Pada saat ini label akan diperiksa apakah konsisten dengan kumpulan label (,). Ternyata tidak karena melanggar constraint Ca,b,c. Ma-ka diberikan nilai yang lain untuk c. Dapat dilihat tidak ada satu pun nilai dari Dc yang konsisten dengan kumpulan label (,). Maka pencarian melakukan backtrack seperti yang terlihat pada gambar 2.3. Label terakhir dari kumpulan label (,) yaitu ditolak dan nilai yang lain diberikan untuk b. Dapat dilihat perbedaan back-tracking dengan generate and test di mana pencarian dengan metode generate and test memberi nilai ke semua variabel terlebih dahulu sebelum memeriksa apakah pemberian nilai ini memenuhi constraint atau tidak. Sementara itu pencarian dengan metode back-tracking memeriksa apakah pemberian nilai itu memenuhi constraint yang ada pada saat setiap variabel diberi nilai.

16

Gambar 2.2: Contoh constraint satisfaction problem di mana terjadi backtrack

Konsistensi Constraint

2.3.1 Pengertian Dasar

Nama lain konsistensi constraint adalah problem reduction. Intinya adalah berusaha meng-urangi masalah dengan harapan masalah yang bersangkutan menjadi lebih mudah dise-lesaikan. Sekarang ini sudah diketahui teknik konsistensi ini sangat penting dalam pe-nyelesaian constraint satisfaction problem yang berat sehingga semua aplikasi komersial penyelesaian constraint satisfaction problem menggunakan teknik konsistensi ini seba-gai langkah dasar (Christian Bessire; Jean-Charles Rgin, 2001, p1). Sejarah konsistensi constraint dapat ditelusuri dari peningkatan efisiensi program pengenalan gambar oleh pe-neliti di intelejensi semu. Pengenalan gambar melibatkan pemberian label kepada semua garis pada gambar dengan cara yang konsisten. Jumlah kombinasi pemberian label pada garis yang memungkinkan dapat menjadi sangat besar, sementara hanya sedikit yang kon-sisten. Teknik konsistensi dengan efektif membuang semua pemberian nilai yang tidak konsisten pada tahap awal. Dengan demikian memperpendek pencarian untuk pemberian nilai yang konsisten.

Untuk mengilustrasikan teknik konsistensi ini akan diberikan sebuah contoh constraint

17

Gambar 2.3: Graf menggambarkan constraint

satisfaction problem yang sangat sederhana. Anggap A < B adalah constraint antara variabel A dengan domain DA = {3..7} dan variabel B dengan domain DB = {1..5}. Dengan jelas tampak bahwa untuk sebagian nilai pada DA tidak ada nilai yang konsisten di DB yang memenuhi constraint A < B dan sebaliknya. Nilai yang demikian dapat dibuang dari domain yang berkaitan tanpa kehilangan solusi apa pun. Reduksi itu aman. Didapatkan domain yang tereduksi DA = {3, 4} dan DB = {4, 5}.

Perhatikan bahwa reduksi ini tidak membuang semua pasangan yang tidak konsisten. Sebagai contoh kumpulan label (,) masih dapat dihasilkan dari domain, te-tapi untuk setiap nilai A dari DA adalah mungkin untuk mencari nilai B yang konsisten dan sebaliknya.

Walaupun teknik konsistensi ini jarang digunakan sendirian untuk menghasilkan solusi (walaupun dapat), teknik konsistensi ini membantu menyelesaikan constraint satisfaction problem dalam beberapa cara. Teknik konsistensi ini dapat dipakai sebelum pencarian maupun pada saat pencarian.

Constraint sering direpresentasikan dengan gambar graf (gambar 2.4) di mana setiap verteks mewakili variabel dan busur antar dua verteks mewakili constraint binari yang mengikat variabel-variabel yang dihubungkan dengan busur tersebut. Constraint unari diwakilkan dengan busur melingkar.

2.3.2 Konsistensi Verteks

Teknik konsistensi yang paling sederhana adalah konsistensi verteks.

Definisi 9.

Sebuah constraint satisfaction problem adalah konsisten secara verteks jika dan ha-nya jika untuk semua variabel semua nilai di domain-nya memenuhi constraint unari untuk variabel yang bersangkutan.

csp((Z, D, C)) :

konsisten-verteks((Z, D, C)) (x Z : (v Dx : memenuhi-constraint(, Cx)))

Konsistensi verteks sering disebut juga dengan konsistensi-1. Angka 1 ini mewakili constraint unari yang harus dipenuhi oleh semua variabel.

Jika domain DX untuk variabel X memiliki nilai a yang tidak memenuhi constra-int unari untuk variabel X, maka pemberian nilai a ke X akan mengakibatkan kegagalan langsung. Oleh karena itu ketidakkonsistenan secara verteks dapat dihapuskan dengan membuang semua nilai dari domain DX untuk variabel X yang tidak memenuhi constra-int unari pada X (Roman Bartk, 2005, p15).

2.3.3 Konsistensi Busur

Jika constraint satisfaction problem yang ada sudah menjadi konsisten secara verteks, ma-ka constraint unari dapat dihapus. Setelah konsisten secara verteks, maka pekerjaan yang tersisa adalah memastikan konsisten secara busur. Busur melambangkan constraint binari. Dua variabel dikatakan konsisten secara busur jika untuk setiap nilai dari domain variabel pertama dapat ditemukan nilai dari domain variabel kedua dan label ini memenuhi con-straint untuk kedua variabel tersebut.

Definisi 10.

Pasangan variabel (x, y) sebuah csp(Z, D, C) adalah konsisten secara busur jika dan

hanya jika setiap nilai a di domain x yang memenuhi constraint pada x, ada nilai dari domain y yang memenuhi constraint pada y dan konsisten dengan label :

csp((Z, D, C)) : x, y Z :

konsisten-busur((x, y), (Z, D, C)) (a Dx : memenuhi-constraint((, Cx) b Dy : (memenuhi-constraint((), Cy)) memenuhi-constraint((, , Cx,y)))

Dari definisi, jelas bahwa busur (Vi, Vj ) dapat dibuat konsisten dengan menghapus nilai-nilai di domain dari Vi di mana tidak ada nilai yang berkaitan di domain Dj sehing-ga constraint binari antara Vi dan Vj dipenuhi (perhatikan bahwa menghapus nilai-nilai tersebut tidak menghapus solusi yang mana pun dari constraint satisfaction problem yang bersangkutan).

Sebuah constraint satisfaction problem dikatakan konsisten secara busur jika setiap nilai pada setiap domain memiliki dukungan di domain yang lain. Membuat masalah constraint satisfaction problem konsisten secara verteks sering dilakukan di tahap pra-pemrosesan: mengurangi ukuran beberapa domain biasanya membuat masalah menjadi lebih mudah dipecahkan (Barbara M. Smith, 1995, p5). Untuk membuat setiap busur dari graf constraint konsisten, atau dengan kata lain untuk membuat suatu constraint satisfac-tion problem konsisten secara busur, adalah tidak cukup untuk melakukan penghapusan nilai-nilai yang tidak konsisten secara busur untuk suatu variabel di domain hanya sekali saja. Ketika domain dari Vi sudah dikurangi anggotanya, maka setiap busur (Vi, Vj ) yang sudah pernah diotak-atik harus diperiksa lagi, karena beberapa anggota dari domain untuk

Vi mungkin tidak konsisten lagi dengan anggota domain variabel-variabel yang diperiksa kekonsistenannya secara busur terhadap variabel Vi. Untuk mengatasi masalah ini, di-kembangkan algoritma AC-1 yang pada dasarnya mengulang pemeriksaan kekonsistenan antara dua variabel terus-menerus sampai tidak ada domain mana pun yang berubah. Ber-ikut adalah dari algoritma AC-1.

Optimalisasi Dalam Constraint Satisfaction Problem

2.4.1 Pengertian Dasar

Pada bagian sebelumnya, sudah dibahas teknik-teknik untuk menyelesaikan constraint satisfaction problem di mana semua solusinya sama baiknya. Pada permasalahan seperti optimalisasi penjadwalan pekerjaan di industri, beberapa solusi adalah lebih baik daripada solusi lainnya. Pada kasus lainnya, pemberian nilai kepada variabel-variabel yang sama mengakibatkan harga yang berbeda. Tugas dari permasalahan ini adalah untuk mencari solusi yang paling optimal di mana keoptimalan suatu solusi itu didefinisikan oleh fungsi yang spesifik untuk aplikasi. Masalah ini biasa disebut sebagai constraint satisfaction optimization problem untuk membedakan dengan constraint satisfaction problem biasa.

Semua masalah optimalisasi yang dipelajari di riset operasional adalah constraint sa-tisfaction problem pada pengertian umum, di mana constraint umumnya adalah numerik.

Definisi 11.

Sebuah constraint satisfaction optimization problem didefinisikan sebagai constra-int satisfaction problem dengan fungsi optimalisasi f yang memetakan setiap tupel solusi ke sebuah nilai numerik:

(Z, D, C, f)

di mana (Z, D, C, f) adalah constraint satisfaction problem, dan jika S adalah him-punan tupel solusi dari (Z, D, C), maka

f : S nilai numerik

Diberikan sebuah tupel solusi T , f(T ) disebut sebagai nilai f dari T .

Tugas dalam constraint satisfaction optimization problem adalah untuk mencari tupel solusi nilai f yang optimal (minimal atau maksimal) yang ditentukan oleh fungsi f op-timalisasi yang spesifik untuk aplikasi. Constraint yang umum disebut hard constraints, sementara fungsi f disebut soft constraints. Penamaan ini menggambarkan bahwa hard constraints harus dipenuhi, sementara soft constraints memiliki preferensi terhadap bebe-rapa solusi (yang mempunyai nilai tinggi/rendah) dari yang lainnya (yang mempunyai nilai lebih rendah/lebih tinggi) (Anonim, http://en.wikipedia.org/wiki/Constraint_optimization, 2006).

Masalah alokasi sumber daya di penjadwalan adalah constraint satisfaction optimi-zation problem. Pada banyak masalah penjadwalan, mencari solusi yang mana pun ti-daklah cukup baik. Seseorang mungkin ingin mencari cara yang paling ekonomis da-lam mengalokasikan sumber daya ke pekerjaan-pekerjaan, atau mengalokasi mesin ke pekerjaan-pekerjaan, memaksimalkan beberapa kualitas yang bisa diukur dari hasil ke-luaran. Masalah-masalah ini adalah constraint satisfaction optimization problem.

Untuk mencari solusi yang paling optimal, seseorang mungkin harus mencari semua solusi terlebih dahulu, dan kemudian membandingkan nilai f mereka. Sebagian dari ru-ang pencarian dapat dipotong jika seseorang dapat membuktikan bahwa solusi yang lebih optimal dari solusi sebelumnya tidak berada di dalamnya. Hal ini berarti tidak ada solusi yang berada di dalamnya atau nilai f pada setiap solusi di ruang pencarian yang dipotong itu tidak lebih optimal dari solusi yang sudah didapatkan (sub-optimal).

2.4.2 Branch and Bound

Untuk menyelesaikan masalah constraint satisfaction optimization problem, digunakan fungsi f untuk memandu pencarian. Branch and bound, yang merupakan algoritma pen-carian umum dalam pencarian solusi optimal, menggunakan fungsi f. Di sini tetap digu-nakan tupel solusi untuk menyebut kumpulan label yang memberikan nilai kepada semua variabel yang memenuhi constraint. Perlu diperhatikan bahwa tupel solusi di sini tidak harus mengacu kepada solusi optimal pada constraint satisfaction optimization problem.

Branch and bound adalah teknik yang terkenal pada riset operasi dan intelejensi semu. Teknik ini didasarkan pada fungsi heuristik yang baik dalam memperkirakan nilai terbaik (terbaik menurut fungsi optimalisasi) pada semua verteks di bawah cabang yang sedang diperiksa pada pohon pencarian (Edward Tsang, 1996, p301). Jika fungsi heuristiknya bagus, seseorang dapat memotong ruang pencarian yang di dalamnya tidak terdapat solu-si optimal. Oleh karena itu, walaupun branch and bound tidak mengurangi kompleksitas algoritma pencarian, tapi teknik ini dapat menjadi lebih efisien daripada backtracking saja.

Untuk menerapkan branch and bound pada constraint satisfaction optimization pro-blem, seseorang memerlukan sebuah fungsi heuristik h yang memetakan semua kumpulan label CL ke sebuah nilai numerik (h : CL angka). Nilai ini disebut nilai h dari kum-pulan label. Supaya fungsi h dapat diterima, nilai h dari setiap kumpulan label CL harus lebih besar (lebih kecil) dari nilai f dari setiap tupel solusi pada masalah maksimalisasi (minimalisasi).

Sebuah variabel global, yang disebut sebagai bound, akan diinisialisasi minus tak ter-hingga pada masalah maksimalisasi. Teknik ini mencari solusi dengan kelakuan depth-first. Teknik ini menggunakan backtracking. Ketika sebuah label ingin ditambahkan ke kumpulan label, nilai h dari kumpulan label yang ada (berikut label yang baru masuk itu) dihitung. Jika nilai h ini lebih kecil dari bound pada masalah maksimalisasi, maka cabang tempat kumpulan label berada dipotong. Ketika sebuah tupel solusi ditemukan, nilai f di-hitung. Nilai f akan menjadi nilai bound jika dan hanya jika lebih besar dari bound yang sudah ada pada masalah maksimalisasi. Ketika nilai f ini lebih besar dari bound, maka solusi yang baru ditemukan akan dimasukkan ke kumpulan solusi terbaik sampai saat ini. Setelah pencarian selesai, tupel solusi yang terakhir didapatkan dapat dianggap sebagai solusi yang paling optimal.Efisiensi dari branch and bound ditentukan oleh dua faktor: kualitas fungsi heuristik dan apakah bound yang bagus ditemukan pada tahap awal. Pada masalah maksimalisasi, jika nilai h adalah selalu memperkirakan lebih tinggi dari nilai f, maka perkiraan menjadi lebih dekat ke nilai f (contohnya, semakin kecil nilai h tanpa lebih kecil dari nilai f), lebih besar kemungkinannya bagian yang cukup besar dari ruang pencarian dipotong.

Contoh constraint satisfaction optimization problem yang sederhana

27

Ruang pencarian yang dijelajahi oleh backtracking sederhana dalam constra-int satisfaction optimization problem

Ruang pencarian yang dijelajahi oleh branch and bound dalam constraint satisfaction optimization problem

28

Ruang pencarian yang dijelajahi oleh branch and bound dalam constraint satisfaction optimization problem ketika bound yang bagus ditemukan pada tahap awal pencarian

II. Kerjakan soal-soal di bawah ini :

1. Selesaikan soal criptarithmetic Problem berikut dengan algoritma Constrain Satisfaction :

CROSS

+ ROADS

DANGER

2. Di bawah ini diperlihatkan search tree dari suatu maximizing game. Dengan menggunakan alph beta prunning algoritm, tentukan nilai alpha optimal yang dapat dicapai oleh seorang maximizing player. Jelaskan bagaimana mekanisme cut off dilakukan terhdp cabang yang tidak relevan

Jawaban1.

CROSS 86433

+ ROADS ( + 64513

DANGER 150946

Solusi :

A = 5

C = 8D = 1

E = 4

N = 0O = 4

R = 6

S = 3

2.

Nilai alpha optimal yang didapat = 8

cutoff dilakukan sebelum titik j dan nilai 10 setelah titik D, dilakukan karena nilai alpha pada saat proses telah memenuhi syarat ( alpha >= beta )

cutoff 1: nilai alpha = 9, beta = 8

cutoff 2: nilai alpha = 8, beta = 7

max

A

10

75

10

K

J

H

D

G

I

F

E

B

C

8

-2

3

4

7

3

5

8

6

9

max

A

10

75

10

K

J

H

D

G

I

F

E

B

C

8

-2

3

4

7

3

5

8

6

9