BAB 2 TINJAUAN PUSTAKA

BAB 2

TINJAUAN PUSTAKA

2.1 Permainan

Di zaman sekarang, terkadang sebagian manusia lebih memilih untuk bermain di kehidupan maya dibandingkan di kehidupan nyata.Dan mereka memilih sebagai dunia baru karena memang lebih tentram juga lebih damai walau kadang ada keributan. Dunia permainan juga tidak jauh beda layaknya dunia maya yang sering dipergunakan untukberinteraksi. Namun dalam dunia permainan maya, kita dapat merasakannya seolah-olah menjadi nyata. Karena di sana kita dapat membentuk karakter yang kita inginkan dan kita juga dapat menjadi karakter yang kita inginkan. Dimana di dalam dunia ini kita membentuk karakter layaknya yang ada di dalam diri kita dan terkadang kita mencerminkan apa yang ada dalam diri kita dalam dunia ini. Sehingga kita tuangkan diri kita ini ke dunia permainantersebut.

2.1.1 Sejarah Permainan

Manusia telah mengenal dan memainkan permainan sejak dahulu kala. Di sahara ditemukan sebuah papan permainan yang terbuat dari batu yang mirip seperti Mancala yang telah berusia ±5000 tahun. Menurut David Fox dan Roman Verhosek, permainan Go, yang popular di Negara-negara oriental, sebenarnya telah ada sejak 2000 SM. Bahkan sebuah permainan yang mirip Backgamon seperti Tabula dan Nard telah tercatat pada skrip Romawi kuno [1].

Universitas Sumatera Utara

Pada tahun 1952, seorang mahasiswa Universitas Cambridge bernama A.S Gouglas membuat permainan OXO (tic tac toe) dalam versi grafik. Permainanini ia kembangkan ketika hendak mendemonstrasikan tesisnya tentang interaksi antara manusia dan komputer.

Memasuki era modern, pada tahun 1966 permainan digital pertama kali dibuat oleh Ralph Baer bersama timnya yang berjumlah 500 orang yang terdiri dari insinyur dan teknisi dan didanai oleh Pentagon. Permainan ini hanya dapat dimainkan dengan komputer seharga US$40.000.Unsur edukasi menjadi tujuan utama dalam permainan ini.Permainan dalam bentuk permainan antara papan dan bola tersebut diperuntukkan untuk membantu pasukan belajar strategi dan melatih kemampuan refleks pemainnya.

Pada tahun 1972, muncul permainan baru yang disebut Permainan Arcade, yang dipelopori oleh Nolan Brushnel dengan permainannya berjudul Pong. Mesin untuk memainkan permainan ini disebut mesin Arcade.Pemain yang ingin bermain diharuskan untuk memasukkan koin kedalam mesin.Pada hari kedua mesin ini diletakkan pada suatu bar, orang-orang mengantri untuk memainkan permainan Pong.

Tidak mau tertinggal dengan sistem Arcade, sistem konsol seperti Magnavox Odyssey, Atari 2006, Mattel Intelvision, Calleco Vision dan Nintendo Entertaiment Sistem menciptakan permainan yang dapat dimainkan di rumah. Permainan yang paling menghebohkan orang-orang dengan tampilan grafik dan permainan play yang luar biasa pada sistem konsol tersebut adalah Super Mario Brothers yang diciptakan oleh Nintendo.

Pada perkembangannya, permainan komputer berkembang dengan pesatnya seiring perkembangan perangkat keras yang mendukung.Hal ini dibuktikan dengan program permainan yang lebih kompleks dan tampilan grafik tiga dimensi.


2.2

Permainan Rubik’s Cube

2.2.1 Sejarah Permainan Rubik’s Cube

Kubus Rubik’s adalah sebuah teka-teki mekanik tiga dimensi yang ditemukan pada tahun 1974 oleh pemahat dan profesor arsitektur Hungaria, Ernő Rubik.

Gambar 2.1 Ernő Rubik Pada awalnya benda ini disebut sebagai “Magic Cube”. Puzzle ini dilisensikan oleh Ernő Rubik untuk dijual produsen Ideal Toys pada tahun 1980. Puzzle ini memenangkan penghargaan spesial yaitu German Game of the Year untuk kategori puzzle terbaik pada masa itu. Pada januari 2009, telah tercatat hampir 350 juta Rubik’s Cube diseluruh dunia dan membuat puzzle ini sebagai game puzzle dengan penjualan tertinggi. Dan otomatis menjadikan Rubik’s Cube sebagai puzzle terbaik di dunia.

Gambar 2.2 Prototipe dan Rubik pertama kali

Pada Rubik’s Cube klasik, setiap sisi tersusun atas sembilan persegi yang masing-masing persegi tersebut memiliki warna, yang mana warna yang menempel tersebut merupakan warna-warna solid (awalnya warna-warna tersebut yaitu putih, merah,

biru,

oranye,

hijau,

dan

kuning).

Dengan

adanya

mekanisme


pivotmemungkinkan tiap persegi untuk bergerak secara bebas, sehingga warna-warna yang ada bisa tercampur. Untuk menyelesaikan teka-teki, setiap sisi harus tersusun atas sembilan persegi dengan warna yang sama.

2.2.2 Mekanika Permainan Rubik’s Cube

Sebuah Rubik’scube standar memiliki sisi yang berukuran 5,7cm. Rubik’s Cube terdiri dari dua puluh enam kubus kubus kecil yang biasa disebut “cubies” atau “cubelets”. Masing-masing kubus terikat satu sama lainnya pada bagian dalam Rubik’s Cube. Yang memunginkan mereka untuk berpindah-pindah lokasi.

Namun kubuspusat dari setiap sisi tersebut, hanyalah sebuah kubus tunggal yang terikat dengan cubies pusat pada sisi lainnya. Kubus-kubus pusat ini melekat pada mekanisme inti dan membentuk suatu cross 3D. Kubus-kubus yang ada, dapat dilepaskan dengan mudah. Yaitu dengan cara memutar satu sisi dengan sudut 45o lalu cabut kubus salah satu kubus yang ada disudut. Hal ini biasa dilakukan untuk menyusun ulang Rubik’s Cube dengan cepat.

Gambar 2.3 Rubik’s Cube yang dibongkar

2.2.3 Aturan Permaianan Rubik’s Cube

Sampai saat ini, aturan permainan Rubik’s Cube masih belum berubah. Hal ini dikarenakan tujuan dari permainan ini sama dengan tujuan permainan puzzle lainnya


yaitu menyusun teka-teki yang telah diacak agar dapat kembali ke bentuk atau susunan semula.

Dalam permainan Rubik’s Cube, kondisi permasalahan telah selesai yaitu ketika setiap sisi telah tersusun atas warna yang sama. Untuk melakukannya yaitu dengan cara menggerakkan sisi-sisinya.

Gambar 2.4 Pergerakan Rubik’s Cube

2.3

Kecerdasan Buatan

Kecerdasan buatan merupakan salah satu bidang ilmu komputer yang didefinisikan sebagai kecerdasan yang dibuat untuk suatu sistem dengan menggunakan algoritmaalgoritma tertentu sehingga sistem tersebut seolah-olah dapat berpikir seperti manusia [2].

Kecerdasan buatan merupakan cabang dari ilmu komputer yang dalam merepresentasi pengetahuan, lebih banyak menggunakan bentuk simbol-simbol dari pada bilangan, dan memproses informasi berdasarkan metode heuristik atau dengan berdasarkan sejumlah aturan (Britannica Online Encyclopedia).

Dari beberapa pengertian di atas, maka dapat ditarik suatu kesimpulan bahwa kecerdasan buatan ialah salah satu bagian dari ilmu komputer yang mempelajari perancangan sistem komputer yang cerdas.Maksud dari sistem cerdas yaitu suatu sistem yang dapat memperlihatkan karakteristik yang ada pada tingkah laku manusia,


seperti mengerti suatu bahasa, mempelajari, mempertimbangkan, dan memecahkan suatu masalah.

Kecerdasan buatan telah memberikan suatu kemampuan baru kepada komputer untuk memecahkan masalah yang lebih besar dan lebih luas, tidak hanya terbatas pada soal-soal perhitungan, penyimpanan data, pengambilan data atau pengendalian yang sederhana saja.

2.3.1 Tujuan Akhir Kecerdasan Buatan

Menurut Lenat dan Feigenbaum [3], terdapat sembilan tujuan akhir dari kecerdasan buatan, yaitu: 1. Memahami pola pikir manusia, mencoba untuk mendapatkan pengetahuan ingatan manusia yang mendalam, kemampuan dalam memecahkan masalah, belajar, dan mengambil keputusan. 2. Otomatisasi, menciptakan sistem yang dapat menggantikan manusia dalam tugas-tugas intelegensi. Menggunakan sistem yang performanya sebaik manusia dalam melakukan pekerjaan. 3. Penguatan intelegensi, membangun sistem untuk membantu manusia agar mampu berpikir lebih baik dan lebih cepat. 4. Intelegensi manusia super, membangun sistem yang mempunyai kemampuan untuk melebihi intelegensi manusia. 5. Menyelesaikan permasalahan, sistem mampu menyelesaikan berbagai masalah yang luas. 6. Wacana

koheren,

mampu

berkomunikasi

dengan

manusia

dengan

menggunakan bahasa alami. 7. Belajar, mampu memperoleh data sendiri dan mengetahui bagaimana cara memperoleh data. Sistem mampu membuat hipotesis, penerapan atau pembelajaran secara heuristik dan membuat alasan dengan analogi. 8. Otonomi, mempunyai sistem intelegensi yang beraksi atas inisiatif sendiri. 9. Informasi, mampu menyimpan informasi dan mengetahui cara mengambil informasi.


2.4

Agen Cerdas

Agen adalah sesuatu yang dapat mengesan lingkungannya melalui sensors dan mengambil tindakan terhadap lingkungannya melalui actuators.Dengan adanya agen cerdas, maka diharapkan sistem mampu berpikir dan menentukan pilihan langkah yang tepat.

Gambar 2.5 Agen berinteraksi dengan lingkungan

Untuk setiap deretan persepsi yang mungkin, sebuah agen hendaklah memilih satu tindakan yang diharapkan memaksimalkan ukuran kemampuannya, dengan adanya bukti yang diberikan oleh deretan persepsi dan apapun pengetahuan terpasang yang dimiliki agen itu.Maka agen harus mampu melakukan atau memberi tindakan yang benar.Tindakan yang benar adalah tindakan yang menyebabkan agen mencapai tingkat yang paling berhasil [4].

2.4.1 Karakteristik Lingkungan Agen

Berikut adalah beberapa karakteristik lingkungan yang dikenal oleh agen: 1. Fully observable – partially observable Apabila sensor pada suatu agen dapat mengakses seluruh keadaan pada lingkungan, maka lingkungan itu dapat dikatakan fully observable terhadap


agen. Lebih efektif lagi lingkungan dikatakan fully observable jika sensor dapat mendeteksi seluruh aspek yang berhubungan dengan pilihan aksi yang akan dilakukan. Lingkungan yang fully observable biasanya sangat memudahkan, karena agen tidak perlu mengurus keadaan internal untuk terus melacak keadaan lingkungan.Suatu lingkungan bisa menjadi partially observable akibat ada gangguan dan ketidakakurasian sensor ataupun karena ada bagian keadaan yang hilang dari data sensor.Permainan Checker bersifat fully observable karena seluruh keadaan pada papan permainan dan bidakbidak yang ada semua dapat dipersepsi dengan baik. 2. Deterministic – stochastic Apabila keadaan lingkungan selanjutnya sepenuhnya bergantung pada keadaan sekarang dan juga tindakan yang akan dilakukan oleh agen, maka lingkungan tersebut bersifat deterministic. Sedangkan stochastic adalah kebalikan dari deterministic, dimana keadaan selanjutnya tidak bergantung pada keadaan sekarang dan juga tindakan yang akan dilakukan oleh agen. Apabila lingkungan bersifat deterministic terkecuali untuk tindakan dari agen, maka lingkungan

tersebut

bersifat

strategic.Permainan

Checker

bersifat

deterministic karena keadaan selanjutnya bergantung pada keadaan sekarang. 3. Episodic – sequential Untuk lingkungan yang bersifat episodic, pengalaman agen dibagi-bagi menjadi beberapa episode pendek. Tiap episode terdiri dari apa yang dirasakan agen dan kemudian melakukan satu tindakan tertentu. Kualitas dari tindakan agen hanya tergantung pada episode itu saja, karena tindakan selanjutnya tidak tergantung pada tindakan apa yang akan dilakukan di episode sebelumnya. Lingkungan episodic lebih sederhana karena agen tidak perlu memikirkan langkah-langkah pada keadaan selanjutnya.Sedangkan pada lingkungan sequential, tindakan saat sekarang dapat mempengaruhi tindakan selanjutnya. Permainan Checker bersifat sequential karena agen berpikir untuk langkahlangkah selanjutnya dan seluruh langkah yang akan diambil oleh agen saling bergantung. 4. Static – dynamic Apabila lingkungan dapat berubah saat agen sedang mengambil keputusan, maka

lingungan

tersebut

bersifat

dynamic,

sebaliknya

bersifat


static.Lingkungan yang bersifat static lebih mudah dihadapi karena agen tidak perlu memperhatikan lingkungannya saat dia sedang mengambil tindakan, maupun waktu yang terus berjalan.Apabila lingkungan tidak berubah seiring waktu berjalan, namun menyebabkan nilai kemampuan agen berubah-ubah, maka lingkungan tersebut bersifat semidynamic.Permainan Checker bersifat static karena saat agen mengambil tindakan, lingkungan tidak berubah dan juga tidak mempengaruhi nilai kemampuan agen. 5. Discrete – continuous Apabila kesan dan tindakan yang akan diterima dan dilakukan oleh agen telah ditetapkan dengan jelas, maka lingkungan tersebut bersifat discrete. Catur bersifat discrete, karena langkah yang akan diambil terbatas dan tertentu. Sedangkan pengendara taxi bersifat continuous, karena kecepatan dan lokasi pada taksi untuk suatu jangka tertentu mempunyai nilai yang terus-menerus berubah.Permainan Checker bersifat discrete karena seluruh kesan dan tindakan telah jelas ditetapkan sesuai dengan peraturan permainan. 6. Single agent – multiagent Agen pemecah permainan teka teki silang berada pada lingkungan yang bersifat single agent.Agen pemain catur berada pada lingkungan yang bersifat multiagent. Ada hal lain yang memberikan perbedaan lingkungan agen, yaitu akan hal apakah agen memberikan bantuan kepada agen lain atau apakah agen akan memaksimalkan kemampuannya bergantung pada prilaku agen lain. Permainan Checker bersifat multiagent karena memikirkan langkah yang akan diambil oleh lawan.

Dengan memahami karakteristik lingkungan pada agen cerdas yang akan dirancang, maka pembuatan agen cerdas dapat dilakukan dengan lebih baik.

2.5

Pohon Permainan

Pohon permainan merepresentasikan kepada kita kondisi-kondisi yang mungkin kita hadapi pada permainan dimulai dari kondisi yang sedang kita hadapi sekarang hingga beberapa kondisi ke depan. Sebuah pohon permainan merupakan representasi grafis


dari contoh permainan. Pohon permainan menyediakan informasi akan pemain, hasil, strategi, dan pilihan langkah.

Pohon permainan dapat direpresentasikan dengan baik pada permainan yang berbasis giliran (turn-based game). Pohon permainan memiliki root yang merupakan representasi dari kondisi dimana langkah belum diambil, nodes pada pohon yang merepresentasikan keadaan-keadaan yang mungkin diambil pada permainan, dan arcs yang merepresentasikan langkah.

Penggunaan pohon permainan pada permainan yang dimainkan oleh dua pemain direpresentasikan dengan cara bergantian. Untuk edges dari tingkat pertama ke tingkat kedua merepresentasikan langkah-langkah yang dapat diambil oleh pemain pertama,

sedangkan

untuk

edges

dari

tingkat

kedua

ke

tingkat

ketiga

merepresentasikan langkah-langkah yang dapat diambil oleh pemain kedua, dan begitu seterusnya.

Leaf nodes pada pohon permainan merepresentasikan keadaan akhir pada permainan, dimana permainan tersebut dimenangkan, dikalahkan ataupun seri.Pada permainan

yang

sederhana,

untuk

mencapai

leaf

nodes

mungkin

dapat

direpresentasikan, tetapi untuk permainan yang rumit seperti Checker, pencapaian leaf nodes sangat tidak dimungkinkan karena percabangan pada pohon permainan yang sangat besar.

Gambar 2.6 Contoh pohon permainan tic-tac-toe [2]


Berikut adalah penjelasan pohon permainan tic-tac-toe pada Gambar 2.6: 1. Terdapat root yang merupakan keadaan awal dimana permainan belum dimulai dan langkah belum diambil. 2. Edges yang menghubungkan tingkat pertama (root) dengan tingkat kedua merupakan langkah pemain pertama dan begitu seterusnya. Sehingga pohon permainan tersebut

merepresentasikan langkah kedua pemain

secara

bergantian. 3. Untuk nodes pada pohon tersebut merepresentasikan keadaan-keadaan yang dapat diambil oleh pemain yang akan melangkah. 4. Percabangan pertama yang dihasilkan adalah 9, kemudian untuk percabangan berikutnya adalah 8, dan begitu seterusnya hingga mencapai keadaan akhir (leaf nodes).

2.6

Algoritma Runut-Balik (Backtracking)

Istilah runut balik pertama kali diperkenalkan oleh D.H. Lehmer pada tahun 1950. Selanjutnya di tahun 1960, R. J. Walker, Golomb, dan Baumert menyajikan uraian umum tentang runut balik dan penerapannya pada berbagai persoalan[4].

Teknik runut balik (backtracking) merupakan salah satu teknik dalam penyelesaian masalah secara umum (General Problem Solving).Adapun dasar dari teknik ini adalah suatu teknik pencarian (Teknik Searching). Teknik pencarian ini digunakan dalam rangka mendapatkan himpunan penyelesaian yang mungkin. Dari himpunan penyelesaian yang mungkin ini akan diperoleh solusi optimal atau memuaskan.

Runut balik (backtracking) adalah algoritma yang berbasis pada Depth First Search (DFS) untuk mencari solusi persoalan secara lebih mangkus.Depth First Search (DFS) merupakan suatu cara pencarian dengan menelusuri node setiap level dari yang paling ke kiri menuju anak suatu node tersebut (level berikutnya). Berikut ini adalah contoh DFS untuk mencari simpul j :


a

b

e

c

f

d

h

g

i

j

Gambar 2.7 DFS untuk mencari simpul j

Runut balik, yang merupakan perbaikan dari algoritma brute-force, secara sistematis mencari solusi persoalan di antara semua kemungkinan solusi yang ada.Dengan metode runut balik, tidak perlu memeriksa semua kemungkinan solusi yang

ada.Hanya

pencarian

yang

mengarah

ke

solusi

saja

yang

selalu

dipertimbangkan.Akibatnya, waktu pencarian dapat dihemat.Saat ini algoritma runut balik banyak diterapkan untuk program games (seperti gametic-tac-toe, menemukan jalan keluar dalam sebuah labirin, catur, dll) dan masalah-masalah pada bidang kecerdasan buatan (artificial intelligence)[4].

Berikut ini adalah contoh penerapan algoritma backtracking pada persoalan NRatu (The N-Queens Problem).

Persoalan: Diberikan sebuah papan catur yang berukuran NxN dan empat buah ratu. Bagaimanakah menempatkan N buah ratu (Q) itu pada petak-petak papan catur sedemikian sehingga tidak ada dua ratu atau lebih yang terletak pada satu baris yang sama, atau pada satu kolom yang sama atau pada satu diagonal yang sama.

Solusi dari permasalahan tersebut adalah sebagai berikut: X = (x1,x2,x3,x4), dimana X merupakan vektor dan xi ∈ Si S = {1,2,3,4}, S menyatakan kolom pada papan catur.


Dari hal ini dapat dibentuk pohon ruang solusi persoalan 4-Ratu sebagai berikut: 1

2

x2=2

18

x2=3

3

x2=4

4

13

19

11

24

x3=3

x3=3

x3=4 x3=2 x3=4

9

x3=3

16

14

20

5

7

x4=2 10

29

12

x2=1

x2=4

x2=2

22

35

x3=2

x3=4

x3=4

x4=4 x4=3

x2=1

x3=1

25

27

x4=4

30

40

32

x4=2 15

17

x4=3

38

x4=4

x4=3

21

23

26

28

31

33

41

37

43

39

46

42

48

44

x3=1

52

x4=1

47

49

x3=3

54

x3=1 57

59

55

62

x4=1 58

x3=2 64

x4=2

x4=3 x4=2

53

61

x3=3

x4=3

x4=2 x4=1

56

x3=2 x3=2

x2=3

x2=2

51

x3=4

x4=4 x4=2

x4=1

x4=3

x3=1 x3=1

36

45

x3=4

x3=3

x4=3

x4=4

x4=4

x2=4

50

x1=1

8

6

34

x2=1

x3=2 x3=3

x1=4

x1=3

x1=2

x1=1

60

x4=1 63

Gambar 2.8 Pohon ruang kemungkinan solusi persoalan 4-Ratu

Dari gambar, dapat dilihat ruang seluruh solusi yang mungkin diterapkan pada persoalan 4-Ratu pada papan catur tersebut. Langkah-langkah solusi dengan menggunakan backtracking adalah berikut :

1. Menelusuri node dari akar sampai ke daun yang membentuk ruang solusi secara DFS. Penelusuran dilakukan dengan mempertimbangkan setiap batasan atau kriteria yang telah ditetapkan.

2. Apabila node yang dikunjungi memenuhi kriteria, maka akan dilakukan penulusuran menuju node berikutnya. Sebaliknya, apabila node yang dikunjungi tidak memenuhi kriteria, maka akan dilakukan backtracking menuju node yang berada di atas dan node tersebut sampai ke bawahnya tidak dipertimbangkan lagi.

3. Pencarian berhenti apabila ditemukan solusi atau tidak ada node hidup pada pohon tersebut.


65

Dari langkah-langkah tersebut, dapat dilihat contoh solusi dan pohon solusi persoalan 4-Ratu pada papan catur tersebut[4].

1

1

1

1

2

2

2 3

(a)

(b)

1

(c)

1

(d)

1

1

2

2

2

3

3 4 (e)

(f)

(g)

(h)

Gambar 2.9 Penelusuran Solusi Backtraking 4-Ratu pada papan catur

1

x1=1

x1=2

2

x2=2

18

x2=3

3

x2=1

x2=4

8

13

B x3=2

x2=3

19

24

B

B

x2=4

29

x3=3

x3=1

x3=2 x3=4

9

11

B

B

14

16

30

B x4=3

x4=3

15

31

B

Gambar 2.10 Pohon pencarian solusi dengan Backtraking pada persoalan 4Ratu


2.7

Penerapan Algoritma Runut-Balik pada permainan Magic-Square

Pada penelitian Nasution[6] dijelaskan penerapan algoritma backtracking sebagai kecerdasan buatan pada permainan Magic Square. Dalam penerapan algoritma Backtracking pada permainan Magic Square, ada beberapa properti yang perlu dipertimbangkan.Yaitu properti solusi persoalan, properti komponen vektor solusi dan properti kriteria pembatas.Berikut adalah penjabaran properti-properti tersebut.

1. Properti Solusi Persoalan Properti solusi persoalan merupakan properti yang berisikan simpul-simpul solusi dari persoalan. Pada permainan magic square ini, simpul-simpul persoalan merupakan kotak permainan yang tersedia pada papan matriks A, B, dan C. Kotak-kotak tersebut berisikan nilai dari 1-16. S = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16} 2. Properti Komponen Vektor Solusi Properti komponen vektor sulusi merupakan parameter yang digunakan untuk mengarahkan penelusuran simpul menuju ke arah solusi. Parameter ini terdiri atas m, dan k. m untuk menyatakan titik koordinat dari matriks B dan k menyatakan titik koordinat pada matriks A. Dimana m memiliki parameter untuk menentukan kolom dan baris yaitu x, dan y. x disini merupakan kolom dan y merupakan baris sehingga terjadi titik koordinat m(x,y). Begitu juga untuk parameter k, juga memiliki parameter untuk kolom dan baris yaitu i, dan j. Dimana I merupakan kolom dan j merupakan baris dan titik koordinat k(i,j).

3. Properti Kriteria Pembatas Properti kriteria pembatas merupakan properti yang berupa fungsi untuk menentukan apakah simpul-simpul mengarah ke solusi. Kriteria pembatas yang diterapkan pada algoritma Backtracking ini, mengacu pada strategi yang akan dipakai pada permainan magic square. Strategi tersebut adalah memindahkan semua nilai yang ada pada matriks B ke matriks A dengan mencari nilai yang tepat pada kriteria yang telah ditentukan sistem yaitu 34 sehingga terjadi urutan nilai yang acak.


Berikut ini adalah pseudocode penerapan algoritma runut balik (backtracking) pada permainan magic square.

procedure Backtrack(input n: integer) {mencari solusi persoalan versi iteratif; Masukan : n, yaitu panjang vektor solusi Keluaran : solusi x =(x[1],…, x[n]) } Deklarasi: k : integer Algoritma: k ←1 while k > 0 do if (x[k] belum dicoba sampai x[k]_T[(k)) and (B(x[1], x[2], ..., x[n]) = true) then if((x[1],x[2],...,x[k])adalah lintasan akar ke daun) then CetakSolusi(x) endif k ←k+1 else k ←k-1 endif endwhile {k=0}

Berikut ini adalah contoh kasus untuk penelusuran algoritma runut balik (backtracking) pada permainan magic square.

Matriks Matriks B

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

A Matriks C

Gambar 2.11 Matriks A Jalannya Solusi, Matriks B Sample, Matriks C Hasil dariSolusi Gambar.2.7 diatas merupakan gambar keadaan awal dari papan matriks A, matriks B, dan Matriks C. Berdasarkan gambar diatas, maka penelusuran pertama


berjalan dimulai dari m(1,1) yang nilainya 1 dan akan masuk ke k(1,1) jika nilai tersebut dapat memenuhi kriteria yang telah ditentukan sistem dan berlanjut penelusuran untuk k(1,2) dan nilai pada m(1,2) masih memenuhi kriteria maka akan dipindahkan sampai ke tingkat tertinggi sehingga untuk nilai k(1,3) = m(4,3) dan k(1,4) = m(4,4). Penelusuran yang terjadi sebenarnya masih mencari nilai horizontal saja sebagai contoh untuk penelusuran vertical dan penelusuran diagonal karena kedua penelusuran ini memiliki sifat menunggu dari penelusuran horizontal.Berikut gambar 2.8 menunjukkan penelusuran horizontal.

Penelusuran Horizontal 34 m=1

1

m=8 m=1

m=1

12

m=1+2 m=12+14

2

13

8

m=13+7

14

m=8+1

7

11 m=8+11+6

m=1+2+1 m=12+14+3m=13+7+10

15 m=1+2+15+1

3

10

6

m=12+14+3+ m=13+7+10+

16

5

4

m=8+11+6+

9

Gambar 2.12 Pohon Ruang Status Terhadap Nilai Horizontal

Pada penelusuran selanjutnya untuk mendapatkan nilai k(2,1), maka yang berjalan disini adalah penelusuran horizontal dan penelusuran vertikal untuk mendapatkan nilai maksimal sehingga didapat nilai dari matriks B adalah m(3,4).

Penelusuran Vertikal 34 m=1

m=16 m=2

1 m=1+1 m=2+14

2

m=15

15 m=15+3

16


m=16+5

Gambar 2.13 Pohon Ruang Status Terhadap Nilai Vertikal

Untuk penelusuran pada k(2,2) yang berjalan adalah penelusuran horizontal, penelusuran vertikal, yang dapat dilihat pada gambar 2.8 dan gambar 2.9 di atas, dan penelusuran diagonal yang ditunjukkan pada gambar 2.10 di bawah ini.

Penelusuran Diagnoal

34 m=1

1

m=16

16

m=1+14

14

m=16+3

3 m=16+3+7

m=1+14+10

10

7

m=1+14+10+9

9

m=16+3+7+8

8

Gambar 2.14 Pohon Ruang Status Terhadap Nilai Diagonal 2.8 Penerapan Algoritma Runut-Balik dalam Teka-teki Sudoku


Algoritma backtracking juga dapat diterapkan dalam permainan teka-teki Sudoku. Seperti pada Mochtar[8].

Sudoku dapat diselesaikan dengan kombinasi teknik pemindaian (scanning), penandaan (marking), dan analisa (analysing). Beberapa teka-teki Sudoku yang tergolong mudah dapat diselesaikan hanya dengan salah satu proses, namun pada umumnya kita harus mengkombinasikan ketiga teknik tersebut.

a. Pemindaian Berupa proses memindai baris atau kolom untuk mengindentifikasi baris mana dalam suatu blok yang terdapat angka-angka tertentu. Proses ini kemudian diulang pada setiap kolom (atau baris) secara sistematis. Kemudian menentukan nilai dari suatu sel dengan membuang nilai-nilai yang tidak mungkin.

b. Penandaan Berupa analisa logika, dengan menandai kandidat angka yang dapat dimasukkan dalam sebuah sel.

c. Analisa Berupa eliminasi kandidat, dimana kemajuan dicapai dengan mengeliminasi kandidat angka secara berturut-turut hingga sebuah sel hanya punya 1 kandidat.

2.8.1 Komputasi dalam Teka-teki Sudoku

Penyelesaian teka-teki Sudoku n² × n² adalah permasalahan NP-complete.Pada dasarnya, Sudoku dapat diselesaikan oleh algoritma traversal graf dengan membangun seluruh pohon kemungkinan.Penyelesaian Sudoku juga dapat dipandang sebagai masalah pewarnaan graf yaitu mewarnai graf dengan simpul n² × n², dimana warna yang digunakan direpresentasikan dalam angka 1- 9, yang seluruhnya harus digunakan.


Algoritma runut balik sangat efektif dalam mengurangi jumlah pencarian kemungkinan

solusi

teka-teki.Menurut

perhitungan

ada

sebanyak

6,670,903,752,021,072,936,960 jumlah kemungkinan status untuk teka-teki Sudoku berukuran 9 x 9.Suatu angka yang sangat besar jika ingin dicari secara brute-force, dengan kompleksitas.Garis besar algoritma runut-balik untuk menyelesaikan teka-teki diberikan di bawah ini: Deklarasi Global N : integer {adalah ukuran papan sudoku } tabel : array[1.. N2] of array[1..N2] {representasi papan sudoku} procedure solve() { menyelesaikan teka-teki Sudoku pada papan n2 * n2, versi: rekursif } Algoritma if( isDone() ) then exit() {papan sudah selesai diisi program selesai} else updateTabel() {update sel tabel yang masih kosong}

if( not isValidBaris() ) then backtrack() else {jika baris valid maka periksa kolom} if( not isValidKolom()) then backtrack() else {jika kolom valid maka periksa blok} if ( not isValidBlok()) then backtrack() else {jika blok valid maka panggil rekursif} solve()


BAB 2 TINJAUAN PUSTAKA

Recommend Documents