NEW
Font size
Worksheetstuan 5
Total questions: 31
Worksheet time: 16mins
Trong thủ tục Minimax(u,v), biến v có ý nghĩa gì?
v là biến lưu lại giá trị của hàm kết quả tại đỉnh kết thúc u
v là biến lưu lại trạng thái mà Trắng đã chọn đi tới từ u
v là biến lưu lại trạng thái kết thúc
v là biến lưu trạng thái bắt đầu
Alpha và Beta trong Chiến lược Cắt cục Alpha-Beta đại diện cho gì?
Giá trị của nước đi hiện tại
Giá trị tối đa và tối thiểu của người chơi
Giá trị tốt nhất hiện tại mà người chơi tối đa hóa và tối thiểu hóa có thể đảm bảo
Giá trị ngẫu nhiên
Đánh giá nào sau đây là đúng nhất về chiến lược Minimax:
Chiến lược Minimax không cho phép ta tìm ra nước đi tối ưu cho quân Trắng
Chiến lược Minimax cho phép ta tìm được nước đi tối ưu cho Trắng
Chiến lược Minimax tìm ra nhanh nước đi tốt nhất.
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, nhưng nó không thực tế, có thể chúng ta sẽ không có đủ thời gian để tính được nước đi tối ưu.
Giải thuật Minimax có tính chất gì?
Rà soát
Phủ định
Vét cạn.
Bao đóng
Giải thuật nào sử dụng chung với thuật toán tìm kiếm Minimax nhằm hỗ trợ giảm bớt các không gian trạng thái?
Giải thuật cắt tỉa Alpha-Beta
Giải thuật tìm kiếm sâu dần.
Tất cả các giải thuật
Giải thuật tìm kiếm beam.
Điền vào dấu “…” của câu sau: Duyệt hết các trạng thái nên giải thuật Minimax sẽ
Tốn nhiều thời gian và bộ nhớ lưu trữ
Giải thuật luôn tìm ra trạng thái tối ưu nhất
Không cần kiểm tra tất cả các trạng thái
Có thể bỏ qua một số trạng thái không quan trọng
Đặc điểm của các trò chơi có hai người chơi được phát biểu như sau:
Hai người chơi thay phiên nhau đưa ra các nước đi tuân theo các luật đi nào đó, các luật này là như nhau cho cả hai người
Chỉ cần một trong hai người chơi tuân theo các luật được đặt ra cho trò chơi
Chỉ một trong hai người chơi được biết thông tin đầy đủ về các tình thế trong trò chơi.
Hai người chơi đều không được biết thông tin đầy đủ về các tình thế trong trò chơi.
Phát biểu nào sau đây là đúng cho hàm Maxval, Minval trong giải thuật tìm kiếm Minimax.
Hàm MinVal xác định giá trị cho các đỉnh Đen
Hàm MaxVal xác định giá trị cho các đỉnh Đen
Hàm MaxVal xác định giá trị cho các đỉnh Trắng và Đen
Hàm MaxVal xác định giá trị cho các đỉnh Trắng, hàm MinVal xác định giá trị cho các đỉnh Đen
Trong chiến lược cắt cụt alpha-beta. Nếu đỉnh c là Trắng thì khi nào ta sẽ cắt bỏ cây con gốc a trong sơ đồ sau:
Khi eval(u) < eval(v)
Khi eval(u) = eval(v)
Khi eval(u) > 0 và eval(v) > 0.
Khi eval(u) > eval(v).
Xét trò chơi Dodgen (được tạo ra bởi Colin Vout). Có hai quân Trắng và hai quân Đen, ban đầu được xếp vào bàn cờ 3*3 như hình vẽ
Quân Đen có thể đi tới ô trống ở bên phải, ở trên hoặc ở dưới. Quân Trắng có thể đi tới ô trống ở bên trái, bên phải, ở trên.
Cả 3 đáp án đều đúng
Quân Đen nếu ở cột ngoài cùng bên phải có thể đi ra khỏi bàn cờ, quân Trắng nếu ở hàng trên cùng có thể đi ra khỏi bàn cờ,
Ai đưa hai quân của mình ra khỏi bàn cờ trước sẽ thắng, hoặc tạo ra tình thế bất đối phương không di được cũng sẽ thắng.
Nếu cây trò chơi có độ cao m, và tại mỗi đỉnh có b nước đi thì độ phức tạp về thời gian của thuật toán Minimax là:
O(m)
O(bm)
O(mb)
O(mo)
Cho không gian trạng thái như hình sau, có đỉnh A là màu Trắng. Cho biết đỉnh D có giá trị bao nhiêu?
A. 0
B. 2
C. 3
D. 5
Trong cây trò chơi ở hình đầu tiên, giá trị của đỉnh B là bao nhiêu?
0
2
3
5
Xét cây trò chơi trong hình, gốc a là đỉnh Trắng. Giá trị của các đỉnh là số ghi cạnh mỗi đỉnh. Phát biểu nào sau đây là đúng về đỉnh i?
Đỉnh i là Đen, nên giá trị của nó là max(3, -2) = 3
Đỉnh i là Trắng, nên giá trị của nó là max(3, -2) = 3
Đỉnh i là Trắng, nên giá trị của nó là min(3, -2) = -2
Đỉnh i là Đen, nên giá trị của nó là min(3, -2) = -2
Xét cây trò chơi trong hình, gốc a là đỉnh Trắng. Giá trị của các đỉnh là số ghi cạnh mỗi đỉnh. Phát biểu nào sau đây là đúng về đỉnh d?
Đỉnh d là Trắng, nên giá trị của nó là max(2, 3, 4) = 4
Đỉnh d là Trắng, nên giá trị của nó là min(2, 3, 4) = 2
Đỉnh d là đỉnh Đen, nên giá trị của nó là min(2, 3, 4) = 2
Đỉnh d là đỉnh Đen, nên giá trị của nó là max(2, 3, 4) = 4
Sử dụng giải thuật nào để xác định được Alpha và Beta trong giải thuật cắt cục Alpha-Beta?
Giải thuật tìm kiếm beam.
Giải thuật tìm kiếm theo chiều rộng.
Không có đáp án nào thỏa mãn.
Giải thuật tìm kiếm A*.
Vấn đề chơi cờ có thể xem 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ế (sự bố trí các quân của hai bên trên bàn cờ). Đâu là phát biểu đúng về trạng thái ban đầu của trò chơi 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 cuộc chơi.
Các đáp án này đều sai
Trạng Thái ban đầu là trạng thái mà quân Trắng đi trước
Trạng Thái ban đầu là trạng thái mà quân Đen đi trước
Phát biểu nào sau đây là đúng về bài toán chơi cờ:
Vấn đề chơi cờ có thể xem như vấn đề tìm kiếm nước đi, tại mỗi lần đến lượt mình, người chơi phải tìm ra trong số rất nhiều nước đi hợp lệ (tuân theo đúng luật đi), một nước đi tốt nhất sao cho qua một dãy nước đi đã thực hiện, anh ta giành phần thắng.
Vấn đề chơi cờ có thể xem 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ế (sự bố trí các quân của hai bên trên bàn cờ).
Cả 3 đáp án trên đều đúng
Vấn đề tìm kiếm nước đi trong chơi cờ sẽ phức tạp hơn vấn đề tìm kiếm khác, bởi vì ở đây có đối thủ, người chơi không biết được đối thủ của mình sẽ đi nước nào trong tương lai.
Xét cây trò chơi gốc u (đỉnh Trắng). Số ghi cạnh các lá là giá trị của hàm đánh giá. Áp dụng chiến lược Minimax và kỹ thuật cắt cục, Giá trị hàm đánh giá tại đỉnh u là bao nhiêu?
8
5
-3
10
Giải thuật Minimax là gì?
Tất cả các đáp án đều sai.
Là một giải thuật không đệ quy.
Là một giải thuật đệ quy.
Là một giải thuật đệ quy và không đệ quy.
Chiến lược tìm kiếm nào dưới đây thường được sử dụng trong các trò chơi có đối thủ như cờ vua, cờ tướng?
Minimax
Tìm kiếm nhị phân
Tìm kiếm theo chiều rộng
Tìm kiếm theo chiều sâu
Chiến lược Cắt cắt alpha - beta khắc phục nhược điểm gì của chiến lược Minimax:
Chiến lược Minimax phải đánh giá tất cả các đỉnh của cây gốc u tới độ sâu h
Tất cả các đáp án đều đúng
Chiến lược Minimax có không gian tìm kiếm lớn
Chiến lược Minimax có thời gian xử lý lớn
Xét cây trò chơi có gốc u (đỉnh Trắng). Số ghi cạnh các lá là giá trị của hàm đánh giá. Áp dụng chiến lược Minimax và kỹ thuật cắt cục, Giá trị hàm đánh giá tại đỉnh a là bao nhiêu?
8
10
-5
12
Vấn đề chơi cờ có thể xem 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ế (sự bố trí các quân của hai bên trên bàn cờ). Đâu là phát biểu đúng về trạng thái ban đầu của trò chơi cờ:
A. Đỉnh f là đính Trắng, nên giá trị của nó là max(5, 2, -3) = 5
B. Đỉnh f là đỉnh Đen, nên giá trị của nó là max(5, 2, -3) = 5
C. Đỉnh f là đỉnh Đen, nên giá trị của nó là min(5, 2, -3) = -3
D. Đỉnh f là đỉnh Trằng, nên giá trị của nó là min (5, 2, -3) = -3
Tại sao thuật toán cắt cục Alpha-Beta lại hữu ích trong việc tối ưu hóa tìm kiếm Minimax?
Vì nó sử dụng thuật toán tìm kiếm đơn giản
Vì nó giảm số lượng nhánh cần duyệt qua
Vì nó giảm thời gian xử lý một đỉnh
Vì nó tăng cường giá trị của các nhánh
Minimax là một dạng của chiến lược tìm kiếm nào?
Tìm kiếm có đối thủ
Tìm kiếm theo chiều rộng
Tìm kiếm nhị phân
Tìm kiếm tối ưu
Trong chiến lược Minimax, người chơi cần tối thiểu hóa điều gì?
Độ sâu của cây tìm kiếm
Giá trị lợi thế của đối thủ
Thời gian tìm kiếm
Số lượng nước đi
Xét cây trò chơi gốc u (đỉnh Trắng). Số ghi cạnh các lá là giá trị của hàm đánh giá. Áp dụng chiến lược Minimax và kỹ thuật cắt cụt, Giá trị hàm đánh giá tại đỉnh k là bao nhiêu?
A. 5
B. 8
C. 10
D. -3
Cho không gian trạng thái như hình sau, có đỉnh A là màu Trắng. Cho biết đỉnh F có giá trị bao nhiêu?
0
3
5
2
Thuật toán cắt tỉa Alpha-Beta chủ yếu được sử dụng để làm gì?
Tìm kiếm theo chiều sâu.
Tối đa hóa giá trị của cây tìm kiếm.
Cắt bỏ những nhánh không cần thiết trong cây tìm kiếm.
Kích thước cây tìm kiếm.
Xét cây trò chơi gốc u (đỉnh Trắng) giới hạn bởi độ cao h = 3. Số ghi cạnh các lá là giá trị của hàm đánh giá. Áp dụng chiến lược Minimax và kỹ thuật cắt cụt, Giá trị hàm đánh giá tại đỉnh v là bao nhiêu?
A. -3
B. 10
C. 12
D. 5
