gameprog 5 game berbasis ai

7/24/2019 Gameprog 5 Game Berbasis Ai

1/29

Game berbasis Artifcial

IntelligencePemrograman Game

Eko Prasetyo

Teknik Inormatika

Univ. Pembangunan Nasional Veteran Jaa Timur

!"#!


2/29

$istem %alam AI$istem yang menggunakan kecer%asan buatan& akan

mencoba untuk memberikan out'ut beru'a solusi %ari suatumasala( ber%asarkan kum'ulan 'engeta(uan yang a%a.

Untuk membangun suatu sistem yang mam'umenyelesaikan masala(& 'erlu %i'ertimbangkan ) (al*

#. +en%efnisikan masala( %engan te'at. Pen%efnisian ini mencaku's'esifkasi yang te'at mengenai kea%aan aal %an solusi yang%i(ara'kan.

!. +enganalisis masala( tersebut serta mencari bebera'a teknik'enyelesaian masala( yang sesuai.

,. +ere'resentasikan 'engeta(uan yang 'erlu untuk menyelesaikanmasala( tersebut.

). +emili( teknik 'enyelesaian masala( yang terbaik.

!

BasisPengetahua

n

BasisPengetahua

n

InferenceEngine

InferenceEngine

Sistem yangmenggunakan AI

MASALAHMASALAH SOLUSISOLUSI


3/29

+en%efnisikan +asala( $ebagai$uatu -uang ea%aan

+isalkan 'ermasala(anyang %i(a%a'i a%ala(/Permainan 0atur1&maka (arus %itentukan*

#. Posisi aal 'a%a 'a'ancatur2

Posisi aal setia''ermainan catur selalu

sama& yaitu semua bi%ak%iletakkan %i atas 'a'ancatur %alam ! sisi& yaitukubu 'uti( %an kubu (itam

,


4/29

+en%efnisikan +asala( $ebagai$uatu -uang ea%aan 3!4!. Aturan5aturan untuk melakukan gerakan secara legal2

Aturan5aturan ini sangat berguna untuk menentukan gerakan suatubi%ak& yaitu melangka( %ari satu kea%aan ke kea%aan lain. +isalkanuntuk mem'ermu%a( menun6ukkan 'osisi bi%ak& setia' kotak%itun6ukkan %alam (uru 3a& b& c& %& e& & g4 'a%a ara( (orisontal& %anangka 3#& !& ,& )& 7& 8&9 :4 'a%a ara( vertikal. $uatu aturan untuk

menggerakkan bi%ak %ari 'osisi 3e&!4 ke 3e&)4& %a'at %itun6ukkan%engan 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/29

+en%efnisikan +asala( $ebagai$uatu -uang ea%aan 3,4,. Tu6uan 3goal42

Tu6uan yang ingin %ica'ai a%ala( 'osisi 'a%a 'a'an catur yangmenun6ukkan kemenangan seseorang ter(a%a' laannya. emenanganini %itan%ai %engan 'osisi -a6a yang su%a( ti%ak %a'at bergerak lagi.

0onto( %i atas menun6ukkan re'resentasi masala( %alam

Ruang Keadaan (State Space),yaitu suatu ruang yang

berisi semua kea%aan yang mungkin. ita %a'at memulai bermain catur %engan menem'atkan %iri 'a%a

kea%aan aal& kemu%ian bergerak %ari satu kea%aan ke kea%aan yanglain sesuai %engan aturan yang a%a& %an mengak(iri 'ermainan 6ikasala( satu tela( menca'ai tu6uan.

$e(ingga secara umum& untuk men%eskri'sikan masala(

%engan baik& (arus*#. +en%efnisikan suatu ruang kea%aan2

!. +eneta'kan satu atau lebi( kea%aan aal2

,. +eneta'kan satu atau lebi( tu6uan2

). +eneta'kan kum'ulan aturan.

7


6/29

-uang ea%aan

A%a bebera'a cara untuk mere'resentasikan -uangea%aan*

Gra'( ea%aan

Po(on Pelacakan

Graph Keadaan

Gra'( ter%iri5%ari no%e5no%e yang menun6ukkankea%aan yaitu kea%aan aal %an kea%aan baru yangakan %ica'ai %engan menggunakan o'erator.

No%e5no%e %alam gra'( kea%aan saling %i(ubungkan%engan menggunakan arc3busur4 yang %iberi 'ana(untuk menun6ukkan ara( %ari suatu kea%aan kekea%aan berikutnya.


7/29

Gra'( ea%aanPa%a gambar& a%a lintasan ) %ari + ke T& yaitu*

+5A5=505E5T

+5A5=505E5>5T

+5


8/29

Po(on Pelacakan

Untuk meng(in%ari kemungkinan a%anya 'roses 'elacakansuatu no%e secara berulang& maka %igunakan struktur 'o(on.

:

M

A D

B

C

C

E

E FT

HI

FT

HI

I

J

J

J

G

GT

T

Level-0

Level-1

Level-2

Level-3

Level-4

Level-5

Level-6

Tuuan

TuuanTuuan

Tuuan

BuntuBuntu

Buntu

BuntuBuntu


9/29

Po(on Pelacakan

$truktur 'o(on %igunakan untuk menggambarkan kea%aan secara(irarkis.

Po(on ter%iri %ari bebera'a no%e.

No%e yang terletak 'a%a level5" %isebut %engan nama /akar1.

No%e akar menun6ukkan kea%aan aal yang biasanya meru'akan to'ik atauobyek.

No%e akar ini terletak 'a%a level ke nol.No%e akar memiliki bebera'a 'ercabangan yang ter%iri5atas

bebera'a no%e successor yang sering %isebut %engan nama /anak1%an meru'akan no%e5no%e 'erantara.

Namun 6ika %ilakukan 'encarian mun%ur& maka %a'at %ikatakan ba(a no%etersebut memiliki 're%ecessor.

No%e5no%e yang ti%ak memiliki anak sering %isebut %engan namano%e /%aun1 yang menun6ukkan ak(ir %ari suatu 'encarian& %a'atberu'a tu6uan yang %i(ara'kan 3goal4 atau 6alan buntu 3dead end4.

Pa%a gambar tersebut& su%a( ti%ak terli(at lagi a%anya siklus&

karena setia' no%e ti%ak %i'erbole(kan memiliki cabang kembalike no%e %engan level yang lebi( ren%a(.

@


10/29

0onto( #* +asala( tekoairA%a ! bua( teko masing5masing berka'asitas ) liter

3teko A4 %an , liter 3teko =4.

Ti%ak a%a tan%a yang menun6ukkan batas ukuran 'a%ake%ua teko tersebut.

A%a sebua( 'om'a air yang akan %igunakan untuk

mengisikan air 'a%a ke%ua teko tersebut.Permasala(annya* =agaimanaka( kita %a'at mengisikan

te'at ! liter air ke %alam teko yang berka'asitas ) liter

#"

3 liter

(tekoB)

4 liter

(tekoA)

Air

takterbatas

Airtak

terbatas


11/29

Penyelesaian

A Identi!kasi ruang keadaanPermasala(an ini %a'at

%ire'resentasikan %engan ! bilanganinteger& yaitu B %an y*

B C air yang %iisikan 'a%a teko ) liter3teko A42

y C air yang %iisikan 'a%a teko , liter

3teko =42-uang kea%aan* 3B&y4 se%emikian

(ingga BD"&!&,&) %an yD"&!&,.

B Keadaan a"al # tu$uanea%aan aal& ke%ua teko %alam

kea%aan kosong* 3"&"42

Tu6uan& kea%aan %imana 'a%a teko )

liter berisi te'at ! liter air* 3!&n4 untuksembarang n.

% Keadaan teko air

ea%aan ke%ua teko %a'at %ili(at 'a%agambar.

##

!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/29

Penyelesaian 3!4

& Aturan'aturan

#!

Aturanke-

Jika Maka

1$ !%"y#

% & 4

!4"y#

Isi tek' A$

2$ !%"y#

y & 3

!%"3#

Isi tek' B$

3$ !%"y#

% ( 0

!%-)"y#

Tuangkan se*agian ai+ kelua+ )a+i tek' A$4$ !%"y#

y ( 0

!%"y-)#

Tuangkan se*agian ai+ kelua+ )a+i tek' B$5$ !%"y#

% ( 0

!0"y#

,'s'ngkan tek' A )engan mem*uang ai+nya ke tanah$

6$ !%"y#

y ( 0

!%"0#

,'s'ngkan tek' B )engan mem*uang ai+nya ke tanah$

$ !%"y#

%.y 4 )an y ( 0

!4"y-!4-%##

Tuangkan ai+ )a+i tek' B ke tek' A sam/ai tek' A /enuh$

$ !%"y#%.y 3 )an % ( 0

!%-!3-y#"y#Tuangkan ai+ )a+i tek' A ke tek' B sam/ai tek' B /enuh$

$ !%"y#

%.y 4 )an y ( 0

!%.y"0#

Tuangkan selu+uh ai+ )a+i tek' B ke tek' A$

10$ !%"y#%.y 3 )an % ( 0

!0"%.y#Tuangkan selu+uh ai+ )a+i tek' A ke tek' B$

11$ !0"2# !2"0#Tuangkan 2 gal'n ai+ )a+i tek' B ke tek' A$

12$ !2"y# !0"y#,'s'ngkan 2 gal'n ai+ )i tek' A )engan mem*uang ai+nya ketanah$


13/29

Penyelesaian 3,4

Representasi ruangkeadaan dengan pohonpelaakanPencarian suatu solusi

%a'at %ilukiskan %enganmenggunakan 'o(on.

Tia'5tia' no%e menun6ukkansatu kea%aan.

Jalur %ari 'arent ke c(il%menun6ukkan satu o'erasi.

Tia'5tia' no%e 'a%a 'o(on

'elacakan ini memilikino%e5no%e c(il% yangmenun6ukkan kea%aan yang%a'at %ica'ai ole( 'arent.

#,


14/29

Gra'( kea%aan solusi

#)

Isi Teko

A (liter)

Isi Teko

B (liter)

Aturan

an!

"i#akai

0 0 2

0 3

3 0 23 3

4 2 5

0 2

2 0 s'lusi

0onto( solusi 'a%a masala( teko


15/29

Fati(an

=agaimana 6ika a%a teko A berka'asitas )liter %an teko = berka'asitas 7 liter.=agaimana cara mengisi ! liter ke sala(satu teko

=agaimana 6ika a%a teko A berka'asitas 7liter %an teko = berka'asitas 9 liter.=agaimana cara mengisi 8 liter ke teko =

=agaimana 6ika a%a teko A berka'asitas 7liter %an teko = berka'asitas 9 liter.=agaimana cara mengisi # liter ke sala(satu teko

#7


16/29

0onto( !* Petani %an ,baaannya$eorang 'etani akan menyeberang bersama

, baaannya& yaitu* seekor kambing& seekorserigala& %an sayur5sayuran %engan sebua('era(u melalui sungai.

Pera(u (anya bisa memuat 'etani %an satu'enum'ang yang lain 3kambing& serigalaatau sayur5sayuran4.

Jika %itinggalkan ole( 'etani tersebut& maka

sayur5sayuran akan %imakan ole( kambing&%an kambing akan %imakan ole( serigala.

Permasala(an* =agaimana cara 'etanibersama , baaannya sam'ai %i seberang

#8


17/29

#9

*etani dan 3 ba"aann+a


18/29

Penyelesaian

A Identi!kasi ruang keadaanPermasala(an ini %a'at %ilambangkan

%engan 3Petani& $ayur& ambing& $rigala.4

Nilai " berarti %i%aera( asal& nilai #

%i%aera( seberang.

B Keadaan a"al # tu$uan

ea%aan aal* Posisi* 3"& "& "& "4Tu6uan*

Posisi* 3#

#:


19/29

Penyelesaian 3!4

#@

0. ea%aan Petani %an , baaannyaAturan

ke-Aturan

1$ Petani )an ,am*ing

menye*e+ang2$ Petani )an Sayu+an

menye*e+ang3$ Petani )an Se+igala

menye*e+ang4$ Petani )an ,am*ing

kem*ali5$ Petani )an Sayu+an

kem*ali

6$ Petani )an Se+igalakem*ali

$ Petani kem*ali

& Aturan'aturan

ea%aan aal

Tu6uan


20/29

Penyelesaian 3,4

!"

E. -e'resentasi ruang kea%aan %engan 'o(on'elacakan


21/29

Gra'( kea%aan solusio'timal

!#

P'sisiAtu+an yang

)i/akai(0, 0, 0, 0) 1(1, 0, 1, 0)

(0, 0, 1, 0) 3(1, 0, 1, 1) 4(0, 0, 0, 1) 2(1, 1, 0, 1) (0, 1, 0, 1) 1(1, 1, 1, 1) s'lusi

0onto( solusi


22/29

Fati(an* eluarga menyeberang%engan 'era(u

A%a satu keluarga yang akan menyeberangsungai menggunakan 'era(u.

eluarga tersebut ter%iri %ari* Aya(& Ibu&%an ! anak.

+asala(nya ka'asitas 'era(u (anyamam'u memuat 'aling banyak # orang%easa atau ! anak& 6ika melebi(ika'asitas maksimal maka 'era(u akan

tenggelam.Permasala(an* =agaimana cara satu

keluarga tersebut menyeberan sungai

!!


23/29

Fati(an* +issionaris %an+onsterA%a 8 'enum'ang& ter%iri %ari , missionaris

%an , monster yang bersama5sama akanmenyeberang sungai menggunakan sebua('era(u.

Pera(u (anya mam'u mengangkutmaksimal ! 'enum'ang.

Jika %isala( satu te'i 6umla( missionariskala( banyak %engan monster maka

missionaris akan %imakan ole( monstertersebut.

Permasala(an* =agaimana caramenyeberangkan 8 'enum'ang tersebut

!,


24/29

!)

issionaris dan onster


25/29

Fati(an* eluarga menyeberangsungai %engan lam'u

A%a sebua( keluarga ter%iri %ari ke'onakan& anak& ibu& aya(& kakek.+ereka akan menyeberangi sungai %engan sebua( 6embatan kayu. Jembatan

kayu tersebut (anya %a'at memuat 'aling banyak ! orang.

$uasana saat itu gela' gulita se(ingga untuk menyeberang %ibantu %enganlam'u 'enerangan beru'a lam'u te'lok 3o'lek4. +asala(nya& minyak tana(%alam lam'u te'lok tersebut (anya %a'at berta(an untuk menerangi selama," menit& ter(itung aal sesi 'enyeberangan. Jika minyak tersebut su%a(

(abis maka lam'u akan mati %an 'enyeberangan ti%ak %a'at %ilan6utkan.arena aktor usia %an kebiasaan menyeberang sungai& setia' anggota

keluarga mem'unyai keberanian yang berbe%a %alam menyeberangi sungai.

e'onakan %a'at menyeberang %alam aktu # menit.

Anak %a'at menyeberang %alam aktu , menit.

Ibu %a'at menyeberang %alam aktu 8 menit.

Aya( %a'at menyeberang %alam aktu : menit.

akek %a'at menyeberang %alam aktu #! menit.

Aturannya& 6ika %ua orang bersama5sama menyeberang maka %urasi'enyeberangan akan mengikuti orang %engan %urasi menyeberang lebi(lama.

=agaimana cara tersebut membagi tugas untuk bisa menyeberangkan semuaanggota keluarga %engan 'erse%iaan minyak %alam lam'u te'lok yangterbatas tersebut

!7


26/29

!8

Keluarga -en+eberang sungai dengan la-


27/29

Fati(an* Pangeranberku%aA%a seorang 'engeran yang menunggangi ku%a akan

melom'at %ari satu menara ke menara yang lain.


28/29

!:

*angeran berkuda


29/29

.AAT/0A A/&AB1AT GA

Tugas ,

!@

gameprog 5 game berbasis ai

Documents