Xây dựng ứng dụng trò chơi cờ tướng trên nền điện thoại
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (2.99 MB, 57 trang )
•^j-f.Mf
TRlTOfNG DAI HOC AN GIANG
KHOA Kt THU^T - CONG NGHE - MOITRI/CING
LAM LONG H^U - DTH082043
KHOA LUAN TOT NGHIEP Dj^I HQC NGANH CU*NHAN TIN HQC
XAY D^TNG tfNG DVNG TRO CHOI COf
TlTdNG TREN NEN DIEN THOAI
TRJCiNG D^l HQC
AN GIANG
THUVIEN
Giang vien hircrng dan:
ThS. Nguy^n Thai Dir
An Giang, 05/2012
h(n cam on
Lai ddu tien, con xin chdn thdnh gui lai cam an sdu sac nhdt vd kinh trQng nhdt den
cha m^, gia dinh da diu ddt con suot nhung chdn dudng ddi, giup con vuat qua nhung
khd khan thu thdch trong cuqc song.
Em xin chdn thdnh gui lai tri an sdu sdc nhdt din quy Thdy, Co Khoa Ky thudt - Cong
ngh$ - Mdi trucmg Trudng Dai hoc An Giang, nhung ngudi da tan tinh, hit long day
do chung em, tqo mqi dieu kien thudn Ipi nhdt de chung em hodn thdnh de tdi tot
nghiip. Dqc bi$t, em xin gui lai tri an sdu sdc nhdt den Thdy Nguyen Thai Du da tan
tinh hudng dan, truyen dqt kien thuc vd chi dan cho em trong suot qua trinh thuc hien
di tdi.
Sau ciing, tdi xin gui Idi cam an den tdt cd cdc ngudi ban, nhung ngudi anh em da
cung tdi chung vai, dqng vien vd giup tdivu^t qua moi khd khan, thu thdch suot qudng
dudng sinh vien...
Longxuyen, ngdy 15 thdng 05 ndm 2012
Sinh vien thire hien:
Lam Long Hau - DTH082043
PHAN TOM TAT
PHAN I: TONG QUAN BE TAI
M6 ta vl ting quan dl tai, dat ra muc tieu tir ting quan d^n cu the cho de tai, neu ra ly
do chpn de tai, gidi thieu lich su va xu tuning phat trien cua de tai. Gidi han pham vi
nghidn cuu, dua ra giai phap tilp can va cong cu du^c sur dpng trong de tai.
PHAN II: CO SOf LY THUYET
Trinh bay khai quat \h noi dung cua Ah tki dupe nghien ciiu va xay dung, cac khdi
ni?m vh cb tudmg, cdr thS va cac luat trong cdf tudng.
So luac v6 nln tang 1^p trinh J2ME cho thilt bi di dong, cac cong cu phdt trien va tich
hop J2ME cho viec phat triln ling dung tren nln di dong h tra Java. Mo ta va giai
thich \h giai thuat Minimax v^ giai thuat Anpha-beta, giai thuat chinh su dung trong
viec phat triln ling dung.
PHAN III: N0I DUNG VA KET QUA NGHIEN CUtJ
Trtah bay e^e phSn phan tich thilt kl Aim bdo cac yeu ciu thuc tl cua he thing dat ra,
dam bao thuc hien day du va dung chiic nang cua he thong.
PHAN IV: TONG KET VA HU"6NG PHAT TRIEN
Tom t5t nhttng ket qua dat dupe va ding thcri neu len nhiing han che ciia de tai. Ben
canh do cung dua ra dupe hudug phat triln len tim cao mdi cho de tai.
MUC LUC
Chucmg 1. TONG QUAN CUA BE TAl1
1.1.Sor lupc vh cac h dikt hanh tren n6n dien thoai[7]1
1.1.1.He di&t hanh BlackBerry cua RIM1
1.1.2.He diSu hanh iPhonecua Apple1
1.2.3.HSdi^u hanh Android cua Google1
1.2.4.Hedieuhanh Symbian ciia Nokia1
1.2.Tdng quan vS lip trinh game tren dien thoai1
1.3.Ly do chpn &h tai2
1.4.Lich su d^ tai2
1.4.1.Mpt so game Cor ttrdng nude ngoai2
1.4.2.Mot s6 game Cd tudng trong nude3
1.4.3.Nhanxet3
1.5.Cong cu thvrc hien3
1.6.Pham vi he thdng4
1.7.Giai phap cho he thdng4
Chuong 2. CO SCJ LY THUYET5
2.1.Khai qu^t vS Cd tudng va luat Cd tudng5
2.1.1.GidithieuCd tudng5
2.1.2.Cac quan cd va ludt di5
2.2.Khai niem Cd thg7
2.3.Khai quat v^ J2ME7
2.4.So lupc v6 cac bo cong cu phat triln ung dung - SDK (Software Development
Kit) va cac moi trudng phat tri^n tich hop - IDE (Intergated Development
Environment) cho J2ME9
2.4.1.J2ME Wireless Toolkit (WTK)9
2.4.2.Borland Jbuilder 20059
2.5.Giai thuat Minimax va giai thuat cai tiSn Alpha-beta[1I]10
2.5.1. Trd choi cd tong bang 010
Khoa luan t6t nghiep
2.5.2.Dinh ly Minimax10
2.5.3.Giai thu^t Minimax11
2.5.4.Giai thu^it cai tiSn Alpha-beta13
2.6. Urig dpng16
Chuong3.PHATTRIENHETH6NG20
3.1.Nghiep vu h th6ng20
3.2.Phan tich he thdng21
3.2.1.Sor d6 Usecase21
3.2.2.Dae ta Usecase22
3.2.3.Thi6t kg h^ th6ng28
Chuong 4. TONG KET VA HlTCSNG PHAT TRIEN49
4.1. K6t qua dat dircrc49
4.2.Hanch649
4.3.Huong ph^t trien49
TAl LIEU THAM KHAO50
Xay dung ling dung tro chcri cb tuong tren ngn difn thoai
Khoa luan t6t nghiep
DANH MUC HINH
Hinh2.1.1:Cacquancdrtrenb^ncdrtud
Hinh 3.1. Quy trinh quan ly tro choi Ca turang20
Hinh 3.2.1. Usecase thyc hien cac chiic nang ting quan cua he thong22
Hinh 3.2.3.1.1: Cac thanh phan tuang tac cua kiln true28
Hinh 3.2.3.1.2: So dl chuc nang cua he thing30
Hinh 3.2.3.1.3: So dl giao dien cua he thing31
Hinh 3.2.3.2.1: giao dien chinh cua tro choi32
Hinh 3.2.3.2.2: Luge dltuan tur "chai mdi"35
Hinh 3.2.3.2.3: Luac dl hoat dpng "chai mdi"36
Hinh 3.2.3.2.4: Luac dl tuln tu "chai tilp"39
Hinh 3.2.3.2.5: Luac dl hoat d^ng "choi tilp"'.40
Hinh 3.2.3.2.6: Luac dl tuln ty "bay ccr thl"43
Hinh 3.2.3.2.7: Luac do hoat dprig "bay ca thl"44
Hinh 3.2.3.2.16: Luac dl tuan ty "giai ca thl"47
Hinh 3.2.3.2.17: Luge dl hoat d|ng "giai cor thl"48
Xay dung urng dung tr6 chai c^ tudng tren nen diSn thoai
Khoa luan tot nghiep
DANH MUC BANG
Bang 1.5:B^ngc6ngc\ith^rchi^n4
Bang 3.1.2.1: Bing dat ta Usecase chai mai23
Bang 3.2.2.2: Bang dat ta Usecase bay c^ thg23
Bang 3.2.2.3: Bang dac ta Usecase chcri tiSp24
Bang 3.2.2.5: Bang dac ta Usecase phuc h6i nirac di25
Bang 3.2.2.6: Bang dac ta Usecase cai dat tro chai25
Bang 3.2.2.7: Bang dac ta Usecase luu \&n ca26
Bang 3.2.2.8: Bang dac tk Usecase chai cct27
Bang 3.2.2.9: Bang dac ta Usecase Giai ccr th27
Bang 3.2.3.1: Bang Yeu cau h? th6ng29
DANH MUC TIT VIET TAT
Y ng hla
Tir viet tat
RIM
CLDC
MIDP
WTK
RMS
Research In Motion
Connected Limited Device
Cofiguration
Mobile Information DeviceProfile
J2ME Wireless Toolkit
Record management system
Xay d\rng ling dpng tro chai cfr tirdng tren nen di^n tho^i
Khda luan t6t nghiep
Chmmg 1. TONG QUAN CUA BE TAI
1.1.Sff luffc vi cac he diiu hdnh tren nin dien thoaim
1.1.1.He dieu hanh BlackBerry cua RIM
BlackBerry OS la nSn ting phdn m6m tu huu do Research In Motion (RIM)
triSn cho dong san phim BlackBerry. ^en canh he diSu hanh nay dap ling rit nhiSu
nhftng tinh nang, no con co nhiing dilm manh ndi bac khac nhir BlackBerry Maps,
cung cap kha nang da nhiem manh me. Hien nay BlackBerry dang chiSm linh thi
trudng the gidi, dac biet la My.
1.1.2.He dieu hanh iPhone cua Apple
iPhone dupe trang bj man hinh cim ung da diSm, may chup anh, kha nang choi
nhac rat tot. Vdi viec ho tro da di^m va tinh nang bao mat cao se la thach thiic Ion cho
lap trinh vien khai pha. H^ dieu hanh nay dang duoc gidi thuong hru ua chupng, vdi
nhung tinh nang vuot troi ve giao dien cung nhu kha nang dap ling cao vl mat cong
nghe nen hd diu hanh nay dang giu vi tri xep hang cao.
1.2.3.He dieu hanh Android cua Google
Android la mot nen tang md cho thi^t bi di dong ciia Google (gom he didu hanh,
middleware va mot so ung dung co ban). Android dang duoc nhi^u ngudi hirdng d^n
va dac biet la Viet Nam. Dilm manh cua Android n^m d chd no la mot he thdng hoan
toan md nen ai cung co th8 phat trien ling dung.
1.2.4.He dieu hanh Symbian cua Nokia;
Nokia dong may dien thoai dupe nhi^u ngudi dung chpn d8n, vdi Symbian dang
tdng budc khang dinh vi th ciia minh tren linh vuc dien thoai thong minh
(smartphone). Dac biet day la he dieu hanh ma nguon md. Cac ham APIs dupe cong
bo rpng rai de bat cii ai cung cd the phat trien phan mem cho Symbian OS, dieu nay
dupe dat ra de day manh kha nang canh tranh cua Symbian.
1.2.Tdng quan ve lap trinh game tren dien thoai
Vdi su phdt trien ngay cang chdng mat va manh me cua cac thiet bi di dong cung
nhu xu hudng cong nghe cua thdi dai, nen cong nghiep che tao di dong cung nhu phat
triSn cac ling dung tren nen di dong cung theo da do ma ldn manh nhanh chdng va
dong vai tro quan trpng trong cong nghe thong tin ma dien hinh la dien thoai di dong,
mot thiet bi cam tay rat quen thupc va gan gui vdi moi chiing ta. Va vdi mot chiec dien
thoai chung ta cd the lam dupe gi? Giai tri, nghe nhac, doc bao... va cung rat nhidu
ling dung khac. Trong do dac biet la lmh vuc giai tri ma dien hinh la game tren dien
thoai da va dang phat trien vupt bac. Chinh vi nhu cau ngay cang cao va da dang ve
linh vuc nay nen lap trinh game cho dien thoai di dong ngay cang trd thanh mot nganh
"hot" va cd doanh thu cao. Tuy nhien de cd dupe mot game ma mpi ngudi yeu thich
thi khong phai di, no ddi hoi cac nha phat trien van dung va ket hop nhieu mang kien
thiic khac nhau nhu: giai thuat, dd hpa, ngdn ngu l^p trinh, va dac biet la sd thich choi
Xay dimg ling dung trd choi cd tudng tren nen dien thoaiTrang 1
Khda Iuan t6t nghi^p
game. Vdi ngon ngu lap trinh thi co nhieu ngon ngtt khac nhau de ta co the bat dau hoc
lap trinh game tren dien thoai chlng han nhu: Java, dotnet (C#), C/C++, Objective C,
Visual C++... trong do thi Java dupe danh gia cao vi no dupe h tra tren cac nln
smartphone pho biln hien nay nhu Android, Symbian, BlackBerry...
Hien nay, lap trinh game dang din trd thanh mot nganh cong nghiep, cung vdi su
phat triln ngay cang cao va sau cua cong nghe tren thilt bi di dong thi nln cong nghiep
game cung c6 vi the ngay cang cao va quan trong trong tuong lai.
1.3.Ly do chon di tdi
Game dang la mdn an tinh than khong thi thilu trong thai dai cong nghiep ngay
nay, khi thai gian danh cho giai tri hay du lich khong nhi^u thi game dong vai tro quan
trong trong viec gidp giai quyet phan nao cac vln de tinh thin cho con nguai, ben canh
do thi cac game co tinh tu duy cao nhu: Ca vua, Ca tudng... da va dang trd thanh xu
hudng phat triln chung cua cac game ngay nay. Chinh vi thi toi chon dl tai "Xay
dung ung dung tro choi cd tudng tren nen dien thoai", ngoai nhthtg ly do tren thi
viec tao cho ban than cd duac mot phan kien thiic ve llnh vuc mdi noi nay, ren luyen
va hoc hoi them tu duy giai thuat trong lap trinh la van de chinh.
1.4.Lich su de tdi
1.4.1. Mot so game Cd tudng nude ngoai
-Chinese Chess Master III (CCH)
Chuang trinh cua hang T-Time Technology, tac gia la Jiang Zhu ngudi Dai Loan,
con duac goi la Cd Tudng Tarn Tang hay Cd Tudng 6ng Gia (Ton Vd Tu), mot
chuang trinh cd tudng cue hay vdi trinh dp ttr thap len cao la cac nhan vat trong Tay
Du Ky hoac cac nhan vat thai su Saddam Hussein, Madonna, Bush...CCH chi chay
ngoai DOS va trong Windows 98 vdi mode tuang thich, con trong Windows XP thi
thong bao loi "Abnormal Program Termination!". Ve trinh dp thi trudc nam 2000,
CCH la chuang trinh cd tudng manh nhat, va trong may tinh cua nhung ai ydu cd luc
do cung deu cd chuang trinh nay.
-XqLearner 4.x
Chuang trinh cd cua mot Hoa kieu d My noi tieng vdi nhieu cong cu giup ngudi
chai tu luyen tap va hoc cd tudng rlt hay. Trinh dp cung rlt cao thich hap cho nhieu
cap dp ngudi dung.
-XieXieMaster 2.x
Nha vo dich giai cd tudng may the gidi nam 2004 tai Dai Loan (The 2004 World
Computer Chinese Chess Champion) ctia Pascal Tang, Hoa kieu Phap goc Hoa.
Chuang trinh nay thudng duac nhieu ky tM ua chupng vi trinh dp tuyet vdi dong deu
d ca 3 giai doan choi cd cung nhu tinh chuyen nghiep cua no. Ho trp nhieu cap dp,
nhieu ngon ngii va giao dien kha dep vdi nhilu tuy bien theo y thich rlt de su dung.
Phan biet vdi ban XieXie Free cd chuc nang dan gian va trinh dp khong cao nhung
chai cd chap (5 phut) thi rlt hay.
-XqMaster 2.x, 3.x
Xay dung ling dung trd chai cd tudng tren nen dien thoaiTrang 2
Khda luan tot nghiep
Nha v6 dich giai Olympic cd tudng may the gidi nam 2005 tai Dai Loan 10th
Computer Olympiad) cua Z. Mingyang. Hien nay nhieu ngudi cho rang day la chuong
trinh cd tudng manh nhat, nhat la d giai doan trung cuoc no rat manh nen nhieu
chuong trinh khac bi bai dudi tay no. Hien gid no phat trien nhidu phien ban tdi uu cho
cac thi he CPU 32bit va 64bit.
1.4.2.Mot so game Cd tudng trong nude
-Saola -The Chinese Chess Challenger
Day la chuong trinh cd tudng cua Pham Hong Nguyen, giang vidn DHQG Ha Npi,
hoi du cac yeu to de hoc tap va luyfn cd thich hop nhat cho ngudi khong chuyen Ian
chuyen nghiep. Ve giao dien va chiic nang, Saola cd phan vuot troi hem cac chuong
trinh khac vi no cd phan co sd du: lieu tich hop cong them rat nhieu chuc nang tien ich
di kern. Saola khai cuoc doi khi khong tdt 15m nhung trung cuoc va tan cuoc lai kha
hay.
-NeoChess
Day la chuong trinh cd tudng tren dien thoai di dong duoc phat tridn bdi cong ty
Tea-m nam 2008, giao dien kha than thien. NeoChess cd ba muc dp di, trung birth,
khd ho trp nhieu ngudi choi. Chuong trinh choi d mpi muc dp kha hay, thai gian suy
nghT tuong doi nhanh so vdi tren may tinh ca nhan.
1.4.3.Nhan xet
-HSu h6t cac chuong trinh game Cd tudn^ deu dupe phat triln tren may tinh ca
nhan, mac du kha nang choi cd d trinh dp cao rlt tot tuy nhien chua tich hop dupe cac
tuy chpn nang cao cho ngudi choi nhu : sip cd the
-Viec phat trien tren trd choi tren nen may tinh nen toe dp xut ly cua may cao,
khong doi hdi nhieu ve bp nhd, do hpa dep mat. Tuy nhien neu phat trien tren dien
thoai thi cac van de nay can dupe chu trpng rat nhieu.
-Cung cap kha nang choi cd 2 ngudi thong qua cac thidt bi kit ndi nhu wireless va
Bluetooth ddi vdi dien thoai chua dupe chii y.
1.5. Cong cu thuc Men
Xay dung ling dung trd choi cd tudng tren nen dien thoaiTrang 3
Khoa luan tot nghiep
Giai doan
Cong cu
Nha san xuat/ Tu phat trien, Phien ban
Power Designer 15.1
Sybase
2010
Microsoft Word
Microsoft
2010
Netbean
Netbeans
Sun Microsystems
6.9.1
Phan tich
Thucthi
Java (TM) ME SDK
Nokia
Nokia 5300
3.0
Bang 1.5: Bang cong cu thuc Men
1.6.Pham vi he thong
He thong duoc phan dinh ra 2 giai doan cu thl nhu sau:
-Giai doan 1: hoan thanh cac chiic nang co ban, mo rong cho he thong co the
dap ling nhu cau giai tri cho nguoi dimg.
-Giai doan 2: Phat triln ling dung len miic do dap ling sau va chuyen nghiep ve
miic do, h6 tro da nen va da ngon ngii.
1.7.Giaiphdp cho he thdng
Giai phap duac chon dk phat tri^n he thong la sur dung ngon ngii lap trinh Java (cu
the la J2ME), ho tro duac da so cac dong dien thoai pho bien hien nay nhu Nokia
va mot s6 smartphone.
Ngoai ra nham dap ling ve miic dp chai tot cho may nen de nghi va ap dung them
mot so giai thuat nhu: cat tia alphabeta tang toe dp va chieu sau tim kiem cho may
phuc vu cupc chai duac tot han.
Xay dung ling dung tro chai ca tuang tren nen dien thoai
Trang 4
Khoa Man t6t nghigp
Chmmg 2. CO SO LY THUYET
2.1. Khdi qudt ve Cd tudng vd luat Cd tu&ng
2.1.1. Gift thi^u Co tirong
Mgc dich cua van eft Van c& dugc tiln hanh giiia hai nguft, mot nguft elm quan
Trang (hay D6), mot ngirft elm quan Den (hay Xanh la cay). Mpc dich cua m6i
nguft la tlm mft each di quin tren ban cfr theo dung luat de chilu bi hay bit Tudmg
(hay Soai, hoac Suy) cua d6i phuong va gianh thing lgi.
-
Ban c^ va quan ca:
+ Ban eft Ik mpt hinh chfi nhat do 9 duong dpc yk 10 duftig ngang clt nhau
vuong g6c tai 90 diem hop thanh. Mot kho^ng trong goi la s6ng (hay ha) nlm
ngang giira ban eft chia bin ccr thanh hai phln d6i xiing blng nhau. M6i ben
co mpt cung Tudng hinh vuong (Cuu cung) do 4 6 hpp thanh t^i cac duong doc
4, 5, 6 ke tir duftig ngang cu6i cua m6i ben, trong 4 6 nay co ve hai duftig
cheo xuyen qua.
+ M6i van ca liic bit dlu phai co dd 32 quin, chia dlu cho mi ben g6m 16
quan Trlng (Do) va 16 quan Den, g6m 7 loai quan. Tuy ten quan ca cua mi
ben co the vilt khac nhau (ky hi^u theo chO: Hin) nhung gia tri va edeh di quan
cua chung l^i gi6ng nhau hoan toan. Bay loai quin c6 ky hieu va s6 lupng cho
moi ben nhu sau:
Hinh 2.1.1: Cac quan cd tren ban cd tudng
2.1.2. Cac quan ca va luat di
2.1.2.1. Quan tuftig
Tuong dupe chot chat trong cung va co tai 2 Sy va Tupng canh gac hai bSn. KM lam
nguy, tit ca sin sang xa than "hp gia". Chinh dieu nay lam cho ^uin dich du co lieu
chet Ian xa vao cung khong chac da thang dupe. Nhu the muon thang mot vin ca cung
rlt kh6 khan, ca may hoa ca \k rlt Ian. Tu mot thuc tl nhu vay, lu^it "16 mat Tuang"
Xay dung tag dyng tro chai cor tutag tren nln di6n thoaiTrang 5
Khda luan t6t nghiep
dupe thiit lap: mot bSn Tudng da chiim dupe mot 16 r^i m3 Tudng b6n kia thd mat ra
16 3y la bi thua ngay lap tire, du hai Tudng 6 each xa nhau muon trung.
Do co luat "lp mat Tudng" nen se co he qua: Tuong b6n n3y mac nhien chiem luon
mot phan ba dipn tich Cuu cung cua dpi phuong, khien d3t mrong than cua doi phuong
bi thu hep dang ke. Do la chua ndi niu Tuong chiSm dupe lp gida thi Tuong cua d6j
phuong mat t<5i hai phin ba cung dim cua mlnh, nghia 13 chi con von ven c6 3 diem dl
di chuyln. Luc d6 d6i phuong chi c6n 1 quan cung c6 thi torn gon dupe du ring dang
d ngay trong cung cim cua minh. Trong khi cd tuong khi Tuong mit hit du6ng chay
thi thua chii khong hoa nhu trong c6 vua.
Tuong chi dupe di ngang hay di dpc ttrng budc mpt trong pham vi cung tudng.Tinh
theo kha nang chien dau thi Tuong la quan yeu nhat do chi di nude mpt va bi gidi han
trong cung. Tuy nhien trong nhieu tinh hu6ng, dac biet khi cd tan don "lp mat tudng"
lai to ra rift hiim va manh.
2.1.2.2.Quan Si
Chung dung ngay sat canh Tuong, chi di timg buoc mpt va di theo duong cheo trong
Cuu cung. Nhu vay, chung chi di chuyen va dung t^i 5 diem va dupe coi la quan cd
yiu nhdt vl bi han chi nude di. Sy co chuc nang trong vi6c bao ve Tudng, mdt Sy dupe
cho la nguy hiim khi dii phuong con du 2 Xe ho3c dhng Xe Ma T6t tin cong. Bo
Phao an Sy r6i dung 2 Xe tin cong la don chiin thuat thudng thiy.Trong tan cupc, Sy
thudng dupe dua len cao de lam ngoi cho Phao tin c6ng.
2.1.2.3.Quan tupng
Quan Tupng ddng ben canh qu3n Sy va tuong duong vdi Tupng trong cd vua. Quan
nay di theo duong cheo cua hinh vuong gom 2 6 cd. Chung khong dupe qua song,
chiing cd nhiem vu d lai ben nay song di bao ve vua. Chi cd 7 diim ma Tupng cd thi
di chuyin tdi va dung d do.
Tupng se khong di chuyen dupe den vi tri d3 neu neu cd 1 quan dat tai vi tri giUa cua .
hinh vuong 2 6. Khi do ta gpi la Tupng bi can va vi tri can dupe gpi 13 "mit Tupng".
Tupng dupe tinh 13 manh hon SI mpt chut. Kh3 nang phdng thu cua Tupng cung dupe
tinh nhinh hern. Ndi chung mat Tupng cd de nguy han mt ST.
2.1.2.4.Quan ma
Ma di theo dudng cheo hinh chtt nhat (gdm 2 6 vudng liin nhau) hoac ndi chinh xac
han 13 Ma di tren canh dai roi rg sang canh ngang cua hinh chii nhat. Neu ngay gitta
canh dai cd bit ky quan n3o durng c3n thi M3 n3y bi c3n, khong thuc hien nude di do
dupe.
2.1.2.5.Quan xe
Quan Xe di v3 an theo mpt dudng thang dumg hoac ngang giong het quan Xe trong cd
vua. Chiing bat dau nude di tir phia gdc cua b3n cd, chiing dupe coi 13 quan cd manh
nhat trong cd tudng.
2.1.2.6.Quan phao
Quan Phao di giong quan Xe, theo chiiu thing ddng hoac ngang, nhung an quan blng
each nh3y qua 1 quan cd khac.
Xay dpng ung dpng trd chai cd tudng tren nin dien tho^iTrang 6
Khoa luan t6t nghipp
2.1.2.7.
Quan tot
Quan Tot a day tuong tu nhu quan T6t or cb vua, chiing di thing theo chiiu diing va co
thi an quan tung bubc mQt. Khi T6t qua dupe song, chung co the di va an theo chieu
ngang. Khong gibng nhu trong cb vua, chung khong co luat phong Hau, hay Xe,... khi
di din hit ban ca, luc nay, chung duqc g
2.2.Khdi niem Ccr the
Cb the la hinh thuc cb ma ban ca luc ban dau da co san cac the ca, quan cb dang a cac
vi trf nhu trong mpt van ccr dang da, muc do thS cb tu dl dSn kho va ngufri chai phai
thing dupe sau mpt s6 nuac di dupe yeu ciu tu trubc. Ca the hay dupe thay a cac le
hoi dan gian.
2.3.Khdi qudt vi J2ME
Muc tieu cua J2ME la cho phep nguai lap trinh viSt cac chuang trinh ling dung dpc lap
vai thiit bi di dpng, khong quan tarn den phin cung. J2ME dupe xay dung bing cac
tang khac nhau de giau di viec th\rc hien phSn ciing khoi nha phat trien. Sau day la cac
ting cua J2ME dupe xay dung tren CLDC:
May ao Java
Hinh 2.4: Cac ting cua CLDCJ2ME
M6i ting tren ting "phin ciing thiit bi" la ting trim tupng han cung cip cho lap
trinh vien nhieu giao dipn lap trinh ling dung (Application program interface) than
thien han.
Xay d^rng ling dpng tr6 chai cb tubng tren nen diin tho^i
Trang7
Khda Man t6t nghiep
T^ng phln cirng thiet bj (Device hardware layer): day chinh la thilt bi di dong
tht sir vdi cau hinh phan ciing cua no vl bo nhd vS t6c do xut ly. That ra n6 khong
phSi la mot phln cua J2ME nhung no la ncd xult phat. Cac thilt bi di dpng khSc
nhau co the co cSc bo vi xu ly khac nhau vdi cSc tap ma lenh khac nhau. Myc tieu
cua J2ME la cung clp mot chuin cho tit cS cac loai thilt bi di dong khac nhau.
Tang mSy So Java (Java virtual machine layer): Khi ma nguon Java duac Men
dich no du^e chuyln ddi thSnh ma bytecode. Ma bytecode nSy sau do duac chuyln
thanh ma ngon ngtt may cua thilt bi di dong. Tang may So Java bao gdm KVM (K
virtual machine) la bo bien dich ma bytecode cd nhiem vy chuyen ma bytecode cua
chuang trinh Java thanh ngon ngtt may dl chay tren thiet bi di dpng. TSng nay
cung clp mpt sp chuin hoa cho cac thilt bi di dpng nao cd J2ME KVM.
Ting cau hlnh (Configuration layer): Tang cau hlnh cua CLDC dinh nghTa giao
dien ngon ngti Java (Java language interface) ca ban de cho phep chuong trinh
Java chay tren thiet bi di dong. Day la mot tap hpp cSc API dinh nghla I5i cua ngon
ngu J2ME. L^p trinh vien co the su dung cac lop va phuang thiic cua cSc API nay
tuy nhien tap cac API huu dung han duac chdra trong ting hifn trang (profile
layer).
Ting Men trang (Profie layer): TSng Men trang hay MIDP (Hien tr^ng thilt bi
thong tin di dpng - Mobile Information device profile) cung clp tap cSc API huu
dpng han cho l^p trinh vien. Muc dich cua hi^n trang IS xay dung tren lop clu hinh
vS cung cSp nhieu thu viSn tag dung han. MIDP dinh nghla cac API riSng Met cho
thiet bi di dong. Cung co the co cSc Men trang va cSc API khSc ngoSi MIDP duac
dung cho umg dung. Cung co the co mot Men trang dinh nghia cac API cho viec tao
cac ling dpng Bluetooth. Thuc tl, cSc hien trang ke tren vS tap cSc API dang duac
xSy dung. Chuin Men trang PDA IS dac tS JSR - 75 vS chuin Bluetooth API IS dac
tSJSR-82.
Hien nay MIDP co hai phien bSn IS MIDP 1.0 vS MIDP 2.0 cung clp:
+ CSc lap vS cSc kieu dtt lieu.
+ H6 tra doi tuang Display.
+ Ho tra Form vS giao dien nguai dung.
+ H6 tra Timer vS Alert.
+ H6 tra Record Management System (RMS) cho viec luu tru dtt lieu.
Cac tinh nang n6i bat cua MIDP 2.0 so vdi MIDP 1.0
+ Nang cap tinh nang bSo mat, ho trgr giao thttc HTTPS, kiem soSt viec ket noi mSy
di dong vai server.
+ Them cSc API h6 tra Multimedia.
+ Md rpng cSc tinh nSng cua Form.
Xay dung ung dyng trd chai cd tudng tren nln dien thoaiTrang 8
Khoa luan t6t nghiep
2.4. Set lucre ve ede bo cong cuphdt triin ung dung - SDK (Software
Development Kit) vd ede nidi trucmg phdt triin tick hap - IDE (Intergated
Development Environment) cho J2ME
2.4.1.J2ME Wireless Toolkit (WTK)
J2ME Wireless Toolkit (WTK) la m6t bp cong cy phat triin Java J2ME (Java
Development Kit - JDK) cung cap cho cac lap trinh vien moi trubng gia lap, cong cy,
tai lieu va cac vi du cln thiSt dl phat triin cac ling dung MIDP.
WTK khong phai la mot IDE ho^n chinh, bcri vi no da bo cac tinh nang soan thao va
go roi yon dupe xem la bat bupc phai co trong mpt IDE. Tuy nhien, KToolbar, dupe
cung cap trong bp WTK la mpt moi trucmg phat triin t6i thilu cung dp mpt GUI danh
cho viec bien dich, dong goi va thuc thi cac dug dpng MIDP.
WTK 2.2 cung cung dp cac bp gia lap da dupe cai tiln ydri cac tinh nang ^ia l^p,
monitor va debug mdi. Ngoai ra, WTK cung co mpt co chl dupe them vao tien trinh
build ciia KToolbar de cho phep vipc tich hpp va thuc thi bp obfuscate Java byte code
khi dong goi MIDlet suite.
WTK 2.2 dupe cai thien t6c dp va h6 trp cac API mdi theo chuln dupe dinh nghia bdi
JCP:
oConnected Limited Device Configuration (CLDC) 1.1 (JSR 139)
oMobile Information Device Profile (MIDP) 2.0 (JSR 118)
oJava Technology for the Wireless Industry (JTWI) 1.0 (JSR 185)
oWireless Messaging API (WMA) 2.0 (JSR 205)
oMobile Media API (MMAPI) 1.1 (JSR 135)
oPDA Optional Packages for the J2ME Platform (JSR 75)
oJava APIs for Bluetooth (JSR 82)
oJ2ME Web Services Specification (JSR 172)
oMobile 3D Graphics API for J2ME (JSR 184)
2.4.2.Borland Jbuilder 2005
-Moi truong lam viec cua JBuilder cho J2ME hoan toan gilng nhu cong viec phat
triin Java binh thucmg, ngoai trtr mpt di^u la co them cac tab va option trong cac hop
thoai, va hai wizard moi: MIDP MIDlet wizard va MIDP Displayable wizard.
-Ngoai ra, trong phien ban JBuilder Professional va Enterprise, trinh Archive Builder
bay gia co thi tao ra mot MIDlet suite vii cac tap tin manifest va JAD tuang ung.
JBuilder 2005 cung cai dat WTK 2.1 dupe su dung nhu mpt moi trucmg gia lap. Tuy
nhien, JBuilder con cung cip cac hudng din cho viec tich hpp them cac J2ME JDK
khac, chlng han nhu Nokia Developer Suite for J2ME vii Siemens Mobility Toolkit
(SMTK).
-Ngoai cac tinh nang chinh cua JBuilder, khi lap trinh J2ME ta dupe th&n cac tinh
nlng sau:
Xly dpng ling dyng tro chai cb tudng trln nen din thoyiTrang 9
Khoa luan tot nghifp
•Code completion cho cac lop CLDC/MIDP
•Duyet class/package cho cac lop CLDC/MIDP
•Chuyin dii JDK
•C4c MIDP wizard
•Bo thiSt ki true quan (visual designer) cho cac thanh phin giao dien
•Cong cu g& roi MIDlet
•Dong goi file JAD va JAR
•Nap du: lieu thong qua OTA (Over The Air Provisioning)
2.5. Giai thuatMinimax va giai thuat cdi tiin Alpha-betar"1
2.5.1.Tro choi co ting bang 0
-Tro choi co ting bang khqng la tro choi co tong gia tri k^t qua (ma ngudi thing
dupe hucrng) la co dinh. Bat cu ben nao thing (+1) cung lam cho ben kia thua cuoc
(-1), tuong ung vdi tinh huong ganh dua thuan tuy, cu6i cung dan tdi ting (+1-1) =
0.
-Co vua la mot tro choi co ting bing khong boi khong thi co trudng hop ca hai ben
deu th^ig hoac deu thua. NSu mot ben thing thi ben kia nhit dinh la thua va nguqc
lai. Thl thao la nhung vi du diln hinh nhit cua tro choi co ting bing khong. Nha
vo dich chi co thi dat duoc vinh quang khi toan bp cac dii thu khac diu thua cupc.
Trong mot giai bong da ting si train thing luon bing ting si tr4n thua cung la boi
tinh chat tong bang khong ay.
-Viec dau tu kinh doanh chiing khoan cung chinh la mot tro choi co ting bing
khong, boi yi a do, so tien thua 16 cua nha dau tu nay se la tien lai cua nha diu tu
khac. Nha dau tu co the mat trang hoac thing Ion, lpi nhuan ma anh ta thu dupe co
the dii bing ca gia tai, doi khi mang sing cua nhung nha dau tu tai chinh khac.
2.5.2.Dinh ly Minimax
Vai tro chai co tong bang khong va co hai nguai choi, mot trong 3 dieu kien sau day
se dan den 2 dieu kien con lai.
1.Ton tai mot cap can bing.
V, = maxminM(p,p) = min max M(p,q) = v,
2.p
iip
3.Tin tai mot so thuc v, mot chiin lupc hin hop p* va mot chiin lupc hin hop q*
sao cho:
Xay dung ling dung tro choi ca tuang tren nen dien thoaiTrang 10
Khda luan tot nghiep
Dieu kien (3 a) noi rSng tdn that trung binh cho ngudi chai 2 dung chien luac thuln tuy
bat ky nao khdng nhd hem v. Tuang tu dieu kien (3b) noi tdn that trung binh cua ngudi
chai 1 dung chien thuat thuan tuy bat ky thi khdng ldn horn v.
2.5.3. Giai thuat Minimax
Xet mdt trd chai ddi khang trong do hai ngudi thay phien nhau di nude cua minh nhu
cd vua, cd tudng, cd card,... Trd chai cd mdt trang thai bit diu va mdi nude di se bidn
ddi trang thai hien hanh thanh mdt trang thai mdi. Trd chai se ket thuc theo mdt quy
dinh nao do, theo do thi cupc chai se dan den mdt trang thai phan anh cd mdt ngudi
thing cupc hoac mdt trang thai ma ca hai ddi thu khdng thd phat tridn dupe nude di
cua minh, ta gpi no la trang thai hda cd.
2.5.3.1.^ tudng
Hai ddi thu trong mdt trd chai duac gpi la MIN va MAX. MAX dai dien cho ddi thu
quydt gianh thing loi hay cd ging tdi da hda uu thd cua minh. Ngupc lai MIN la ddi
thu cd ging tdi thidu hda didm sd cua MAX. Ta gia thidt MIN cung dung cung nhung
thong tin nhu MAX.
Mdt trd chai nhu vay cd the duac bieu dien bdi mdt c^y trd chai. Mdi mdt mit cua c^y
bieu dien cho mdt trang thai. Nut gdc bieu dien cho trang thai bat dau cua cupc chai.
Mdi mit la bidu diln cho mdt trang thai kit thiic ciia trd chai (trang thai thing, thua
hoac hda). Neu trang thai x dupe bieu dien bdi mit n thi cac con cua n bidu dien cho tat
ca cac trang thai ket qud ciia cac nude di cd the xuat phat tu trang thai x. Do hai dau
thu luan phien nhau di nude cua minh nen cac miic (lap) tren cay trd chai cung luSn
phien nhau la MAX va MIN. Cay trd chai vi thi con cd ten la cay MIN-MAX. Tren
cay trd chai cac mit ling vdi trang thai ma tvr do ngudi chai MAX chpn nude di se
thudc lap MAX, cac mit ling vdi trang thai ma tir do ngudi chai MIN chpn nude di se
thudc lap MIN. Chien luac minimax the hien qua quy tac dinh tri cho cac mit tren cSy
trd chai nhu sau:
-Neu mit la mit la gan cho mit do mdt gia tri dl phan anh trang thai thing thua hay hda
cua cac diu thu.
-Su dung gia tri cua cac mit la de xac dinh gia tri ciia cac mit d cac mtrc tren trong cay
trd chai theo quy tac:
+ Niit thudc lap MAX thi gan cho no gia tri ldn nhat cua cac mit con ciia mit do.
+ Niit thudc lap MIN thi gan cho no gia tri nhd nhat ciia cac nut con ciia mit do.
Gia tri duac gan cho tung trang thai theo quy tic tren chi rd gia tri ciia trang thai tdt
nhat ma mdi ddi thu cd thd hy vpng dat duac. Ngudi chai se sir dpng cac gia tri nay dd
lua chpn cac nude di cho minh. Ddi vdi ngudi chai MAX khi den luat di, ngudi chai
nay se chpn nude di ling vdi trang thai cd gia tri cao nhit trong cac trang thai con, con
vdi ngudi chai MIN khi ddn luat se chpn nude di ling vdi trang thai cd gia tri nhd nhat
trong cac trang thai con.
2.5.3.2.Thu tuc Minimax
Xay dung ling dung trd chai cd tudng tren nen dien thoaiTrang 11
Khda ludn t6t nghi^p
Tit y tudng ta co the suy ra cdc budc cua thuat todn Minimax nhu sau:
-Neu nhu dat den gidi han tim kiSm (den ting dudi cung cua cay tim kiem tdrc niit la),
tinh gid tri tinh cua thd co hien t?i ling vdi ngudi choi d do. Ghi nhd kit qua
-Neu nhu muc dang xet la cua ngudi choi cue tieu (niit MIN), dp dung thu tuc
Minimax ndy cho cac con ciia nd. Ghi nhd ket qua nhd nhat.
-Ndu nhu miic dang xet la ciia ngudi choi epe d^i (niit MAX), dp dung thu tuc
Minimax nay cho cdc con cua nd. Ghi nhd ket qua ldn nhat.
Tit y tudng phan tich tren ta cd the xay dung thu tuc Minimax nhu sau:
Ham Minimax nhan vao mot thi cd pos va trd vi gia tri cua thi cd do.
Neu the cd pos tuong ling vdi niit la trong cay trd choi thl trd ve gia tri da duqc gdn
cho niit la. Nguqc lai ta cho pos mdt gia tri tarn value Id -o hoac <x> tuy thupc pos la niit
MAX hay MIN va xet cac thi cd con cua pos. Sau khi mpt con cua pos cd gia tri V thi
dat lai value= max(value, V) ndu n la niit MAX va value= mm(value,V) ndu n la niit
MIN. Khi tit cd cac con cua n da dupe xet thi gia tri tarn value cua pos trd thanh gia tri
cua nd. (INFINITY the hien cho gia tri vo cung).
Ta cd gia ma cho gidi thuat Minimax nhu sau:
2.
function Minimax(pos): integer;
3.
value, best: integer;
4.
begin
ifpos la nut Id then return eval(pos)
5.
6.
else
7.
begin
{Khdi tao gia tri tarn cho best}
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
ifpos Id nut MAX then
best:= -INFINITY
else best: = INFINITY;
{ham genPos sinh ra mqi nude di tit the cdpos}
genPosfpos);
{Xet tdt cd cac con cua pos, moi ldn xdc dfnh dupe gia trj cua mot niit con,
ta phdi dat I^i gia trf tarn value. Khi da xet hit tat cd ede con thi value Id gia tri
ciian}
while (con lay dupe mpt nude di m) do
begin
pos .= Tinh the cd mdi nhd di m;
value = Minimax(pos);
ifpos Id nut MAX then
if (value > best) then best := value;
ifpos Id nut MIN then
if (value < best) then best:- value;
end;
Minimax := best;
Xdy d^rng ling dpng trd chai cd tudng tren nen di^n tho^iiTrang 12
Khda luan t6t nghiep
24.end;
Xem xet doan chuong trinh tren ta thdy:
- Co hai ham la ham eval(pos) va ham genPos(pos). Ham eval(pos) thuc hien viec tinh
gid tri (lupng gid) cua the cd pos. Ham genPos(pos) sinh ra tat cd cdc nude di co the tu
th.6 cd pos hien tai. Vide xay dung hai ham nay se phu thudc vao timg trd choi cu thd.
Ham danh gia Eval ung vdi moi trang thai (the cd) pos cua trd choi vdi mot gia tri so
Eval(pos). Gia tri nay la sir danh gia dp lai thd cua (rang thai pos. Trang thai pos cang
thuan lpi cho MAX thi Eval(pos) la s6 duong cang ldn, pos cang thuan loi cho MEN
thi eval(pos) la so am cang nhd, Eval(pos) 0 doi vdi trang thai khdng lai thd cho ai
ca. Chat luang cua chuang trinh chai cd phu thuoc rat nhieu vao ham danh gia. Neu
ham danh gia cho ta sir danh gia khdng chinh xdc vd cac trang thai, no cd the hudng ta
di tdi trang thai dupe xem la tot, nhung thuc td lai rat lai cho ta. Thidt kd mot ham
danh tot la mot viec khd. Ddi hoi ta phai quan tam den nhieu nhan to. (^ day cd sir mau
thuan giura do chinh xac ciia ham danh gia va thai gian tinh cua no. Ham danh gia
chinh xac se ddi hoi riit nhieu thdi gian tinh todn, ma ngudi choi lai bi gidi han bdi thai
gian phai dua ra nude di.
2.5.4. Giai thuat cai tien Alpha-beta
Thuat toan Minimax yeu cau phai cd su phan tich qua hai budc doi vdi khong gian tim
kiem: budc dau truydn xuong den do sau cua ldp dp dung heuristic va budc sau de
truyen nguac cac gia tri tren cay. Minimax Ian theo tat ca cac nhanh trong khdng gian
bao gom ca nhiing nhanh ma mot thuat toan thong minh han cd the bd qua hay tia bdt.
Cac nha nghien cuu trong linh vuc chai game da xay dung mot ky thuat tim kidm goi
la cat tia Alpha-beta nham nang cao hieu qua tim kiem trong cac bai toan trd chai hai
ddi thii.
Bp danh gid tinh trong thu tuc Minimax cdn dupe thuc hien ddi vdi tit cd cac nut tai
miic cudi cua cay trd chai (nut Id). Ta cd thd giam bdt sd tinh toan tdn kem nay bang
each giam sd nhanh cay can tao ra va sd cac danh gia tinh can tinh ra. Do vay mot giai
phap nhu da dung trong thu tuc nhanh va bien la khdng tiep tuc di theo cac dudng
khdng tdt.
Thuat toan Alpha-beta la mot cdi tidn cua thuat toan Minimax nhdm tia bdt nhanh cua
cay trd chai, ldm gidm sd luang nut phai sinh va luang gid, do do cd thd tang dp sau
ciia cay tim kidm.
2.5.4.1. Y tirdng
Y tudng cua tim kiem Alpha-beta rat dan gian: Thay vi neu nhu tim kiem toan bd
khdng gian den mot dp sdu ldp cd dinh, tim kiem Alpha-beta thuc hien theo kieu tim
kiem sau. Cd hai gid tri, goi la alpha va beta dupe tao ra trong qua trinh tim kidm:
-Gid tri alpha lien quan vdi cac mit MAX va cd khuynh hudng khdng bao gid giam.
-Ngupc lai gid tri beta lien quan ddn cac mit MIN va cd khuynh hudng khdng bao gid
tang.
Gia sd cd gid tri alpha cua mot nut MAX la 6, MAX khdng cdn phai xem xet gid tri
truyen ngupc nao nhd han hoac bang 6 cd lien quan vdi mot mit MIN nao do ben dudi.
Xay d\rng ung dung trd chai cd tudng tren ndn dien thoaiTrang 13
Khda luan t6t nghiep
Gia trj alpha la gia tri thip nMt ma MAX co thg nhan dupe sau khi cho r^ng MIN
cung se nhan gia tri t6t nhat cua no. Tucmg tu niu MIN co gia tri beta la 6 no cung
khdng can xem xet cac nut nlm dudfi no c6 gia tri 1cm hem hoac bSng 6.
Dg bit diu thugt toan tun kiim Alpha-beta, ta di xu6ng hit do sau lop theo kieu tim
kigm sau, ddng thdi ap dung danh gia heuristic cho mot trang thai va tit ca cac trang
thai anh em cua no. Gia thuyit tit ci dlu la nut MIN. Gia tri t6i da cua ede nut MIN
nay se dupe truygn ngupc lgn cho nut cha me (la mpt nut MAX). Sau do gia tri nay
dupe gan cho dng bd cua cac niit MIN nhu la mt gia tri beta kit thuc t6t nhlt. Tiip
theo thuat toan nay sg di xu6ng cac nut chau khac va ket thuc vide tim kigm doi vdi niit
cha me cua chung niu gap bit ky mot gia tri nao Ion hon hoac blng gia tri beta nay.
Qua trinh nay goi Id clt tia Beta (P cut). Cach lam tuong tu cung dupe thuc hien cho
viec cat tia Alpha (a cut) d6i vdi cac nut chau cua mot nut MAX.
Hai luat cat tia dua trgn cac gia tri alpha va beta la:
1.Qua trinh tim kigm co thg ket thuc bgn duoi mot nut MIN nao co gia tri beta
nho hon hodc bang gia tri alpha cua mot niit cha MAX bat ky cua no.
2.Qua trinh tim kigm co thg kit thuc bgn duoi mot niit MAX nao co gia tri alpha
Ion horn hoac blng gia tri beta cua mot mit cha MIN bit ky cua no.
Viec cat tia Alpha-beta nhu vay thg hien quan he giua cac niit d lop n va cac niit cr lop
n+2 va do quan he do toan b6 cac cay con bit nguin d lop n+1 diu cd thi loai khdi
viec xem xet.
Chu y ring gia tri truygn ngupc thu dupe hodn toan gidng nhu kit qua Minimax, ddng
thdi tiit kiem dupe cac budc tim kiim mot each dang ki.
Nguygn tac Alpha-beta:
Y tudng nay dupe gpi la nguygn tic Alpha-beta do no ddng trong thu tuc Alpha-beta.
Hai tham so cua thu tuc nay dupe gpi la alpha va beta dupe dung dg theo doi cac triin
vpng - chiing cho biit cac gia tri nlm ngodi khoang [alpha, beta] la cac diim "that sp
tdi" va khong can phai xem xet nua. Khoang [alpha, beta] con dupe gpi la cua sd
alpha, beta. Trong ngii canh cua cac trd choi, nguygn tic Alpha-beta ndi ring, mdi khi
xem xet mot niit bat ki, ngn kiem tra cac thong tin da bigt vg cac niit cha, ong cua no.
Cd thg do cd du thong tin td cha, ong ngn khong can phai lam bat cii viec gi nua cho
nut n^y. Do do, nguygn tac nay cung giup chinh siia hoac xac dinh chinh xac gia tri tai
nut cha, ong no. Nhu trgn ndi, mot each dg tien theo doi qua trinh tinh toan la dung e^e
tham sd alpha va beta di ghi lai cac thong tin theo doi cin thiit. Thu tuc Alpha-beta
dupe bit diu tai nut gdc vdi gia tri ciia alpha la - va beta la +. Thu tuc se tu gpi d
quy chinh no vdi khoang each giua cac gia tri alpha va beta ngay cang hep hom.
2.5.4.2 Giai thuat
-Niu miic dang xet la dinh (gdc cay), d^t gia tri cua alpha la -
va beta la + .
-Niu nhu dat ddn gidi han tim kiim (din tang dudi cdng cua cay tim kigm, niit la),
tinh gia tri tinh cua thg cd hien tai fag vdi ngudi choi d do. Ghi lai kgt qua.
Xay dung fag dpng trd choi cd tudng trgn ngn dign thoaiTrang 14
Khda luan t6t nghiep
-Neu nhir miic dang xdt la cua ngudi chai cue tieu (MIN), thuc hi^n ede cong viec
sau cho den khi tit cd cac con cua no da duac xdt vdi thti tuc Alpha-beta hoac cho
den khi alpha la bang hoac Ion hon beta.
+ Ap dung thu tuc Alpha-beta vdi gid tri alpha vd beta hien tai cho mpt con. Ghi
nhd lai ket qua.
+ So sdnh gid tri ghi nhd vdi gia tri beta, neu gia tri do nhd hon thi dat beta
bang gia tri nidi nay. Ghi nhd lai beta (thu hep khodng [alpha, beta] bang each
giara gid tri beta).
-Nlu nhu miic dang xet la cua ngudi chai cue dai (MAX), thuc hien ede cong viec
sau cho den khi tit ca cac con cua no da duac xet vdi thii tuc Alpha-beta hoac cho
d^n khi alpha Id bang hoac Ion hen beta.
+ Ap dung thu tuc Alpha-beta vai gid tri alpha va beta hien tai cho mpt con. Ghi
nhd l^ii kit qud.
+ So sdnh gid tri ghi nhd vdi gid tri alpha, nlu gid tri do ldn hon thi d^t Alpha
bang gid tri mdi nay. Ghi nhd lai alpha (thu hep khodng [alpha, beta] bang each
tang gid tri alpha).
Tu y tudng tren ta cd ma gid cho ham AlphaBeta nhu ben dudi, trong do depth la do
sau tim kilm, INFINITY la gid tri vo cung, thuat toan tinh todn dua tren thi cd hien tai
pos la ede bien todn cue.
function AlphaBeta(alpha, beta, depth): integer;
begin
if (depth = 0) or (pos Id nut Id) then
AlphaBeta: = Eval { Tinh gid tri the cdpos }
else
begin
best :=-INFINITY;
Gen; { Sinh ra nu?i nude di tie vi tripos }
while (con lay dupe mot nude di m) and (best < beta) do
begin
ifbest > Alpha then Alpha := best;
Thuc hien nude di m;
value := -AlphaBeta(-beta, -Alpha, depth-1);
Bo thuc Men nude di m;
if value > best then best := value;
end;
AlphaBeta := best;
end;
end;
Xay d\mg dtng d\mg trd chai cd tudng tren nln di|n tho^iTrang 15
Khoa luan t6t nghipp
2.6. U ng dung
2.6.1. Danh gia mot the cd
Danh gia mot the cd la mot trong nhtrng nhiem vu quyet djnh chuong trinh chai cor cua
ban co la "cao thu" hay khong. Can cur yao mot thi ca may se gan cho no mot dilm s6
(lupng gia ttnh) de danh gia dp t6t - xau. Nhd diim nay may mdi co thl so sanh cac
thi ca vdi nhau \k biit chpn nude di t6t nhit. D&y la mdt nhiSm vu rlt khd khan va
phdc tap do khong tdn tai mot thuat todn tdng qu&t va thing nhit n^o de tinh diSm.
Diem cua mot the c^^ d\ra tren rlt nhiSu ygu t6 ma kho co th6 s6 hoa h^t dupe nhu phu
thupc vao so lupng va gia tri cac quan ca hi^n tai, php thuQC vao tinh ham, tinh bien,
the cong, the thu cua tung quan'ca cung nhu ca cue dien tran dau.
Trong chuang trinh nay toi chi cai dat phuang phap dan gian nhung ca ban nhdt la
lupng gia dpa tren ca sd gia tri cua tung quan cfr. Cach tinh nay se ldy t6ng gia tri cac
quan cd hien c6 cua ben minh trir di tong gia tri cac quan cd hien co cua ddi phuang.
Do do, mot the cd nay han the cd kia d cho no con nhieu quan ben minh hon, nhieu
quan gia tri cao han cung nhu cd bat dupe nhieu quan va quan gia tri cao cua doi
phuang han khong.
Diem cac quan cd dupe danh gia theo kinh nghiem vh cho bi^t sir tuang quan gitta cac
quan cd. Sau day la dilm tung quan ma mpi ngudi thudng chip nhan:
Quan cfr
KihieuDiem
Tot
PAWN
1 (2 neu da qua song)
SI
BISHOP
2
Tupng
ELEPHANT
2
Ma
KNIGHT
4
Phao
CANNON
4.5
Xe
ROOK
9
Ban cung cd the theo bat ki thang diem nao kh^c tuy theo hieu biet va sd thich cua
minh. Vi dp nhu trong lang cd Viet Nam thudng cho diem cac quan hai khac nhu: Tot
- 1 (2 ndu da qua song), SI - 2, Tupng - 2.5, Ma - 4.5, Phao - 5, Xe - 10.
Trong ban cd, quan Tudng la quan quan trong nhat, du mdt mpi quan hoac dat dupe
th6 cd nao di nua d^u khong dupe mit Tudng vi no din din thua cd. Do do, Tudng
thudng dupe cho mot dilm rdt cao, each biet nhiiu lin so vdi cac quan khac, dam bao
diem tong cua cac quan con deu khong bang dupe Tudng. Trong chuang trinh, toi cho
no 1000 diem. Ham lupng gia nhu sau:
Xay dirng ung dpng trd chai cd tudng tren ndn dien tho^iTrang 16
Khoa luan t6t nghiep
public int hamLuongGia(byte []bc){
int long = 0;
//khal bdo mdng diem ciia cdc qudn cd tren ban cd
int [/diem = {13,6,2,1,1000,7,1};
forfbyte i = 0; i < 90; i++){
//neu Id cd ben may thi cong vdo
iffbc/i] <8&& bc[i] > 0)
long += diem[bc[i]-l];
//nguoc lai se tru ra neu cd ben ngudi choi
elseif(bc[i]>9)
tong-=diem[(bc[i]/10)-l];
}
return long;
2.6.2. Phinrng thvc Anpha-beta
public int alphaBetaf int alpha, int beta, byte depth, byte turn) {
//neu quit den chieu sdu quy djnh thi thuc hi^n luqmggid ban cd
if(depth = 0)
return bc.dokho % 2 = 0 ? hamLuongGia(bc.banCo) :
hamLuongGia2(bc.banCo);
elsef
int best = -10000, value;
//lay todn bo nude di cua qudn cd theo bien turn. Neu turn = -1 thi lay nude di
cua may, nguoc lai turn = 1 Idldy nude di cua ngudi choi.
Vector v = layCacNuocDifbcbanCo, -turn);
inti = 0;
//thuc hi$n vdng Idp cho den khi hit cdc nude di hoqc thda dieu kien cat tia
Anpha-beta
whilefi < v.sizeO && best < beta)/
if/best > alpha)
alpha = best;
// thuc hi$n nude di gid de luqng gid ban cd
taoNuocDi(String.valueOf(v.elementAt(i)));
Xay dyng ling dyng trd chai cai
Trang 17
AN GIANG
THLf VIEN
Khda luan t6t nghiep
//thuc hi^n gqi de quy de lay gid tri tit cdc nut con
value = -a!phaBeta(-beta, -alpha, (byte)(depth-l), (byte)-turn);
// huy nude di gid sau khi ban cd duqc lutyng gid
boNuocDiO;
//gdn tqm thdi lu^ng gid tot nhdt cua ban cd cho Men best
iffvalue > best && Math.abs(value) != 10000){
best = value;
//neu xet din chieu sau quy d\nh thi luu Iqi tarn thdi nude di tot nhdt
iffdepth = bc.doklw){
s = String.valueOf(v.elementAt(i));
return best;
Trong phuang thurc Anpha-beta c6 mpt s6 phucmg thuc h6 tr^ khac nhu sau:
Phuong thiic luprng gid tmh hamLuongGia(bc.banCo), hamLuongGia2(bc.banCo): tuy
theo chieu sau quy dinh cua ngu^^ri choi la chan hay I^ md ta co cac ham luong gia
tuong ung. Ham lugmg gia duac xdt (t phan tren.
Phuang thiic sinh nuac di layCacNuocDi(bc.banCo, -turn): dung dd ldy tit ca cac
nude di cua ngucri chcri hay may tuy thugc vao bidn turn, neu turn = 1 thi ta liy cac
nuac di cua ngudi chai, nguac l^i turn = -1 thi lay cac nude di cua may. Phuang thdc
duac cai dat nhu sau:
public Vector layCacNuocDi(byte []bc, intmauco){
Vector v = new Vector^);
switch(mauco) {
case 1:
for (byte i = 0; i < 90; i++){
if(bc[i] != 0 && bc[i] < 8)
forfbytej = 0;j < 90;j++){
if(kiemTraNuocDi(bc, i,j)){
v.addElement(new String(i + "," +j));
;
Xay dung ting dyng tro chai cd tudng tren nen di^n tho^iTrang 18
