1

1. RENCANA JUDUL

Penerapan Konsep Algoritma Minimax dengan Menggunakan Breadth-First Search

(BFS) pada Permainan Reversi.

2. BIDANG ILMU

Ilmu Komputer.

3. LATAR BELAKANG MASALAH

Permainan papan (board game) adalah sebuah permainan di mana bidak-bidak

diletakkan, dipindahkan ataupun dimakan oleh bidak lawan yang dimainkan di atas

papan yang bertanda sesuai dengan peraturan yang berlaku pada permainan tersebut.

Permainan papan ada yang murni berbasis strategi, kesempatan ataupun gabungan dari

kedua hal tersebut dan biasanya mempunyai suatu tahap kemenangan yang ingin

dicapai oleh para pemain. Permainan papan juga mempunyai berbagai jenis yang

dibedakan oleh ukuran papan dan jumlah pemain.

Reversi merupakan salah satu permainan papan yang murni berbasis strategi

dan dimainkan oleh dua pemain pada papan yang berukuran 8 baris dan 8 kolom dan

setiap pemain memiliki bidak yang berbeda warna (biasanya hitam dan putih). Pemain

dikatakan menang bila pada akhir permainan mempunyai jumlah bidak lebih banyak

daripada jumlah bidak lawan. Reversi juga dikenal dengan othello karena dipasarkan

oleh perusahaan permainan Amerika dengan nama othello.

Kecerdasan buatan merupakan salah satu bidang ilmu komputer yang

didefinisikan sebagai kecerdasan yang dibuat untuk suatu sistem dengan

menggunakan algoritma-algoritma tertentu sehingga sistem tersebut seolah-olah dapat

berpikir seperti manusia. Program kecerdasan buatan pertama kali ditulis pada tahun

1951 untuk menjalankan mesin Ferranti Mark di University of Manchester (UK) yang

merupakan mesin permainan naskah yang ditulis oleh Christopher Strachey.

2

Algoritma minimax adalah salah satu algoritma yang digunakan pada

permainan papan yang dimainkan oleh dua pemain dan berbasis zero-sum (Pendapatan

poin untuk pemain yang satu merupakan kehilangan poin untuk pemain lawan).

Algoritma ini sering mendasari pola pikir langkah penyelesaian masalah dalam

beberapa jenis permainan papan yang dimainkan di komputer. Secara garis besar

konsep algoritma minimax ini adalah meminimalkan kemungkinan kekalahan dan

memaksimalkan kemungkinan kemenangan.

Breadth-First Search (BFS) merupakan metode pencarian buta (blind search)

yang dilakukan pada sebuah pohon yang ditelusuri dari tingkat teratas sampai tingkat

terbawah. Pada metode pencarian ini,semua node pada level n akan dikunjungi

terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai

dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level

berikutnya demikian pula dari kiri ke kanan hingga ditemukannya solusi.

(Sri Kusumadewi, 2003).

“Pada tahun 1997, seorang juara dunia Takeshi Murakami dari Jepang berhasil

dikalahkan oleh sebuah program komputer dengan skor 6-0 dalam permainan othello,

yang dirancang oleh Michael Buro, yang diberi nama Logistello.”

(Ben Coppin, 2004).

Mencermati hal-hal di atas, maka penulis berkeinginan untuk menerapkan

konsep algoritma minimax dengan menggunakan BFS untuk membuat aplikasi

permainan reversi yang berbasis kecerdasan buatan dan mampu mengalahkan

manusia. Dengan menerapkan konsep algoritma minimax dengan menggunakan

algoritma BFS, maka akan memungkinkan terjadinya beberapa cut-off sehingga waktu

eksekusi untuk algoritma ini akan lebih efisien.

4. RUMUSAN MASALAH

Berdasarkan latar belakang di atas maka rumusan masalahnya adalah bagaimana

menerapkan konsep algoritma minimax dengan menggunakan BFS pada permainan

reversi.

3

5. BATASAN MASALAH

Penulis membuat batasan masalah yaitu:

1. Penulis tidak membandingkan algoritma ini dengan algoritma lain.

2. Algoritma ini hanya akan menelusuri 10 langkah ke depan.

3. Kecerdasan buatan ini tidak dapat melakukan pembelajaran.

6. TUJUAN PENELITIAN

Tujuan dari penelitian ini adalah untuk menganalisis, mendesain dan

mengimplementasikan konsep algoritma minimax dengan menggunakan BFS pada

permainan reversi yang mampu mengalahkan manusia.

7. MANFAAT PENELITIAN

Hasil penelitian ini diharapkan dapat digunakan sebagai:

1. Sarana yang dapat memberikan kejelasan tentang bagaimana cara kerja

kecerdasan buatan pada permainan reversi yang menggunakan algoritma

minimax dan BFS dan untuk selanjutnya dapat dikembangkan menggunakan

algoritma baru.

2. Alat yang dapat memicu pola berpikir manusia dalam menyusun strategi agar

dapat memenangkan permainan reversi pada aplikasi ini.

8. TINJAUAN PUSTAKA

8.1 Agen Cerdas

Permainan atau aplikasi yang dirancang menggunakan agen cerdas sebagai otak untuk

melawan manusia. Agen adalah sesuatu yang dapat mengesan lingkungannya melalui

sensors dan mengambil tindakan terhadap lingkungannya melalui actuators. Agen

yang berinteraksi dengan lingkungan melalui sensors dan actuators dapat dilihat pada

Gambar 1.

4

Gambar 1. Agen yang berinteraksi dengan lingkungan melalui

sensors dan actuators

Definisi agen rasional adalah untuk setiap deretan persepsi yang mungkin,

sebuah agen rasional hendaklah memilih satu tindakan yang diharapkan

memaksimalkan ukuran performance-nya, dengan adanya bukti yang diberikan oleh

deretan presepsi dan apapun pengetahuan terpasang yang dimiliki agen itu.

Beberapa jenis lingkungan yang digunakan pada agen, yaitu fully observable

atau partially observable, deterministic atau stochastic, episodic atau sequential, static

atau dynamic, discrete atau continuous, dan single agent atau multiagent.

Empat jenis agen dasar, yaitu simple reflex agents, model-based reflex agents,

goal-based agents, dan utility-based agents.

(Stuart Russel, Peter Norvig, 2003).

8.2 Pohon Permainan

Kebanyakan permainan dua pemain secara efisien dapat direpresentasikan

menggunakan pohon, yang dinamakan pohon permainan. Sebuah pohon permainan

merupakan suatu perumpamaan di mana simpul akar merepresentasikan keadaan awal

sebelum langkah diambil, sedangkan simpul pada pohon merepresentasikan

5

kemungkinan keadaan pada permainan (atau posisi), dan arah anak panah

merepresentasikan langkah-langkah.

Pohon permainan untuk permainan dua pemain direpresentasikan dengan

langkah yang diambil secara bergantian, jadi untuk simpul akar sampai simpul tingkat

pertama merepresentasikan langkah-langkah yang mungkin untuk pemain pertama,

sedangkan untuk simpul tingkat pertama sampai simpul tingkat kedua

merepresentasikan langkah-langkah yang mungkin untuk pemain kedua, dan begitu

seterusnya.

Simpul daun merepresentasikan keadaan akhir, di mana permainan

dimenangkan, dikalahkan, atau seri. Pada permainan yang sederhana, goal-state

mungkin dapat direpresentasikan dengan kemenangan komputer, sedangkan untuk

permainan yang kompleks seperti catur, konsep goal-state jarang digunakan.

Contoh struktur pohon permainan pada permainan tic-tac-toe dapat dilihat

pada Gambar 2.

Gambar 2. Potongan pohon permainan untuk permainan tic-tac-toe

(Ben Coppin, 2004).

6

8.3 Breadth-First Search (BFS)

Breadth-First Search (BFS) adalah algoritma yang melakukan pencarian secara

melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul

kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut

terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan

simpul-simpul yang tadi dikunjungi, demikian seterusnya. Jika grafik berbentuk

pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum

simpul-simpul pada aras d+1.

Algoritma ini memerlukan sebuah antrian q untuk menyimpan simpul yang

telah dikunjungi. Simpul-simpul ini diperlukan sebagai acuan untuk mengunjungi

simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungi

masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan tabel

boolean untuk menyimpan simpul yang telah dikunjungi sehingga tidak ada simpul

yang dikunjungi lebih dari satu kali. (Cynthia Kustanto, Ratna Mutia S, Pocut

Viqarunnisa (2005) pada makalah Penerapan Algoritma Breadth-First Search dan

Depth-First Search Pada FTP Search Engine for ITB Network)

8.4 Algoritma Minimax

Algoritma minimax merupakan algoritma yang digunakan untuk menentukan

pilihan agar memperkecil kemungkinan kehilangan nilai maksimal. algoitma ini

diterapkan dalam permainan yang melibatkan dua pemain seperti tic-tac-toe,

checkers, go dan permainan yang menggunakan strategi atau logika lainnya. Hal

ini berarti permainan-permainan tersebut dapat dijelaskan sebagai suatu rangkaian

aturan dan premis.

Algoritma ini mulai dikembangkan dari teori game zero-sum. Teori ini

mendeskripsikan situasi di mana jika terdapat pemain yang mengalami pendapatan,

pemain lain akan mengalami kehilangan dengan nilai yang sama dari pendapatan

tersebut, dan sebaliknya. Jumlah pendapatan dari pemain yang dikurangi dengan

jumlah kehilangan akan berjumlah nol. Teori minimax menyatakan: untuk setiap

7

dua orang pemain dalam zero-sum game, terdapat nilai V dari strategi yang

dimiliki pemain seperti:

1. Strategi yang ditentukan pemain kedua akan menghasilkan konsekuensi

kemungkinan untuk pemain pertama, V.

2. Strategi yang ditentukan pemain pertama akan menghasilkan konsekuensi

kemungkinan untuk pemain kedua, -V.

Secara setara, strategi pemain pertama akan memastikan suatu nilai V tanpa

memperdulikan strategi pemain kedua, dan bersamaan dengan itu pemain kedua akan

memastikan dirinya kehilangan nilai sebesar –V.

Algoritma Minimax merupakan algoritma dasar pencarian DFS (Depth-

First Search) untuk melakukan traversal dalam pohon. DFS akan mengekspansi

simpul paling dalam terlebih dahulu. Setelah simpul akar dibangkitkan, algoritma

ini akan membangkitkan simpul pada tingkat kedua, yang akan dilanjutkan pada

tingkat ketiga, dst. Dalam melakukan traversal, misalkan dimulai dari suatu simpul i,

maka simpul selanjutnya yang akan dikunjungi adalah simpul tetangga j, yang

bertetangga dengan simpul k, selanjutnya pencarian dimulai lagi secara rekursif dari

simpul j. Ketika telah mencapai simpul m, di mana semua simpul yang bertetangga

dengannya telah dikunjungi, pencarian akan dirunutbalik ke simpul terakhir yang

dikunjungi sebelumnya dan mempunyai simpul j yang belum dikunjungi. Selanjutnya

pencarian dimulai kembali dari j. Ketika tidak ada lagi simpul yang belum dikunjungi

yang dapat dicapai dari simpul yang telah dikunjungi maka pencarian selesai.

Dalam representasi pohon dalam algoritma minimax, terdapat dua jenis node,

yaitu node min dan node max. Max node akan memilih langkah dengan nilai tertinggi

dan min node akan memilih langkah dengan nilai terendah. Pohon pencarian algoritma

minimax dapat dilihat pada Gambar 3.

8

Gambar 3. Pohon pencarian algoritma minimax

(Nadhira Ayuningtyas (2008) pada makalah Algoritma Minimax dalam Permainan

Checkers).

Modul Utama

Komputer ( AI ) Manusia

BFS Minimax

Evaluator

Tunggu tampilan

9

9. DIAGRAM KONSEP

Berikut adalah diagram konsep dari aplikasi yang akan dibangun.

Gambar 4. Diagram Konsep

1. Modul Utama

Modul utama bertanggung jawab sebagai penentu giliran pemain yang akan

melangkah selanjutnya, serta mengidentifikasi permainan jika telah selesai.

2. Manusia (Human Player)

Dalam hal ini human player adalah user yang akan bermain melawan

komputer, setelah melakukan pergerakan maka human player akan menunggu

pergerakan komputer.

3. Komputer (Artificial Intelligence)

Komputer menentukan pergerakan terbaik dengan konsep algoritma minimax

menggunakan pencarian BFS untuk mengoptimalkan langkah selanjutnya.

4. Evaluator

Evaluator mengevaluasi nilai dari hasil yang diperoleh dari algoritma

sebelumnya, sehingga langkah yang diambil benar-benar optimal.

10

10. METODE PENELITIAN

Langkah-langkah yang ditempuh dalam menyelesaikan penelitian sebagai berikut:

1. Studi literatur

Pada tahap ini penulis mencari literatur dengan rincian sebagai berikut:

a. Mencari referensi mengenai kecerdasan buatan.

b. Mencari referensi mengenai algoritma minimax dan breadth-first search.

2. Analisis sistem

Pada tahap ini dilakukan analisis bagaimana menerapkan konsep algoritma

minimax dengan menggunakan BFS pada permainan reversi.

3. Perancangan dan implementasi algoritma

Pada tahap ini dilakukan perancangan sesuai dengan hasil dari analisis sistem

dan dilanjutkan dengan mengimplementasi hasil analisis dan perancangan ke

dalam sistem.

4. Pengujian

Pada tahap ini dilakukan pengujian sistem (20 responden) apakah berjalan

sesuai dengan tujuan penelitian.

5. Penyusunan laporan

Pada tahap ini dilakukan penulisan dokumentasi hasil analisis dan

implementasi dari konsep algoritma minimax dengan menggunakan BFS pada

permainan reversi.

11

11. RENCANA KEGIATAN KERJA

No

Kegiatan

Tahun

2010

Maret April Mei JuniJuli

III

IV

III

III

IV

III

III

IV

III

III

IV

I

1Seminar Proposal

2 Studi literatur

3Analisis Sistem

4

Perancangan dan Implementasi Algoritma

5 Pengujian

6

Penyusunan Laporan dan Kesimpulan Akhir

7 Seminar Hasil

8Sidang Meja Hijau

Tabel rencana kegiatan pengerjaan skripsi ini dapat dilihat pada tabel di bawah ini.

Medan, 16 April 2010Disetujui oleh: Pembimbing I Mahasiswa

(Drs. Marihat Situmorang, M.Kom) (Surya Wijaya)NIP. 196312141989031001

12

12. DAFTAR PUSTAKA

Ayuningtyas, Nadhira. 2008. “Algoritma minimax dalam permainan checkers”.

DALAM Strategi Algoritmik 2008. Bandung, Indonesia: Institut Teknologi

Bandung.

Coppin, Ben. 2004. Artificial Intelligence Illuminated.

Kustanto, Chintya, Ratna Mutia S, dan Pocut Viqarunnisa. 2005. “Penerapan

algoritma breadth-first search dan depth-first search pada FTP search engine for

ITB network”. Bandung, Indonesia: Institut Teknologi Bandung.

Kusumadewi, Sri. 2003. Artificial Intelligence (Teknik dan Aplikasinya). Yogyakarta:

Graha Ilmu.

Stuart, Russel and Peter Norvig. 2005. Artificial Inteligence A Modern Approach. 2nd

Edition. United States of America: Prentice Hall.

http://kamusbahasaindonesia.org/

Diakses pada tanggal 12 April 2010.