BAB 2 LANDASAN TEORI

BAB 2 LANDASAN TEORI

2.1

Algoritma Algoritma adalah jantung dari ilmu computer. Banyak cabang dari ilmu

komputer yang masuk dalam terminologi algoritma. Jangan beranggapan bahwa algoritma selalu identik dengan ilmu komputer saja, karena dalam kehidupan sehari-hari banyak terdapat proses yang dinyatakan dalam suatu algoritma. Sebagai contoh, caracara membuat kue atau masakan yang dinyatakan dalam suatu resep juga dapat disebut sebagai algoritma. Pada setiap resep selalu ada urutan langkah-langkah membuat masakan. Bila langkah - langkah yang dilakukan tidak logis maka tidak akan dihasilkan masakan yang diinginkan. Ibu - ibu yang mencoba suatu resep masakan akan membaca satu per satu langkah - langkah pembuatannya lalu mengerjakan proses sesuai yang dibaca. Secara umum, pihak (benda) yang mengerjakan proses disebut pemroses (processor). Pemroses tersebut dapat berupa manusia, komputer, robot atau alat-alat elektronik lainnya. Pemroses melakukan suatu proses dengan melaksanakan atau “mengeksekusi” algoritma yang menjabarkan proses tersebut. (Alex Budianto, 2003) Melaksanakan Algoritma berarti mengerjakan langkah-langkah di dalam Algoritma tersebut. Pemroses mengerjakan proses sesuai dengan algoritma yang diberikan kepadanya. Juru masak membuat kue berdasarkan resep yang diberikan kepadanya, pianis memainkan lagu berdasarkan papan not balok. Oleh karena itu, suatu Algoritma harus dinyatakan dalam bentuk yang dapat dimengerti oleh pemroses. Jadi suatu pemroses harus : 6

7

•

Mengerti setiap langkah dalam Algoritma

•

Mengerjakan operasi yang sesuaian dengan langkah tersebut.

2.1.1

Sejarah Algoritma Asal usul kata Algoritma mempunyai sejarah yang aneh. Pada awalnya orang-

orang hanya menemukan kata Algorism yang berarti proses menghitung dengan menggunakan angka arab. Seseorang dikatakan Algorist jika anda menghitung menggunakan Angka Arab. Para ahli bahasa terus berusaha menemukan asal kata tersebut tetapi hasilnya kurang memuaskan. Akhirnya para ahli sejarah matematika menemukan asal kata tersebut, rupanya kata Algoritma berasal dari nama seorang ahli matematika dari Uzbekistan yang hidup di masa tahun 770-840 masehi yaitu Abu Ja’far Muhammad Ibnu Musa Al-Khuwarizmi. Kata “Al-Khuwarizmi” dibaca oleh orang barat menjadi Algorism. Al-Khuwarizmi menulis buku yang berjudul Kitab Al Jabar WalMuqabala yang memiliki arti “Buku pemugaran dan pengurangan”. Dari judul buku ini kita juga memperoleh asal usul kata “Aljabar” (Algebra). Perubahan kata dari Algorism menjadi Algorithm muncul karena kata Algorism sering di kelirukan dengan Arithmetic, sehingga akhiran –sm berubah menjadi –thm. Karena perhitungan dengan menggunakan angka arab sudah menjadi hal yang biasa. Maka kata Algoritm berangsur-angsur dipakai sebagai metode perhitungan (komputasi) secara umu, sehingga kehilangan makna kata aslinya. Dalam Bahasa Indonesia, kata Algorithm diserap menjadi Algoritma. (Alex Budianto, 2003)

8

2.1.2

Definisi Algoritma Definisi dari Algoritma adalah “Urutan langkah-langkah logis penyelesaian

masalah dalam bentuk kalimat dengan jumlah kata terbatas, tetapi disusun secara sistematis dan logis”. (Alex Budianto, 2003)

2.1.3

Ciri – Ciri Algoritma Algoritma memiliki beberapa ciri, antara lain:

a.

Mempunyai awal dan akhir Setiap algoritma memiliki tahap-tahap di mana algoritma akan mulai dan tahap algoritma akan berakhir.

b.

Setiap langkah didefinisikan dengan tepat Setiap langkah dalam suatu metode algoritma harus didefinisiskan dengan tepat agar tidak terjadi kerancuan atau kesalahan saat algoritma tersebut dijalankan.

c.

Memiliki masukkan (input) Algoritma dalam menyelesaikan suatu masalah harus memiliki variabel-variabel tertentu yang dijadikan masukkan untuk menyelesaikan suatu masalah. Contoh : dalam algoritma perhitungan luas persegi panjang terdapat dua variabel masukkan yaitu panjang dan lebar.

d.

Memiliki keluaran (output) Algoritma jika sudah selesai dijalankan harus menghasilkan suatu hasil yang merupakan solusi dalam permasalahan yang diselesaikan dalam algoritma tersebut. Contoh : dalam algoritma perhitungan luas persegi panjang, suatu algoritma akan mengeluarkan output berupa luas persegi panjang.

9

e.

Harus efektif (bisa menyelesaikan persoalan) Suatu algoritma harus dapat menyelesaikan persoalan yang ada, untuk tujuan tersebutlah suatu algoritma dibangun. Contoh : dalam algoritma perhitungan luas persegi panjang, maka suatu algoritma harus dapat menyelesaikan perhitungan luas suatu persegi panjang.

2.1.4

Sifat Algoritma Sifat-sifat dari algoritma adalah:

a.

Input Sifat ini berarti, suatu algoritma memiliki kondisi awal sebelum dilaksanakan.

b.

Output Sifat ini berarti, suatu algoritma menghasilkan keluaran setelah dilaksanaan.

c.

Definitif Sifat ini berarti, langkah-langkah dari suatu algoritma terdefinisi dengan jelas.

d.

Finit Sifat ini berarti, suatu algoritma melakukan langkah yang terbatas jumlahnya dalam mengolah input menjadi output.

e.

Efektif Sifat ini berarti, suatu algoritma dapat memberi solusi sesuai harapan.

f.

General Sifat ini berarti, suatu algoritma berlaku untuk setiap himpunan input.

10

2.1.5

Struktur Algoritma Setiap Algoritma akan selalu terdiri dari tiga bagian yaitu:

•

Judul (Header)

•

Kamus

•

Algoritma Pada setiap bagian tersebut apabila akan dituliskan komentar mengenai setiap

bagian tersebut dituliskan di antara tanda kurung kurawal, contoh { Komentar }. Notasi algoritma yang dituliskan di antara tanda ini tidak akan dieksekusi oleh program. Contoh : Judul { Komentar mengenai Algoritma seperti cara kerja program, Kondisi awal dan kondisi akhir dari algoritma } Kamus { Pada bagian ini, didefinisikan nama konstanta, nama variable, nama prosedur dan nama fungsi } Algoritma { Pada bagian ini algoritma dituliskan. Semua teks yang ditulis tidak diantara

tanda

kurung

kurawa

akan

dianggap

sebagai notasi algoritma yang algoritma }

akan

berpengaruh

terhadap

kebenaran

11

2.1.5.1 Judul (Header) Judul adalah bagian teks algoritma yang digunakan sebagai tempat mendefinisikan nama dengan menentukan apakah teks tersebut adalah program, prosedur, fungsi. Setelah judul disarankan untuk menuliskan spesifikasi singkat dari teks algoritma tersebut. Nama algoritma sebaiknya singkat namun cukup menggambarkan apa yang akan dilakukan oleh algoritma tersebut.

Contoh : Program Luas_Kubus

{ Judul Algoritma }

{ Menghitung luas kubus untuk ukuran sisi yang dibaca dari piranti masukan lalu mencetak hasil ke piranti keluaran }

{ Spesifikasi Algoritma}

Catatan : Untuk memisahkan antara kata dalam judul algoritma menggunakan tanda “_” bukanlah suatu keharusan. Anda dapat menuliskan LuasLingkaran atau Luas_Lingkaran. Tetapi sebaiknya anda tidak menggunakan spasi “ “ untuk memisahkan antara kata di dalam nama algoritma.

12

2.1.5.2 Kamus (Deklarasi) Kamus adalah bagian teks algoritma sebagai tempat untuk mendefinisiskan : •

Nama type

•

Nama konstanta

•

Nama variable

•

Nama fungsi

•

Nama prosedur Semua nama tersebut baru dapat dipakai di dalam algoritma jika telah

didefinisiskan terlebih dahulu di dalam kamus. Penulisan sekumpulan nama dalam kamus sebaiknya dikelompokan menurut jenis nama tersebut. Nama variable belum terdefinisi nilainya ketika didefinisikan. Pendefinisian nama konstanta sekaligus memberi harga konstanta tersebut, pendefinisian nama fungsi dilakukan sekaligus dengan domain / range serta spesifikasinya. Pendefinisian nama prosedur sekaligus dengan pendefinisian parameter (jika ada) dan spesifikasi prosedur (kondisi awal “Initial State”, kondisi akhir “Final State” dan proses yang dilakukan).

Contoh : Kamus {Nama type, hanya untuk type yang bukan type dasar} type jam : {Type jam terdiri dari 3 masukan yaitu “hh” sebagai jam, “mm” sebagai menit dan “ss” sebagai detik}

{Nama konstanta, harus menyebutkan type dan nilai}

13 constant phi : real = 3,14159 constant nama : string = ‘Alex’ constant

benar : boolean = true

{Nama Informasi, menyebutkan type} x,y : integer {suatu nilai yang bertype bilangan bulat} NMax : real {nilai maksimal yang bertype bilangan real} Nana : string P : point

{nilai yang merupakan kumpulan karakter}

{nilai pada bilangan kartesian}

Cari : Boolean

{suatu nilai logika}

{Nama fungsi, menyebutkan domain dan range} function RealToInt (x:real)

integer

{mengubah harga x yang bertype real menjadi harga ekivalen yang bertype integer}

{Nama prosedur, menyebutkan “IS” initial state, “FS” final state dan proses} procedure tukar (input/output x,y : real) { IS x dan y terdefinisi, x = a dan y = b FS x = b dan y = a Proses : menukar isi informasi bilangan x dan y}

14

2.1.5.3 Algoritma (Deskripsi) Algoritma adalah bagian inti dari suatu algoritma yang berisi instruksi atau pemanggilan aksi yang telah didefinisikan. Komponen teks algoritma dalam pemrograman procedural dapat berupa : •

Instruksi dasar seperti input/output, assignment

•

Sequence (runtutan)

•

Analisa kasus

•

Perulangan Setiap langkah algoritma dibaca dari “atas” ke “bawah”. Urutan deskripsi

penulisan menentukan urutan langkah pelaksanaan perintah.

Contoh : Algoritma input (c,d)

{menerima masukan 2 bilangan c

dan d} if c < d then e Å a + b

{operasi kondisional} {e di assignment oleh nilai a

dan b} else e Å a – b output (e) e}

{hasil keluaran berupa bilangan

15

2.1.6

Contoh Algoritma Mencetak String “Selamat Belajar Algoritma dan Pemrograman” ke piranti

Keluaran. Program Cetak_string {mencetak

string

“Selamat

Belajar

Algoritma

dan

Pemrograman” ke piranti keluaran} Kamus {tidak ada} Algoritma Output (‘Selamat Belajar Algoritma dan Pemrograman’)

Menentukan nilai terbesar dari bilangan bulat yang dibaca dari piranti masukan dan menuliskan hasilnya ke piranti keluaran. Program Nilai_Maksimal {Menentukan nilai tertinggi yang dibaca dari piranti masukan dan hasilnya dicetak ke piranti keluaran} Kamus hasil,x,y : integer {hasil merupakan variable untuk menampung nilai keluaran} {x,y

adalah

variable

untuk

menampung nilai masukan} Algoritma input(x,y)

{membaca nilai x dan y dari piranti masukan}

if

x < y then

{operasi kondisional}

16 hasil

Å

x

{hasil

di

assignment

oleh

nilai

terbesar} else hasil Å y output (hasil)

{nilai didalam variable hasil dicetak ke piranti keluaran}

2.2

Artificial Intelligent Dewasa ini, banyak orang tertarik kepada hal – hal yang berhubungan dengan

Artificial Intelligence ( AI ), tetapi banyak yang tidak dapat menjelaskan dengan pasti apa itu AI. Menurut Kusumadewi ( 2003, p1 ), AI adalah salah satu bagian ilmu komputer yang membuat agar komputer dapat melakukan pekerjaan seperti dan sebaik yang dilakukan oleh manusia. Pada awal diciptakannya, komputer hanya dipakai sebagai alat hitung saja. Namun, seiring dengan perkembangan zaman maka peran komputer semakin mendominasi kehidupan umat manusia. Manusia bisa menjadi pandai dalam menyelesaikan segala permasalahan di dunia ini karena manusia mempunyai pengetahuan dan pengalaman. Pengetahuan diperoleh dari belajar. Semakin banyak bekal pengetahuan yang dimiliki oleh seseorang tentu saja diharapkan akan lebih mampu dalam menyelesaikan permasalahan. Agar komputer bisa bertindak seperti dan sebaik manusia maka komputer juga harus diberi bekal pengetahuan dan mempunyai kemampuan untuk menalar. Untuk itu pada AI, akan mencoba untuk memberikan beberapa metode untuk membekali komputer dengan kedua komponen tersebut agar komputer bisa menjadi benda yang pintar.

17

Lebih detilnya, pengertian AI dapat dipandang dari berbagai sudut pandang, antara lain : 1.

Sudut pandang kecerdasan AI akan membuat komputer menjadi cerdas dan mampu berbuat seperti apa yang dilakukan oleh manusia.

2.

Sudut pandang penelitian AI adalah suatu studi bagaimana membuat agar komputer dapat melakukan sesuatu sebaik yang dikerjakan oleh manusia.

3.

Sudut pandang bisnis AI adalah kumpulan peralatan yang sangat powerful dan metodologis dalam menyelesaikan masalah – masalah bisnis.

4.

Sudut pandang pemrograman AI meliputi studi tentang pemrograman simbolik, problem solving, dan searching.

2.2.1. Sejarah Artificial Intelligent Program AI pertama yang bekerja ditulis pada 1951 untuk menjalankan mesin Ferranti Mark I di University of Manchester (UK): sebuah program permainan naskah yang ditulis oleh Christopher Strachey dan program permainan catur yang ditulis oleh Dietrich Prinz. John McCarthy membuat istilah "kecerdasan buatan" pada konferensi pertama yang disediakan untuk pokok persoalan ini, pada 1956. John McCarthy juga menemukan bahasa pemrograman Lisp. Alan Turing memperkenalkan "Turing test" sebagai sebuah cara untuk mengoperasionalkan test perilaku cerdas. Joseph Weizenbaum membangun ELIZA, chatterbot yang menerapkan psikoterapi Rogerian.

18

Selama tahun 1960-an dan 1970-an, Joel Moses mendemonstrasikan kekuatan pertimbangan simbolis untuk mengintegrasikan masalah di dalam program Macsyma, program berbasis pengetahuan yang sukses pertama kali dalam bidang matematika. Marvin Minsky dan Seymour Papert menerbitkan Perceptrons, yang mendemostrasikan batas jaringan syaraf sederhana dan Alain Colmerauer mengembangkan bahasa komputer Prolog. Ted Shortliffe mendemonstrasikan kekuatan sistem berbasis aturan untuk representasi pengetahuan dan inferensi dalam diagnosa serta terapi medis yang kadangkala disebut sebagai sistem pakar pertama. Hans Moravec mengembangkan kendaraan terkendali komputer pertama untuk mengatasi jalan berlintang yang kusut secara mandiri. Pada tahun 1980-an, jaringan syaraf digunakan secara meluas dengan algoritma perambatan balik, pertama kali diterangkan oleh Paul John Werbos pada 1974. Tahun 1990-an ditandai perolehan besar dalam berbagai bidang AI dan demonstrasi berbagai macam aplikasi. Lebih khusus Deep Blue, sebuah komputer permainan catur, mengalahkan Garry Kasparov dalam sebuah pertandingan enam game yang terkenal pada tahun 1997. DARPA menyatakan bahwa biaya yang di simpan melalui penerapan metode AI untuk unit penjadwalan dalam Perang Teluk pertama telah mengganti seluruh investasi dalam penelitian AI sejak tahun 1950 pada pemerintah AS. Tantangan Hebat DARPA, yang dimulai pada 2004 dan berlanjut hingga hari ini, adalah sebuah pacuan untuk hadiah dua juta dolar di mana kendaraan dikemudikan sendiri tanpa komunikasi dengan manusia, menggunakan GPS, komputer dan susunan sensor yang canggih, melintasi beberapa ratus mil daerah gurun yang menantang.

19

2.2.2. Definisi Artificial Intelligent •

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

•

Menurut 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.”

•

Menurut 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.”

Tujuan dari kecerdasan buatan menurut Winston dan Prendergast (1984): 1.

Membuat mesin menjadi lebih pintar (tujuan utama)

2.

Memahami apa itu kecerdasan (tujuan ilmiah)

3.

Membuat mesin lebih bermanfaat (tujuan entrepreneurial)

20

AI dapat dipandang dalam berbagai perspektif. a.

Menurut perspektif Kecerdasan (Intelligent) AI adalah bagaimana membuat mesin yang “cerdas” dan dapat melakukan halhal yang sebelumnya dapat di lakukan oleh manusia.

b.

Menurut perspektif bisnis AI adalah sekelompok alat bantu (tools) yang berdaya guna, dan metodologi yang menggunakan tool-tool tersebut guna menyelesaikan masalah-masalah bisnis.

c.

Dari perspektif pemrograman (Programming) AI termasuk di dalamnya adalah studi tentang pemrograman simbolik, pemecahan masalah, proses pencarian (search).

2.2.3. Kecerdasan Buatan vs Kecerdasan Alamiah Keuntungan Kecerdasan Buatan dibanding kecerdasan alamiah: a.

Lebih permanen Kecerdasan buatan lebih bersifat permanent disbanding kecerdasan alami karena sifat manusia yang semakin berkurang kemampuannya sejalan dengan perubahan umur.

b.

Memberikan kemudahan dalam duplikasi dan penyebaran Kecerdasan buatan dapat dengan mudah dan cepat untuk di duplikasi sedangkan untuk menduplikasi kecerdasan alami otak manusia sangat sulit dan membutuhkan waktu yang lama (untuk belajar).

21

c.

Relatif lebih murah dari kecerdasan alamiah Sampai saat ini belum ada yang dapat menciptakan otak manusia sehingga kecerdasan alami merupakan sesuatu yang sangat mahal.

d.

Lebih Konsisten dan teliti Hal ini disebabkan karena adanya sifat lupa yang dimiliki oleh kecerdasan alami.

e.

Dapat didokumentasi Keputusan yang dibuat oleh komputer dapat didokumentasi dengan mudah dengan cara melacak setiap aktivitas dari sistem tersebut.

Keuntungan Kecerdasan Alamiah dibanding kecerdasan buatan a.

Bersifat lebih kreatif Kemampuan otak manusia untuk menambah atau memenuhi pengetahuan sangat melekat pada jiwa manusia, sedangkan pada kecerdasan buatan untuk menambah pengetahuan diperlukan melalui sistem yang dibangun.

b.

Dapat melakukan proses pembelajaran secara langsung, sementara AI harus mendapatkan masukan berupa simbol dan representasi-representasi

22

Tabel 2.1 Perbedaan antara mikroprosesor dengan otak manusia 2.2.4. Bidang-bidang AI a.

Expert System Expert System adalah program komputer yang didesain untuk berlaku sebagai seorang ahli dalam suatu bidang khusus. Namun sekarang Expert System ‘hanya’ digunakan untuk membantu para ahli dalam memecahkan suatu masalah. Bahkan banyak orang yang tidak percaya bahwa Expert System dapat menggantikan para ahli, karena harus sedemikian banyaknya pengetahuan yang harus di miliki oleh Expert System.

b.

Natural Language Processing (NLP) NLP di maksudkan untuk mengenal makna dari bentuk kalimat yang berbedabeda. Selain mampu mengerti bahasa sehari-hari, NLP juga mencakup kemampuan membentuk kalimat dalam bahasa sehari-hari.

23

c.

Recognition Contohnya adalah Speech Recognition. Dengan ini suatu komputer dapat mengenali suara kita, dan sekaligus bisa membedakan berbagai macam bentuk sinyal. Contoh yang lain adalah Character Recognition. Dengan ini suatu komputer dapat mengenali karakter, dan sekaligus bisa membedakan berbagai macam bentuk karakter.

d.

Computer Vision Ilmu pengetahuan dan teknologi mesin yang dapat melihat. Di mana Computer Vision terkait dengan teori untuk membangun suatu sistem yang terdiri dari gambar. Contoh yang sering digunakan adalah untuk mendeteksi plat nomor kendaraan.

e.

Robotic Robot adalah mesin yang dapat di program untuk melaksanakan tugas-tugas mekanik. Robot yang berintelegensi dapat memberi respon terhadap perubahan lingkungan.

f.

Intelligent Computer Assisted Instruction Komputer dimaksudkan untuk membantu dalam pendidikan, sehingga dapat mengajar dengan cara sesuai keadaan pelajar.

g.

Automatic Programming Komputer dapat membuat program sendiri sesuai dengan spesifikasi yang di inginkan oleh programmer.

24

h.

Planning and Decision Support Komputer ini khusus membantu manager secara aktif dalam perencanaan dan pengambilan keputusan.

2.3

Soft Computing Menurut Prof. Lotfi A. Zadeh Soft Computing adalah koleksi dari beberapa

metodologi yang bertujuan untuk mengeksploitasi adanya toleransi terhadap ketidaktepatan, ketidakpastian, dan kebenaran parsial untuk dapat di selesaikan dengan mudah, robustness, dan biaya penyelesaian yang murah Soft computing merupakan inovasi baru dalam membangun sistem cerdas. Sistem cerdas merupakan sistem yang memiliki keahlian seperti manusia pada domain tertentu, mampu beradaptasi dan belajar agar dapat bekerja lebih baik jika terjadi perubahan lingkungan.

Unsur pokok dalam Soft Computing yaitu : •

Jaringan Syaraf/ Neural Network (menggunakan pembelajaran)

•

Probabilistic Reasoning (mengakomodasi ketidakpastian)

•

Evolutionary Computing / Genetic Algorithm (optimasi)

•

Sistem Fuzzy (mengakomodasi ketidaktepatan)

Karakteristik dari Soft Computing yaitu : •

Soft Computing memerlukan keahlian manusia, apabila direpresentasikan dalam bentuk aturan (IF - THEN).

•

Model komputasinya diilhami oleh proses biologis.

25

•

Soft Computing merupakan Teknik optimasi baru.

•

Soft Computing menggunakan komputasi numeris.

•

Soft Computing memiliki toleransi kegagalan (meskipun kualitasnya berangsurangsur memburuk).

2.4

Data Data adalah bentuk jamak dari datum, berasal dari bahasa Latin yang berarti

"sesuatu yang diberikan". Dalam penggunaan sehari-hari data berarti suatu pernyataan yang di terima secara apa adanya. Pernyataan ini adalah hasil pengukuran atau pengamatan suatu variabel yang bentuknya dapat berupa angka, kata-kata, atau citra. Sedangkan menurut Departemen Pertahanan Republik Indonesia pengertian data adalah fakta atau kenyataan yang secara simbolis dapat dinyatakan sesuai lingkup perhatian suatu aplikasi, dapat di simpan atau di rekam. (www.total.or.id)

2.5

Informasi Informasi adalah hasil pemrosesan, manipulasi dan pengorganisasian/penataan

dari sekelompok data yang mempunyai nilai pengetahuan (knowledge) bagi penggunanya. Namun demikian istilah ini memiliki banyak arti bergantung pada konteksnya, dan secara umum berhubungan erat dengan konsep seperti arti, pengetahuan, negentropy, komunikasi, kebenaran, representasi, dan rangsangan mental. (www.total.or.id)

26

2.6

Database Basis data (bahasa Inggris: database), atau sering pula di sebut basisdata,

adalah kumpulan informasi yang di simpan dalam komputer secara sistematik sehingga dapat di periksa menggunakan suatu program komputer untuk memperoleh informasi dari basis data tersebut (www.total.or.id). Perangkat lunak yang digunakan untuk mengelola dan memanggil kueri (query) basis data disebut sistem manajemen basis data (database management system, DBMS). Sistem basis data di pelajari dalam ilmu informasi. Istilah "basis data" berawal dari ilmu komputer. Meskipun kemudian artinya semakin luas, memasukkan hal-hal di luar bidang elektronika, artikel ini mengenai basis data komputer. Catatan yang mirip dengan basis data sebenarnya sudah ada sebelum revolusi industri yaitu dalam bentuk buku besar, kwitansi dan kumpulan data yang berhubungan dengan bisnis. Konsep dasar dari basis data adalah kumpulan dari catatan-catatan, atau potongan dari pengetahuan. Sebuah basis data memiliki penjelasan terstruktur dari jenis fakta

yang

tersimpan

di

dalamnya:

penjelasan

ini

disebut

skema.

Skema

menggambarkan obyek yang di wakili suatu basis data, dan hubungan di antara obyek tersebut. Ada banyak cara untuk mengorganisasi skema, atau memodelkan struktur basis data: ini di kenal sebagai model basis data atau model data. Model yang umum digunakan sekarang adalah model relasional, yang menurut istilah Layman mewakili semua informasi dalam bentuk tabel-tabel yang saling berhubungan di mana setiap tabel terdiri dari baris dan kolom (definisi yang sebenarnya menggunakan terminologi matematika). Dalam model ini, hubungan antar tabel di wakili dengan menggunakan

27

nilai yang sama antar tabel. Model yang lain seperti model hierarki dan model jaringan menggunakan cara yang lebih eksplisit untuk mewakili hubungan antar tabel. Istilah basis data mengacu pada koleksi dari data-data yang saling berhubungan, dan perangkat lunaknya seharusnya mengacu sebagai sistem manajemen basis data (database management system/DBMS). Jika konteksnya sudah jelas, banyak administrator dan programer menggunakan istilah basis data untuk kedua arti tersebut.

2.7

State Transition Diagram ( STD ) State Transition Diagram ( STD ) merupakan model yang menggambarkan sifat

ketergantungan pada waktu dari suatu sistem. STD terdiri dari simbol kotak dan simbol panah. Masing – masing anak panah menggambarkan perubahan atau transisi yang disertai dengan keterangan seperti if condition then statement. Keterangan pada anak panah tersebut dibagi menjadi dua buah kalimat. Kalimat pada bagian atas adalah kondisi dan kalimat pada bagian bawah adalah statement jika kondisi dipenuhi. (http://www.nikhef.nl/~p63/www/STD.html)

Tabel 3.1 Tabel Notasi STD

28

2.8

Gambaran Umum Checker Permainan Checker adalah game yang paling tua di dunia dan kembali diatas

4000 tahun. Menurut catatan di kuil Thebes, makam raja mesir membutuhkan waktu keluar dari bangunan Pyramid untuk menyelesaikan para orang istana pada checkers. (The American Checker Federation, 2007, p1) Homer's Odyssey, membuat referensi untuk game dan dimainkan di istana dari Ulysses dalam Ithaca; Plato juga membuat sebutan yang sering digunakan dari game didalam tulisannya. Buku checker paling awal telah diterbitkan oleh Antonio Torquemada, seorang pengarang Spanyol pada Valencia, Spanyol, pada tahun 1547. Pada Checker Amerika papan permainan adalah 8x8, dengan 12 pion pada masing-masing sisi dimana untuk membedakan kedua kubuh pion ini dibedakan dengan dua warna dasar yaitu merah dan putih. Permainan hanya dilakukan pada papan berwarnah hitam. Pion yang sampai ujung papan akan menjadi raja dan mendapatkan kelebihan yaitu dapat melangkah mundur dalam permainan. Pada awal permainan yang boleh bergerak hanya bagian atas pion saja yang boleh melangkah (tidak boleh melewati pion teman sendiri). Checkers yang papannya berukuran 8x8 dimainkan pada Negara Inggris (yang dikenal dengan draughts), USA, Kanada, Autralis, Irlandia, Spanyol, Itali dan sedikit negara lainnya. Dan Checker yang popular dengan papan berukuran 10x10 dimainkan pada negara Eropa Timur, USA, yang terkadang dipanggil Polish Checkers. Pada tempat lain disebut dengan International Draughts.

29

2.8.1. Sejarah Checker Draughts(Checkers) Suatu permainan primitif yang membutuhkan papan dengan cara bermain melompat dan menangkap telah ada dari empat puluh abad yang lalu.(Arie Van Der Stoep, p1) Orang Afrika memindahkan batu atau kulit diatas garis-garis yang telah digambar diatas pasir. Seperti halnya Checkers, mereka mengambil suatu potongan dengan cara melompatinya. Permainan ini diberi nama Draughts. Draughts muncul antara tahun 2000 sampai 1500 sebelum masehi. Permainan ini dimainkan diatas papan dengan jumlah titik sebnyak 25 dimana 24 titik diisi oleh potongan bidak pemain dan satu tutuk ditengah dibiarkan kosong, dua pemain masing-masing memulai dengan 12 potongan. Untuk lebih jelas lihat gambar dibawah.

Gambar 2.1 Papan ini telah diukir ke dalam mengatapi papan dari kuil dari Luxor, yang dibangun dengan diamdiam sisi yang barat dari Sungai Nil

30

Draughts: dari Timur Tengah ke Athens dan Roma Pharaoh’S dari Mesir memainkan game ini sekitar 3500 tahun yang lalu. Sebagai tambahan terhadap Draughts, orang Mesir pada masa lalu juga memainkan permainan yang disebut dengan Morris (dengan cara sama seperti kita lakukan) dan merupakan asal dari permainan backgammon. Seperti halnya saat ini dimana seseorang memproduksi barang-barang yang diperlukan oleh orang lain. Beberapa pedagang yang bepergian ke bagian dunia lain membawa barang bawaan dari suatu tempat. Menurut ahli filsafat Plato, bangsa Yunani membawa papan permainan ini dari Mesir. Bangsa Yunani mulai memainkan permainan ini pada lima tahun setelah masehi, oleh orang Yunani permainan ini diberi nama “Five Line Game”. Draughts lalu menjadi permainan yang sangat umum dan populer, dan permainan ini menciptakan sebuah pepatah. Jika seseorang harus lebih dulu berada pada posisi yang baik, pepatah Yunani mengatakan : “pemain harus menyerah di garis suci”. Garis suci ini adalah garis pusat yang horizontal dari campuran papan. Merupakan garis tunggal tidak bisa di ambil, mungkin hanya raja saja yang dapat menyerang dua musuh tunggal secara serempak. Pada masa lampau bangsa Yunani dan bangsa Roma berada pada masa yang sama. Pada masa itu apakah bangsa Roma bermain Draughts? Ya. Pemain Draughts Roma yang diketahui adalah Publius Mucius Scaevola, hidup pada akhir dua masehi. Publius Mucius Scaevola mengatakan dapat bermain dengan mata tertutup kain. Publius Mucius Scaevola merupakan salah satu warga negara dari Roma yang mempunyai nama baik.

31

Tidak ada bahasan secara jelas dalam Literatur kuno bangsa Roma mengenai perkembangan permainan Draughts disana. Apakah dulu bangsa Roma memiliki variasi dalam permainan draughts sehingga berbeda dengan permainan di bangsa Yunani atau tidak.

Warisan bangsa Roma Bangsa Roma merupakan salah satu bangsa yang sangat berpengaruh di daerah Eropa. Tiga negara yang memiliki kultur kental bangsa Roma adalah: Perancis, Italy dan Spanyol dimana ketiga negara itu menggunakan bahasa latin. Salah satu warisan yang mereka terima dari kultur bangsa Roma adalah permainan Draughts pada enam tahun masehi. Permainan ini dalam bahasa latin mempunyai nama “Game With Pieces”. Ada game kedua yang bernama: Morris, yang membuktikan Draughts dan Morris sering dimainkan bersama.

Seorang Raja yang Baru: Sebelum tahun delapan Setelah Masehi Nama Latin “game with pieces“ digunakan pula oleh bangsa Arab. Sebelum tahun delapan

masehi, permainan Draughts Arab mengangkat aturan baru: raja

diberikan kebebasan untuk melangkah. Pada tahun delapan masehi bangsa Arab ditaklukkan oleh bangsa Spanyol. Permainan Draughts mereka lebih lincah dan cepat di banding permainan Draughts Roma dengan gerak raja yang terbatas.

32

Draughts beralih ke Papan Catur : 14 Tahun Masehi. Di Perancis antara tahun 1000 dan 1500, mungkin lebih awal, Draughts ini menjadi sangat populer sehingga diciptakan inovasi dimana pada tahun 14 masehi permainan Draughts di Perancis menggunakan papan seperti pada permainan catur saat ini. Inpvasi ini diterima di Perancis dan diberi nama jeu de dames, yang berarti “game dari induk”. Permainan Draughts dari negara-negara benua lainnya akhirnya ikut mengadopsi inovasi ini, tetapi para pemain Inggris lebih menyukai nama Checkers, yang secara literal berarti “game dengan papan bercorak catur”.

Pengenalan Tentang Huff: 15 Tahun Masehi Pada 15 tahun masehi. Suatu inovasi baru yaitu Huff. Huff berarti setiap pemain untuk memakan bidak lawan harus melewati dan mengambil bidak lawan tersebut dari atas papan, membawa pion dan membuangnya. Huff mempunyai sebutan yang berbedabeda dimasing-masing negara, di Perancis disebut force, di Inggris disebut draughts, yang secara literal berarti “moving a piece ”. Pemain Draughts Spanyol mengadopsi aturan ini, tetapi mereka memperluasnya dengan berbagai cara menangkap. Seperti yang sudah kita lihat, permainan Draughts Spanyol berasal dari Arab, variasi dengan panjang raja. Asal nama dari raja baru ini adalah dama, yang di ambil dari kata Spanyol damas, ’Draughts’. Pada 13 tahun masehi. Draughts dari lingkungan raja Alfonso mungkin telah menjadi pelengkap game, tetapi dua abad kemudian akan jauh dari lengkap, sebab dapat mempengaruhi permainan catur.

33

Pengenalan Tentang 100 Kotak Papan: Tahun 16 Masehi Dua inovasi lebih lanjut mengambil tempat lebih ke arah utara: di Belanda. Pembaruan yang pertama adalah pengenalan tentang yang menangkap mundur dari potongan yang tidak dipromosikan, pembaruan yang kedua pengenalan tentang 100 kotak papan. Permainan yang telah di perbaharui diberi nama Polish draughts. Di Belanda kata Polish berarti ‘aneh, asing’.

Penghapusan Huff: 19th c. Huff merupakan aturan dalam suatu pertandingan. Lihat contoh gambar 3.2 (dalam papan internasional):

Gambar 2.2 Kemenangan Pion Putih dengan Papan 10x10

34

Kemenangan putih sebagai berikut : 33-28 (22x33), 24-13 (13x24), 27-21 (16x27), 31x4. Peraturan Huff mencegah kombinasi seperti ini untuk mengeksekusi dalam kenyataan game. Hitam mengambil 22x33 dan 13x24, tetapi menolak menangkap 16x27. Potongan ini bujur sangkar 16 adalah Huff tetapi memenangkan satu potongan.

2.8.2. Detail Game Checker Checker adalah papan permainan yang dimainkan oleh dua pemain yang dilakukan secara bergantian setiap langkahnya oleh masing-masing pemain seperti pada permainan catur. Setiap pemain memiliki 12 buah potongan bidak dengan warna yang berbeda antara pemain yang satu dengan pemain yang lain. Pemain yang tidak dapat melangkah lagi karena potongan bidaknya sudah habis atau karena semua potongan bidak yang dia miliki sudah terhalang dan tidak dapat melangkah lagi maka pemain tersebut dinyatakan kalah dari permainan.(Jim Loy, 1999. p1)

Gambar 2.3 Papan Checker Papan permainan berbentuk persegi dengan 64 buah kotak kecil didalamnya yang disusun dalam dimensi 8 x 8. Kotak-kotak kecil tersebut memiliki pola warna yang bergantian bergantian antara kotak berwarna terang dan kotak berwarna gelap. Langkahlangkah dalam permainan Checker ini dijalankan pada kotak berwarna gelap. Setiap

35

pemain memiliki kotak kecil berwarna gelap pada sudut paling kiri dan kotak kecil berwarna terang pada sudut paling kanan.

Gambar 2.4 Pion Checker Pada awal kemunculan permainan Checker, potongan bidak memiliki 2 warna yaitu bidak berwarna hitam dengan bidak berwarna putih. Tetapi pada saat ini potongan bidak pada permainan ini lebih banyak menggunakan warna merah dengan warna putih. Potongan bidak ini berbentuk silinder tebal yang tidak bergambar. Potongan bidak ini diletakkan pada kotak kecil berwarna gelap di atas papan permainan.

Gambar 2.5 Posisi Awal Pion Checker

Posisi awal adalah setiap pemain mempunyai 12 potongan bidak berbeda warna yang diletakkan di atas kotak kecil berwana gelap yang berada di tepi papan permainan yang terdekat dengan masing-masing pemain. Pada sketsa, biasanya potongan bidak diletakkan pada kotak kecil berwarna cerah. Tetapi pada papan permainan sebenarnya potongan bidak diletakkan pada kotak kecil berwarna gelap.

36

Gambar 2.6 Pion Melangkah Satu Kotak Langkah: Potongan bidak yang bukan raja dapat bergerak satu kotak maju dengan arah diagonal seperti pada sketsa dimana potongan bidak bergerak diagonal maju ke kanan. Potongan raja juga hanya dapat bergerak satu kotak secara diagonal, bedanya pada raja adalah raja selain dapat maju diagonal ke depan tetapi juga bergerak diagonal mundur ke belakang. Potongan (bidak atau raja) hanya dapat bergerak ke kotak kecil yang kosong. Langkah (bidak atau raja) terdiri dari satu atau lebih lompatan (paragraph berikutnya).

Gambar 2.7 Pion Putih Memakan Satu Pion Merah Lompatan: Pemain dapat merebut potongan (bidak atau raja) dari lawan dengan cara melompati potongan lawan kita tersebut secara diagonal ke kotak kecil kosong yang berbatasan langsung dengan potongan musuh. Tiga Kotak kecil tersebut (yang berisi potongan bidak kita,potongan bidak lawan dan kotak kecil yang kosong) harus berada dalam satu garis (berbentuk diagonal) seperti pada gambar diatas. Potongan raja dapat melompat satu kotak diagonal maju ataupun mundur. Sedangkan potongan yang bukan raja (bidak) hanya dapat melompat satu kotak diagonal maju.

Gambar 2.8 Pion Putih Memakan Dua Pion Merah dalam Satu Langkah

37

Pada lompatan lebih dari satu, lompatan potongan bidak atau raja dapat berubah arah, lompatan pertama kesatu arah dan lompatan berikutnya kearah yang lainnya. Potongan bidak atau raja lawan yang telah dilompati akan diambil dan dihilangkan dari papan permainan. Pemain tidak dapat melompati potongan bidak atau raja milik sendiri. Pemain juga tidak dapat melompati lebih dari satu potongan bidak atau raja lawan dalam satu lompatan. Jika Pemain memiliki kesempatan untuk melompati potongan bidak atau raja lawan maka langkah tersebut harus dilakukan terlebih dahulu sehingga tidak dapat melakukan langkah lain sebelum itu. Jika pemain memiliki pilihan melompat maka dapat memilih salah satu di antaranya. Potongan bidak dapat melompati potongan raja, begitupun sebaliknya. Potongan raja: Ketika potongan bidak pemain berada di baris ujung tepi daerah lawan ( Baris Raja), maka bidak tersebut akan berubah menjadi potongan raja. Potongan raja tersebut tidak dapat melanjutkan lompatan sebelum langkah berikutnya. Langkah pertama di mulainya permainan adalah langkah yang dilakukan oleh pemain yang memiliki potongan bidak berwarna merah (hitam). Setiap pemain hanya dapat melakukan satu langkah dalam satu giliran di mana pemain harus melakukan langkah tersebut, jika pemain tidak dapat melangkah maka pemain tersebut telah kalah dalam permainan.

2.8.3

Turnamen Checkers

Pada checkers terdapat dua jenis mode yang diperlombakan yaitu: 1.

Go-As-You-Please(GAYP) Pada mode ini pemain bebas memulai permainan dengan langkah yang diinginkan. (kondisi awal seperti pada gambar 2.5) (Jim Loy, 1997, p4)

38

2.

3-Move Restriction Dalam 3-Move, tiga langkah pertama(Merah-Putih-Merah) dipilih secara acak dari daftar yang diterima 3-Move pembuka. Daftar berisi bukan pembukaan yang diketahui kerugiannya. 3-Move lebih populer di dalam turnamen yang serius dan pertandingan, sebagai pengurangan nomor dari seri. Setelah bermain satu kali dengan 3-Move pembukaan, permainan kedua dengan pembukaan yang sama, tetapi dari sisi lain papan (pemain memainkan warna yang sebaliknya), untuk keluar dari kerugian setelah permainan pembukaan yang lemah.

Pada pertandingan World Championship digunakan kedua mode permainan diatas. 3-Move pada World Championship semakin bergengsi. Dengan adanya National Championship

Tournaments,

District

Tournaments,

State

Tournaments,

local

tournaments, mail tournaments, mail ladders, International Team Matchs, dan event lainnya. U.S National Tournament adalah turnamen yang kuat dan paling bergengsi di dunia. Setiap empat tahun sekali, pemenang tournamen akan di lombakan pada World Championship. Pertengahan tahun, British Championship Turnament menentukan penantang untuk dimasukkan kedalam World Championship.

American Checker Federation(ACF) adalah organisasi non laba dan pusat badan pengatur checker di U.S. Sekarang, ACF keanggotaan berada di Australia, Barbados, Bermuda, Kanada, Inggris, Irlandia, Italy, Malta, Netherlands, New Zealand, Skotlandia, Afrika Selatan, Amerika, Wales, dan Hindia Barat. (American Checker Federation, 2007, p1)

39

AFC menjaga banyak turnamen checker melintasi Amerika dan sponsor tahunan turnamen checker nasional, pemenang mendapatkan bayaran bertanding untuk mendapatkan gelar World Championship.

2.8.3.1 15 Aturan Standar Internasional Turnamen Checker Sudah sejak lama permainan checker di adakan pertandingan internasionalnya. Dalam pertandingan internasional ini terdapat 15 dalil standar yang mengatur jalannya permainan(Jim Loy, 1995,p3), 15 dalil tersebut adalah sebagai berikut: 1.

Papan resmi permainan checker yang digunakan dalam pertandingan internasional dan pertandingan resmi lainnya memiliki motif berwarna Hijau dan Kuning mengkilap pada setiap kotak kecil berukuran 2 inci. Kotak kecil di tepi pojok kanan papan yang berhadapan dengan masing-masing pemain berwarna hijau.

2.

Potongan bidak resmi permainan ini yang digunakan dalam pertandingan internasional dan pertandingan resmi berbentuk silinder dengan warna yang berbeda antar pemain yaitu Merah dan Putih, dan memiliki diameter tidak kurang dari satu sampai 1 ¼ inci dan tidak lebih dari satu sampai 1 ½ inci. Potongan bidak ini diletakkan pada kotak kecil berwarna Hijau.

3.

Pada awal permainan, para pemain akan mengundi warna bidak apa yang akan mereka dapatkan. Langkah pertama akan di mulai oleh pemain yang memainkan potongan bidak berwarna Merah. Berikutnya pemain yang memenangkan pertandingan akan menggunakan potongan bidak berwarna merah pada pertandingan berikutnya.

40

4.

Setiap akhir lima menit (jika belum membuat langkah sebelumnya) ”waktu” dipanggil dengan cara beda oleh orang yang di tetapkan untuk kasus tersebut; jika pemain tidak menyelesaikan pada akhir menit yang lain, game akan divonis sebagai keterlambatan yang tidak patut dilakukan. Ketika pemain adalah tuli atau secara parsial tuli, dengan mengangkat kata “waktu” dicetak dalam kertas besar ditempatkan atau diletakkan pada meja permainan kapanpun waktunya untuk melangkah.

5.

Ketika seorang pemain mendapat dua atau lebih langkah untuk melompat, akan diberikan waktu lima menit untuk melakukan langkah. Ketika hanya terdapat satu langkah untuk melompat, akan diberikan waktu satu menit untuk melangkah dan jika langkah tersebut tidak dijalankan pada batas waktu yang diberikan maka akan diputuskan bahwa pemain tersebut akan kehilangan langkah dan akan digantikan oleh langkah berikutnya oleh pemain lawan .

6.

Pada awal permainan masing-masing pemain akan menyusun sendiri potongan bidak masing-masing di atas kotak papan permainan. Saat permainan telah di mulai (ketika langkah pertama sudah dijalankan), jika salah satu pemain menyentuh atau menggerakkan salah satu potongan bidaknya, tanpa memberi isyarat terlebih dahulu, maka pemain tersebut akan diberi peringatan pertama, dan akan kehilangan permainan untuk peringatan berikutnya. Jika ada pemain yang sedang mendapat giliran untuk melangkah sudah terlanjur menyentuh salah satu potongan bidaknya, maka pemain tersebut harus menjalankan potongan bidak tersebut atau kehilangan permainan.

41

7.

Bila ada suatu bagian dari bidak dapat dimainkan atas suatu sudut kotak yang diatasnya ditempatkan, pemain harus menyelesaikan arah tersebut. Dengan tidak hati-hati memindahkan, menyentuh atau mengganggu dari kedudukan bidak yang tidak dapat dimainkan, saat aksi “melompat” atau membuat suatu langkah diharapkan tidak membentuk langkah, dan bidak akan ditempatkan kembali dalam posisi dan game dilanjutkan.

8.

Jika terdapat langkah yang dapat melompati potongan bidak lawan, maka langkah tersebut harus dilakukan dan tidak dapat melakukan langkah lain sebelum langkah tersebut dilakukan, dan potongan bidak lawan yang telah di lompati akan dipindahkan dari papan permainan.

9.

Ketika potongan bidak sampai pada puncak papan wilayah lawan, maka bidak tersebut akan berubah menjadi raja. Jika lawan mengabaikan untuk melakukannya dalam permainan, kemudian permainan seperti akan mengambil kembali bidak yang harusnya telah menjadi raja adalah raja. “waktu” tidak di mulai pada permainan, bidak siapa harusnya telah menjadi raja sampai bidak menjadi raja.

10.

Ketika bidak menjadi raja, bidak tersebut dapat bergerak kearah manapun baik maju maupun mundur sesuai dengan luas papan permainan. Ketika potongan raja tidak tersedia, maka harus dilengkapi oleh wasit.

11.

Hasil seri didapatkan ketika masing-masing pemain memiliki kekuatan yang sama untuk memenangkan permainan dan dibuatnya kesepakatan antar pemain agar permainan ini di akhiri dengan hasil seri.

42

12.

Saat permainan sudah di mulai, tidak boleh ada pemain yang meninggalkan papan permainan tanpa izin dari wasit. Jika izin telah diberikan pada seorang pemain maka pemain lawan dapat menemaninya atau wasit akan menunjuk seseorang untuk menemaninya. Waktu akan dikurangi dari pemain yang mendapat giliran untuk melangkah.

13.

Benda apapun yang cenderung mengganggu atau mengacaukan perhatian lawan di larang ada dalam permainan, seperti membuat tanda atau mengeluarkan suara, berada atau melayang-layang di atas papan permainan, salah satu dari tangan atau kepala, atau dengan tidak penting menunda langkah permainan. Siapapun pemain

yang

melakukan

setelah

diberi

peringatan

makan

sebagai

konsekuensinya pemain tersebut akan kehilangan permainan atau kalah. 14.

Pemain diperbolehkan merokok selama pertandingan tetapi tidak boleh meniupkan asap rokok melintasi papan permainan agar tidak mengganggu lawan bermainnya. Jika hal tersebut menggangu lawan maka pemain tersebut tidak diperkenankan untuk merokok.

15.

Setiap penonton dilarang untuk membuat keributan ataupun merokok dekat dengan papan permainan. Jika terjadi keributan maka permainan akan dihentikan hingga keributan sudah dapat di sudahi.

2.8.4

Checker Strategi Apapun subjek yang dipilih orang, jika ingin mempelajari metode yang

digunakan oleh eksponen di dalam bidang.(Derek Oldbury, p1) Jika seorang pemain golf yang ambisius pasti akan membaca pukulan dari pemain pro dan mendengarkan tips-tips untuk menjadi mahir. Dalam checker, secara khusus, orang baru telah di lalaikan oleh

43

otoritas di samping melimpahnya literature berhadapan dengan hasil turnamen, pertandingan, dan game lain yang dimainkan oleh ahli. Hal ini dilampirkan dengan suatu kelanjutan dari analisis dalam majalah dan surat kabar namun hanya sedikit atau tidak ada yang menulis penjelasan dari prinsip dan ide yang mendasari ilmu pengetahuan game dalam cara pantas untuk pemula. Mereka semua membuat kesalahan dari berusaha untuk menghilangkan perbedaan antara pemula dan mahir dengan beberapa keadaan umum sebagai ganti memberikan nasehat. Banyak pemain luar biasa mencapai rangking mereka dengan cara yang sulit, pelajaran mengoreksi bentuk dan mendasari prinsip tanpa pendidikan yang diterima di sekolah yang akan membuat secara sederhana untuk maju. Beberapa ke beruntungan untuk mempunyai pelatih yang mahir secara pribadi dan bertahan pada mencoba dan salah metode untuk belajar, yang mana satu ke kurangan sebab membuang waktu dan usaha dan tidak memberikan jaminan mutu. Pemula pada checker sering membayangkan pemain mahir memiliki rahasia aturan matematik untuk memecahkan tiap-tiap situasi yang timbul pada papan checker. Ide ini adalah salah seperti banyaknya posisi yang tidak mungkin hampir tak terbatas, dan tidak seorangpun telah pernah menguasai permainan checker dengan tujuan untuk kesempurnaan. Keuntungan pemain mahir berada di dalam penggunaan sistemetis dari permainan dihafalkan tambahan kemampuan untuk memandang ke depan dengan jelas, menggunakan prinsip definisi, teori formasi, dan pengetahuan praktis dari akhir game. Memori adalah suatu factor penting dalam kemajuan. Kemampuan pemain mungkin sangat baik tetapi mengatur keadaan terhadap lawan, ketika pengikut lain mengetahui buku permainan yang mana dikumpulkan akumulasi dari pelajaran orang yang mahir(master). Pengetahuan adalah kekuatan dalam checker. Jika kamu mengetahui langkah yang benar dalam posisi tidak saja menjadi juara bahkan tidak dapat

44

mengalahkannya. Pemain siapa yang menolak semua buku pengetahuan dan mempercayakan atas papan silang usaha sendiri mengingatkan pada satu pemusik yang melakukan tanpa persiapan. Memaksa lawanmu untuk melangkah adalah salah satu rahasia untuk menangkan game checker. Untuk menerapkan taktik memaksa diperlukan kemampuan mengenai formasi, perangkap dan menembak, permasalah pada akhir-game, dan untuk melihat pemain depan dengan visi yang tajam. Dalam perencanaan game kamu menggunakan prinsip memaksa dalam pilihan untuk menantikan saat terbaik, berharap untuk keliru. Pemain yang cukup mempunyai kekurangan, berusaha untuk memindahkan “salah langkah”, ketika mereka bisa dengan mudah memaksa suatu kemenangan dengan mengkoreksi posisi permainan. Dalam hal-hal tertentu game checker serupa untuk berperang. Masing-masing pemain di samakan secara umum dengan angkatan perang dari duabelas pion pada atas lantai pertempuran pada 32 kotak. Para pemimpin dalam berperang siasat angkatan perang mereka dengan ketepatan militer, menyerang di sini, mengorbankan di sana, bekerja keras untuk memperdaya lawan mereka dengan strategi atau berlimpahan mereka dengan angka-angka atas. Taktik ini sama digunakan pada olahraga ramah pada checker, game ini didasarkan semata-mata pada kekuatan mental. Suatu pertempuran tidak membantu dalam pertempuran secara sembrono. Demikian juga permainan checker menjadi segalanya tetapi urusan ilmiah, perencanaan di depan dan penggunaan formasi dalam melindungi orang-orang satu sama lain dan menyajikan suatu medan yang direncanakan ke arah oposisi.

45

2.8.4.1 Kendali Pusat Ketika kamu memasuki suatu perkelahian, tetang segala pengurutan, suatu perhatian yang utama haruslah medan perang. Mungkin saja zona berbahaya yang harus dihindari, ke dalam mana pemain harus mencari untuk mendorong lawan: hal ini harus di kenal. Mungkin saja ada titik point yang mana, menangkap, akan mengendalikan keseluruhan lapisan dari tindakan dan akan membiarkan keadaan peristiwa didikte- oleh anda sendiri, atau oleh pemain yang lain.(Derek Oldbury, p5) Lihat lagi, dan catatan pertama bahwa kotak tidak sama semua. Mereka yang di dalam pusat papan sangat tidak sama dengan di sekitar garis keliling. Dari pusat, hanya digunakan beberapa gerakan untuk dapat ke kotak lainnya pada papan, beberapa langkah - langkah dan ada diperistiwa. Hal ini merupakan suatu cara panjang dari satu sisi papan ke lainnya, pada saat itu pemain ada di sana mungkin saja sudah terlambat. Terlepas dari kecepatan, kotak tengah menawarkan suatu lingkup lebih luas: dari sana pemain dapat menyerang atau menegakkan maupun yang mengapit, di mana saja ada kemungkinan beruntung. Dalam beberapa hal pemain akan melakukan serangan, atau pertahanan, dari pengapit, dan pada umumnya pemain harus menerobos kotak tengah. Jika ini dalam kendali pemain, pemain dapat menyelesaikan rencananya, Jika mereka sedang dikuasai oleh lawan komunikasi terputus, dan bidak mungkin dapat menyelinap di sekitar sisi garis, bersembunyi dalam bayang-bayang sampai akhirnya, sendiri, mereka bunuh diri. Kendali dari pusat berarti kendali dari papan. Jika luar kotak lebih sedikit diinginkan, kemudian dari kotak paling sudut dari papan nantinya bahkan lebih sedikit dan dalam kesempatan ini sungguh tidak aman. Petinju tidak akan menjepitkan di tali pagar ring tinju jika prtinju dapat membantu itu.

46

Jika petinju mempertahankan dalam posisi menyudutkan kemudian di dalam gangguan yang mengerikan. Empat sudut pada papan checker tidak serupa. Dua dari mereka terdiri hanya satu kotak dengan satu jalan keluar dari kotak: sudut tunggal ini lazimnya akan menjadi tempat yang baik untuk menghindar. Pada sudut ganda pada kotak melindungi satu sama lain, dan dengan jalan keluar yang sama nantinya akan menyelamatkan dalam perbedaan sudut yang tunggal. Sekarang, semua keterangan ini memberikan ide dengan bermain ke arah pusat sejak semula dapat pergi sepanjang memenangkan alur; tetapi tidak terlalu cepat. Begitulah caranya merusak. Jika pemain melangkahkan semua pion ke pusat, mereka hanya akan mendapatkan dijalan masing-masing yang lain dan mengakibatkan penghalangan. Mengemasi dengan ketat kelompok menimbulkan gerakan penyempitan dari lawan. Kendali adalah yang penting, pemain menduduki pusat oleh sebanyak pion ketika akan memperoleh kendali, tetapi tidak lagi. Pemain mengendalikan lawanmu ketika tidak mampu untuk bergerak kemanapun dari pusat kotak dan demikian memaksa supaya semakin sedikit yang membantu area dari papan. Hal ini adalah fakta gol kemenangan terakhir: untuk memandu musuh ke dalam hutan belantara di mana lawan akan binasa. Selalu main pelan-pelan dan dengan penuh pertimbangan, menguji tiap-tiap gerak yang mungkin. Gerakan pukulan pemain sering kali di lewati atau tidak berpikir pantas dari pertimbangan. Gerakan terburu-buru dan menyesal dengan santai adalah sesuai dengan moto dalam Checker. Ketika ini adalah putaran pemain untuk bergerak, gunakan proses penghapusan dengan cepat untuk menentukan pemain terbaik. Mulai dengan cepat mental lupa

47

hitungan dari tiap gerak yang mungkin. Kemudian mengguji yang terburuk melihat, seperti memberi satu atau lebih pion pergi. Hal ini dapat dengan cepat dihapuskan dari pertimbangan lebih lanjut ketika masing-masing menemukan kerugian palsu(jebakan) atau memberikan keuntungan bagi pihak lain. Cara ini jauh lebih baik tersedia langkah untuk menentukan segera dan perhatian memusat pada mereka. Analisis dengan teliti dan dengan cepat pada masing-masing, visualisasi perubahan dalam posisi jauh ke depan seperti dapat mengambil langkah terbaik. Selalu harapkan lawanmu untuk membuat langkah terbaik.

2.8.4.2 Opening, Mid-Game, dan End-Game Menyenangkan untuk tujuan belajar serta berbagi, dalam game terdapat tiga tahap; pembuka(opening), pertengahan-game(mid-game), akhir-game(end-game). Divisi ini bukanlah seluruhnya tiruan seperti alasan pemimpin mendasari masing-masing tahap sungguh sangat membedakan. Tema dominan dari pembukaan mungkin dikatakan untuk persiapan sepanjang pertempuran mengamuk. Pada pertengahan-game; konflik pada pertengahan-game adalah memecahkan dalam akhir-game. Pada pemain belakang mencari untuk membuktikan nilai riil untuk memperoleh keuntungan atau hilang sepanjang permainan awal. Satu kebutuhan hanya menggambarkan tujuan akhir-game, untuk melihat ini harus melihat tahap paling terpenting dari game. Tahap terdahulu mempunyai kaitan dengan menciptakan prospek yang baik, dalam akhir-game harus mempertimbangkan hasil nyata, menang, kalah, atau seri. Tergelincir pada langkah dan semua ide cemerlang masa lalu menjadi tidak berharga. Pada sisi lain akhir-game, menuntut ketika mengerjakan kedua-duanya ketepatan dan artistik, boleh memberikan satu kesempatan

48

untuk memperbaiki posisi dan memutar kekalahan kedalam kemenangan. Dalam Draughts pemain terbaik menang dan tanda bukti adalah pada akhir-game. Memberikan satu atau lebih pion di depan bukanlah sikap sportif yang lemah, tetapi secara ilmiah dan sesuai cara untuk menyelesaikan game. Objek dalam Checker adalah untuk menang tidak sama sekali jumlah gerakannya, apakah dengan menghalangi posisi, menyudutkan pion lawanmu sehingga hanya dapat memberikan mereka pergi, atau dengan membuat mereka jatuh, satu per satu. Dalam banyak situasi di mana keuntungan dalam jumlah berlaku, kemenangan tidak dapat dipaksakan kecuali dengan pertukaran. Antara mahir, suatu akhir dengan angka ganjil, kecuali jika ada suatu keuntungan posisi untuk mengganti kerugian, adalah melulu suatu prosedur yang rutin. Abad ke-19, pemain memikirkan tujuan yang sesuai dalam permainan checker untuk memenangkan pertandingan. Sekarang ini, pandangan bahwa pemain terutama sekali main untuk menghindari kekalahan, itu yang dikatakan, bermain untuk menghasilkan gambaran. Tentu saja jika suatu kesempatan untuk menang tampak diperlukan (dan IS dari kebetulan ) kemudian mengambil itu, tetapi dapat menjaga gambaran dalam melihat kapanpun. Kemudian untuk pembaharuan, suatu pembukaan bukanlah lemah jika menyelamatkan untuk seri, meskipun mungkin hampir menawarkan kesempatan untuk menang. Berlatih dengan seorang master Checker. Seseorang tidak perlu bepergian jauh untuk menemukan tenaga ahli. Mereka ada dimana-mana, penyelesaian paling kecil yang membuat juara. Tenaga ahli lokal cenderung untuk jadikan para siswa mendalam pengalaman para siswa dalam buku pengetahuan dan mampu menawarkan kompetisi yang kaku. Jika komunitas kamu mempunyai club Checker, bergabung dan memperoleh manfaat dengan jenis yang benar dari berlatih. Pemain akan menemukan pemain dari

49

seluruh lapisan masyarakat yang dipersatukan dalam persahabatan, yang terpesona oleh salah satu hiburan intelektual terbesar. Checkers membantu mengembangkan ciri karakter yang diperlukan untuk hidup sukses. Sebagian dari ini adalah perhatian, konsentrasi, pengendalian-diri, ketenangan, ketepatan, kesabaran, sumber daya, dan pemikiran metodis.

2.8.4.3 Diagonal Suatu rantai dari kotak berlaku untuk semua membentuk garis miring. Barangkali kita dapat dapat memanggil seperti bentuk diagonal – betapapun, itulah yang mereka sebut. Seperti pemain akan segera lihat, ada tujuh diagonal. (Derek Oldbury, p17) Bagaimanapun, hanya satu dari mereka sungguh langsung dari akhir ke akhir; itu adalah diagonal yang meluas dari sudut tunggal ke sudut tunggal, seperti :

Gambar 2.9 D-line diagonal (Diagram 1)

Mungkin saja untuk perkiraan yang alami dari diagonal pemain berminat untuk menduduki atau mengendalikan. Diagonal boleh mempengaruhi tenaga dari pion sama halnya pemain menemukan kotak tersebut. Efek yang paling jelas nyata bahwa sudut

50

diagonal yang tunggal dapat memotong papan ke dalam membelah dua, sebagaimana. Itu membagi pionmu dari lawan. Di lihat dari sudut ini, saat memulai permainan hanya satu dari 12 pion siap kedalam area musuh; tiga posisi netral. Dalam permainan menyerang pion nantinya menerapkan dengan sedikit penundaan, pemain boleh mengira mungkin benar. Sudut diagonal yang tunggal adalah garis dari pertahanan (disebut dengan D-line) memisahkan dua angkatan perang: untuk menguasai terhadap garis ini perlu inisiatif; untuk menyebrang di mulai untuk menyerang.

Gambar 2.10 Contoh Diagonal D-line: dalam situasi ini perlu menyediakan sisi untuk mengambil resiko dan kontrol bersama. (Diagram1b). Jika sudut diagonal yang tunggal adalah bertahan sifatnya, kemudian satu baris yang memotong ke seberang dan melalui pusat papan harus dengan jelas disebut dengan baris penyerangan: aktivitas manapun sepanjang garis ini menandakan agresi. Ini adalah A-line.

51

Gambar 2.11 A-line diagonal (Diagram 2)

Gambar 2.12 Contoh A-Line: Pada diagram ini, hitam menduduki A-Line mereka sendiri dan mengendalikan dengan caranya. Apakah mereka juga mengendalikan A-Line putih akan tergantung dengan penempatan dari pion putih.(Diagram 2b).

Pemain siapa yang terlibat pertama kali dalam A-line akan mempelopori penyerangan. Lawan harus menjawab dalam beberapa cara lain. Dalam diagram 1b dan 2b, apakah kamu berpesan ekstra pion di dasar? Meskipun demikian pion tidak

52

mengambil bagian apapun yang aktif di dalam memerintahkan diagonal, kekuatan yang ditambahkan adalah diinginkan, untuk dasar yang mana lawan akan menyerang. Jika dasar dapat dibinasakan keseluruhan struktur boleh pisahkan Diagonal A dan D adalah bentuk utama dari serangan dan pertahanan. Pemain memperluas kekuatan dan lingkup dari pion ketika mengisi dan mengontrol bentuk penting dengan mereka, maka tentu saja hal ini patut dicoba. Diagonal yang berlari sisi ini dari A-Line, karena kontras sangat sedikit mengimport untuk semakin memperbesar bagian dari panjangnya poin untuk sisi dari papan. Kotak terbaik adalah mereka yang berada di tepi, mungkin digunakan untuk mendukung potongan lebih aktif. B-line adalah diagonal dengan kelemahan, lawan yang pandai akan sering menggunakan miliknya pada akhir. Salah satu jalan semakin kuat adalah untuk menempatkan pion lawan pada kotak yang tumpang tindih D-line dan Bline, mendominasi keduanya dan pengasiran A-line.

Gambar 2.13 B-Line diagonal yang lemah (Diagram 3)

53

Kebanyakan dari C-line berlari ke arah pusat dan demikian lebih kuat dari B-line yang dekat, dan juga bagian dari C-line tumpang tindih menyerang A-line hal tersebut dapat disebut diagonal penting. Pemain dengan susah mengatakan bahwa kotak di mana A-line dan C-line bertemu dan menyilang adalah nilai terbaik dalam pemain formal, baik dalam menyerang dan serangan balasan. Hal tersebut adalah kunci kotak, dan sekarang pemain mengetahui mengapa.

Gambar 2.14 The C-line diagonal (Diagram 4) Baris E dan F untuk kebanyakan bagian bertahan, pendukung mereka sepanjang melakukan aktivitas D-line. Ini adalah kegunaan utama mereka.

Gambar 2.15 E-line diagonal (Diagram 5)

54

Gambar 2.16 F-line diagonal (Diagram 6) Jika memperhatikan Diagram 1b, akan terlihat kedua sisi menduduki E-Lines mereka, dan ini adalah suatu khas membangun. Diagonal yang terakhir adalah G-Line.

Gambar 2.17 G-line diagonal (Diagram 7)

Fakta bahwa G-line mempunyai hampir semua fitur dari A-line menggoda satu untuk hormat sebagai garis serangan, ketika mereka menyadari itu adalah G-line begitu juga A-line lawan. Serangan manapun sepanjang garis mungkin diharapkan untuk

55

berasal dari sisi papan lawan dibanding dari sisi pemain. Bagaimanapun, jika pemain pertama menyediakan formasi yang kuat sepanjang A-line

kemudian serangan

sepanjang G-line dapat lebih berhasil, seperti:

Gambar 2.18 Contoh G-Linediagonal: Hitam membantu dua pion sepanjang GDiagonal, dengan dukungan yang kuat dari formasi menunjukkan sebelumnya, pada Diagram 5. Hal ini adalah tentang jalan terbaik untuk melakukan serangan G-Line. (Diagram 7b)

Secara umum, suatu kemajuan awal dalam game sepanjang G-line servis hanya untuk mencegah aktivitas dan untuk mengukur pertahanan

56

Gambar 2.19 Contoh G-Line diagonal: Hitam telah membuang-buang keuntungan yang alami dari setelah hak untuk bergerak pertama dan membuat ancaman yang pertama, dan di sini main untuk pertahanan yang aman. (Diagram 7c) Jika sekarang meringkas survei kotak dan diagonal, pemain harus datang untuk melihat dengan jelas ketika kotak sering menentukan nilai dari pion, sehingga untuk tindakan pion secara keseluruhan boleh menentukan karakter dan kekuatan diagonal – suatu diagonal adalah kuat sebab mengijinkan membangun dari menceritakan pola formasi. Hal tersebut bisa jadi berguna bagi status secara umum bahwa, awal game, ketika kita mempunyai angka-angka dari pion untuk membentuk rantai dari serangan atau pertahanan, kemudian diagonal sangat penting. Terlambat dalam game, kapan angkatan perang berkurang untuk sedikit unit terserak, kemudian individu kotak masuk ke dalam milik mereka sendiri. Salah satu konsep penting game adalah bahwa pemain tidak selalu bergerak ke arah yang pemain inginkan, tetapi terkadang pemain harus memutar dan pemain harus bergerak ke suatu tempat. Jika ini putaran pemain dan tidak bisa, kemudian pemain sudah kalah dalam game. Itu yang memutuskan nasib pemain, tidak yang lain.

57

2.9

Chinook Chinook adalah suatu proyek yang sengaja dibuat oleh para pengemar permainan

Checker. Program Chinook menggunakan kemungkinan-kemungkinan yang dapat terjadi dan disimpan ke dalam database, sebanyak 443,748,401,247 posisi. Berikut adalah nama para pembuat game Chinook saat ini, yaitu: Yngvi Bjornsson, Martin Bryant, Neil Burch, Joe Culberson, Akihiro Kishimoto, Rob Lake, Paul Lu, Martin Mueller, Jonathan Schaeffer, Steve Sutphen, Norman Treloar. Para pembuat Chinook ini bersatu untuk membuat game yang bahkan sulit dikalahkan oleh manusia, karena lengkapnya data-data langkah dalam permainan. Sehingga pemain mahir sekalipun akan kesulitan untuk menghadapi program Chinook ini. (http://www.cs.ualberta..ca/~chinook/)

2.9.1

Project Proyek Chinook di mulai pada tahun 1989 dengan tujuan mengembang program

yang mampu mengalahkan manusia dalam bermain checkers. Di tahun 1990, chinook menjadi program pertama di dunia yang berhasil ikut di kejuaraan checker dunia melawan manusia. Program mengalami kekalahan di kejuaraan pertamanya pada tahun 1992, tetapi menjadi pemenang di 1994. Pada tahun 1996, dengan jelas program ini lebih pintar dari beberapa pemain manusia, dan chinook akhirnya tidak ikut lagi dalam kejuaraan tersebut. Permainan checkers punya di mensi kemungkinan sebanyak 5x10 langkah, sebuah angka yang sangat besar. Sejak 1989 secara berkelanjutan (kecuali pada periode 1997 sampai 2001), puluhan komputer bekerja siang malam selama 24 jam untuk memecahkan permainan ini. Akhirnya pada tanggal 29 April 2007, para pengembang

58

program chinook dengan yakin mengumumkan bahwa permainan checkers telah terpecahkan oleh program ini. Mulai dari posisi awal standar, biji hitam (pemain yang pertama kali mendapat giliran melangkah) dijamin seri dengan dengan permainan yang sempurna. biji putih (pemain dengan giliran kedua) juga di jamin seri, tanpa tergantung dengan langkah pertama yang di ambil oleh pemain dengan biji hitam. permainan checkers merupakan permainan terbesar yang telah terpecahkan solusinya sampai saat ini, lebih besar dibanding dengan permainan Connect Four dan permainan Awari. Dalam perjalanannya, proyek Chinook telah mempublikasikan banyak riset. Chinook's memenangkan kejuaraan Man-Machine dunia (tiga tahun sebelum pertandingan catur the Deep Blue) menjadi tonggak sejarah dalam riset kecerdasan buatan. Pada tahun 1996, Guinness Book of World Record mencatat Chinook sebagai program komputer pertama yang menang dalam kejuaraan dunia manusia.

Tonggak Sejarah Chinook 1989: proyek permainan Checkers dimulai. Menghitung basis data 4-piece endgame (7 juta posisi). Program chinook menang dalam olimpiade komputer. 1990: Menyelesaikan basis data dari 6-piece endgame (2.5 juta posisi). 1990: Chinook memenangkan kesempatan untuk menantang juara dunia checkers. 1992: Pada kejuaraan dunia Man-Machine pertama, meraih beberapa kemenangan dari pemain manusia. 1994: Menyelesaikan basis data dari 8-piece endgame (444 milyar posisi). 1994: Pada kejuaraan dunia Man-Machine Kedua, Chinook memenangkan kejuaraan. 1995: Berhasil mempertahankan gelar juara dunia.

59

1996: Kejuaraan terakhir untuk chinook, memenangkan pertandingan melawan pemain manusia paling kuat di kejuaraan U.S. 1997: Menerbitkan One Jump Ahead: menantang keunggulan manusia dalam permainan checkers. 1997: Guinness Book of World Record mencatat Chinook sebagai program komputer pertama yang memenangkan kejuaraan manusia. 1997: Usaha pertama memecahkan permainan checkers gagal dan proyek dihentikan. 2001: Bangunan basis data Endgame Checker mulai di kembangkan lagi. 2004: Usaha kedua memecahkan permainan checkers mulai kembali. 2005: Basis data 10-piece endgame selesai (39 trilyun posisi). 2007: permainan checkers berhasil terpecahkan. Permainan sempurna memimpin dengan kepastian seri.

Warisan Arthur Samuel Arthur Samuel mulai mengembang program permainan checkers di tahun 1950. Pada tahun 1962, program checker ini bertanding melawan Robert Nealey. Kemenangan tunggal yang di raih program buatan Arthur merupakan peristiwa bersejarah, tetapi dari waktu ke waktu prestasi ini di lebih-lebihkan. Pencapaian program Arthur bernilai tinggi hanya untuk jamannya saja. Meskipun begitu, ide yang dibuat Arthur dalam programnya menjadi tonggak awal dalam riset kecerdasan buatan. Proyek Arthur akhirnya memberi kesan yang salah bahwa permainan checker telah terpecahkan solusinya. Akibatnya, para peneliti mengalihkan penelitiannya kepada permainan catur, dan sebagian besar peneliti mengabaikan permainan Checker selama lebih dari 25 tahun.

60

Gambar 2.20 Arthur Samuel sedang meneliti permainan Checker manusia dengan AI

“Arthur Samuel (berdiri), peneliti IBM tentang kecerdasan buatan, sedang menyaksikan permainan checker antara manusia dan robot (komputer besar). Komputer tersebut akhirnya memenangkan permainan ini dan menuliskan pada layarnya: 'Maaf, anda kalah. '” John Pfeiffer, The Thinking Machine, J.B. Lippincott Company, Philadelphia & NY, 1962. Berikut ini akan menjelaskan pertandingan bersejarah di mana program rancangan Arthur melawan Robert Nealey, dan akibat jangka panjang dari pertandingan ini. Ini dikutip dari One Jump Ahead: Challenging Human Supremacy at Checkers, Jonathan Schaeffer, Springer-Verlag, 1997: Tidak memakan waktu yang lama saat samuel membuat sebuah program permainan checkers, yang mampu secara mudah mengalahkan pemain pemula. Pertama kali dipublikasikan di televisi pada tanggal 24 februari 1956. Thomas Watson, Presiden IBM, Mengatur program untuk diperlihatkan ke pemegang saham. Thomas Watson

61

meramalkan bahwa program ini akan mengakibatkan

kenaikan harga saham IBM

sebesar 50% pada saat itu. Pada tahun 1961, Edward Feigenbaum dan Julian Feldman menerbitkan buku klasik mereka yang berjudul Computer and Thought, sebuah naskah pertama dalam riset kecerdasan buatan. mereka meminta Samuel untuk ikut ambil bagian dalam pembuatan naskah ini termasuk di dalamnya mendiskusikan program terbaik dalam permainan checkers. Untuk memberikan kesan bahwa program buatannya adalah program terbaik, Samuel memutuskan bahwa program buatan dia akan menantang pemain terkuat dalam sebuah pertandingan resmi. Catatan sejarah kurang jelas, tetapi untuk beberapa alasan Samuel memilih pertandingan pertama program dia melawan Robert Nealey, pemenang pertandingan checkers dari Stamford, Connecticut. IBM's Research News mengklaim bahwa Nealey adalah “mantan juara permainan checkers tuna netra pada kejuaraan Connecticut, dan salah satu pemain checker terkemuka didunia. ” Saat pertandingan tersebut, Nealey tidak menampilkan permainan layaknya seorang juara Connecticut, meskipun pada tahun 1966 berhasil memenangkan gelar tersebut, empat tahun setelah pertandingan melawan program buatan Samuel. Sepanjang sejarah kejuaraan Connecticut, tidak pernah menyatakan bahwa ada pemain hebat yang ikut dalam kejuaraan tersebut. Nealey tidak pernah bermain dalam kejuaraan checker resmi, seperti kejuaraan US. dan ternyata dia memiliki reputasi buruk melawan pemain lokal.

62

Berikut adalah jalannya pertandingan program Samuel melawan Nealey, dengan catatan yang dibuat oleh Samuel. Hitam: Program Samuel Putih: R.W.Nealey 1. f6-e5 e3-f4 2. g7-f6 c3-b4 3. h8-g7 b4-a5 4. e5-d4 g3-h4 5. b6-c5 d2-e3 6. d6-e5 f4xd6 7. c7xe5 h2-g3 8. e5-f4 g3xe5 9. a7-b6 a5xc7 10. b8xd6xf4xd2 e1xc3xe5 11. f6xd4 c1-d2 12. g7-f6 b2-c3 13. d4xb2 a1xc3 14. f6-e5 f2-e3 15. e5-f4 e3xg5 16. h6xf4

Posisi kritis. lihat gambar 10. 16. . . . g1-f2 putih membuat langkah yang salah.

63

Salah satu prinsip paling utama dalam permainan checkers adalah menempatkan bidak permainan dibelakang bidak permainan yang lain sebagai tameng pertahanan. Dengan memindahkan pasukan bidak paling belakangnya, Nealey memberikan raja secara gratis untuk bidak hitam. Sebaliknya, bidak hitam mempunyai barisan bidak belakang yang kuat, membuat bidak putih sulit untuk memperoleh raja. Chinook menyatakan pertandingan berjalan seri hingga terjadi kesalahan. Dengan langkah g1-f2, dapat di tetapkan bahwa kemenangan ada di pihak bidak hitam. Sebaliknya, langkah h4g5 adalah satu-satunya langkah untuk mendapatkan hasil seri.

Gambar 2.21 Nealey (putih) melangkah g1-f2, sebuah langkah yang membuat kerugian 17. f4-g3 dengan jelas, menjamin bidak hitam menjadi raja.

17. . . . f2-e3 18. g3-f2 c3-d4 19. f2-e1=k d4xb6 20. e1xc3 b6-a7 21. c3-d2 langkah yang memaksa putih tidak dapat berkembang.

64

21. . . . e3-f4 22. d2-c3 f4-g5 23. c3-d4 a3-b4 24. d4-e3 b4-a5 25. d8-c7 Kemenangan hitam tergambar sekarang.

Benarkah ini? tidak ditunjukkan dalam kepustakaan, tetapi d8-c7 merupakan kesalahan fatal dari langkah yang dijalankan program buatan Samuel. Dengan memperlemah baris terakhir, Nealey dapat memperoleh raja dan mendapatkan hasil seri.

25. . . . g5-f6

Saling membalas. Nealey tidak menyadari posisi ini. chinook menyatakan bahwa dengan strange-looking g5-h6 diikuti oleh a7-b8=k, putih dapat meraih hasil seri (a7b8=k pertama mengalami kerugian).

26. e7xg5 h4xf6 27. e3-f4 Putih menyerah.

Putih tidak bisa mencegah serangan raja hitam yang akhirnya memenangkan pertandingan di f6. sebagai contoh, jika a7-b8=k, maka f4-g5 b8xd6 g5xe7xc5.

65

Akhirnya, ini adalah permulaan yang bagus untuk program buatan Samuel. Nealey mengatakan dukungnya: “Pertandingan ini tidak mempunyai titik temu. Permainan berjalan sesuai perkiraan, kecuali ketika saat mencoba berusaha untuk mempersulit langkah komputer, tapi usaha yang di lakukan sia-sia . Pada langkah g1-f2 kerugian dan keuntungan, semua bermain dengan baik sepanjang penglihatan. Hal ini sangat menarik perhatian dimana komputer dapat membuat beberapa langkah [sangat baik] untuk memperoleh kemenangan, dan sebaliknya memiliki beberapa kesempatan untuk mendapatkan hasil seri. Itulah mengapa Nealey masih terus melanjutkan pertandingan. Oleh karena itu, komputer, bermain dengan sangat sempurna tanpa melakukan satu pun kesalahan. Dan terakhir, Nealey tidak pernah lagi bertanding dalam turnamen checker melawan manusia sejak tahun 1954, di mana Nelay mengalami kegagalan terakhir kali. ” Walaupun tidak cukup berguna untuk di katakan, Nealey sangat tidak sependapat dengan apa yang dia katakan. Waw! komputer telah mengalahkan pemain checker kelas dunia! ini akan menjadi berita utama terbaru. Komputer telah berhasil memecahkan permainan checkers. Kepintaran manusia telah ditantang oleh sebuah monster elektrik. Untuk literatur kemajuan di bidang teknologi pada tahun 1962, ini merupakan peristiwa besar. Ini merupakan tahap awal di mana kecerdasan komputer dapat menyelesaikan berbagai persoalan lebih baik daripada manusia. berapa lama lagi waktu sebelum komputer menjadi lebih pandai daripada manusia? Tetapi pada akhirnya, kecerdasan komputer mengalami perkembangan yang tidak segnifikan pada beberapa tahun selanjutnya karena ketakutan manusia.

66

Pertandingan ulang dilakukan pada tahun berikutnya, dan pada saat itu menggambarkan wawasan bagaimana program komputer tersebut dapat berhasil menjalani pertandingan yang luar biasa beberapa tahun lalu: Bertanding di rumahnya, Nealey duduk di depan papan checker dan menerangkan masing-masing posisi dalam enam pertandingan. (Walaupun dia tidak sepenuhnya buta, dia mengenali bidak lebih dengan menggunakan sentuhan dibanding dengan penglihatan, secara garis besar dia bermain dengan “tanganku dan otakku”) Setelah menentukan langkah yang ambil, Nealey menandainya di selembar kertas dan mengirimkannya kepada Pusat Riset Waston IBM di Yorktown Heights, N.Y , di mana program komputer itu berada. Program dapat menganalisis minimal enam langkah dan maksimal 20 langkah ke depan, tergantung pada tingkat ketelitian yang di butuhkan. Dengan kata lain, program ini menganalisis ribuan bahkan puluhan ribu macam posisi sebelum memutuskan langkah terbaik yang akan diambil. Hal tersebut tentu saja hampir mustahil untuk dilakukan oleh manusia. 7094 [IBM komputer] dapat melakukan 15 juta penambahan atau enam juta perkalian dalam satu menit, atau sama dengan kemampuan perhitungan manusia dalam satu tahun. Komputer hanya memerlukan waktu seputuh atau duapuluh detik untuk menentukan langkahnya. (Walaupun kecepatan ini tidak berpengaruh untuk lawan yang bermain lewat surat, tetapi ini dapat membingungkan lawan di pertandingan langsung.) Sedangkan rata-rata waktu yang dibutuhkan Nealey untuk menentukan langkah adalah tiga menit. Hasil akhirnya adalah kemenangan untuk Nealey, dengan satu kali menang dan lima kali seri.

67

Di tahun 1966, Samuel menyertakan program buatannya dalam pertandingan kelas dunia melawan Walter Hellman (Juara bertahan, u.s.) dan Derek Oldbury (Inggris). IBM mensponsori pertandingan ini, dimana program Samuel ini akan menjalani empat pertandingan untuk masing-masing lawan, dan ternyata program Samuel mengalami kekalahan dengan mudah di semua pertandingan yang dijalani. Harapan yang dikemukakan pada tahun 1962 akhirnya hanya merupakan ilusi belaka. Program buatan Samuel ini menginspirasi siapapun yang menggunakan checker sebagai bahan percobaan dalam beberapa dasawarsa mendatang. Pandangan bahwa permainan checkers adalah permainan yang telah terpecahkan akhirnya timbul kembali. Banyak ilmuan yang mencoba menghidupkan kembali kebohongan itu. Berikut adalah beberapa contohnya: “. . . seperti yang telah diramalkan sebelumnya, permainan checkers akan menjadi permainan yang sudah terpecahkan. ” richard bellman, Proceedings of the Nation Academy of Science, 53(1965). “Dan ketika komputer dapat menyelesaikan permainan tick-tack-toe, dan bahkan permainan checkers, dengan melihat semua kemungkinan untuk mengakhiri permainan, mereka tidak bisa melakukannya pada permainan catur. ” lynn steen, “Computer Chess: Mind vs. Machine," Science News,29 November 1975. “Walaupun sudah sejak lama komputer tak terkalahkan dalam permainan dasar seseperti permainan checkers. . . . ” Clark Whelton, Horizon, Februari 1978. “Komputer menjadi tak terkalahkan di permainan checkers dalam beberapa tahun yang lalu. ” Thoma Hoover, “Intelligent Machines,” Omni magazine, 1979. Pada tahun 1992 pengembang program Chinook melakukan pertemuan dengan anggota Natural Sciences and Engineering Council of Canada (NSERC), penyokong

68

utama dana untuk riset ilmiah di kanada. Dia bertanya kepada NSERC mengapa permintaanya untuk pembiayaan riset kecerdasan buatan dengan menggunakan bahan permainan checkers dihentikan. NSERC menjawab, “Bukankah Samuel telah memecahkan permainan tersebut 30 tahun yang lalu? ”

2.9.2

Penjelasan Chinook Dalam permainan checkers, hanya 32 kotak dari 64 kotak pada papan permainan

yang digunakan. papan diposisikan dengan kotak hitam di pojok kiri atas dan pojok kanan bawah. Kotak yang mungkin di tempati oleh bidak permainan diberi nomor satu sampai 32. Jika pemain bermain dengan menggunakan bidak berwarna putih, penomoran bidak di mulai dari kiri ke kanan dari baris atas ke bawah. Dua gambar di bawah menunjukan posisi awal permainan dengan bidak hitam ada di puncak, dan penomoran kotak permainan.

Gambar 2.22 Pemain memainkan bidak putih

Jika pemain bermain dengan bidak berwarna hitam, penomoran bidak di mulai dari kanan ke kiri dari baris bawah ke atas. Dua gambar di bawah menunjukan posisi awal permainan dengan bidak putih ada di puncak, dan penomoran kotak permainan.

69

Gambar 2.23 Pemain memainkan bidak hitam

Sebuah langkah menggambarkan titik awal dan titik akhir letak bidak saat bidak tersebut melangkah dengan dipisahkan oleh tanda '-'. Sebagai contoh, jika pemain memainkan bidak berwarna hitam dan menjalankan langkah 11-15 sebagai langkah pertamamu dari posisi awal, kamu akan melihat posisi ini:

Gambar 2.24 Langkah awal 11-15 Tidak seperti catur, kenaikan pangkat bidak tidak muncul sebagai bagian dari notasi. Tata cara dalam perhitungan notasi ini digunakan untuk semua permainan Chinook's.

70

2.10

Algoritma Genetik Algoritma genetik adalah algoritma komputasi yang diinspirasi teori evolusi

yang kemudian di adopsi menjadi algoritma komputasi untuk mencari solusi suatu permasalahan dengan cara yang lebih “alamiah”. Salah satu aplikasi algoritma genetik adalah pada permasalahan optimasi kombinasi, yaitu mendapatkan suatu nilai solusi optimal terhadap suatu permasalahan yang mempunyai banyak kemungkinan solusi. (http://ilmukomputer.com/2006/08/19/pengenalan-algoritma-genetik/)

2.10.1 Teori Genetika Teori genetika pertama kali dikemukakan oleh Charles Darwin yang bisa disebut juga teori evolusi. Darwin menyatakan bahwa kelangsungan hidup suatu makhluk dipengaruhi aturan “yang kuat adalah yang menang”. (Suyanto,2005) Darwin juga menyatakan bahwa kelangsungan hidup suatu makhluk dapat dipertahankan melalui proses reproduksi, crossover, dan mutasi. Konsep dalam teori evolusi Darwin tersebut kemudian diadopsi menjadi algoritma komputasi untuk mencari solusi suatu permasalahan dengan cara yang lebih “alamiah”.

2.10.2 Dasar Algoritma Genetik Dalam algoritma genetika sebuah solusi yang di bangkitkan dalam algoritma genetik disebut sebagai chromosome, sedangkan kumpulan chromosome-chromosome tersebut disebut sebagai populasi. Sebuah chromosome di bentuk dari komponenkomponen penyusun yang disebut sebagai gen dan nilainya dapat berupa bilangan numerik, biner, simbol ataupun karakter tergantung dari permasalahan yang ingin diselesaikan. Chromosome-chromosome tersebut akan berevolusi secara berkelanjutan

71

yang disebut dengan generasi. Dalam tiap generasi chromosome-chromosome tersebut dievaluasi tingkat keberhasilan nilai solusinya terhadap masalah yang ingin diselesaikan (fungsi_objektif) menggunakan ukuran yang disebut dengan fitness. Untuk memilih chromosome yang tetap dipertahankan untuk generasi selanjutnya dilakukan proses yang disebut dengan seleksi. Proses seleksi chromosome menggunakan konsep aturan evolusi Darwin yang telah disebutkan sebelumnya yaitu chromosome yang mempunyai nilai fitness tinggi akan memiliki peluang lebih besar untuk terpilih lagi pada generasi selanjutnya. Chromosome-chromosome baru yang disebut dengan offspring, dibentuk dengan cara melakukan perkawinan antar chromosome-chromosome dalam satu generasi yang disebut sebagai proses crossover. Jumlah chromosome dalam populasi yang mengalami crossover ditentukan oleh paramater yang disebut dengan crossover_rate. Mekanisme perubahan susunan unsur penyusun mahkluk hidup akibat adanya faktor alam yang disebut dengan mutasi direpresentasikan sebagai proses berubahnya satu atau lebih nilai gen dalam chromosome dengan suatu nilai acak. Jumlah gen dalam populasi yang mengalami mutasi ditentukan oleh parameter yang dinamakan mutation_rate. Setelah beberapa generasi akan dihasilkan chromosome-chromosome yang nilai gen-gennya konvergen ke suatu nilai tertentu yang merupakan solusi terbaik yang dihasilkan oleh algoritma genetika terhadap permasalahan yang ingin diselesaikan.

72

Contoh aplikasi Algoritma Genetika pada permasalahan Linear Programming Berikut adalah contoh aplikasi algoritma genetika yang digunakan untuk menyelesaikan masalah kombinasi. Misalkan ada persamaan a+2b+3c+4d = 30, kita mencari nilai a, b, c, dan d yang memenuhi persamaan diatas. Kita mencoba menggunakan algoritma genetika untuk menyelesaikan permasalahan diatas. Diagram alir dari algoritma genetika untuk menyelesaikan permasalahan diatas dapat dilihat pada Gambar 2.5

73

Gambar 2.25 Diagram alir algoritma genetik

74

Penjelasan mengenai langkah-langkah penyelesaian permasalahan diatas menggunakan algoritma genetika adalah sebagai berikut:

c.

Pembentukan chromosome Karena yang dicari adalah nilai a, b, c, d maka variabel a, b, c, d dijadikan

sebagai gen-gen pembentuk chromosome. Batasan nilai variabel a adalah bilangan integer 0 sampai 30. Sedangkan batasan nilai variabel b, c, dan d adalah bilangan integer 0 sampai 10. d.

Inisialisasi Proses inisialisasi dilakukan dengan cara memberikan nilai awal gen-gen dengan

nilai acak sesuai batasan yang telah ditentukan. Misalkan kita tentukan jumlah populasi adalah enam, maka: Chromosome[1] = [a;b;c;d] = [12;05;03;08] Chromosome[2] = [a;b;c;d] = [02;01;08;03] Chromosome[3] = [a;b;c;d] = [10;04;03;04] Chromosome[4] = [a;b;c;d] = [20;01;10;06] Chromosome[5] = [a;b;c;d] = [01;04;03;09] Chromosome[6] = [a;b;c;d] = [20;05;07;01] e.

Evaluasi Chromosome Permasalahan yang ingin diselesaikan adalah nilai variabel a, b, c, dan d yang

memenuhi persamaan a+2b+3c+4d = 30, maka fungsi_objektif yang dapat digunakan untuk mendapatkan solusi adalah fungsi_objektif(chromosome) = | (a+2b+3c+4d) – 30 | Kita hitung fungsi_objektif dari chromosome yang telah dibangkitkan:

75

fungsi_objektif(chromosome[1]) = Abs(( 12 + 2*5 + 3*3 + 4*8 ) - 30) = Abs((12 + 10 + 9 + 32 ) - 30) = Abs(63 - 30) = 33 fungsi_objektif(chromosome[2]) = Abs(( 2 + 2*1 + 3*8 + 4*3 ) - 30) = Abs(( 2 + 2 + 24 + 12 ) - 30) = Abs(40 - 30) = 10 fungsi_objektif(chromosome[3]) = Abs(( 10 + 2*4 + 3*3 + 4*4 ) - 30) = Abs(( 10 + 8 + 9 + 16 ) - 30) = Abs(43 - 30) = 13 fungsi_objektif(chromosome[4]) = Abs(( 20 + 2*1 + 3*10 + 4*6 ) - 30) = Abs(( 20 + 2 + 30 + 24 ) - 30) = Abs(76 - 30) = 46 fungsi_objektif(chromosome[5]) = Abs(( 1 + 2*4 + 3*3 + 4*9 ) - 30) = Abs(( 1 + 8 + 9 + 36 ) - 30) = Abs(54 - 30) = 24 fungsi_objektif(chromosome[6]) = Abs(( 20 + 2*5 + 3*7 + 4*1 ) - 30) = Abs(( 20 + 10 + 21 + 4) - 30) = Abs(55 - 30) = 25

76

Rata-rata dari fungsi objektif adalah: rata-rata = (33+10+13+46+24+25)/6 = 151 / 6 = 25.167 f.

Seleksi Chromosome Proses seleksi dilakukan dengan cara membuat chromosome yang mempunyai

fungsi_objektif kecil mempunyai kemungkinan terpilih yang besar atau mempunyai nilai probabilitas

yang

tinggi.

Untuk

itu

dapat

digunakan

fungsi

fitness

=

(1/(1+fungsi_objektif)), fungsi_objektif perlu ditambah satu untuk menghindari kesalahan program yang diakibatkan pembagian oleh nol.

fitness[1]

= 1 / (fungsi_objektif[1]+1) = 1 / 34 = 0.0294

fitness[2]

= 1 / (fungsi_objektif[2]+1) = 1 / 11 = 0.0909

fitness[3]

= 1 / (fungsi_objektif[3]+1) = 1 / 14 = 0.0714

fitness[4]

= 1 / (fungsi_objektif[4]+1) = 1 / 47 = 0.0212

77

fitness[5]

= 1 / (fungsi_objektif[5]+1) = 1 / 25 = 0.0400

fitness[6]

= 1 / (fungsi_objektif[6]+1) = 1 / 26 = 0.0385

total_fitness

= 0.0294 + 0.0909 + 0.0714 + 0.0212 + 0.04 + 0.0385 = 0.2914

Rumus untuk mencari probabilitas: P[i] = fitness[i] / total_fitness P[1] = 0.0294 / 0.2914 = 0.1009 P[2] = 0. 0909 / 0.2914 = 0.3119 P[3] = 0. 0714 / 0.2914 = 0.2450 P[4] = 0. 0212 / 0.2914 = 0.0728 P[5] = 0.04 / 0.2914 = 0.1373 P[6] = 0.0385 / 0.2914 = 0.1321 Dari probabilitas diatas dapat kita lihat kalau chromosome kedua yang mempunyai fitness paling besar maka chromosome tersebut mempunyai probabilitas untuk terpilih pada generasi selanjutnya lebih besar dari chromosome lainnya. Untuk

78

proses seleksi kita gunakan roulete wheel, untuk itu harus mencari dahulu nilai kumulatif probabilitasnya: C[1] = 0.1009 C[2] = 0.1009+ 0.3119 = 0.4128 C[3] = 0.1009+ 0.3119 + 0.2450 = 0.6578 C[4] = 0.1009+ 0.3119 + 0.2450 + 0.0728 = 0.7306 C[5] = 0.1009+ 0.3119 + 0.2450 + 0.0728 + 0.1373 = 0.8679 C[6] = 0.1009+ 0.3119 + 0.2450 + 0.0728 + 0.1373 + 0.1321 =1 Setelah dihitung cumulative probabilitasnya maka proses seleksi menggunakan roulete-wheel dapat dilakukan. Prosesnya adalah dengan membangkitkan bilangan acak R dalam range 0-1. Jika R[k] < C[1] maka pilih chromosome satu sebagai induk, selain itu pilih chromosome ke-k sebagai induk dengan syarat C[k-1] < R < C[k]. Putar roulete wheel sebanyak jumlah populasi yaitu enam kali (bangkitkan bilangan acak R) dan pada tiap putaran, pilih satu chromosome untuk populasi baru. Misalnya: R[1] = 0.201 R[2] = 0.284 R[3] = 0.009 R[4] = 0.822

79

R[5] = 0.398 R[6] = 0.501 Angka acak pertama R[1] adalah lebih besar dari C[1] dan lebih kecil daripada C[2] maka pilih chromosome[2] sebagai chromosome pada populasi baru, dari bilangan acak yang telah dibangkitkan diatas maka populasi chromosome baru hasil proses seleksi adalah: chromosome[1] = chromosome[2] chromosome[2] = chromosome[2] chromosome[3] = chromosome[1] chromosome[4] = chromosome[5] chromosome[5] = chromosome[2] chromosome[6] = chromosome[3] Chromosome baru hasil proses seleksi: chromosome[1] = [02;01;08;03] chromosome[2] = [02;01;08;03] chromosome[3] = [12;05;03;08] chromosome[4] = [01;04;03;09] chromosome[5] = [02;01;08;03] chromosome[6] = [10;04;03;04] g.

Crossover Setelah proses seleksi maka proses selanjutnya adalah proses crossover. Metode

yang digunakan salah satunya adalah one-cut point, yaitu memilih secara acak satu posisi dalam chromosome induk kemudian saling menukar gen. Chromosome yang

80

dijadikan induk dipilih secara acak dan jumlah chromosome yang mengalami crossover dipengaruhi oleh parameter crossover_rate ( ρc ). Pseudo-code untuk proses crossover adalah sebagai berikut: begin k← 0; while(k<populasi) do R[k] ← random(0-1); if (R[k] < ρc ) then select Chromosome[k] as parent; end; k = k + 1; end; end;

Misal kita tentukan crossover probability adalah sebesar 25%, maka diharapkan dalam satu generasi ada 50% Chromosome (tiga chromosome) dari satu generasi mengalami proses crossover. Prosesnya adalah sebagai berikut: Pertama kita bangkitkan bilangan acak R sebanyak jumlah populasi R[1] = 0.191 R[2] = 0.259 R[3] = 0.760 R[4] = 0.006 R[5] = 0.159 R[6] = 0.340

81

Maka Chromosome ke k akan dipilih sebagai induk jika R[k] < ρc, dari bilangan acak R diatas maka yang dijadikan induk adalah chromosome[1], chromosome[4] dan chromosome[5]. Setelah melakukan pemilihan induk proses selanjutnya adalah menentukan posisi crossover. Ini dilakukan dengan cara membangkitkan bilangan acak dengan batasan satu sampai (panjang chromosome-1), dalam kasus ini bilangan acak yang dibangkitkan adalah satu sampai tiga. Misalkan didapatkan posisi crossover adalah satu maka chromosome induk akan dipotong mulai gen kesatu kemudian potongan gen tersebut saling ditukarkan antar induk. chromosome[1] >< chromosome[4] chromosome[4] >< chromosome[5] chromosome[5] >< chromosome[1] Posisi cut-point crossover dipilih menggunakan bilangan acak satu sampai tiga sebanyak jumlah crossover yang terjadi, misal C[1] = 1 C[2] = 1 C[3] = 2 offspring[1] = chromosome[1] >< chromosome[4] = [02;01;08;03] >< [01;04;03;09] = [02;04;03;09] offspring[4] = Chromosome[4] >< Chromosome[5] = [01;04;03;09] >< [02;01;08;03] = [01;01;08;03]

82

offspring[5] = Chromosome[5] >< Chromosome[1] = [02;01;08;03] >< [02;01;08;03] = [02;01;08;03] Dengan demikian populasi Chromosome setelah mengalami proses crossover menjadi: chromosome[1] = [02;04;03;09] chromosome[2] = [02;01;08;03] chromosome[3] = [12;05;03;08] chromosome[4] = [01;01;08;03] chromosome[5] = [02;01;08;03] chromosome[6] = [10;04;03;04]

h.

Mutasi Jumlah chromosome yang mengalami mutasi dalam satu populasi ditentukan

oleh parameter mutation_rate. Proses mutasi dilakukan dengan cara mengganti satu gen yang terpilih secara acak dengan suatu nilai baru yang didapat secara acak. Prosesnya adalah sebagai berikut. Pertama kita hitung dahulu panjang total gen yang ada dalam satu populasi. Dalam kasus ini panjang total gen adalah total_gen = (jumlah gen dalam chromosome) * jumlah populasi =4*6 = 24 Untuk memilih posisi gen yang mengalami mutasi dilakukan dengan cara membangkitkan bilangan integer acak antara satu sampai total_gen, yaitu satu sampai 24. Jika bilangan acak yang kita bangkitkan lebih kecil daripada variabel mutation_rate (ρm) maka pilih posisi tersebut sebagai sub-chromosome yang mengalami mutasi. Misal

83

ρm kita tentukan 10% maka diharapkan ada 10% dari total_gen yang mengalami populasi: jumlah mutasi = 0.1 * 24 = 2.4 =2 Misalkan setelah kita bangkitkan bilangan acak terpilih posisi gen 12 dan 18 yang mengalami mutasi. Dengan demikian yang akan mengalami mutasi adalah chromosome ketiga gen nomor empat dan Chromosome kelima gen nomor dua. Maka nilai gen pada posisi tersebut kita ganti dengan bilangan acak nol sampai tigapuluh. Misalkan bilangan acak yang terbangkitkan adalah dua dan lima. Maka populasi chromosome setelah mengalami proses mutasi adalah: chromosome[1] = [02;04;03;09] chromosome[2] = [02;01;08;03] chromosome[3] = [12;05;03;02] chromosome[4] = [01;01;08;03] chromosome[5] = [02;05;08;03] chromosome[6] = [10;04;03;04] Setelah proses mutasi maka kita telah menyelesaikan satu iterasi dalam algoritma genetika atau disebut dengan satu generasi. Maka fungsi_objective setelah satu generasi adalah:

84

chromosome[1]

= [02;04;03;09]

fungsi_objektif[1]

= Abs(( 2 + 2*4 + 3*3 + 4*9 ) - 30) = Abs(( 2 + 8 + 9 + 36 ) - 30) = Abs( 55 - 30) = 25

chromosome[2]

= [02;01;08;03]

fungsi_objektif[2] = Abs(( 2 + 2*1 + 3*8 + 4*3 ) - 30) = Abs(( 2 + 2 + 24 + 12 ) - 30) = Abs(40 - 30) = 10 chromosome[3]

= [12;05;03;02]

fungsi_objektif[3] = Abs(( 12 + 2*5 + 3*3 + 4*2 ) - 30) = Abs(( 12 + 10 + 9 + 8 ) - 30) = Abs(39 - 30) =9 chromosome[4]

= [01;01;08;03]

fungsi_objektif[4] = Abs(( 1 + 2*1 + 3*8 + 4*3 ) - 30) = Abs(( 1 + 2 + 24 + 12 ) - 30) = Abs(39 - 30) =9

85

chromosome[5]

= [02;05;08;03]

fungsi_objektif[5] = Abs(( 2 + 2*5 + 3*8 + 4*3 ) - 30) = Abs(( 2 + 10 + 24 + 12 ) - 30) = Abs(48 - 30) = 18 chromosome[6]

= [10;04;03;04]

fungsi_objektif[6] = Abs(( 10 + 2*4 + 3*3 + 4*4 ) - 30) = Abs(( 10 + 8 + 9 + 16 ) - 30) = Abs(43 - 30) = 13 Rata-rata fungsi objektif setelah satu generasi adalah: rata-rata = ( 25 + 10 + 9 + 9 + 18 + 13) / 6 = 84 / 6 = 14.0

Dapat dilihat dari hasil perhitungan fungsi objektif diatas bahwa setelah satu generasi, nilai hasil rata-rata fungsi_objektif lebih menurun dibandingkan hasil fungsi_objektif pada saat sebelum mengalami seleksi, crossover dan mutasi. Hal ini menunjukkan bahwa chromosome atau solusi yang dihasilkan setelah satu generasi lebih baik dibandingkan generasi sebelumnya. Maka pada generasi selanjutnya chromosomechromosome yang baru adalah: chromosome[1] = [02;04;03;09] chromosome[2] = [02;01;08;03] chromosome[3] = [12;05;03;02]

86

chromosome[4] = [01;01;08;03] chromosome[5] = [02;05;08;03] chromosome[6] = [10;04;03;04] Chromosome-chromosome ini akan mengalami proses yang sama seperti generasi sebelumnya yaitu proses evaluasi, seleksi, crossover dan mutasi yang kemudian akan menghasilkan chromosome-chromosome baru untuk generasi yang selanjutnya. Proses ini akan berulang sampai sejumlah generasi yang telah ditetapkan sebelumnya. Setelah 50 generasi didapatkan chromosome yang terbaik adalah: Chromosome = [07;05;03;01] Jika didekode maka: a=7 ; b=5 ; c=3 ; d=1 Jika dihitung terhadap persamaan f = a+2b+3c+4d: 7 + (2*5) + (3*3) + (4*1) = 30