Đề tài: Xây dựng chương trình Game 15-Puzzle

Tr

ng đ i h c H i Phòng

ườ

ạ ọ

ả

Khoa Toán-Tin

Đ tài xây d ng ch

ng trình Game

ự

ề

ươ

15-Puzzle

Giáo viên h

ng d n: Nguy n Ng c Kh

ướ

ễ

ẫ

ọ

ươ

ệ

ự

ngươ

Sinh viên th c hi n: Ø Nguy n Văn Hùng ễ Ø Đào Quang Ph Ø Đào Nh t Th nh

ậ

ị

N i dung

ộ

i thi u Game 15-Puzzle

ớ

ệ

Ø Game 15-puzzle còn g i là Gem Puzzle, Boss Puzzle, Game of

ọ

Ø Là trò ch i di chuy n trên m t khung bao g m các ô vuông đánh

Fifteen, Mystic Square và nhi u tên khác ề

ể

Ø Trò ch i này cũng t n t

ơ ứ ự ẫ ộ ồ ng u nhiên v i m t ô b thi u ớ ế ộ ị s theo th t ố

t nh h n là 8-Puzzle

c khác nhau, đ c bi ỡ

ặ

ệ

ỏ ơ

i trong các kích ồ ạ ơ

i thi u Game 15-Puzzle

ớ

ệ

Ø N u kích th

ế ặ

c đ t tên t ơ ượ ọ ọ ơ ượ ng ô và s l ng ng s l ướ ế ượ ặ ươ ứ c g i là 8-Puzzle ho c 9- c g i là 15-Puzzle ho c ặ ng c a ủ ố ượ ố ượ

c là 3 x 3 ô, trò ch i đ Puzzle, và n u là 4 × 4 ô, trò ch i đ 16-Puzzle, đ không gian

Ø M c tiêu c a trò ch i là đ t các ô theo tr t t ơ

b ng cách tr t ậ ự ằ ủ ụ ặ ượ

Ø n-Puzzle là m t v n đ c đi n cho các thu t toán mô hình hóa

các ô đ di chuy n không gian tr ng ể ể ố

ề ổ ể ộ ấ ậ

liên quan đ n ế đánh giá

i thi u Game 15-Puzzle

ớ

ệ

ượ ử ụ ườ ề ồ

§ Hàm đánh giá th ố ỗ

ổ

c s d ng cho v n đ này bao g m ấ đ m s ô đ t sai ch và tìm ki m t ng kho ng cách Manhattan ế ả ế gi a m i kh i v i v trí c a nó trong c u hình m c tiêu ữ ng đ ặ ỗ ố ớ ị ủ ụ ấ

ậ ấ

ng di i ấ ả ể ố ượ ả ả ố ằ

§ T t c hàm đánh giá đ u đ chuy n nhi u s không đ ề ẽ ậ ư

u cho các thu t toán tìm ki m nh t đ nh ch ng h n nh A* ề ượ ượ ế c ch p nh n, nghĩa là, s l c đánh giá cao nh m đ m b o t ẳ ấ ị ư ạ

Mô t

gi ả ả

i thu t A* ậ

Ø Trong khoa h c máy tính, A* (đ c là

A sao) là m t thu t toán tìm ọ ậ ộ

ọ ki m trong đ th . ồ ị ế

Ø Thu t toán này tìm m t đ c (ho c t

ậ

ộ ườ ặ ớ ướ i m t m t nút kh i đ u t ng đi t ộ ở ầ ớ i m t nút th a mãn m t đi u ki n ệ ề ộ ừ ộ ỏ ộ

nút đích cho tr đích).

Ø Thu t toán này s d ng m t "đánh giá heuristic" đ x p lo i ạ t nh t đi qua nút đó.

ậ ể ế

ộ ng v tuy n đ ng t ử ụ c l ướ ượ t ng nút theo ừ ế ườ ề ấ ố

Ø Thu t toán duy t các nút theo th t ệ

c a đánh giá heuristic này ậ ứ ự ủ

Mô t

gi ả ả

i thu t A* ậ

Ø A* S d ng các t p: Open , Close (Đ l u các tr ng

ử ụ

ể ư

ậ

ạ

thái)

Và các giá tr : G,H,F (Đ ph n ánh đ t

t c a

ộ ố ủ

ể

ả

ị

tr ng thái)

ạ

Ø Trong đó:

§ Open: Ch a các tr ng thái đã đ

c sinh ra nh ng

ượ

ch a đ

ạ ứ ư ượ xét đ nế c

§ Close: Ch a các tr ng thái đã đ

ứ

ạ

ượ

c xét đ n ế

§ G(x):Chi phí đ đi t

tr ng thái đ u đ n tr ng thái

ể

ừ ạ

ế

ầ

ạ

§ H(x):Là hàm đánh giá heuristic v chi phí nh nh t

ề

ấ

ỏ

ừ x đ đ n đích

ể ế

§ F(x)=G(x)+H(x) :F(x) Dùng đ đánh giá đ u tiên

ộ ư

ể

c a x Nh v y F(x) càng nh thì đ u tiên càng

ư ậ

ộ ư

ủ

ỏ

l n ớ

Mô t

gi ả ả

i thu t A* ậ

Ø Ngoài ra ta còn s d ng thêm 1 giá tr ị

ử ụ

Ø Vi c s d ng thêm giá tr Cha nh m giúp ta có th tìm l

Cha(x):L u l i tr ng thái đã sinh ra tr ng thái x ư ạ ạ ạ

c ể ằ ị i đ ạ ượ

con đ ệ ử ụ ng t ườ ừ ạ tr ng thái đích đ n tr ng thái đ u ế ạ ầ

Mô t

gi ả ả

i thu t A* ậ

ỉ

ứ T0(Tr ng ạ

thái ban đ u).

1. Đ t ặ OPEN ch ch a ầ

Đ t ặ g(T0) = 0 ; Cha(T0)=null ; Tính H(T0) và F(T0)

Đ t ặ CLOSE là t p h p r ng.

ợ ỗ

ậ

c sau cho đ n

ạ

ế

2. L p l ặ khi g p đi u ki n d ng. ặ

i các b ề

ướ ệ ừ

2.a. N u ế OPEN r ng : bài toán

ỗ

vô nghi m, thoát.

ệ

2.b. Ng

c l

i, ch n

ượ ạ

ọ Tmax

trong OPEN sao cho F(Tmax) là

nh nh t

ấ

ỏ

2.b.1. L y ấ Tmax ra kh i ỏ

OPEN và đ a ư Tmax vào CLOSE.

2.b.2. N u ế Tmax chính là Đích

thì thoát và thông báo l

i gi

i là

ờ

ả

Tmax.

Mô t

gi ả ả

i thu t A* ậ

ạ ọ

2.b.3. N u ế Tmax không Đích. Sinh ra các ph i làả ủ Tmax. tr ng thái con c a G i m t tr ng thái này là ạ ộ ỗ Tk, làm các Tk. V i m i ớ c sau b ướ 2.b.3.1.

Tính g(Tk) =

g(Tmax) + cost(Tmax, Tk).

Đ tặ

Cha(Tk)=Tmax

; Tính

H(Tk) và F(Tk)

2.b.3.2. N u t n t

i

ế ồ ạ Tk’

trong OPEN ho c ặ CLOSE

trùng v i ớ Tk.

N u ế G(Tk) < G(Tk’)

thì

G(Tk’)

=

Đ t ặ

G(Tk)

Tính l

i ạ F(Tk’)

Cha(Tk’) =

Đ t ặ

Tmax

2.b.3.3. N u ế Tk ch a ư

xu t hi n trong c

ả OPEN

ệ

ấ

l n ẫ CLOSE thì

Thêm Tk vào OPEN

Mô t

gi ả ả

i thu t A* ậ

Mô t

gi ả ả

i thu t A* ậ

Mô t

gi ả ả

i thu t A* ậ

Mô t

gi ả ả

i thu t A* ậ

ộ ụ

§ Đ ph c t p th i gian c a A* ph thu c vào đánh giá heuristic. c m r ng theo hàm mũ ấ i, nh ng nó s là hàm đa th c khi hàm ứ ả

ứ ạ ườ ộ ượ ở ộ

ủ ng h p x u nh t, s nút đ ẽ ấ ố ư ờ

ờ Trong tr ợ i gi c a đ dài l ộ ủ heuristic h th a mãn đi u ki n sau: ỏ ề ệ

ế

ể

i u, nghĩa là hàm cho k t qu là chi ả ố ư ố ủ h i đích. Nói cách khác, sai s c a ớ ả h * -

§ trong đó h* là heuristic t ừ x t phí chính xác đ đi t không nên tăng nhanh h n lôgarit c a "heuristic hoàn h o" ơ ự ừ x t hàm tr v kho ng cách th c t ả

i đích. ả ề ủ ớ

Mô t

gi ả ả

i thu t A* ậ

§ V n đ s d ng b nh c a A* còn r c r i h n đ ph c t p

ắ ố ơ ề ử ụ ứ ạ ớ ủ ộ ộ

§ Trong tr

th i gian. ấ ờ

ng h p x u nh t, A* ph i ghi nh s l ng nút tăng ườ ớ ố ượ ấ ả ấ ợ

§ M t s bi n th c a A* đã đ

theo hàm mũ.

ộ ố ế ệ

ượ ng này, m t trong s đó là A* l p sâu d n ( ể ủ ộ ể ặ ầ

c phát tri n đ đ i phó v i hi n ớ ể ố iterative ớ ớ ạ memory-bounded A* - MA*) simplified memory bounded ớ ớ ạ

t ố ượ i h n ( deepening A*), A* b nh gi ộ và A* b nh gi i h n đ n gi n ( ả ơ ộ A*).

Mô t

gi ả ả

i thu t IDS ậ

Ø Thu t toán tìm ki m sâu d n(IDS-Iterative deepening search)

ầ

Ø Là thu t toán tìm m t đ

ế là m t thu t toán tìm ki m trong đ th ồ ị ậ ộ ế ậ

ừ ộ

ộ ườ c (ho c t ặ ớ i m t m t nút kh i đ u t ng đi t ộ ở ầ ớ i m t nút th a mãn m t đi u ki n ệ ề ộ ỏ ộ ướ

Ø Thu t toán này s d ng gi

ậ nút đích cho tr đích)

i thu t DFS(Depth First Search) ử ụ ả

ậ cho t ng đ sâu trong cây tìm ki m ậ ừ ế ộ

Mô t

gi ả ả

i thu t IDS ậ

ØTìm ki m theo chi u sâu-DFS

ế

ề

§ Phát tri n các nút ch a xét theo chi u sâu – ề ư đ sâu gi m c xét theo th t

ứ ự ộ

ượ

ả

ể Các nút đ d nầ

§ Cài đ t:ặ

ộ

fringe là m t c u trúc ki u ngăn x p ể ớ ượ b sung vào đ u

ế ầ

ổ

ấ (LIFO) – Các nút m i đ c a ủ fringe)

DFS (N, A, n0, ĐICH)

{

fringe ← n0;

closed ← ;∅

while (fringe ≠ ) do∅

{ n ← GET_FIRST(fringe); // l y ph n t đ u tiên c a ầ ử ầ ủ fringe ấ

closed ← closed n;⊕

if (n ĐICH) then return SOLUTION(n); ∈

if (Γ(n) ≠ ) then fringe ← Γ(n) fringe; ∅ ⊕

}

return (“No solution”);

}

Mô t

gi ả ả

i thu t IDS ậ

§ Ví d DFS: ụ

Mô t

gi ả ả

i thu t IDS ậ

§ Ví d DFS: ụ

Mô t

gi ả ả

i thu t IDS ậ

§ Ví d DFS: ụ

Mô t

gi ả ả

i thu t IDS ậ

§ Ví d DFS: ụ

Mô t

gi ả ả

i thu t IDS ậ

§ Ví d DFS: ụ

Mô t

gi ả ả

i thu t IDS ậ

§ Ví d DFS: ụ

Mô t

gi ả ả

i thu t IDS ậ

ØTìm ki m sâu d n-IDS

ế

ầ

§ Áp d ng gi ả ụ có đ dài<=1 ộ

i thu t DFS đ i v i các đ ng đi (trong cây) ố ớ ậ ườ

i gi i), ti p t c áp d ng ả ụ

§ N u th t b i (không tìm đ ế i thu t DFS đ i v i các đ ả

§ N u th t b i (không tìm đ

gi ấ ạ ậ ố ớ c l ế ụ ượ ờ ng đi có đ dài <=2 ộ ườ

i gi i), ti p t c áp d ng ả ế ụ ụ

§ …(ti p t c nh trên, cho đ n khi: tìm đ

gi ế i thu t DFS đ i v i các đ ả ấ ạ ậ ố ớ c l ượ ờ ườ ng đi có đ dài <=3 ộ

i gi ế ụ ư ế c l ượ ờ ả i ho c ặ

toàn b cây đã đ c xét mà không tìm đ i gi i) ộ ượ c l ượ ờ ả

Mô t

gi ả ả

i thu t IDS ậ

i ớ

IDS (N, A, n0, ĐICH, l) // l: gi h n đ sâu

ạ ộ

{

; depth

∅

fringe ← n0; closed ← ← l;

while (fringe ≠ ) do∅ { n ← GET_FIRST(fringe); // l y ấ

ph n t

đ u tiên c a

ầ ử ầ

ủ fringe

closed ← closed

n;⊕

if

(n

ĐICH)

then

return

∈

SOLUTION(n);

if (Γ(n) ≠

) then

∅

{ case d(n) do // d(n): đ sâu c a

ủ

ộ

nút n

[0..(depth-1)]: fringe ← Γ(n)

⊕

fringe;

depth: fringe ← fringe

Γ(n);

⊕

(depth+1): { depth ← depth + l;

if (l=1) then fringe

Γ(n);

⊕

else fringe ← Γ(n)

fringe;

⊕

}

return (“No solution”);

}

Mô t

gi ả ả

i thu t IDS ậ

• Ví d IDS ụ

Mô t

gi ả ả

i thu t IDS ậ

• Ví d IDS ụ

Mô t

gi ả ả

i thu t IDS ậ

• Ví d IDS ụ

Mô t

gi ả ả

i thu t IDS ậ

• Ví d IDS ụ

Mô t

gi ả ả

i thu t IDS ậ

ng các

nút

c sinh ra trong gi

§ V i đ sâu ớ ộ ượ

d và h s phân nhánh b, thì s l ố ượ ầ ậ

i thu t tìm ki m sâu d n là: ế

ệ ố ả

§ Đ ph c t p v th i gian c a IDS

NIDS = (d+1)b0 + db1 + (d-1)b2 + … + 3bd-2 +2bd-1 + 1bd

ộ ứ ạ ề ờ ủ

§ Đ ph c t p v b nh c a IDS

(d+1)b0 + db1 + (d-1)b2 + … + 3bd-2 +2bd-1 + 1bd = O(bd)

O(bd)

ộ ứ ạ ề ộ ớ ủ

i thu t xây d ng Game 15-Puzzle

Áp d ng gi ụ

ả

ự

ậ

Ø M t b ng 4x4 v i các ô trong đó có s t

Bài toán 15-puzzle:

1->15 và 1 ô tr ng ộ ả ố ừ ớ ố

Ø Các ô đ c đ t ượ ặ ở đ i ch cho nhau ỗ ổ

Ø Tìm cách di chuy n các ô sao cho các con s v đúng th t

các v trí ng u nhiên, ô tr ng và ô s có th ể ẫ ố ố ị

ố ề ứ ự ể

Ø Bài toán đ t ra ở chuy n là ít nh t ấ ể

đây là tìm ph ng án t i u sao cho s l n di ặ ươ ố ư ố ầ

i thu t xây d ng Game 15-Puzzle

Áp d ng gi ụ

ả

ự

ậ

Tr ng thái đ u

Tr ng thái đích

ầ

ạ

i bài toán đi u ki n đ u tiên c n quan tâm là xác đ nh ệ ề ầ ầ ị

§Đ gi ể ả tr ng thái đích ạ §Ti p sau đó là d a vào tr ng thái đích và tr ng thái đ u đ xem ế bài toán có gi

ể ầ ạ

ạ c hay không ự i đ ả ượ

i thu t xây d ng Game 15-Puzzle

Áp d ng gi ụ

ả

ự

ậ

§ V i bài toán 15-Puzzle ta có đi u ki n gi

ệ

ề

ớ

i đ ả ượ

c nh sau: ư

.N mod 2 = 0 và ô tr ng n m trên dòng trên ằ ố ch nẵ tính t ừ

xu ngố

§ Vi c tính N s đ

trên xu ng .N mod 2 = 1 và ô tr ng n m trên dòng ố ằ lẻ tính t ừ ố

Đ u tiên hãy th tính có bao nhiêu s bé h n 5

sau ô ch a giá

ử

ứ

ở

ố c là 4 (nh ng ô khoanh tròn)

tr 5. K t qu nh n đ

ữ

ả ậ ượ

ế

ầ ị

c theo các b ẽ ượ ệ ướ c nh sau: ư

i thu t xây d ng Game 15-Puzzle

Áp d ng gi ụ

ả

ự

ậ

T

ng t

ươ

ư ậ

ự

ễ

ấ

nh v y v i ô có giá tr 11. D th y trong 4 ô ị (9,13,14,12) có 1 giá tr nh h n 11 là 9.

ớ ị ỏ ơ

i ô cu i cùng (12) và c ng d n các

ầ

ớ

ộ

ồ

ố

 Làm nh trên t ô đ u tiên (7) t ừ ư c giá tr nh n đ ậ ượ ị

 N = 6+4+1+2+0+1+1+2+6+0+1+0+1+1+0=26

 Ta có ô tr ng n m trên dòng 2 và N mod 2 = 0 => Bài toán gi

ằ

ố

34 c i đ ả ượ

i thu t xây d ng Game 15-Puzzle

Áp d ng gi ụ

ả

ự

ậ

Ø Áp d ng gi ụ

i thu t A* đ gi i quy t bài toán v y vi c ti p ả ể ả ế ệ ế ậ

Đ i v i bài toán puzzle ng

ườ

ự

ố ớ ổ

ủ

ố

ủ c s d ng và nó có tên g i là

ệ ng đ

ng đánh giá tr ng thái d a i ta th ạ vào t ng s ô sai l ch c a các ô s so v i v trí đúng c a nó. Đây ớ ị ố ọ Manhattan. là cách tính th

ượ ử ụ

ườ

Ví d :ụ

theo ta c n xây d ng hàm đánh giá heuristic(H) ầ ậ ự

Đích

i thu t xây d ng Game 15-Puzzle

Áp d ng gi ụ

ả

ự

ậ

Trong b ng s ố 7 vào đúng v trí ố 4×4 trên, đ di chuy n ô s 3 ô khác), đ di chuy n ô s ố ể ể

ả ể ị

ể ầ

Làm l n l

ta c n di chuy n nó 9 v đúng v trí ta c n di chuy n nó ầ ể 3 l n(qua ể 1 l nầ ầ ề ị

Ta tính đ

t nh v y cho t ng ô s ầ ượ ư ậ ừ ố

Nh v y

c H = 3+2+1+0+1+1+0+1+2+2+1+1+1+1+1=18 ượ

tr ng thái đích thì H s có giá tr th p nh t là = ư ậ ở ạ ị ấ ẽ ấ

ả

Xin chân thành c m ơn!

Đề tài: Xây dựng chương trình Game 15-Puzzle

Chủ đề:

Đồ án công nghệ thông tin

Đồ án khoa học máy tính

Tr

ng đ i h c H i Phòng

ườ

ạ ọ

ả

Khoa Toán-Tin

N i dung

ộ

1. Đ t ặ OPEN ch ch a ầ

2. L p l ặ khi g p đi u ki n d ng. ặ

2.a. N u ế OPEN r ng : bài toán

2.b. Ng

2.b.1. L y ấ Tmax ra kh i ỏ

OPEN và đ a ư Tmax vào CLOSE.

2.b.2. N u ế Tmax chính là Đích

Tmax.

ạ ọ

2.b.3. N u ế Tmax không Đích. Sinh ra các ph i làả ủ Tmax. tr ng thái con c a G i m t tr ng thái này là ạ ộ ỗ Tk, làm các Tk. V i m i ớ c sau b ướ 2.b.3.1.

Tính g(Tk) =

g(Tmax) + cost(Tmax, Tk).

Đ tặ

Cha(Tk)=Tmax

; Tính

H(Tk) và F(Tk)

2.b.3.2. N u t n t

i

ế ồ ạ Tk’

trong OPEN ho c ặ CLOSE

trùng v i ớ Tk.

N u ế G(Tk) < G(Tk’)

thì

G(Tk’)

=

Đ t ặ

G(Tk)

Tính l

i ạ F(Tk’)

Cha(Tk’) =

Đ t ặ

Tmax

2.b.3.3. N u ế Tk ch a ư

xu t hi n trong c

ả OPEN

ệ

ấ

l n ẫ CLOSE thì

Thêm Tk vào OPEN

i ớ

IDS (N, A, n0, ĐICH, l) // l: gi h n đ sâu

ạ ộ

{

; depth

∅

fringe ← n0; closed ← ← l;

while (fringe ≠ ) do∅ { n ← GET_FIRST(fringe); // l y ấ

ph n t

đ u tiên c a

ầ ử ầ

ủ fringe

closed ← closed

n;⊕

if

(n

ĐICH)

then

return

∈

SOLUTION(n);

if (Γ(n) ≠

) then

∅

{ case d(n) do // d(n): đ sâu c a

ủ

ộ

nút n

[0..(depth-1)]: fringe ← Γ(n)