BAB I
PENDAHULUAN
A.
Latar Belakang
Kecerdasan Buatan sebenarnya sudah dimulai sejak
musim panas tahun 1956. pada waktu itu sekelompok pakar komputer, pakar dan
peneliti dari disiplin ilmu lain dari berbagai akademi, industri serta berbagai
kalangan berkumpul di Dartmouth College untuk membahas potensi komputer dalam
rangka menirukan atau mensimulasi kepandaian manusia. Beberapa ilmuwan yang
terlibat adalah Allen Newel, Herbert Simon, Marvin Miskey, Oliver Selfridge,
dan John McCarthy.
Pada mulanya Kecerdasan Buatan hanya ada di
universitas-universitas dan laboratorium-laboratorium penelitian, dan hanya
sedikit sekali – jika ada – produk praktis yang sudah dikembangkan.
Game ini adalah sebuah game yang mengasah logika
seorang pemain yang melawan AI (Komputer). Pada game ini terdapat 49 kotak yg
terdiri dari 7 baris dan 7 kolom, yang digunakan sebagai arena permainan. Didalam
game ini terdapat 2 buah simbol yaitu ultraman dan plankton. Ultraman merupakan
symbol dari user dan plankton adalah symbol dari komputer/AI.
Lalu untuk memudahkan permainan, pada game ini
ditambahkan beberapa inovasi yaitu menu, waktu dan score. Untuk bagian menu,
ditambahkan menu How to Play, About dan Exit. Menu How to Play digunakan untuk
menampilkan tutorial cara bermain game ini, menu About digunakan untuk
menjelaskan tentang game ini. Dan menu Exit digunakan untuk keluar dari
permainan. Selain menu, game ini juga telah ditambahkan score dan waktu. Score
pada game ini digunakan untuk menampilkan jumlah kemenangan yang telah di
dapatkan oleh pemain maupun lawannya yaitu komputer. Sedangkan waktu digunakan
untuk membatasi lamanya permainan. Jika waktu habis maka game selesai.
B.
Rumusan Masalah
1.
Apa itu game
Hanoi ?
2.
Apa itu game
Sodoku?
3.
Apa itu game
Kanibal ?
4.
Bagaimana
langkah langkah dan aturan permainan kecerdasan buatan?
C.
Tujuan Pembuatan Makalah
Untuk megatahui bagaimana menganalisis kecerdasan buatan
games
BAB II
PEMBAHASAN
A.
Menara Hanoi
Menara Hanoi
adalah sebuah permainan matematis atau teka-teki. Permainan ini terdiri dari
tiga tiang dan sejumlah piringan dengan ukuran berbeda-beda yang bisa
dimasukkan ke tiang mana saja. Permainan dimulai dengan piringan-piringan yang
tertumpuk rapi berurutan berdasarkan ukurannya dalam salah satu tiang, piringan
terkecil diletakkan teratas, sehingga membentuk kerucut.
Tujuan dari
teka-teki ini adalah untuk memindahkan seluruh tumpukan ke tiang yang lain, mengikuti
aturan berikut:
1.
Hanya satu
piringan yang boleh dipindahkan dalam satu waktu.
2.
Setiap
perpindahan berupa pengambilan piringan teratas dari satu tiang dan memasukkannya
ke tiang lain, di atas piringan lain yang mungkin sudah ada di tiang tersebut.
3.
Tidak boleh
meletakkan piringan di atas piringan lain yang lebih kecil.
Aturan Permainan
Permasalahan pada permainan Menara Hanoi
ini adalah bagaimana cara memindahkan semua piringan dari menara asal ke menara
tujuan dengan bantuan satu menara bantu yaitu menara sementara.
Adapun aturan-aturan permainannya,
sebagai berikut :
1.
Setiap kali
memindah cakram hanya diperbolehkan mengangkat satu cakram.
2.
Setiap cakram
yang lebih besar tidak boleh diletakkan di atas cakram yang lebih kecil.
3.
Piringan yang
lebih besar ditempatkan di bawah piringan yang lebih kecil.
Permainan Menara Hanoi
yang akan di bahas kali ini menggunakan 3 menara dan 4 piringan. Dimana ukuran
piringan tersebut berbeda satu sama lain. Semua piringan berada pada menara
asal dengan susunan secara berurutan, yang terbesar berada pada posisi paling
bawah dan yang terkecil pada posisi paling atas seperti yang tampak pada gambar
di bawah ini.
Bila didefinisikan
menara A sebagai menara asal, menara C sebagai menara tujuan dan menara B
sebagai menara sementara, dengan 4 jumlah piringan yang masing-masing
didefinisikan sebagai N1, N2 dan N3 dimana ukuran N4 > N3> N2> N1.
Menara A berisi 4 piringan dengan
susunan N4, N3, N2, N1 dari bawah ke atas. Sedangkan menara C dan B dalam
kondisi tidak ada piringan (kosong).
Dengan metode Pencarian mendalam Pertama DFS (Depth
First Search) Pencarian buta, proses pemecahan masalah pada permainan Menara
Hanoi dapat disimpulkan sebagai berikut:
1.
Metode DFS mampu
menyelesaikan masalah pada permainan Menara Hanoi.
2.
Sesuai dengan
kelebihan pada metode DFS, telah terbukti bahwa pemecahan permasalahan
permainan Menara Hanoi dapat diselesaikan dengan beberapa solusi. Dimana solusi
dari permasalahan tersebut yang terbaik adalah solusi yang paling cepat
ditemukan dimana letak solusi yang dicari berada pada level yang dalam dan
paling kiri.
3.
Untuk N buah
piringan diperlukan pemindahan sebanyak 2n – 1 kali. Ternyata dengan
menggunakan metode DFS terbukti pula
untuk 3 buah piringan dapat diselesaikan dengan 2 4 – 1 langkah = 7 langkah.
Algoritma :
a.
Jika keadaan
awal merupakan tujuan, keluar (sukses)
b.
Jika tidak,
kerjakan langkah-langkah berikut ini sampai tercapai keadaan sukses
atau gagal :
·
Bangkitkan
succesor E dari keadaan awal. Jika
tidak adab succesor, maka akan terjadi
kegagalan.
·
Panggil DFS
dengan E sebagai keadaan awal
·
Jika sukses
berikan tanda sukses.Namun jika tidak, ulangi langkah 2
Keuntungan :
·
Membutuhkan
memori relatif kecil, karena hanya
node-node pada lintasan yang aktif saja
yang disimpan
·
Secara
kebetulan, akan menemukan solusi tanpa
harus menguji lebih banyak lagi dalam
ruang keadaan
Kelemahan :
·
Memungkinkan
tidak tujuan yang diharapkan
·
Hanya mendapat 1
solusi pada setiap pencarian
B.
Sodoku
Sejarah Sudoku
Sudoku (数独
sūdoku?) juga dikenal sebagai Number Place atau Nanpure, adalah sejenis
teka-teki logika. Tujuannya adalah untuk mengisikan angka-angka dari 1 sampai 9
ke dalam jaring-jaring 9x9 yang terdiri dari 9 kotak 3x3 tanpa ada angka yang
berulang di satu bads, kolom atau kotak. Sudoku adalah sebuah puzzle yang
didasarkan pada konsep Latin Square. Latin Square sendiri diperkenalkan pada
tahun 1783 oleh Leonhard Euler, seorang matematikawan asal Swiss. Permainan ini
pertama kali diterbitkan di sebuah surat kabar Perancis pada 1895. Versi modern
permainan ini dimulai di Indiartapdis path 1979. Kemudian menjadi terkenal
kembali di Jepang pada 1986, ketika penerbit Nikoli menemukan teka-teki ini
yang diciptakan Howard Garns seorang mantan arsitek yang meninggal tahun 1989.
Kemudian Nikoli membawa permainan ini ke Jepang dan menerbitkannya di sebuah
media cetak khusus puzzle miliknya "Monthly Nikolist". Mereka
menamakannya "Suuji Wa Dokushin Ni Kagiru" (数字は独身に限る?), disingkat Sudoku (artinya "angka-angkanya
harus tetap tunggal") dan mematenkan kata ini. Media lain pun kemudian
menerbitkan permainan ini dengan nama aslinya, Number Place. Mulai saat itulah
permainan ini mewabah di Jepang. Lebih dari 600.000 majalah tentang Sudoku
terjual di Jepang setiap bulannya. Lucunya, mereka lebih senang menyebutnya
Number Place, sementara orang di luar Jepang menamakannya Sudoku. Sudoku
menjadi benar-benar mewabah di Inggris ketika The Daily Telegraph
mengenalkannya path pembacanya path bulan Februari 2005. Mecia lain pun
kemudian mengikuti dengan menyediakan permainan ini di edisinya masing-masing.
Pertengahan
Mei 2005 adalah awal demam Sudoku. Segala hal tentang Sudoku menjadi ladang
uang, pemuatan di koran harian, penerbitan buku, penerbitan majalah,
pertunjukkan televisi, siaran radio, pelayanan langganan lewat email, dan
penyediaan layanan di telepon genggam. Khusus untuk buku, News & Star
mencatat bahwa 6 dari 10 buku nonfiksi yang paling laris saat ini adalah buku
tentang Sudoku. Dad Inggris, Sudoku kemudian menyebar di daratan Eropa, dari
Prancis sampai Slowakia, lalu menular pula ke Australia dan Amerika.
Aturan
Permainan Sudoku
Aturan permainan untuk puzzle ini sangat sederhana,
untuk menyelesaikan permainan ini tidak diperlukan pengetahuan umum, kepandaian
atas bahasa tertentu, juga kemampuan matematika. Tetapi hanya memerlukan
kecermatan, kesabaran, dan logika.
Papan Sudoku terbuat dari sembilan buah kotak
berukuran 3x3 (disebut blok/ subgrid) yang disusun sedemikian rupa sehingga
menghasilkan kotak besar berukuran 9x9. Beberapa kotak sudah diisi sebagai
petunjuk awal dan tugas pemain adalah melengkapi angka-angka pada kotak yang
lain sehingga keseluruhan papan permainan terisi angka secara lengkap. Aturan
perrnainannya sangatlah sederhana:
1.
Kotak-kotak pada
setiap baris, kolom, dan blog subgrid harus berisi sebuah angka.
2.
Angka-angka yang
diiskan harus unik dari 1 hingga 9 sehingga dalam 1 blok/ subgrid hanya terdiri
atas angka 1-9 yang tidak berulang dan tidak ada angka yang berulang dalam 1
baris maupun kolom. Angka-angka ini sebenarnya tidak memiliki hubungan
aritmetis satu sama lain. Anda boleh menggantinya dengan 9 huruf, lambang, atau
wama yang berbeda.
Algoritma
Backtracking (Runut Balik) Dalam Permainan Sudoku
Algoritma backtracking
pertama kali diperkenalkan oleh D.H. Lehmer pada tahun 1950 menyajikan uraian
umum tentang backtracking dan penerapannya dalam berbagai persoalan dan
aplikasi. Algoritma backtracking (runut balik) merupakan salah satu metode
pemecahan masalah yang termasuk dabm strategi yang berbasis pencarian pada
ruang status. Algoritma backtracking bekerja secara rekursif dan melakukan
pencarian solusi persoalan secara sistematis pada semua kemungkinan solusi yang
ada. Oleh karena algoritma ini berbasis pada algoritma Depth-First Search (DFS)
untuk mencari solusi persoalan secara lebih mangkus, maka pencarian solusi
dilakukan dengan menelusuri suatu struktur berbentuk pohon berakar.
Algoritma backtracking
adalah suatu algodtma yang merupakan perbaikan dari algoritma brute force,
secara sistematis mencari solusi persoalan di antara semua kemungkinan solusi
yang ada. Backtracking merupakan bentuk tipikal dari algoritma rekursif dan
berbasis pada DFS dalam mencari solusi yang tepat. Selain itu, algoritma ini
juga merupakan metode yang mencoba-coba beberapa keputusan sampai kita
menemukan salah satu yang "berjalan". Kita tidak perlu memeriksa
semua kemungkinan solusi yang ada, tetapi cukup yang mengarah kepada solusi
saja. Dengan memangkas (pruning) simpul-simpul yang tidak mengarah ke solusi.
sehingga waktu pencarian dapat dihemat. Algoritma ini banyak diterapkan untuk
program games dan permasalahan pada bidang kecerdasan buatan.
Strategi
umum penyelesaian teka-teki Sudoku
1.
Pemindahan
(scanning) Berupa proses memindahkan bads atau kolom untuk mengindentifikasi
bads mana dalam suatu blok yang terdapat angka-angka tertentu. Proses ini
kemudian diulang pada setiap kolom (atau bads) secara sistematis. Kemudian
menentukan nilai dari suatu sel dengan membuang nilai-nilai yang tidak mungkin.
2.
Penandaan
(marking) Berupa analisa logika, dengan menandai kandidat angka yang dapat
dimasukkan dalam sebuah sel.
3.
Analisa
(analysing) Berupa eliminasi kandidat, dimana kemajuan dicapai dengan
mengeliminasi kandidat angka secara berturut-turut hingga sebuah sel hanya
punya 1 kandidat.
Prinsip
Pencarian Solusi dengan Metode Backtracking
Seperti yang
tetah dijelaskan bahwa pencarian solusi dengan menggunakan algpritma
backtracking digunakan pohon ruang status. Cara kerjanya adalah dengan
membentuk lintasan dari akar ke daun.
Langkah-langkah
pencarian solusi pada pohon ruang status:
1.
Solusi dicari
dengan membentuk lintasan dari akar ke daun. Aturan pembentukan yang dipakai
adalah mengikuti metode pencarian mendalam (DFS). Simpul-simpul yang sudah
dibhirkan dinamakan simpul hidup (live node). Simpul hidup yang sedang
diperluas dinamakan simpul-E (Expand-node). Simpul dinomori dari alas ke bawah
sesuai dengan urutan kelahirannya.
2.
Tiap kali
simpul-E diperluas. lintasan yang dibangun olehnya bertambah panjang. Jika
lintasan yang sedang dibentuk tidak mengarah ke solusi maka simpul-E tersebut
"dibunuh" sehingga menjadi simpul mati (dead node). Fungsi yang
digunakan untuk membunuh simpul-E adalah dengan menerapkan fungsi pembatas
(bounding function). Simpul yang sudah mati tidak akan pernah diperluas lagi.
3.
Jika pembentukan
lintasan berakhir dengan simpul mati, maka proses pencarian diteruskan dengan
membangkitkan simpul anak yang lainnya. Bila tidak ada lagi simpul anak yang
dapat dibangkitkan, maka pencarian solusi dilanjutlon dengan melakukan
backtracking ke simpul hidup terdekat (simpul orang tua). Selanjutnya simpul
ini menjadi simpul-E yang baru. Lintasan baru dibangun kembali sampai lintasan
tersebut membentuk solusi.
4.
Pencarian
dihentikan bila kita telah menemukan solusi atau tidak ada simpul hidup untuk
backtracking atau simpul yang dapat di diperluas.
Manfaat
Permainan Sudoku
manfaat bagi yang
memainkannya yaitu dalam pengembangan otak. Sudoku lebih menekankan pada
permainan logika, maka dibutuhkan logika yang tepat untuk menyelesaikannya
(tentunya tiap level kesulitannya, juga membutuhkan tingkat logika yang
berbeda). Dari sini, kita melatih otak kiri kita yang bekerja secara
sistematis. Bukan hanya berhenti di situ, dengan bertambahnya level
kesulitannya,kita juga dituntut kreatif mencari solusi penyelesaian materi.
Dari sisi ini, kita dilatih juga otak kanan yang bekerja secara kreatif.
C.
Kanibal
Permainan ini tidak begitu populer diantara
permainan-permainan lainnya disebabkan karena permainannya sederhana dan
interface yang kurang menarik sehingga tidak menarik orang untuk memainkannya.
Namun permainan ini sangatlah bagus untuk mengasah logika. Karena untuk
menyelesaikan permainan ini, dibutuhkan sedikit logika.
Pada saat awal permainan, terdapat dua buah daratan
disebelah kanan dan kiri yang dipisahkan oleh sebuah sungai. Terdapat tiga
manusia dan tiga kanibal di sisi kanan sungai dan sebuah perahu atau boat di
sisi kanan sungai. Perahu tersebut hanya dapat mengangkut paling banyak dua
penumpang dan dikendalikan oleh salah satu penumpang di dalam perahu. Dan
perahu hanya dapat bergerak ke kanan atau kiri.Selain itu juga terdapat aturan
bahwa jumlah manusia tidak boleh lebih sedikit dari jumlah kanibal pada kedua
sisinya. Jika jumlah manusia lebih sedikit dari jumlah kanibal, maka kanibal
akan memakan manusia dan game pun akan berakhir.
Tujuan akhir dari permainan ini adalah memindahkan
ketiga manusia dan ketiga kanibal dari daratan sebelah kanan ke daratan sebelah
kiri dengan selamat. Jadi dibutuhkan perhitungan yang tepat agar jumlah manusia
lebih banyak daripada jumlah kanibal di setiap sisi atau jumlah manusia sama
dengan jumlah kanibal di setiap sisi.
Berikut penjelasan singkat mengenai teknis
permainan. Untuk menaikkanmissionary atau cannibal, cukup mengkliknya maka
missionary atau cannibal akan otomatis masuk ke perahu. Begitu pula untuk
mengeluarkannya dari perahu tinggal mengklik missionary atau cannibal yang ada
di dalam perahu. Untuk menjalankan perahu, cukup mengklik tombol GO! Yang
terletak kanan atas.
Aturan Permainan
1.
Ada tiga
misionaris dan tiga kanibal yangharus menyebrang sungai.
2.
Hanya disediakan
satu perahu.
3.
Perahu bisa berjalan jika ada minimalsatu
orang atau satu kanibal (satupenumpang).
4.
Perahu maksimum berisi dua (1kanibal/1
misionaris /2 kanibal /2misionaris)
5.
Jumlah kanibal
tidak boleh lebih banyakdari jumlah misionaris di salah satu sisidaratan.
6.
Jika jumlah
kanibal lebih banyak darijumlah misionaris pada suatu sisi daratanmaka kanibal
akan memakan misionaris.
7.
Pemain berhasil
menyelesaikanpermainan jika semua misionaris dansemua kanibal ada di sisi
seberang yangmenjadi tujuan.
Dasar
Aturan (Rule Base)
Untuk mencapai keadaan
tujuan maka dibuatlah aturan-aturan yang dapat memenuhi semua keadaan yang
mungkin terjadi. Adapun aturan-aturan tersebut adalah sebagai berikut :
ATURAN KE
|
ATURAN
|
1
|
1M (Menyebrang)
|
2
|
1K (Menyebrang)
|
3
|
1M (Kembali)
|
4
|
1K (Kembali)
|
5
|
2M (Menyebrang)
|
6
|
2K (Menyebrang)
|
7
|
2M (Kembali)
|
8
|
2K (kembali)
|
9
|
1M1K (Menyebrang)
|
10
|
1M1K (Kembali)
|
Ket :
M :
Missionaris
K :
Kanibal
|
Aturan Permainan Missionaries dan Canibal
Solusi
Salah satu metode yang dapat dipakai
dalam proses pemecahan permasalahan pada permainan Missionaries dan Cannibals
yaitu dengan menggunakan metode
DFS (Depth First Search)
atau pencarian mendalam.
Depth First Search adalah algoritma pencariansolusi yang melakukan
pencarian pada graf ataupohon berakar secara mendalam dengan caramelakukan proses pencarian dilakukan pada semua
anaknya sebelum dilakukan pencarian ke node-node yang selevel.
Kelebihan dari metode Depth First Search yaitu:
1.
Membutuhkan memori relatif kecil,
karena hanya node-node pada lintasan yang aktif saja yang disimpan.
2.
Secara kebetulan, akanmenemukan solusi tanpa harus menguji lebih banyak lagi
dalam ruang keadaan.
Kelemahan dari metode Depth First Search yaitu:
1.
Memungkinkan tidak ditemukannya
tujuan yang diharapkan
2.
Hanya mendapat 1 solusi pada setiap
pencarian
Langkah-langkah pencarian
solusimenggunakan metode DFS adalah
sebagai berikut:
1.
Solusi dicari dengan membentuk
lintasan dari akar sampai daun. Simpul-simpul yang sudah dilahirkan dinamakan
simpul anak kiri dan simpul anak kanan.
2.
Simpul yang dibentuk, terlebih dahulu
simpul sebelah kiri dan mendalam sampai ditemukan solusi.
3.
Jika lintasan yang sedang dibentuk tidak
mengarah ke solusi, maka lintasan yang sebelah kiri dihentikan disebut simpul
mati dan dilanjutkan ke simpul anak kanan terdekat. Simpul yang sudah
dihentikan (simpul mati) tidak akan pernah diperluas lagi.
4.
Bila tidak ada lagi simpul anak yang dapat
dibangkitkan, maka pencarian solusi dilanjutkan dengan melakukan pembentukan ke
simpul hidup terdekat. Selanjutnya simpul ini menjadi simpul hidup yang baru.
5.
Lintasan baru dibangun kembali sampai lintasan
tersebut membentuk solusi.
Solusi permasalahan untuk pemindahan
seluruh Missionaries dan Cannibals dari seberang kanan(asal) ke seberang
kiri(tujuan) pada permainan Missionaries dan Cannibals dengan metode DFS dapat
dilihat pada table berikut ini.
NO
|
KEADAAN
|
ATURAN
|
AKSI
|
HASIL
|
1
|
(0,0) |
(3,3) K
AWAL
|
6
|
2 Kanibal Menyebrang
|
K (0,2)
| (3,1)
|
2
|
K (0,2)
| (3,1)
|
4
|
1 Kanibal Kembali
|
(0,1) |
(3,1) K
|
3
|
(0,1) |
(3,1) K
|
6
|
2 Kanibal Menyebrang
|
K (0,3)
| (3,0)
|
4
|
K (0,3)
| (3,0)
|
4
|
1 Kanibal Menyebrang
|
(0,2) |
(3,1) K
|
5
|
(0,2) |
(3,1) K
|
6
|
2 Kanibal Menyebrang
|
K (2,2)
| (1,1)
|
6
|
K (2,2)
| (1,1)
|
10
|
1 Missonaris dan 1 kanibal Kembali
|
(1,1) |
(2,2) K
|
7
|
(1,1) |
(2,2) K
|
5
|
2 Missionaris Menyebrang
|
K (3,1)
| (0,2)
|
8
|
K (3,1)
| (0,2)
|
4
|
1 Kanibal Kembali
|
(3,0) |
(0,3) K
|
9
|
(3,0) |
(0,3) K
|
6
|
2 Kanibal Menyebrang
|
K (3,2)
| (0,1)
|
10
|
K (3,2)
| (0,1)
|
3
|
1 Missionaris Kembali
|
(2,2) |
(1,1) K
|
11
|
(2,2) |
(1,1) K
|
9
|
1 Missionaris dan 1 Kanibal Menyebrang
|
K (3,3)
| (0,0)TUJUAN
|
Tabel2. Solusi Permainan Missionaries
dan Canibals
BAB III
PENUTUP
A.
Kesimpulan
Menara Hanoi adalah sebuah permainan
matematis atau teka-teki. Permainan ini terdiri dari tiga tiang dan sejumlah
piringan dengan ukuran berbeda-beda yang bisa dimasukkan ke tiang mana saja.
Permainan dimulai dengan piringan-piringan yang tertumpuk rapi berurutan
berdasarkan ukurannya dalam salah satu tiang, piringan terkecil diletakkan
teratas, sehingga membentuk kerucut.
Sudoku (数独
sūdoku?) juga dikenal sebagai Number Place atau Nanpure, adalah sejenis
teka-teki logika. Tujuannya adalah untuk mengisikan angka-angka dari 1 sampai 9
ke dalam jaring-jaring 9x9 yang terdiri dari 9 kotak 3x3 tanpa ada angka yang
berulang di satu bads, kolom atau kotak. Sudoku adalah sebuah puzzle yang
didasarkan pada konsep Latin Square.
Permainan
ini tidak begitu populer diantara permainan-permainan lainnya disebabkan karena
permainannya sederhana dan interface yang kurang menarik sehingga tidak menarik
orang untuk memainkannya. Namun permainan ini sangatlah bagus untuk mengasah
logika. Karena untuk menyelesaikan permainan ini, dibutuhkan sedikit logika.
DAFTAR
PUSTAKA
