Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Tìm kiếm đối kháng-trò chơi (Tô Hoài Việt)

Bài giảng Tìm kiếm đối kháng-trò chơi (Tô Hoài Việt) giới thiệu đến các bạn những nội dung: Trò chơi, quyết định tối ưu trong trò chơi, thuật toán MINIMAX, tỉa nhánh, hàm lượng giá, tìm kiếm cắt nhánh. Mời các bạn tham khảo. | Tìm kiếm đối kháng – Trò chơi Tô Hoài Việt Khoa Công nghệ Thông tin Đại học Khoa học Tự nhiên TPHCM thviet@fit.hcmuns.edu.vn Trang Tổng quan Trò chơi Quyết định tối ưu trong Trò chơi Thuật toán MINIMAX Tỉa nhánh - Hàm lượng giá, Tìm kiếm cắt nhánh Trang Trò chơi Là một trong những đặc tính được xem là “thông minh” của con người Các trò chơi ra đời gần như cùng lúc với AI Đã dành được những thành tựu đáng kể Ở đây ta xem xét các dạng trò chơi trí tuệ (board game) Trang Trò chơi Checkers: Hai người chơi Người chơi lần lượt di chuyển quân của mình theo đường chéo, 1 lần 1 ô Nếu có quân đối phương trước mặt, có thể nhảy qua (nếu có ô trống) và ăn Ván cờ kết thúc khi một trong hai người không còn nước đi Trang Trò chơi Checker Năm 1952, Arthur Samuel (IBM) viết các chương trình chơi cờ đầu tiên Năm 1994, Chinook đánh bại Tinsley, vô địch thế giới, thua 3 ván trong 42 năm! Bí quyết: Tìm kiếm tất cả nước đi khi có 8 hay ít hơn quân Tất cả được nhận diện thông tin thắng, thua, hòa hoàn hảo Lưu trữ 444 tỷ vị trí với hàng tetrabyte bộ nhớ Trang Trò chơi Cờ vua 1997, DeepBlue đánh bại Gary Kasparov trong một trận đấu 6 ván Bí quyết: Tìm kiếm vét cạn với độ sâu cao nhất có thể Tính được 200.000.000 nước đi mỗi giây so với 2 của Kasparov (99.99% nước đi được xem là ngu ngốc) Hàm lượng giá cực kỳ phức tạp Trang Trò chơi Một số khác: Othello: năm 1997, chương trình Logistello đánh bại vô địch thế giới Cờ vây (GO): vẫn chưa có chương trình hiệu quả (do độ phân nhánh quá lớn, b> 300) Trang Quyết định tối ưu trong Trò chơi Lời giải tối ưu: một đường đi bảo đảm chiến thắng cho người chơi Hai người chơi: MAX vs. MIN Các thành phần: Trạng thái ban đầu (initial state) Trạng thái kết thúc (terminal state) Hàm succs(s): các nước đi hợp lệ Hàm lợi ích (utility function): đánh giá trạng thái kết thúc Trang Ví dụ cây tìm kiếm trò chơi - TicTacToe X X X X X X X O X O X O X O X O X O X O O X X X O X O X X X O O MAX(x) MAX(x) MIN(o) KẾT THÚC Lợi ích . | Tìm kiếm đối kháng – Trò chơi Tô Hoài Việt Khoa Công nghệ Thông tin Đại học Khoa học Tự nhiên TPHCM thviet@fit.hcmuns.edu.vn Trang Tổng quan Trò chơi Quyết định tối ưu trong Trò chơi Thuật toán MINIMAX Tỉa nhánh - Hàm lượng giá, Tìm kiếm cắt nhánh Trang Trò chơi Là một trong những đặc tính được xem là “thông minh” của con người Các trò chơi ra đời gần như cùng lúc với AI Đã dành được những thành tựu đáng kể Ở đây ta xem xét các dạng trò chơi trí tuệ (board game) Trang Trò chơi Checkers: Hai người chơi Người chơi lần lượt di chuyển quân của mình theo đường chéo, 1 lần 1 ô Nếu có quân đối phương trước mặt, có thể nhảy qua (nếu có ô trống) và ăn Ván cờ kết thúc khi một trong hai người không còn nước đi Trang Trò chơi Checker Năm 1952, Arthur Samuel (IBM) viết các chương trình chơi cờ đầu tiên Năm 1994, Chinook đánh bại Tinsley, vô địch thế giới, thua 3 ván trong 42 năm! Bí quyết: Tìm kiếm tất cả nước đi khi có 8 hay ít hơn quân Tất cả được nhận diện thông tin thắng, .