- Trang Chủ
- Công nghệ thông tin
- Tóm tắt Đồ án tốt nghiệp Lập trình máy tính: Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
Xem mẫu
- TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN
HỮU NGHỊ VIỆT - HÀN
KHOA CÔNG NGHỆ THÔNG TIN
ỨNG DỤNG TRÍ TUỆ NHÂN TẠO ĐỂ LẬP TRÌNH
TRÒ CHƠI CARO GIỮA NGƢỜI VÀ MÁY
TÓM TẮT ĐỒ ÁN TỐT NGHIỆP
NGÀNH: LẬP TRÌNH MÁY TÍNH
HSSV thực hiện : Lê Hữu Hùng
MÃ HSSV : CCLT17A003
Cán bộ hƣớng dẫn : TS. Lê Tân
Khóa đào tạo : 2017 - 2020
Đà Nẵng, 01/2020
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
MỞ ĐẦU
1. Lý do chọn đề tài
Từ lâu con người đã có suy nghĩ muốn tạo ra một cỗ máy có
thể tự suy nghĩ và hành động. Chính vì thế, trí tuệ nhân tạo (AI) trở
thành một một lĩnh vực mới trong thời đại công nghệ thông tin ngày
nay. Các ngành nghề trong xã hội đang có xu hướng xử dụng AI để
khiến máy móc thông minh hơn. Trong giải trí, trong y tế, hay cả
trong giáo dục, rất nhiều robot thông minh được tạo ra có thể thay
thế con người dạy học, giúp đỡ người già, thực hiện các công đoạn
trong công nghiệp,...
Vì những ứng dụng hữu ích của nó, em xin trình bày một ứng
dụng của AI trong game caro giữa người và máy dựa trên các thuật
toán cơ bản hay dùng trong trí tuệ nhân tạo. Mong muốn thông qua
game này, em sẽ có những cái nhìn cụ thể về đề tài AI, từ đó mở
rộng để nghiên cứu và phát triển thêm.
2. Mục tiêu và nhiệm vụ nghiên cứu
Mục tiêu:
Tìm hiểu định nghĩa, lịch sử phát triển của trí tuệ nhân tạo
Tìm hiểu cấu trúc, các thuật toán và cách hoạt động của AI
Nhiệm vụ: Ứng dụng nghiên cứu để lập trình game caro mà
máy tính có thể tự đưa ra bước đi
3. Đối tƣợng và phạm vi nghiên cứu
Đối tượng nghiên cứu: Lĩnh vực AI
Phạm vi nghiên cứu: Trong game caro giữa người và máy
SVTH: Lê Hữu Hùng – Lớp CCLT17A 1
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
4. Phƣơng pháp nghiên cứu
Nghiên cứu dựa trên:
Tài liệu
Tham khảo từ giáo viên hướng dẫn
Thực hành viết mã trên máy tính bằng ngôn ngữ java
5. Dự kiến kết quả
Đạt được mục tiêu đã nêu ra, lập trình thành công game caro
giữa người và máy. Dự kiến hoàn thành trong khoảng 1 tháng.
6. Ý nghĩa khoa học và thực tiễn
Ý nghĩa khoa học:
Tìm hiểu về các thuật toán được sử dụng trong công nghệ AI.
Có được nền tảng để mở rộng phạm vi nghiên cứu ở những
mặt ứng dụng khác của trí tuệ nhân tạo
Thực tiễn: Lập trình game caro phục vụ cho giải trí và nâng
cao khả năng lập trình.
7. Nội dung đồ án tốt nghiệp
Ngoài phần mở đầu, kết luận và tài liệu tham khảo, nội dung
đồ án gồm có 2 chương:
Chương 1: Giới thiệu về AI
Chương 2: Ứng dụng AI để lập trình game caro giữa người và máy
SVTH: Lê Hữu Hùng – Lớp CCLT17A 2
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
CHƢƠNG I: GIỚI THIỆU VỀ AI
1.1. GIỚI THIỆU VỀ AI
1.1.1. Tìm hiểu khái niệm
1.1.2. Lịch sử phát triển
1.1.3. Các lĩnh vực nghiên cứu của AI
1.1.4. Ứng dụng của AI
1.2. NHỮNG VẤN ĐỀ CHƢA ĐƢỢC GIẢI QUYẾT CỦA TRÍ
TUỆ NHÂN TẠO
1.3. NHỮNG ƢU ĐIỂM VÀ RỦI RO CỦA AI HIỆN TẠI
1.3.1. Ƣu điểm
1.3.2. Rủi ro
SVTH: Lê Hữu Hùng – Lớp CCLT17A 3
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
CHƢƠNG II: ỨNG DỤNG AI ĐỂ LẬP TRÌNH GAME CARO
GIỮA NGƢỜI VÀ MÁY
2.1. CÁC CHƢƠNG TRÌNH CHƠI CỜ VÀ LỊCH SỬ GAME
CARO
2.1.1. Sơ lƣợc về lịch sử các chƣơng trình chơi cờ
2.1.2. Lịch sử của game caro
2.1.3. Sự phát triển của game caro
2.2. PHÂN TÍCH BÀI TOÁN
nh 2.4. Cây tìm kiếm của trò chơi
2.3. PHƢƠNG PHÁP GIẢI QUYẾT
2.3.1. Các thuật toán tìm kiếm
2.3.2. Phân tích và lựa chọn thuật toán cho game
Sau khi đã t m hiểu các thuật toán trên, dễ thấy rằng giải thuật
tìm kiếm minimax kết hợp cắt tia alpha-beta rất phù hợp để tìm kiếm
nước đi tốt cho máy. Vì vậy trong game caro giữa người và máy em
sẽ sử dụng thuật toán này.
Game bao gồm một vùng 20x20 ô, khi bắt đầu game, sẽ có 2
trường hợp người đánh trước hoặc máy đánh trước. Khi máy được
tùy chỉnh để đánh trước, máy sẽ đánh vào ô trung tâm, ngược lại, khi
người chơi đánh trước sẽ khởi chạy thuật toán minimax và cắt tỉa
alpha-beta để tìm kiếm nước đi cho máy.
SVTH: Lê Hữu Hùng – Lớp CCLT17A 4
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
nh 2.15. Sơ đồ hàm alphabeta
SVTH: Lê Hữu Hùng – Lớp CCLT17A 5
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
nh 2.16. Sơ đồ hàm maxvalue
àm maxvalue đầu tiên sẽ gọi hàm Giatribanco() để tính toán
giá trị của các ô. Sau đó sẽ lấy ra ô có giá trị lớn nhất, nghĩa là ô này
là ô lợi thế cho máy. Kiểm tra xem đã chạm tới giới hạn độ sâu chưa,
v như đã nói ở thuật toán minimax phần trước, chúng ta chỉ xét cây
trò chơi trong một độ sâu nhất định. Nếu đã đạt tới độ sâu
MAXDEPTH thì trả về giá trị của ô lợi thế. Ngược lại thì lấy ra
MAXMOVE (ở đây là 4) ô có giá trị lớn nhất. Sau đó cho máy đánh
thử vào các ô tạo thành một trạng thái bàn cờ mới (node mới) rồi áp
dụng hàm minvalue cho node đó. Cứ lặp lại như thế đến khi đạt đến
MAXDEPTH thì trả về giá trị của ô lớn nhất, hoặc tìm thấy trạng
thái chiến thắng cho máy thì trả về giá trị max và gán nước đi tiếp
theo bestmove cho nước đi đang xét (nước đi dẫn đến chiến thắng).
SVTH: Lê Hữu Hùng – Lớp CCLT17A 6
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
nh 2.17. Sơ đồ hàm minvalue
àm min cũng tương tự như hàm max
Với hàm Giatribanco() chúng ta sẽ tính giá trị của các ô trống
trên bàn cờ dựa theo các chiều dựa trên hàm danhgia(). Hàm danhgia
xét một khối gồm 5 ô liên tiếp theo chiều dọc, ngang và 2 đường
chéo. Nếu tìm thấy một khối chỉ có 1 loại quân (hoặc chỉ có X hoặc
chỉ có O) thì ta sẽ tính giá trị của các ô trống còn lại trong khối đó
như sau: Nếu đến lượt người có loại quân như trong khối thì các ô
trống sẽ nhận giá trị theo mảng Diemtancong[] dựa trên số quân đang
có trong khối, càng nhiều quân điểm càng cao. Ngược lại đến lượt
của đối thủ thì ô trống sẽ nhận giá trị theo mảng Diemphongthu[].
SVTH: Lê Hữu Hùng – Lớp CCLT17A 7
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
Ngược lại đối với khối chỉ có toàn quân địch thì giá trị các ô trống sẽ
giảm dần theo 2 mảng trên.
nh 2.18. Hàm GiaTriBanCo()
Hàm danhgia () bên dưới là hàm sẽ tính giá trị cho từng ô theo
các chiều khác nhau
SVTH: Lê Hữu Hùng – Lớp CCLT17A 8
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
nh 2.19. Khởi tạo tọa độ bắt đầu và kết thúc tùy theo phương duyệt
Đầu tiên hàm đánh giá sẽ dựa vào thông số đưa vào là
phuongduyet để gán các giá trị cho tọa độ bắt đầu (gh_cot1;
gh_dong1), và tọa độ kết thúc duyệt (gh_cot2; gh_dong2). Nếu xét
theo chiều ngang, phần bàn cờ được xét sẽ là toàn bộ bàn cờ trừ đi
phần 4 cột bên phải bàn cờ, nếu xét theo chiều dọc phần bàn cờ được
xét là toàn bộ bàn cờ trừ đi phần 4 cột ngoài cùng bên trái, tương tự
với 2 đường chéo sẽ là trừ đi phần 4 cột phải và 4 dòng dưới cùng,
hoặc là trừ đi 4 cột trái và 4 dòng cuối cùng
SVTH: Lê Hữu Hùng – Lớp CCLT17A 9
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
Hình 2.21 Thực hiện tính toán giá trị cho các ô trống trong hàm
danhgia()
Tiếp theo trong hàm đánh giá, chúng ta duyệt một mảng 2
chiều gồm các ô trong phần bảng đã chọn tùy theo phuongduyet.
Trong một lần duyệt của 2 vòng lặp, nó sẽ thực hiện những điều sau
đây:
Từ vị trí ô đang duyệt, thực hiện xét một khối gồm 5 ô liền
kề rồi đếm xem trong 5 ô đó có bao nhiêu quân cờ của máy và bao
nhiêu quân cờ của người. Ở đây hàm tangbiendem() sẽ giúp ta tăng
các biến i và j trong vòng lặp for tùy theo phương duyệt, ví dụ nếu
duyệt theo phương dọc, tangbiendem() sẽ chỉ tăng j, khi duyệt theo
phương ngang th tangbiendem() sẽ chỉ tăng i, khi duyệt theo đường
SVTH: Lê Hữu Hùng – Lớp CCLT17A 10
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
chéo từ trái sang phải thì tangbiendem() sẽ tăng cả i và j thêm 1, khi
duyệt theo đường chéo từ phải qua trái thì sẽ tăng j và giảm i.
nh 2.15. Hàm tangbiendem()
Tiếp theo sẽ kiểm tra trong khối 5 ô liên tiếp đó có thỏa mãn:
Hoặc chỉ chứa toàn quân của máy, hoặc chứa toàn quân của người
nh 2.22. Xét 5 ô chỉ có một loại cờ
SVTH: Lê Hữu Hùng – Lớp CCLT17A 11
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
Nếu thỏa mãn điều kiện ở bước thứ 2, kiểm tra tiếp lượt đánh
là của người hay máy, nếu khối 5 ô chỉ chứa toàn quân của máy mà
lại đến lượt của người chơi th giảm giá trị của ô đó theo mảng
Diemphongthu[], ngược lại nếu tới lượt máy th tăng giá trị ô đó theo
mảng Diemtancong[].
Vậy sau khi kết thúc hàm GiaTriBanCo() ta sẽ được một mảng
2 chiều các đối tượng Oco gồm các thuộc tính như quân cờ với giá trị
1 nếu là quân của máy, -1 nếu là quân của người, 0 nếu là ô trống.
Thuộc tính giá trị chứa các giá trị mà ta vừa tính xong bằng hàm
GiaTriBanCo().
nh 2.24. Đối tượng OCo
Ở trên là cách thức hoạt động của hàm minimax để đưa ra
nước đi tiếp theo cho máy. Phần tiếp theo, ta tìm hiểu cách xây dựng
giao diện và cơ chế chiến thắng của game
2.3.3. Tạo giao diện và các cơ chế game
a) Giao diện game
Giao diện game được chia làm 2 phần, xây dựng dựa trên các
thành phần của thư viện java.swing và thư viện Graphics:
SVTH: Lê Hữu Hùng – Lớp CCLT17A 12
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
Hình 2.25 Giao diện game caro
Vùng chơi game: Gồm 20x20 ô được tạo thành bởi thành
phần Jbutton của thư viện java.swing
nh 2.26.Vùng chơi game
SVTH: Lê Hữu Hùng – Lớp CCLT17A 13
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
Khi khởi chạy game, khi người chơi bấm vào nút New Game
hoặc khi kết thúc ván chơi hàm createBox sẽ được gọi để vẽ lại
20x20 ô trên JPanel Gamearea.
nh 2.27. Sơ đồ tạo giao diện chơi game
Ở đây ta khởi tạo và gán cho Jbutton các sự kiện để khi click
vào nó sẽ setIcon cho Jbutton đó theo biểu tượng tương ứng với quân
cờ người hoặc máy đánh.
Vùng thông báo và tùy chỉnh game: Gồm một hình minh họa
game, một dòng String vẽ bởi thành phần Graphic thông báo luật
chơi, và các nút Jbutton để điều chỉnh game
SVTH: Lê Hữu Hùng – Lớp CCLT17A 14
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
nh 2.28. Menu game
b) Cơ chế game
Khi người hoặc máy có 5 quân liên tiếp sẽ có thông báo chiến
thắng. Mỗi khi có một quân cờ được đánh, máy sẽ duyệt theo 4
hướng ngang, dọc và 2 đường chéo xem quân đó có tạo thành 5 quân
liên tiếp không bằng hàm isEnd(), hàm này sẽ kiểm tra các hàm
doc(), ngang(), cheo1(), cheo2(), nếu một trong các hàm này mang
giá trị True thì thông báo kết thúc ván cờ
SVTH: Lê Hữu Hùng – Lớp CCLT17A 15
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
nh 2.29. Kiểm tra chiến thắng
Kiểm tra theo hàng dọc: máy sẽ duyệt từ vị trí quân vừa đánh
theo 2 hướng lên trên và xuống dưới, nếu gặp một quân có cùng quân
với ô vừa đánh, tăng biến đếm thêm 1, ngược lại thì dừng, không
đếm nữa. Nếu biến đếm lớn hơn hoặc bằng 5 thì thông báo chiến
thắng
nh 2.30. Duyệt theo chiều dọc
Tương tự với chiều ngang, 2 đường chéo
SVTH: Lê Hữu Hùng – Lớp CCLT17A 16
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
nh 2.31. Duyệt theo chiều ngang
nh 2.32. Duyệt đường chéo từ trái qua phải
SVTH: Lê Hữu Hùng – Lớp CCLT17A 17
- Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy
nh 2.33. Duyệt đường chéo từ phải qua trái
2.3.4. Các công cụ, thành phần sử dụng để thực hiện lập trình
game.
SVTH: Lê Hữu Hùng – Lớp CCLT17A 18
nguon tai.lieu . vn