BAB I

PENDAHULUAN

1.1 Latar Belakang

Pada era globalisasi saat ini teknlogi berkembang pesat. Teknologi hampir memasuki

semua lini kehidupan. Dalam makalah ini lebih membahas teknologi yang memasuki dunia

hiburan terutama bidang permainan.

Teknologi yang sering dijumpai dalam permainan sekarang ini adalah teknologi

kecerdasan buatan (AI).Kecerdasan buatan adalah Teknologi yang mensimulasikan kecerdasan

manusia, yaitu bagaimana mendefinisikan dan mencoba menyelesaikan persoalan menggunakan

computer dengan meniru bagaimana manusia menyelesaikan dengan cepat.

Pemainan sudah ada sejak jaman dahulu. Permainan merupakan sebuah aktivitas rekreasi

dengan tujuan bersenang-senang, mengisi waktu luang, atau berolahraga ringan. Permainan

biasanya dilakukan sendiri atau bersama-sama (kelompok). Orthello adalah pemainan sederhana

yang menerapkan teknologi terkini untuk memenangkannya.

Setelah membaca makalah ini para pembaca diharapkan lebih bias memanfaatkan

teknologi di semua lini kehidupan termasuk dalam sebuah permainan.

1.2 Tujuan

Mengetahui teknologi kecerdasan buatan pada sebuah permainan

Dapat menggunakan kemajuan teknologi dalam permainan.

Membuat mesin lebih bermanfaat

1.3 Manfaat

Teknologi kecerdasan buatan dapat dimanfaatkan dalam permainan.

Menambah ilmu tentang memenangkan permaianan dengan kecerdasan buatan

BAB 2

PERUMUSAN MASALAH

Sehubungan dengan latar belakang diatas timbul permasalahan,permasalahan tersebut

dapat dirumuskan sebagai berikut :

1. Apa itu kecerdasan buatan ?

2. Apa yang terkandung dalam kecerdasan buatan?

3. Syarat game playing apa saja?

4. Bagaiaman cara memenangkan game orthello menggunakan teknologi kecerdasan

buatan?

BAB II

PEMBAHASAN

Kecerdasan buatan memeliki beberapa definisi menurut beberapa sumber, berikut definisi

dari kecerdasan buatan atau kita kenal dgn AI

H. A. Simon [1987] :

“ Kecerdasan buatan (artificial intelligence) merupakan kawasan penelitian, aplikasi dan

instruksi yang terkait dengan pemrograman komputer untuk melakukan sesuatu hal yang -dalam

pandangan manusia adalah- cerdas”

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

· 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”

Dengan beberapa definisi diatas, Kecerdasan Buatan menawarkan baik media maupun

teori kecerdasan. Teori-teori ini dapat dinyatakan dalam bahasa program computer dan

dibuktikan eksekusinya pada computer nyata.

Program computer standar hanya bias menyelesaikan persoalan yang di program secara

spesifik. Jika sebuah program standar perlu dirubah untuk menyesuaikan diri dengan informasi

baru, seluruh program harus dilihat satu persatu sampai kita dapatkan ruang optimal untuk

meyisipkan perubahan atau modifikasi tersebut. Cara seperti ini tidak hanya memboroskan

waktu, namun juga dapat menghilangkan bagian tertentu dari program sehingga mudah

timbulnya error.

Sebaliknya kecerdasan buatan dapat memungkinkan computer ‘berfikir’.Dengan cara

menyederhanakan program. Kecerdasan buatan dapat menirukan proses belajar manusia

sehingga informasi baru dapat diserap tanpa mempengaruhi informasi lain yang lebih dahulu

tersimpan.Teknik yang digunakan dalam kecerdasan buatan memungkinkan dibuatnya sebuah

program yang berjalan secara indepeden dan dapat diidentifikasi dengan baik untuk memecahkan

suatu persoalan.

Kecerdasan Buatan sendiri dimunculkan oleh seorang professor dari Massachusetts

Institute of Technology (MIT) yang bernama John McCarthy pada tahun 1956 pada saat

Dartmouth Conference yang dihadiri oleh parapeneliti AI.

Kecerdasan buatan dapat dipilah menjadi sejumlah sub disiplin ilmu diantaranya :

1. Sistem pakar

2. Pengolahan bahasa alami

3. Speech recognition

4. Robotika dan sensor

5. Machine learning

6. Game playing

Dalam makalah kali ini pembahasan lebih tertuju kepada sub game playing.Game playing

memiliki beberapa karakteristik dan batasan diantaranya :

Dimainkan oleh 2 (dua) pemain: manusia dan komputer. Para pemain saling bergantianmelangkah.

Perfect Information Game: kedua pemain sama-sama memiliki akses pada informasiyang lengkap tentang keadaan permainan, sehingga tidak ada informasi yang tertutupbagi lawan mainnya.

No Determined by Chances. Tidak melibatkan faktor probabilitas, misalnya denganmenggunakan dadu.

No Phsychological Factors. Tidak melibatkan faktor psikologi, seperti "gertakan"(misalnya Poker)

No Oversight Errors. Smart Opponent. Lawan diasumsikan pintar juga, jadi janganmengharap lawan khilaf, sehingga terjadi salah langkah.

Game playing yang dibahas kali ini adalah orthello. Sejarah othello berawal tahun 1945,

setelah bom atom dijatuhkan di Hiroshima dan Nagasaki. September 1945, Hasegawa Goro yang

tengah duduk di kelas satu SMP menerima pelajaran sembari duduk di tanah di bawah langit

biru. Mito juga menjadi sasaran pengeboman hingga kastil dan bangunan bersejarah lain ikut

habis dalam kobaran api. Dalam suasana seperti itulah permainan ini dilahirkan. Aturan awalnya,

bila batu milik pemain pertama diapit oleh batu milik pemain kedua, maka batu pemain pertama

menjadi milik pemain kedua. Permainan ini cukup merepotkan karena harus dipakai kertas yang

diwarnai hitam pada salah satu sisi dan putih pada sisi yang lain. Sebenarnya asal kata othello itu

sendiri, bukan dari bahasa Jepang. Ayah Hasegawa Goro, memberikan nama ini dari salah satu

karya Shakespeare dengan judul yang sama. Othello dalam karya Shakespeare tersebut

mengisahkan seorang kulit hitam yang mempunyai istri kulit putih yang cantik bernama

Desdemona.

Karena permainan orthello ini pada awalnya menggunakan kertas yang dwarnai terlebih

dahulu,akhirnya permainan ini memakai batu dengan 2 warna. Permainan othello dimainkan

pada arena papan kotak-kotak persegi dengan koin hitam dan putih diatas arena. Pada awal

permainan diletakkan dua koin hitam dan dua koin putih pada pusat arena. Koin warna hitam

harus melewati koin warna putih agar

koin putih dapat diubah menjadi koin hitam, dan sebaliknya. Permainan akan berakhir jika

semua kotak arena sudah terisi koin, atau seluruh koin yang ada di atas arena berwarna sama.

Pemenang adalah pemain yang memiliki jumlah koin lebih banyak diatas arena. Permainan ini di

luar negeri lebih dikenal dengan nama Reversi. Saat ini Othello tidak hanya dimainkan secara

tradisional, namun sudah banyak dibuat dalam bentuk animasi pada komputer.

Permainan Othello dimainkan oleh dua orang pemain. Permainan ini dimainkan di atas

papan arena permainan persegi yang terdiri dari kotak-kotak kecil, biasanya berukuran 8x8

kotak. Peralatan lain yang dibutuhkan ialah koin hitam dan koin putih masing-masing sebanyak

64 buah. Pada awal permainan akan diletakkan dua koin hitam dan dua koin putih pada pusat

arena. Misalkan pemain pertama menggunakan koin hitam dan pemain kedua menggunakan koin

putih. Koin hitam harus dapat ‘melompati’ koin putih agar koin putih dapat menjadi hitam.

Setelah koin hitam berpindah posisi dan koin-koin yang dilalui diubah warnanya menjadi hitam,

koin putih yang mendapat giliran untuk berpindah. Koin putih harus ‘melompati’ koin hitam agar

koin tersebut dapat diganti menjadi koin putih. Kedua pemain terus menerus secara bergantian

memindahkan letak koin masing-masing. Hanya 1 koin yang dapat dipindahkan setiap kali

giliran jalan. Gerakan koin dapat lurus maupun diagonal asalkan setiap pergerakan membentuk

satu garis lurus. Permainan akan berakhir jika seluruh kotak-kotak kecil pada arena permainan

terisi koin atau seluruh koin di atas arena berwarna sama. Pemenang ialah pemain yang

memiliki jumlah koin paling banyak di atas arena permainan.

Dengan memanfaatkan kecerdasan buatan di era teknologi sekarang ini permainan

orthello lebih asyik dimainkan. Materi-materi yang bias digunakan di dalam permainan orthello

diantaranya : negascout, memory-enhanced test driver value f, fungsi evaluasi, dan algoritma

greedy.

Dibawah ini akan dijelaskan satu persatu menegnai langkah-langkah diatas.

1. Negascout

Negascout adalah salah satu metode pencarian minimax dengan berasumsi bahwa langkah

pertama yang diambil merupakan langkah terbaik, sedangkan sisanya merupakan langkah

terburuk (Aske Plaat,1994). Namun jika ternyata ada langkah yang lebih baik dari langkah

pertama, maka akan terjadi proses research atau proses pencarian ulang. Berikut penjelasan

algoritma Negascout yang dijabarkan pada gambar 1.

Gamabr 1. Algoritma Negascout

Pada algoritma dari gambar 1, syarat untuk melakukan research adalah jika nilai dari t

lebih besar dari B, lebih kecil dari beta, bukan anak pertama dari node yang diproses (i>1), dan

pada node tersebut harus mempunyai anak sampai kedalaman lebih besar dari satu (depth>1).

Syarat t lebih kecil dari beta diperlukan karena jika t lebih besar dari beta, maka beta pruning

akan diproses sehingga proses research tidak akan terjadi.

2. Memory-enhanced Test Driver value f

Pencarian pada MTDF menggunakan bound sebagai tempat penyimpanan nilai minimax,

dimana bound tersebut terbagi menjadi 2 macam, yaitu upperbound dan lowerbound yang

menunjukkan rentang dimana nilai minimax berada (Aske Plaat,1994). Cara kerja dari algoritma

mtdf adalah dengan cara melakukan serangkaian pemanggilan algoritma

alpha beta secara berulang-ulang. Berikut penjelasan algoritma MTDF yang dijabarkan pada

gambar 2.

Gambar 2. Algoritma MTDF

Pada algoritma gambar 2, parameter f merupakan nilai perkiraan. Jika nilai dari parameter

tersebut mendekati nilai minimax maka proses pemanggilan terhadap algoritma alpha beta akan

semakin sedikit. Minimal dilakukan dua kali proses pemanggilan, dimana untuk menentukan

nilai dari upperbound dan lowerbound . Proses pemanggilan algoritma alpha beta akan berhenti

jika nilai dari lowerbound lebih besar dari upperbound. Algoritma alpha beta yang digunakan

sedikit berbeda dengan algoritma alpha beta konvensional. Dimana pada algoritma alpha beta

with memory menyimpan nilai upperbound dan lowerbound setiap node, yang nantinya

digunakan untuk perbandingan dengan nilai alpha dan beta yang didapat. Berikut penjelasan

algoritma alpha beta with memory yang dijabarkan pada gambar 3. Pada algoritma gambar 3,

dapat dilihat pada baris 1, merupakan proses pengambilan nilai upperbound dan lowerbound

yang kemudian dicek dengan nilai alpha beta saat itu, dari situ akan banyak pruning yang akan

dihasilkan. Pruning terjadi untuk lowerbound jika nilai lowerbound lebih besar sama dengan

nilai beta, kemudian nilai yang dikembalikan adalah nilai lowerbound saat itu. Pruning terjadi

untuk upperbound jika nilai upperbound kurang dari sama dengan nilai alpha, kemudian nilai

yang dikembalikan adalah nilai upperbound saat itu.

Gambar 3. Algoritma alpha beta with memory.

Pada algoritma gambar 3, untuk baris ke 3 dan 4 merupakan proses penyimpanan nilai

upperbound dan lowerbound kedalam memory node saat itu. Untuk baris 2 terlihat sama dengan

algoritma pada alpha beta konvensional. Jadi pada algoritma alpha beta with memory, terdapat

tambahan algoritma untuk menyimpan nilai upperbound dan lowerbound, yang mana nilai

minimax berada diantara nilai upperbound dan lowerbound.

3. Fungsi Evaluasi

Banyak orang beranggapan bahwa yang terpenting dalam memenangkan permainan

Othello adalah jumlah disc yang dapat dibalik atau dirubah pada tiap kali kesempatan. Anggapan

tersebut tidaklah benar, yang terpenting dalam permainan tersebut sebenarnya ada pada jumlah

langkah yang dapat diambil disebut juga dengan mobility. Semakin banyak mobility yang

didapat maka akan semakin banyak pula langkah-langkah bagus yang dapat dimainkan. Berikut

beberapa fungsi evaluasi yang digunakan beserta komponen pendukungnya, antara lain edge

table, mobility, liberties, frontier dan penguasaan corner.

3.1 Edge Table

Edge table merupakan wadah untuk menyimpan nilai-nilai mobility dari papan

permainan. Cara kerja edge table adalah dengan hanya mengevaluasi satu sisi papan, yang mana

selanjutnya hanya perlu mencerminkannya kesemua sisi-sisi pada papan permainan. Berikut

penjelasan berupa gambar contoh cara penyimpanan nilai pada edge table.

Gambar 4.Penyimpanan edge table

Maksud dari penjelasan pada gambar 4 adalah jika misalkan terdapat pola pada salah satu

sisi papan 00001020 (0 menunjukkan petak kosong, 1 disc putih, 2 disc hitam), maka nilai dari

hasil pola tersebut akan disimpan pada edge table pada index ke-33. Selanjutnya data yang telah

tersimpan dalam edge table akan diolah oleh mobility.

3.2 Mobility

Seperti yang telah dijelaskan sebelumnya bahwa mobility merupakan jumlah langkah

yang dapat dimainkan oleh pemain pada tiap kali kesempatan. Jumlah langkah ini didapat

dengan mengevaluasi pola pada satu sisi papan dan selanjutnya disimpan kedalam edge table.

Berikut penjelasan berupa gambar tabel, yang berisi mengenai beberapa contoh cara

mengevaluasi nilai mobility.

Tabel 1. Contoh evaluasi mobility

Pada tabel 1, pada kolom pola terdapat tanda panah ke atas, yang menunjukkan posisi-posisi

dimana pemain dapat meletakkan disc. Pemberian nilai pada kolom mobility ini berdasarkan

jumlah posisi disc yang dapat diletakkan dan harus sesuai dengan jenis disc yang

diletakkan.Berikut langkahlangkah yang diperlukan mulai dari awal hingga

didapat nilai mobility total untuk keseluruhan sisi papan.

a. Siapkan 5 jenis edge table dengan ukuran penampung berbeda-beda. Edge untuk 8 petak

dengan ukuran 6561, 7 petak ukuran 2187, 6 petak 729, 5 petak 243 dan 4 petak 81.

Diperlukan edge untuk menampung 7 sampai 4 petak, karena untuk mengevaluasi petak

dengan sisi diagonal.

b. Proses semua kombinasi pola pada satu sisi papan mulai dari 00000000 sampai 22222222

dan hitung jumlah mobility yang ada seperti pada contoh tabel evaluasi mobility,

kemudian simpan kedalam edge table.

c. Evaluasi seluruh sisi papan, baik horisontal, vertikal dan diagonal. Keseluruhan ada 34

sisi yang diproses, 8 sisi horisontal, 8 sisi vertical dan 18 sisi diagonal.

Setelah mengetahui bagaimana langkah-langkah yang diperlukan dalam mengevaluasi

nilai mobility, selanjutnya akan dijelaskan mengenai contoh permasalahan yang mungkin terjadi

papan permainan. Berikut contoh gambar permasalahan yang mungkin terjadi, dapat dilihat pada

gambar 5.

Gambar 5. Contoh permasalahan papan.

Berikut penjelasan mengenai cara perhitungan berdasarkan pada gambar 6. Sebelumnya

perlu diketahui untuk perhitungan hanya untuk disc putih dan sisi-sisi yang dilingkari saja yang

akan dihitung (pada penerapan, seluruh sisi horisontal, vertikal dan diagonal perlu dihitung).

Mobility 1 = 0 ← Edge_Tabel[35 x 2 + 34 x 2+ 33 x 2 = 702]

Mobility 2 = 1 ← Edge_ Tabel[34 x 1 + 33 x 2 = 135]

Mobility 3 = 0 ← Edge_ Tabel[34 x 1 = 81]

Mobility 4 = 0 ← Edge_ Tabel[34 x 2 = 162]

Mobility 5 = 1 ← Edge_ Tabel[34 x 2 + 33 x 1 + 32 x 1 = 198]

Mobility 6 = 0 ← Edge_ Tabel[34 x 2 + 33 x 2 = 216]

Nilai evaluasi = Mobility 1 + … +

Mobility 6

= 0 + 1 + 0 + 0 + 1 + 0 = 2

Berdasarkan pada contoh permasalahan yang terjadi pada papan pada gambar 6 dan hasil

perhitungan nilai mobility yang telah dilakukan dapat disimpulkan bahwa nilai evaluasi total

yang didapat untuk disc putih adalah 2. Nilai evaluasi total berdasarkan perhitungan yang telah

dilakukan didapat dengan cara menjumlahkan seluruh mobility yang didapat dari hasil evaluasi

yang telah diproses untuk sisi horisontal dan vertikal dari contoh permasalahan pada gambar 5.

3.3 Liberties

Liberties digunakan untuk menampung jumlah petak kosong yang berada disekeliling

tiap-tiap petak pada papan. Berikut nilai-nilai yang disimpan kedalam liberties dapat dilihat pada

gambar inisialisasi nilai-nilai liberties.

Gambar 6.Inisialisasi nilai-nilai Liberties

Setelah proses penyimpanan nilai-nilai liberties dilakukan, selanjutnya nilai-nilai yang

disimpan tersebut akan diproses oleh frontier untuk mengetahui jumlah disc yang berbatasan

dengan petak kosong.

3.4 Potential Mobility atau Frontier

Frontier merupakan jumlah disc yang berbatasan dengan petak kosong. Jika terjadi

kondisi dimana semakin banyak frontier yang didapat, maka akan semakin jelek pula posisinya,

karena semakin banyak frontier memungkinkan lawan untuk mendapatkan semakin banyak

mobility tambahan pada beberapa langkah ke depan dan juga mengurangi mobility-nya sendiri.

Berikut penjelasan berupa gambar contoh nilai-nilai liberties dan papan, untuk selanjutnya

dihitung frontiernya. Berdasarkan gambar 7 cara menghitung frontieradalah jumlahkan

banyaknya disc pada papan dengan melihat nilai-nilai pada liberties yang lebih

besar dari nol. Dari gambar contoh nilai-nilai liberties dan papan, untuk nilai frontier disc putih

sebanyak 5, sedangkan untuk disc hitam sebanyak 6 (jumlah disc 7, namun nilai liberties pada

petak (5,4) adalah nol, jadi tidak dihitung).

Gambar 7. Contoh liberties dan papan

Gambar contoh nilai-nilai liberties pada gambar 7 dengan gambar inisialisasi liberties

pada gambar 6 berbeda, karena perubahan yang terjadi pada papan mengakibatkan nilai-nilai

liberties juga ikut berubah. Cara merubah nilai-nilai pada liberties adalah dengan mengurangi

sebanyak satu kali dari nilai liberties tiap-tiap petak yang berbatasan dengan

disc yang baru saja diletakkan.

3.5 Penguasan Corner

Penguasaan corner merupakan penguasaan terhadap posisi-posisi pojok dari papan,

karena disc yang diletakkan pada posisi tersebut tidak dapat dirubah atau dibalik. Jadi

kemungkinan besar kemenangan dapat diraih dengan menguasai posisiposisi pojok tersebut.

Berikut penjelasan berupa gambar mengenai pemberian nilai pada posisi-posisi pojok tersebut

dapat dilihat pada gambar inisialisasi nilai-nilai corner.

Gambar 8.Inisialisasi nilai-nilai corner

Pemberian nilai-nilai pada gambar inisialisasi nilai-nilai corner hanya berupa nilai

perkiraan saja. Pemberian nilai -3 karena pada posisi tersebut tidak terlalu rawan, sedangkan

nilai -60 merupakan posisi paling rawan untuk mendapatkan posisi pojok.

4. Algoritma Greedy

Algoritma greedy merupakan metode yang paling populer untuk memecahkan masalah

optimasi. Algoritma greedy membentuk solusi langkah per langkah. Pendekatan yang digunakan

di dalam algoritma greedy adalah membuat pilihan yang tampak memberi perolehan terbaik,

yaitu dengan membuat pilihan optimum local pada setiap langkah dengan harapan akan

mengarah ke solusi optimum global. Prinsip algoritma greedy pada setiap langkah ialah

mengambil pilihan terbaik yang dapat diperoleh saat itu tanpa memperhatikan konsekuensi ke

depan, dan berharap bahwa dengan memilih optimum lokal pada setiap langkah akan

menghasilkan optimum global pada akhir proses. Persoalan optimasi algoritma greedy disusun

oleh elemen-elemen berikut :

1. Himpunan kandidat, yang berisi elemen-elemen

pembentuk solusi.

2. Himpuan solusi, berisi kandidat-kandidat yang

terpilih sebagai solusi persoalan.

3. Fungsi seleksi, dinyatakan dengan predikat

SELEKSI memilih kandidat yang paling

memungkinkan mencapai solusi optimal pada setiap

langkah.

4. Fungsi kelayakan, dinyatakan dengan predikat

LAYAK, memeriksa apakah suatu kandidat yang

telah dipilih dapat memberikan solusi yang layak

dengan tidak melanggar constraints yang ada.

5. Fungsi objektif, yang memaksimumkan atau

meminimumkan nilai solusi.

Prinsip algoritma greedy pada setiap langkah ialah mengambil pilihan terbaik yang dapat

diperoleh saat itu tanpa memperhatikan konsekuensi ke depan, dan berharap bahwa dengan

memilih optimum lokal pada setiap langkah akan menghasilkan optimum global pada akhir

proses. Skema umum algoritma greedy dapat digambarkan melalui pseudo-code berikut,

Gambar 9.Pseudocode algoritma greedy

Terdapat dua strategi greedy heuristik yang akan diimplementasikan untuk menghasilkan

sebanyak mungkin koin sehingga dapat memenangkan permainan, yaitu :

1. Greedy by jumlah koin

Pada setiap langkah, koin pemain akan menuju koordinat yang menghasilkan sebanyak

mungkin koin lawan. Strategi ini berusaha memaksimumkan jumlah koin pada akhir

permainan dengan menghasilkan koin sebanyak-banyaknya pada setiap langkah.

2. Greedy by jarak ke tepi

Pada setiap langkah, koin pemain akan menuju ke koordinat yang semakin dekat dengan

tepi arena permainan. Strategi ini berusaha memaksimumkan jumlah koin pada akhir

permainan dengan menguasai daerah tepi yang sulit untuk dilangkahi koin lawan. Bahkan

untuk bagian pojok arena, sama sekali tidak dapat dilangkahi oleh lawan.

4.1 Greedy untuk Jumlah Koin pada Permainan Orthello

Untuk merepresentasikan masalah digunakan sebuah larik (array) dua dimensi yang

diberi nama isi[i][j]. Elemen array isi akan bernilai 1 jika pada koordinat tersebut terdapat koin

berwarna hitam, dan akan bernilai 0 jika pada koordinat tersebut terdapat koin berwarna putih.

Indeks i dan j masing-masing antara 1-8 yang menunjukkan koordinat terhadap sumbu X dan

sumbu Y.

Nilai himpunan kandidat disimpan di dalam sebuah array satu dimensi yang diberi nama

jumlah[k]. Range k berkisar antara 1-8. Angka 1-8 menunjukkan arah dari koordinat asal ke

koordinat tujuan, 1 menunjukkan arah kanan, kemudian urut berlawanan arah dengan jarum jam,

hingga angka 8 yang menunjukkan arah kanan bawah. Selain array, terdapat pula dua buah

variabel bertipe integer yang diberi nama JHitam dan JPutih. JHitam akan berisi jumlah koin

hitam di atas arena permainan, sedangkan JPutih berisi jumlah koin putih di atas arena

permainan.

Sebelum memulai setiap langkah, pemain akan menghitung nilai yang akan didapatkan

pada setiap kemungkinan langkah. Kemudian pemain akan memilih langkah yang menghasilkan

nilai terbesar dengan harapan akan menghasilkan solusi yang optimum. Jika terdapat lebih dari

satu jumlah[k] yang bernilai paling besar, prioritas pemilihan langkah ialah ke arah kanan, kanan

atas, atas, dan terus memutar berlawanan arah dengan jarum jam, sehingga prioritas terakhir

ialah ke arah kanan bawah.

Gambar 10. Prioritas pergerakan koin jika jumlah[k] sama

4 3 2

5 1

6 7 8

Pada suatu permainan Othello sangat mungkin pada satu giliran jalan terdapat banyak

koin yang mungkin untuk dijalankan. Jika hal ini terjadi, prioritas pemilihan langkah ialah arah 1

dari seluruh koin, dengan prioritas letak koin di kanan-atas. Kemudian dilanjutkan dengan urutan

koin yang sama dengan arah 2, dan seterusnya.

Persoalan optimasi dengan greedy by jumlah koin disusun oleh elemen-elemen berikut :

1. Himpunan kandidat, seluruh jumlah[k] yang memungkinkan dimana k berada pada

range 1-8. Jika pada arah tertentu tidak terdapat koin lawan untuk dilangkahi, tidak ada

pergerakan yang dapat dilakukan sehingga arah tersebut tidak masuk ke dalam

himpunan kandidat.

2. Himpunan solusi, langkah-langkah pada himpunan kandidat yang memiliki

jumlah[k] terbesar.

3. Fungsi seleksi, pilihlah langkah yang menghasilkan jumlah[k] terbesar. Jika terdapat

lebih dari satu jumlah[k] memiliki nilai paling besar, pilih langkah sesuai urutan

prioritas.

4. Fungsi kelayakan, periksa apakah k masih dalam range yang telah ditetapkan.

5. Fungsi objektif, langkah yang dipilih menghasilkan jumlah[k] maksimum.

Pemilihan jumlah[k] terbesar merupakan pemilihan optimum lokal yang diharapkan akan

menjadi optimum global. Pemain yang menggunakan koin hitam akan memenangkan permainan

jika JHitam > JPutih, dan sebaliknya jika JPutih lebih besar nilainya, pemain yang

menggunakan koin putih yang akan memenangkan permainan.

B A

O O O

O O O O O

O O O

Gambar 11. Contoh ilustrasi permainan Othello dengangreedy by jumlah koin, A menunjukkan langkah selanjutnya

Huruf A pada Gambar 3 menunjukkan langkah selanjutnya yang dipilih jika bermain

menggunakan greedy by jumlah koin. Koordinat yang ditandai dengan huruf A dan huruf B

sama-sama menghasilkan dua koin putih, namun koordinat B memiliki prioritas lebih rendah

sehingga koordinat A yang dipilih sebagai langkah selanjutnya.

4.2 Greedy untuk Jarak ke Tepi pada Permainan Orthello

Dalam permainan Othello, koin yang terletak di tepi arena permainan lebih sulit untuk

dilangkahi karena hanya mungkin dilangkahi dari 2 arah saja. Bahkan koin yang terletak di pojok

arena tidak dapat dilangkahi dari arah manapun. Karena itulah para pemain seringkali memiliki

prioritas untuk melangkah ke tepi.

Jarak ke tepi yang menjadi fokus batasan pada algoritma ini ialah jarak ke tepi kiri dan

tepi kanan. Jarak ke tepi atas dan bawah tidak ikut diperhitungkan. Serupa dengan greedy by

nilai koin, pada greedy by jarak ke tepi juga menggunakan sebuah larik (array) dua dimensi yang

diberi nama isi[i][j] untuk merepresentasikan masalah. Elemen array isi akan bernilai 1 jika pada

koordinat tersebut terdapat koin berwarna hitam, dan akan bernilai 0 jika pada koordinat tersebut

terdapat koin berwarna putih. Range indeks i dan j berada diantara 1-8 yang menunjukkan

koordinat terhadap sumbu X dan sumbu Y.

Jarak ke kedua tepi disimpan dalam dua buah array satu dimensi. Jarak ke kanan

disimpan dalam array kanan[p] dan jarak ke kiri dalam array kiri[p]. p menunjukkan prioritas

arah seperti yang ditunjukkan Gambar 10. Terdapat pula dua variabel bertipe integer yang diberi

nama JHitam dan JPutih untuk menyimpan jumlah koin.

Misalkan, untuk pergerakan ke titik (3,5),

kanan[p] = 8 – 3kiri [p] = 3 – 1

Konstanta 8 merupakan koordinat paling kanan, sedangkan konstanta 1 merupakan koordinat

paling kiri.

Persoalan optimasi dengan greedy by jarak ke tepi disusun oleh elemen-elemen berikut :

1. Himpunan kandidat, seluruh kanan[p] dan kiri[p] yang mungkin dimana p

menunjukkan arah langkah seperti ditunjukkan Gambar 10. Jika pada arah

tertentu tidak terdapat koin lawan untuk dilangkahi, tidak ada pergerakan yang

dapat dilakukan sehingga arah tersebut tidak masuk ke dalam himpunan kandidat.

2. Himpunan solusi, kanan[p] dan kiri[p] yang memiliki nilai paling minimum, yang

berarti jarak paling dekat dengan tepi arena.

3. Fungsi seleksi, pilihlah langkah yang menghasilkan kanan[p] atau kiri[p] terkecil. Jika

terdapat lebih dari 1 nilai terkecil, pilih berdasarkan urutan prioritas.

4. Fungsi kelayakan, periksa apakan p dan q masih termasuk dalam range

yang telah ditetapkan.

5. Fungsi objektif, langkah yang dipilih menghasilkan jarak minimum dengan tepi arena.

Pemilihan kanan[p] atau kiri[p] terkecil merupakan pemilihan optimum lokal yang

diharapkan akan menjadi optimum global. Pemain yang menggunakan koin hitam akan

memenangkan permainan jika JHitam > JPutih, dan sebaliknya jika JPutih lebih besar nilainya,

pemain yang menggunakan koin putih yang akan memenangkan permainan.

O O O

O O O O

O A

Gambar 4. Contoh ilustrasi permainan Othello dengangreedy by jarak ke tepi, A menunjukkan langkah selanjutnya

Huruf A pada Gambar 4 menunjukkan langkah selanjutnya yang akan dipilih jika

bermain menggunakan greedy by jarak ke tepi. Semakin dekat jarak ke tepi, semakin besar

prioritas koordinat tersebut untuk dipilih.

BAB III

PENUTUP

3.1 Kesimpulan

Dari penjelasan sebelumnya yang berisi mengenai metode pencarian minimax dan proses

perhitungan untuk fungsi evaluasi, dapat disimpulkan bahwa, Negascout berasumsi langkah

pertama yang ditelusuri adalah langkah terbaik dan menganggap bahwa langkah-langkah

selanjutnya sebagai langkah terburuk. Jika terdapat langkah yang lebih baik dari langkah pertama

maka akan dilakukan proses research.

MTDF yang menggunakan upperbound dan lowerbound bekerja dengan melakukan

pemanggilan alpha beta with memory secara berulang-ulang. Proses pruning akan banyak

dihasilkan dari penggunaan bound ini.

Edge table digunakan untuk menyimpan nilai mobility dengan mengevaluasi satu sisi papan,

selanjutnya untuk evaluasi total didapatkan dengan cara mencerminkannya keseluruh sisi-sisi

papan. Semakin banyak mobility atau jumlah langkah yang dapat dimainkan oleh pemain pada

satu kali kesempatan maka akan semakin bagus, karena semakin banyak pula langkah bagus

yang dapat dimainkan. Potential mobility atau frontier menggunakan liberties untuk

mengevaluasi jumlah disc yang berbatasan dengan petak kosong. Semakin banyak frontier maka

akan semakin buruk, karena lawan akan mendapat semakin banyak mobility tambahan

dan juga akan mengurangi mobility yang didapat.

Penguasaan corner pada permainan othello juga penting, karena kemungkinan besar

kemenangan akan diraih dengan menguasai daerah-daerah pojok. Pemberian nilai yang tepat

akan mempengaruhi hasil dari perhitungan fungsi evaluasi, jadi perlu diperhatikan.

Algoritma greedy dapat memecahkan masalah optimasi, namun tidak selalu menghasilkan solusi

yang optimum. Pada kenyataannya, umumnya pemain mengkombinasikan kedua algoritma di

atas untuk mendapatkan hasil yang optimum. Pada awal permainan, pemain diharapkan lebih

fokus untuk mengincar daerah tepi arena agar dapat menyusun ‘benteng pertahanan’. Namun

sebaliknya, saat telah menguasai daerah tepi pemain diharapkan dapat melompati koin sebanyak

mungkin agar dapat memenangkan permainan

DAFTAR PUSTAKA

bsavitri.staff.gunadarma.ac.id/.../Bab+1+Pengenalan+Kecerdasan+Buatan.pdf

http://journal.uii.ac.id/index.php/Snati/article/view/1278/1088

wsilfi.staff.gunadarma.ac.id/Downloads/files/4338/1-AI.pdf

www.hansmichael.com/download/gameplaying.pdf

www.informatika.org/~rinaldi/Stmik/.../MakalahIF2251-2008-024.pdf

www.unimmer.ac.id/download/Kecerdasan_buatan.pdf

MAKALAH TEKNOLOGI INFORMASI

Memenangkan Permainan Orthello Menggunakan Kecerdasan Buatan

KARYA TULIS ILMIAH

Disusun untuk memenuhi tugas

Mata Kuliah Teknologi Informasi

Yang diampu oleh :

Sukmawati Nur Endah, Ssi, MKom

Disusun Oleh :

ARGA BRAHMANTYO

J2D009027

JURUSAN FISIKA

UNIVERSITAS DIPONEGORO

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

SEMARANG

2010