Báo cáo Đồ án 2 Minesweeper - Cơ sở dữ liệu | Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Thành phố Hồ Chí Minh

lOMoARcPSD|46342985 lOMoARcPSD|46342985
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN – ĐHQG TPHCM
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO ĐỒ ÁN 2: MINESWEEPER
MÔN: CƠ SỞ TRÍ TUỆ NHÂN TẠO LỚP: 21CLC07
Giảng viên hướng dẫn: Cô Nguyễn Ngọc Thảo, Thầy Nguyễn Hải Đăng
Thầy Lê Ngọc Thành, Thầy Nguyễn Trần Duy Minh
Danh sách thành viên nhóm:
21127012 – Trần Huy Bân
21127090 – Võ Nguyễn Hoàng Kim
21127419 – Ngô Phước Tài
21127478 – Trần Thị Thanh Vân
TPHCM, tháng 8 năm 2023 lOMoARcPSD|46342985 NỘI DUNG I.
Tổng quan....................................................................................................................................1
I.1. Mô tả bài toán............................................................................................................................1
I.2. Yêu cầu:......................................................................................................................................1
I.3. Các lưu ý trong chương trình...................................................................................................1
I.3.1. Thư viện sử dụng:...............................................................................................................1
I.3.2. Các lưu ý về thực thi chương trình....................................................................................2
I.4 Đánh giá mức độ hoàn thành công việc và đánh giá nhóm......................................................3 II.
Cài đặt CNF và sử dụng thư viện PySat....................................................................................5
II.1. PySat.........................................................................................................................................5
II.2. Cài đặt và tạo ra các câu CNF từ ma trận ban đầu...............................................................5
II.2.1. Ý tưởng thiết lập giá trị trong các câu CNF....................................................................5
II.2.2. Ý tưởng tạo ra các clauses CNF từ ma trận ban đầu......................................................6
II.2.3. Cài đặt thuật toán..............................................................................................................9
II.2.3.1 Các hàm bổ trợ............................................................................................................9
II.2.3.2. Hàm chính - hàm tạo CNF (CreateCNF)................................................................10
III. Thuật toán A* (không dùng thư viện).....................................................................................11
III.1. Ý tưởng thực hiện.................................................................................................................11
III.2. Giải thích thuật toán.............................................................................................................13
III.2.1. Hàm bổ trợ.....................................................................................................................13
III.2.1.1. Hàm tính heuristic..................................................................................................13
III.2.1.2. Hàm tạo các successors...........................................................................................14
III.2.2 Hàm chính – A*..............................................................................................................14
IV. Thuật toán Backtracking và Brute - Force.............................................................................16
IV.1. Backtracking.........................................................................................................................16
IV.1.1. Ý tưởng thực hiện..........................................................................................................16
IV.1.2. Giải thích thuật toán......................................................................................................16
IV.2. Brute - Force.........................................................................................................................17
IV.2.1. Các hàm được sử dụng trong thuật toán Brute - force gồm:......................................17
IV.2.2 Giải thích chi tiết.............................................................................................................18 V.
Dùng thư viện PySat.Solver....................................................................................................19
VI. So sánh giữa A*, Backtracking và Brute-Force và kết quả đạt được...................................20
VI.1. Test case 1 (5 x 5)..................................................................................................................20
VI.2. Test case 2 (9 x 9)..................................................................................................................21
VI.3. Test case 3 (11 x 11)..............................................................................................................21
VI.4. Test case 4 (15 x 15)..............................................................................................................22
VI.5. Test case 5 (20 x 20)..............................................................................................................22 lOMoARcPSD|46342985
VI.6 Đánh giá và so sánh...............................................................................................................23
VII. Video demo thực hiện...............................................................................................................24
VIII. Tài liệu tham khảo....................................................................................................................24 lOMoARcPSD|46342985 I. Tổng quan
I.1. Mô tả bài toán
Minesweeper là một trò chơi đơn giản và quen thuộc trên máy tính với việc
giải đố và tìm các ô mìn trong một bàn cờ kích thước NxN.
Đối với bản game trên các PC hay laptop thì người chơi sẽ tìm một ô bắt đầu
và ở đó sẽ xuất hiện một con số là thông tin về số lượng bom xung quanh (tối đa 8).
Yêu cầu của bài toán đó là giải quyết toàn bộ bàn cờ (bảng) với toàn bộ thông tin
ở tất cả các ô. Đối với yêu cầu đề thì chúng ta sẽ nhận một bảng với các thông số
có sẵn và sẽ dựa vào đó để giải. I.2. Yêu cầu:
1/ Cài đặt được các câu CNF với những ô có mìn sẽ là “True” và các ô không
chứa mìn sẽ là “False”. Ngoài ra các CNF được tạo ra không được trùng nhau.
2/ Cài đặt hàm để tự tạo ra các CNF từ một ma trận ban đầu.
3/ Giải các câu CNF bằng thư viện hỗ trợ PySat và trả về một bàn cờ với
các ô trong đó đã được gắn giá trị phù hợp.
4/ Cài đặt A* để giải CNF
5/ Thực hiện hai thuật toán Brute - Force và Backtracking để giải các CNF
và so sánh thời gian thực thi với thuật toán A*.
I.3. Các lưu ý trong chương trình
I.3.1. Thư viện sử dụng:
Các thư viện sử dụng trong chương trình bao gồm:
- PySat để cài đặt CNF và solver để giải các CNF
- Heapq để phục vụ cho việc hỗ trợ thiết lập thuật toán A*
- Time, Tracemalloc để tính thời gian thực thi khi thực hiện thuật toán 1 lOMoARcPSD|46342985
I.3.2. Các lưu ý về thực thi chương trình 1/ Về chương trình
Khi thực thi chương trình (mã nguồn), cần sử dụng các môi trường thực
thi được Python3. Khi chương trình chạy, chương trình sẽ yêu cầu người dùng
nhập số từ 1 đến 5 tương ứng với 5 files test case đầu vào. Với thứ tự từ 1 đến 5
tương ứng lần lượt là các kích thước (5x5, 9x9, 11x11, 15x15, 20x20). Sau đó
người dùng sẽ lựa 1 trong 3 thuật toán từ 1 đến 4 với thứ tự là Brute Force,
Backtracking, A* và dùng thư viện PySat để giải.
2/ Đặt tên file và tổ chức cây thư mục
Thứ nhất, đối với 5 test case đầu vào phải có dạng InputX.txt với X từ 1
đến 5 và bên trong chứa một ma trận NxN có thể giải. Nhờ vậy, khi thực thi
chương trình, kết quả sẽ đước ghi vào file output theo cú pháp OutputX.txt.
Thứ hai, về thư mục bài nộp sẽ bao gồm 2 folder chính là SOURCE và
REPORT. Trong folder REPORT sẽ chứa 1 file pdf ghi báo cáo các kết quả và
những gì nhóm thực hiện.
Thứ ba, đối với thư mục SOURCE, thư mục sẽ gồm một file mã nguồn
thực thi (.py) và 5 file input (.txt) và 5 file output (.txt) được tạo sẵn chứa lần lượt
các test case và kết quả tương ứng với test case đó.
3/ Quy định về kí hiệu trong file input và output
Đối với file input đầu vào, những ô mang giá trị là số (từ 0 đến 8) sẽ tương
ứng với số lượng mìn xung quanh ô đó. Đối với những ô chưa được mở (chưa có
thông tin thì sẽ được kí hiệu bằng kí tự ‘-’.
Đối với file output đầu ra, những ô mang giá trị là số sẽ tương tự như file input là
mang giá trị từ 0 đến 8 tương ứng với số lượng bom xung quanh. Đối với các ô là mìn sẽ
được kí hiệu bằng kí tự ‘X’. Vì chúng ta sẽ hướng tới việc giải được nên đa phần các
ô trong các test case đều mang giá trị là số hoặc là mìn. Tuy vậy, đối với các ô
không chứa thông tin (không giải được) sẽ mang kí hiệu ‘- ‘. 2 lOMoARcPSD|46342985
I.4 Đánh giá mức độ hoàn thành công việc và đánh giá nhóm TÊN CÔNG VIỆC
MỨC ĐỘ HOÀN THÀNH
Miêu tả các giải pháp để tìm ra logic và thiết lập cho 100% việc tạo CNF
Tạo được các CNF tương ứng với các Input 100%
Dùng được thư viện PySat để giải các CNF tạo ra 100%
Viết được thuật toán A* không dùng thư viện PySat 100%
để giải các CNF được tạo ra
Viết được thuật toán Brute Force và Backtracking để 100% so sánh với A*
Tạo được ít nhất 5 test cases với các kích thước khác 100% nhau
Có được sự so sánh và nhận định, viết được báo cáo 100% hoàn chỉnh
(Bảng đánh giá các công việc nhóm đã thực hiện) 3 lOMoARcPSD|46342985 TÊN SINH VIÊN MSSV
CÁC CÔNG VIỆC THỰC HIỆN Trần Huy Bân
21127012 1/ Phổ biến bài toán và tìm kiếm các tài liệu và công cụ
hỗ trợ liên quan đến bài toán
2/ Lên ý tưởng, phát triển công thức tạo CNF và thực
hiện chính việc thiết lập hàm tạo CNF một cách tự động
3/ Lên ý tưởng, cách tính heuristic và thực hiện các
hàm phụ cho thuật toán A*
4/ Tạo 3 test case (9x9, 15x15, 20x20)
5/ Đánh giá, so sánh và nhận xét chất lượng và tốc độ
xử lí của các thuật toán tương ứng với các test case. Võ Nguyễn Hoàng Kim
21127090 1/ Lên ý tưởng và thực hiện chính thuật toán Brute Force
2/ Hỗ trợ thực hiện thuật toán Backtracking
3/ Hỗ trợ xử lý đầu vào của các thuật toán Ngô Phước Tài
21127419 1/ Thực hiện chính thuật toán A* giải các CNF
2/ Hỗ trợ thuật toán Brute Force
3/ Tạo 1 test case (5x5)
4/ Lên ý tưởng thực hiện thuật toán Backtracking
5/ Tham gia xử lý đầu ra của các thuật toán
6/ Thực hiện video demo Trần Thị Thanh Vân
21127478 1/ Hỗ trợ thiết lập giải thuật cho việc tự động tạo CNF và thuật toán A*
2/ Lên ý tưởng cho việc tiền xử lý đầu vào của các thuật toán
3/ Tạo một test case (11x11)
4/ Lên ý tưởng và thực hiện chính thuật toán Backtracking
5/ Tham gia xử lý đầu ra của các thuật toán
(Bảng các công việc các thành viên thực hiện) 4 lOMoARcPSD|46342985
II. Cài đặt CNF và sử dụng thư viện PySat II.1. PySat
Trong thư viện PySat, chúng em dùng CNF và Solver của thư viện này để
phục vụ cho việc lưu trữ các CNF và giải các CNF đó.
Đối với việc lưu trữ CNF, dạng chuẩn CNF của thư viện PySat được lưu
dưới dạng kiểu dữ liệu “List”. Mở rộng hơn, đối với mỗi “clause” được lưu trữ sẽ
đều có định dạng kiểu “List” và “List” này phải chứa các phần tử có định dạng là
kiểu “int” (integer) và giá trị phải đều khác giá trị 0.
Vì vậy, tập hợp các clauses CNF sẽ là một “List” chứa các “List” là các clauses CNF bên trong.
Đối với Solver, đây là công cụ để khi chúng em tạo ra các CNF bằng thuật
toán của nhóm thì sẽ dùng Solver để giải và kiểm tra.
II.2. Cài đặt và tạo ra các câu CNF từ ma trận ban đầu
II.2.1. Ý tưởng thiết lập giá trị trong các câu CNF
1/ Đối với bài toán dò mìn, đây là bài toán có dạng thiết kế có phần tương đồng
với bài toán N-queens khi mà chúng ta có thể xem bàn cờ của cờ vua tương tự như bàn
cờ giải mìn của chúng ta. Ở đây, khi áp dụng điều này thì với mỗi ô trong bàn cờ dò mìn
sẽ được đánh dấu với một số thứ tự. Cụ thể với bàn cờ có kích thước NxN
(gồm N dòng và M cột) thì thứ tự đánh dấu sẽ là từ phải sang phải từ trên xuống
với giá trị từ 1,2,3, …, NxN.
(ảnh ví dụ về thứ tự trong bàn cờ 3x3) 5 lOMoARcPSD|46342985
2/ Yếu tố thứ hai đó là ở một ô trong bàn cờ, dấu của giá trị theo thứ tự ở ô đó
sẽ là yếu tố quyết định ô đó có mìn hay không. Cụ thể, nếu giá trị mang dấu dương
(không dấu) thì ô sẽ có mìn và ngược lại nếu là dấu âm thì ô đó sẽ không có mìn.
3/ Kết hợp hai yếu tố trên, từ một ma trận ban đầu với các ô có thông tin đều là
kiểu chuỗi và mang giá trị và các ô không có thông tin sẽ có kí hiệu “-” thì chúng ta sẽ
tạo ra các câu CNF với việc đánh thứ tự như ở ý thứ (1) và đánh dấu các ô có thông tin
đó với dấu âm như ý thứ (2). Vậy câu hỏi đặt ra sẽ là với các ô không có thông tin (ô
mang giá trị “-”) thì giá trị trong bàn cờ mới sẽ như thế nào. Đối với các ô đó, chúng ta
sẽ bỏ qua vì khi thiết lập cài đặt các CNF thì chúng ta chỉ quan tâm đến các ô có giá trị (có thông tin). Ví dụ:
Ở ô thứ 2 mang giá trị là 1 (có thông tin) thì CNF clause tương ứng cho ô đó sẽ là [2].
Ở ô 2 hoặc 5 có 1 quả mìn thì CNF clause tương ứng cho trường hợp này sẽ là [2, 5].
II.2.2. Ý tưởng tạo ra các clauses CNF từ ma trận ban đầu
Từ ý tưởng về việc thiết lập các giá trị trong một câu CNF thì từ ma trận
ban đầu với các thông tin có được, các câu CNF sẽ được tạo ra theo một vòng lặp
duyệt qua từng ô và tuân thủ theo các quy luật như sau:
1/ Các ô không có thông tin sẽ được bỏ qua và đi đến ô kế tiếp
2/ Với những ô mang giá trị (có thông tin) thì sẽ tạo một CNF clause là một
“List” chứa giá trị âm theo thứ tự của ô đó (như đã nêu ở phần ý tưởng phía trên).
Sau khi thỏa các điều kiện là một ô có thông tin thì chương trình sẽ tiến
hành tìm kiếm các ô lân cận (hàng xóm xung quanh) của vị trí ô vừa xử lý. Các ô
hàng xóm là các ô có độ dài Euclid chênh lệch với ô vừa kiểm tra là 1. Theo cách
này, một ô sẽ có tối đa là 8 hàng xóm. Dựa vào các yếu tố này, các clauses CNF
tiếp theo sẽ tuân theo (không tính (2)) sẽ tuân theo các quy luật kế tiếp:
3/ Nếu giá trị ô đó mang là ‘0’ thì mỗi ô hàng xóm sẽ được tính là một ô có
thông tin và tạo ra các CNF như ở quy luật (2). 6 lOMoARcPSD|46342985 Ví dụ:
Từ số 0 ở vị trí 1 ta có được các clauses bên phải với ý nghĩa là ở ô 2, 4, 5 thì sẽ không có mìn.
Nếu như một ô thỏa điều kiện (2) nhưng không thỏa điều kiện (3) nghĩa là ô
đó có giá trị > 0 thì ta sẽ có 2 quy luật (4) và (5) như sau:
4/ Nếu số lượng hàm xóm = giá trị trong ô thì sẽ tạo ra các clauses là mìn
với mỗi clause ứng với một hàng xóm xung quanh. Ví dụ:
Từ số 0 ở vị trí 1 ta có được các clauses bên phải với ý nghĩa là ở ô 2, 4, 5 sẽ có mìn.
5/ Nếu số lượng hàm xóm > giá trị trong ô thì sẽ tạo tất cả các clauses là mìn
có liên quan tới số lượng hàm xóm và tất cả các clauses không là mìn liên quan
đến số lượng hàng xóm (sẽ giải thích cụ thể ở phần cài đặt thuật toán). 7 lOMoARcPSD|46342985 Ví dụ:
Từ số 0 ở vị trí 1 ta∨ có∨được các clauses bên phải với ý nghĩa lần lượt là ở ô 2, 4, 5 sẽ có
một ô có mìn (2 4 5).
3 clauses kế tiếp nghĩa∨ là với∨giá trị 1 ở∨ ô 1 thì trong 3 hàng xóm xung quanh sẽ
có 2 ô không có mìn [(-2 -4), (-2 -5), (-4 -5)]
(Sơ đồ ý tưởng cho việc tạo CNF) 8 lOMoARcPSD|46342985
II.2.3. Cài đặt thuật toán
II.2.3.1 Các hàm bổ trợ
1/ Hàm combinations (lấy tổ hợp chập k của n)
Từ phần ý tưởng, tổng quát hóa thì đối với việc cài đặt CNF cho mọi
trường hợp, khi dựa trên các ô có giá trị để tạo ra các CNF thì ta luôn lấy một tổ
hợp chập k giá trị tùy thuộc vào giá trị của ô trong n giá trị hàng xóm.
Cụ thể ở đây, đối với trường hợp tổng quát thì khi giá trị của ô đang xét
nhỏ hơn số lượng hàng xóm thì ta sẽ áp dụng 2 công thức sau để tạo CNF:
- Clauses về số ô có mìn:
- Clauses về số ô không có mìn:
Với k là giá trị tại ô đang xét và n là số lượng hàng xóm.
Từ công thức trên, kết hợp với việc tham khảo hàm combinations của thư viện
itertools, chúng em thiết lập 2 hàm combinations (combinations_positive(neighbors,
k) và combinations_negative(neighbors, k)) lần lượt để tạo clauses có mìn và
không có mìn như sau:
1/ Truyền vào một mảng các hàng xóm và số lượng cần chập.
2/ Dùng đệ quy để bắt cập lần lượt các cặp với số lượng k giá trị với số
lượng cặp là tổ hợp chập k của n với n là độ dài mảng các hàng xóm. Mỗi khi tạo
ra được một câu CNF thì sẽ bỏ vào một “List” để lưu trữ và về list đó.
Ở đây, với cách tạo này thì chỉ tạo được các clause CNF cho việc các ô có mìn,
không đủ điều kiện để thực hiện các ô không có mìn nên sẽ tách ra 2 hàm để khi thực
hiện việc tạo các CNF clauses cho các ô không có mìn (mang giá trị âm) thì hàm
“negative” sẽ làm điều đó với sự khác biệt khi thêm các CNF vào List lưu trữ sẽ để
thành dấu âm và đồng thời khác sau về số lượng cần chập như công thức ở phía trên. 9 lOMoARcPSD|46342985
(Ví dụ về các clauses khi sử dụng 2 hàm combinations nêu trên)
2/ Hàm lấy các hàng xóm (neighbors)
Đối với việc lấy các hàng xóm, chúng ta sẽ xét 8 vị trí xung quanh một ô và
kiểm tra rằng với mỗi ô, liệu ô đó có nằm trong bàn cờ ta đang xét hay không.
Hơn nữa, hàm này chỉ trả ra những ô hàng xóm chưa có thông tin.
Hàm nhận vào ma trận bàn cờ ban đầu và tọa độ ô cần tìm hàng xóm. Vì các ô
hàng xóm đều có khoảng cách Euclid với ô đang xét là 1, nên tại ô đang xét (x, y), ta có
tối đa 8 hàng xóm: (x-1, y-1), (x-1, y), (x-1, y+1), (x, y-1), (x, y+1), (x+1, y-1), (x+1, y),
(x+1, y+1). Do đó, khởi tạo mảng [-1, 0, 1] là độ lệch tọa độ của ô đang xét so với các ô hàng xóm.
Thực hiện 2 vòng lặp trên mảng [-1, 0, 1], nếu ô (x+i, y+j) (i, j thuộc [-1, 0,
1]) nằm trong bàn cờ và giá trị của ô đó không phải là số (tức chưa có thông tin),
ta thêm vào danh sách hàng xóm. Sau khi duyệt hết 8 vị trí xung quanh, ta trả về
danh sách các ô hàng xóm chưa có thông tin.
II.2.3.2. Hàm chính - hàm tạo CNF (CreateCNF)
Dựa vào các hàm bổ trợ và ý tưởng thực hiện, từ một trạng thái ban đầu (một
bàn cờ 2D) chương trình duyệt qua từng ô trong bàn cờ ấy và thực hiện các bước sau:
B1: Kiểm tra giá trị ở ô đó phải là số hay không (do trạng thái đầu vào là
một ma trận với ô đều là kiểu “string”.
B2: Tạo CNF cho ô đó nếu là “số” và thêm nó vào danh sách CNF.
B3: Dùng hàm neighbors để lấy các hàng xóm của ô đó và thực hiện tạo CNF. 10 lOMoARcPSD|46342985
B4: Kiểm tra các trường hợp:
- Nếu giá trị là 0 thì tạo các clause bằng hàm negative để tạo CNF cho
từng ô hàng xóm (tổ hợp chập 1 của n) và thêm vào tập CNF_negative.
- Nếu giá trị bằng với số lượng hàng xóm thì tạo các clause bằng hàm
positive để tạo CNF cho từng ô hàng xóm (tổ hợp chập 1 của n) và
thêm vào tập CNF_positive.
- Nếu giá trị nhỏ hơn với số lượng hàng xóm thì tạo các clause bằng
hàm positive lẫn negative để tạo CNF cho từng ô hàng xóm (tổ hợp
chập k của n theo 2 công thức từ phần combinations) và thêm vào
tập CNF_positive lần CNF_negative.
B5: Duyệt qua từng tập positive và negative và thêm các CNF clauses vào
với điều kiện là các clauses ấy không tồn tại trong danh sách CNF. Sau đó loại bỏ
các CNF rỗng nếu có do tính chất của hàm đệ quy.
III. Thuật toán A* (không dùng thư viện)
III.1. Ý tưởng thực hiện
Đối với thuật toán A*, tương tự như N-queens problem, chúng ta sẽ mượn
ý tưởng từ bài toán N quân hậu vào bài toán này.
Trước hết, từ một ma trận ban đầu với các ô có thông tin đều là kiểu chuỗi và
mang giá trị và các ô không có thông tin sẽ có kí hiệu “-” thì chúng ta sẽ tạo ra một List
1 chiều với việc đánh thứ tự như ở ý thứ (1) của phần ý tưởng cài đặt CNF và
đánh dấu các ô có thông tin đó với dấu âm như ý thứ (2) của phần ý tưởng cài đặt
CNF. Vậy câu hỏi đặt ra sẽ là với các ô không có thông tin (ô mang giá trị “-”) thì
giá trị trong bàn cờ mới sẽ như thế nào. Đối với các ô đó, chúng ta sẽ gán giá trị là
0 vì các clause CNF chỉ có thể mang giá trị khác 0 và là số nguyên nên việc gán
giá trị 0 sẽ nhằm phân biệt với các ô khác và xử lý sau.
Để tối ưu thời gian chạy, trước khi đưa một ma trận vào xử lý, dựa vào các
CNF clauses đơn, nghĩa là CNF clauses chỉ có 1 giá trị bên trong thì ta sẽ cập nhật
ma trận ban đầu sao cho giảm thiểu số ô cần xét nhất có thể. 11 lOMoARcPSD|46342985
(Ví dụ về việc xử lý ma trận ban đầu đưa vào A*)
Đối với bài toán N quân hậu thì mỗi successor của một trạng thái sẽ là sự thay đổi
vị trí của một con hậu so với trạng thái đó thì ở đây, chúng ta sẽ có sự thay đổi một ít.
Cụ thể, với những ô được đánh giá trị là 0 thì chúng ta sẽ gán cho nó hai giá trị là âm
hoặc dương với thứ tự vị trí ấy. Ví dụ một ô có thứ tự là 7 chưa có thông tin sẽ có giá trị
0 thì hai successors sẽ là 7 và -7. Vậy thì ở thuật toán A* này, chúng ta sẽ phải thiết lập
tìm kiếm các ô trống (ô chưa có thông tin) và đồng thời chúng ta đi kèm một điều kiện
đó là ô đó phải là ô mà các hàng xóm xung quanh phải tồn tại ít nhất 1 ô có thông tin .
Điều này sẽ giúp chúng ta dò và kiểm tra được bằng các CNF vì nếu gắn giá trị cho một
ô mà xung quanh chỉ toàn là những ô không có thông tin thì việc gắn giá trị này là vô nghĩa.
Yếu tố quan trọng khác đó là Heuristic. Ở bài toán này, chúng em lựa chọn
heuristic là số clauses mà một trạng thái sẽ sai. Đối với một tập CNF cố định từ
ma trận ban đầu, với mỗi một clauses bị sai thì lượng heuristic của trạng thái đó
sẽ cộng thêm 1. Vì vậy, với việc tạo ra các successors có thể có thì nếu một trạng
thái thỏa điều kiện heuristic = 0 thì đó sẽ là đáp án cần tìm. 12 lOMoARcPSD|46342985
(Sơ đồ ý tưởng cho việc thực hiện thuật toán A*)
III.2. Giải thích thuật toán
III.2.1. Hàm bổ trợ
III.2.1.1. Hàm tính heuristic
Trong thuật toán A*, như đã nêu ở phần ý tưởng, heuristic chúng em dùng
là số clauses CNF bị sai khi đưa từng state vào kiểm tra. Để đưa điều này vào
chương trình, chúng em thực hiện như sau:
B1: Duyệt qua từng clause CNF trong danh sách các CNF. Do ở đây các clause
được biểu diễn bằng dạng “List” của các số nguyên (đã nêu ở phần giới thiệu về thư viện
PySat nên chúng em sẽ lấy ra từng phần tử của mỗi clause CNF ra và kiểm tra. 13 lOMoARcPSD|46342985
B2: Sau khi lấy được phần tử của mỗi clause, tiến hành kiểm tra xem phần tử ấy
có đang nằm trong List các giá trị của State đang xét hay không. Theo lý thuyết, các
phần tử trong clause CNF được nối nhau bằng toán tử hoặc (Ú) nên chỉ cần 1 trong các
phần tử của clause đúng thì cả clause sẽ đúng. Nếu như không có phần tử nào trong
clause tồn tại trong state đang xét thì sẽ cộng 1 heuristic cho state đó tương ứng với 1 clause sai.
III.2.1.2. Hàm tạo các successors
Để tạo được các successors, chúng ta sẽ nói lại 1 ý trong phần ý tưởng khi mỗi
successor sẽ là một state mới với việc một ô mang giá trị 0 và có hàng xóm mang
thông tin sẽ được gán giá trị âm/dương. Đưa vào lập trình, chúng ta sẽ kiểm tra từng
ô, nếu ô đó là giá trị 0 thì sẽ kiểm tra đến các hàng xóm xung quanh và nếu như các
hàng xóm xung quanh đều là giá trị 0 hết thì chứng tỏ một điều rằng khi gán một giá
trị âm/dương tương ứng với thứ tự của ô đó thì không thể kiểm tra được CNF của
ô đó nên sẽ bỏ qua và tiến đến ô kế tiếp.
III.2.2 Hàm chính – A*
Trước hết, thuật toán nhận vào ma trận ban đầu và tiến hành xử lý ma trận
đầu vào và biến nó thành List khởi đầu (gọi là startstate) như ý tưởng thuật toán (đã
nêu ví dụ ở trên). Sau đó tiến hành thực hiện thuật toán A* theo các bước như sau:
B1: tạo một tập Frontier lưu trữ các giá trị về ma trận khởi đầu gồm 4 giá
trị lần lượt là f, h, g, cursate. Trong đó f là giá trị khi lấy h + g với h là heuristic
của ma trận đang xét và g là chi phí bước đi đối với state đó (state khởi đầu có g =
0). Song đó, tạo một tập ExploredSet để lưu trữ các state đã xét.
B2: Tiến hành thực hiện các bước trong thuật toán A*. Trước hết là lấy ra state
khởi đầu và tiếp tục xét, tổng quát hóa, chúng ta sẽ lấy ra trạng thái có giá trị f thấp
nhất theo lý thuyết về thuật toán A* bằng thư viện heapq. Lấy ra trạng thái có giá trị f
nhỏ nhất bằng hàm heappop thì ở đây, hàm này sẽ lấy dựa trên giá trị nhỏ nhất theo sắp
xếp thứ tự trong một List. Chính vì vậy, chúng ta cần để giá trị f ở đầu để khi lấy ra,
hàm sẽ lấy đúng được trạng thái tương ứng và đúng theo yêu cầu thuật toán. 14 lOMoARcPSD|46342985
B3: Kiểm tra heuristic của trạng thái được lấy ra xem có bằng 0 hay không.
Nếu bằng 0 thì đây là trạng thái cần tìm, nếu không thì sẽ tiếp tục đến bước kế tiếp.
B4: Đưa trạng thái vừa xét vào tập ExploredSet và tạo ra các successors từ
trạng thái đó bằng hàm tạo các successors đã nêu ở phía trên.
B5: Tiến hành kiểm tra từng trạng thái con được tạo ra, với mỗi trạng thái
con, chúng ta sẽ kiểm tra rằng liệu trạng thái này đã được duyệt qua hay có sắp
được duyệt hay không bằng cách kiểm tra nó có tồn tại trong tập ExploredSet và
Frontier. Điều này giúp thuật toán tránh phải kiểm tra lại các trạng thái đã đi
qua. Nếu như trạng thái con được tạo ra không nằm trong 2 tập được nêu trên thì
sẽ thêm nó vào Frontier với heuristic tương ứng và giá trị g bằng với giá trị g của
trạng thái cha +1. Ở đây ta quy định mỗi bước tạo ra trạng thái con hay cụ thể là
chi phí từ một trạng thái cha đến một trạng thái con đều là 1.
Kết thúc thuật toán A*, nếu như tồn tại một trạng thái thỏa mãn các CNF clause
thì đây sẽ là trạng thái bàn cờ cần tìm và thuật toán sẽ trả về trạng thái này. Ngược lại,
nếu sau một số lượng MaxStep nhất định tương ứng với từng kích thước bàn cờ nhưng
vẫn không có kết quả thì thuật toán sẽ trả về None hay không có trạng thái thỏa mãn.
Sau khi thuật toán kết thúc và nếu tìm được một kết quả thỏa mãn thì kết
quả trả về sẽ được thông qua một bước xử lý Output để có thể ghi vào file kết quả. Xử lý Output:
Đối với A*, sau khi tìm được một trạng thái thỏa mãn (một List với các giá trị
thỏa mãn các CNF clauses) thì chương trình sẽ biến đổi từ một List một chiều với các
phần tử mang giá trị âm dương theo vị trí từ 1 đến NxN thành một ma trận 2 chiều với
các tọa độ (i, j) sao cho quy đổi tương ứng với thứ tự ấy và vẫn mang giá trị như trong
List đưa vào. Ở đây, đối với mỗi thuật toán thực hiện sẽ có đôi nét khác nhau tương đối
ở phần này, chúng em gọi đây là tiền xử lý Output và với ở đây là 3 thuật toán sẽ
có 3 thao tác tiền xử lý output khác nhau.
Sau khi tiền xử lý Output xong, chúng ta tiến hành thực hiện việc ghi kết
quả vào file Output (bước này ở cả 3 thuật toán là như nhau). 15 lOMoARcPSD|46342985
B1: Tạo một ma trận cùng kích thước với ma trận thực hiện ở bước tiền xử lý.
B2: Dò qua từng tọa độ (i, j) của từng ô và tiến hành kiểm tra giá trị ô đó
đang mang. Nếu là giá trị dương thì gắn ‘X’ ý nghĩa là ô có mìn, nếu là giá trị âm
thì kiểm tra các hàng xóm xung quanh có bao nhiêu ô mang mìn và trả về giá trị
tương ứng với số mìn xung quanh. Ngoài ra với các ô mang giá trị là 0 thì sẽ trả
về 0 vì ở đây, chúng ta chỉ xét các trường hợp có thể giải được, khác với các trò
chơi Minesweeper ở ngoài, khi chúng luôn tồn tại các ô rỗng (ô không chứa giá trị
lẫn chứa mìn) thì chúng ta sẽ thay thế chúng bằng giá trị 0.
B3: Ghi từng dòng của ma trận vào file Output như biểu diễn một ma trận.
IV. Thuật toán Backtracking và Brute - Force IV.1. Backtracking
IV.1.1. Ý tưởng thực hiện
Vì biến là clause đơn sẽ chỉ mang 1 giá trị (dương hoặc âm) và các biến
không xuất hiện trong các CNF clause là các biến không có thông tin liên quan
nên không xét giá trị cho những ô đó. Do đó, thực hiện backtracking trên danh
sách các ô chưa gán giá trị (không phải là những ô được nêu trên).
Lần lượt gán giá trị dương (có bom) và âm (không có bom) cho từng ô chưa gán.
Đến khi gán xong tất cả các ô, kiểm tra tính hợp lệ của những giá trị đó với CNF
clause. Nếu đúng, trả về True; ngược lại, trả về False, quay về bước trước đó, xóa
giá trị vừa gán và gán giá trị khác.
IV.1.2. Giải thích thuật toán
Trước hết, khởi tạo danh sách notAssigned chứa các ô chưa gán giá trị. Từ
ô 1 đến ô cuối cùng của bàn cờ, nếu ô đó không phải là clause đơn và có xuất hiện
trong các CNF clause thì thêm vào notAssigned. Khởi tạo danh sách assigned chứa
các ô đã gán giá trị với các phần tử ban đầu là các clause đơn.
Hàm backtracking nhận tham số đầu vào là assigned và idx (chỉ số hiện tại của
ô trong notAssigned). Nếu đã gán hết các ô (idx = độ dài của notAssigned), trả về kết quả
kiểm tra tính đúng đắn của assigned với các CNF clause bằng hàm checkConflict() 16 lOMoARcPSD|46342985
(trong từng clause CNF, nếu 1 trong các biến có giá trị xuất hiện trong assigned
thì trả về True; ngược lại, trả về False)
Vì mỗi ô có 2 khả năng dương (có bom) hoặc âm (không có bom), nên mảng val
được khởi tạo với 2 phần từ 1 và -1. Với mỗi giá trị trong mảng val, nhân nó với ô đang
thực hiện và thêm giá trị đó vào assigned. Gọi đệ quy hàm backtracking() cho idx tiếp
theo. Nếu kết quả đệ quy trả ra True, trả về True cho bước hiện tại và dừng thuật toán;
ngược lại, xóa giá trị vừa thêm khỏi assigned và nhân giá trị khác của val cho ô đó. Nếu
đã dùng hết giá trị trong val mà vẫn không ra giải pháp, dừng đệ quy bằng cách trả về False.
Kết thúc hàm backtracking , nếu trả về True, trả ra danh sách assigned gồm các
ô với giá trị dương/âm; ngược lại, trả ra None. Xử lý ou tput:
Sau khi có danh sách các ô đã được gán giá trị, ta đưa chúng về dạng ma
trận 2 chiều để chuẩn bị xuất ra file output. Với mỗi chỉ số ô tính được từ tọa độ
(i, j) trong ma trận bàn cờ, nếu biến ô đó có trong assigned thì ta gán giá trị dương
hoặc âm (có mìn hoặc không có mìn) tương ứng vào mảng 2 chiều; ngược lại, nếu
ô đó không có trong assigned (tức không có thông tin), ta gán giá trị 0.
Sau bước tiền xử lý, thực hiện đếm số lượng mìn xung quanh và xuất ra
file output như đã trình bày trong phần giải thích hàm A*. IV.2. Brute - Force
IV.2.1. Các hàm được sử dụng trong thuật toán Brute - force gồm:
CreateCNF(InitMatrix, cnf): Hàm có chức năng tạo danh sách các biểu thức logic
dạng CNF từ ma trận đầu vào (InitMatrix) và trả danh sách biểu thức đó vào cnf.
preHandle(cnf): Hàm có chức năng lấy ra các biểu thức trong cnf. Các biểu thức
được lấy ra trong hàm là các ràng buộc có thể đặt bom trong ma trận (các vị trí có
thể được đặt bom). Các biểu thức hợp lệ sẽ được gán vào một biến (myPos). Hàm
trả về giá trị của myPos. 17