Desty Putri A
Priskyla Vivi
Rocky D
Syara
Yerni
Daftar Isi
Daftar Isi …………………………………………………………. 1
Initial State …………………………………………………………. 2
Rules …………………………………………………………. 3
Goal …………………………………………………………. 4-5
Konsep AI …………………………………………………………. 6
Listing Program
................................................................................ 7-14
Daftar Pustaka …………………………………………………………. 15
Glosarium …………………………………………………………. 16
1
INITIAL
STATE
Initial
State yang digunakan untuk membuat
program Tic Tac Toe atau SQUARE
adalah pembuatan papan permainanya. Pada
papan permainan tersebut menggunakan papan 2 dimensi yang berukuran 7 x 7. Game
Tic-Tac-Toe merupakan
permainan yang terdapat di strawberry prolog yang diatur kembali logika dalam
prolog agar user dan AI komputer dapat bermain dengan baik yang diolah agar
user dan AI komputer dapat meraih yang sesuai diinginkan. Game ini akan mengasah otak
pemainnya untuk bisa
mengalami kondisi yang diharapkan. Pemain dipaksa
untuk menerapkan strategi yang tepat untuk memenangkan game ini. Permainan ini
hanya dapat dimainkan oleh satu pemain, sedangkan Komputer bertindak sebagai
lawan. Kondisi
awal pada Game SQUARE
adalah suatu papan yang terdiri dari tujuh
kolom dan tujuh
baris. Tujuan dari game ini adalah membentuk suatu garis baik itu horizontal, vertikal maupun diagonal untuk dapat dimainkan oleh user maupun AI komputer.
Dimana objek yang dilambangkan dengan spongesbob dengan
berbeda motif antara user dan AI komputer agar perlawanan terlihat jelas.
Pada game ini, user mendapat giliran yang pertama.
2
RULES
Berikut ini adalah aturan dalam permainan SQUARE :
- Pada games ini papan terbentuk atas 7 kolom dan 7 baris (7x7).
- User dilambangkan dengan objek spongebob dan AI Computer dilambangkan dengan spongebob juga tetapi dengan motif yang berbeda.
- User bermain terlebih dahulu, dan memiliki kebebasan untuk menaruh objek di salah satu setiap kotak 7 x 7 tersebut.
- Setelah itu AI Computer mendapat giliran selanjutnya.
- AI Computer berusaha untuk menghalangi user membentuk garis horizontal, vertikal maupun diagonal tujuan untuk user tidak dapat meraih kemenangan . Begitupun sebaliknya, user juga akan menghalangi AI Computer membentuk garis horizontal, vertikal maupun diagonal dengan tujuan yang sama.
- Pemenangnya ditentukan berdasarkan pemain pertama yang dapat membentuk secara berhimpitan garis vertikal, horisontal atau diagonal.
- Jika tidak ada pemain yang dapat membentuk garis vertikal, horizontal, atau diagonal secara berhimpitan, maka permainan berakhir seri (draw).
3
GOALS
Goal atau tujuan permainan SQUARE ini agar meraih kemenangan.
Pemain dikatakan menang apabila
berhasil
membentuk garis baik vetikal,
horizontal maupun diagonal secara
berhimpitan.
Akan tetapi, apabila tidak
ada pemain yang berhasil mencapai goal, maka permainan berakhir seri. Maka dari itu, pemain berusaha untuk bisa bermain dengan
logika agar bisa meraih kemenangan.
Contoh kondisi permainan SQUARE :
1. Kondisi USER menang
4
2.
Kondisi AI komputer menang atau USER kalah
3. Kondisi seri
5
KONSEP AI (Artificial Intelligence)
Artificial
Intelligence atau kecerdasan
buatan digunakan dalam permainan ini, yaitu diletakkan pada komputer yang
bertindak sebagai lawan dari user dimana
AI komputer layaknya seperti perlawanan dengan manusia. Hal
ini dikarenakan
komputer selain berusaha membuat goal dan
menghalangi jalannya user dalam membuat goal. Sehingga user berusaha untuk bisa menghalangi jalannya
komputer hingga mencapai goal atau tujuan.
Permainan
ini dimainkan dengan dua pemain dan menggunakan algoritma minimax.
Algoritma minimax merupakan sebuah algoritma DFS(Depth First Search), dimana
algoritma minimax dapat memutuskan langkah terbaik yang harus dilakukan computer. Keuntungan yang didapat dengan menggunakan
algoritma minimax yaitu mampu menganalisis segala kemungkinan posisi permainan
untuk menghasilkan keputusan yang terbaik karena algoritma minimax ini bekerja
secara rekursif dengan mencari langkah yang akan membuat lawan mengalami
kerugian minimum. Semua strategi lawan akan dihitung dengan algoritma yang sama
dan seterusnya.Hal ini menyebabkan user mendapat keuntungan minimum dan
komputer mendapat keuntungan maksimum, karena komputer akan selalu menghalangi
setiap langkah user. Selain menghalangi, komputer juga memikirkan cara untuk
menang dalam setiap analisis pergerakan yang harus dilakukan.
Pada permainan ini,
tujuannya adalah membuat objek tersebut
sejajar
baik itu horizontal, vertical, atau diagonal secara berhimpit. Sehingga pada
permainan tic tac toe ini digunakan nilai berupa menang, seri, dan kalah. Dari langkah-langkah inilah komputer akan
menentukan simpul mana dari pohon permainan yang akan dipilih, tentunya simpul
yang akan dipilih tersebut adalah simpul dengan tahap-tahp logika yang akan menuntun
permainan ke hasil akhir yang menguntungkan bagi komputer maupun user. Hingga
bisa memainkan dan mendapat hasil menang, seri dan kalah.
6
LISTING PROGRAM
%This game is developed by Desty Putri A.
%3IA16 - Gunadarma University
win_deep(0). % semakin besar kedua nilai ini semakin
pintar AI%
nolose_deep(0).
?-
%=========Deklarasi Gambar==========%
G_background is
bitmap_image("images.bmp",_),
G_x is
bitmap_image("spong.bmp",_),
G_o is
bitmap_image("spong1.bmp",_),
set(pos([[f,f,f,f,f,f,f], [f,f,f,f,f,f,f], [f,f,f,f,f,f,f], [f,f,f,f,f,f,f],
[f,f,f,f,f,f,f], [f,f,f,f,f,f,f], [f,f,f,f,f,f,f]])),
set(lose_flag(false)),
brush(system_color(window)),
window( _, _, win_func(_), "SQUARE", 30, 90, 500, 520).
%=======Window Button Main==========%
win_func(init) :-
menu(normal, _, _, menu_new(_), "&New Game"),
menu(normal,_,_,menu_help(_),"Help"),
menu(normal,_,_,about(_),"About"),
menu(normal, _, _, menu_exit(_), "&Exit").
put_mark(Mark) :-
pos(Current_Pos),
member(Current_Pos, L, Y),
member(L, Mark, X),
X1 is 40 + 60*X, Y1 is 40 + 60*Y, X2 is X1 + 40, Y2 is Y1 +40,
write_mark(Mark, X1, Y1, X2, Y2),
fail.
put_mark(_).
write_mark(x, X1, Y1, X2, Y2) :-
draw_bitmap(X1, Y1,G_o, _, _).
write_mark(o, X1, Y1, X2, Y2) :-
draw_bitmap(X1, Y1,G_x, _, _).
7
%=======window papan permainan======%
win_func(paint) :-
draw_bitmap(30,30,G_background,_,_),
pen(4, rgb(0, 0, 0)), % black
%line(30, 30, 510, 30),% garis
horizonta
line(30, 90, 450, 90),
line(30, 150, 450, 150),
line(30, 210, 450, 210),
line(30, 270, 450, 270),
line(30, 330, 450, 330),
line(30, 390, 450, 390),
line(30, 450, 450, 450),
%line(30, 510, 450, 510),
%line(30, 30, 30, 510),% garis
vertikal
line(90, 50, 90, 450),
line(150, 50, 150, 450),
line(210, 50, 210, 450),
line(270, 50, 270, 450),
line(330, 50, 330, 450),
line(390, 50, 390, 450),
%line(510, 30, 510, 450),
pen(4, rgb(255, 0, 0)), % red
put_mark(x),
pen(4, rgb(0, 0, 255)), % blue
put_mark(o),
fail.
win_func(mouse_click(X, Y)) :-
lose_flag(false),
X>30, Y>30,
X<510, Y<510,
X1 is (X - 30)//60,
Y1 is (Y - 30)//60,
pos(Current_Pos),
member(Current_Pos, L, Y1),
member(L, f, X1),
!,
replace(L2, L, x, X1),
replace(Current_Pos2, Current_Pos,
L2, Y1),
set(pos(Current_Pos2)),
not(win_func(paint)),
think(Current_Pos2).
win_func(mouse_click(X, Y)) :-
beep.
8
think(Pos) :-
victory(x, Pos), !,
set(lose_flag(true)),
message("You win","Congrats",!).
think(Pos) :-
try_to_win(Pos), !.
think(Pos) :-
retractall(last_good_move(_)), try_nolose(Pos).
think(_) :-
last_good_move(Sit2), !,
set(pos(Sit2)),
not(win_func(paint)).
think(Pos) :-
message("Nice", "Keep Spirit!!", n),
move(o, Pos, Sit2),
nolose(x, Sit2, 0), !, % Tries to make the lose farther
set(pos(Sit2)),
not(win_func(paint)).
think(Pos) :-
move(o, Pos, Sit2),
set(pos(Sit2)),
not(win_func(paint)).
try_nolose(Pos) :-
move(o, Pos, Sit2),
nolose_deep(Deep),
nolose(x, Sit2, Deep),
set(last_good_move(Sit2)),
random(3)=:=0, !, fail. % this makes the game more
interesting
try_to_win(Pos) :-
move(o, Pos, Sit2),
is_it_win(Sit2).
is_it_win(Sit2) :-
victory(o, Sit2),
set(pos(Sit2)),
not(win_func(paint)),
set(lose_flag(true)),
beep("suara ketawa.wav"),
message("Sorry","You lose!",s).
is_it_win(Sit2) :-
win_deep(Deep),
win(x, Sit2, Deep),
set(pos(Sit2)),
not(win_func(paint)),
message("Please","Give up",i).
9
member([Element, _, _, _, _, _, _], Element, 0).
member([_, Element, _, _, _, _, _], Element, 1).
member([_, _, Element, _, _, _, _], Element, 2).
member([_, _, _, Element, _, _, _], Element, 3).
member([_, _, _, _, Element, _, _], Element, 4).
member([_, _, _, _, _, Element, _], Element, 5).
member([_, _, _, _, _, _, Element], Element, 6).
replace([Element, A, B, C, D, E, F], [_, A, B, C, D, E, F], Element, 0).
replace([A, Element, B, C, D, E, F], [A, _, B, C, D, E, F], Element, 1).
replace([A, B, Element, C, D, E, F], [A, B, _, C, D, E, F], Element, 2).
replace([A, B, C, Element, D, E, F], [A, B, C, _, D, E, F], Element, 3).
replace([A, B, C, D, Element, E, F], [A, B, C, D, _, E, F], Element, 4).
replace([A, B, C, D, E, Element, F], [A, B, C, D, E, _, F], Element, 5).
replace([A, B, C, D, E, F, Element], [A, B, C, D, E, F, _], Element, 6).
%======kondisi menang horizontal======%
victory( Who, [[Who, Who, Who, Who, Who, Who, Who],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _]]).
victory( Who, [[_, _, _, _, _, _, _],
[Who, Who, Who, Who, Who, Who, Who],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _]]).
victory( Who, [[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[Who, Who, Who, Who, Who, Who, Who],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _]]).
10
victory( Who, [[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[Who, Who, Who, Who, Who, Who, Who],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _]]).
victory( Who, [[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[Who, Who, Who, Who, Who, Who, Who],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _]]).
victory( Who, [[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[Who, Who, Who, Who, Who, Who, Who],
[_, _, _, _, _, _, _]]).
victory( Who, [[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[Who, Who, Who, Who, Who, Who, Who]]).
%=========kondisi menang vertikal=======%
victory( Who, [[Who, _, _, _, _, _, _],
[Who, _, _, _, _, _, _],
[Who, _, _, _, _, _, _],
[Who, _, _, _, _, _, _],
[Who, _, _, _, _, _, _],
[Who, _, _, _, _, _, _],
[Who, _, _, _, _, _, _]]).
victory( Who, [[_, Who, _, _, _, _, _],
[_, Who, _, _, _, _, _],
[_, Who, _, _, _, _, _],
[_, Who, _, _, _, _, _],
[_, Who, _, _, _, _, _],
[_, Who, _, _, _, _, _],
[_, Who, _, _, _, _, _]]).
victory( Who, [[_, _, Who, _, _, _, _],
[_, _, Who, _, _, _, _],
[_, _, Who, _, _, _, _],
[_, _, Who, _, _, _, _],
[_, _, Who, _, _, _, _],
11
[_, _, Who, _, _, _, _],
[_, _, Who, _, _, _, _]]).
victory( Who, [[_, _, _, Who, _, _, _],
[_, _, _, Who, _, _, _],
[_, _, _, Who, _, _, _],
[_, _, _, Who, _, _, _],
[_, _, _, Who, _, _, _],
[_, _, _, Who, _, _, _],
[_, _, _, Who, _, _, _]]).
victory( Who, [[_, _, _, _, Who, _, _],
[_, _, _, _, Who, _, _],
[_, _, _, _, Who, _, _],
[_, _, _, _, Who, _, _],
[_, _, _, _, Who, _, _],
[_, _, _, _, Who, _, _],
[_, _, _, _, Who, _, _]]).
victory( Who, [[_, _, _, _, _, Who, _],
[_, _, _, _, _, Who, _],
[_, _, _, _, _, Who, _],
[_, _, _, _, _, Who, _],
[_, _, _, _, _, Who, _],
[_, _, _, _, _, Who, _],
[_, _, _, _, _, Who, _]]).
victory( Who, [[_, _, _, _, _, _, Who],
[_, _, _, _, _, _, Who],
[_, _, _, _, _, _, Who],
[_, _, _, _, _, _, Who],
[_, _, _, _, _, _, Who],
[_, _, _, _, _, _, Who],
[_, _, _, _, _, _, Who]]).
%=====kondisi menang diagonal 7 kotak====%
victory( Who, [[Who, _, _, _, _, _, _, _],
[_, Who, _, _, _, _, _, _],
[_, _, Who, _, _, _, _, _],
[_, _, _, Who, _, _, _, _],
[_, _, _, _, Who, _, _, _],
[_, _, _, _, _, Who, _, _],
[_, _, _, _, _, _, Who, _],
[_, _, _, _, _, _, _, Who]]).
victory( Who, [[_, _, _, _, _, _, _, Who],
[_, _, _, _, _, _, Who, _],
[_, _, _, _, _, Who, _, _],
[_, _, _, _, Who, _, _, _],
[_, _, _, Who, _, _, _, _],
[_, _, Who, _, _, _, _, _],
[_, Who, _, _, _, _, _, _],
[Who, _, _, _, _, _, _, _]]).
12
%====kondisi menang diagonal 4 kotak ====%
victory( Who, [[_, _, _, Who, _, _, _],
[_, _, Who, _, _, _, _],
[_, Who, _, _, _, _, _],
[Who, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _]]).
victory( Who, [[_, _, _, Who, _, _, _],
[_, _, _, _, Who, _, _],
[_, _, _, _, _, Who, _],
[_, _, _, _, _, _, Who],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _]]).
victory( Who, [[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, Who],
[_, _, _, _, _, Who, _],
[_, _, _, _, Who, _, _],
[_, _, _, Who, _, _, _]]).
victory( Who, [[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[_, _, _, _, _, _, _],
[Who, _, _, _, _, _, _],
[_, Who, _, _, _, _, _],
[_, _, Who, _, _, _, _],
[_, _, _, Who, _, _, _]]).
win( o, Sit, Deep) :- move(o, Sit, Sit2), win(x, Sit2, Deep).
win( x, Sit, _) :- victory(o, Sit).
win( x, Sit, 0) :- !, fail.
win( x, Sit, Deep) :- Deep1 is Deep - 1, not(nowin( x, Sit, Deep1)).
nowin(x, Sit, _) :- not(move(Sit)). % the last move belongs to O
nowin(x, Sit, Deep) :- move(x, Sit, Sit2), nowin(o, Sit2, Deep).
nowin( o, Sit, _) :- victory(x, Sit).
nowin(o, Sit, Deep) :- not(win(o, Sit, Deep)).
lose( x, Sit, Deep) :- move(x, Sit, Sit2), lose(o, Sit2, Deep).
lose( o, Sit, _) :- victory(x, Sit).
lose( o, Sit, 0) :- !, fail.
lose( o, Sit, Deep) :- Deep1 is Deep - 1, not(nolose( o, Sit, Deep1)).
13
nolose(o, Sit, Deep) :- move(o, Sit, Sit2), nolose(x, Sit2, Deep).
nolose( x, Sit, _) :- victory(o, Sit).
nolose(x, Sit, _) :- not(move(Sit)). % the last move belongs to O
nolose(x, Sit, Deep) :- not(lose(x, Sit, Deep)).
move(P, Sit, Sit2) :-
member(Sit, L, Y),
member(L, f, X),
replace(L2, L, P, X),
replace(Sit2, Sit, L2, Y).
move(Sit) :-
member(Sit, L, _),
member(L, f, _).
menu_new(press) :-
set(pos([[f,f,f,f,f,f,f], [f,f,f,f,f,f,f], [f,f,f,f,f,f,f], [f,f,f,f,f,f,f],
[f,f,f,f,f,f,f], [f,f,f,f,f,f,f], [f,f,f,f,f,f,f]])),
set(lose_flag(false)),
update_window(_).
about(press):-
message("About","Tic Tac Toe Spidey Trap by Desty Putri Arifin, 3IA16, 51411913",i).
menu_help(press):-
message("Help","Tempatkan ikon Spong dengan cara meng-klik di salah satu kotak. Susun
hingga membentuk sebuah garis terdiri dari 7 simbol secara vertikal, horizontal
ataupun 4 simbol diagonal dikotak keempat.",i).
%===========Window Exit=============%
menu_exit(press) :-
close_window(_).
win_func(close):- %----> isi
menu keluar
ask.
ask:-
yes_no( "Exit","i'm give up", ?),
!,message("Yes", "try again!",!),
end.
ask:-
message("No", "let's play again!", s).
14
DAFTAR PUSTAKA
15
GLOSARIUM
- Algoritma Minimax
Algoritma
minimax merupakan basis dari semua permainan berbasis AI seperti permainan tictactoe misalnya. Pada algoritma minimax, pengecekan akan
seluruh kemungkinan yang ada sampai akhir permainan dilakukan. Pengecekan
tersebut akan menghasilkan pohon permainan yang berisi semua kemungkinan
tersebut. Keuntungan
yang didapat dengan menggunakan algoritma minimax yaitu mampu menganalisis
segala kemungkinan posisi permainan untuk menghasilkan keputusan yang terbaik
karena algoritma minimax ini bekerja secara rekursif dengan mencari langkah
yang akan membuat lawan mengalami kerugian minimum. Semua strategi lawan akan
dihitung dengan algoritma yang sama dan seterusnya.
Ini berarti, pada langkah pertama komputer
akan menganalisis seluruh pohon permainan. Dan untuk setiap langkahnya,
komputer akan memilih langkah yang paling membuat lawan mendapatkan keuntungan
minimum, dan yang paling membuat komputer itu sendiri mendapatkan keuntungan
maksimum. Dalam penentuan keputusan tersebut dibutuhkan suatu nilai yang
merepresentasikan kerugian atau keuntungan yang akan diperoleh jika langkah
tersebut dipilih. Untuk itulah disini digunakan tahap logika untuk mengevaluasi nilai
sebagai nilai yang merepresentasikan hasil permainan yang akan terjadi jika
langkah tersebut dipilih.
Biasanya
pada permainan tic tac toe ini digunakan nilai 1,0,-1 untuk mewakilkan hasil
akhir permainan berupa menang, seri, dan kalah. Dari langkah-langkah inilah komputer akan
menentukan simpul mana dari pohon permainan yang akan dipilih, tentunya simpul
yang akan dipilih tersebut adalah simpul dengan tahap-tahp logika yang akan menuntun
permainan ke hasil akhir yang menguntungkan bagi komputer maupun user.
16
