Xây dựng game cờ gánh dân gian trên điện thoại Android.

Phát biểu bài toán

Trò chơi dân gian Cờ Gánh là một trong những trò chơi phổ biến ở nông thôn Việt Nam, nhưng đang dần bị lãng quên do sự phát triển xã hội và nhu cầu giải trí ngày càng cao Việc tin học hóa trò chơi này là hợp lý, giúp tổ chức ván chơi Cờ Gánh trở nên dễ dàng hơn Với hình ảnh sinh động và các hỗ trợ hấp dẫn, trò chơi tạo không khí vui tươi, kích thích sự hứng thú cho người chơi Luật chơi đơn giản, Cờ Gánh phù hợp với mọi lứa tuổi và hứa hẹn sẽ trở thành trò chơi phổ biến trên các máy tính hiện nay.

Mục đích, ý nghĩa, phạm vi đề tài

Tên đề tài

“Xây dựng game cờ gánh dân gian trên điện thoại Android”

Mục đích và ý nghĩa

Xây dựng game với các mục đích ý nghĩa sau:

Tạo ứng dụng game cờ gánh dân gian trên điện thoại Android với giao diện trực quan không chỉ đáp ứng nhu cầu giải trí của nhiều người chơi mà còn giúp nâng cao hiểu biết về trò chơi truyền thống này.

- Nắm bắt và hiểu được công nghệ lập trình game trên hệ điều hành Android Nâng cao kỹ năng lập trình, kỹ năng giải quyết vấn đề

- Ứng dụng trí tuệ nhân tạo để máy có khả năng suy nghĩ tối ưu cho mỗi nước

Xây dựng game cờ Gánh dân gian GVHD: PGS.TSKH Trần Quốc Chiến

- Sử dụng thành thạo một số công cụ hổ trợ cho môi trường làm việc, lập trình game.

Phạm vi đề tài

Ứng dụng game trí tuệ trên hệ điều hành Android cho phép người chơi tham gia vào các trận đấu giữa Người và Máy, với nhiều mức độ khó khác nhau, phù hợp với kích thước màn hình của thiết bị di động.

Những việc sẽ giải quyết trong đề tài

Các bước thực hiện

- Tìm hiểu thông tin liên quan

- Xem xét bàn bạc tính khả thi của các yêu cầu trong ứng dụng

- Xác định thời gian thực hiện và hoàn thành dự án

- Lên kế hoạch để thực hiện dự án

- Phân tích các yêu cầu của dự án

- Phân tích thiết kế từng chi tiết của từng module

- Dựa vào bảng phân tích thiết kế tiến hành code ứng dụng

- Tiến hành kiểm thử ứng dụng

- Báo cáo sẽ được viết song song trong suốt quá trình làm dự án.

Dự kiến kết quả đạt được

Hi vọng chương trình sẽ đáp ứng được các yêu cầu như sau:

- Xây dựng hoàn chỉnh game cờ gánh chơi giữa người và máy với các mức độ khác nhau

- Đồ họa bắt mắt, các thao tác đơn giản, tiện dụng

- Tối ưu khả năng suy nghĩ của máy

Nội dung của đề tài

Toàn bộ khóa luận bao gồm 3 phần:

Phần 1: Cơ sở lý thuyết

Phần 2: Thiết kế và xây dựng game cờ gánh

Phần 3: Kết quả của ứng dụng

Kết luận và hướng phát triển

CƠ SỞ LÝ THUYẾT

Tìm hiểu về Android

I.1 Android và hệ điều hành Android

Android là hệ điều hành di động chủ chốt, được phát triển bởi Google và dựa trên nền tảng Linux Ban đầu, Android được phát triển bởi công ty liên hợp Android, trước khi được Google mua lại vào năm 2005 Hiện nay, Android không chỉ được sử dụng trên điện thoại di động mà còn trên các thiết bị như đầu phát HD, HD Player và TV.

Các nhà phát triển ứng dụng Android chủ yếu sử dụng ngôn ngữ Java Android được ra mắt vào ngày 5 tháng 11 năm 2007, đánh dấu sự hình thành của liên minh thiết bị cầm tay mã nguồn mở với sự tham gia của 78 công ty trong lĩnh vực phần cứng, phần mềm và viễn thông, nhằm xây dựng một chuẩn mở cho điện thoại di động trong tương lai.

Tính năng mở của hệ điều hành Android cho phép các nhà phát triển tạo ra ứng dụng di động hấp dẫn, tận dụng tối đa khả năng của thiết bị Android được thiết kế với tính mở thực sự, mang đến nhiều cơ hội cho sự sáng tạo và phát triển ứng dụng.

Hình 1.1: Hình ảnh về Android

Game cờ Gánh dân gian, do PGS.TSKH Trần Quốc Chiến hướng dẫn, được phát triển trên nền tảng Linux Kernel Nó sử dụng một máy ảo tùy chỉnh nhằm tối ưu hóa bộ nhớ và tài nguyên phần cứng cho môi trường di động Nền tảng này hứa hẹn sẽ tiếp tục phát triển khi cộng đồng các nhà phát triển hợp tác để tạo ra những ứng dụng di động sáng tạo.

Tất cả ứng dụng đều có thể được phát triển cho Android, vì hệ điều hành này không phân biệt giữa ứng dụng lõi và ứng dụng của bên thứ ba Người dùng có thể tận dụng một loạt ứng dụng và dịch vụ, giúp họ tùy chỉnh điện thoại theo nhu cầu cá nhân Họ có thể thay đổi giao diện màn hình, kiểu dáng của dialer và bất kỳ ứng dụng nào khác để phù hợp với sở thích của mình.

Android giúp phá bỏ rào cản trong việc phát triển ứng dụng mới và sáng tạo bằng cách cho phép truy cập vào thông tin như địa chỉ liên hệ, lịch và vị trí địa lý Điều này mang đến trải nghiệm người dùng phong phú hơn Ví dụ, nhà phát triển có thể tạo ra ứng dụng cho phép người dùng theo dõi vị trí của bạn bè và nhận thông báo khi họ ở gần, tạo cơ hội kết nối dễ dàng hơn.

I.2 Các phiên bản của hệ điều hành Android

Android 1.1 (Petit Four): Ra mắt ngày 9-2-2009 Không bao gồm nhiều tính năng, phiên bản này bổ sung một số chức năng mới cho Google Maps hiển thị chi tiết hơn, bàn phím ảo gọi điện thoại đã có thể hiển thị hoặc ẩn khi gọi, chương trình SMS cho phép người dùng lưu tập tin đính kèm Petit Four sửa một số lỗi trong Android 1.0

Android 1.5 (Cupcake): Ra mắt ngày 30-4-2009 Cupcake, tên mã đầu tiên áp dụng cho phiên bản Android Cupcake mang nhiều tính năng mới như bàn phím ảo có khả năng dự đoán từ đang gõ, từ điển từ ngữ do người dùng đặt ra, hỗ trợ widget trên giao diện chủ, quay phim và phát lại video clip, lược sử thời gian cuộc gọi, chế độ tự động xoay màn hình theo hướng sử dụng (screen rotation)

Android 1.6 (Donut): Ra mắt ngày 30-9-2009 Donut khắc phục các chức năng

Trong phiên bản Cupcake, chức năng tìm kiếm bằng giọng nói và ký tự đã được mở rộng đến bookmark và danh bạ, giúp người dùng dễ dàng truy cập thông tin Android Market đã trở thành "chợ đầu mối" lý tưởng để tìm kiếm và khám phá các ứng dụng Android Ứng dụng chụp ảnh và quay phim trong phiên bản Donut hoạt động nhanh hơn, mang lại trải nghiệm tốt hơn cho người dùng Hệ điều hành cũng hỗ trợ màn hình có độ phân giải lớn hơn, phù hợp với xu hướng smartphone màn hình lớn hiện nay.

Android 2.0 (Eclair): Ra mắt ngày 26-10-2009 Chỉ sau gần một tháng ra mắt Donut, Google tung ra Eclair, phiên bản được nhận định là "bước đi lớn" của hệ điều hành này Eclair cải tiến rất nhiều, từ giao diện đến ứng dụng bên trong hệ thống Ứng dụng chụp ảnh tăng cường thêm chức năng zoom số (phóng to), cân bằng trắng, hỗ trợ đèn flash và các hiệu ứng màu sắc Eclair là phiên bản Android đầu tiên hỗ trợ ảnh nền động (live wallpaper) dù tùy chọn này tiêu tốn khá nhiều pin

Android 2.2 (Froyo): Ra mắt ngày 20-5-2010 Từ phiên bản 2.0 trở đi, Android dần hoàn thiện hơn Froyo mang Adobe Flash đến Android, kéo theo hàng loạt ứng dụng và game trên nền Flash Người dùng cũng có thể xem video clip nền Flash như YouTube và "ra lệnh" thực hiện cuộc gọi qua Bluetooth

Android 2.3 (Gingerbread): Ra mắt ngày 6-12-2010 Đến cuối năm 2012,

Gingerbread hiện đang chiếm ưu thế trên nhiều thiết bị Android, với tỷ lệ lên đến 54% Google đã hợp tác cùng Samsung để ra mắt smartphone đầu tiên sử dụng Gingerbread, mang tên Nexus S, và tích hợp công nghệ giao tiếp tầm gần NFC.

Android 3.0 (Honeycomb): Ra mắt ngày 22-2-2011 Đây không chỉ là một phiên bản, mà có thể xem là một thế hệ Android đầu tiên dành riêng cho máy tính bảng (tablet), ra mắt cùng tablet Motorola XOOM Honeycomb đặt nền móng quan trọng cho thế hệ Android 4.x hợp nhất, khắc phục sự phân mảng của Android

Android 4.0 (Ice Cream Sandwich) Ra mắt: ngày 19-10-2011 "Bánh kem sandwich" (ICS) là thế hệ Android được mong đợi nhất đến nay, ra đời cùng dòng smartphone "bom tấn" Samsung Galaxy Nexus, thế hệ smartphone đầu tiên trang bị ICS Ice Cream Sandwich hoạt động mượt mà, nhanh và đẹp hơn

Android 4.1 (Jelly Bean): Ra mắt: 9-7-2012 Máy tính bảng Nexus 7, sản phẩm hợp tác giữa Google và Asus, là thiết bị dùng Jelly Bean đầu tiên ra mắt Android 4.1 nâng tầm hoạt động cho hệ điều hành của Google, trở thành hệ điều hành cho thiết bị di động hàng đầu hiện nay, đe dọa cả "ông lớn" Windows

Lập trình ứng dụng Android

II.1 Thiết lập môi trường phát triển ứng dụng

Môi trường được thiết lập trên hệ điều hành Windows 8 64 bit Để tiến hành cài đặt, bạn cần chuẩn bị các gói cài đặt cần thiết.

Link: http://www.oracle.com/technetwork/java/javase/downloads/index.html

Link: http://developer.android.com/sdk/index.html

 IDE Eclipse for Java Developer

Link: http://www.eclipse.org/downloads/

II.2 Các thành phần trong Android Project

II.2.1 Tạo mới Android Project

Mở eclipse, chọn File  New  Android Application Project (trường hợp không có Android Application Project thì ta bấm vào Orther)

Hình 1.7: Tạo mới 1 ứng dụng Android

- Application Name: Tên ứng dụng mà bạn mong muốn

- Project Name: Tự động cập nhập khi chúng ta điền Application Name

Tên package là yếu tố quan trọng, bạn có thể đặt tên tùy ý nhưng cần đảm bảo dễ nhớ và không chứa ký tự đặc biệt, chỉ bao gồm chữ thường và các chữ số từ 0 đến 9.

- Minimum Required SDK: Phiên bản Android thấp nhất chạy ứng dụng này

- Target SDK: Phiên bản hiện tại của ứng dụng

- Compile With: Phiên dịch sang phiên bản khác

Sau khi tạo mới xong 1 Android Application Project ta sẽ tìm hiểu cấu trúc của một Android Project Một Android Project gồm:

- /src folder: chứa các mã nguồn (source code) là các file Java

File R.java là một phần quan trọng trong việc quản lý các tài nguyên được tạo ra từ các tập tin nguồn trong ứng dụng Android File này được tự động tạo ra và không nên bị chỉnh sửa hay thay đổi để đảm bảo tính ổn định và hoạt động chính xác của ứng dụng.

- /Android 4.4: bao gồm các API 4.4 tương ứng với hệ điều hành Android 4.4, các thư viện này được Import khi ta khởi tạo Project bằng cách chọn Target ở trên

- /assets: chứa các file tài nguyên như database sẽ đi kèm với Project khi ta đóng gói ứng dụng

- /res/drawable-hdpi: nơi lưu hình ảnh sử dụng cho ứng dụng hdpi (High dpi: độ phân giải cao) tương thích với điện thoại có màn hình WVGA800 (480x800), WVGA854 (480x854)

- /res/drawable-ldpi: cũng là thư mục để chứa các file ảnh có độ phân giải thấp hơn Low dpi: QVGA (240x320), WQVGA400 (240x400), WQVGA432 (240x432)

- /res/drawable-mdpi: chứa các file ảnh có độ phân giải trung bình Medium dpi: HVGA (320x480), WVGA800 (480x800), WVGA854 (480x854)

- /res/layout/main.xml: file thiết kế giao diện cho ứng dụng, có thể tạo thêm nhiều file khác cho nhưng màn hình khác nhau

Tập tin /res/values/strings.xml định nghĩa các giá trị cho tài nguyên trong dự án, giúp tối ưu hóa việc quản lý các giá trị mặc định của các đối tượng String trên mỗi layout.

- /AndroidManifest.xml: file cấu hình cho ứng dụng

Ngoài ra còn có một số folder và file do người lập trình tự định nghĩa

II.2.2 Thiết kế giao diện trong Android

Không giống như lập trình java thông thường, lập trình android ngoài các lớp

Xây dựng game cờ Gánh dân gian dưới sự hướng dẫn của PGS.TSKH Trần Quốc Chiến sẽ được thực hiện bằng cách sử dụng XML, giúp đơn giản hóa quy trình phát triển Việc áp dụng XML không chỉ tiết kiệm thời gian mà còn làm cho việc chỉnh sửa và nâng cấp ứng dụng trong tương lai trở nên dễ dàng hơn.

Về nguyên tắc, khi lập trình ứng dụng ta thiết kế giao diện bằng XML và cài đặt các xử lý khi tương tác với giao diện trong code

Layout được sử dụng để sắp xếp các thành phần giao diện theo một trật tự nhất định, giúp thiết kế giao diện phù hợp với nhiều độ phân giải khác nhau Khi lập trình, việc kết hợp nhiều layout với nhau là cần thiết để tạo ra giao diện mong muốn.

 FrameLayout: Layout đơn giản nhất, thêm các thành phần con vào góc trên bên trái của màn hình

 LinearLayout: thêm các thành phần con theo 1 chiều nhất định

(ngang hoặc dọc) Đây là layout được sử dụng nhiều nhất

 RelativeLayout: thêm các thành phần con dựa trên mối quan hệ với các thành phần khác hoặc với biên của layout

 TableLayout: thêm các thành phần con dựa trên 1 lưới các ô ngang và dọc

 AbsoluteLayout: thêm các thành phần con dựa theo tọa độ x, y

 Một số thuộc tính cơ bản

The layout_width and layout_height attributes in Android define the dimensions of a view The value "fill_parent" makes the view's width or height match the size of its parent layout, while "wrap_content" adjusts the view to fit its content precisely.

In LinearLayout, views are arranged either horizontally or vertically, and the orientation is specified to determine the layout style (horizontal or vertical).

 Gravity: thuộc tính này qui định các view nằm bên trong layout sẽ đặt theo vị trí nào so với layout(trung tâm, trái , phải, trên dưới…)

Trọng số (weight) được sử dụng để xác định tỷ lệ diện tích hiển thị của từng view trên màn hình Tỷ lệ này được tính dựa trên trọng số của từng view so với tổng trọng số Đối với các view không khai báo trọng số, hệ thống sẽ tự động xem xét chiều rộng (width) và chiều cao (height) để tính toán.

Android cung cấp một thư viện đồ họa toàn diện thông qua gói android.graphics, bao gồm các lớp quan trọng như Color và Canvas, hỗ trợ phát triển ứng dụng với các tính năng đồ họa phong phú.

- Color: Color được thể hiện bởi 4 giá trị, đầu tiên là alpha, red, green and blue

Mỗi thể hiện màu trong AGRB gồm 256 giá trị 8 bit, cho phép một màu có giá trị cao nhất lên tới 32 bit integer Android thuận tiện hơn khi cho phép thể hiện giá trị màu bằng số nguyên, thay vì sử dụng lớp Color Để khởi tạo một giá trị màu, ta có thể khai báo theo cách đơn giản.

Nếu ta có thể biết độ alpha, thì ta có thể khai báo:

Nhưng trong Android, người ta thường định nghĩa trong file XML, chẳng hạn color.xml để sau này thuận tiện hơn cho việc sửa chữa

Khi đó ta sử dụng màu trong code của mình bằng cách:

Paint là một lớp thiết yếu trong Android, không thể thiếu trong bất kỳ ứng dụng nào Lớp này bao gồm các kiểu dáng, màu sắc và thông tin cần thiết để vẽ các dạng đồ họa như bitmap và văn bản.

Ví dụ: ta paint cái gì lên screen, muốn vẽ nó với solid color Ta set nó như sau: cPaint.setColor(Color.LTGRAY);

Canvas là một lớp quan trọng trong xây dựng ứng dụng, đặc biệt trong game Trong khi lớp Paint cung cấp các công cụ như màu sắc, đường nét và kích thước, Canvas cho phép bạn vẽ các hình dạng như đường thẳng, đường tròn và hình chữ nhật Để sử dụng Canvas cho việc vẽ, bạn cần ghi đè phương thức View.onDraw().

@Override Protected void onDraw(Canvas canvas) { // Drawing commands go here

} Lúc này ta có thể đưa những phương thức vẽ vào onDraw()

Đối tượng Bitmap là một kiểu định dạng tập tin hoặc tổ chức bộ nhớ dùng để lưu trữ ảnh số, bao gồm một mảng hai chiều với mỗi phần tử chứa giá trị màu RGB tương ứng cho từng điểm màu trên bức ảnh hoặc điểm màu hiển thị trên màn hình.

Ta dùng BitmapFactory.decodeResource( ) để đối tượng Bitmap từ một tập tin hình ảnh lưu trong thư mục drawable

@Override protected void onDraw(Canvas canvas) {

Bitmap bitmap BitmapFactory.decodeResource(getResource(),

Android cung cấp một thư viện đa phương tiện toàn diện bao gồm âm thanh và video thông qua gói android.media, với lớp MediaPlayer là phần cốt lõi của gói này.

THIẾT KẾ VÀ XÂY DỰNG ỨNG DỤNG GAME CỜ GÁNH

Phân tích hệ thống

Xây dựng game cờ gánh trên các dòng điện thoại Android cung cấp các mức độ chơi khó dễ khác nhau giữa ngươi chơi với máy

Khi trò chơi bắt đầu, một màn hình splash sẽ xuất hiện trong 5 giây trước khi chuyển sang menu chính Tại menu này, người chơi sẽ thấy các lựa chọn chính để tiếp tục trải nghiệm.

 Bắt đầu chơi: Chọn mức độ để bắt đầu chơi giữa người với máy

 Cài đặt: Tùy chọn âm thanh, mặt định ban đầu là bật âm thanh

 Hướng dẫn: Hiển thị thông tin hướng dẫn luật chơi game cờ gánh

 Giới thiệu: Hiển thị thông tin về tác giả

 Thoát Để thực hiện các lựa chọn trên người dùng phải trỏ vào menu có tên tương ứng với sự lựa chọn đó

Khi tham gia trò chơi, người chơi cần chỉ vào quân cờ muốn di chuyển và sau đó chọn ô đích Ứng dụng sẽ tự động cập nhật các quân cờ bị ăn sau mỗi lượt đi Bên nào hết quân cờ trước sẽ thua cuộc Nếu người chơi chiến thắng, màn hình sẽ hiển thị thông báo thắng; ngược lại, nếu thua, màn hình sẽ hiển thị thông báo thua.

Người chơi có thể dễ dàng hủy bỏ ván chơi hiện tại và quay lại Menu bằng cách chạm vào mục Menu ở góc dưới màn hình, sau đó xác nhận việc hủy bỏ để trở về Menu.

Để xây dựng game cờ Gánh dân gian, người chơi có thể lùi lại một bước nếu đi sai bằng cách chạm vào nút Lùi ở góc dưới màn hình Chương trình chỉ cho phép lùi lại một nước đi gần nhất để đảm bảo tính công bằng và thú vị trong trò chơi.

Sau khi trình bày tổng quan về các chức năng sẽ được phát triển trong ứng dụng, cần xác định các yêu cầu đối với môi trường và hệ thống, bao gồm các tiêu chí kỹ thuật và điều kiện hoạt động cần thiết để đảm bảo hiệu suất và tính ổn định của ứng dụng.

I.2.1 Yêu cầu phi chức năng

 Thiết bị di động sử dụng hệ điều hành Android 2.3 trở lên

 Đồ họa bắt mắt, dễ nhìn

 Dễ dàng sử dụng, chuyển đổi qua lại giữa các trạng thái trong khi chơi game

 Sử dụng touch để thao tác các hoạt động khi chơi game

 Cung cấp chức năng bật hoặc tắt âm thanh

 Hiển thị trạng thái của từng lượt đi

 Hiển thị các nước đi hợp lệ khi có một quân cờ được chọn để người chơi chọn ra một nước đi

 Phải có chức năng undo để quay lại 1 nước đi gần nhất nếu trước đó người chơi đi sai

 Thông báo kết quả chung cuộc khi ván chơi kết thúc

 Ứng dụng phải cung cấp đầy đủ thông tin về luật chơi, hướng dẫn cách chơi và cách sử dụng thiết bị để chơi.

Thuật toán tìm kiếm có đối thủ

Chương trình chơi cờ đầu tiên được viết bởi Claude Shannon vào năm 1950 đã

Trong bài viết này, chúng ta sẽ khám phá việc xây dựng game cờ Gánh dân gian dưới sự hướng dẫn của PGS.TSKH Trần Quốc Chiến, tập trung vào các trò chơi có hai người tham gia Việc giải quyết bài toán tìm kiếm trong không gian trạng thái là cần thiết để phát triển chiến lược cho máy tính chọn các nước đi hợp lệ Tuy nhiên, thách thức lớn hơn là người chơi không thể dự đoán nước đi tiếp theo của đối thủ, làm cho quá trình tìm kiếm trở nên phức tạp hơn Chương này sẽ đi sâu vào một số vấn đề liên quan đến việc phát triển chiến lược trong trò chơi này.

 Chiến lược tìm kiếm phổ biến như Minimax

 Phương pháp cắt cụt Alpha – Beta, một kỹ thuật tăng hiệu quả của tìm kiếm Minimax

II.1 Cây trò chơi đầy đủ

Các trò chơi đối kháng đặc trưng bởi việc hai người chơi lần lượt thực hiện các nước đi hợp lệ theo luật chung của trò chơi Các trò chơi như cờ vua, cờ tướng, cờ ca rô và cờ gánh đều tuân theo nguyên tắc này Trong cờ gánh, một người điều khiển quân Xanh và người còn lại điều khiển quân Đỏ, mỗi người có quyền lựa chọn nước đi của mình dựa trên các quy định đã được thiết lập.

Luật đi quân cờ của cả hai bên là giống nhau, và cả hai người chơi đều nắm rõ thông tin về tình hình cuộc chơi Trong mỗi lượt, người chơi cần tìm kiếm nước đi tốt nhất trong số nhiều lựa chọn hợp lệ, với mục tiêu cuối cùng là giành chiến thắng sau chuỗi nước đi đã thực hiện.

Chơi cờ có thể được mô hình hóa trong không gian trạng thái, trong đó mỗi trạng thái đại diện cho một tình huống cụ thể của trò chơi, thể hiện sự sắp xếp các quân cờ trên bàn cờ.

- Trạng thái xuất phát là sự sắp xếp các quân cờ của hai bên khi bắt đầu cuộc chơi (chưa ai đưa ra nước đi)

- Các toán tử biến đổi trạng thái là các nước đi hợp lệ

Các trạng thái kết thúc trong trò chơi là những tình huống mà cuộc chơi dừng lại, thường được xác định bởi các điều kiện dừng cụ thể, chẳng hạn như chiến thắng của quân Xanh hoặc quân Đỏ.

- Hàm kết cuộc: mang giá trị tương ứng với mỗi trạng thái kết thúc

Trong các trò chơi đối kháng, người chơi điều khiển quân Xanh luôn cố gắng xây dựng một chuỗi các nước đi xen kẽ với quân Đỏ, nhằm tạo ra một lộ trình chiến thắng từ trạng thái ban đầu đến trạng thái kết thúc.

Không gian tìm kiếm cho các trò chơi này được mô tả bằng một cây trò chơi, trong đó gốc cây đại diện cho trạng thái xuất phát và các đỉnh tương ứng với các trạng thái của bàn cờ Các cung (u, v) thể hiện sự chuyển đổi từ trạng thái u sang trạng thái v Đỉnh được gán nhãn Xanh (Đỏ) tương ứng với nước đi của quân Xanh (Đỏ) Nếu đỉnh u được gán nhãn Xanh (Đỏ), thì các đỉnh con v của nó là tất cả các trạng thái có được từ u thông qua một nước đi hợp lệ Do đó, các đỉnh trên cùng một mức của cây đều mang nhãn giống nhau, và các lá của cây đại diện cho các trạng thái kết thúc.

Ví dụ 1: Trò chơi Cờ Gánh

Trên bàn cờ 5x5, có hai loại quân: quân Xanh và quân Đỏ Quân Xanh có khả năng di chuyển đến ô trống bên phải, bên trên hoặc bên dưới, trong khi quân Đỏ có thể di chuyển tới ô trống bên trái, bên phải hoặc bên trên Trò chơi kết thúc khi một bên ăn hết quân của đối phương theo các quy tắc của cờ Gánh, và bên đó sẽ giành chiến thắng.

Giả sử Đỏ đi trước, ta có cây trò chơi được biểu diễn như sau

Hình 16:Biểu diễn cây trò chơi Cờ Gánh với Đỏ đi trước

Quá trình chơi cờ diễn ra giữa hai bên Xanh và Đỏ, trong đó mỗi bên lần lượt đưa ra quyết định và thực hiện các nước đi hợp lệ Trên cây trò chơi, mỗi nước đi tạo ra một đường đi từ gốc đến lá Khi đạt đến một đỉnh u, nếu u là đỉnh Xanh (Đỏ), bên Xanh (Đỏ) sẽ chọn một trong các đỉnh Đỏ (Xanh) v là con của u Tại đỉnh v, bên Đỏ (Xanh) sẽ tiếp tục chọn một trong các đỉnh Xanh (Đỏ) w là con của v Quá trình này sẽ kết thúc khi đạt đến một đỉnh lá của cây.

Để xác định nước đi tối ưu cho Xanh tại đỉnh u, cần tìm đỉnh con tốt nhất cho Xanh trong số các đỉnh con của u Giả sử đối thủ Đỏ sẽ chọn nước đi tốt nhất cho mình từ đỉnh v Giá trị của các đỉnh trong cây trò chơi được xác định từ các đỉnh lá, tương ứng với các trạng thái kết thúc, với giá trị lớn hơn tốt cho Xanh và giá trị nhỏ hơn tốt cho Đỏ Quá trình xác định giá trị các đỉnh diễn ra từ mức thấp nhất đến gốc u.

Trong quá trình xây dựng game cờ Gánh dân gian dưới sự hướng dẫn của PGS.TSKH Trần Quốc Chiến, giá trị của các đỉnh được xác định theo quy tắc cụ thể: nếu v là đỉnh Xanh, giá trị của nó sẽ là giá trị lớn nhất trong số các đỉnh con; ngược lại, nếu v là đỉnh Đỏ, giá trị của nó sẽ là giá trị nhỏ nhất trong các đỉnh con.

Các hàm đệ quy MaxVal và MinVal được sử dụng để gán giá trị cho các đỉnh trong cây quyết định Hàm MaxVal xác định giá trị cho các đỉnh Xanh, trong khi hàm MinVal xác định giá trị cho các đỉnh Đỏ Cụ thể, hàm MaxVal sẽ trả về giá trị của đỉnh nếu nó là đỉnh kết thúc, thông qua hàm Eval(u) để tính giá trị của thế cờ Xanh Ngược lại, nếu không phải là đỉnh kết thúc, MaxVal sẽ lấy giá trị lớn nhất từ các đỉnh con của nó thông qua hàm MinVal Tương tự, hàm MinVal cũng sẽ trả về giá trị của đỉnh nếu là đỉnh kết thúc, sử dụng Eval(u) để tính giá trị của thế cờ Đỏ, và nếu không, nó sẽ lấy giá trị nhỏ nhất từ các đỉnh con thông qua hàm MaxVal.

Hàm Eval(u) được sử dụng để tính giá trị của thế cờ, đánh giá độ lợi thế của trạng thái trong game cờ Gánh Hàm này tính tổng số quân cờ hiện có của quân Xanh (Đỏ) Thủ tục chọn nước đi cho quân Xanh tại đỉnh u diễn ra trong quy trình Minimax(u,v), trong đó v là biến lưu lại trạng thái mà quân Xanh sẽ chọn để đi tới từ u Quy trình Minimax bắt đầu với việc khởi tạo giá trị val bằng -∞.

Xây dựng game cờ Gánh dân gian GVHD: PGS.TSKH Trần Quốc Chiến end;

Chiến lược Minimax là quy trình chọn nước đi trong trò chơi, trong đó người chơi Xanh lựa chọn nước đi dẫn đến đỉnh có giá trị lớn nhất (max) trong số các đỉnh con, trong khi người chơi Đỏ phản ứng bằng cách chọn nước đi tới đỉnh có giá trị nhỏ nhất (min) trong các đỉnh con.

Thuật toán Minimax là thuật toán tìm kiếm theo độ sâu, ở đây ta đã cài đặt thuật toán Minimax bởi các hàm đệ quy

Chiến lược Minimax lý thuyết giúp tìm nước đi tối ưu cho Xanh, nhưng thực tế không khả thi do yêu cầu thời gian để tính toán Thuật toán này cần xem xét toàn bộ các đỉnh của cây trò chơi, mà trong các trò chơi phức tạp như cờ vua, cây trò chơi có thể lên tới khoảng 10^120 đỉnh chỉ với độ sâu 40 Độ phức tạp thời gian của thuật toán Minimax là O(b^m), với m là độ cao cây và b là số nước đi tại mỗi đỉnh Để tìm nước đi tốt hơn mà không cần tính toán tối ưu, chúng ta sử dụng hàm đánh giá và chỉ xem xét một phần của cây trò chơi.

Thiết kế hệ thống thông tin

III.1 Xây dựng kiến trúc chương trình

 Kiến trúc của hệ thống menu trong ứng dụng game

Hình 19: Kiến trúc menu trong game

Khi bắt Khi bắt đầu vào ứng dụng game sau trạng thái Splash là trạng thái MainMenu Tại đây User có thể chọn New game, Options, Help, About, Exit

 New game: Bắt đầu vào chơi game, người chơi sẽ chọn mức độ khó để chơi với máy

 Options: Là một menu con bao gồm các lựa chọn như: Sound Options

 Help: Cung cấp thông tin về luật chơi, cách chơi của game, thông tin về cách sử dụng, chức năng của các phím

 About: Cung cấp thông tin về bản quyền (thời gian sản xuất ra ứng dụng, tên tác giả…)

 Exit: Cho phép User thoát khỏi game

 Kiến trúc của Game Loop (Vòng lặp game)

Hình 20: Kiến trúc Game Loop của game

Hàm Draw chịu trách nhiệm vẽ lên màn hình giá trị của các biến trạng thái, với việc vẽ phụ thuộc vào vị trí, sự định hướng và trạng thái hiện tại Quá trình vẽ sẽ được cập nhật mỗi khi hàm validate() được gọi.

 Update: có nhiệm vụ thay đổi toàn trạng thái của game, không liên quan đến việc draw Nó bao gồm A.I, Input, và Sound

 A.I Decisions: A.I tạo ra những quyết định của máy như: di chuyển tới đâu, đánh giá vị trí của quân cờ

 Input Handling: Các hành động của User sẽ được phân tích và xử lý

Nếu lệnh hợp lệ sẽ được thực hiện ngay lập tức, ngược lại chương trình sẽ đưa ra thông tin phản hồi cho User

 Sounds: hiệu ứng âm thanh bao gồm nhạc nền, sound lúc di chuyển 1 quân cờ sẽ được cập nhật mỗi khi cần

 Kiến trúc thuộc tính đối tƣợng

CurTouchPos movedPos isSelected isLoad isPreviousLoad

Hình 21: Các thuộc tính của ChessBoard

ChessBoard được cấu thành từ các thuộc tính và đối tượng Item, trong đó đối tượng Item mô tả quân cờ cùng với vị trí hiện tại và vị trí trước đó của quân cờ.

 Index: Biểu diễn quân cờ của bên xanh hay đỏ

 CurrentPos: Vị trí hiện tại của quân cờ

 PreviousPos: Vị trí trước đó của quân cở

 CurSelectedPos: Vị trí hiện tại đang chọn

 CurTouchPos: Vị trí trỏ (touch) lên màn hình

 movedPos: Vị trí quân cờ vừa di chuyển

 isSelected: Kiểm tra quân cờ nào đang chọn không

 isLoad: Kiểm tra nước mới đi mở gánh hay không

 isPreviousLoad: Trạng thái mở gánh trước đó

 indexYou: Màu quân cờ của bạn xanh hay đỏ

 depthInit: Độ sâu (độ khó) của thuật toán tìm kiếm Minimax

 isPlay: Kiểm tra có phải đến lượt bạn đi hay không

III.2 Xây dựng cấu trúc dữ liệu và thuật toán

Tuần tự để tìm ra một nước đi tốt nhất

Khởi tạo độ sâu cần tìm kiếm nước đi

Thực hiện nước đi tốt nhất cho máy

Chọn nước đi tốt nhất cho người Đánh giá các nước đi Đánh giá các nước đi Đánh giá các nước đi

Thực hiện nước đi tốt nhất cho máy

1 đơn vị Độ sâu = độ sâu ban đầu

Lần lượt thực hiện từng nước đi trong tập các nước đi của máy Giảm độ sâu đi 1 đơn vị

Lần lượt thực hiện các nước đi tiếp theo Tiếp tục giảm độ sâu 1 đơn vị

Tiến hành thực hiện các nước đi tiếp theo, giảm độ sâu 1 đơn vị cho đến khi đạt được độ sâu = 0 Trong trạng thái này, máy hoặc người chơi có thể chiến thắng.

Hình 22: Máy tìm nước đi tốt nhất theo chiến lược Minimax

Mỗi quân cờ item sẽ có các thuộc tính (indexBitmap, currentCol, currentRow, previousCol, previousRow) chi tiết như sau:

- indexBitmap: Biễu diễn giá trị quân xanh là 1, quân đỏ là 2

- currentCol: Vị trí cột hiện tại của quân cờ

- CurrentRow: vị trí hàng hiện tại của quân cờ

- previousCol: Vị trí cột trước đó quân cờ vừa rời đi

- previousRow: Vị trí dòng trước đó quân cờ vừa rời đi

Bàn cờ ChessBoard bao gồm 16 quân cờ, được tổ chức thành một mảng Items với 16 phần tử kiểu Item, tương ứng với các quân cờ trên bàn cờ.

Ta khởi tạo giá trị ban đầu cho bàn cờ như sau:

Hình 23: Khởi tạo giá trị bàn cờ ban đầu

Ta tạo được mảng như sau:

Item[] = { item1(1, 0, 0, x, x), item2(1, 1, 0, x, x), item3(1, 2, 0, x, x), item4(1, 3, 0, x, x), item5(1, 4, 0, x, x), item6(1, 0, 1, x, x), item7(1, 4, 1, x, x), item8(1, 0, 2, x, x), item9(2, 4, 2, x, x), item10(2, 0, 3, x, x), item11(2, 4, 3, x, x), item12(2, 0, 4, x, x), item13(2, 1, 4, x, x), item14(2, 2, 4, x, x), item15(2, 3, 4, x, x), item16(2, 4, 4, x, x) }

Nước đi hợp lệ trong cờ được xác định dựa trên vị trí hiện tại của quân cờ Để thực hiện một nước đi hợp lệ, quân cờ phải di chuyển đến một vị trí kề bên, tuân theo các đường kẻ trên bàn cờ và không được chèn lên quân cờ khác.

Nhìn vào bàn cờ ta thấy nếu quân cờ đang đứng ở vị trí dòng currentRow và vị trí cột currentCol thì:

 Nếu tổng số dòng và số cột (currentCol+currentRow) là một số lẻ thì quân cờ đó chỉ có thể đi theo hàng ngang hoặc cột dọc

Nếu tổng số dòng và số cột (currentCol + currentRow) là một số chẵn, quân cờ không chỉ có thể di chuyển theo chiều ngang và chiều dọc mà còn có khả năng di chuyển theo đường chéo.

Chỉ đi trong phạm vi bàn cờ nên vị trí đi tới phải thỏa mãn số dòng và số cột nằm trong khoảng từ 0 đến 4

Ví dụ 2: Quân cờ sau đang nằm ở vị trí (2,1) có tổng số dòng và cột là 3 (số lẻ) nên chỉ có thể đi ngang hoặc dọc

Hình 24: Ví dụ quân cờ chỉ di chuyển theo hàng ngang, cột dọc

Quân cờ tại vị trí (3,1) có khả năng di chuyển theo hàng ngang, cột dọc và đường chéo do tổng số dòng và cột là 4, tức là số chẵn.

Hình 25:Nước đi hợp lệ của quân cờ

Sau mỗi nước đi, vị trí của quân cờ sẽ được thay đổi Khi di chuyển quân cờ item1 đến vị trí mới (i, j), ta cập nhật giá trị của item1 bằng cách gán item1.previousCol = item1.currentCol và item1.previousRow = item1.currentRow.

Tương tự như việc di chuyển các quân cờ, việc ăn các gánh cũng phụ thuộc vào vị trí mà quân cờ di chuyển đến

 Mở gánh Để kiểm tra nước vừa đi có phải là nước mở gánh hay không, ta cần kiểm tra các điều kiện sau:

- Có ít nhất 1 quân cờ của đối phương có thể di chuyển đến vị trí cũ mà quân cờ vừa rời khỏi

- Nếu quân cờ của đối phương di chuyển tới vị trí đó thì phải gánh được ít nhất 1 gánh

Nếu quân cờ vừa đi thỏa mãn hai điều kiện, nó sẽ tạo ra một nước mở gánh tại vị trí mà quân cờ vừa rời khỏi Điều này buộc đối phương phải di chuyển vào vị trí mở gánh để ăn gánh.

Trong trường hợp mở gánh, khi quân xanh di chuyển từ vị trí (1,1) lên (1,0), vị trí (1,1) sẽ được mở gánh để quân đỏ có thể vào và ăn gánh Điều này yêu cầu quân đỏ phải đi vào vị trí (1,1) để thực hiện ăn gánh, và không được phép di chuyển vào ô khác trong tình huống này.

Hình 26: Ví dụ quân cờ xanh đang mở gánh, đối phương phải vào ăn gánh

 Bóp chết Để kiểm tra nước vừa đi có bóp chết được quân cờ nào của đối phương hay không, ta lần lượt thực hiện:

- Ăn các gánh có thể của đối phương (chuyển các quân cờ bị gánh thành quân cờ của mình)

Để kiểm tra các quân cờ bị kẹt, ta tạo một mảng tạm gọi là ItemsTemp[], ban đầu gán mảng này bằng giá trị của mảng Items[], phản ánh trạng thái hiện tại của các quân cờ.

Loại bỏ các quân cờ di chuyển của đối phương khỏi mảng tạm ItemsTemp[] cho đến khi không còn quân cờ nào của đối phương có khả năng di chuyển.

Kiểm tra mảng tạm ItemsTemp[] để xác định xem còn quân cờ nào của đối phương tồn tại hay không Tất cả các quân cờ của đối phương còn lại trong mảng ItemsTemp[] sẽ bị loại bỏ và chuyển thành quân cờ của mình.

Ví dụ 5: Các bước tìm quân cờ bị bóp chết

Hình 27: Ví dụ các bước tìm các quân cờ bị bóp chết

III.3 Biểu đồ trạng thái

 Biểu đồ trạng thái của Ingame

Trạng thái InGame sẽ duy trì cho đến khi ván chơi kết thúc hoặc người dùng nhấn nút Exit Nếu người dùng chọn Continue sau khi ván chơi kết thúc, trạng thái InGame sẽ được khởi động lại Ngược lại, nếu người dùng chọn Exit, hệ thống sẽ chuyển ngay sang trạng thái MainMenu, kết thúc trạng thái InGame.

Hình 28: Biểu đồ trạng thái InGame

 Biểu đồ trạng thái cho cả hệ thống

Khi khởi động ứng dụng, người dùng sẽ thấy trạng thái Splash, tiếp theo là trạng thái MainMenu Tại MainMenu, có nhiều tùy chọn con như New game, Options, Help và About, cho phép người dùng quay lại MainMenu khi cần Nếu chọn Exit từ MainMenu, ứng dụng sẽ chuyển sang trạng thái kết thúc.

Biểu đồ lớp

Xây dựng biểu đồ lớp cho ứng dụng

KẾT QUẢ CỦA ỨNG DỤNG

Tiêu đề	Xây Dựng Game Cờ Gánh Dân Gian Trên Điện Thoại Android
Tác giả	Nguyễn Quốc Tùng
Người hướng dẫn	PGS.TSKH Trần Quốc Chiến
Trường học	Đại học Đà Nẵng
Chuyên ngành	Cử nhân công nghệ thông tin
Thể loại	khóa luận tốt nghiệp
Năm xuất bản	2014
Thành phố	Đà Nẵng

Định dạng
Số trang	69
Dung lượng	2,7 MB