< prev

Page 1Page 2Page 3Page 4Page 5Page 6Page 7Page 8

Page 2 of 8
next >

Jurnal Ilmiah Komputer dan Informatika (KOMPUTA)

100

Vol. 5, No. 2, Oktober 2016, ISSN : 2089-9033

tingkat kemenangannya lebih besar dari algoritma

Minimax.

2. ISI PENELITIAN

2.1 Game Congklak

Congklak merupakan suatu permainan tradional

yang yang dimainkan oleh 2 orang dengan

menggunakan media papan. Biasanya dalam

permainan ini menggunakan batu atau sejenis kulit

kerang yang digunakan sebagai alat permainan [5].

Papan congklak terdiri dari sejumlah lubang kecil

dan dua lubang besar yang terdapat di masing-masing

tiap ujung papan. Setiap pemain memiliki daerahnya

sendiri. Pada awal permainan, semua lubang yang ada

dipapan diisi dengan jumlah yang sama (batu, biji

atau kerang). Jumlah isi di setiap lubang biasanya

sama dengan jumlah lubang di salah satu sisi. Tujuan

dari permainan ini adalah untuk mengumpulkan isi

lubang sendiri dan mengosongkan isi lubang lawan

yang ada di papan permainan. Pemain yang

memenangkan permainan adalah pemain yang

mengumpulkan batu / kulit kerang terbanyak.

Gambar 1. Papan Game Congklak

2.2 Kecerdasan Buatan

artificial

intelligent

Acting rationallyRational agent

Hal ini berdasarkan pemikiran bahwa komputer bisa

melakukan penalaran secara logis dan juga bisa

melakukan aksi secara rasional berdasarkan hasil

penalaran tersebut [6].

Kecerdasan buatan atau AI merupakan kegiatan

membuat komputer agar dapat berpikir dan

mengerjakan kegiatan yang dapat dilakukan oleh

manusia maupun binatang. Saat ini dapat ditemukan

program komputer yang memiliki kemampuan

aritmatic, sorting,

searching

board game

pada manusia. Namun masih banyak hal yang tidak

dapat dilakukan dengan baik oleh komputer. Seperti,

mengenali wajah, berbicara bahasa manusia,

menentukan sendiri apa yang harus dilakukan, dan

bertingkah kreatif. Hal itu semua merupakan domain

dari AI untuk mencoba menentukan algoritma apa

yang dibutuhkan untuk memenuhi kebutuhan diatas.

Dalam bidang akademik, beberapa peneliti AI

termotivasi oleh filosofi, yaitu memahami alam

pikiran dan alam kecerdasan dan membangun

program untuk memodelkan bagaimana proses

berpikir. Beberapa juga termotivasi oleh psikologi,

bertujuan untuk memahami mekanisme otak manusia

dan proses mental. Dan lainya termotivasi oleh

engineering

untuk melakukan kegiatan seperti manusia atau

hewan. Dalam pembangunan Game, umumnya akan

cenderung hanya pada sisi engineering yang

bertujuan

membangun

algoritma

yang

dapat

membuat Game karakter mengerjakan kegiatan

seperti yang dilakukan manusia atau binatang [6].

2.3 Algoritma Negascout

Pada tahun 1982 dan 1983 dibuat dua algoritma

yang mirip, yaitu algoritma PVS dan Algoritma

Negascout. Algoritma negascout diperkenalkan oleh

Alexander Reinefeld yang menggabungkan konsep

algoritma SCOUT dan algoritma alpha-beta dalam

notasi negamax [4].

Negascout game tree mirip dengan SCOUT, tetapi

menggunakan notasi negamax dan menggunakan

beberapa optimasi. Implementasinya mengasumsikan

nilai integer dari fungsi evaluasi, seperti dalam

gambar 2. Dalam memperkecil jendela pencarian agar

mendapat jendela pencarian dengan lebar nol.

Negascout akan memotong hampir semua cabang-

cabang dari pohon, untuk membuat suatu pencarian

yang sangat tepat. Tetapi sayangnya, ia akan

memotong semua cabang-cabang berguna bersamaan

dengan yang tidak berguna. Hal ini tidak berlaku jika

algoritma dimulai dengan hasil yang benar. Satu

jendela nol dapat dilihat sebagai uji coba. Uji coba

dilakukan jika nilai sebenarnya sama dengan nilai

yang ditebak.

Gambar 2. Algoritma Negascout

1

function minimax(node,depth)

2 if depth <= 0 then

3

{positive values are good for the maximizing player}

4

{negative values are good for the minimizing player}

5

return objective_value(node)

6 end

7

{maximizing player is (+1)}

8

{minimizing player is (-1)}

9

local alpha = -node.player * INFINITY

10 local child = next_child(node,nil)

11 while child ~= nil do

12

local score = minimax(child,depth-1)

13

alpha = node.player==1 and math.max(alpha,score) or

math.min(alpha,score)

14

child = next_child(node,child)

15 end

16 return alpha

17 end