Chào đồng chí Dương Trần,
Theo tớ biết, có nhiều cách tiếp cận để giải quyết bài toán cờ ca rô hay cờ nói chung.
Ở đây tớ nêu ra 2 cách:
- Xây dựng một hệ thống dựa trên tập luật (giống như hệ chuyên gia).
- Sử dụng các giải thuật tìm kiếm để tìm ra nước đi tối ưu (Duyệt với một độ sâu nào
đó)
Theo cách tiếp cận thứ nhất, ta phải xây dựng được tập luật, mỗi luật được biểu diễn
dưới dạng sau:
If(State = A) then Move(A,x,B)
- Trong đó A là trạng thái hiện tại của bàn cờ
- Move(A,x,B) thực hiện nước đi tốt nhất x (dựa trên kinh nghiệm) tại trạng thái A
của bàn cờ; B là trạng thái tiếp theo của bàn cờ sau khi thực hiện nước đi x
Tuy nhiên, cách tiếp cận này gặp phải một số vấn đề sau:
- Số trạng thái của bàn cờ quá lớn, do đó không thể liệt kê hoặc lưu trữ được toàn bộ
tập luật
- Việc xác định nước đi tốt nhất tại trạng thái cho trước của bàn cờ là rất khó
Do đó, người ta thường giải quyết bài toán theo cách tiếp cận thứ 2: coi bài toán chơi
cờ như trường hợp đặc biệt của lớp các bài toán tìm kiếm
Biểu diễn không gian trạng thái bàn cờ
Như đã nói ở trên, bài toán cờ ca rô có thể mô tả như một trường hợp đặc biệt của lớp
các bài toán tìm kiếm. Đối với lớp các bài toán này, giải thuật tìm kiếm sẽ duyệt trên
không gian trạng thái của bài toán, bắt đầu từ trạng thái khởi đầu cho đến khi tìm
được trạng thái biểu diễn lời giải. Nếu ta mô phỏng không gian trạng thái của bàn toán
như một cây (tree) thì giải thuật tìm kiếm sẽ bắt đầu từ gốc, theo một "strategy" nào
đó, duyệt trên các node trung gian cho đến khi tìm được lời giải trên node lá của cây.
Như vậy, vấn đề đầu tiên cần phải giải quyết là biều diễn không gian trạng thái của
bàn cờ như thế nào. Với cờ ca rô, bạn có thể đơn giản biểu diễn bàn cờ như 1 mảng 2
chiều, phần tử của mảng mang giá trị 0 nếu ô trống, 1 nếu ô chứa nước đi của bạn, -1
nếu ô chứa nước đi của đối thủ. Tuy nhiên, đối với một số loại cờ khác như cờ vua, cờ
tướng thì việc biêu diễn sẽ phức tạp hơn. Trạng thái của bàn cờ phải mô tả được tất cả
các khả năng có thể có của bàn cờ.

Bước tiếp theo là mô tả tất cả cái nước đi có thể đối với một trạng thái bất kỳ của bạn
cờ. Tại mỗi trạng thái của bàn cờ, bạn (hay đối thủ có thể thực hiện được một số nước
đi hợp lệ. Khi thực hiện các nước đi này, bàn cờ sẽ chuyển sang trạng thái mới. Một
lần đi có thể biểu diễn như sau:
If(State==A, move(A,x,B)) then State = B
Trong đó:
A là trạng thái hiện tại
move(A,x,B) là thực hiện nước đi x tại trạng thái A
B là trạng thái bàn cờ sau đi đi nước đi x
Khi đã biểu diễn được trạng thái của bàn cờ và các nước đi hợp lệ ứng với từng trạng
thái, không gian trạng thái của bàn cờ có thể được biểu diễn như một cây, với node


gốc (roof) là bàn cờ ca rô lúc ban đầu (không có quân cờ nào), một node B ở mức i
(level i-child) đuợc xây dựng từ một node A ở mức i - 1 (parent) ứng với một nước đi
hợp lệ move(A,x,B). Cuối cùng là các node lá. Các node này tương ứng với các trạng
thái kết thúc của ván cờ (bạn thua, thắng, hoặc hòa). Lời giải cho bài toán chính là các
node lá ứng với trạng thái "thắng" (mức ưu tiên 1) hoặc hòa (ưu tiên 2).
Đến đây, ta có thể thấy giải thuật này chính là một trường hợp của bài toán tìm kiếm.
Nếu bạn có một máy tính với tài nguyên "đủ lớn", bạn có thể tìm ra trình tự các nước
đi (đuờng đi từ gốc tới lá) sao cho kết thúc của ván cờ là "tốt nhất" với bạn.
Tuy nhiên, các thuật toán cờ cũng có nhiều điểm khác biệt. Ví dụ:
- Bạn không thể biết trước được nước đi của đối thủ
- Kích thước không gian trạng thái bàn cờ là rất lớn (khoảng 15 mũ 80 nodes với cờ
vua, 200 mũ 300 với cờ vây,...). Đặc biệt với những loại cờ đơn giản như cờ ca rô, cờ
vây thì không gian trạng thái thường lớn hơn do không có nhiều ràng buộc giữa các
quân cờ.
- Việc đánh giá so sánh giữa các trạng thái bàn cờ (hay các nước đi) là rất khó (một
nước đi có thể có lợi tại thời điềm hiện tại nhưng chưa chắc đã tốt ở các nước tiếp
theo)

Do vậy, đối với các loại cờ thì cần các kỹ thuật tìm kiếm khác thay vì các phương
pháp tìm kiếm thông thường.
Hàm lượng giá và các giải thuật min-max, anpha-beta
Như đã nói ở trên, vì không gian trạng thái của bàn cờ là rất lớn và đặc tính đối kháng
trong trò chơi, ta không thể sử dụng các phương pháp tìm kiếm thông thường (e.g. vét
cạn) để tìm kiếm lời giải tối ưu. Các giải thuật áp dụng trong các trò cờ chỉ có thể tìm
kiếm trong một không gian con các trạng thái của bàn cờ để cho "lời giải tốt tương
đối" ứng với thời gian cho trước (2 phút với cờ vua). Giải pháp được thường được sử
dụng trong cờ ca rô cũng như các loại cờ khác là tìm kiếm tới một độ sâu định trước
(search up to certain level) hoặc tìm kiếm cho tới khi đạt tới thời gian cho phép (a
wellknown methode: iterative deepening search).
Một vấn đề đặt ra ở đây là: làm sao có thể biết là trạng thái bàn cờ tìm được là tốt, làm
sao so sánh giữa các trạng thái bàn cờ? Nói một cách khác là sao lượng giá trạng thái
bàn cờ như thế nào. Bạn có thể nói: rất dễ, chỉ việc cho mỗi trạng thái của bàn cờ một
giá trị! Nhưng có 2 vấn đề phát sinh là:
1. Không thể liệt kê cũng như đánh giá hết các trạng thái bàn cờ
2. Việc đánh giá này cũng không dễ dàng
Đây là vấn đề khó nhất gặp phải khi thiết kế một chương trình đánh cờ. Nó cũng đúng
với người chơi cờ: Người chơi cờ giỏi là người có thể đánh giá thế cờ tốt hơn người
khác!
Một giải pháp là dùng một hàm lượng giá (hay hàm mục tiêu) để lượng giá trạng thái
của bàn cờ. Với hàm mục tiêu này mỗi trạng của bàn cờ sẽ tương ứng với một giá trị
thực. Ví dụ, trong cờ vua, người ta có thể lượng giá bạn cờ bàng tổng (có trọng số)
của các quân đen - tổng số các quân trắng. Việc lựa chọn các hàm mục tiêu như thế
nào là tùy thưộc vào sự "nhạy cảm" của bạn. Trên thực tế, trong các trò cờ nổi tiếng
như Deepblue, C3000, người ta dùng nhiều kỹ thuật khác nhau; eg. Machine learning,


Artificial Neural Nets để tính giá trị cho các trạng thái của bàn cờ.
Sau khi đã xây dựng được hàm mục tiêu, mỗi node trên cây trạng thái sẽ có một giá trị

nào đó. Vấn đề bây giờ là tìm một nút lá với giá trị "lớn nhất có thể" và tìm kiếm một
đường đi từ nút gốc tới nút lá đó.
Vì tính chất đối kháng của trò chơi, bạn không thể biết trước nước đi của đối thủ, và
việc tìm kiếm cũng hơi khác một chút. Giải thuật min-max được dùng phổ biết cho
hầu hết các chương trình cờ (thậm chí cả Deepblue). Ý tường của giải thuật này là:
1. Gán người chơi nhãn MIN, Máy nhãn MAX
3. Xây dựng cây tới một độ sâu nào đó, trên mỗi level của cây, gán MAX nếu MAX
đi, MIN nếu MIN đi.
4. Tính toán giá trị cho các nút lá (dùng hàm lượng giá),
5. Sau đó tính ngược từ dưới lên giá trị của các nút trung gian+nút gốc theo (1)
SCORE(parent-MAX) = MAX (SCORE(all children))
(2) SCORE(parent-MIN) = MIN(SCORE(all children))
Theo cách này, tới lân máy đi, máy sẽ chọn đi node có giá trị lớn nhất, khi lân người
đi, anh ta có xu hướng chọn node có giá trị nhỏ nhất (để giảm thiệt hại). Kết quả là,
cuối cùng trạng thái bàn có 'giá trị đối kháng" tốt nhất.
Thuật toán apha-beta có được trình bày dưới đây:
Initialise depthbound;
Minimax (board, depth) =
IF depth = depthbound
THEN return static_evaluation(board);
ELSE IF maximizing_level(depth)
THEN FOR EACH child child of board
compute Minimax(child, depth+1);
return maximum over all children;
ELSE IF minimizing_level(depth)
THEN FOR EACH child child of board
compute Minimax(child, depth+1);
return minimum over all children;
Call: Minimax(current_board, 0)
Ngoài ra, để làm giảm các nhánh duyệt người ta còn áp dụng nhiều ký thuật khác như:

constraint processing, Backtracking, Backjumping, Backmarking, ..., Một thuật toán
khác được cải tiến từ thuật toán MIN-MAX là thuật toán Alpha-Beta.
Để tìm hiểu thêm, bạn có thể tham khảo "Trí tuệ nhân tạo" của Nguyễn Thanh Thủy.
Chúc thành công!