Tài liệu Báo cáo bài tập lớn kỹ thuật lập trình game reversi (ver 1.0)

Đại Học Quốc Gia Thành Phố Hồ Chí Minh Trường Đại Học Bách khoa Báo Cáo Bài Tập Lớn Kỹ Thuật Lập Trình Đề tài: GAME REVERSI (Ver 1.0) Giảng viên: thầy Vương Bá Thịnh Sinh viên tham gia: STT Họ tên MSSV 1 Trần Quang Khôi 1411875 2 Nguyễn Đức Huy 1413369 3 Nguyễn Hữu Phúc 1412962 4 Lê Đình Duy 1410561 TP. HỒ CHÍ MINH, 12/2015 1 MỤC LỤC MỤC LỤC.....................................................................................1 I. GIỚI THIỆU........................................................................2 II. Ý TƯỞNG THUẬT TOÁN.................................................2 III. Ý TƯỞNG HOÀN THIỆN GIAI ĐOẠN 3........................3 IV. CÁC HÀM XỬ LÝ CHÍNH................................................5 V. BẢNG TÓM TẮT CHỨC NĂNG......................................6 VI. MỘT SỐ HÌNH ẢNH TRONG GAME.............................7 VII. TÀI LIỆU THAM KHẢO.................................................19 VIII. PHỤ LỤC GAME REVERSI.........................................19 1 I. GIỚI THIỆU Game REVERSI là một game trí tuệ đơn giản 2 người chơi đối kháng với 1 lưới 8x8 có thể chứa quân trắng, quân đen, hoặc trống. Luật chơi: - 2 người chơi, một người chơi quân trắng, một người chơi quân đen. - Đến lượt chơi của mình thì người chơi buộc phải đặt quân cờ vào vị trí hợp lệ, nếu không tồn tại bất kì vị trí hợp lệ nào có thể đặt quân thì nhường quyền cho người chơi còn lại. - Vị trí đặt quân hợp lệ là vị trí sao cho khi người chơi đặt quân vào vị trí đó thì có thể “ăn” được quân của đối phương. (Xin xem phần phụ lục về luật chơi ) Trò chơi kết thúc trong 2 trường hợp sau: +Bàn cờ không còn ô trống +Cả 2 người chơi không có bất kì vị trí nào có thể đặt quân Luật thắng thua: khi trò chơi kết thúc thì người chơi nào có số lượng quân cờ trên bàn cờ nhiều hơn là người chiến thắng. Yêu cầu Giai đoạn 1: Tạo danh sách các vị trí đặt quân hợp lệ của một người chơi Sinh viên được cung cấp 2 file “Assignment.c” chứa prototype các hàm cần hiện thực, “Main.c” dùng để test chương trình. Trong đó hàm generate_list_valid_moves nhận input là trạng thái hiện tại của bàn cờ, và người chơi cần đặt quân là người nào, output là danh sách các vị trí hợp lệ. Quy định: 1-người chơi quân đen, 2-người chơi quân trắng. output theo thứ tự các dòng từ nhỏ tới lớn và ứng với mỗi dòng, các cột cũng từ nhỏ tới lớn Giai đoạn 2: Cập nhật trạng thái bàn cờ sau một bước đi Giai đoạn 3: Hoàn thiện game 2 người chơi II. Ý TƯỞNG THUẬT TOÁN - Giai đoạn 1 : + Tạo 4 quân cờ đầu tiên ở các vị trí (5,5);(4,4);(5,4);(4,5) 1 + Quét dọc và ngang bàn cờ, ở mỗi vị trí có quân cờ (giá trị X) đối với người chơi là 1(biến đầu vào), hoặc giá trị O đối với người chơi 2 (biến đầu vào) thì bắt đầu làm các bước sau :  Xét theo hàng dọc, từ giá trị đang xét cộng thêm 1 đơn vị , nếu giá trị ô bàn cờ kế tiếp là quân ta thì bỏ qua, nếu là quân địch thì xét tiếp cho tới khi hết bàn cờ. Nếu cuối bàn cờ hoặc cuối dãy quân địch không có quân ta thì đưa tọa độ điểm cuối cùng vào ma trận gợi ý. Làm tương tự xét từ giá trị đang xét trừ đi 1 đơn vị.  Xét theo hàng ngang, từ giá trị đang xét cộng thêm 1 đơn vị , nếu giá trị ô bàn cờ kế tiếp là quân ta thì bỏ qua, nếu là quân địch thì xét tiếp cho tới khi hết bàn cờ. Nếu cuối bàn cờ hoặc cuối dãy quân địch không có quân ta thì đưa tọa độ điểm cuối cùng vào ma trận gợi ý. Làm tương tự xét từ giá trị đang xét trừ đi 1 đơn vị.  Xét theo đường chéo, từ giá trị đang xét cộng thêm 1 đơn vị , nếu giá trị ô bàn cờ kế tiếp là quân ta thì bỏ qua, nếu là quân địch thì xét tiếp cho tới khi hết bàn cờ. Nếu cuối bàn cờ hoặc cuối dãy quân địch không có quân ta thì đưa tọa độ điểm cuối cùng vào ma trận gợi ý. Làm tương tự xét từ giá trị đang xét trừ đi 1 đơn vị. - Giai đoạn 2 :  - Giai đoạn 3 : Tạo các vòng lặp để hoàn thiện menu game và các bước ở giai đoạn 1, giai đoạn 2 liên tục cho đến khi kết thúc game. III. Ý TƯỞNG HOÀN THIỆN GIAI ĐOẠN 3 : - Thiết kế giao diện người dùng của game trên nền tảng console với các tùy chỉnh và điều khiển trực quan. - Sau khi khởi động game, menu chính của game xuất hiện với các tính năng : 2 + Giúp đỡ : Chương trình sẽ xuất ra các hiển thị về luật chơi, sau khi xem xong, người dùng có thể bấm phím bất kì để quay lại menu game. + Tùy chọn: Chương trình xuất ra các menu con khác để người dùng tùy chỉnh các chức năng sau :  Chế độ chơi : Chơi với máy hoặc 2 người chơi. (mặc định là 2 người chơi)  Lựa chọn quyền đánh trước. (mặc định là X đánh trước)  Điều chỉnh thời gian của mỗi lượt đi ( mặc định là 30s ) + Game mới : Tạo game mới, bàn cờ 8x8  Các vị trí quân cờ ban đầu được tạo ra trên bàn cờ, các vị trí gợi ý được hiển thị. Người chơi điều khiển con trỏ và đánh vào vị trí mong muốn(dòng, cột). Nếu không đánh đúng vị trí gợi ý, hoặc vị trí không hợp lệ thì màn hình báo lỗi “Bạn không được phép đi ngoài gợi ý” và yêu cầu nhập lại.  Khi bàn cờ đã đầy hoặc một trong 2 bên đạt điều kiện thắng thì xuất thông báo người chiến thắng. Trường hợp không đi trong thời gian quy định sẽ bị xử thua.  Trong quá trình chơi có thể bấm ESC để quay lại menu. +Lưu game : Chương trình lưu bàn cờ dưới dạng một tập tin có phần mở rộng *CR, lưu tại thư mục cài đặt game với phần tên là thời gian hiện tại của hệ thống. +Tải game : Chương trình hiển thị danh sách các ván cờ đã lưu. Sau khi người chơi chọn ván cờ cần tải thì chương trình sẽ tái hiện ván cờ như thời điểm đã lưu. +Giới thiệu : Hiển thị thông tin game và mssv nhóm. +Thoát : Nếu chọn chức năng này khi đang chơi thì chương trình sẽ hiển thị thông báo “bạn có muốn lưu ván cờ trước khi thoát không?” Nếu chọn có thì chương trình sẽ lưu. 3 - Điều khiển các chức năng trên menu bằng các phím mũi tên, phím enter để chọn chức năng tương ứng. - Điều khiển trực quan : + Người chơi 1 dùng các phím mũi tên để di chuyển, enter để đánh. + Người chơi 2 dùng các phím a,w,s,d để di chuyển ( tương tự các game fps ) , phím space để đánh. + Các quân cờ của 2 người chơi có màu sắc khác nhau, chuyển từ các số 1-2 thành X,O, các ô gợi ý chuyển thành dấu “-“ ở giữa ô bàn cờ. - Gián đoạn trong lúc chơi : trong lúc đang chơi, người chơi có thể thực hiện các phím tắt để gọi các chức năng trong menu : + F2 : hiển thị giúp đỡ +F3 : lưu game +F4 : tải game +F5 : hiển thị thông tin game +ESC : quay lại menu chính - ViẾt chương trình đánh với máy. IV. CÁC HÀM XỬ LÝ CHÍNH - Trong file coRVS.cpp: chứa các hàm để vẽ ô bàn cờ và các ô thông tin trong lúc chơi. - Hàm veMenu: thực hiện hiển thị và chọn MENU GAME, khi chạy chương trình thì hàm này sẽ được gọi đầu tiên trong main(); Trong khi chơi hay đang trong các thao tác khác, nếu ta nhấn phím ESC thì hàm này sẽ được gọi -> trở về MENU GAME. - Hàm veGioiThieu: in ra thông tin nhóm, mssv. - Hàm giupDo: in ra thông tin hướng dẫn phím bấm cũng như luật chơi của GAME. - Cài đặt: 4 - Hàm veCaiDat để in ra giao diện khi người chơi chọn phần tùy chọn trong MENU GAME. Trong hàm veCaiDat lại gọi hàm caiDat để thực hiện thay đổi các thông số (các biến). - Hàm luuGame: thực hiện chức năng LƯU GAME đang chơi. - Tải game và lưu game : khi người chơi chọn chức năng tải GAME thì sẽ gọi hàm menuTaiGame để hiện thị ra danh sách các GAME ĐÃ LƯU, khi chọn một GAME ĐÃ LƯU thì gọi hàm taiGame để thực hiện chức năng TẢI GAME. - Hàm catch_keys1 & hàm catch_keys2: bắt sự kiện phím di chuyển con trỏ khi chơi. Trong khi chơi thì đọc vào một phím, nếu không phải là phím di chuyển thì gọi hàm bamPhimKhiChoi để thực hiện các phím chức năng F1, F2,… - Hàm kiemtrasoquan: kiểm tra xem bàn cờ đầy quân chưa. V. BẢNG TÓM TẮT CHỨC NĂNG Stt 1 Chức năng MENU GAME Nội dung - Hiển thị MENU GAME với các chức năng, nhưng người dùng chọn bằng phím điều hướng và phím enter. 2 GIÚP ĐỠ - Hiển thị hướng dẫn cách chơi. Hiển thị hướng dẫn luật chơi. Nhấn phím bất kì trở lại MENU GAME. 3 TÙY CHỌN - Lựa chọn quyền đánh trước với người 1 - Cho biết thông tin hiện tại: chế độ chơi, quyền đánh trước, thời gian mặc định cho mỗi lượt đi. - Tùy chỉnh thời gian mỗi lượt đi (thấp nhất 10 (s) và nhiều nhất 99 (s). 4 GAME MỚI - Hiển thì bàn cờ có kích thước nxn 5 Người chơi đánh quân cờ bằng các phím điều hướng (a/s/d/w) và enter (space). - Dùng màu sắc và kí hiệu riêng cho quân cờ mỗi bên. - Trong quá trình chơi GAME, nhấn các phím chức năng: + Nhấn F1: để hiển thị GIÚP ĐỠ . + Nhấn F2: để CHƠI GAME MỚI. + Nhấn F3: để chơi LƯU GAME + Nhấn F4: để TẢI GAME. + Nhấn F5: Hiển thị THÔNG TIN GAME + Nhấn ESC: để quay lại MENU GAME -Tính thời gian cho mỗi nước đi. 5 LƯU GAME - Tự động LƯU ván cờ đang chơi ở dạng một tập tin với phần tên là thời gian hiện tại của hệ thống và mở rộng là *.CR và LƯU tại thư mục cài đặt GAME. - Xuất thông báo sau khi LƯU GAME thành công. 6 TẢI GAME - Hiển thị danh sách các ván cờ đã LƯU (tên file game). - Người chơi chọn ván cờ cần chơi tiếp bằng cách nhập giá trị tương ứng trong danh sách. 7 8 THÔNG TIN THOÁT - Hiển thị thông tin nhóm Thoát game Nếu đang chơi chương trình sẽ hiện thông báo hỏi có muốn lưu game không. 6 *Đề tài vẫn chưa viết được chương trình chơi game với máy. VI. MỘT SỐ HÌNH ẢNH TRONG GAME 7 8 9 10 11 VII. TÀI LIỆU THAM KHẢO - Website : http://dtvt.org/forum_posts.asp?TID=13162&title=mt-s-hm-m-rng-trn-c-c (Tham khảo các hàm mở rộng trong C/C++: hàm thay đổi kích thước cửa sổ console, hàm Sleep(), hàm tạo màu cho text.) - Wikipedia. - Tài liệu : +Slide bài giảng kỹ thuật lập trình. +Tài liệu thực hành kỹ thuật lập trình. Game mẫu : Tap Reversi Free VIII. PHỤ LỤC 1. Luật chơi 12 - Mỗi mặt của quân cờ đại diện cho một bên chơi. Ta có thể gọi cờ hai bên là đen và trắng, nhưng cũng có thể gọi là sấp và ngửa, bởi vì mỗi quân cờ có 2 mặt riêng biệt. -Trước kia, cờ Othello không quy định vị trí đặt quân cờ đầu tiên. Sau đó, nó đã chấp nhận luật chơi mới với điều khoản là phải có 4 điểm đặt đầu tiên vào vị trí 4 hình vuông ở trung tâm bàn cờ, hai quân sẫm và hai quân nhạt. Quân màu sẫm được đi đầu tiên. Quân màu sẫm cần phải được đặt ở vị trí tồn tại ít nhất một hàng ngang hoặc dọc, hoặc chéo giữa quân mới và quân cũ và ở giữa hai quân này có một hay nhiều quân nhạt. Trong hình dưới, quân sẫm có thể được đặt ở những vị trí gợi ý. Sau khi đặt một quân, quân sẫm sẽ lật tất cả những quân nhạt nằm trên đường dóng giữa quân sẫm mới được đi và quân sẫm cũ. Những quân sáng màu đó bây giờ trở thành màu sẫm và quân sẫm có thể sử dụng chúng trong lượt đi tiếp theo, trừ phi quân nhạt lại lật chúng lại trong một nước đi nào đó. 13 Nếu quân sẫm quyết định đi ở vị trí d6 (theo hình dưới), một quân nhạt sẽ bị lật mặt và bàn cờ bây giờ có dạng như hình dưới đây. Bây giờ đến lượt quân nhạt đi cũng nước tương tự như vậy để tìm cơ hội lật mặt quân sẫm. Các khả năng có thể như sau: Quân nhạt đi vào c4 và lật được một quân sẫm: Người chơi thay phiên nhau lần lượt đi quân. Nếu một bên không đi được tiếp thì sẽ tiếp tục đến lượt người kia cho đến khi cả hai bên đều không đi được nước nào nữa. Điều này xảy ra khi các ô cờ đã kín hết quân hay khi một bên chơi không 14 còn quân nào trên bàn cờ. Người chơi có nhiều quân trên bàn cờ hơn là người thắng cuộc. Một điều khác giữa Reversi và cờ Othello về ciệc sử dụng quân. Ở Reversi mỗi người chơi được chia đều 32 quân từ lúc bắt đầu và chỉ được đi 32 quân đó (bao gồm cả hai quân trên bàn cờ lúc bắt đầu chơi) cho đến khi không còn quân nào đi được nữa. Họ không được sử dụng quân cờ của đối thủ. Ở cờ Othello tất cả quân cờ đều thuộc sở hữu chung của hai người chơi; các quân cờ được để chung trong một hộp, hai bên đều có cơ hội dùng quân ngang nhau. 2. Chiến thuật - Các quân cờ thay đổi màu rất nhanh, dễ dàng và thường xuyên, do vậy, đó là một ưu điểm nhưng cũng có thể là nhược điểm nếu cố gắng có được nhiều quân từ lúc bắt đầu. Chiếm góc, cạnh, mobility, parity, tàn cuộc và dự đoán trước mọi việc là chìa khóa của thành công trong cờ Othello. - Chiếm góc Nếu có một quân đã được đặt tại góc thì quân đó sẽ không bị đổi cho đến hết trận cờ. Do đó, người chơi có thể sử dụng quân cờ tại góc để chốt giữ nhóm quân cùng với cạnh ngay sát nó làm thành một hệ thống chắc chắn. Do vậy việc chiếm giữ góc là một chiến lược có hiệu quả khi có cơ hội đến. Nói chung, một quân cờ được ổn định khi nó được nằm trong 4 hướng ranh giới, trong một hàng đã kín các quân, trong đó có các quân cùng màu nằm cạnh liên tiếp và bị chặn hai đầu bởi quân màu khác. - Mobility Một người chơi có chiến thuật sẽ không dễ dàng từ bỏ việc chiếm góc hay bất kỳ nước đi tốt nào. Do vậy, để đoạt được những nước đi tốt này bạn cần phải ép đối thủ đi những nước từ bỏ cách đi tốt đó. Cách tốt nhất để làm việc đó là làm giảm số lượng nước đi có thể cho đối thủ của bạn. Nếu bạn nhất định tìm cách hạn chế số nước đi hợp lý của đối thủ thì sớm hay muộn họ sẽ phải đi nước đi mà họ không mong muốn. Một ví trí cần thực hiện được đó là tất cả các quân của bạn đứng cạnh nhau, bao vây xung quanh là quân của đối thủ. Với vị trí như vậy, bạn có thể đọc ra được các nước đi của đối thủ - Tại biên 15 Các quân cờ được đặt ở phía biên bàn cờ dường như chắc chắn (bởi vì chúng không bị lật mặt dễ dàng) . Bốn ô vuông ở mỗi góc bàn cờ được gọi là X-vuông. Lúc bắt đầu hay giữa ván cờ, nếu các ô đó được chiếm giữ, sẽ đảm bảo chắc chắn cho việc sở hữu chúng. - Đoán trước Như trong bất kỳ chiến thuật nào của cờ vua hay checkers, người chơi không nên chỉ xem xét về thế cờ hiện tại. Đối với mỗi nước đi, bạn cần phải cân nhắc các diễn biến có thể có từ phía đối thủ, sau đó là khả năng phản ứng lại của bạn với các nước đi đó và tiếp theo nữa là như thế nào. Tình thế hiện tại cũng có thể không liên quan đến các nước đi sau. Do vậy, khi phân tích các khả năng đi, chiếm góc hoặc bất cứ khả năng nào khác, bạn nên xem xét cách tốt nhất để thực hiện chiến lược trong một thời gian dài hơn là chỉ quan tâm đến nước đi hiện tại. 3. Các chương trình chơi game trên máy tính - Chương trình chơi cờ Othello tốt nhất có thể dễ dàng đánh bại người chơi cờ giỏi nhất. Vào đầu năm 1980, chương trình Moor đã thắng đương kim vô địch lúc đó và vào năm 1997, chương trình Logistello đã đánh bại nhà vô địch Takeshi Murakami với tỷ số 6:0. Sự nổi trội hơn này không có ở những trò chơi như cờ vua, nơi mà máy tính chơi giỏi nhất cũng ngang ngửa với người hay ở cờ vây, nơi thậm chí một người chơi trung bình cũng thắng được máy tính giỏi nhất. - Nói chung, loài người không thể thắng được trí thông minh của máy tính trong cờ Othello bởi vì máy tính có thể tính toán được rất nhiều nước đi tiếp theo, việc này con người không thể bằng được. Các nhà phân tích đã ước tính số lượng vị trí hợp lệ ở cờ Othello nhiều nhất là 1028 và nó có độ phức tạp xấp xỉ 1058. 16 17