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 đấ
- 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
- M
ụ
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 ...]