Hướng dẫn chơi cờ caro luôn thắng Informational, Commercial
|
Báo cáo sơ bộ bài tập lớnMôn Trí Tuệ Nhân TạoĐề tài : Làm game chơi cờ caro Nhóm thực hiện: - Phạm Hoàng Hà- Mai Đức Khiêm- Nguyễn Thanh Loan- Hoàng Quyết Tiến Nội dung báo cáo Nội dung báo cáo 1.Cờ caro ?2. Tìm kiếm nước đi của players3.Tìm kiếm nước đi của Computer 4. Lập trìnhComputer Player vs Human Player Một số công việcđã thực hiện được -Xây dựng được giao diện bàn cờ + sự kiện đánh cờ giữa 2 người.-Xây dựng được một số hàm lượng giá các trạng tháicủa bàn cờ.-Xây dựng bàn cờ theo các cell và có thể đánh đượctrên bàn cờ đó-Viết được code cơ bản của Anpha-beta PH Ầ N I 1. Gi ớ i thi ệ u - Trò chơi đối kháng (two - agent,conflicting game ) : G ồm 2 người chơi, đối thủ này sẽ tìm cách dành chiến thắng trước đối thủ kia trong một số h ữ u h ạn nước đi, mỗi nước đi đuợc tạo ra dựa từ 1 trạng thái b ất kỳ c ủa trận đấ
ếu sau 1 số giới hạn nước đi, nếu chưa ai dành chiến thắng thì xem như hoà. Ngoài ra , thông tin về trận đấu là hoàn toàn biết đuợc (perfect information) đối với cả 2 đối thủ . - C ờ Carô (hay còn gọi là Gomoku ) cũng là 1 loại trò chơi đối kháng, trong đó mỗi đối thủ trong mỗi lượt đi của mình sẽ ch ọn 1 ô trống còn lại trên bàn cờ (kẻ sẵn các ô lưới ) sao cho tạo thành n con liên tiếp để chiến thắng ... Nếu n = 3 thì nó có 1 tên khác là Tic Tac Toe , nế u b ổ sung thêm luật cho nó thì có thể đổi tên là Penta,Pentix (có ăn quân) ... Ngoài ra, có luật thi đấu mà người ta đã chứng minh đuợc người đi truớc bao giờ cung có thuật toán để thắng (thông tin này đáng tin cậy không thì em hông chắ c ... ch ỉ biết là em có đọc qua tài liệu này ...hì hì hì... ), do đó để h ạn chế thuận lợi của người đi trước, người ta đã đặt ra "luật rừng" sau ( luật này sẽ sử dụng cho quá trình phát triển chương trình ) : + Bàn cờ có kích thước tuỳ ý NxN, chọn n = 16; + Quân cờ đầu tiên phải đánh chính giữa lưới bàn cờ . + N ếu tồn tại đúng 5 con liên tiếp trên 1 hàng là thắng (chéo,ngang,dọ c).[*] + N ế u h ết chỗ đi thì 2 bên hoà. + Và 1 số luật khác, nhưng để đon giản, em dẹp sạ ch ... [*] : Lu ật này đáng lẽ là gắt hơn như sau : Đúng 5 con và không bị ch ặn hai đầu ... nhưng em để dành cho các bác cải tiến ... 2. Thu ậ t ng ữ Anh Vi ệ t - Để tiện cho các bác đọc sau này, em xin giới thiệu 1 số thuật ngữ cơ bản sau, dĩ nhiên mớ này là em tự dịch hoặc xem tài liệu nên không tránh đuợc sai sót hoặc chưa chính xác ... mong các bác thông cảm và góp ý ... (1) Giới thiệu về không gian tìm kiếm nước đi : - Như các bác đã biết, trong trò chơi Caro, cứ sau mỗi nướ c c ờ, mỗi đối thủ sẽ ch ọn ra từ những ô trống (empty - not occupied) để đi, do đó, sau 1 mỗi nước đi thì số ô trống còn lại sẽ giảm. Như vậy, việc tìm nước đi tiếp theo cho trạng thái có sẵn chỉ là việc tìm kiếm những ô trống còn lại, đồng thời, không gian tìm kiếm sẽ thu hẹp theo số nước đi đã tạo ... Em nói đến điều này là để sau này cải tiến thêm việc gia tăng độ sâu tính toán cho chương trình ở những nướ c c ờ tàn ... Như vậy, để ch ọn 1 nước đi kế tiếp từ 1 trạng thái bàn cờ c ó sẵn, ta phải tìm kiếm nước đi ... - Không gian chọn nước đi từ mỗi trạng thái ban đầu là hữ u h ạn, nhưng không gian tìm kiếm (searching space) 1 nước đi dẫn đến chiến thắng là ... hữ u h ạn luôn (?..hì..?..hì..?..hì... ) ... nhưng rõ ràng số lượng phần tử c ủa hai không gian này đuợc so sánh giống như hạt cát và sa mạc ( hoặc như tập số tự nhiên là vô hạn đếm đuợc, tập số h ữu tỉ cũng vô hạn đếm đuợc nhưng mà số lượng phần tử c ủa Q so với của N là 1 trời 1 vực ...) ... Do đó ta không thể vét sạch không gian tìm kiếm nước đi này ( nếu làm đuợc điều này thì làm gì còn những giải cờ nữa ... vì chỉ c ần học thuộc thế c ờ là xong ...) mà ta phải giới hạn không gian tìm kiếm ... - M ột không gian tìm kiếm có thể hiện thực theo dạng 1 cái cây đa phân bình thường như trong Data Struct định nghia, lúc này nó đuợc gọi là cây tìm kiếm, cây trò chơi ...( Searching Tree,Game Tree), mỗi nút (Node) cùng mứ c c ủa cây này thể hiện một lự a ch ọn các nước đi có sẵn, mức (Ply) này sẽ thể hiện cho việc đánh giá khoảng cách từ nút gốc đến những nút con này ... Nếu số nút ở mỗi mức càng nhiều, tức là có nhiều khả năng chọn lựa 1 nước đi từ 1 trạng thái trước, do đó độ phân nhánh ( Branching factor) của cây này càng lớn ... - D ựa vào cái cây trò chơi đã định nghĩa ở trên, việc tìm kiếm nước đi là chọn 1 nút trên cây ( ở mứ c 1) sao cho nước đó là tốt ( tốt ở đây đuợc hiểu là do mình đánh giá thui, vì 1 nước đi này là tốt hơn nước đi kia thì phụ thuộc trình độ, khả năng của người chơi cờ ...), theo thông thường khi chơi, một nước đi tốt hay không là phụ thuộc vào khả năng dành chiến thắng là cao hay thấp sau khi nước đi này đuợc "made" (tức là "đi"), do đó, muốn chọn 1 nước đi tốt thì nế u ch ỉ dựa vào thế c ờ hiện tại là chưa đủ, mà phải biết thông tin của những thế c ờ sau khi chọn nước này để đi ... Ví dụ như khi chơi trò Carô, các bác lại chọn một nước đi vào 1 ô nào đó để ch ận đuờng 3 hở hai đầ u c ủa đối thủ (Opponent, Enemy) vì các bác biết là nếu không đi nuớc này thì sẽ thua ở 2 nửa nước đi tiếp theo, tức là trạng thái thua còn chưa biết đuợ c nếu ngay sau khi chọn đi 1 ô khác để đi xuất phát trạng thái này. Khái niệm độ sâu cung nảy sinh từ đây, đon giản thì độ sâu (Depth) là khả năng "nhìn thấy trước" (looking ahead) 1 nước đi tốt sau một loạt nước đi xuất phát từ hiện tại , ví dụ như nếu từ trạng thái này, các bác nhận biết đuợc là sau 6 con nữ a là mình sẽ thắng (tức là mỗi bên đi 3 con), khi đó độ sâu tính toán của các bác là >= 6 [not 3], ví dụ này cung chưa chính xác lắm, nhưng 1 ví dụ khác thế này nhá : ở trạng thái hiện tại, các bác chọn đi 1 nuớ c đi "tốt" theo sự tính toán của mình, các bác dự đoán là sau 4 con nữa là mình vẫn chưa thua, nhưng thực tế sau đó 3 nuớc nữa (mỗi bên đi 3 con) thì các bác bị thua (..hi hi hi... ), khi đó, rõ ràng "thua" là trạng thái mà các bác không hề nhận thấy khi chọn nước đi tốt ở trên, tức là độ sâu tính toán của các bác trong trường hợp này chính xác là 3, đó cung gọi là độ sâu lớn nhất (Max Depth) mà các bác có thể đạt đuợc khi tìm kiếm ...Như vậy, Max depth thể hiện khả năng & trình độ c ủa người chơi c ờ, các bác chơi càng hay thì giá trị này càng lớn ( rõ ràng 1 thằng độ sâu max 6 chơi với 1 thằng độ sâu max 8 thì thằng (6) không bao giờ ăn đuợc thằng (8), hiển nhiên ...)... Khi Max Depth = 0 \==> No thinking ahead - L ại nói viết chương trình cho máy tính chơi cờ ... tức là máy tính phải tự tìm nước đi khi mình đưa vào 1 trạng thái bàn cờ b ất kì, do không gian tìm kiếm là quá lớn (coi như là vô hạn) nên mình chỉ giới hạn cho máy tính chi tìm kiếm đến 1 độ sâu nào đó mà thôi (cách hiện thực này giống như mình chơi cờ thui ...), đó là độ sâu tìm kiếm lớn nhất ... thể hiện khả năng của chương trình, chúng ta sẽ c ố gắng nâng cao giá trị này bằng cách cài đặt thêm các tri thứ c c ờ cho nó (Heuristic, Knowledge ...), tức là sau khi chạy chương trình, máy tính p h ải biết chọn ra 1 nước tốt trong một mớ các ô trống còn lại sao cho sẽ chưa bị thua sau 1 loạt nước đi (= MAXDEPTH [not MAXDEPTH*2]) kế tiếp ... - M ột số thuật ngữ [*] : Game Tree : cây trò chơi. Searching Tree : Cây tìm kiếm Ply : mứ c c ủa cây (Level) Depth : độ sâu (max Ply) Iterative Deepening : Tìm kiếm sâu dần Quiescence depth : độ sâu tĩnh Branching factor : độ phân nhánh Parent Node : nút cha Children Node : nút con Leave Node : nút lá Max Node : nút nước đi của đối thủ hiện tại Min Node : nút nước đi của đối thủ vừa mới đi Evaluation : Sự lượng giá Evaluate : Lượng giá Static/Dynamic Evaluate : Lượng giá tinh/động Lazy Evaluation : Lượng giá lười Extension Knowledge - Extension Heuristic : Tri thứ c b ổ sung Upperbound : Chận trên L owerbound : Chận dưới Make Move : Uýnh 1 nước đi đã chọn NULL- Move : nước đi trống Move Ordering : Sắp xếp nội nước đi Move Generation : Sinh nuớc đi Capture : "Đớp" Generation Move : Nước đi Dangerous Gen - Move : Nuớc đi nguy hiểm (đe doạ ) Winning thread : Nhánh dẫn đến thắng Straight four : 4 con đã bị ch ận 1 đầu (XOOOO*, * là ô trống) Opened three : Đuờng 3 mở 2 đầu (**OOO**,X*OOO**...) Broken three : đuờng 3 gãy không bị ch ận 2 đầu (*OO*O*) Winning line : Đuờng thắng (ví dụ : Straight four,Open three,Broken three..) Tranpositon Table : Bảng truyền Hash Table : Bảng băm Offense/Defense - Offensive/Defensive - Aggressive Attack : Các chế độ chiến đấ u c ủa chương trình Prune, Pruning, Cut Off,...: Cắt nhánh Horizontal Effect : Hiệ u ứng đuờng chân trời,đuờng ngang Back Tracking : Quay lui tìm tới Opening Books : Mở Book - Database Search by MinMax/AlphaBeta/NegaScout/MTD(f)/PVS Algorithms : Các thuật toán tìm kiếm [*] : Nh ững thuật ngữ trên có 1 mớ đã giới thiệu, mớ còn lại sẽ đuợc giới thiệ u ở những bài kế tiếp ... 3. Vi ế t m ột chương trình Game Gomoku như thế nào
ụ c tiêu : - Viết 1 chương trình mà máy có khả năng "biết chơi" cờ carô (tức là biết uýnh đúng luật ...hì hì..) ... - Chương trình ít nhất phải đánh thắng những người hông biết đánh cờ carô (biết đuợc đuờng thắng...), ngoài ra phải cho những cao thủ người phải "e ngại" vì chương trình có tính người (có suy nghi đàng hoàng) - Các khả năng còn lại của chương trình là của các bác ... (dzí dụ : có thể cài đặt để máy "uýnh" dzới máy, "uýnh" nhau trên mạng, "uýnh" multiplayer : 1 người chơi với 2 máy bồ nhau ... hi hi hi ...) |
