Game berbasis Artificial IntelligencePemrograman Game

Eko PrasetyoTeknik Informatika

Univ. Pembangunan Nasional Veteran Jawa Timur2012

2

Sistem dalam AI Sistem yang menggunakan kecerdasan buatan, akan

mencoba untuk memberikan output berupa solusi dari suatu masalah berdasarkan kumpulan pengetahuan yang ada.

Untuk membangun suatu sistem yang mampu menyelesaikan masalah, perlu dipertimbangkan 4 hal:1. Mendefinisikan masalah dengan tepat. Pendefinisian ini

mencakup spesifikasi yang tepat mengenai keadaan awal dan solusi yang diharapkan.

2. Menganalisis masalah tersebut serta mencari beberapa teknik penyelesaian masalah yang sesuai.

3. Merepresentasikan pengetahuan yang perlu untuk menyelesaikan masalah tersebut.

4. Memilih teknik penyelesaian masalah yang terbaik.

Basis Pengetahua

n

Basis Pengetahua

n

Inference Engine

Inference Engine

Sistem yang menggunakan AI

MASALAHMASALAH SOLUSISOLUSI

3

Mendefinisikan Masalah Sebagai Suatu Ruang KeadaanMisalkan permasalahan

yang dihadapi adalah “Permainan Catur”, maka harus ditentukan:

1. Posisi awal pada papan catur;◦Posisi awal setiap

permainan catur selalu sama, yaitu semua bidak diletakkan di atas papan catur dalam 2 sisi, yaitu kubu putih dan kubu hitam

4

Mendefinisikan Masalah Sebagai Suatu Ruang Keadaan (2)2. Aturan-aturan untuk melakukan gerakan secara legal;

◦ Aturan-aturan ini sangat berguna untuk menentukan gerakan suatu bidak, yaitu melangkah dari satu keadaan ke keadaan lain. Misalkan untuk mempermudah menunjukkan posisi bidak, setiap kotak ditunjukkan dalam huruf (a, b, c, d, e, f, g) pada arah horisontal, dan angka (1, 2, 3, 4, 5, 6,7 8) pada arah vertikal. Suatu aturan untuk menggerakkan bidak dari posisi (e,2) ke (e,4), dapat ditunjukkan dengan aturan:

 IF Bidak putih pada Kotak(e,2), ◦ And Kotak(e,3) Kosong, ◦ And Kotak(e,4) Kosong◦ Then Gerakkan bidak dari (e,2) ke (e,4)

5

Mendefinisikan Masalah Sebagai Suatu Ruang Keadaan (3)3. Tujuan (goal);

◦ Tujuan yang ingin dicapai adalah posisi pada papan catur yang menunjukkan kemenangan seseorang terhadap lawannya. Kemenangan ini ditandai dengan posisi Raja yang sudah tidak dapat bergerak lagi.

Contoh di atas menunjukkan representasi masalah dalam Ruang Keadaan (State Space), yaitu suatu ruang yang berisi semua keadaan yang mungkin. ◦ Kita dapat memulai bermain catur dengan menempatkan diri pada

keadaan awal, kemudian bergerak dari satu keadaan ke keadaan yang lain sesuai dengan aturan yang ada, dan mengakhiri permainan jika salah satu telah mencapai tujuan.

Sehingga secara umum, untuk mendeskripsikan masalah dengan baik, harus:1. Mendefinisikan suatu ruang keadaan;2. Menetapkan satu atau lebih keadaan awal;3. Menetapkan satu atau lebih tujuan;4. Menetapkan kumpulan aturan.

6

Ruang KeadaanAda beberapa cara untuk merepresentasikan

Ruang Keadaan:◦ Graph Keadaan◦ Pohon Pelacakan

Graph KeadaanGraph terdiri-dari node-node yang menunjukkan

keadaan yaitu keadaan awal dan keadaan baru yang akan dicapai dengan menggunakan operator.

Node-node dalam graph keadaan saling dihubungkan dengan menggunakan arc (busur) yang diberi panah untuk menunjukkan arah dari suatu keadaan ke keadaan berikutnya.

Dalam praktiknya, sangatlah sulit untuk menggambarkan graph keadaan.

7

Graph Keadaan Pada gambar, ada lintasan 4 dari M ke T, yaitu:

◦ M-A-B-C-E-T◦ M-A-B-C-E-H-T◦ M-D-C-E-T◦ M-D-C-E-H-T

Pada graph ini, ada juga lintasan yang tidak sampai ke tujuan atau menemui jalan buntu, yaitu:◦ M-A-B-C-E-F-G◦ M-A-B-C-E-I-J◦ M-D-C-E-F-G◦ M-D-C-E-I-J◦ M-D-I-J

Tanpa mempertimbangkan arah, akan didapat siklus: D-C-E-I-D, node-node ini akan selalu berulang (pada graph tanpa arah).

A

M T

4

3

35

2

6

4

8 6

7

4

H

I

D

E

J

F

C

BG

2

1

8

Pohon Pelacakan Untuk menghindari kemungkinan adanya proses pelacakan

suatu node secara berulang, maka digunakan struktur pohon.

M

A D

B

C

C

E

E F THI

F THI

I

J

J

J

G

GT

T

Level-0

Level-1

Level-2

Level-3

Level-4

Level-5

Level-6

Tujuan

TujuanTujuan

Tujuan

BuntuBuntu

Buntu

BuntuBuntu

9

Pohon Pelacakan Struktur pohon digunakan untuk menggambarkan keadaan secara

hirarkis. Pohon terdiri dari beberapa node. Node yang terletak pada level-0 disebut dengan nama “akar”.

◦ Node akar menunjukkan keadaan awal yang biasanya merupakan topik atau obyek.

◦ Node akar ini terletak pada level ke nol. Node akar memiliki beberapa percabangan yang terdiri-atas

beberapa node successor yang sering disebut dengan nama “anak” dan merupakan node-node perantara. ◦ Namun jika dilakukan pencarian mundur, maka dapat dikatakan bahwa

node tersebut memiliki predecessor. Node-node yang tidak memiliki anak sering disebut dengan nama

node “daun” yang menunjukkan akhir dari suatu pencarian, dapat berupa tujuan yang diharapkan (goal) atau jalan buntu (dead end).

Pada gambar tersebut, sudah tidak terlihat lagi adanya siklus, karena setiap node tidak diperbolehkan memiliki cabang kembali ke node dengan level yang lebih rendah.

10

Contoh 1: Masalah teko air Ada 2 buah teko masing-masing berkapasitas 4 liter

(teko A) dan 3 liter (teko B). Tidak ada tanda yang menunjukkan batas ukuran pada

kedua teko tersebut. Ada sebuah pompa air yang akan digunakan untuk

mengisikan air pada kedua teko tersebut. Permasalahannya: Bagaimanakah kita dapat mengisikan

tepat 2 liter air ke dalam teko yang berkapasitas 4 liter ?

3 liter

(teko B)

4 liter

(teko A)

Air

tak terbatas

Air

tak terbatas

11

PenyelesaianA. Identifikasi ruang keadaan. Permasalahan ini dapat

direpresentasikan dengan 2 bilangan integer, yaitu x dan y:

x = air yang diisikan pada teko 4 liter (teko A);

y = air yang diisikan pada teko 3 liter (teko B);

Ruang keadaan: (x,y) sedemikian hingga x{0,1,2,3,4} dan y{0,1,2,3}.

B. Keadaan awal & tujuan. Keadaan awal, kedua teko dalam

keadaan kosong: (0,0); Tujuan, keadaan dimana pada teko 4

liter berisi tepat 2 liter air: (2,n) untuk sembarang n.

C. Keadaan teko air.◦ Keadaan kedua teko dapat dilihat pada

gambar.  

(0,0)

(0,1)

(0,2)

(0,3)

(1,0)

(1,1)

(1,2)

(1,3)

(2,0)

(2,1)

(2,2)

(2,3)

(3,0)

(3,1)

(3,2)

(3,3)

(4,0)

(4,1)

(4,2)

(4,3)

Keadaan Awal

Tujuan

12

Penyelesaian (2)D. Aturan-aturan

Aturan ke-

Jika Maka

1. (x,y)x < 4

(4,y)Isi teko A.

2. (x,y)y < 3

(x,3)Isi teko B.

3. (x,y)x > 0

(x-d,y)Tuangkan sebagian air keluar dari teko A.

4. (x,y)y > 0

(x,y-d)Tuangkan sebagian air keluar dari teko B.

5. (x,y)x > 0

(0,y)Kosongkan teko A dengan membuang airnya ke tanah.

6. (x,y)y > 0

(x,0)Kosongkan teko B dengan membuang airnya ke tanah.

7. (x,y)x+y 4 dan y > 0

(4,y-(4-x))Tuangkan air dari teko B ke teko A sampai teko A penuh.

8. (x,y)x+y 3 dan x > 0

(x-(3-y),y)Tuangkan air dari teko A ke teko B sampai teko B penuh.

9. (x,y)x+y 4 dan y > 0

(x+y,0)Tuangkan seluruh air dari teko B ke teko A.

10. (x,y)x+y 3 dan x > 0

(0,x+y)Tuangkan seluruh air dari teko A ke teko B.

11. (0,2) (2,0)Tuangkan 2 galon air dari teko B ke teko A.

12. (2,y) (0,y)Kosongkan 2 galon air di teko A dengan membuang airnya ke tanah.

13

Penyelesaian (3)E. Representasi ruang

keadaan dengan pohon pelacakan.

Pencarian suatu solusi dapat dilukiskan dengan menggunakan pohon.

Tiap-tiap node menunjukkan satu keadaan.

Jalur dari parent ke child menunjukkan satu operasi.

Tiap-tiap node pada pohon pelacakan ini memiliki node-node child yang menunjukkan keadaan yang dapat dicapai oleh parent.

14

Graph keadaan solusi

Isi Teko A (liter)

Isi Teko B (liter)

Aturan yang

dipakai0 0 20 3 93 0 23 3 74 2 50 2 92 0 solusi

Contoh solusi pada masalah teko air

15

LatihanBagaimana jika ada teko A berkapasitas 4

liter dan teko B berkapasitas 5 liter. Bagaimana cara mengisi 2 liter ke salah satu teko ?

Bagaimana jika ada teko A berkapasitas 5 liter dan teko B berkapasitas 7 liter. Bagaimana cara mengisi 6 liter ke teko B?

Bagaimana jika ada teko A berkapasitas 5 liter dan teko B berkapasitas 7 liter. Bagaimana cara mengisi 1 liter ke salah satu teko ?

16

Contoh 2: Petani dan 3 bawaannyaSeorang petani akan menyeberang bersama

3 bawaannya, yaitu: seekor kambing, seekor serigala, dan sayur-sayuran dengan sebuah perahu melalui sungai.

Perahu hanya bisa memuat petani dan satu penumpang yang lain (kambing, serigala atau sayur-sayuran).

Jika ditinggalkan oleh petani tersebut, maka sayur-sayuran akan dimakan oleh kambing, dan kambing akan dimakan oleh serigala.

Permasalahan: Bagaimana cara petani bersama 3 bawaannya sampai di seberang ?

17

Petani dan 3 bawaannya

18

PenyelesaianA. Identifikasi ruang keadaan.Permasalahan ini dapat dilambangkan

dengan (Petani, Sayur, Kambing, Srigala.)Nilai 0 berarti didaerah asal, nilai 1

didaerah seberang.  B. Keadaan awal & tujuan.Keadaan awal:

◦Posisi: (0, 0, 0, 0)Tujuan:

◦Posisi: (1,1,1,1)

19

Penyelesaian (2)C. Keadaan Petani dan 3 bawaannya

Aturan ke- Aturan

1. Petani dan Kambing menyeberang

2. Petani dan Sayuran menyeberang

3. Petani dan Serigala menyeberang

4. Petani dan Kambing kembali

5. Petani dan Sayuran kembali

6. Petani dan Serigala kembali

7. Petani kembali

D. Aturan-aturan

Keadaan awal

Tujuan

20

Penyelesaian (3)E. Representasi ruang keadaan dengan pohon pelacakan

21

Graph keadaan solusi optimal

PosisiAturan yang

dipakai(0, 0, 0, 0) 1(1, 0, 1, 0) 7(0, 0, 1, 0) 3(1, 0, 1, 1) 4(0, 0, 0, 1) 2(1, 1, 0, 1) 7(0, 1, 0, 1) 1(1, 1, 1, 1) solusi

Contoh solusi

22

Latihan: Keluarga menyeberang dengan perahuAda satu keluarga yang akan

menyeberang sungai menggunakan perahu.

Keluarga tersebut terdiri dari: Ayah, Ibu, dan 2 anak.

Masalahnya kapasitas perahu hanya mampu memuat paling banyak 1 orang dewasa atau 2 anak, jika melebihi kapasitas maksimal maka perahu akan tenggelam.

Permasalahan: Bagaimana cara satu keluarga tersebut menyeberan sungai ?

23

Latihan: Missionaris dan MonsterAda 6 penumpang, terdiri dari 3

missionaris dan 3 monster yang bersama-sama akan menyeberang sungai menggunakan sebuah perahu.

Perahu hanya mampu mengangkut maksimal 2 penumpang.

Jika disalah satu tepi jumlah missionaris kalah banyak dengan monster maka missionaris akan dimakan oleh monster tersebut.

Permasalahan: Bagaimana cara menyeberangkan 6 penumpang tersebut ?

24

Missionaris dan Monster

25

Latihan: Keluarga menyeberang sungai dengan lampu Ada sebuah keluarga terdiri dari keponakan, anak, ibu, ayah, kakek. Mereka akan menyeberangi sungai dengan sebuah jembatan kayu. Jembatan

kayu tersebut hanya dapat memuat paling banyak 2 orang. Suasana saat itu gelap gulita sehingga untuk menyeberang dibantu dengan

lampu penerangan berupa lampu teplok (oplek). Masalahnya, minyak tanah dalam lampu teplok tersebut hanya dapat bertahan untuk menerangi selama 30 menit, terhitung awal sesi penyeberangan. Jika minyak tersebut sudah habis maka lampu akan mati dan penyeberangan tidak dapat dilanjutkan.

Karena faktor usia dan kebiasaan menyeberang sungai, setiap anggota keluarga mempunyai keberanian yang berbeda dalam menyeberangi sungai. ◦ Keponakan dapat menyeberang dalam waktu 1 menit.◦ Anak dapat menyeberang dalam waktu 3 menit.◦ Ibu dapat menyeberang dalam waktu 6 menit.◦ Ayah dapat menyeberang dalam waktu 8 menit.◦ Kakek dapat menyeberang dalam waktu 12 menit.

Aturannya, jika dua orang bersama-sama menyeberang maka durasi penyeberangan akan mengikuti orang dengan durasi menyeberang lebih lama.

Bagaimana cara tersebut membagi tugas untuk bisa menyeberangkan semua anggota keluarga dengan persediaan minyak dalam lampu teplok yang terbatas tersebut ?

26

Keluarga menyeberang sungai dengan lampu

27

Latihan: Pangeran berkuda Ada seorang pengeran yang menunggangi kuda akan

melompat dari satu menara ke menara yang lain. Diantara 2 menara itu ada sejumlah spot yang

tertata sedemikian rupa sehingga pangeran dapat menggunakannya sebagai batu loncatan ke menara kedua, tetapi dengan syarat:◦ Dia harus melompati semua spot.◦ Mulai dari sebuah spot sembarang dan harus kembali ke

spot awal yang dipilih.◦ Setiap spot (selain spot awal yang dipilih) hanya boleh

dilewati tepat satu kali.◦ Karena menunggangi kuda, maka pelompatannya harus

menggunakan lompatan kuda (seperti permainan catur). Permasalahan: Bagaimana urutan pelompatan

pangeran dan kudanya pada spot tersebut ?

28

Pangeran berkuda

29

SAATNYA ANDA MEMBUAT GAME

Tugas 3