ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ LƢU MINH ĐỨC TÌM HIỂU VỀ CHIẾN LƢỢC TÌM KIẾM TRONG CÁC TRÕ CHƠI ĐỐI KHÁNG VÀ ỨNG DỤNG VÀO TRÕ CHƠI 2048 LUẬN VĂN THẠC SỸ NGÀNH CÔNG NGHỆ THÔNG TIN HÀ NỘI - 2014 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ LƢU MINH ĐỨC TÌM HIỂU VỀ CHIẾN LƢỢC TÌM KIẾM TRONG CÁC TRÕ CHƠI ĐỐI KHÁNG VÀ ỨNG DỤNG VÀO TRÕ CHƠI 2048 Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã Số: 60480104 LUẬN VĂN THẠC SỸ NGÀNH CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. LÊ NGUYÊN KHÔI HÀ NỘI - 2014 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com LờI CAM ĐOAN Tôi xin cam đoan luận văn “Tìm hiểu về chiến lược tìm kiếm trong các trò chơi đối kháng và ứng dụng vào trò chơi 2048" là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả được trình bày trong luận văn là hoàn toàn trung thực. Tôi đã trích dẫn đầy đủ các tài liệu tham khảo, công trình nghiên cứu liên quan.
Ngoại trừ các tài liệu tham khảo này, luận văn hoàn toàn là công việc của riêng tôi. Luận văn được hoàn thành trong thời gian tôi là học viên tại Khoa Công nghệ Thông tin, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội. Hà Nội, ngày 24 tháng 10 năm 2014 Học viên Lƣu Minh Đức 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com LờI CảM ƠN Lời đầu tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới thầy hướng dẫn TS. Lê Nguyên Khôi đã tận tình hướng dẫn tôi trong suốt quá trình thực hiện luận văn tốt nghiệp.
Tôi chân thành cảm ơn các thầy, cô đã tạo cho tôi những điều kiện thuận lợi để tôi học tập và nghiên cứu tại trường Đại học Công Nghệ. Tôi xin gửi lời cảm ơn tới các bạn trong lớp cao học K18 đã ủng hộ, khuyến khích tôi trong suốt quá trình học tập tại trường. Cuối cùng, tôi muốn được gửi lời cảm ơn vô hạn tới gia đình và bạn bè, những người thân yêu luôn bên cạnh và động viên tôi trong suốt quá trình thực hiện luận văn tốt nghiệp. Tôi xin chân thành cảm ơn! Hà Nội, ngày 24 tháng 10 năm 2014 Học viên Lƣu Minh Đức 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com MỤC LỤC LỜI NÓI ĐẦU.
5 CHƢƠNG 1: TỔNG QUAN VỀ LÝ THUYẾT TRÕ CHƠI .1 Giới thiệu về lý thuyết trò chơi .2 John Nash và thuyết cân bằng .2 Bài toán tìm kiếm và không gian tìm kiếm .1 Bài toán tìm kiếm .2 Không gian tìm kiếm .3 Các kỹ thuật tìm kiếm cơ bản .4 Trò chơi đối kháng.24 CHƢƠNG 2: THUẬT TOÁN TÌM KIẾM MINIMAX .1 Thuật toán Minimax .2 Một số khái niệm trong trò chơi đối kháng .3 Ý tưởng thuật toán .4 Thuật toán Minmax với độ sâu định trước .5 Thủ tục Minimax .6 Đánh giá thuật toán Minimax .2 Thuật toán cải tiến Minimax Alpha-beta .1 Ý tưởng thuật toán .2 Giải thuật Minmax Alpha-beta .34 CHƢƠNG 3: ÁP DỤNG VÀO TRÕ CHƠI 2048 .1 Phân tích bài toán .1 Giới thiệu trò chơi 2048.2 Áp dụng Minimax Alpha-beta vào trò chơi 2048 .3 Cách tính trọng số nút lá .2 Cài đặt chương trình .1 Môi trường phát triển và công nghệ sử dụng.2 Giao diện của chương trình .3 Chi tiết cài đặt .4 Thống kê kết quả .5 Quan sát quá trình chơi tự động và một số kinh nghiệm thu được .53 TÀI LIỆU THAM KHẢO. 55 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com DANH MỤC HÌNH VẼ Hình 1.1: Ví dụ về đồ thị và các trạng thái .2: Trạng thái ban đầu và trạng thái kết thúc của bài toán 8 số.3: Cây tìm kiếm minh hoạ giải thuật DFS .4 Đánh giá trạng thái u .5: Ví dụ biểu diễn một cây trò chơi caro 9 ô .6: Cây tìm kiếm và sự bùng nổ tổ hợp[1] .1: Cây tìm kiếm đã tính đƣợc trọng số lá .2: Cây tìm kiếm đã đƣợc tính trọng số tất cả các nút .3: Minh hoạ cây tìm kiếm với giải thuật Minimax .4: Một phần của cây trò chơi với ý tƣởng cắt nhánh alpha .5: Minh hoạ ý tƣởng cắt nhánh theo alpha .1: ví dụ một trạng thái của trò chơi và trạng thái chiến thắng .2: Mô hình bài toán tổng quát .3: Ví dụ về cách di chuyển và tính điểm của một trạng thái .4(a): Trạng thái có độ mịn tối ƣu .4(b): Trạng thái có tính đơn điệu tốt .5: giao diện chính chƣơng trình .5(b): giao diện cấu hình cho việc chơi tự động .5(a): giao diện cài đặt cho trò chơi .6: Sơ đồ khối của quá trình chơi tự động .7: Màn hình hiển thị kết quả trong quá trình chạy thử nghiệm .8(a): Màn hình hiển thị một trạng thái kết quả của việc chọn cách di chuyển và xây dựng nền tảng các con số ở hàng dƣới cùng .8(b): Màn hình hiển thị một trạng thái kết quả của việc chọn cách di chuyển để cố gắng cân bằng các con số .8(c): Màn hình hiển thị một trạng thái kết quả của việc chọn cách chơi giảm số lần di chuyển trống .8(d): Màn hình hiển thị một trạng thái kết quả của việc chọn cách chơi xây dựng những nền tảng nhỏ. 51 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com LỜI NÓI ĐẦU Trong những năm gần đây với sự phát triển không ngừng của các thiết bị di động và theo đó là sự phát triển về nhu cầu giải trí trên các thiết bị di động đang bùng nổ một cách mạnh mẽ. Một trong những lĩnh vực phát triển mãnh liệt nhất ở thế giới số là các trò chơi trên thiết bị di động.
Từ năm 2000 đến năm 2012 thị trường trò chơi trên thiết bị di động đã tăng trưởng 955% từ 20 triệu người chơi đến 211 triệu người. Năm 2014 chúng ta chứng kiến sự ra đời của trò chơi rất thú vị trên nền tảng di động đó là trò chơi 2048. Đây là một trò chơi đòi hỏi trí tuệ cộng với sự may mắn và nó đã thu hút nhiều triệu người trên khắp thế giới tham gia. Tuy nhiên đây là một trò chơi khó và rất ít người có thể dành chiến thắng trong trò chơi này.
Xuất phát từ những điểm trên, luận văn này đưa ra ý tưởng làm sao cho máy có thể thay người tự chơi trò chơi này dể dành chiến thắng. Tôi đã đưa ra ý tưởng về một trò chơi đối kháng để vận dụng vào trò chơi 2048. Luận văn này sẽ tập trung tìm hiểu về trò chơi đối kháng và chiến thuật trong trò chơi đối kháng, qua đó áp dụng vào trò chơi 2048. Kết quả cuối cùng của luận văn là xây dựng lại trò chơi 2048 cho máy tự động chơi.
5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƢƠNG 1: TỔNG QUAN VỀ LÝ THUYẾT TRÕ CHƠI 1.1 Giới thiệu về lý thuyết trò chơi 1.1 Giới thiệu Lý thuyết trò chơi là một nhánh của toán học trong đó nó sử dụng các mô hình để nghiên cứu các tình huống chiến thuật, các đối thủ cố gắng làm tối đa kết quả đạt được cho mình. Trong thời đại công nghệ thông tin phát triển mạnh như hiện nay thì Lý thuyết trò chơi thu hút được rất nhiều sự chú ý của các nhà khoa học máy tính do ứng dụng của nó trong Trí tuệ nhân tạo và điều khiển học[1]… Một số tài liệu ghi lại thì lý thuyết trò chơi xuất hiện lần đầu tiên vào năm 1713 vào thời điểm đó tác giả đưa ra lời giải chiến thuật hỗn hợp Minimax cho một trò đánh bài 2 người Leher. Tuy nhiên thì Lý thuyết trò chơi chỉ thực sự tồn tại là một ngành khi John von Neumann xuất bản một loạt các bài báo năm 1828. John von Neumann cũng là người đầu tiên hình thức hóa Lý thuyết trò chơi trong thời ký trước và trong chiến tranh lạnh, chủ yếu do áp dụng của nó trong chiến lược quân sự, nổi tiếng là khái niệm đảm bảo phá hủy lẫn nhau[7][8][9].
Hiện nay Lý thuyết trò chơi đã được sử dụng rộng rãi trong nhiều ngành khác nhau như : Kinh tế và kinh doanh, sinh học, chính trị học, triết học, khoa học máy tính và logic, viễn thông, một số trò chơi trên truyền hình … Với sự phát triển của ngành công nghệ thông tin như hiện nay thì Lý thuyết trò chơi đóng một vai trò hết sức quan trọng, đặc biệt trong logic và khoa học máy tính. Một số lý thuyết logic có cơ sở trong ngữ nghĩa trò chơi. Thêm vào đó những khoa học gia máy tính đã sử dụng trò chơi để mô phỏng những tính toán tương tác với nhau. Trong Lý thuyết trò chơi nhân loại đã nghiên cứu được rất nhiều thuật toán hay để ứng dụng vào các trò chơi ví dụ như: thiết kế trò chơi Nim; thiết kế kiểu trò chơi có nhân, có tính đối xứng; thuật toán liên quan đến chiến lược tìm 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com kiếm… Luận văn này đề cập đến thuật toán tìm kiếm MinMax và thuật toán cắt tỉa Alpha-Beta trong việc xây dựng chương trình trò chơi 2048.2 John Nash và thuyết cân bằng Cân bằng Nash: là một khái niệm trong Lý thuyết trò chơi, được John Nash đưa ra với mô hình trò chơi với n đối thủ.
Cân bằng Nash xác định một chiến lược tối ưu cho các trò chơi khi chưa có điều kiện tối ưu nào được xác định trước đó. Nội dung cơ bản của khái niệm cân bằng Nash là: Nếu tồn tại một tập hợp các chiến lược cho một trò chơi với đặc tính là không một đối thủ nào có thể hưởng lợi bằng cách thay đổi chiến lược hiện tại của mình khi các đối thủ khác không thay đổi, tập hợp các chiến lược đó và phần thu nhận tương ứng tạo nên cân bằng Nash. Nói cách khác, cân bằng Nash đạt được nếu như thay đổi một cách đơn phương của bất cứ ai trong số các đối thủ cũng sẽ làm cho chính người đó thu lợi ít hơn mức có được với chiến lược hiện tại. Khái niệm này áp dụng cho những trò chơi gồm từ hai đối thủ trở lên và Nash đã chỉ ra rằng tất cả các khái niệm khác nhau về giải pháp trong các trò chơi được đưa ra trước đó đều có cân bằng Nash[9].
Vì mối quan hệ giữa giá trị cực đại và giá trị cực tiểu đã được thiết lập, chúng ta có thể định nghĩa một giá trị cân bằng của trò chơi. Một cặp chiến lược (p’,q’) được gọi là cân bằng nếu p’ tương xứng tốt với q’ và ngược lại q’ tương xứng tốt với p’ , nghĩa là: M( p,q’) M( p’,q’) M( p’,q)[7][9].