TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
*

BÁO CÁO MÔN HỌC
TRÍ TUỆ NHÂN TẠO
Đề tài: Chương trıǹ h trò chơi cờ tướng
sử du ̣ng giải thuâ ̣t cắ t tıả α-β
Giảng viên: Nguyễn Nhâ ̣t Quang
Nhóm sinh viên thực hiên:
̣

Ho ̣ tên
1. Trầ n Văn Thành
2. Đă ̣ng Bá Tú
3. Vũ Thi ̣Nga

MSSV
20133560
20134472
20132741

Lớp
CNTT-TT 2.04
CNTT-TT 2.01
CNTT-TT 2.04

Hà Nô ̣i
Ngày 15 tháng 11 năm 2015

LỜI MỞ ĐẦU
Trı́ tuê ̣ nhân ta ̣o (hay AI: Articifial Intelligence) là mô ̣t ngành khoa ho ̣c ngày càng
phát triể n ma ̣nh mẽ và có ứng du ̣ng rô ̣ng raĩ trong cuô ̣c số ng. Rõ ràng máy tı́nh với
đô ̣ thông minh nhấ t đinh
̣ có ảnh hưởng không nhỏ đế n cuô ̣c số ng ngày nay và trong
tương lai phát triể n của văn minh nhân loa ̣i. Mô ̣t trong những ứng du ̣ng có thể kể đế n
của AI đó là viê ̣c xây dựng, phát triể n các trò chơi đố i kháng. Cờ tướng cũng là mô ̣t
trong số đó.
Cờ tướng có nguồ n gố c từ Trung Quố c, là trò chơi trı́ tuê ̣ dành cho hai người, cùng
với cờ vua trở thành hai loa ̣i cờ phổ biế n nhấ t trên thế giới.
Để tı̀m hiể u sâu hơn về AI nói chung cũng như các kı ̃ thuâ ̣t tı̀m kiế m nói riêng,
chúng em quyế t đinh
̣ lư ̣a cho ̣n đề tài: “Chương trı̀nh trò chơi cờ tướng sử du ̣ng giải
thuâ ̣t cắ t tı̉a α-β”
Do thời gian ha ̣n he ̣p cũng như viê ̣c thiế u nhiề u kı ̃ năng trong xây dư ̣ng, thiế t kế
phầ n mề m cũng như những hiể u biế t về AI, đề tài của chúng em vẫn còn nhiề u ha ̣n
chế . Rấ t mong nhâ ̣n đươ ̣c sư ̣ đóng góp ý kiế n của thầ y và các ba ̣n để đề tài ngày càng
hoàn thiêṇ hơn.


MỤC LỤC
I.

Giới thiệu mô tả bài toán thực tế………………………………….

II.

Phương pháp giải quyết bài toán……………………………….....

III.


Các tài nguyên, dữ liệu sử dụng từ bên ngoài…………………….

IV.

Các vấn đề gặp phải………………………………………………

V.

Phương pháp giải quyết…………………………………………..

VI.

Đánh giá…………………………………………………………..

VII. Ý tưởng cải tiến…………………………………………………...


NỘI DUNG
I. Giới thiê ̣u, mô tả bài toán thực tế
Cờ tướng là loa ̣i cờ diễn ra giữa hai người chơi. Xét mô ̣t ván cờ, 2 người chơi
lầ n lươ ̣t thay phiên nhau đi các quân cờ trên bàn cờ sao cho phù hơ ̣p với luâ ̣t
chơi môn cờ tướng để nhằ m chiế u tướng đố i phương và dành chiế n thắ ng. Bài
toán đă ̣t ra là cầ n xây dư ̣ng mô ̣t chương trı̀nh để máy tı́nh có thể tư ̣ đô ̣ng chơi
cờ, thi đấ u với đố i thủ là con người, đảm bảo chấ t lươ ̣ng nước đi cũng như chi
phı́ vı̀ thời gian.
Chương trıǹ h chơi cờ có các chức năng sau:
- Ta ̣o môi trường là giao diêṇ bàn cờ và các quân cờ cho 2 đố i thủ người chơi
và máy tı́nh.
- Máy tı́nh sinh nước đi tư ̣ đô ̣ng khi đế n lươ ̣t đảm bảo đúng luâ ̣t chơi bằ ng viê ̣c

đánh giá điể m khi đi thử từng quân cờ, lấ y điể m quân cờ đa ̣t giá tri lơ
̣ ́ n nhấ t và
thực hiê ̣n nước đi đó.
- Sau đó đế n lươ ̣t người chơi thực hiê ̣n nước đi của mı̀nh
- Chương trın
̀ h tiế p tu ̣c lă ̣p la ̣i như vâ ̣y đế n khi người chơi thoát chương trıǹ h
hoă ̣c xác đinh
̣ đươ ̣c người thắ ng cuô ̣c.

II. Phương pháp giải quyế t bài toán
Trò chơi đươ ̣c biể u diễn trong mô ̣t không gian tra ̣ng thái. Nút gố c biể u diễn
tra ̣ng thái bắ t đầ u, mỗ i nước đi se ̃ biế n đổ i tra ̣ng thái hiêṇ hành thành mô ̣t tra ̣ng


thái mới. Các tra ̣ng thái bàn cờ khác nhau đươ ̣c biể u diễn thành mô ̣t cây trò
chơi, chương trı̀nh tiế n hành tı̀m kiế m trên cây để tı̀m nước đi tố t nhấ t.
Chương trın
̀ h sẽ đươ ̣c dư ̣ tıń h trước mô ̣t đô ̣ sâu lớp của cây tı̀m kiế m, các tra ̣ng
thái trên mức đó đươ ̣c đánh giá theo mô ̣t hàm heuristic. Chương trıǹ h sử du ̣ng
giải thuâ ̣t cắ t tıả α-β.Ý tưởng của tı̀m kiế m α-β đó là thay vı̀ tım
̀ kiế m toàn bô ̣
không gian đế n mô ̣t đô ̣ sâu cố đinh,
̣ tı̀m kiế m α-β thư ̣c hiêṇ theo kiể u tı̀m kiế m
sâu. Giá tri α
̣ liên quan đế n các nút MAX và có khuynh hướng không bao giờ
giảm, trong khi giá tri β̣ la ̣i liên quan đế n các nút MIN và có khuynh hướng
không bao giờ tăng.
Hai luâ ̣t cắ t tı̉a dư ̣a trên các giá tri α,
̣ β:
- Quá trı̀nh tı̀m kiế m có thể kế t thúc bên dưới mô ̣t nút MIN nào có giá tri β̣

nhỏ hơn hoă ̣c bằ ng giá tri ̣α của mô ̣t nút cha MAX bấ t kı̀ nào đó.
- Quá trı̀nh tı̀m kiế m có thể kế t thúc bên dưới mô ̣t nút MAX nào có giá tri α
̣
nhỏ hơn hoă ̣c bằ ng giá tri ̣ β của mô ̣t nút cha MIN bấ t kı̀ nào đó.
Giải thuâ ̣t giúp tı̉a bớt nhánh trên cây trò chơi, từ đó tăng hiêụ quả tı̀m kiế m.
Ta xét chi tiế t phương pháp đươ ̣c dùng để giải quyế t bài toán:
1. Biể u diễn các quân cờ
- Ta xây dư ̣ng các lớp biể u diễn cho từng quân cờ.
- Trong mỗi lớp ta se ̃ ta ̣o mô ̣t hàm getValue() trả la ̣i giá tri ̣của quân đó. Bên
ca ̣nh đó, ở các lớp Cannon, Chariot, Horse, Soldier, ta dùng mô ̣t mảng lưu
la ̣i giá tri ̣khác nhau ta ̣i mỗi vi trı
̣ ́ của chúng trên bàn cờ. Các giá tri du
̣ ̀ ng để
phu ̣c vu ̣ cho viê ̣c xây dựng hàm lươ ̣ng giá sau này.
- Dựa trên luâ ̣t chơi của môn cờ tướng, trong mỗi lớp ta cũng xây dư ̣ng hàm
để kiể m tra các nước đi hơ ̣p lê ̣ cho từng quân cờ, đảm bảo đươ ̣c vi trı
̣ ́ giới
ha ̣n, tı́nh bi ̣chă ̣n của mô ̣t số quân.
2. Hàm lươ ̣ng giá thế cờ


Như đã trı̀nh bày ở trên, trong mỗi lớp biể u diễn quân cờ sẽ có hàm để trả
la ̣i giá tri ̣của quân cờ đó. Để tı́nh giá tri ̣của mô ̣t thế cờ, ta thiế t kế mô ̣t hàm
lươ ̣ng giá đơn giản. Đó là, lấ y tổ ng điể m quân mı̀nh trừ đi tổ ng điể m quân
đố i phương.
Giá tri ̣của các quân cờ đươ ̣c tıń h dư ̣a theo cách tıń h giá tri ̣trong tài liêụ
“Computer Chinese Chess”
Dưới đây là giá tri ̣mă ̣c đinh
̣ của các quân cờ:
General


Chariot

Cannon

Elephant Horse

Advisor

Soldier

6000

600

285

120

120

30

270

Giá tri ̣vi ̣trı́ của các quân:
Cannon: int[][]=

Chariot: int[][]=


{6, 4, 0, -10, -12, -10, 0, 4, 6},

{14, 14, 12, 18, 16, 18, 12, 14, 14},

{2, 2, 0, -4, -14, -4, 0, 2, 2},

{16, 20, 18, 24, 26, 24, 18, 20, 16},

{2, 2, 0, -10, -8, -10, 0, 2, 2},

{12, 12, 12, 18, 18, 18, 12, 12, 12},

{0, 0, -2, 4, 10, 4, -2, 0, 0},

{12, 18, 16, 22, 22, 22, 16, 18, 12},

{0, 0, 0, 2, 8, 2, 0, 0, 0},

{12, 14, 12, 18, 18, 18, 12, 14, 12},

{-2, 0, 4, 2, 6, 2, 4, 0, -2},

{12, 16, 14, 20, 20, 20, 14, 16, 12},

{0, 0, 0, 2, 4, 2, 0, 0, 0},

{6, 10, 8, 14, 14, 14, 8, 10, 6},

{4, 0, 8, 6, 10, 6, 8, 0, 4},


{4, 8, 6, 14, 12, 14, 6, 8, 4},

{0, 2, 4, 6, 6, 6, 4, 2, 0},

{8, 4, 8, 16, 8, 16, 8, 4, 8},

{0, 0, 2, 6, 6, 6, 2, 0, 0}

{-2, 10, 6, 14, 12, 14, 6, 10, -2}};


Horse: int[][]=

Soldier: int[][]=

{4, 8, 16, 12, 4, 12, 16, 8, 4},

{0, 3, 6, 9, 12, 9, 6, 3, 0},

{4, 10, 28, 16, 8, 16, 28, 10, 4},

{18, 36, 56, 80, 120, 80, 56, 36, 18}

{12, 14, 16, 20, 18, 20, 16, 14, 12},

{14, 26, 42, 60, 80, 60, 42, 26, 14}

{8, 24, 18, 24, 20, 24, 18, 24, 8},

{10, 20, 30, 34, 40, 34, 30, 20, 10},


{6, 16, 14, 18, 16, 18, 14, 16, 6},

{6, 12, 18, 18, 20, 18, 18, 12, 6},

{4, 12, 16, 14, 12, 14, 16, 12, 4},

{2, 0, 8, 0, 8, 0, 8, 0, 2},

{2, 6, 8, 6, 10, 6, 8, 6, 2},

{0, 0, -2, 0, 4, 0, -2, 0, 0},

{4, 2, 8, 8, 4, 8, 8, 2, 4},

{0, 0, 0, 0, 0, 0, 0, 0, 0},

{0, 2, 4, 4, -2, 4, 4, 2, 0},

{0, 0, 0, 0, 0, 0, 0, 0, 0},

{0, -4, 0, 0, 0, 0, 0, -4, 0}

{0, 0, 0, 0, 0, 0, 0, 0, 0}

3. Giải thuâ ̣t tı̀m kiế m α-β

 Là một giải thuật cho bài toán tìm kiếm có đối thủ dựa trên ý tưởng về
chiến lược tối ưu cho mỗi nước đi tiếp theo của mỗi bên.


 Có sử dụng tri thức bổ sung giúp cắt một bộ phận thuộc tập khả năng mà
không có khả năng tạo ra nước đi tốt hơn nước khác.

 Trong bài toán cờ tướng:
 Trạng thái ban đầu là trạng thái bàn cơ hai bên khi bắt đầu chơi.
 Các toán tử là các nước đi hợp lệ.
 Trạng thái kết thúc là tính thế khi một trong hai bên bị mất tướng.

III. Các phương pháp, tư liệu sử dụng từ bên ngoài.
 -Tư liệu tham khảo từ bài viết của Shi-Jim Yen, Jar-hang Chen,Tai-Ning
Yang, Shun-Chin Hsu (Taipei, Taiwan);
( /> Bảng đánh giá giá trị ban đầu của các quân


 Bảng đánh giá giá trị theo vị trí của từng quân

 Hàm lượng giá của chương trình sử dụng ý tưởng của tài liệu đã nên
đó là sử dụng các giá trị vị trí và chỉ số của quân mà đánh giá giá trị
ước lượng của thế cờ
 Ngoài ra các thư viện sử dụng trong chương trình gồm có:
 Các gói thư viện chuẩn do java cung cấp.


IV. Những vấn đề khó khăn gặp phải.
 Trong thời gian chấp nhận được, thuật toán cắt tỉa chỉ có độ sâu tối đa thấp
(<=4).
 Chương trình sử dụng quá nhiều bộ nhớ RAM (> 700MB)
 Sử dụng hàm lượng giá chưa tốt dẫn đến chất lượng các nước đánh của máy
tính chưa cao.
 Vấn đề đọc ghi dữ liệu đồng thời (Concurrent Modification).

 Vấn đề khi chạy đa luồng do chưa sử dụng tốt việc chia công việc cho các
luồng và phải phụ thuộc máy ảo Java xử lý với luồng.

V. Phương pháp giải quyết
 Sử dụng cấu trúc dữ liệu hàng đợi ưu tiên để sắp xếp các trạng thái bàn cờ
theo giá trị ước lượng tại mỗi độ sâu trước khi tìm kiếm ở độ sâu thấp hơn.
 Tối ưu bộ nhớ thông qua việc : không tạo ra bộ nhớ mới để lưu trữ cả trạng
thái của bàn cờ mà chỉ lưu trữ vết thay đổi của trạng thái bàn cờ mức hiện tại
so với mức cha.
 Tăng tốc độ chương trình bằng cách tính giá trị ước lượng của thế cờ ngay tại
lúc thay đổi sang thế cờ khác mà không phải tính tất cả tại lúc so sánh.
 Hàm lượng giá có sử dụng việc tăng giá trị ước lượng hơn khi là nước chiếu
và khi một nước cờ có khả năng bắt quân đối thủ.

VI. Đánh giá về chương trình


 Ưu điểm:
 Đã có sự thông minh cơ bản của trò chơi cờ tướng.
 Với độ sâu cắt tỉa là 6 chương trình đủ thông minh để chơi thắng
người chơi có trình độ trung bình.
 Hoàn toàn có thể chơi với người chơi và không gặp bug.
 Nhược điểm:
 Độ sâu của cắt tỉa chưa bằng với phần lớn các chương trình đánh cờ
tướng hiện tại.
 Cấu trúc lưu trữ của dữ liệu trong chương trình chưa tối ưu nên
chương trình vẫn còn yêu cầu nhiều bộ nhớ.
 Hàm ước lượng trạng thái đang còn cơ bản
 Một số kết quả đạt được của chương trình
Độ sâu


Thời gian (ms)

Bộ nhớ (MB)

1

5

60

2

15

75

3

16

80

4

94

85

5


229

90

6

896

450

7

4260

550


VII. Hướng phát triển
 Tối ưu hàm lượng giá.
 Tạo cơ sở dữ liệu cho các nước đi đầu.
 Tăng tầm quan trọng của các thế cờ tại các nước cuối.
 Sử dụng cách thức lưu trữ trạng thái bàn cờ khác (qua giá trị số ).
 Thực hiện việc tính toán song song hàm cắt tỉa .