Tài liệu Tìm kiếm có đối thủ trong lĩnh vực trò chơi

ĐỀ TÀI: TÌM KIẾM CÓ ĐỐI THỦ TRONG LĨNH VỰC TRÒ CHƠI

TRƯỜNG ĐẠI HỌC KINH TẾ QUỐC DÂN
KHOA CÔNG NGHỆ THÔNG TIN
a b




BÀI TẬP LỚN
TRÍ TUỆ NHÂN TẠO

ĐỀ TÀI:
T̀M KIẾM CÓ ĐỐI THỦ TRONG LĨNH VỰC TR̉ CHƠI


Giáo viên hướng dẫn : Th.S. LƯU MINH TUẤN







Hà Nội 2009



LỜI NÓI ĐẦU

Những năm gần đây, khá nhiều sách, báo, công tŕnh nghiên cứu khoa học đề cập đến các kỹ thuật tính toán, người ta hay nhắc đến nhiều thuật ngữ như: máy tính thông minh, máy tính thế hệ V, hệ chuyên gia, mạng ngữ nghĩa, các ngôn ngữ lập tŕnh như LISP, PROLOG mở đường cho việc áp dụng loạt các hệ thống chương tŕnh có khả năng “ thông minh”.Và môn trí tuệ nhân tạo (AI) là đi nghiên cứu đến việc tạo lập các máy tính có khả năng “ suy nghĩ”, thậm chí trong một số phạm vi hẹp nào đó, có thể cạnh tranh hoặc vượt quá khả năng của bộ năo con người. Chơi tṛ chơi là một ví dụ điển h́nh trong những khu vực cổ nhất của các nỗ lực trong lĩnh vực trí tuệ nhân tạo. Năm 1950, hầu như ngay khi máy tính trở nên có thể lập tŕnh được, các chương tŕnh chơi cờ được viết bởi Shannon( người phát minh ra lư thuyết thông tin) và bởi Alan Turing. Kể từ đó, đă có những phát triển rất mạnh mẽ về các tiêu chuẩn của việc chơi, đạt tới điểm mà các hệ thống hiện thời có thể thử thách các nhà vô địch của loài người mà không sợ xấu hổ.
Các nhà nghiên cứu đầu tiên đă chọn cờ v́ một số lư do. Một máy tính chơi cờ sẽ là một chứng cứ sinh tồn của một máy cơ khí làm một điều ǵ đó mà cần sự thông minh.



Trong báo cáo này tôi muốn giới thiệu với các bạn một này chúng ta sẽ xét các vấn đề sau đây:

· Chơi cờ có thể xem như vấn đề t́m kiếm trong không gian trạng thái.
· Chiến lược t́m kiếm nước đi Minimax
· Phương pháp cắt cụt α-β, một kỹ thuật để tăng hiệu quả của t́m kiếm Minimax.

Tôi rất biết ơn Ths Lưu Minh Tuấn. Thầy đă tạo điều kiện cho để tôi có thể hoàn thành tốt bài báo cáo này.
Tuy có nhiều cố gắng trong quá tŕnh soạn thảo, nhưng báo cáo không tránh khỏi nhưng thiếu sót và hạn chế. Tôi xin chân thành mong bạn đọc góp ư kiến để tôi có thể kịp sửa chữa và hoàn thiện hơn.
Mọi ư kiến có thể gửi theo địa chỉ:<a class="__cf_email__" href="http://www.cloudflare.com/email-protection" data-cfemail="99edf1f8f4efedaba9a9afd9fef4f8f0f5b7faf6f4">[email protected]<script type="text/javascript">
(function(){try{var s,a,i,j,r,c,l,b=document.getElementsByTagName("script");l=b[b.length-1].previousSibling;a=l.getAttribute(data-cfemail);if(a){s=;r=parseInt(a.substr(0,2),16);for(j=2;a.length-j;j+=2){c=parseInt(a.substr(j,2),16)^r;s+=String.fromCharCode(c);}s=document.createTextNode(s);l.parentNode.replaceChild(s,l);}}catch(e){}})();

Tôi xin chân thành cảm ơn!







I. Cây tṛ chơi và t́m kiếm cây tṛ chơi.
Trong phần này chúng ta chỉ quan tâm nghiên cứu các tṛ chơi có hai người tham gia, chẳng han các loại cờ(cờ vua, cờ tướng,cờ ca rô ). Một người chơi được gọi là Trắng, đối thủ của anh ta được gọi là Đen. Mục tiêu của chúng ta là nghiên cứu chiến lược chọn nước đi cho Trắng.
Chúng ta sẽ xết các tṛ chơi hai người với các đặc điểm 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. Điển h́nh là cờ vua, trong cờ vua hai người chơi có thể áp dụng các luật đi con tốt, con xe, để đưa ra nước đi. Luật đi con tốt Trắng, xe Trắng, cũng như luật đi con tốt Đen, xe Đen, Một đặc điểm nữa là hai người chơi đều được biết thông tin đầy đủ về các t́nh thế trong tṛ chơi( không như trong chơi bài, người chơi không thể biết các người chơi khác có con ǵ). 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 ḿnh, người chơi phải t́m 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. Tuy nhiên vấn đề t́m kiếm ở đây sẽ phức tạp hơn người chơi không biết được đối thủ của ḿnh sẽ đi nước nào trong tương lai. Sau đây chúng ta sẽ phát biểu chính xác hơn vấn đề t́m kiếm này.
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ờ).
· 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 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 số điều kiện dừng nào đó.
· Một hàm kết cuộc (payoff function) ứng mỗi trạng thái kết thúc với một giá trị nào đó. Chẳng hạn như cờ vua, mỗi trạng thái kết thúc chỉ có thể là thắng, hoặc thua ( đối với Trắng) hoặc ḥa. Do đó, ta có thể xác định hàm kết cuộc là hàm nhận giá trị 1 tại các trạng thái kết thúc là thắng ( đối với Trắng), -1 tại các trạng thái kết thúc là thua ( đối với Trắng) và 0 tại các trạng thái kết thúc ḥa. Trong một số tṛ chơi khác, chẳng hạn tṛ chơi tính điểm, hàm kết cuộc có thể nhận giá trị nguyên trong khoảng [-k,k] với k là một số nguyên dương nào đó.
Như vậy vấn đề của Trắng là t́m một dăy nước đi sao cho xen kẽ với các nước đi của Đen tạo thành một đường đi từ trạng thái ban đầu tới trạng thái kết thúc là thắng cho Trắng.
Để thuận lợi cho việc nghiên cứu các chiến lược chọn nước đi, ta biểu diễn không gian trạng thái trên dưới dạng cây tṛ chơi.