Trang nhất
 Tin cờ
 Cờ và văn hóa
 Kiến thức cờ
 Khoa học Cờ
 Các ván cờ

Chuyên đề & Bài hay
 
 
 
 

Chủ nhật, 13-03-2011 Xem: 7315
Nghiên cứu cờ tàn bằng máy tính

Trong bài này tôi sẽ đề cậ­p đến một số kiến thức và kết quả của việc dùng máy tính vào nghiên cứu cờ tàn nói chung (cờ Vua, cờ Tướng) và minh họa bằng một số kết quả cụ thể với cờ Tướng.

I. Mở đầu
Cũng như mời ngành kinh tế quốc dân và khoa học kỹ thuậ­t, ngày nay việc áp dụng máy tính vào cờ là điều rất cần thiết và mang lại nhiều kết quả kích lệ. Một trong những kết quả của việc áp dụng hiệu quả của máy tính vào cờ này là nghiên cứu cờ tàn - xây dựng các Cơ sở dữ liệu tàn cuộc (Endgame databases - riêng với cờ Vua còn được gọi là TableBases).

Một số sách cờ thường chia cờ tàn thành hai loại: cờ thế và cờ tàn thực dụng.

  • Cờ thế (còn gọi là cờ tàn nghệ thuậ­t) là những thế cờ thường do còn người nghĩ ra để đố nhau, để thưởng thức, gây bất ngờ cho ngươi giải qua những nước đi kỳ lạ. Do đó, cờ thế rất ít khi gặp trong thực tế chiến đấu. Cờ thế cũng không nhất thiết phải là cờ tàn. Nói chung số quân tham gia của cờ thế thường tương đối lớn. Аôi khi căn cứ vào số quân trên bàn, nó phải được liệt vào trung cuộc. Cờ thế thường có rất ít lời giải đúng (nhiều khi chỉ có một lời giải duy nhất) với những nước đi thường rất bất ngờ và đòi iều toàn bộ quá trình đi quân phải rất chính xác. Do số quân lớn, đòi iều nhiều trí trí sáng tạo của con người (cả người đặt thế lẫn người giải) nên máy thường khó áp dụng vào loại cờ này (máy hầu như không thể lậ­p được cờ thế và thường không giải được những thế phức tạp).
  • Cờ tàn thực dụng: Аây là những thế cờ thường dẫn đến khi gần kết thúc ván cờ. Khác với cờ thế, cờ tàn thường có nhiều lời giải hơn và có khá nhiều ván không đòi iều người chơi phải đi thậ­t chính xác. Các tác giả thường không nhất trí ranh giới khi nào một ván cờ chuyển từ trung cuộc sang tàn cuộc nhưng thường đồng ý rằng tàn cuộc là ván cờ mà hai bên chỉ còn rất ít quân mạnh, một vài con Chốt và hàng phòng thủ sứt mẻ ít nhiều. Người chơi bắt buộc phải nghiên cứu cờ tàn nếu muốn đi đúng khi gặp những thế cờ đó. Аây chính là mảnh đất khai phá rất tốt cho máy tính.
II. Cơ sở dữ liệu tàn cuộc (CSDLTC)

CSDLTC là gì?

CSDLTC chỉ đơn giản là các file dữ liệu máy tính trong đó ghi lại mời thế cờ có thể có của một tàn cuộc và mời trạng thái thắng thua của tất cả các thế cờ đó. Nó chính là một dạng "cẩm nang" tra cứu. Với một chương trình chuyên dụng đi kèm, người dùng có thể nhậ­p vào một thế cờ bất kỳ và máy sẽ tra và cho biết trạng thái của thế cờ đó: đó hoặc đó là thế cờ hòa, hoặc một bên sẽ thắng và thắng trong bao lâu (chiếu hết trong bao nhiêu nước). Chỉ việc lần theo chuổi thế cờ ta sẽ biết được những nước đi tối ưu nhất: nếu hòa phải đi như thế nào để đảm bảo hòa, nếu thắng sẽ tìm ra chuổi nước đi ngắn nhất, nếu thua, sẽ biết cách chống cự lâu nhất.

Người ta xây dựng CSDLTC như thế nào?

Аể xây dự các CSDLTC, người ta viết chương trình dùng thuậ­t toán tính lùi (retrograde). Nguyên tắc khá đơn giản, đầu tiên người ta tìm ra tất cả các thế cờ mà một bên chiếu hết bên kia và đánh dấu vào CSDL các thế cờ đó là các nước chiếu hết (chiếu hết trong 0 nước). Sau đó, người ta tìm tất cả các thế cờ mà sau khi đi một nước sẽ dẫn đến các các thế cờ chiếu hết. Аó chính là các thế cờ chiếu hết trong một nước. Cứ như vậ­y, họ sẽ tìm ra các thế cờ chiếu hết trong 2 nước, 3 nước... Việc truy tìm này sẽ dừng lại khi không còn tìm được thế cờ dẫn đến chiếu hết nữa. Các thế cờ còn lại sẽ được đánh dấu là hòa.

Trong thực tế, để có thể xây dựng được những CSDLTC lớn, cần có những chương trình khá tinh vi và đặc biệt cần rất nhiều thời gian chạy máy. Việc nghiên cứu và xây dựng các CSDLTC cho cờ Vua được bắt đầu từ những năm 1950-60. CSDLTC đầu tiên (Thompson) được dùng trong thực tế xuất hiện vào giữa thậ­p nhiên 1980 - nó được xây dựng bằng máy tính lớn. Vào những năm 1990 một số CSDLTC khác (cũng cho cờ Vua - với thiết kế khác) cũng bắt đầu xuất hiện và được xây dựng trên máy tính để bàn. Hiện nay, CSDLTC Nalimov là loại phổ biến nhất trong thế giới cờ Vua.

Hiện tại, đối với cờ Vua, người ta đã xây dựng xong các CSDLTC cho mời tàn cuộc có từ 5 quân (5 men) trở xuống. Tổng kích thước cờ¡ 8GB. Người ta đang cố gắng xây dựng các CSDLTC cho các tàn cuộc có nhiều quân hơn (6 quân). Аể xây dựng CSDLTC khoảng dưới 10 GB, người ta cần nhiều tháng chạy máy PC ròng rã vào những năm 1990. Hiện nay, do máy tính PC đã mạnh, nhanh, có bộ nhớ lớn hơn nên thời gian xây dựng một CSDLTC kích cờ¡ này đã giảm đi đáng kể, chỉ cần một vài tuần.

Cũng nhờ khả năng máy tính mạnh hơn, một số CSDLTC cho những trò chơi khác (vốn có số quân và kích thước lớn hơn nhiều) mới có cơ phát triển. Một trong số đó chính là CSDLTC của cờ Tướng.

III. ờ¨ng dụng của CSDLTC

Chơi cờ:

Các sách dậ­y tàn cuộc chỉ có thể chọn và in vọng loại tàn cuộc vài ván cờ điển hình. Người chơi sẽ căn cứ vào những ván cờ và phân tích của tác giả để tự nắm được phương pháp chơi. Sau này, khi gặp những thế cờ mới của tàn cuộc đó, người chơi phải tự mình áp dụng các kiến thức thu được để giải thế cờ, tìm ra nước đi đúng. Cách làm này dĩ nhiên là lâu, là... "mệt" và không phải lúc nào người chơi cũng có thể tìm được ra nước đi tối ưu. Tệ hơn nữa, anh ta có thể bờ lờ¡ mất cơ hội chiến thắng. Trong khi đó, nếu có CSDLTC của tàn cuộc đó, máy sẽ chỉ ngay ra kết quả (thắng, hòa, thua) cho bất cứ thế cờ nào và làm sao để đi tối ưu nhất. Một khi CSDLTC nói thắng, đối phương sẽ không có cách nào "chạy thoát", cho dù còn hàng chục nước phải đi nữa. Аối với máy/người dùng CSDLTC, anh ta cũng không còn phải lo thiếu thời gian nữa: thời gian là ngừng chạy vì lúc này máy tính chỉ bờ ra một phần rất nhờ của giây để tìm ra nước đi tốt nhất từ CSDLTC.

Ví dụ, có bạn iều về tàn cuộc một Mã chống lại một Sĩ, CSDLTC của chúng tôi chỉ ra rằng:

  • Có tổng cộng 12,684 thế cờ hợp lệ khác nhau
  • Bên mạnh (bên có Mã) nếu đến lượt đi có tới 99.70 % cơ hội để thắng và chỉ có 0.3% dẫn đến hòa. Trong khi đó, nếu bên yếu (bên có Sĩ) có thể cải thiện tình hình một chút nếu được đi trước: có 4.38% cơ hội hòa.
  • Thế cờ dài nhất phải cần đến 19 nước đi để bên trắng thắng.
Bây giờ nếu bạn đưa ra bất cứ thế cờ nào của tàn cuộc này, chúng tôi sẽ chỉ ngay lậ­p tức trạng thái và nước đi tối ưu, đảm bảo chính xác 100%.

Аối với người nghiên cứu cờ

Các CSDLTC có thể giúp tiết kiệm hàng chục năm của người nghiên cứu tàn cuộc. Từ CSDLTC của một tàn cuộc, anh ta có thể đúc rút ra các thế cờ khác nhau, các cách đi tối ưu, nghiên cứu các biến một cách dễ dàng và nhanh chóng.

Một trong các ví dụ khác mà mời người có thể kiểm chứng là tàn cuộc một Xe chống lại Sĩ Tượng bờn. Bình thường người ta coi thế cờ này là thường hòa trừ một số tình huống đặc biệt. Các sách cờ thường trình bầy khoảng 10 thế cờ dẫn đến thắng này. Với CSDLTC của thế cờ này, số liệu chính xác lại đưa ra một bức tranh khác:
- Có tổng cộng 465,705 thế cờ khác nhau
- Bên mạnh (bên có Xe) khi đến lượt có tới 81.79% cơ hội thắng, hòa chỉ 18.21%
- Bên yếu đến lượt đi: thua 51.07%, gờ¡ hòa : 48.93%
- Thế cờ dài nhất cần đến 32 nước đi.
Như vây, nếu bên trắng chủ động thì đây là thế cờ thường thắng chứ không phải thường hòa.

Аể tự mình kiểm chứng tàn cuộc này, bạn hãy download chương trình EON tại trang web của chúng tôi (www.xqfan.com). Chạy chương trình này, bạn có thể xem các thế cờ điển hình do máy tìm ra, thay đổi các tham số để tìm ra các thế cờ khác theo ý bạn, soạn một thế bất kỳ và đưa vào iều máy lời giải. Nếu bạn không "thích" một lời giải của máy thì có thể thoải mái di chuyển quân theo ý mình, máy sẽ tìm ra ngay lời đáp tối ưu cho nước đi của bạn. Thay cho 10 thế cờ tiêu biểu, bạn mặc sức thưởng thức và tìm hiểu trong hơn 370 nghìn thế cờ thắng cho bên trắng.

Các CSDLTC cũng mang lại nhiều kết quả mới đầy bất ngờ. Một trong những kết quả ấn tượng là tàn cuộc Tướng, Pháo, Chốt, Sĩ, Tượng chống là Tướng Sĩ Tượng bờn. Một số tàn cuộc Pháo Chốt đã được nghiên cứu từ thế k 16. Vào đầu thế k 20, một tác giả người TQ đã kết luậ­n rằng Tượng, Pháo, Chốt (cao), Sĩ, hai Tượng có thể thắng Tướng Sĩ Tượng bờn. Tác giả Ren Wu chỉ với một cái máy tính đã xây dựng nên các CSDL và chứng minh được rằng Tướng Pháo Chốt, Sĩ, Tượng (bớt một Tượng) có thể thắng được Tướng Sĩ Tượng bờn. Thế cờ dài nhất phải cần đến 95 nước đi chính xác, bên quân mạnh mới có thể bắt được quân đầu tiên của bên kia. Аây là một trong những kết quả gây sốc cho làng cờ Tướng.

IV. Nơi tìm hiểu các CSDLTC
Cờ Vua
Nếu bạn có trong tay các chương trình cờ Vua cao cấp (như Fritz), trong bộ đĩa CD đầy đủ của nó có CSDLTC cờ Vua. Bạn cũng có thể download (miễn phí) các CSDLTC này (tại ftp://ftp.cis.uab.edu/pub/hyatt/) nhưng cần phải có một đường truyền tốc độ cao.

Cờ Tướng
Аối với cờ Tướng, mời sự dường như mới bắt đầu. Trước đây, có một số tác giả đã nghiên cứu và xây dựng CSDLTC cho cờ Tướng. Người bắt đầu sớm nhất có lẽ chính là Ren Wu (thuộc Phòng thí nghiệm Bell). Ngoài ra còn có một vài nhóm ở Аài Loan. Аa số các tác giả không công bố các CSDLTC của họ.
Chúng tôi bắt đầu nghiên cứu và xây dựng CSDLTC cờ Tướng từ giữa năm 2000, kết quả công bố đầu tiên là tàn cuộc một Xe chống lại Sĩ Tượng bờn Аây có lẽ là công trình đầu tiên được công bố cho mời người dùng. Cùng với CSDLTC này chúng tôi đã phát triển chương trình EON (một phần mờm miễn phí) dùng để khai thác CSDLTC này (download tại http://www.xqfan.com/). Sau một thời gian gián đoạn vì những nghiên cứu khác, gần đây chúng tôi đã quay trở lại xây dựng tiếp CSDLTC cờ Tướng (nhà tôi lúc nào cũng có 2 máy tính bậ­t 24 giờ / 24 giờ một ngày và chạy ròng rã không nghỉ nhiều tháng nay để xây dựng CSDLTC đó).

Chương trình EON

Giới hạn
Cũng giống con người, mặc dù với khả năng tính toán phi thường, máy tính cũng bị nhiều giới hạn trong việc nghiên cứu cờ tàn cuộc. Thông thường, chúng tôi chỉ lậ­p được các tàn cuộc chỉ có khoảng 2 quân mạnh, cộng với 1 hoặc 2 quân Chốt. Cái khó của CSDLTC cờ Tướng là tổng số quân tham gia (tính cả các quân phòng ngự) thường tương đối nhiều. Nói chung người nghiên cứu thường phải đối mặt với các thế cờ có trên 10 quân (trong khi cờ Vua hiện tại chỉ khoảng 5 quân). Một bộ CSDLTC cờ Tướng dùng được trong thực tế phải có kích thước từ hàng trăm GB trở lên (trong khi tàn cuộc 5 quân của cờ Vua chỉ chiếm có 8GB, đã được dùng rộng rãi và tờ ra khá hiệu quả). Các tàn cuộc nhiều quân hơn thường nằm ngoài khả năng của cả người và máy do đòi iều quá lớn về kích thước lưu trữ và thời gian chạy máy.

Tuy nhiên, con người vẫn có thể nghiên cứu được một số ngoại lệ. Một ví dụ điển hình là tàn cuộc Pháo, Mã, Chốt, Sĩ Tượng bờn chống lại hai Pháo, hai Sĩ. Một số tác giả đã nghiên cứu thành công (thủ công) và đúc kết cách thắng của tàn cuộc này. Nhưng khi chúng tôi thờ­ bắt tay vào xây CSDLTC thì thấy có vấn đề lớn. Tính toán sơ bộ cho thấy, chúng tôi sẽ phải bờ ra vài khoảng 150 nghìn đô la để mua vài ngàn đĩa cứng về chứa tàn cuộc này. Nhưng điều bất khả là nó đòi iều thời gian tính toán lên đến... 295 năm trên một máy PC hiện đại.

Một thế cờ Xe thắng Sĩ Tượng toàn không có trong bất cứ quyển sách tàn cuộc nào:

Ván cờ:
(Bạn nên bấm vào hình để bật bàn cờ theo dõi thuận tiện hơn)



Bấm vào hình để bật bàn cờ

1. Tg6-5  S6.5 2. Tg5.1  S5/6 3. X9-8  S6.5 4. X8/3  Tg6/1 5. X8-4  Tg6-5 6. X4.1  Tg5-4 7. X4-3  Tg4.1 8. X3.2  S5/4 9. X3/3  S4.5 10. Tg5-6  Tg4/1 11. X3.3  Tg4.1 12. X3-8  S5.6 13. X8-9  Tg4-5 14. X9-6  Tg5-6 15. X6/2
Ý kiến của bạn?

Phạm Hồng Nguyên
Phản hồi từ bạn đọc:
Phan Quoc Viet
Xin chao tac gia bai viet!
Xin dinh chinh mot chut la: Tan cuoc cho 6 quan trong co vua da co roi, va chiem 1,2TB bo nho. Con cho 7 quan khoang 2015 se xong, va chiem khoang 300-400TB.

Tiêu điểm
Hướng dẫn sờ­ dụng XB cho IPhone / IPad
Cờ cười: chơi cờ mời tình huống
Hướng dẫn cài đặt XB cho IPhone
Giới thiệu chương trình XB phiên bản cho IPhone
Cờ cười: Những kiểu kết thúc
Cờ thế
Ván cờ hay
Nghiên cứu cờ tàn bằng máy tính
Cờ Tướng Khai cuộc cẩm nang: Chương III Cách đi hậ­u (2)
Cờ Tướng Khai cuộc cẩm nang: Chương II Những nguyên tắc cơ bản trong khai cuộc (7)
Cờ Tướng Khai cuộc cẩm nang: Chương II Những nguyên tắc cơ bản trong khai cuộc (6)
Cờ Tướng Khai cuộc cẩm nang: Chương II Những nguyên tắc cơ bản trong khai cuộc (4)
Cờ thế



Chuyên đề & Bài hay
 
Hit: 1771448