Code Đồ Án Trí Tuệ Nhân Tạo, Đồ Án Trí Tuệ Nhân Tạo Chọn Lọc

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 (297.43 KB, 10 trang )

Đang xem: đồ án trí tuệ nhân tạo

HỌC VIỆN KỸ THUẬT QUÂN SỰKHOA CÔNG NGHỆ THÔNG TINĐồ ánNhập môn trí tuệ nhân tạoĐề tài: Không gian trạng thái là trò chơi cờ vua. Xây dựng chương trình giải quyết bài toán theo phương pháp MinimaxThầy giáo hướng dẫn: Ngô Hữu Phúc Học viên: Nguyễn Trần Quyết Lớp: Tin học 5AHà Nội, 3 – 20101I. Lời nói đầuNgày này, việc nguyên cứu Trí tuệ nhân tạo và đưa nó vào các ứng dụng thực tế đang ngày càng nhiều, và ngày càng chứng tỏ được thế mạnh của mình trong các công việc đòi hỏi khả năng suy nghĩ và tính toán giống như con người. Trong đó, vấn đề Tìm kiếm có đối thủ đang được áp dụng rất rộng rãi trong các trò chơi đối kháng, tất nhiên, tuân theo những tiêu chuẩn nhất định. Bản đồ án này được xây dựng, cũng nằm một trong số đó. Áp dụng lí thuyết Trí tuệ nhân tạo, kết hợp với các hàm đánh giá, từ đó xây dựng một chương trình cờ vua mang tính chất minh họa thuật toán hơn là xây dựng một chương trình có tính ứng dụng cao trong thực tế. Sau đây là cơ sở lý thuyết về không gian trạng thái cờ vua theo phương pháp Minimax.II. Cơ sở lí thuyếtVấn đề chơi cờ có thể xem xét như vấn đề tìm kiếm trong không gian trạng thái. Mỗi trạng thái là một tình thế (cách bố trí các quân cờ trên bàn cờ).- Trạng thái ban đầu là sự sắp xếp các quân cờ của hai bên lúc bắt đầu chơi.- Các toán tử là các nước đi hợp lệ.- Các trạng thái kết thúc là các tình thế mà cuộc chơi
dừng, thường được xác định bởi một điều kiện dừng nào đó.- Một hàm kết cuộc ứng mỗi trạng thái kết thúc với một giá trị nào đó.Chiến lược tìm kiếm Minimax là chiến lược tìm kiếm theo độ sâu. Quá trình chơi cờ là quá trình trắng và đen thay phiên nhau đưa ra quyết định, thực hiện một trong số các nước đi hợp lệ. Trên cây trò chơi, quá trình đó sẽ tạo ra đường đi từ gốc đến lá. Giả sử tới một thời điểm nào đó, đường đi đã dẫn tới đỉnh u. Nếu u là đỉnh trắng (đen) thì trắng (đen) cần chọn đi tới một trong các đỉnh đen (trắng) v là con của u. Tại đỉnh đen (trắng) v mà trắng (đen) vừa chọn, đen (trắng) sẽ phải 2chọn đi tới một trong các đỉnh trắng (đen) w là con của v. Quá trình trên sẽ dừng lại khi đạt tới một đỉnh là lá của cây.Giả sử trắng cần tìm nước đi tại đỉnh u. Nước đi tối ưu cho trắng là nước đi dần tới đỉnh con của v là đỉnh tốt nhất(cho trắng) trong số các đỉnh con của u. Ta cần giả thiết rằng, đến lượt đối thủ chọn nước đi từ v, đen cũng sẽ chọn nước đi tốt nhất cho a ta. Như vậy, để chọn nước đi tối ưu cho trắng tại đỉnh u, ta cần phải xác định giá trị các đỉnh của trò chơi gốc u. Giá trị của các đỉnh lá là giá trị của hàm kết cuộc. Đỉnh có giá trị càng lớn càng tốt cho trắng, đỉnh có giá trị càng nhỏ càng tốt cho đen, Để xác định giá trị các đỉnh của cây trò chơi gốc u, ta đi từ mức thấp nhất lên gốc u. Giả sử v là đỉnh trong của cây và giá trị các đỉnh con của nó đã được xác định. Khi đó nếu v là đỉnh trắng thì giá trị của nó được xác định là giá trị lớn nhất trong các giá trị của các đỉnh con. Còn nếu v là đỉnh đen thì giá trị nhỏ nhất trong các giá trị của các đỉnh con.Để cài đặt kĩ thuật Minimax, việc gán giá trị cho các đỉnh được thực hiện bởi các hàm đệ quy Maxval và Minval. Hàm MaxVal xác định giá trị cho các đỉnh trắng, hàm MinVal xác
riêng, với mục đích phản ảnh rõ nhất cục diện bàn cờ cũng như đưa ra được lựa chọn tốt nhất ứng với trạng thái cụ thể.Hàm đánh giá của chương trình được xây dựng dựa trên các yếu tố về các giai đoạn của ván cờ, giá trị các quân cờ và vị trí của chúng (vị trí trung tâm). Cụ thể:7Hàm tính giá trị của từng quân cờ: For i = 0 To 7 For j = 0 To 7 If mangdanhgia.Vitri(i, j) > 0 Then tgiatri(mangdanhgia.Vitri, i, j, mangdanhgia.Vitri(i, j)) End If Next NextVị trí trung tâm: For i = 0 To 7 For j = 0 To 7 If 3 mangdanhgia.Vitri(i, j) > 0 Then eval += 200 ElseIf 2 mangdanhgia.Vitri(i, j) > 0 Then eval += 100 End IfHàm MinVal: tính giá trị nhỏ nhấtPublic Sub Minval(ByVal u As Trangthai, ByVal a As Integer, ByVal b As Integer) Dim i, j As Integer If u.cls = 2 Then
Heristis(u) min = u.Eval Else For i = 0 To 7 For j = 0 To 7 If u.Vitri(i, j) > 0 Then Duyet(u, i, j, u.Vitri(i, j)) End If Next Next For i = 1 To chiso If Mangduyet(i).Father = u.Name Then Maxval(Mangduyet(i), a, b) End If Next min = b End If End SubHàm MaxVal: tính giá trị lớn nhấtPublic Sub Maxval(ByVal u As Trangthai, ByVal a As Integer, ByVal b As Integer) Dim i, j As Integer8 If u.cls = 2 Then Heristis(u) max = u.Eval Else For i = 0 To 7 For j = 0 To 7 If u.Vitri(i, j) > 0 Then
Duyet(u, i, j, u.Vitri(i, j)) End If Next Next For i = 1 To chiso If Mangduyet(i).Father = u.Name Then Minval(Mangduyet(i), a, b) End If Next max = a End If End SubHàm Minimax: Áp dụng giải thuật Minimax vào chương trìnhPublic Sub Minimax(ByVal u As Trangthai, ByVal v As Trangthai) Dim a, b, i, j As Integer a = -100 b = 100 For i = 0 To 7 For j = 0 To 7 If u.Vitri(i, j) > 0 Then Duyet(u, i, j, u.Vitri(i, j)) End If Next Next For i = 1 To chiso If Mangduyet(i).Father = u.Name Then Minval(Mangduyet(i), a, b) If a a = min ketqua = Mangduyet(i)
End If End If Next End SubIV. Những mặt hạn chế của đề tài:Về mặt lý thuyết, chiến lược Minimax cho phép ta tìm được nước đi tối ưu cho trắng. Song nó không thực tế, chúng ta sẽ không đủ 9thời gian để tính được nước đi tối ưu. Bởi vì thuật toán Minimax đòi hỏi chúng ta phải xem xét toàn bộ các đỉnh của cây trò chơi. Trong các trò chơi hay, cây trò chơi là cực lớn. Chẳng hạn đối với cờ vua, chỉ tính đến độ sâu 40, thì cây trò chơi đã có khoảng 10120 đỉnh!Chất lượng của chương trình phụ thuộc vào hàm đánh giá, để xây dựng được hàm đánh giá thông minh thì ta cần phải xét toàn bộ các yếu tố cần thiết. Ở đây hàm đánh giá của chương trình còn chưa chặt chẽ nên cần phải phân tích rõ hơn về hàm đánh giá để máy có thể đánh thông minh hơn.V. Kết luận:Khuôn khổ của đồ án này chỉ giới hạn trong việc xây dựng không gian trạng thái trò chơi Cờ Vua, chưa thể thành một trò chơi để người đấu trí với máy được. Nếu muốn áp dụng thực tế và phát triển đồ án hơn thì sẽ cần nhiều thời gian và quá trình nghiên cứu tìm tòi hơn. Sau khi kết thúc môn học này, em mong thầy có thể giúp đỡ em để em hoàn thành chương trình một cách hoàn thiện hơn.10

*

Báo cáo Bài tập lớn trí tuệ nhân tạo :Không gian trạng thái được mô tả là trò chơi cờ tướng. Hãy xây dựng chương trình giải quyết bài toán theo phương pháp cắt tỉa alpha-beta 5 4 74

*

Báo cáo trí tuệ nhân tạo: Xây dựng chương trình cho phép tìm kiếm đường đi từ 1 điểm tới 1 điểm khác trên bản đồ theo phương pháp tìm kiếm Beam 10 1 5

*

Báo cáo trí tuệ nhân tạo :xây dựng chương trình cho phép tìm kiếm đường đi từ 1 điểm trên bản đồ đến 1 điểm khác trên bản đồ theo phương pháp tìm kiếm Nhành và cận 19 1 12

Xem thêm: Cách Root Xiaomi Redmi Note 4X Không Cần Máy Tính, Hướng Dẫn Cách Root Điện Thoại Xiaomi Redmi 4X

*

Báo cáo đồ án trí tuệ nhân tạo: Xây dựng chương trình mô tả không gian trạng thái của toán chiếc balô loại 2 giải quyết theo giải thuật Gene với phương pháp chọn Rank 10 1 3

*

Báo cáo đồ án trí tuệ nhân tạo: Xây dựng chương trình giải quyết bài toán chơi cờ vua theo phương pháp Minimax 10 2 23

*

Báo cáo đồ án trí tuệ nhân tạo : GIẢI THUẬT TÌM KIẾM THEO CHIỀU SÂU (DEPTH FIRST SEARCH) 11 3 18

*

báo cáo đồ án trí tuệ nhân tạo : Không gian trạng thái được mô tả là trò chơi Lines, kích thước là tùy ý 5 978 12

*

Báo cáo đồ án trí tuệ nhân tạo: Không gian trạng thái được mô tả là bài toán n- queens. Xây dựng chương trình giải quyết bài toán theo giải thuật gene với phương pháp chọn là Elitism 11 930 0

*

Báo cáo đồ án trí tuệ nhân tạo: Mô tả không gian trạng thái bài toán người đưa thư (Travelling Saleman Problem – PST) và dùng giải thuật Local Search để giải quyết 11 1 1

*

Báo cáo đồ án trí tuệ nhân tạo : xây dựng chương trình sử dụng MLP đa lớp để tìm đường phân lớp 2 tập điểm là các điểm trên không gian 2 chiều 22 964 3

*

Xem thêm: Làm Cách Nào Để Xáo Trộn Thứ Tự Trong Excel ? Sắp Xếp Ngẫu Nhiên Các Ô, Hàng Và Cột

(240.5 KB – 10 trang) – Báo cáo đồ án trí tuệ nhân tạo: Xây dựng chương trình giải quyết bài toán chơi cờ vua theo phương pháp Minimax

Xem thêm bài viết thuộc chuyên mục: Đồ án