Chủ đề 3 - Tìm hiểu về heuristic trong các trò chơi
DuongNT
Các anh chị tập trung trao đổi về chủ đề này bằng cách:
- Phân tích các trò chơi có sử dụng heurictics
- Hướng dẫn sử dụng Demo các trò chơi on/offline
Have a good result!
Trọng Cả
O1. Giới thiệu
Line là một game mini cổ điển được nhiều người chơi ưa thích với cách
chơi cực kỳ đơn giản được Microsoft tích hợp trong các hệ điều hành cũ
bắt đầu từ Windows 98,Windows XP.
Game Lựa Đậu được xây dựng trên cơ sở của game Line, tuy nhiên hình
ảnh và giao diện của game sẽ mang đến cho người chơi một cảm giác mới
lạ dựa trên nền một câu chuyện cổ tích rất quen thuộc “Tấm Cám ”
Lựa Đậu thời @
Như thường lệ, hàng năm triều đình có một ngày hội game để các game
thủ có dịp trổ tài và để chọn ra một đội tuyển để đi thi đấu với các
vương quốc khác. Ngày hội đã sắp tới rồi mà Tấm thì lại rất muốn tham
gia nhưng sợ dì ghẻ bắt phải lựa đậu mới cho đi như năm ngoái.Tấm gục
mặt xuống bàn phím khóc nức nở. Không ngờ,tay Tấm đụng trúng phím tắt
và Bụt Google hiện lên. Như bắt được vàng,Tấm liền hỏi Bụt Google cách
để vượt qua thử thách lựa đậu do Dì Ghẻ đặt ra.Bụt liền đưa cho Tấm
game Lựa Đậu và dặn: “Để có thể lựa đậu nhanh, hằng ngày con phải bỏ
ra một ít thời gian để luyện game này,nhiệm vụ của con là phải sắp ít
nhất 5 hạt đậu giống nhau thành một hàng ngang hoặc hàng dọc, hoặc
chéo thì những hạt đậu đó sẽ tự động biến mất và tự chui vào những hộp
đựng riêng biệt.Con cố luyện tập nhé! Chúc con thành công!” Bụt vừa
dứt lời thì Dì Ghẻ phát hiện Tấm lên mạng nên đã ngắt kết nối internet
nhưng may mắn cho Tấm game Lựa Đậu là game offline. Và kể từ hôm đó,
ngày nào Tấm cũng dành một ít thời gian để luyện game với hi vọng vượt
qua được thử thách của Dì Ghẻ để đi dự hội.
2. Phương pháp/thuật toán
Để làm trò chơi Lựa Đậu, đầu tiên phải xác định được đường đi của hạt
đậu (khi chọn một hạt đậu và chọn vào một ô trống nào đó trên bảng).
Có thể có nhiều cách để xác định đường đi này. Đồ án này sẽ trình bày
cách sử dụng thuật toán Heuristic để tìm đường đi của hạt đậu trên
bảng
2.1 xây dựng đồ thị
Đưa ma trận cho trước về danh sách các điểm kề theo hình
Sau đó thiết lập danh sách kề bằng cách:
- Lặp xét hết từng điểm trên ma trận
- Tại mỗi điểm chỉ xét có tạo cạnh liên thông với 2 điểm lân cận
tiến¬¬¬¬¬
Vì thuật toán này có tính lặp nên chỉ xét 2điểm các điểm lân cận trên
cũng sẽ được xét và tạo cạnh với điểm đang được xét
2.2 Thuật toán Heuristic:
¬¬¬¬
2.2.1 Ý tưởng:
Duyệt dần các điểm trên đồ thị này bằng cách sau khi đi tới 1 điểm,
đánh dấu điểm đó đã đi và tiếp tục duyệt các điểm lân cận của điểm đó.
Để duyệt những điểm kề của một điểm chúng ta tiến hành lặp để tìm kiếm
có điểm hiện tại trong dach sách kề hay không. Heuristic là dựa vào
các chỉ số tọa độ hiện tại của điểm hiện tại với điểm đích với mong
muốn với bước đi như thế nào đó sẽ là đúng và trùng với bước đi ngắn
nhất.
Tuy nhiên không phải mọi trường hợp heuristic cũng sử dụng số bước
tính toán là ít nhất, thậm chí đôi lúc đường đi mà thuật heuristic tìm
ra còn dài hơn các thuật toán vét cạn khác
2.2.2 Mô phỏng thuật toán
Thực hiện tìm kiếm heuristic trên danh sách
{Điểm s là điểm bắt đầu, điểm f là điểm kết thúc}
<Khởi tạo stack rỗng>
push s
pathVisited(s) := 1
isFound := false
while (<Nếu stack chưa rỗng>)
{
pop x
if (x == f)
isFound := true
<Hàm heristic chọn các điểm ưu tiên, cho một biến đại diện chung là r>
<push r>
r := pathVisited(x)+1
}
Thực hiện tìm đường trên đồ thị
if (isFound=True)
{
tim := pathVisited(f)
curPos = f
trace(tim) := curPos
while (pathVisited(curPos)) > 1
{
Lặp tìm điểm x lân cận của curPos thỏa bằng tim-1
if (pathVisited(x) = tim-1)
{
trace(tim-1) := x
curPos := x
Lộc PhamNhu
bài toán NP-đầy đủ…, có nghĩa là nó không có lời giải khả thi, thay vì
đi tìm lời giải tối ưu ta đi tìm lời giải có thể chấp nhận được.Các
lời giải này chính là thuật giải hueristic. Giải bài toán theo thuật
giải heuristic thường dễ dàng và nhanh chóng đưa ra kết quả hơn so với
giải thuật tối ưu, vì vậy chi phí thấp hơn. Thuật giải Heuristic
thường thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động
của con người.
Các thuật giải này rất phong phú như nguyên lý vét cạn thông minh,
nguyên lý tham lam (Greedy), đệ quy quay lui, nhánh cận...Do thuật
toán Heuristic được con người sử dụng thường mang đặc trưng của những
gợi ý hay lời khuyên, nên các phương pháp dựa trên Heuristic đôi khi
không chỉ ra con đường trực tiếp để đạt tới mục đích.
Đối với những bài toán trí tuệ phức tạp, số khả năng có thể lớn tới
mức không thể có một máy tính nào dầu hiện đại đến mấy đáp ứng nổi.
Việc lựa chọn một nước đi tốt nhất trong 1 số trò chơi đòi hỏi phải
tìm kiếm trong khoảng 10 mũ 40 khả năng khác nhau, thậm chí đối với
chơi cờ, số khả năng cỡ 10 mũ 120. Một cách xử lý tốt trong những
trường hợp này là sử dụng thao tác rút gọn các hướng tìm kiếm.
Vấn đề quan trọng là ở chỗ, chúng ta biết khai thác khéo léo thông tin
tại mỗi trạng thái để tìm ra thứ tự ưu tiên và đẩy nhanh quá trình tìm
kiếm. Thông thường ta gắn với mỗi trạng thái của bài toán với một số
đo (một hàm đánh giá) nào đó để đánh giá mức độ gần đích của nó.
Để minh họa cho thuật toán Heuristic, chúng ta cùng nghiên cứu bài
toán Ta-canh (8-puzzle). Đây là một trò chơi được một nhà thiết kế trò
chơi nổi tiếng của Mỹ là Sam Loyd phát minh vào cuối những năm 1870 và
đã trở thành một trò chơi được cực kỳ được ưa chuộng ở Mỹ vào thời
điểm đó, cho đến nay vẫn chưa tìm ra được phương án tối ưu.
Trò chơi bao gồm một hình vuông kích thước 3x3 ô. Có 8 ô có số, mỗi ô
có một số từ 1 đến 8. Một ô còn trống. Mỗi lần di chuyển chỉ được di
chuyển một ô nằm cạnh ô trống về phía ô trống. Vấn đề là từ một trạng
thái ban đầu bất kỳ, làm sao đưa được về trạng thái cuối là trạng thái
mà các ô được sắp lần lượt từ 1 đến 8 theo thứ tự từ trái sang phải,
từ trên xuống dưới, ô cuối dùng là ô trống.
tại mỗi trạng thái, bạn chỉ được phép chuyển các con số tối đa 4
hướng lên trên, xuống dưới, sang trái và sang phải từ một ô có con số
sang ô trống.
Để giảm không gian tìm kiếm ta k duyệt thứ tự mà duyệt 1 cách "mù
quáng", ta xây dựng một thứ tự ưu tiên để duyệt các hướng đi. Đó là sử
dụng hàm đánh giá h với ý nghĩa: h(u) cho biết số các chữ số trong
trạng thái u không trùng với vị trí của nó trong trạng thái đích. Khi
đó, trạng thái có tiềm năng dẫn tới đích nhanh nhất là trạng thái có
hàm đánh giá h đạt giá trị min.
Thuật toán cho trò chơi 8-puzzle:
Một số ký hiệu:
- Tập P các trạng thái chờ quyết định được tổ chức dưới dạng stack.
- Tập Q các trạng thái đã phát triển được tổ chức dưới dạng hàng đợi.
- Tập P′ lưu trữ tạm thời các trạng thái kề v của u khi ta phát triển
một đỉnh u (v thu được từ u thông qua một phép di chuyển con số).
- Biến found.
- Hàm father.
Thuật toán:
Input: trạng thái ban đầu u0 và trạng thái đích ut
1.P← { u0 } ; Q ← Φ ; found ← false; P′ ← Φ ;
2.While(P ≠ Φ ) and (not found) do
2.1. Loại trạng thái u ở đỉnh stack P và đặt nó vào Q:
Pop(P,u);
Ađ(u,Q);
2.2. If u=ut then found ← true
Else for v thuộc kề(u) do
If v không thuộc P hợp Q then
Begin
father (v) ← u;
Ađ (v,P′);
End;
If P′ ≠ Φ then
Begin
Sắp xếp P′ theo thứ tự tăng của hàm h. Chuyển P′ vào đỉnh stack P sao
cho trạng thái nhiều hứa hẹn nhất (có giá trị hàm h nhỏ nhất) ở đỉnh
của P.
End;
(Chú ý: Sau khi chuyển P′ vào đỉnh stack P thì P′ trở thành rỗng.)
Output: Nếu found = false thì bài toán vô nghiệm.
Nếu found = true thì nghiệm là đường đi từ u0 tới ut được xác định
bằng cách sử dụng hàm father.
Việc lựa chọn hàm đánh giá cho bài toán trên có thể tính thông qua
tổng khoảng cách ngắn nhất (tính theo ô) của từng con số trong trạng
thái hiện tại so với vị trí đúng của nó trong trạng thái đích.