- Tham gia
- 20/4/2008
- Bài viết
- 9.433
CỜ TƯỚNG - PHIÊN BẢN ĐẦU TIÊN (VERY SIMPLE CHINESE CHESS PROGRAM - VSCCP 1.0)
Tác giả: PHẠM HỒNG NGUYÊN
I. Giới thiệu
Trò chơi Cờ Tướng (tên phiên âm Trung Quốc XiangQi, tên tiếng Anh Chinese Chess) là một minh hoạ rất tốt cho bài toán tìm kiếm trên cây trò chơi và áp dụng thuật toán AlphaBeta trên cây này như thế nào. Đây là một trò chơi thú vị và tương đối phổ biến ở Việt nam, châu Á cũng như trên toàn thế giới. Nó tạo cảm giác dường như máy tính có thể suy nghĩ và đọ sức với con người (thực tế cho đến nay nó vẫn chỉ tính toán mà thôi). Cờ Tướng là loại cờ có độ phức tạp và rất nhiều mặt tương đương với cờ Vua.
Trong phần này, chúng tôi sẽ giới thiệu với bạn những kiến thức cơ bản nhất về một chương trình chơi cờ phải như thế nào. Các chương trình mẫu VSCCP (Very Simple Chinese Chess Program - Chương trình Cờ Tướng rất đơn giản) cũng hết sức đơn giản và có đầy đủ trong các phụ lục.
II. Viết chương trình chơi cờ VSCCP 1.0
1. Biểu diễn bàn cờ và quân cờ
Bàn cờ trong trò chơi cờ Tướng là một bảng chữ nhật bao gồm 9 đường dọc và 10 đường ngang. Các quân cờ chia làm hai bên đứng tại các giao điểm của các đường. Bàn cờ và vị trí khởi đầu các quân cờ như hình 2.1. Cách đơn giản nhất để biểu diễn một bàn cờ trong máy tính là ta dùng một mảng hai chiều, kích thước 9 x 10:
piece: array[1..10, 1..9] of byte
Mảng trên hoạt động tốt nhưng có cái bất tiện là ta phải dùng tới hai chỉ số để truy cập vào mảng (ví dụ vị trí quân Pháo góc trên bên trái (cột 2, dòng 3) là piece[3, 2]). Một cải tiến nhỏ là ta dùng mảng một chiều như sau:
piece: array[1..90] of byte
Truy nhập đến vị trí quân Pháo góc trên bên trái lúc này là piece[20].
Các ô của mảng sẽ chứa những giá trị khác nhau cho biết đó là quân cờ gì. Mỗi quân cờ sẽ được gán một mã số khác nhau như bảng dưới đây. Các chỗ trống (không có quân cờ) sẽ được điền kí hiệu trống (EMPTY):
Ngoài mục đích gán mỗi quân cờ một mã số để phân biệt, mã này còn giúp ta ước lượng sơ bộ tầm quan trọng của quân cờ đó.
Như vậy, lúc khởi đầu, các ô trong mảng sẽ được gán các giá trị quân cờ nhờ khai báo const (trong Pascal) như dưới, trong đó BOARD_SIZE (kích thước bàn cờ = 90) là một hằng số đã được định nghĩa trước đó:
Đến đây, bàn cờ còn chưa có thông tin để phân biệt một quân cờ là của bên nào. Ta có thể cải tiến thay cho kiểu byte của mảng piece là một bản ghi nhằm lưu thêm các thông tin này. Chúng tôi xin giới thiệu một phương pháp đơn giản là dùng thêm một mảng nữa - mảng color, để lưu các thông tin về bên. Hai bên được gán kí hiệu và mã như bảng dưới. Những chỗ trống sẽ dùng cùng kí hiệu trống EMPTY.
Ta lại có thông tin về bên được khai báo khởi đầu tương tự:
Để biết bên nào tới lượt đi, ta dùng một biến toàn cục side chứa một trong hai giá trị LIGHT và DARK. Một biến toàn cục khác xside sẽ có sẵn giá trị ngược với side để tiện tính toán (ví dụ nếu side = LIGHT thì xside = DARK). Khi tới phiên đối phương đi, ta cần đảo ngược giá trị trong cả side và xside bằng các lệnh như sau (chú ý là LIGHT+DARK = 3):
side := xside; xside := 3 - xside;
Ngoài ra, ta còn khai báo biến computerside cũng chỉ có một trong hai giá trị LIGHT và DARK nhằm cho biết bên nào là máy. Để hiện bàn cờ, phương pháp đơn giản nhất là hiện ở chế độ text (văn bản). Tuy cách này trông xấu và thường không dùng trong các chương trình có trên thị trường nhưng nó có các ưu điểm nổi trội sau:
Ta sẽ hiện bàn cờ ở dạng như hình 2.3. Chú ý cách đánh kí hiệu các vị trí trong bàn cờ bằng chữ và số giống như bàn cờ Vua.
Để hiện một quân cờ, ta viết một thủ tục DrawCell với tham số là vị trí bàn cờ. Ngoài ra, nó còn một tham số nữa cho biết sẽ hiện mầu nền của quân cờ với mầu bình thường NORMAL (sẽ có nền đen) hay mầu khác SELECT (sẽ có nền xanh sẫm) để thể hiện quân cờ đó được chọn (phục vụ cho chọn và đi quân của người chơi).
procedure DrawCell(pos, mode: byte);
Như vậy, để hiện toàn bộ bàn cờ ta chỉ cần gọi một vòng lặp for là xong:
for i := 1 to BOARD_SIZE do DrawCell(i, NORMAL);
2. Sinh nước đi
Một trong những việc quan trọng nhất để máy tính có thể chơi được cờ là phải chỉ cho nó biết mọi nước đi có thể đi được từ một thế cờ. Máy sẽ tính toán để chọn nước đi có lợi nhất cho nó. Các yêu cầu chính đối với một thủ tục sinh nước đi là:
Một nước đi có hai giá trị cần quan tâm. Đó là điểm xuất phát (from) và điểm đến (dest). Ta sẽ khai báo một cấu trúc move như sau để dùng những nơi cần đến dữ liệu nước đi.
type
move = record { Định nghĩa cấu trúc nước đi }
from, dest: byte;
end;
Kiểm tra giới hạn bàn cờ
Ví dụ có một quân Xe nằm ở ô số 84 (trong mảng piece). Bây giờ ta sẽ sinh thử một nước đi sang trái một ô cho nó. Nước đi sang trái một ô được chuyển thành ô số 83 là một vị trí cùng hàng với ô xuất phát nên được chấp nhận. Một nước đi khác cần phải xem xét là sang trái ba ô - ô 81. Ô 81 tuy có trong bàn cờ nhưng khác hàng nên không được chấp nhận. Như vậy, muốn biết ô của nước đi sang trái có được phép không ta phải kiểm tra xem nó có cùng hàng với ô xuất phát không. Việc kiểm tra thực hiện bằng cách chia cho 9 (kích thước của một dòng) và lấy phần nguyên (trước đó lại phải chuyển thứ tự ô về gốc là 0 bằng cách trừ đi 1). Ta thấy ((83-1) div 9) = ((84-1) div 9) nên ô 83 được chấp nhận; trong khi đó do ((81-1) div 9) <> ((84-1) div 9) nên kết luận là nước đi đến ô 81 không hợp lệ (hình 2.5).
Các nước đi vừa sinh ra sẽ được đưa vào danh sách nước đi nhờ gọi thủ tục Gen_push. Thủ tục này có hai tham số là vị trí xuất phát của quân cờ sẽ đi và nơi đến dest của quân cờ đó.
Dưới đây là đoạn chương trình dùng để sinh những nước đi sang trái của một quân Xe, trong đó x là vị trí của quân Xe này .
Việc sinh những nước đi theo chiều khác cũng tương tự (ví dụ để sinh nước đi theo chiều đứng ta chỉ cần cộng hoặc trừ một bội số của 9) nhưng điều kiện kiểm tra sẽ khác nhau. Như vậy, chương trình sinh nước đi Gen có dạng như sau:
for Xét lần lượt từng quân cờ bên hiện tại do
case quâncờ of
Xe: begin
while Xét lần lượt tất cả các ô từ bên phải Xe cho đến lề trái bàn cờ do
begin
if (ô đang xét là ô trống) or (ô đang xét chứa quân đối phương) then
gen_push(vị trí của Xe, vị trí ô đang xét)
if ô đang xét không trống then break;
end;
while Xét lần lượt tất cả các ô từ bên trái Xe cho đến lề phải bàn cờ do
...
while Xét lần lượt tất cả các ô từ bên trên Xe cho đến lề trên bàn cờ do
...
while Xét lần lượt tất cả các ô từ bên dưới Xe cho đến lề dưới bàn cờ do
...
end; { Xong quân Xe }
Pháo:
...
Phương pháp này có nhược điểm là chương trình phải viết phức tạp, cồng kềnh, khó tìm lỗi nhưng khá nhanh.
Trong chương trình mẫu VSCCP, chúng tôi giới thiệu một kĩ thuật khác có tên gọi là "hộp thư" (mail box - do các bảng của nó có dạng các hộp phân thư). Mục đích chính của kĩ thuật này là nhằm giảm bớt các phép kiểm tra vượt giới hạn bàn cờ và làm đơn giản chương trình. Mấu chốt là thay cho bàn cờ có kích thước bình thường 9x10 = 90, ta dùng một bàn cờ mở rộng, mỗi chiều có thêm 2 đường nữa (bàn cờ mới có kích thước 13x14 = 182). Các ô ứng với các đường bao mở rộng đều có giá trị -1, tức là các giá trị báo vượt biên. Các nước đi trên bàn cờ 9x10 được chuyển tương ứng sang bàn cờ này. Nếu một nước đi được sinh ra lại rơi vào một trong hai đường bao thì có nghĩa nó đã rơi ra ngoài bàn cờ rồi, phải bỏ đi và ngừng sinh nước về phía đó. Sở dĩ có đến hai đường biên (chứ không phải một) do quân Mã và Tượng có thể nhẩy xa đến hai ô (hình 2.6).
Việc chuyển đổi toạ độ thực hiện nhờ hai mảng. Mảng mailbox90 dùng để chuyển từ toạ độ bàn cờ thường sang toạ độ bàn cờ mới. Mảng ứng với bàn cờ mới - mailbox182 dùng để kiểm tra các nước đi vượt quá đường biên và dữ liệu để chuyển trở lại toạ độ bình thường.
Ví dụ, nếu vị trí quân Xe nằm ở ô số 84 (trong mảng piece) như hình 2.5, thì khi đổi sang bàn cờ mở rộng sẽ thành vị trí mailbox90[84] = 148. Có nghĩa là nó ứng với ô thứ 148 của mảng mailbox182. Bây giờ ta sẽ sinh thử một nước đi sang trái một ô cho quân Xe này. Việc sinh và kiểm tra sẽ được thực hiện trong bàn cờ mở rộng, nước đi mới là ô số 148 - 1 = 147. Do mailbox182[147] = 83 ¹ -1 nên nước đi này được chấp nhận. Số 83 cho biết kết quả sang trái một ô là vị trí 83 trong bàn cờ bình thường. Tuy nhiên, nước đi sang trái ba ô, có số 148 - 3 = 145 và mailbox182[145] = -1 cho biết đó là một nước đi không hợp lệ.
Chương trình cũng cần kiểm tra số nước đi tối đa theo một hướng của quân cờ đang xét. Chỉ có quân Pháo và Xe có thể đi đến 9 nước đi, còn các quân khác có nhiều nhất là 1.
Việc đi một quân sang vị trí mới thực chất là ta đã thay đổi toạ độ của nó bằng cách cộng với một hằng số (dương hoặc âm). Ở trên ta đã thấy để quân Xe sang trái một nước ta đã phải cộng vị trí hiện tại với -1. Để sinh một ô mới theo hàng dọc, ta phải cộng với +13 hoặc -13 (chú ý, việc sinh nước và kiểm tra hợp lệ đều dựa vào mảng mailbox182 nên giá trị 13 là kích thước một dòng của mảng này). Để sinh các nước đi chéo ta phải cộng trừ với một hằng số khác. Ta nên lưu các hằng số này vào mảng offset có 2 chiều. Một chiều dựa vào loại quân cờ nên chỉ số được đánh từ 1 đến 7. Chiều còn lại là số hướng đi tối đa của một quân cờ.
Quân cờ có nhiều hướng nhất là quân Mã có tới 8 hướng nên chiều này được khai báo chỉ số từ 1 đến 8. Các quân cờ có số hướng ít hơn sẽ được điền 0 vào phần thừa. Chú ý là nước đi quân Tốt của hai bên khác nhau hướng tiến. Để tiết kiệm ta chỉ lưu nước tiến của Tốt đen, còn nước tiến của Tốt trắng chỉ đơn giản lấy ngược dấu.
Kiểm tra vị trí được phép đến
Việc chuyển toạ độ từ bàn cờ thường sang bàn cờ mở rộng chỉ giúp ta loại bỏ được các nước vượt quá biên. Ta còn phải kiểm tra một số giới hạn khác. Ví dụ như Tướng và Sĩ không thể đi ra ngoài cung, Tượng chỉ được phép ở 7 điểm cố định phía bên mình, Tốt chỉ được phép tung hoành trên đất đối phương, còn phía bên mình cũng bị giới hạn ngặt nghèo một số ô... Để thực hiện những phép kiểm tra này, ta dùng một mảng là legalmove ứng với từng ô trên bàn cờ sẽ cung cấp các thông tin này. Để kiểm tra một quân cờ có được phép ở đó không, ta dùng một mặt nạ bít Maskpiece mà tuỳ theo từng quân sẽ có giá trị khác nhau. Nếu ở ô cần kiểm tra có bit trùng với mặt nạ này được đặt là 1 thì quân cờ đó được phép đến ô đấy.
Ví dụ, ô số 3 có giá trị legalmove[3] = 5 (chuyển thành số nhị phân là 00000101) cho biết các quân cờ được phép đi đến đó là Tượng, Xe, Pháo, Mã.
Ngoài ra, ta còn phải kiểm tra nước bị cản (đối với Tượng và Mã) và xử lí cách ăn quân của quân Pháo như một trường hợp đặc biệt. Như vậy, tổng thể sinh các nước đi cho một quân cờ có dạng như sau:
Một vấn đề nữa là luật hai Tướng không được đối mặt trực tiếp với nhau. Việc kiểm tra được thực hiện nhờ hàm kingface. Hàm sẽ trả lại giá trị true nếu nước vừa đi gây hở mặt Tướng. Hàm này có thể được đặt trong thủ tục sinh nước Gen. Tuy nhiên đơn giản hơn, ta đặt nó trong thủ tục gen_push, nếu hở mặt Tướng thủ tục này sẽ không đưa nước đi đó vào danh sách các nước đi.
3. Đánh giá một thế cờ
Đánh giá một thế cờ là một trong những nhiệm vụ quyết định chương trình chơi cờ của bạn có là "cao thủ" hay không. Căn cứ vào một thế cờ máy sẽ gán cho nó một điểm số (lượng giá tĩnh) để đánh giá độ tốt - xấu. Nhờ điểm này máy mới có thể so sánh các thế cờ với nhau và biết chọn nước đi tốt nhất. Đây là một nhiệm vụ rất khó khăn và phức tạp do không tồn tại một thuật toán tổng quát và thống nhất nào để tính điểm cả. Điểm của một thế cờ dựa trên rất nhiều yếu tố mà khó có thể số hoá hết được như phụ thuộc vào số lượng và giá trị các quân cờ hiện tại, phụ thuộc vào tính h.ãm, tính biến, thế công, thế thủ của từng quân cờ cũng như cả cục diện trận đấu. Ví dụ, một cặp Mã giao chân, có thể sát cánh tiến quân và tựa lưng phòng thủ thường có giá hơn hai Mã đứng rời. Nhưng cũng có lúc hai Mã đứng rời lại tốt hơn hai Mã giao chân khi Mã này lại cản Mã kia trong một thế trận nào đó. Ta cũng biết rằng, "lạc nước hai Xe đành bỏ phí, gặp thời một Tốt cũng thành công", thế nhưng số hoá điều này qua hàm lượng giá quả là một điều khó quá sức.
Chúng ta bắt đầu với việc công nhận các giả thuyết sau:
Cách làm này đã bỏ qua mất những nghệ thuật, chiến lược chơi cờ (mà đó là những điểm để đánh giá một người là giỏi cờ hay không). Các quân cờ được triển khai không theo một chiến lược chung nào hết (vô định). Nó còn tạo cảm giác như cờ "vồ", nghĩa là chỉ nhằm nhằm sơ hở của đối phương là "ăn" ngay mà không cần biết đến hậu quả (điều này không hẳn đúng, lí do sẽ trình bầy dưới). Tuy nhiên phương pháp tính điểm này có những ưu điểm sau:
Bạn cũng có thể theo bất kì thang điểm nào khác tuỳ theo hiểu biết và sở thích của mình. Ví dụ như trong làng cờ Việt nam thường cho điểm các quân hơi khác (xem bài đọc dưới): Tốt - 1 (2 nếu đã qua sông), Sĩ - 2, Tượng - 2.5, Mã - 4.5, Pháo - 5, Xe - 10.
Trong chương trình cờ của chúng ta, điểm cụ thể của từng quân cờ là các số nguyên 10, 20, 20, 40, 45 và 90. Ta dùng một mảng piecevalue để lưu điểm từng quân cờ. Cho điểm như vậy không những vẫn giữ nguyên được tương quan và tránh dùng số thực (tính chậm) mà ta còn có một khoảng cách hợp lí giữa các điểm để sau này dễ dàng thêm những điểm bổ xung "thưởng" hoặc "phạt", tức là những điểm căn cứ vào những yếu tố khác (ví dụ cùng là Pháo nhưng lúc chỉ được 40 điểm do ở vị trí "bí", lúc khác lại có thể đến 85 do ở vị trí Pháo trống và đang đe doạ Pháo lồng).
Trong bàn cờ, quân Tướng là quân quan trọng nhất, dù mất mọi quân hoặc đạt được thế cờ nào đi nữa đều không được mất Tướng vì nó dẫn đến thua cờ. Do đó, Tướng thường được cho một điểm rất cao, cách biệt nhiều lần so với các quân khác, đảm bảo điểm tổng của các quân còn lại cùng đủ mọi loại "thưởng", "thêm" đều không bằng được Tướng. Trong chương trình, ta cho nó 1000 điểm.
Hàm lượng giá thật đơn giản như sau (chú ý là ta chưa tăng điểm cho Tốt đã qua sông):
Vấn đề cải tiến hàm lượng giá sẽ được bàn riêng trong một chương phần sau.
Tham khảo kiến thức cờ Tướng
GIÁ TRỊ CỦA CÁC QUÂN CỜ
Khái niệm giá trị của các quân cờ không phải là mới đối với những người chơi cờ từ các thế kỷ trước. Từ lâu, làng cờ đã có câu nhận định sức mạnh của các quân chủ lực là "Xe 10, Pháo 7, Mã 3" hoặc đánh giá Xe là quân chủ lực mạnh nhất bằng câu "Nhất Xa sát vạn" hay đánh giá một Tốt qua hà, sức mạnh bằng nửa con Xe (nhất Tốt độ hà, bán Xa chi lực). Thế nhưng sự đánh giá nhận định này về sức mạnh của các quân không chính xác và cũng không đầy đủ. Do đó khái niệm giá trị của các quân cần được xác định rõ và hoàn chỉnh hơn. Thông thường, theo thời gian một ván cờ được chia thành ba giai đoạn: khai cuộc, trung cuộc và tàn cuộc. Trong ba giai đoạn này thì trung cuộc chiếm nhiều thời gian nhất và có ý nghĩa đến thắng thua nhiều nhất. Do đó các định giá quân cờ thường là cho giai đoạn này.
Chúng ta đã biết mỗi loại quân cờ hay mỗi binh chủng có đặc điểm, tính năng và tác dụng khác nhau nên sức mạnh của chúng cũng khác nhau, giá trị của chúng cũng không giống nhau. Ngay bản thân mỗi quân cờ cũng không phải lúc nào sức mạnh cũng giữ nguyên như cũ. Khi đứng ở vị trí tốt nó phát huy tính năng tác dụng tối đa khác hẳn với khi nó đứng ở vị trí xấu, không thể phát huy tính năng tác dụng được, hay chỉ phát huy ở mức rất hạn chế. Vậy điều trước tiên chúng ta phải thấy mỗi quân cờ có hai giá trị: giá trị vốn có và giá trị biến động. Giá trị vốn có thường được gọi là giá trị cơ bản (giá trị tĩnh), còn giá trị biến động được gọi là giá trị tương đối.
Các nhà nghiên cứu lí luận về cờ đã trao đổi thống nhất với nhau bảng giá trị cơ bản của các quân như sau:
Nếu lấy Tốt chưa qua sông làm chuẩn để xác định giá trị thì nó là quân kém năng lực nhất trên bàn cờ. Khi chưa qua sông nó chỉ kiểm soát hay khống chế mỗi một điểm trước mặt nó nên tạm cho nó có giá trị bằng 1. Khi Tốt qua sông, nó khống chế đến 2 hay 3 điểm trước mặt và bên cạnh (Tốt biên chỉ khống chế được 2). Bây giờ nó mang giá trị tương đối, phải thấy nó mạnh hơn lúc chưa qua sông nên giá trị lúc này của nó phải bằng 2.
Đối với Sĩ, Tượng là loại binh chủng phòng ngự, có nhiệm vụ chính là bảo vệ an toàn cho Tướng, đôi lúc chúng cũng trợ giúp các quân khác tấn công. Trong giai đoạn trung cuộc, Tốt đối phương qua sông đổi được một Sĩ hoặc một Tượng. Do đó người ta đánh giá Sĩ hoặc Tượng có giá trị bằng một Tốt đã qua sông, tức là bằng 2. Nhưng vì so sánh năng lực giữa Tượng và Sĩ thì thấy Tượng có phần đắc lực hơn nên định giá trị Sĩ là 2 thì Tượng phải là 2.5 mới công bằng.
Quân Mã trên bàn cờ có khả năng khống chế tối đa 8 điểm. Mỗi bước nhẩy của nó vượt được hai tuyến đường ngang hay dọc. So ra thì Mã cũng mạnh đấy nhưng tác chiến ở tầm cự ly ngắn mà thôi. Nếu so với hai Tốt đã qua sông cặp kè nhau thì năng lực của Mã không hơn bao nhiêu, do đó định giá trị cơ bản của Mã 4.5 là vừa. Nên nhớ hai Tốt cặp kè nhau khi qua sông phải có giá trị hơn 4.
Pháo là binh chủng tác chiến tầm xa rất có hiệu quả. Trên đường dọc, Pháo khống chế tối đa chỉ 8 điểm nhưng nó còn khống chế được cả đường ngang. Mặt khác Pháo là quân có tính cơ động cao, nó có thể đi một bước vượt đến 9 tuyến đường. Nhưng ở cự li gần, nhiều khi Pháo bất lực, không làm gì được để khống chế đối phương. Do đó so với Mã thì phải thấy mỗi quân có một sở trường riêng, sức mạnh của chúng coi như tương đương nhau. Thế nhưng trong giai đoạn trung cuộc quân số của hai bên tương đối còn nhiều, Mã đi lại dễ bị cản trở, còn Pháo thì nhanh nhẹn hơn, dễ phát huy năng lực hơn nên giá trị cơ bản của Pháo phải hơn Mã một chút và bằng 5.
Đối với Xe thì rõ ràng là một binh chủng cơ động mạnh nhất, nó khống chế ngang, dọc tối đa đến 17 điểm. Nếu đem Xe đổi lấy một Pháo và một Mã của đối phương thì thấy có phần thiệt thòi một chút, còn đối với hai Pháo thì có thể coi là cân bằng. Do đó giá trị cơ bản của Xe là 10.
Còn Tướng, bản thân nó không có sức mạnh gì nhiều dù đôi khi nó cũng làm được nhiệm vụ trợ giúp cho các quân phe nó tấn công có kết quả. Thế nhưng giá trị cơ bản của nó thì vô cùng to lớn, không một quân nào so sánh được. Tất cả các quân đều có thể đổi, có thể hi sinh nhưng riêng quân Tướng không thể đánh đổi mà cũng không thể hi sinh, vì mất Tướng là thua cờ. Do đó cũng không nên định giá trị cơ bản của Tướng vì định cũng chẳng có ý nghĩa gì.
(Sưu tầm)
4. Xử lí một nước đi "thử"
Trong quá trình tính toán tìm nước đi tốt nhất cho mình, máy thường phải đi "thử" một nước rồi lại tính tiếp. Sau đó nó sẽ phục hồi lại nước đi này. Do quá trình thử - phục hồi diễn ra rất nhanh và không hiện ra màn hình nên máy có thể thử hàng chục triệu lần mỗi khi đến lượt. Việc đi thử được thực hiện nhờ gọi hàm Makemove. Việc khôi phục nước đi này nhờ gọi thủ tục UnMakemove. Như vậy, chương trình thường xuyên thực hiện các câu lệnh dạng như sau:
Để tính được điểm của nước đi vừa thực hiện, nhiều khi máy lại phải thử đi tiếp một số nước nữa. Cứ như vậy các hàm Makemove và UnMakemove có thể được gọi lồng nhau rất sâu.
Khi đi thử, hàm Makemove phải lưu lại các thông tin cần thiết cho việc khôi phục lại sau này. Cách đơn giản nhất - lưu lại cả bàn cờ, không dùng được do các thông tin phải lưu quá nhiều. Thực chất, ta chỉ cần lưu các thông tin bao gồm: điểm xuất phát của quân cờ, điểm đến và loại quân cờ mà nó bắt được (nếu có). Để lưu các thông tin này, hàm sử dụng một mảng hist_dat các bản ghi chứa thông tin đó và con trỏ hdp được tổ chức như một ngăn xếp, nghĩa là nước đi sau cùng sẽ được phục hồi trước nhất.
Khi máy đi "thử" cho một bên một nước, thì nước sau sẽ đến lượt đối phương. Do đó hàm này cũng phải thay đổi giá trị các biến toàn cục về bên đi và đối thủ side và xside (việc thay đổi này là rất cần thiết để hàm Gen sinh nước đi cho đúng bên tới lượt). Nó cũng tăng biến ply (độ sâu) thêm 1 do đã dấn sâu thêm một bước trên cây tìm kiếm.
Hàm khôi phục nước đi thử UnMakemove có nhiệm vụ là làm mọi thứ ngược lại với hàm Makemove.
Một vấn đề nẩy sinh ở đây là nếu một quân Tướng bị bắt thì có cần phải đi "thử" nữa không. Nếu mất một Tướng, ván cờ sẽ kết thúc ngay lập tức, do đó không cần phải đi thử tiếp và nhánh cây trò chơi bị cắt tại đây dù vẫn chưa đạt đến độ sâu tìm kiếm tối đa. Còn nếu để máy đi thử tiếp, máy sẽ coi Tướng như một quân bình thường (dù có giá trị rất cao) và có thể đổi quân được - nó sẵn sàng để mất Tướng miễn là ngay sau đó ăn lại được Tướng đối phương (hình 2.8). Ta buộc phải cắt nhánh ở những nơi Tướng đã bị mất (hình 2.9).
Để xử lí những trường hợp này, ta cần chuyển Makemove thành một hàm boolean, trả lại giá trị true nếu nước đi thử này lại ăn được Tướng đối phương. Nếu ăn được, hiển nhiên điểm sẽ rất cao (được 1000 điểm) và không cần phải tính điểm cho những nhánh con nữa. Phần chương trình đi thử có dạng như sau:
Trong các câu lệnh trên có một chỗ hơi khó hiểu: tại sao ta lại cho nước ăn Tướng là 1000 - ply mà không phải đúng 1000? Biến ply là biến chỉ độ sâu tìm kiếm. Nếu không có biến này và trong trường hợp Tướng (bên máy tính) sắp bị bắt dù đi bất cứ nước nào thì mọi nhánh cây đều trả về điểm -1000. Do đó máy sẽ chọn nhánh đầu tiên để đi. Nước đi này có thể không hay do chấp nhận thua quá sớm như minh hoạ trên hình 2.10. Máy nên chọn nước thua lâu nhất để hi vọng đối phương đi "nhầm" (còn nước còn tát) và đúng tinh thần chiến đấu hơn.
5. Tìm kiếm AlphaBeta
Ta đã thấy chương trình mẫu của thủ tục AlphaBeta trong chương 1. Hàm AlphaBeta của VSCCP về cơ bản là giống như vậy, chỉ bỏ đi các tham số pos (thế cờ hiện tại - ở đây là giá trị của hai mảng piece và color) ở một số hàm do đã biến đổi trực tiếp vào các mảng toàn cục piece và color (nhờ các hàm Makemove và UnMakemove mà ta đã đề cập đến ở trên) nên chúng chính là thế cờ đang xét.
Nước đi tốt nhất (điểm cao nhất) ở độ sâu 0 (ply = 0) được lưu vào một biến toàn cục newmove. Máy sẽ chọn đi theo nước này.
Thủ tục gọi hàm AlphaBeta chỉ có các lệnh đơn giản như dưới. Nó gọi hàm này với các giá trị khởi đầu thích hợp để bắt đầu tìm kiếm.
6. Xử lí điều khiển của người chơi
Người chơi dùng bàn phím để điều khiển các quân bên mình khi đến lượt: dùng các phím mũi tên điều khiển con trỏ màn hình chạy đến quân cờ thích hợp, bấm phím Space hoặc Enter để chỉ mình sẽ đi quân này, chuyển con trỏ đến chỗ mới và vẫn bấm phím Space hoặc Enter để chỉ đó là chỗ đến. Người chơi có thể ngừng chơi giữa chừng bằng cách bấm phím ESC. Hàm xử lí điều khiển của người chơi GetHumanMove phải làm nhiệm vụ xử lí các phím điều khiển và trả về nước đi được chọn trong biến toàn cục newmove. Hàm cũng xử lí hai biến toàn cục x, y là toạ độ của con trỏ màn hình.
Một chương trình chơi cờ tốt còn phải giúp đỡ người chơi không đi sai luật. Các nước đi không hợp lệ (dù cố ý hay vô tình) đều cần được phát hiện và ngăn cấm. Cách làm thì có nhiều, ở đây chúng tôi giới thiệu phương pháp đơn giản nhất sử dụng hàm sẵn có: hàm Gen. Đầu tiên, ta gọi nó để sinh ra tất cả những nước đi có thể có từ thế cờ hiện tại với bên đi là người - đó chính là các nước đi hợp lệ. Mỗi khi người chơi chọn một nước, máy sẽ kiểm tra xem nó có trong danh sách các nước đi hợp lệ không. Nếu có, máy sẽ chấp nhận nước đi đó và thoát khỏi hàm GetHumanMove. Nếu không nó sẽ đòi người chơi phải chọn lại.
7. Cập nhật một nước đi
Sau khi "suy nghĩ" xong, đã đến lúc máy hoặc người phải thực hiện một nước đi thực sự. Chương trình phải cập nhật tất cả các thông tin cần thiết liên quan đến nước đi và hiện hình những thay đổi. Việc này được thực hiện nhờ gọi hàm UpdateNewMove. Nó có khá nhiều chỗ giống như hàm Makemove nhưng đơn giản hơn. Tham số quan trọng nhất mà nó quan tâm là nước đi được người hoặc máy chọn đi (đặt trong biến toàn cục newmove). Hàm cũng đồng thời sẽ kiểm tra tình trạng thắng cờ của bên vừa đi (ăn được Tướng đối phương) và trả về giá trị true nếu có một bên thắng. Vòng lặp chính sẽ căn cứ vào giá trị chân lí này để ngừng chơi.
8. Vòng lặp chính xử lí trò chơi
Sau khi có các hàm và thủ tục cần thiết, đã đến lúc ta liên kết chúng lại thành một trò chơi hấp dẫn. Trong phần thân chương trình chính, ta sẽ bắt gặp vòng lặp repeat. Vòng lặp này sẽ lặp mãi cho đến khi người chơi bấm phím ESC hoặc một bên thắng cờ. Tuỳ theo bên tới lượt nó sẽ gọi hàm xử lí thích hợp cho người hoặc máy. Sau khi nhận kết quả nó lo cập nhật các số liệu cần thiết, chuyển đối phương thành người đến lượt chơi.
9. Hiện thông tin
Đến đây, chương trình đã sẵn sàng đọ sức với bạn rồi đấy. Nhưng có thể bạn muốn biết thêm một vài số liệu như: thời gian mỗi lần máy nghĩ, hệ số phân nhánh của cây trò chơi, số thế cờ nó phải tính giá trị, khả năng xét thế cờ trung bình của máy là bao nhiêu cũng như nhiều số liệu khác. Việc quan sát các số liệu này còn giúp ta biết các cải tiến, sửa đổi về sau có thực sự hoạt động tốt không.
Cách lấy số liệu rất đơn giản, ta khai báo thêm một số biến toàn cục, thêm một số lệnh và cuối cùng in chúng ra màn hình ở chỗ thích hợp. Một số thông tin rất khó lấy chính xác, ta sẽ tạm bằng lòng với những số liệu gần đúng vậy.
Để biết mỗi lần nghĩ, máy đã lượng giá bao nhiêu thế cờ - một thông tin vô cùng quan trọng, ta khai báo một biến toàn cục evalcount và mỗi khi hàm Eval được gọi ta lại tăng giá trị của nó thêm một.
Ta cũng cần biết máy đã nghĩ trong bao lâu bằng cách khai báo các biến để tính thời gian. Thời gian được đo căn cứ vào số xung đồng hồ ở vị trí tuyệt đối $40:$6c trong bộ nhớ. Từ đây ta tính được thời gian tính bằng giây nhờ chia cho 18.23 - số xung trong mỗi giây. Khi biết được thời gian đã tiêu tốn có thể ước tính tốc độ lượng giá của máy bằng cách chia tổng số nút đã lượng giá cho thời gian tiêu tốn. Tất nhiên thời gian tiêu tốn này ngoài thời gian tiêu cho hàm lượng giá còn phải chi cho nhiều thứ khác như chạy các lệnh của hàm Gen, hàm AlphaBeta... nên cách làm này chỉ cho biết con số ước lượng mà thôi.
Để có được hệ số phân nhánh chính xác ta phải thống kê qua một số dữ liệu lớn. Chú ý rằng, số nhánh con được sinh ra mỗi lần gọi hàm Gen được đo bằng hiệu gen_end[ply]-gen_begin[ply]. Do đó hệ số phân nhánh được đo bằng cách lấy tổng các nhánh con này rồi chia cho số lần gọi hàm Gen (đo bằng biến gencount). Càng chơi lâu, các dữ liệu đo được càng lớn, kết quả sẽ càng chính xác.
Ngoài ra, bạn có thể còn muốn hiện chú giải nước vừa đi của máy để dễ theo dõi và xem xét điểm đạt được. Hãy chú ý cách tính các con số này (chú ý số 65 là mã của chữ cái A, 9 là số cột của một dòng bàn cờ).
Sau đây là những chỗ cần bổ xung để bạn có được các thông tin cần thiết. Những chỗ thêm, sửa từ nay về sau đều được đánh dấu bằng một mũi tên trắng cho dễ tìm.
10. Chạy thử
Bây giờ bạn hãy dịch và chạy thử chương trình trên (toàn bộ nguồn trong Phụ lục A). Cẩn thận nhé, ta chưa cài chức năng cho phép hoãn đi. Nếu đi nhầm bạn không thể đi lại. Chương trình máy tính lại không "nhầm lẫn" và với độ sâu ngầm định 4 (tức là nghĩ trước tới 4 nước đi) nó có khả năng đánh bại những người chơi có trình độ trung bình và chơi ẩu. Bạn hãy chịu khó suy nghĩ kĩ một chút, cẩn thận một chút thì có thể thắng được.
Hình 2.11 là thông tin in ra màn hình sau khi máy đi nước đầu tiên. Chương trình được chạy trên máy tính Pentium 166MHZ cài hệ điều hành Windows 98 và tìm kiếm đến độ sâu bằng 4. Các số liệu cho ta biết cây trò chơi có hệ số phân nhánh khoảng 41. Nếu lấy tròn là 40 thì ta có bd = 404 = 2560000 (tức là số nút lá của cây trò chơi có khoảng trên hai triệu rưởi nút). Đó chính là số nút ta phải xét nếu dùng phương pháp tìm kiếm Minimax. Với tốc độ trung bình xét được 55985 nút mỗi giây thì thời gian để xét hết bằng phương pháp này sẽ mất khoảng 2560000/55985 » 46 giây. Ở đây, ta đang dùng phương pháp tìm kiếm AlphaBeta, số nút phải xét chỉ còn 150480, nghĩa là ít hơn 17 lần và tổng thời gian phải bỏ ra chỉ 2.63 giây thay cho 46 giây. Nước đi Mã vào góc không được hay lắm - nhưng không sao, đây mới chỉ là phiên bản đầu tiên và độ sâu tìm kiếm còn hạn chế.
Nếu bạn chưa hề thực hiện một cải tiến nào mà chỉ nhập nguyên vẹn chương trình mẫu từ Phụ lục A và dịch chạy thì các giá trị về độ sâu, số nút lượng giá, hệ số phân nhánh, điểm đạt được, máy tính đi (trừ những thông số liên quan đến thời gian do tuỳ thuộc loại máy bạn có) phải y hệt như hình 2.11. Nếu có điều gì khác có nghĩa là đã có sai sót trong khi nhập chương trình nguồn, bạn cần thận trọng kiểm tra chương trình.
Tuỳ theo sức mạnh máy tính (và cả khả năng chờ đợi), bạn hãy thử tăng độ sâu tìm kiếm bằng cách sửa khai báo hằng số MAX_PLY từ 4 lên 5 hoặc 6. Đừng ham tăng nhiều. Do bùng nổ tổ hợp, nếu tăng nhiều bạn sẽ không chờ nổi đâu. Càng tăng độ sâu, bạn sẽ thấy chương trình chơi càng bớt hớ hênh và càng khó thắng đấy.
Bạn hãy thử kiểm nghiệm với độ sâu 5 xem sao. Các con số đều tăng khủng khiếp. Trên máy tính của tôi, thời gian xét nước đầu tiên đã tăng từ 2.63 tới 88 giây (tăng 33 lần). Số nút phải lượng giá là 5574794 nút (tăng 37 lần).
Nếu máy tính của bạn là loại tốt, hãy thử tiếp với độ sâu 6. Trên máy tính của tôi, thời gian máy "nghĩ" nước đầu tiên đã mất tới 1031 giây (hơn 17 phút, gần gấp 12 lần). Còn số nút phải lượng giá là 62929742 (gấp 11 lần). Bạn có thể thấy các con số cũng tăng rất nhiều nhưng dù sao chỉ tăng cỡ 11 lần. Hệ số phân nhánh được thống kê qua số lượng nhiều hơn đã tụt xuống còn 40.15. Nước được chọn đi hơi khác là B7C7 (có lẽ là nước tốt hơn). Còn độ sâu 7 tôi chỉ dám thử một lần vì thời gian tiêu tốn cho lần nghĩ nước đầu tiên mất đến... 3.7 giờ (trong khi qui định tổng cộng tất cả các nước của một đấu thủ chỉ được trong 1 giờ khi thi đấu).
Nếu ta cho rằng tăng một độ sâu thời gian tính toán chỉ dài thêm trung bình 10 lần thì chỉ cần đến độ sâu 11, các máy tính cỡ Pentium 166 MHZ sẽ mất đến... 4 năm để nghĩ nước đi đầu tiên (còn đến độ sâu 14 thì mất... 4223 năm).
Ta hãy thử ước mơ nếu có được chiếc máy tính mạnh và chuyên dụng (cho cờ) như Deep Blue thì tính được đến đâu. Loại máy lần đầu tiên thắng được Kasparov (năm 1997) có khả năng xét được trung bình 200 triệu (đôi khi lên đến 400 triệu) nước đi mỗi giây. Với độ sâu 7 (mà máy tính của tôi phải ỳ ạch trong 3.7 tiếng đồng hồ) sẽ được máy chiếu cố trong khoảng... 3 giây. Nếu được nghĩ một nước trong 3 phút (thời gian được phép trung bình cho một nước) thì độ sâu có thể đến được sẽ khoảng từ 8 đến 10 (nếu không có cải tiến đặc biệt).
Đến đây ta cũng có thể thấy, các chương trình cờ thuộc loại tốt nhất chạy trên các máy tính thông thường (loại PC và không gắn các mạch chuyên dụng) cũng chỉ tìm kiếm được đầy đủ đến độ sâu từ 5 đến 8 mà thôi (với giới hạn thời gian thi đấu bình thường). Dù vậy các cố gắng cải tiến bỏ ra cũng phải rất nhiều và rất lâu mới đạt được đến các độ sâu như vậy (bạn sẽ được nghiên cứu một vài cải tiến nhằm nâng độ sâu trong thời gian chơi hợp lí).
Chú ý là thông báo về tốc độ xét nước có thể rất khác nhau khi thay đổi độ sâu cực đại do hàm lượng giá dùng ở đây quá đơn giản, tỷ trọng thời gian không lớn so với các hàm khác và thời gian đo lại bao gồm tất cả mọi thứ nên các con số bị ảnh hưởng nhiều. Tuy nhiên, nếu với cùng độ sâu thì tốc độ hiện tương đối ổn định.
Toàn bộ mã nguồn chương trình cờ Tướng VSCCP phiên bản 1.0 cho trong phần Phụ lục A.
Tổng kết chương 2
Chương này đi sâu vào cách viết một chương trình cờ Tướng đơn giản. Những điểm quan trọng trong chương là các khai báo các loại dữ liệu khác nhau, cách biểu diễn một bàn cờ, các thủ tục và hàm cơ bản. Chú ý là các cấu trúc dữ liệu và các khai báo trong chương trình mẫu rất đơn giản nhưng cũng rất hiệu quả. Thủ tục Gen là lằng nhằng, phức tạp và dễ sai nhất.
Thuật toán AlphaBeta tuy giống như đã đề cập đến trong chương 1 nhưng đến chương này bạn cần phải hiểu nó thật sự. Bạn cũng cần nắm vững cách lấy số liệu cũng như hiểu các số liệu này để tiếp tục theo dõi các cải tiến chương trình trong các chương sau.
GỢI Ý PHÁT TRIỂN
+Thoái (lui): (/) gạch chéo. Ngược với tấn. Ví dụ M7/8 nghĩa là Mã cột 7 thoái lui sang cột 8.
+Bình (sang ngang): (-) dấu ngang (P2-5 nghĩa là Pháo 2 sang ngang đến cột 5).
Ví dụ: Các nước đi dẫn đến thế cờ như hình 2.12 (thế này có tên dài dòng là: Pháo đầu Xe tuần hà đối bình phong Mã cổ điển) được ghi như sau:
1. P2-5 M8.7
2. M2.3 C3.1
3. X1-2 X9-8
4. X2.4 M2.3
Tác giả: Phạm Hồng Nguyên
Tác giả: PHẠM HỒNG NGUYÊN
I. Giới thiệu
Trò chơi Cờ Tướng (tên phiên âm Trung Quốc XiangQi, tên tiếng Anh Chinese Chess) là một minh hoạ rất tốt cho bài toán tìm kiếm trên cây trò chơi và áp dụng thuật toán AlphaBeta trên cây này như thế nào. Đây là một trò chơi thú vị và tương đối phổ biến ở Việt nam, châu Á cũng như trên toàn thế giới. Nó tạo cảm giác dường như máy tính có thể suy nghĩ và đọ sức với con người (thực tế cho đến nay nó vẫn chỉ tính toán mà thôi). Cờ Tướng là loại cờ có độ phức tạp và rất nhiều mặt tương đương với cờ Vua.
Trong phần này, chúng tôi sẽ giới thiệu với bạn những kiến thức cơ bản nhất về một chương trình chơi cờ phải như thế nào. Các chương trình mẫu VSCCP (Very Simple Chinese Chess Program - Chương trình Cờ Tướng rất đơn giản) cũng hết sức đơn giản và có đầy đủ trong các phụ lục.
1. Biểu diễn bàn cờ và quân cờ
Bàn cờ trong trò chơi cờ Tướng là một bảng chữ nhật bao gồm 9 đường dọc và 10 đường ngang. Các quân cờ chia làm hai bên đứng tại các giao điểm của các đường. Bàn cờ và vị trí khởi đầu các quân cờ như hình 2.1. Cách đơn giản nhất để biểu diễn một bàn cờ trong máy tính là ta dùng một mảng hai chiều, kích thước 9 x 10:
piece: array[1..10, 1..9] of byte
Mảng trên hoạt động tốt nhưng có cái bất tiện là ta phải dùng tới hai chỉ số để truy cập vào mảng (ví dụ vị trí quân Pháo góc trên bên trái (cột 2, dòng 3) là piece[3, 2]). Một cải tiến nhỏ là ta dùng mảng một chiều như sau:
piece: array[1..90] of byte
Truy nhập đến vị trí quân Pháo góc trên bên trái lúc này là piece[20].
Các ô của mảng sẽ chứa những giá trị khác nhau cho biết đó là quân cờ gì. Mỗi quân cờ sẽ được gán một mã số khác nhau như bảng dưới đây. Các chỗ trống (không có quân cờ) sẽ được điền kí hiệu trống (EMPTY):
| Quân cờ | Kí hiệu | Giá trị |
| Tốt (Chốt) | PAWN | 1 |
| Sĩ | BISHOP | 2 |
| Tượng | ELEPHANT | 3 |
| Mã | KNIGHT | 4 |
| Pháo | CANNON | 5 |
| Xe | ROOK | 6 |
| Tướng | KING | 7 |
| Trống | EMPTY | 0 |
Ngoài mục đích gán mỗi quân cờ một mã số để phân biệt, mã này còn giúp ta ước lượng sơ bộ tầm quan trọng của quân cờ đó.
Như vậy, lúc khởi đầu, các ô trong mảng sẽ được gán các giá trị quân cờ nhờ khai báo const (trong Pascal) như dưới, trong đó BOARD_SIZE (kích thước bàn cờ = 90) là một hằng số đã được định nghĩa trước đó:
PHP:
piece: array[1..BOARD_SIZE] of byte =
( 6, 4, 3, 2, 7, 2, 3, 4, 6,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 5, 0, 0, 0, 0, 0, 5, 0,
1, 0, 1, 0, 1, 0, 1, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 0, 1, 0, 1, 0, 1, 0, 1,
0, 5, 0, 0, 0, 0, 0, 5, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
6, 4, 3, 2, 7, 2, 3, 4, 6);Đến đây, bàn cờ còn chưa có thông tin để phân biệt một quân cờ là của bên nào. Ta có thể cải tiến thay cho kiểu byte của mảng piece là một bản ghi nhằm lưu thêm các thông tin này. Chúng tôi xin giới thiệu một phương pháp đơn giản là dùng thêm một mảng nữa - mảng color, để lưu các thông tin về bên. Hai bên được gán kí hiệu và mã như bảng dưới. Những chỗ trống sẽ dùng cùng kí hiệu trống EMPTY.
| Bên | Kí hiệu | Giá trị |
| Đen | DARK | 1 |
| Trắng | LIGHT | 2 |
| Trống | EMPTY | 0 |
Ta lại có thông tin về bên được khai báo khởi đầu tương tự:
PHP:
color: array[1..BOARD_SIZE] of byte =
(1, 1, 1, 1, 1, 1, 1, 1, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 1, 0,
1, 0, 1, 0, 1, 0, 1, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
2, 0, 2, 0, 2, 0, 2, 0, 2,
0, 2, 0, 0, 0, 0, 0, 2, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
2, 2, 2, 2, 2, 2, 2, 2, 2);Để biết bên nào tới lượt đi, ta dùng một biến toàn cục side chứa một trong hai giá trị LIGHT và DARK. Một biến toàn cục khác xside sẽ có sẵn giá trị ngược với side để tiện tính toán (ví dụ nếu side = LIGHT thì xside = DARK). Khi tới phiên đối phương đi, ta cần đảo ngược giá trị trong cả side và xside bằng các lệnh như sau (chú ý là LIGHT+DARK = 3):
side := xside; xside := 3 - xside;
Ngoài ra, ta còn khai báo biến computerside cũng chỉ có một trong hai giá trị LIGHT và DARK nhằm cho biết bên nào là máy. Để hiện bàn cờ, phương pháp đơn giản nhất là hiện ở chế độ text (văn bản). Tuy cách này trông xấu và thường không dùng trong các chương trình có trên thị trường nhưng nó có các ưu điểm nổi trội sau:
- Vẫn hiện được bàn cờ rất đầy đủ, trực quan, dễ hiểu, cho phép theo dõi và thi đấu bình thường.
- Rất đơn giản và tin cậy. Bạn sẽ đỡ nhiều thời gian tìm hiểu và phát triển giao diện, dồn sức cho việc quan trọng hơn - làm chương trình chơi hay hơn. Giao diện đồ hoạ chỉ cần thiết lúc hoàn chỉnh - lúc bạn "đóng gói" chương trình.
- Việc hiện thêm các thông tin để kiểm tra, tìm lỗi rất dễ dàng. Rõ ràng việc dùng hai thủ tục có sẵn của Pascal là gotoxy và write thì dễ, nhanh và đảm bảo hơn các hàm đồ hoạ.
- Dễ chuyển đổi hệ máy và hệ điều hành. Có thể bạn sẽ muốn thử chạy trên những máy tính có nền tảng khác như máy mini, macintosh, hệ điều hành Windows 3.1, Win95, Win98, WinNT, System7, UNIX...
- Bạn có thể tự phát triển giao diện đồ hoạ và cài chuột theo ý mình.
Ta sẽ hiện bàn cờ ở dạng như hình 2.3. Chú ý cách đánh kí hiệu các vị trí trong bàn cờ bằng chữ và số giống như bàn cờ Vua.
Để hiện một quân cờ, ta viết một thủ tục DrawCell với tham số là vị trí bàn cờ. Ngoài ra, nó còn một tham số nữa cho biết sẽ hiện mầu nền của quân cờ với mầu bình thường NORMAL (sẽ có nền đen) hay mầu khác SELECT (sẽ có nền xanh sẫm) để thể hiện quân cờ đó được chọn (phục vụ cho chọn và đi quân của người chơi).
procedure DrawCell(pos, mode: byte);
Như vậy, để hiện toàn bộ bàn cờ ta chỉ cần gọi một vòng lặp for là xong:
for i := 1 to BOARD_SIZE do DrawCell(i, NORMAL);
2. Sinh nước đi
Một trong những việc quan trọng nhất để máy tính có thể chơi được cờ là phải chỉ cho nó biết mọi nước đi có thể đi được từ một thế cờ. Máy sẽ tính toán để chọn nước đi có lợi nhất cho nó. Các yêu cầu chính đối với một thủ tục sinh nước đi là:
- Chính xác (rất quan trọng). Một nước đi sai sẽ làm hỏng mọi tính toán. Đồng thời chương trình có thể bị trọng tài xử thua luôn. Do số lượng nước đi sinh ra lớn, luật đi quân nhiều và phức tạp nên việc kiểm tra tính đúng đắn tương đối khó.
- Đầy đủ (rất quan trọng). Sinh được mọi nước đi có thể có từ một thế cờ.
- Nhanh. Do chức năng này phải sinh được hàng triệu nước đi mỗi khi máy đến lượt nên giảm thời gian sinh nước đi có ý nghĩa rất lớn.
Một nước đi có hai giá trị cần quan tâm. Đó là điểm xuất phát (from) và điểm đến (dest). Ta sẽ khai báo một cấu trúc move như sau để dùng những nơi cần đến dữ liệu nước đi.
type
move = record { Định nghĩa cấu trúc nước đi }
from, dest: byte;
end;
Kiểm tra giới hạn bàn cờ
Ví dụ có một quân Xe nằm ở ô số 84 (trong mảng piece). Bây giờ ta sẽ sinh thử một nước đi sang trái một ô cho nó. Nước đi sang trái một ô được chuyển thành ô số 83 là một vị trí cùng hàng với ô xuất phát nên được chấp nhận. Một nước đi khác cần phải xem xét là sang trái ba ô - ô 81. Ô 81 tuy có trong bàn cờ nhưng khác hàng nên không được chấp nhận. Như vậy, muốn biết ô của nước đi sang trái có được phép không ta phải kiểm tra xem nó có cùng hàng với ô xuất phát không. Việc kiểm tra thực hiện bằng cách chia cho 9 (kích thước của một dòng) và lấy phần nguyên (trước đó lại phải chuyển thứ tự ô về gốc là 0 bằng cách trừ đi 1). Ta thấy ((83-1) div 9) = ((84-1) div 9) nên ô 83 được chấp nhận; trong khi đó do ((81-1) div 9) <> ((84-1) div 9) nên kết luận là nước đi đến ô 81 không hợp lệ (hình 2.5).
Dưới đây là đoạn chương trình dùng để sinh những nước đi sang trái của một quân Xe, trong đó x là vị trí của quân Xe này .
PHP:
i := x - 1; { Nước sang trái đầu tiên }
while ((i-1) div 9) = ((x-1) div 9) do
begin
if (ô thứ i là trống) or (ô thứ i có quân đối phương) then
gen_push(vị trí của Xe, vị trí ô đang xét);
if ô thứ i không trống then
break; { Kết thúc quá trình sinh nước đi sang trái }
i := i - 1; { Xét tiếp vị trí bên trái }
end;Việc sinh những nước đi theo chiều khác cũng tương tự (ví dụ để sinh nước đi theo chiều đứng ta chỉ cần cộng hoặc trừ một bội số của 9) nhưng điều kiện kiểm tra sẽ khác nhau. Như vậy, chương trình sinh nước đi Gen có dạng như sau:
for Xét lần lượt từng quân cờ bên hiện tại do
case quâncờ of
Xe: begin
while Xét lần lượt tất cả các ô từ bên phải Xe cho đến lề trái bàn cờ do
begin
if (ô đang xét là ô trống) or (ô đang xét chứa quân đối phương) then
gen_push(vị trí của Xe, vị trí ô đang xét)
if ô đang xét không trống then break;
end;
while Xét lần lượt tất cả các ô từ bên trái Xe cho đến lề phải bàn cờ do
...
while Xét lần lượt tất cả các ô từ bên trên Xe cho đến lề trên bàn cờ do
...
while Xét lần lượt tất cả các ô từ bên dưới Xe cho đến lề dưới bàn cờ do
...
end; { Xong quân Xe }
Pháo:
...
Phương pháp này có nhược điểm là chương trình phải viết phức tạp, cồng kềnh, khó tìm lỗi nhưng khá nhanh.
Trong chương trình mẫu VSCCP, chúng tôi giới thiệu một kĩ thuật khác có tên gọi là "hộp thư" (mail box - do các bảng của nó có dạng các hộp phân thư). Mục đích chính của kĩ thuật này là nhằm giảm bớt các phép kiểm tra vượt giới hạn bàn cờ và làm đơn giản chương trình. Mấu chốt là thay cho bàn cờ có kích thước bình thường 9x10 = 90, ta dùng một bàn cờ mở rộng, mỗi chiều có thêm 2 đường nữa (bàn cờ mới có kích thước 13x14 = 182). Các ô ứng với các đường bao mở rộng đều có giá trị -1, tức là các giá trị báo vượt biên. Các nước đi trên bàn cờ 9x10 được chuyển tương ứng sang bàn cờ này. Nếu một nước đi được sinh ra lại rơi vào một trong hai đường bao thì có nghĩa nó đã rơi ra ngoài bàn cờ rồi, phải bỏ đi và ngừng sinh nước về phía đó. Sở dĩ có đến hai đường biên (chứ không phải một) do quân Mã và Tượng có thể nhẩy xa đến hai ô (hình 2.6).
Ví dụ, nếu vị trí quân Xe nằm ở ô số 84 (trong mảng piece) như hình 2.5, thì khi đổi sang bàn cờ mở rộng sẽ thành vị trí mailbox90[84] = 148. Có nghĩa là nó ứng với ô thứ 148 của mảng mailbox182. Bây giờ ta sẽ sinh thử một nước đi sang trái một ô cho quân Xe này. Việc sinh và kiểm tra sẽ được thực hiện trong bàn cờ mở rộng, nước đi mới là ô số 148 - 1 = 147. Do mailbox182[147] = 83 ¹ -1 nên nước đi này được chấp nhận. Số 83 cho biết kết quả sang trái một ô là vị trí 83 trong bàn cờ bình thường. Tuy nhiên, nước đi sang trái ba ô, có số 148 - 3 = 145 và mailbox182[145] = -1 cho biết đó là một nước đi không hợp lệ.
Chương trình cũng cần kiểm tra số nước đi tối đa theo một hướng của quân cờ đang xét. Chỉ có quân Pháo và Xe có thể đi đến 9 nước đi, còn các quân khác có nhiều nhất là 1.
Việc đi một quân sang vị trí mới thực chất là ta đã thay đổi toạ độ của nó bằng cách cộng với một hằng số (dương hoặc âm). Ở trên ta đã thấy để quân Xe sang trái một nước ta đã phải cộng vị trí hiện tại với -1. Để sinh một ô mới theo hàng dọc, ta phải cộng với +13 hoặc -13 (chú ý, việc sinh nước và kiểm tra hợp lệ đều dựa vào mảng mailbox182 nên giá trị 13 là kích thước một dòng của mảng này). Để sinh các nước đi chéo ta phải cộng trừ với một hằng số khác. Ta nên lưu các hằng số này vào mảng offset có 2 chiều. Một chiều dựa vào loại quân cờ nên chỉ số được đánh từ 1 đến 7. Chiều còn lại là số hướng đi tối đa của một quân cờ.
Quân cờ có nhiều hướng nhất là quân Mã có tới 8 hướng nên chiều này được khai báo chỉ số từ 1 đến 8. Các quân cờ có số hướng ít hơn sẽ được điền 0 vào phần thừa. Chú ý là nước đi quân Tốt của hai bên khác nhau hướng tiến. Để tiết kiệm ta chỉ lưu nước tiến của Tốt đen, còn nước tiến của Tốt trắng chỉ đơn giản lấy ngược dấu.
Kiểm tra vị trí được phép đến
Việc chuyển toạ độ từ bàn cờ thường sang bàn cờ mở rộng chỉ giúp ta loại bỏ được các nước vượt quá biên. Ta còn phải kiểm tra một số giới hạn khác. Ví dụ như Tướng và Sĩ không thể đi ra ngoài cung, Tượng chỉ được phép ở 7 điểm cố định phía bên mình, Tốt chỉ được phép tung hoành trên đất đối phương, còn phía bên mình cũng bị giới hạn ngặt nghèo một số ô... Để thực hiện những phép kiểm tra này, ta dùng một mảng là legalmove ứng với từng ô trên bàn cờ sẽ cung cấp các thông tin này. Để kiểm tra một quân cờ có được phép ở đó không, ta dùng một mặt nạ bít Maskpiece mà tuỳ theo từng quân sẽ có giá trị khác nhau. Nếu ở ô cần kiểm tra có bit trùng với mặt nạ này được đặt là 1 thì quân cờ đó được phép đến ô đấy.
Ví dụ, ô số 3 có giá trị legalmove[3] = 5 (chuyển thành số nhị phân là 00000101) cho biết các quân cờ được phép đi đến đó là Tượng, Xe, Pháo, Mã.
Ngoài ra, ta còn phải kiểm tra nước bị cản (đối với Tượng và Mã) và xử lí cách ăn quân của quân Pháo như một trường hợp đặc biệt. Như vậy, tổng thể sinh các nước đi cho một quân cờ có dạng như sau:
PHP:
p := piece[i]; { Sinh nước đi cho quân cờ p ở vị trí i }
for j := 1 to 8 do begin { Số hướng đi tối đa }
if offset[p,j] = 0 then break;
x:=mailbox90[i]; { Chuyển sang bàn cờ mở rộng}
if p in [ROOK, CANNON] then n := 9 else n := 1;
for t:=1 to n do { Số nước có thể đi theo một hướng}
begin
if (p=PAWN) and (side=LIGHT) then x := x - offset[p, j]
else x := x + offset[p, j]; { Nước đi mới }
y := mailbox182[x]; { Chuyển về toạ độ bình thường }
if side = DARK then t := y else t := 91-y;
if (y=-1) or { Ra ngoài lề ? }
((legalmove[t] and maskpiece[p])=0) { Được phép ở vị trí này không ? }
then break; { Thoát nếu nước đi không hợp lệ }
{ Kiểm tra nước cản với Tượng, Mã và xử lí Pháo ở đây }
...Một vấn đề nữa là luật hai Tướng không được đối mặt trực tiếp với nhau. Việc kiểm tra được thực hiện nhờ hàm kingface. Hàm sẽ trả lại giá trị true nếu nước vừa đi gây hở mặt Tướng. Hàm này có thể được đặt trong thủ tục sinh nước Gen. Tuy nhiên đơn giản hơn, ta đặt nó trong thủ tục gen_push, nếu hở mặt Tướng thủ tục này sẽ không đưa nước đi đó vào danh sách các nước đi.
3. Đánh giá một thế cờ
Đánh giá một thế cờ là một trong những nhiệm vụ quyết định chương trình chơi cờ của bạn có là "cao thủ" hay không. Căn cứ vào một thế cờ máy sẽ gán cho nó một điểm số (lượng giá tĩnh) để đánh giá độ tốt - xấu. Nhờ điểm này máy mới có thể so sánh các thế cờ với nhau và biết chọn nước đi tốt nhất. Đây là một nhiệm vụ rất khó khăn và phức tạp do không tồn tại một thuật toán tổng quát và thống nhất nào để tính điểm cả. Điểm của một thế cờ dựa trên rất nhiều yếu tố mà khó có thể số hoá hết được như phụ thuộc vào số lượng và giá trị các quân cờ hiện tại, phụ thuộc vào tính h.ãm, tính biến, thế công, thế thủ của từng quân cờ cũng như cả cục diện trận đấu. Ví dụ, một cặp Mã giao chân, có thể sát cánh tiến quân và tựa lưng phòng thủ thường có giá hơn hai Mã đứng rời. Nhưng cũng có lúc hai Mã đứng rời lại tốt hơn hai Mã giao chân khi Mã này lại cản Mã kia trong một thế trận nào đó. Ta cũng biết rằng, "lạc nước hai Xe đành bỏ phí, gặp thời một Tốt cũng thành công", thế nhưng số hoá điều này qua hàm lượng giá quả là một điều khó quá sức.
Chúng ta bắt đầu với việc công nhận các giả thuyết sau:
- Ta có thể biểu diễn chất lượng một thế cờ bằng một con số. Ví dụ, con số đó có thể là đánh giá của ta về xác suất chiến thắng, nhưng đối với đa số chương trình thì con số đó không có gì đặc biệt, nó chỉ là con số mà mục đích chính là so sánh được với nhau.
- Chúng ta nên đo chất lượng của một thế cờ tương tự như phép đo của đối phương (do đó, nếu ta coi là đạt được một thế tốt thì đối phương của ta phải thấy đó là thế xấu đối với họ và ngược lại). Điều này tuy không thật đúng lắm, nhưng nó giúp cho thuật toán tìm kiếm của ta làm việc tốt và trong thực tế cũng khá gần với sự thật.
Cách làm này đã bỏ qua mất những nghệ thuật, chiến lược chơi cờ (mà đó là những điểm để đánh giá một người là giỏi cờ hay không). Các quân cờ được triển khai không theo một chiến lược chung nào hết (vô định). Nó còn tạo cảm giác như cờ "vồ", nghĩa là chỉ nhằm nhằm sơ hở của đối phương là "ăn" ngay mà không cần biết đến hậu quả (điều này không hẳn đúng, lí do sẽ trình bầy dưới). Tuy nhiên phương pháp tính điểm này có những ưu điểm sau:
- Là cách tính điểm cơ bản nhất, đóng vai trò chủ đạo trong điểm của một thế cờ. Nó là cơ sở của đa số hàm đánh giá. Ta cũng có thể nhận thấy trong phần lớn thời gian diễn ra trận đấu, hai bên đều tìm cách tiêu diệt quân của nhau. Các phương án, chiến lược thường chỉ được tính như những điểm cộng thêm vào và đóng góp một tỷ lệ nhỏ trong tổng số điểm của một thế cờ. Việc chỉ nhằm "vồ" quân của đối phương nhưng sau khi suy nghĩ sâu nhiều nước cũng đã trở thành "cao cờ" rồi đấy. Nói cho cùng, mục đích chính của chúng ta cũng là "vồ" bằng được quân có giá trị cao nhất - Tướng đối phương.
- Là cách tính đơn giản nhất và nhanh nhất. Do tính nhanh, ta có thể tăng thêm độ sâu tìm kiếm. Việc tăng thêm độ sâu lại giúp máy có cái nhìn xa hơn, "cao cờ" hơn và nhiều khi khắc phục được nhược điểm của cách tính đơn giản.
| Quân cờ | Kí hiệu | Điểm |
| Tốt | PAWN | 1 (2 nếu đã qua sông) |
| Sĩ | BISHOP | 2 |
| Tượng | ELEPHANT | 2 |
| Mã | KNIGHT | 4 |
| Pháo | CANNON | 4.5 |
| Xe | ROOK | 9 |
Bạn cũng có thể theo bất kì thang điểm nào khác tuỳ theo hiểu biết và sở thích của mình. Ví dụ như trong làng cờ Việt nam thường cho điểm các quân hơi khác (xem bài đọc dưới): Tốt - 1 (2 nếu đã qua sông), Sĩ - 2, Tượng - 2.5, Mã - 4.5, Pháo - 5, Xe - 10.
Trong chương trình cờ của chúng ta, điểm cụ thể của từng quân cờ là các số nguyên 10, 20, 20, 40, 45 và 90. Ta dùng một mảng piecevalue để lưu điểm từng quân cờ. Cho điểm như vậy không những vẫn giữ nguyên được tương quan và tránh dùng số thực (tính chậm) mà ta còn có một khoảng cách hợp lí giữa các điểm để sau này dễ dàng thêm những điểm bổ xung "thưởng" hoặc "phạt", tức là những điểm căn cứ vào những yếu tố khác (ví dụ cùng là Pháo nhưng lúc chỉ được 40 điểm do ở vị trí "bí", lúc khác lại có thể đến 85 do ở vị trí Pháo trống và đang đe doạ Pháo lồng).
Trong bàn cờ, quân Tướng là quân quan trọng nhất, dù mất mọi quân hoặc đạt được thế cờ nào đi nữa đều không được mất Tướng vì nó dẫn đến thua cờ. Do đó, Tướng thường được cho một điểm rất cao, cách biệt nhiều lần so với các quân khác, đảm bảo điểm tổng của các quân còn lại cùng đủ mọi loại "thưởng", "thêm" đều không bằng được Tướng. Trong chương trình, ta cho nó 1000 điểm.
Hàm lượng giá thật đơn giản như sau (chú ý là ta chưa tăng điểm cho Tốt đã qua sông):
PHP:
function Eval: integer;
const piecevalue:array[1..7]of integer=(10,20,20,40,45,90,1000);
var i, s: integer;
begin
s := 0;
for i:=1 to BOARD_SIZE do begin
if color[i] = side then s := s + piecevalue[piece[i]]
else if color[i] = xside then s := s - piecevalue[piece[i]];
end;
Eval := s;
end;Vấn đề cải tiến hàm lượng giá sẽ được bàn riêng trong một chương phần sau.
Tham khảo kiến thức cờ Tướng
GIÁ TRỊ CỦA CÁC QUÂN CỜ
Khái niệm giá trị của các quân cờ không phải là mới đối với những người chơi cờ từ các thế kỷ trước. Từ lâu, làng cờ đã có câu nhận định sức mạnh của các quân chủ lực là "Xe 10, Pháo 7, Mã 3" hoặc đánh giá Xe là quân chủ lực mạnh nhất bằng câu "Nhất Xa sát vạn" hay đánh giá một Tốt qua hà, sức mạnh bằng nửa con Xe (nhất Tốt độ hà, bán Xa chi lực). Thế nhưng sự đánh giá nhận định này về sức mạnh của các quân không chính xác và cũng không đầy đủ. Do đó khái niệm giá trị của các quân cần được xác định rõ và hoàn chỉnh hơn. Thông thường, theo thời gian một ván cờ được chia thành ba giai đoạn: khai cuộc, trung cuộc và tàn cuộc. Trong ba giai đoạn này thì trung cuộc chiếm nhiều thời gian nhất và có ý nghĩa đến thắng thua nhiều nhất. Do đó các định giá quân cờ thường là cho giai đoạn này.
Chúng ta đã biết mỗi loại quân cờ hay mỗi binh chủng có đặc điểm, tính năng và tác dụng khác nhau nên sức mạnh của chúng cũng khác nhau, giá trị của chúng cũng không giống nhau. Ngay bản thân mỗi quân cờ cũng không phải lúc nào sức mạnh cũng giữ nguyên như cũ. Khi đứng ở vị trí tốt nó phát huy tính năng tác dụng tối đa khác hẳn với khi nó đứng ở vị trí xấu, không thể phát huy tính năng tác dụng được, hay chỉ phát huy ở mức rất hạn chế. Vậy điều trước tiên chúng ta phải thấy mỗi quân cờ có hai giá trị: giá trị vốn có và giá trị biến động. Giá trị vốn có thường được gọi là giá trị cơ bản (giá trị tĩnh), còn giá trị biến động được gọi là giá trị tương đối.
Các nhà nghiên cứu lí luận về cờ đã trao đổi thống nhất với nhau bảng giá trị cơ bản của các quân như sau:
Nếu lấy Tốt chưa qua sông làm chuẩn để xác định giá trị thì nó là quân kém năng lực nhất trên bàn cờ. Khi chưa qua sông nó chỉ kiểm soát hay khống chế mỗi một điểm trước mặt nó nên tạm cho nó có giá trị bằng 1. Khi Tốt qua sông, nó khống chế đến 2 hay 3 điểm trước mặt và bên cạnh (Tốt biên chỉ khống chế được 2). Bây giờ nó mang giá trị tương đối, phải thấy nó mạnh hơn lúc chưa qua sông nên giá trị lúc này của nó phải bằng 2.
Đối với Sĩ, Tượng là loại binh chủng phòng ngự, có nhiệm vụ chính là bảo vệ an toàn cho Tướng, đôi lúc chúng cũng trợ giúp các quân khác tấn công. Trong giai đoạn trung cuộc, Tốt đối phương qua sông đổi được một Sĩ hoặc một Tượng. Do đó người ta đánh giá Sĩ hoặc Tượng có giá trị bằng một Tốt đã qua sông, tức là bằng 2. Nhưng vì so sánh năng lực giữa Tượng và Sĩ thì thấy Tượng có phần đắc lực hơn nên định giá trị Sĩ là 2 thì Tượng phải là 2.5 mới công bằng.
Quân Mã trên bàn cờ có khả năng khống chế tối đa 8 điểm. Mỗi bước nhẩy của nó vượt được hai tuyến đường ngang hay dọc. So ra thì Mã cũng mạnh đấy nhưng tác chiến ở tầm cự ly ngắn mà thôi. Nếu so với hai Tốt đã qua sông cặp kè nhau thì năng lực của Mã không hơn bao nhiêu, do đó định giá trị cơ bản của Mã 4.5 là vừa. Nên nhớ hai Tốt cặp kè nhau khi qua sông phải có giá trị hơn 4.
Pháo là binh chủng tác chiến tầm xa rất có hiệu quả. Trên đường dọc, Pháo khống chế tối đa chỉ 8 điểm nhưng nó còn khống chế được cả đường ngang. Mặt khác Pháo là quân có tính cơ động cao, nó có thể đi một bước vượt đến 9 tuyến đường. Nhưng ở cự li gần, nhiều khi Pháo bất lực, không làm gì được để khống chế đối phương. Do đó so với Mã thì phải thấy mỗi quân có một sở trường riêng, sức mạnh của chúng coi như tương đương nhau. Thế nhưng trong giai đoạn trung cuộc quân số của hai bên tương đối còn nhiều, Mã đi lại dễ bị cản trở, còn Pháo thì nhanh nhẹn hơn, dễ phát huy năng lực hơn nên giá trị cơ bản của Pháo phải hơn Mã một chút và bằng 5.
Đối với Xe thì rõ ràng là một binh chủng cơ động mạnh nhất, nó khống chế ngang, dọc tối đa đến 17 điểm. Nếu đem Xe đổi lấy một Pháo và một Mã của đối phương thì thấy có phần thiệt thòi một chút, còn đối với hai Pháo thì có thể coi là cân bằng. Do đó giá trị cơ bản của Xe là 10.
Còn Tướng, bản thân nó không có sức mạnh gì nhiều dù đôi khi nó cũng làm được nhiệm vụ trợ giúp cho các quân phe nó tấn công có kết quả. Thế nhưng giá trị cơ bản của nó thì vô cùng to lớn, không một quân nào so sánh được. Tất cả các quân đều có thể đổi, có thể hi sinh nhưng riêng quân Tướng không thể đánh đổi mà cũng không thể hi sinh, vì mất Tướng là thua cờ. Do đó cũng không nên định giá trị cơ bản của Tướng vì định cũng chẳng có ý nghĩa gì.
(Sưu tầm)
4. Xử lí một nước đi "thử"
Trong quá trình tính toán tìm nước đi tốt nhất cho mình, máy thường phải đi "thử" một nước rồi lại tính tiếp. Sau đó nó sẽ phục hồi lại nước đi này. Do quá trình thử - phục hồi diễn ra rất nhanh và không hiện ra màn hình nên máy có thể thử hàng chục triệu lần mỗi khi đến lượt. Việc đi thử được thực hiện nhờ gọi hàm Makemove. Việc khôi phục nước đi này nhờ gọi thủ tục UnMakemove. Như vậy, chương trình thường xuyên thực hiện các câu lệnh dạng như sau:
PHP:
while tất cả các nước đi có thể có từ một thế cờ do begin
Makemove(một_nước_đi); { Đi thử một nước }
best := Tính điểm của nước đi thử đó;
UnMakemove; { phục hồi nước đi này}
Lưu nước đi có điểm cao nhất;
end;Khi đi thử, hàm Makemove phải lưu lại các thông tin cần thiết cho việc khôi phục lại sau này. Cách đơn giản nhất - lưu lại cả bàn cờ, không dùng được do các thông tin phải lưu quá nhiều. Thực chất, ta chỉ cần lưu các thông tin bao gồm: điểm xuất phát của quân cờ, điểm đến và loại quân cờ mà nó bắt được (nếu có). Để lưu các thông tin này, hàm sử dụng một mảng hist_dat các bản ghi chứa thông tin đó và con trỏ hdp được tổ chức như một ngăn xếp, nghĩa là nước đi sau cùng sẽ được phục hồi trước nhất.
Khi máy đi "thử" cho một bên một nước, thì nước sau sẽ đến lượt đối phương. Do đó hàm này cũng phải thay đổi giá trị các biến toàn cục về bên đi và đối thủ side và xside (việc thay đổi này là rất cần thiết để hàm Gen sinh nước đi cho đúng bên tới lượt). Nó cũng tăng biến ply (độ sâu) thêm 1 do đã dấn sâu thêm một bước trên cây tìm kiếm.
Hàm khôi phục nước đi thử UnMakemove có nhiệm vụ là làm mọi thứ ngược lại với hàm Makemove.
Một vấn đề nẩy sinh ở đây là nếu một quân Tướng bị bắt thì có cần phải đi "thử" nữa không. Nếu mất một Tướng, ván cờ sẽ kết thúc ngay lập tức, do đó không cần phải đi thử tiếp và nhánh cây trò chơi bị cắt tại đây dù vẫn chưa đạt đến độ sâu tìm kiếm tối đa. Còn nếu để máy đi thử tiếp, máy sẽ coi Tướng như một quân bình thường (dù có giá trị rất cao) và có thể đổi quân được - nó sẵn sàng để mất Tướng miễn là ngay sau đó ăn lại được Tướng đối phương (hình 2.8). Ta buộc phải cắt nhánh ở những nơi Tướng đã bị mất (hình 2.9).
Để xử lí những trường hợp này, ta cần chuyển Makemove thành một hàm boolean, trả lại giá trị true nếu nước đi thử này lại ăn được Tướng đối phương. Nếu ăn được, hiển nhiên điểm sẽ rất cao (được 1000 điểm) và không cần phải tính điểm cho những nhánh con nữa. Phần chương trình đi thử có dạng như sau:
PHP:
while tất cả các nước đi có thể có từ một thế cờ do begin
if Makemove(một_nước_đi) then { Đi thử một nước. Hàm trả về giá trị true nếu ăn được Tướng đối phương }
best := 1000 - ply { Điểm của nước cờ nếu ăn được Tướng đối phương}
else best := Tính điểm của nước đi thử;
UnMakemove; { phục hồi nước đi này}
Lưu nước đi có điểm cao nhất
end;Trong các câu lệnh trên có một chỗ hơi khó hiểu: tại sao ta lại cho nước ăn Tướng là 1000 - ply mà không phải đúng 1000? Biến ply là biến chỉ độ sâu tìm kiếm. Nếu không có biến này và trong trường hợp Tướng (bên máy tính) sắp bị bắt dù đi bất cứ nước nào thì mọi nhánh cây đều trả về điểm -1000. Do đó máy sẽ chọn nhánh đầu tiên để đi. Nước đi này có thể không hay do chấp nhận thua quá sớm như minh hoạ trên hình 2.10. Máy nên chọn nước thua lâu nhất để hi vọng đối phương đi "nhầm" (còn nước còn tát) và đúng tinh thần chiến đấu hơn.
5. Tìm kiếm AlphaBeta
Ta đã thấy chương trình mẫu của thủ tục AlphaBeta trong chương 1. Hàm AlphaBeta của VSCCP về cơ bản là giống như vậy, chỉ bỏ đi các tham số pos (thế cờ hiện tại - ở đây là giá trị của hai mảng piece và color) ở một số hàm do đã biến đổi trực tiếp vào các mảng toàn cục piece và color (nhờ các hàm Makemove và UnMakemove mà ta đã đề cập đến ở trên) nên chúng chính là thế cờ đang xét.
PHP:
function AlphaBeta(alpha, beta: integer; depth: byte): integer;
var i, best, value: integer;
begin
if depth = 0 then AlphaBeta := Eval
else begin
Gen; best := -INFINITY;
i := gen_begin[ply]; { Khởi đầu để lặp tất cả các nước }
while (i < gen_end[ply]) and (best < beta) do begin
if best > alpha then alpha := best;
if MakeMove(gen_dat[i].m) then value := 1000-ply
else value := -AlphaBeta(-beta, -alpha, depth-1);
UnMakemove;
if value > best then begin
best := value;
if ply = 0 then newmove := gen_dat[i].m;
end;
inc (i);
end; { while }
AlphaBeta := best;
end;
end;Nước đi tốt nhất (điểm cao nhất) ở độ sâu 0 (ply = 0) được lưu vào một biến toàn cục newmove. Máy sẽ chọn đi theo nước này.
Thủ tục gọi hàm AlphaBeta chỉ có các lệnh đơn giản như dưới. Nó gọi hàm này với các giá trị khởi đầu thích hợp để bắt đầu tìm kiếm.
PHP:
(***** THINK - MÁY TÍNH TÍNH NƯỚC ĐI *****)
procedure ComputerThink; { Tìm nước đi tốt nhất cho máy }
begin
AlphaBeta (-INFINITY, INFINITY, MAX_PLY);
end;6. Xử lí điều khiển của người chơi
Người chơi dùng bàn phím để điều khiển các quân bên mình khi đến lượt: dùng các phím mũi tên điều khiển con trỏ màn hình chạy đến quân cờ thích hợp, bấm phím Space hoặc Enter để chỉ mình sẽ đi quân này, chuyển con trỏ đến chỗ mới và vẫn bấm phím Space hoặc Enter để chỉ đó là chỗ đến. Người chơi có thể ngừng chơi giữa chừng bằng cách bấm phím ESC. Hàm xử lí điều khiển của người chơi GetHumanMove phải làm nhiệm vụ xử lí các phím điều khiển và trả về nước đi được chọn trong biến toàn cục newmove. Hàm cũng xử lí hai biến toàn cục x, y là toạ độ của con trỏ màn hình.
Một chương trình chơi cờ tốt còn phải giúp đỡ người chơi không đi sai luật. Các nước đi không hợp lệ (dù cố ý hay vô tình) đều cần được phát hiện và ngăn cấm. Cách làm thì có nhiều, ở đây chúng tôi giới thiệu phương pháp đơn giản nhất sử dụng hàm sẵn có: hàm Gen. Đầu tiên, ta gọi nó để sinh ra tất cả những nước đi có thể có từ thế cờ hiện tại với bên đi là người - đó chính là các nước đi hợp lệ. Mỗi khi người chơi chọn một nước, máy sẽ kiểm tra xem nó có trong danh sách các nước đi hợp lệ không. Nếu có, máy sẽ chấp nhận nước đi đó và thoát khỏi hàm GetHumanMove. Nếu không nó sẽ đòi người chơi phải chọn lại.
PHP:
function GetHumanMove: boolean;
const x: byte = 5; y: byte = 5;
var ch: char; selecting, from, t, i: integer;
begin
Gen; { Dùng để kiểm tra nước đi hợp lệ của người chơi }
GetHumanMove := false; selecting := 0;
while true do begin
MoveTo(x, y);
ch := ReadKey;
case ch of
#13, ' ': begin { Đánh dấu/chọn một nước đi }
t := x + (y-1)*SIZE_X;
if selecting=0 then begin { Người chơi đánh dấu }
if color[t]=side then begin
selecting:=1; from := t; DrawCell(t,SELECT);
end;
end
else begin { Người chơi chỉ ra nước đi đến }
if t <> from then DrawCell(from, NORMAL);
if color[t]=side then begin
from := t; DrawCell(t, SELECT);
end
else begin
newmove.from := from; newmove.dest := t;
{ Kiểm tra xem nước đi vừa chọn có trong danh sách các nước đi hợp lệ không. Nếu có sẽ thoát khỏi hàm này để đến lượt máy }
for i := gen_begin[ply] to gen_end[ply]-1 do
if (gen_dat[i].m.from = from) and
(gen_dat[i].m.dest = t)then
exit;
{ Nếu nước đó không hợp lệ, hiện lại quân xuất phát, để người chơi chọn nước đi khác }
DrawCell(from, SELECT);
end;
end;
end;
#27: { Xử lí các phím khác ở đây }
...7. Cập nhật một nước đi
Sau khi "suy nghĩ" xong, đã đến lúc máy hoặc người phải thực hiện một nước đi thực sự. Chương trình phải cập nhật tất cả các thông tin cần thiết liên quan đến nước đi và hiện hình những thay đổi. Việc này được thực hiện nhờ gọi hàm UpdateNewMove. Nó có khá nhiều chỗ giống như hàm Makemove nhưng đơn giản hơn. Tham số quan trọng nhất mà nó quan tâm là nước đi được người hoặc máy chọn đi (đặt trong biến toàn cục newmove). Hàm cũng đồng thời sẽ kiểm tra tình trạng thắng cờ của bên vừa đi (ăn được Tướng đối phương) và trả về giá trị true nếu có một bên thắng. Vòng lặp chính sẽ căn cứ vào giá trị chân lí này để ngừng chơi.
8. Vòng lặp chính xử lí trò chơi
Sau khi có các hàm và thủ tục cần thiết, đã đến lúc ta liên kết chúng lại thành một trò chơi hấp dẫn. Trong phần thân chương trình chính, ta sẽ bắt gặp vòng lặp repeat. Vòng lặp này sẽ lặp mãi cho đến khi người chơi bấm phím ESC hoặc một bên thắng cờ. Tuỳ theo bên tới lượt nó sẽ gọi hàm xử lí thích hợp cho người hoặc máy. Sau khi nhận kết quả nó lo cập nhật các số liệu cần thiết, chuyển đối phương thành người đến lượt chơi.
PHP:
repeat
if side=computerside then ComputerThink
else if GetHumanMove then break;{ Thoát nếu ESC được bấm}
side := xside; xside := 3 - xside; { Đổi bên tới lượt chơi }
until UpdateNewMove;9. Hiện thông tin
Đến đây, chương trình đã sẵn sàng đọ sức với bạn rồi đấy. Nhưng có thể bạn muốn biết thêm một vài số liệu như: thời gian mỗi lần máy nghĩ, hệ số phân nhánh của cây trò chơi, số thế cờ nó phải tính giá trị, khả năng xét thế cờ trung bình của máy là bao nhiêu cũng như nhiều số liệu khác. Việc quan sát các số liệu này còn giúp ta biết các cải tiến, sửa đổi về sau có thực sự hoạt động tốt không.
Cách lấy số liệu rất đơn giản, ta khai báo thêm một số biến toàn cục, thêm một số lệnh và cuối cùng in chúng ra màn hình ở chỗ thích hợp. Một số thông tin rất khó lấy chính xác, ta sẽ tạm bằng lòng với những số liệu gần đúng vậy.
Để biết mỗi lần nghĩ, máy đã lượng giá bao nhiêu thế cờ - một thông tin vô cùng quan trọng, ta khai báo một biến toàn cục evalcount và mỗi khi hàm Eval được gọi ta lại tăng giá trị của nó thêm một.
Ta cũng cần biết máy đã nghĩ trong bao lâu bằng cách khai báo các biến để tính thời gian. Thời gian được đo căn cứ vào số xung đồng hồ ở vị trí tuyệt đối $40:$6c trong bộ nhớ. Từ đây ta tính được thời gian tính bằng giây nhờ chia cho 18.23 - số xung trong mỗi giây. Khi biết được thời gian đã tiêu tốn có thể ước tính tốc độ lượng giá của máy bằng cách chia tổng số nút đã lượng giá cho thời gian tiêu tốn. Tất nhiên thời gian tiêu tốn này ngoài thời gian tiêu cho hàm lượng giá còn phải chi cho nhiều thứ khác như chạy các lệnh của hàm Gen, hàm AlphaBeta... nên cách làm này chỉ cho biết con số ước lượng mà thôi.
Để có được hệ số phân nhánh chính xác ta phải thống kê qua một số dữ liệu lớn. Chú ý rằng, số nhánh con được sinh ra mỗi lần gọi hàm Gen được đo bằng hiệu gen_end[ply]-gen_begin[ply]. Do đó hệ số phân nhánh được đo bằng cách lấy tổng các nhánh con này rồi chia cho số lần gọi hàm Gen (đo bằng biến gencount). Càng chơi lâu, các dữ liệu đo được càng lớn, kết quả sẽ càng chính xác.
Ngoài ra, bạn có thể còn muốn hiện chú giải nước vừa đi của máy để dễ theo dõi và xem xét điểm đạt được. Hãy chú ý cách tính các con số này (chú ý số 65 là mã của chữ cái A, 9 là số cột của một dòng bàn cờ).
Sau đây là những chỗ cần bổ xung để bạn có được các thông tin cần thiết. Những chỗ thêm, sửa từ nay về sau đều được đánh dấu bằng một mũi tên trắng cho dễ tìm.
PHP:
const
...
{ Các biến dùng để đo hệ số phân nhánh }
brandtotal: longint = 0; gencount: longint = 0;
...
Var
evalcount: longint;
systicks: longint absolute $40:$6C; { Biến để đo thời gian }
...
procedure Gen;
...
brandtotal := brandtotal + gen_end[ply] - gen_begin[ply];
inc(gencount);
end;
function Eval: integer;
var i, s: integer;
begin
inc(evalcount);
...
procedure ComputerThink; { Tìm nước đi và hiện thông tin }
var best: integer; tickstart, tickend: longint;
begin
evalcount := 0; tickstart := systicks;
best := AlphaBeta(-INFINITY, INFINITY, MAX_PLY);
{ Phục vụ hiện các thông tin theo dõi }
tickend := systicks; textcolor(7);
gotoxy(50, 4); write('Do sau : ', MAX_PLY);
gotoxy(50, 5); write('So nut luong gia: ', evalcount, ' ');
gotoxy(50, 6); write('He so phan nhanh: ',
brandtotal/gencount:3:2, ' ');
gotoxy(50, 7); write('Thoi gian (giay): ',
(tickend-tickstart)/18.23:0:2, ' ');
gotoxy(50, 8); write('Toc do xet nut : ',
evalcount*18.23/(tickend-tickstart+1):0:0, ' ');
gotoxy(50, 9); write('Diem dat duoc : ', best, ' ');
gotoxy(50,11); write('May tinh di : ',
chr(((newmove.from-1) mod SIZE_X)+65),
SIZE_X -(newmove.from-1) div SIZE_X,
chr(((newmove.dest-1) mod SIZE_X)+65),
SIZE_X-(newmove.dest-1)div SIZE_X,' ');
end;10. Chạy thử
Bây giờ bạn hãy dịch và chạy thử chương trình trên (toàn bộ nguồn trong Phụ lục A). Cẩn thận nhé, ta chưa cài chức năng cho phép hoãn đi. Nếu đi nhầm bạn không thể đi lại. Chương trình máy tính lại không "nhầm lẫn" và với độ sâu ngầm định 4 (tức là nghĩ trước tới 4 nước đi) nó có khả năng đánh bại những người chơi có trình độ trung bình và chơi ẩu. Bạn hãy chịu khó suy nghĩ kĩ một chút, cẩn thận một chút thì có thể thắng được.
Hình 2.11 là thông tin in ra màn hình sau khi máy đi nước đầu tiên. Chương trình được chạy trên máy tính Pentium 166MHZ cài hệ điều hành Windows 98 và tìm kiếm đến độ sâu bằng 4. Các số liệu cho ta biết cây trò chơi có hệ số phân nhánh khoảng 41. Nếu lấy tròn là 40 thì ta có bd = 404 = 2560000 (tức là số nút lá của cây trò chơi có khoảng trên hai triệu rưởi nút). Đó chính là số nút ta phải xét nếu dùng phương pháp tìm kiếm Minimax. Với tốc độ trung bình xét được 55985 nút mỗi giây thì thời gian để xét hết bằng phương pháp này sẽ mất khoảng 2560000/55985 » 46 giây. Ở đây, ta đang dùng phương pháp tìm kiếm AlphaBeta, số nút phải xét chỉ còn 150480, nghĩa là ít hơn 17 lần và tổng thời gian phải bỏ ra chỉ 2.63 giây thay cho 46 giây. Nước đi Mã vào góc không được hay lắm - nhưng không sao, đây mới chỉ là phiên bản đầu tiên và độ sâu tìm kiếm còn hạn chế.
Nếu bạn chưa hề thực hiện một cải tiến nào mà chỉ nhập nguyên vẹn chương trình mẫu từ Phụ lục A và dịch chạy thì các giá trị về độ sâu, số nút lượng giá, hệ số phân nhánh, điểm đạt được, máy tính đi (trừ những thông số liên quan đến thời gian do tuỳ thuộc loại máy bạn có) phải y hệt như hình 2.11. Nếu có điều gì khác có nghĩa là đã có sai sót trong khi nhập chương trình nguồn, bạn cần thận trọng kiểm tra chương trình.
Tuỳ theo sức mạnh máy tính (và cả khả năng chờ đợi), bạn hãy thử tăng độ sâu tìm kiếm bằng cách sửa khai báo hằng số MAX_PLY từ 4 lên 5 hoặc 6. Đừng ham tăng nhiều. Do bùng nổ tổ hợp, nếu tăng nhiều bạn sẽ không chờ nổi đâu. Càng tăng độ sâu, bạn sẽ thấy chương trình chơi càng bớt hớ hênh và càng khó thắng đấy.
Bạn hãy thử kiểm nghiệm với độ sâu 5 xem sao. Các con số đều tăng khủng khiếp. Trên máy tính của tôi, thời gian xét nước đầu tiên đã tăng từ 2.63 tới 88 giây (tăng 33 lần). Số nút phải lượng giá là 5574794 nút (tăng 37 lần).
Nếu máy tính của bạn là loại tốt, hãy thử tiếp với độ sâu 6. Trên máy tính của tôi, thời gian máy "nghĩ" nước đầu tiên đã mất tới 1031 giây (hơn 17 phút, gần gấp 12 lần). Còn số nút phải lượng giá là 62929742 (gấp 11 lần). Bạn có thể thấy các con số cũng tăng rất nhiều nhưng dù sao chỉ tăng cỡ 11 lần. Hệ số phân nhánh được thống kê qua số lượng nhiều hơn đã tụt xuống còn 40.15. Nước được chọn đi hơi khác là B7C7 (có lẽ là nước tốt hơn). Còn độ sâu 7 tôi chỉ dám thử một lần vì thời gian tiêu tốn cho lần nghĩ nước đầu tiên mất đến... 3.7 giờ (trong khi qui định tổng cộng tất cả các nước của một đấu thủ chỉ được trong 1 giờ khi thi đấu).
Nếu ta cho rằng tăng một độ sâu thời gian tính toán chỉ dài thêm trung bình 10 lần thì chỉ cần đến độ sâu 11, các máy tính cỡ Pentium 166 MHZ sẽ mất đến... 4 năm để nghĩ nước đi đầu tiên (còn đến độ sâu 14 thì mất... 4223 năm).
Ta hãy thử ước mơ nếu có được chiếc máy tính mạnh và chuyên dụng (cho cờ) như Deep Blue thì tính được đến đâu. Loại máy lần đầu tiên thắng được Kasparov (năm 1997) có khả năng xét được trung bình 200 triệu (đôi khi lên đến 400 triệu) nước đi mỗi giây. Với độ sâu 7 (mà máy tính của tôi phải ỳ ạch trong 3.7 tiếng đồng hồ) sẽ được máy chiếu cố trong khoảng... 3 giây. Nếu được nghĩ một nước trong 3 phút (thời gian được phép trung bình cho một nước) thì độ sâu có thể đến được sẽ khoảng từ 8 đến 10 (nếu không có cải tiến đặc biệt).
Đến đây ta cũng có thể thấy, các chương trình cờ thuộc loại tốt nhất chạy trên các máy tính thông thường (loại PC và không gắn các mạch chuyên dụng) cũng chỉ tìm kiếm được đầy đủ đến độ sâu từ 5 đến 8 mà thôi (với giới hạn thời gian thi đấu bình thường). Dù vậy các cố gắng cải tiến bỏ ra cũng phải rất nhiều và rất lâu mới đạt được đến các độ sâu như vậy (bạn sẽ được nghiên cứu một vài cải tiến nhằm nâng độ sâu trong thời gian chơi hợp lí).
Chú ý là thông báo về tốc độ xét nước có thể rất khác nhau khi thay đổi độ sâu cực đại do hàm lượng giá dùng ở đây quá đơn giản, tỷ trọng thời gian không lớn so với các hàm khác và thời gian đo lại bao gồm tất cả mọi thứ nên các con số bị ảnh hưởng nhiều. Tuy nhiên, nếu với cùng độ sâu thì tốc độ hiện tương đối ổn định.
Toàn bộ mã nguồn chương trình cờ Tướng VSCCP phiên bản 1.0 cho trong phần Phụ lục A.
Tổng kết chương 2
Chương này đi sâu vào cách viết một chương trình cờ Tướng đơn giản. Những điểm quan trọng trong chương là các khai báo các loại dữ liệu khác nhau, cách biểu diễn một bàn cờ, các thủ tục và hàm cơ bản. Chú ý là các cấu trúc dữ liệu và các khai báo trong chương trình mẫu rất đơn giản nhưng cũng rất hiệu quả. Thủ tục Gen là lằng nhằng, phức tạp và dễ sai nhất.
Thuật toán AlphaBeta tuy giống như đã đề cập đến trong chương 1 nhưng đến chương này bạn cần phải hiểu nó thật sự. Bạn cũng cần nắm vững cách lấy số liệu cũng như hiểu các số liệu này để tiếp tục theo dõi các cải tiến chương trình trong các chương sau.
GỢI Ý PHÁT TRIỂN
- Thay cho mảng một chiều biểu diễn bàn cờ, bạn hãy thử dùng mảng hai chiều (dạng piece[1..10, 1..9] of byte). Tự mình khám phá các ưu, nhược điểm của cách làm này.
- Một byte là quá đủ để lưu thông tin về quân cờ và bên chơi. Nói cách khác, mảng color không thật cần thiết. Bạn hãy sửa lại chương trình sao cho vẫn giữa nguyên khai báo của mảng piece, nhưng lại bỏ được mảng color.
- Tại sao bạn lại phải chuyển sang bàn cờ mở rộng kích thước 13´14 (và để rồi lại phải chuyển về bàn cờ thường 9´10) để làm mỗi nhiệm vụ kiểm tra việc vượt quá biên cho nước cờ đang được sinh? Bạn có thể dùng trực tiếp bàn cờ mở rộng này để chơi được không (dùng trực tiếp bàn cờ 13x14)?
- Bạn hãy tự sửa chương trình cho phép cả hai bên đều là máy (hoặc đều là người) chơi. Nghĩa là cho máy có thể tự đấu.
- Thử để máy đấu cả hai bên với độ sâu giống và khác nhau (ví dụ như 3-3, 3-4, 4-4, 3-5 hoặc 4-5) và thay đổi lượt đi trước của các bên. Bên nào thắng?
- Bạn hãy tự cải tiến hàm lượng giá theo ý mình. Ví dụ hãy thử cho điểm các quân cờ tuỳ ý.
- Hãy thi đấu nhiều với máy. Chắc chắn trong quá trình chơi máy sẽ đi nhiều nước khá lạ lùng (trên quan điểm của người chơi bình thường). Hãy ghi lại những nước đi đó và hãy thử lí giải vì sao máy lại đi như vậy. Khảo sát kĩ và hãy thử cải tiến hàm lượng giá nếu máy phạm sai lầm nhiều.
- Bạn hãy cài thêm một chức năng nữa cho người chơi: chức năng "hoãn", nghĩa là bỏ nước vừa đi (hoặc một loạt nước vừa đi) và cho người chơi đi lại nước khác. Chú ý: hãy tận dụng tối đa những thủ tục có sẵn như UnMakemove.
- Bạn hãy cài chức năng "gợi ý" (hay "mách nước") cho người chơi biết nên đi nước nào bằng cách chỉ ra các nước đi chống cự tốt nhất. Bạn nên tận dụng những kết quả có sẵn trong lần máy nghĩ trước đó mà không cần phải tính lại.
- Hãy cho phép người chơi ghi lại ván cờ đang chơi dở và lúc khác có thể nạp vào để chơi tiếp.
- Cho phép người chơi được bầy cờ thế. Bầy xong mới thi đấu.
- Hãy tự cải tiến giao diện: dùng đồ hoạ, cài thêm chuột, thêm menu, phím gõ tắt... Hãy tham khảo các chương trình cờ có trên thị trường để làm cho tốt.
- Bình luận: Theo dõi một trận đấu bất kì, mỗi khi một đấu thủ đi một nước thì cố gắng giải thích lí do chọn nước đó. Ví dụ giải thích nước đi đó dẫn tới thế cờ hay (nhờ điểm cao), sẽ ăn được quân nào đó của đối phương hoặc tránh được mất quân, hoặc dẫn tới thắng hoặc tránh thua sau bao nhiêu nước...
- Ghi nước đi: Ta đã làm quen với cách ghi nước đi đơn giản ở trên. Ví dụ như A1A6 nghĩa là quân cờ ở vị trí A1 sẽ chuyển đến vị trí A6. Cách này xử lí thật đơn giản. Tuy vậy, đây không phải là cách ghi nước đi thường dùng trong "làng cờ". Nếu bạn đưa bản ghi một ván cờ như thế cho một người chơi cờ bình thường thì họ không hiểu. Ta cần ghi một ván cờ theo các qui định ghi chép biên bản ván đấu (do Liên đoàn cờ Việt nam đưa ra). Các qui định này như sau:
- Bàn cờ được tính theo cột (hình 2.12). Bên nào tính theo cột bên đó.
- Kí hiệu quân cờ: Tg - Tướng; S - Sĩ; T - Tượng; X - Xe; P - Pháo; M - Mã; B - Tốt (Binh).
- Để phân biệt các quân cùng loại đứng trước, sau hay ở giữa thì dùng các chữ viết tắt: t - trước, s - sau, g - giữa.
- Kí hiệu đi quân:
+Thoái (lui): (/) gạch chéo. Ngược với tấn. Ví dụ M7/8 nghĩa là Mã cột 7 thoái lui sang cột 8.
+Bình (sang ngang): (-) dấu ngang (P2-5 nghĩa là Pháo 2 sang ngang đến cột 5).
Ví dụ: Các nước đi dẫn đến thế cờ như hình 2.12 (thế này có tên dài dòng là: Pháo đầu Xe tuần hà đối bình phong Mã cổ điển) được ghi như sau:
1. P2-5 M8.7
2. M2.3 C3.1
3. X1-2 X9-8
4. X2.4 M2.3
Tác giả: Phạm Hồng Nguyên
Em nghiên cứu cờ tướng oke là làm được cờ vua mà 
