Nghiên cứu cờ tàn bằng máy tính - cập nhật những nghiên cứu mới

Trong topic này tôi sẽ cập nhật những nghiên cứu mới nhất trong lĩnh vực cờ tàn.
Để bắt đầu mời các bạn đọc lại bài giới thiệu, viết năm 2003, 14 năm trước đây:

-----------------

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 (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 hỏi toàn bộ quá trình đi quân phải rất chính xác. Do số quân lớn, đòi hỏi 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 hỏi 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 ?ocẩ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 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. Hiện nay 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 vài tuần. CSDLTC Nalimov là loại phổ biến nhất trong thế giới cờ Vua.

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 mỗi 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à... ?omệ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 ?ochạ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ì 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.

Ví dụ, có bạn hỏi 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 trắng (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 đen 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%. Bạn có thể xem một số thông tin về thế cờ này tại địa chỉ:
http://www.nchess.com/forum/viewtopic.php?t=179.

Đối với người nghiên cứu và kỳ thủ cao cấp:
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 trắng (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 đen đế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.nchess.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 hỏi máy lời giải. Nếu bạn không ?othí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 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 (nhà nghiên cứu của 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.nchess.com/download.html). 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 đó).

Một số kết quả thú vị các bạn có thể tìm thấy ở diễn đàn Cờ Tướng Máy (Computer Chinese Chess http://www.nchess.com/forum/)

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ừ trăm GB trở lên (trong khi 8 GB của cờ Vua đã đượ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. 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 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 hỏi thời gian tính toán lên đến... 295 năm trên một máy PC hiện đại (chi tiết tại: http://www.nchess.com/forum/viewtopic.php?t=200).


Hi vọng các bạn có thêm được một chút thông tin vui và bổ ích

PHN

Chào chú ! Cho cháu mạn phép hỏi chú có phải là Pham Hong Nguyen, người viết chương trình cờ tướng Saola hơn 10 năm trước phải không ? Nếu đúng, thì cháu rất vui mừng khi chú vẫn còn hứng thú với bộ môn này. Như chú nói, bàn cờ trải rộng lại thêm bộ sĩ tượng khiến cho việc xây dựng CSDLTC rất tốn kém thời gian và tiền bạc. Theo thiển ý của cháu thì làng cờ tướng Việt Nam hiện nay đang cần một phần mềm giống như Chessbase bên cờ vua, hơn là CSDLTC. Mọi người hiện nay chủ yếu xài CCBridge crack, đòi hỏi người chơi phải biết chút ít về tin học mới sử dụng được. Cháu rất mong chú dành thời gian viết 1 chương trình XiangqiBase chứa CSDL ván đấu giống SAOLA + chức năng tìm vị thế tương tự SCID cờ vua + thêm Engine ngoài vào để phân tích. Nếu được như vậy, anh em yêu cờ ngày càng có cơ hội nghiên cứu nâng cao trình độ. Cháu cũng đề nghị chú nên làm phần mềm trả phí thay vì miễn phí, có như vậy mới lâu dài.

Cảm ơn em vì bài viết!

Thêm chức năng không khó. Vấn đề ở đây là có rất ít người dùng. Tôi vẫn cập nhật chương trình XB (Xiangqi Browser) trên iOS, cho xem và tìm kiếm với các CSDL cờ. Người thường chỉ dùng được các chức năng rất cơ bản, còn đến mức tìm kiếm phức tạp hơn như em nói thì chỉ rất ít. Chính vì vậy tôi thường giữ cho các tiện ích của tôi đơn giản nhất có thể.

Cờ máy là thú vui (hobby) chính của tôi nên không bỏ, cho dù có thời gian dài tôi không viết engine (chỉ mới quay lại việc này có vài tháng nay). Đơn giản cái này không phải là nghề sống được, cho dù có bán cả nghìn đô một bản như cyclone hay xqms.

Tôi không đơn thuần là người viết chương trình cờ mà còn là người nghiên cứu. Cái gì khó, thiên hạ sợ tránh lại là mảnh đất khai phá cho người làm nghiên cứu. Dù những công việc dạng này thường không mang lại kinh tế, thậm chí còn phải tiêu pha đắt đỏ, tốn công tốn sức... nhưng cũng thật sự thách thức, thú vị và có lợi cho khoa học kỹ thuật.

Trích dẫn:

---

Gửi bởi chezz

Cảm ơn em vì bài viết!

Thêm chức năng không khó. Vấn đề ở đây là có rất ít người dùng. Tôi vẫn cập nhật chương trình XB (Xiangqi Browser) trên iOS, cho xem và tìm kiếm với các CSDL cờ. Người thường chỉ dùng được các chức năng rất cơ bản, còn đến mức tìm kiếm phức tạp hơn như em nói thì chỉ rất ít. Chính vì vậy tôi thường giữ cho các tiện ích của tôi đơn giản nhất có thể.

Cờ máy là thú vui (hobby) chính của tôi nên không bỏ, cho dù có thời gian dài tôi không viết engine (chỉ mới quay lại việc này có vài tháng nay). Đơn giản cái này không phải là nghề sống được, cho dù có bán cả nghìn đô một bản như cyclone hay xqms.

Tôi không đơn thuần là người viết chương trình cờ mà còn là người nghiên cứu. Cái gì khó, thiên hạ sợ tránh lại là mảnh đất khai phá cho người làm nghiên cứu. Dù những công việc dạng này thường không mang lại kinh tế, thậm chí còn phải tiêu pha đắt đỏ, tốn công tốn sức... nhưng cũng thật sự thách thức, thú vị và có lợi cho khoa học kỹ thuật.

---

Chào anh. Em là 1 nghiên cứu sinh đang học ở Úc, ngành Toán Tin. Em có nghiên cứu khá nhiều về Machine Learning và Optimization. Em rất muốn học hỏi nhiều đièu từ anh cũng như muốn giúp đỡ anh trong việc cải thiện khai phá engine. Là 1 người đam mê nghiên cứu và cũng mê cờ, rất hy vọng em có thể cùng anh tìm đc 1 mảng gì đó để cùng hợp tác thành công. Thân.

Trích dẫn:

---

Gửi bởi imagination

Chào anh. Em là 1 nghiên cứu sinh đang học ở Úc, ngành Toán Tin. Em có nghiên cứu khá nhiều về Machine Learning và Optimization. Em rất muốn học hỏi nhiều đièu từ anh cũng như muốn giúp đỡ anh trong việc cải thiện khai phá engine. Là 1 người đam mê nghiên cứu và cũng mê cờ, rất hy vọng em có thể cùng anh tìm đc 1 mảng gì đó để cùng hợp tác thành công. Thân.

---

P/S: nchess ko vào đc anh.

Trích dẫn:

---

Gửi bởi imagination

Chào anh. Em là 1 nghiên cứu sinh đang học ở Úc, ngành Toán Tin. Em có nghiên cứu khá nhiều về Machine Learning và Optimization. Em rất muốn học hỏi nhiều đièu từ anh cũng như muốn giúp đỡ anh trong việc cải thiện khai phá engine. Là 1 người đam mê nghiên cứu và cũng mê cờ, rất hy vọng em có thể cùng anh tìm đc 1 mảng gì đó để cùng hợp tác thành công. Thân.

---

Hi imagination, rất vui được biết em. Em đang ở thành phố nào vậy? Có thể chúng ta sẽ có nhiều cơ hội gặp nhau.

Về ML nói chung tôi không còn làm trực tiếp nữa. Tuy vậy tôi có các nhóm sinh viên cũ (giờ đang làm việc ở một số Đại học trong và nước ngoài) vẫn theo đuổi. Họ cũng đặc biệt mạnh về NLP. Tôi có thể giúp các em liên kết.

Riêng cờ thì tôi vẫn theo đuổi và làm mọi thứ liên quan. Nếu em định viết các engine mạnh (đọ với các engine hàng đầu của TQ) thì tôi sẵn sàng hỗ trợ tối đa (nhưng cái này khó viết bài nghiên cứu nhé). Trước tôi không tin lắm vào việc dùng NN cho cờ, nhưng từ ngày chương trình Alpha Go của GG thành công thì cũng thấy đó là hướng nên thử.

PS:
- Cái tên miền nchess tôi bị mất lâu rồi, giờ đang dùng xqfan.com cho cờ
- Trao đổi thêm thông qua hộp thư nhé

Chào anh Phạm Hồng Nguyên !

Trước tiên xin mạn phép được gọi là anh vì cũng đoán chắc hơn mình ít tuổi.

Xin được giới thiệu mình tên Hoàng Trung Hiếu, 43 tuổi, hiện sinh sống tại thành phố Hồ Chí Minh.
Tốt nghiệp đại học khoa học tự nhiên tp HCM, ngành toán tin.

Mình là người rất yêu cờ tướng ( nhưng chơi hơi bị tệ, hihi ), hiện tại mình mới làm xong website clbbandao.com, và app chơi cờ tướng, cờ úp có tên Tượng Kỳ ( đã up lên google play và app store vui lòng search với từ khóa "tượng kỳ cờ tướng" có dấu đầy đủ ), hiện tại cũng là phó chủ nhiệm câu lạc bộ cờ tướng Bàn Đào ở tp HCM (clb mới thành lập, chưa ra mắt mọi người, tiền thân là quán cà phê Bàn Đào).

Kế hoạch là hết tháng 12/2017 sẽ chính thức triển khai câu lạc bộ, website, app Tượng Kỳ vào thực tế ( website đang trong giai đoạn tạo dữ liệu ).

Cũng xin nói, trong website và app Tượng Kỳ, mình áp dụng thuật toán tìm nước đi của anh Phạm Hồng Nguyên( mình chuyển từ ngôn ngữ C++ sang java script và java ). Mình cũng có ý muốn viết engine cờ tướng nhưng chưa hiểu nhiều về nó, nay tình cờ gặp được anh ở đây, mình rất mong được anh giúp đỡ trong việc viết engine chơi cờ tướng.

Mong nhận được hồi âm của anh, email của mình
hieuht2002@gmail.com

Thân chào

Chào Hiếu, rất vui được làm quen ở đây. Hi vọng có lúc được thăm clb của các bạn.

Tôi rất sẵn sàng giúp / hỗ trợ các bạn, đặc biệt những ai tâm huyết và sẵn sàng đi lâu đi sâu về môn này. Mong muốn của tôi là có VN có vài nhóm và vài chương trình cờ thuộc hàng đầu.

Hồi năm 2000 sau Giải cờ máy (ĐHQG HN) đã có một vài nhóm như vậy. Tôi đã từng rất hi vọng, đặc biệt là một nhóm ở SG, họ đã phát triển chương trình cờ trong vài năm liền, lúc đó chơi khá tốt. Rất tiếc cuối cùng lại mất hút.

Hi vọng giờ chúng ta sẽ có một số nhóm theo đuổi :)

Có gì chúng ta trao đổi kỹ hơn trong PM nhé.

Chào anh Nguên !

Rất vui khi nhận được hồi âm của anh, anh cho mình xin địa chỉ mail nhé. Mình có rất nhiều điều muốn nói và muốn hỏi, nhưng không tiện nói trên diễn đàn.

Anh yên tâm là đã có người muốn theo đuổi môn cờ theo định hướng chiều sâu và chuyên nghiệp.

Địa chỉ mail của mình
hieuht2002@gmail.com

Thân chào

Đã gửi mail:)

Hy vọng thời gian tới các bác có phần mềm đánh ngang ngửa Typhoon :)

những người có tầm và có tâm đây rồi:khivotay

Trích dẫn:

---

Gửi bởi convit

Hy vọng thời gian tới các bác có phần mềm đánh ngang ngửa Typhoon :)

---

Hy vọng là vậy :)

Nhưng tỉnh táo mà nói thì điều đó rất khó xẩy ra, nhất là trong “thời gian tới”.

Những người lập trình cho Cyclone, XQMS... đã viết và cập nhật liên tục chương trình của họ từ rất lâu rồi, 10 - 15 năm liên tục. Có thể họ cũng kiếm sống bằng những phần mềm đó luôn (căn cứ vào giá cao và tốc độ họ cập nhật) nên có thể chúng được họ đầu tư toàn thời gian. Họ lại sống trong cái nôi của cờ Tướng, với vô thiên lủng sách vở, người đam mê, chuyên gia... xung quanh, sẵn sàng giúp họ mỗi khi cần. Tôi biết các phần mềm này thường được các kỳ thủ giỏi nhất chơi thường xuyên và góp ý, có các nhóm chuyên gia chuyên phân tích cờ thế cho họ.

Tôi viết cờ như một thú vui, không phải nghề. Thời gian đầu tư bị đứt đoạn và cũng không nhiều. Tài liệu, dữ liệu, người cộng tác... không nhiều và không thể sánh được với họ. Ngoài ra tôi còn là nhà nghiên cứu, la cà những chỗ nào mình thích chứ không tập trung vào mỗi engine. Có gì hay thường mang ra chia xẻ chứ không giữ rịt làm của riêng, bí kíp riêng như những người sống bằng nghề này. Ví dụ hiện nay tôi vẫn đang “lang thang” trong lĩnh vực cờ tàn. Vừa tặng (miễn phí) tác giả chương trình Sachess một bộ thư viện mã nguồn và dữ liệu cờ tàn. Có thể thời gian tới Sachess sẽ được phát hành kèm chúng. Tương lai gần sẽ còn vài phần mềm đỉnh cao sẽ dùng thư viện này (hoặc nhái theo).

Cuộc chiến “giảm cân”

Một vấn đề lớn với các cơ sở dữ liệu tàn cuộc (Endgame tablebase - viết tắt CSDLTC) là kích thước cực kỳ khổng lồ của chúng. Việc tạo ra chúng luôn là vấn đề nan giải. Người ta phải dùng máy tính đắt tiền, chạy ròng rã hàng tháng, thậm chí hàng năm trời. Tuy vậy phần tạo còn có thể được một số cá nhân hoặc tổ chức “cố” được thì để phổ biến chúng lại không cố được khi các CSDLTC mới nhất thường vượt quá khả năng download và lưu trữ trong máy tính của người dùng bình thường. Do đó việc “giảm cân” cho các CSDLTC (xuống đến mức người dùng chấp nhận được) luôn là bài toàn hóc búa, thách thức và cũng là chìa khoá thành công của chúng.

Chúng ta điểm qua cuộc chiến này.

I. Cờ Vua

1) Thompson
Đây là CSDLTC đầu tiên trên Thế giới, cho 3, 4 và 5 quân cờ (3-4-5 men), được tạo bởi Thompson. Ông là nhà nghiên cứu người Mỹ làm việc tại phòng thí nghiệm Bell danh tiếng. Ông bắt đầu tạo CSDLTC này từ giữa những năm 1970, sử dụng máy tính lớn thời đó và phải đến giữa những năm 1980 mới hoàn thành. Ông dùng vài phương pháp mã hoá đơn giản và thuật toán nén cũng đơn giản nên CSDLTC của ông rất lớn, ước chừng tổng kích thước của CSDLTC trên 50 GB. Để hiểu kích thước này khổng lồ đến thế nào, chúng ta xem ví dụ sau: những năm đầu 1990 khi máy tính PC bắt đầu phổ biến ở VN, chúng tôi thường dùng các đĩa mềm to hơn bàn tay nhưng chỉ chứa được khoảng 360 KB (tức là phải cần đến cả hộp đĩa chục cái như vậy để chứa được một cái ảnh số hoặc một bản nhạc bây giờ). Một người dùng máy tính thời đó thường chỉ có một vài hộp đĩa. Như vậy phải cần đến 140 nghìn cái đĩa mềm đó mới chứa hết dữ liệu của Thompson. Sau đó các đĩa cứng bắt đầu xuất hiện ở VN, kích thước rất “khổng lồ” (so với đĩa mềm) nhưng... cũng chỉ khoảng vài MB. Lúc đó ở nước ngoài đã phổ biến Internet, nhưng tốc độ đường truyền lúc đó cũng vô cùng chậm (so với tốc độ Internet ngày nay). Không ai có ý định download từng đó dữ liệu.

https://upload.wikimedia.org/wikiped...sk_2009_G1.jpg
Đĩa mềm giữa (mầu cam, loại 5 1/2 inch, 360 KB) phổ biến ở VN những năm đầu 1990

Tất cả các điều trên làm cho CSDLTC của Thompson không phổ biến. Hầu như không ai dùng ngoại trừ... chính tác giả. Thế là cứ thỉnh thoảng ông lại viết một bài báo (báo khoa học chứ không phải báo thường, phổ thông). Thường là về loại tàn cuộc này thắng hay thua, đi như thế nào thì thắng, thắng trong bao nhiêu nước..., dựa trên phân tính CSDLTC của ông. Phải có cả chục bài báo nghiên cứu như vậy.

Tình trạng cô lập, có không ai dùng đó kéo dài cho đến khi đĩa CD bắt đầu phổ biến. Thompson tìm cách nén CSDLTC cho nhỏ thêm, cắt bớt một số tàn cuộc để cuối cùng dữ liệu của ông còn khoảng 2.5 GB lọt vừa bốn đĩa CD. Lúc này ông có thể phân phát chúng cho người khác (từ năm 1991). Lúc đầu rất oái oăm với những người viết phần mềm Thompson không bán mà chỉ lấy phí phát hành, cộng thêm điều kiện người viết phần mềm phải cho ông xem mã nguồn chương trình của họ - không phải ai cũng thích điều này (về sau đó ông cũng bỏ điều kiện này). Do kích thước dữ liệu vẫn còn quá lớn so với lúc đó mà vẫn thiếu rất nhiều (4 đĩa CD chỉ chứa được cỡ 1/20 dữ liệu mà thôi), phần giải nén chạy không ổn định, nên người ta không dùng được CSDLTC này trong lúc engine đang tìm kiếm (vì nó chạy quá chậm, ảnh hưởng rất lớn đến tốc độ), mà chỉ dùng được khi ván cờ đã chuyển về cờ tàn. Do vậy việc dùng CSDLTC của Thompson không giúp nhiều cho engine, có chăng là thỉnh thoảng giúp nó chơi cờ tàn tốt hơn. Do vậy người viết phần mềm không mặn mà gì và có rất ít phần mềm dùng CSDLTC Thompson.

Điều đáng tiếc là hồi đó phong trào chia xẻ mã nguồn không mạnh như bây giờ. Do vậy dù đã chia xẻ rất nhiều ý tưởng, dữ liệu, mã nguồn cần để làm việc với các dữ liệu đó,... nhưng Thompson lại ít đề cập những phần kiến thức sâu nhất và quan trọng nhất của ông, giữ kín phần mã nguồn và cả thuật toán dùng để tạo CSDLTC. Chính vì vậy một thời gian dài (cùng với nhiều khó khăn khác) có rất ít người học theo và tạo CSDLTC.

Đóng góp nhiều nhất của Thompson ngoài việc đưa ra CSDLTC đầu tiên, chứng minh có thể tạo và sử dụng được chúng với engine còn là các ý tưởng. Không phải mọi cái ông đều thực hiện nhưng ông có rất nhiều ý tưởng hay, mang tính cách mạng. Tất cả các CSDLTC về sau nói cho cùng cũng chỉ là thực hiện ý tưởng của ông và làm tốt hơn mà thôi.

http://images.computerhistory.org/ch...pson.jpg?w=600
Thompson là người cầm cup đứng giữa ảnh

Trích dẫn:

---

Gửi bởi chezz

Trước tôi không tin lắm vào việc dùng NN cho cờ, nhưng từ ngày chương trình Alpha Go của GG thành công thì cũng thấy đó là hướng nên thử.

---

Vừa rồi nhóm Google DeepMind đã áp dụng NN cho cờ vua và đã đánh bại stockfish chỉ sau 4 giờ tự học. Như vậy có cơ sở NN cũng có thể ứng dụng tốt cho cờ tướng.

Giới cờ máy cũng đang rất xôn xao về sự kiện này (AlphaZero đánh bại Stockfish). Tôi cũng vừa viết một bài tổng kết về việc này, sẽ đăng ở đây sau. Nếu sửa AlphaZero chơi cờ Tướng thì gần như cầm chắc nó sẽ thắng mọi chương trình cờ Tướng hiện tại. Vấn đề giờ lại là làm sao khắc chế được kiểu học - chơi của AlphaZero và làm sao chạy được các chương trình như AlphaZero trên máy PC thường (giờ nó đang chạy trên máy lớn)

Rất mong được xem con AlphaZero này đánh với Cyclone, có lẽ Alphazero sẽ thắng thôi nhưng chắc sẽ được xem những ván cờ rất đã mắt, vừa nhìn biên bản mấy ván nó đánh với Stockfish, không hiểu sao nó học có 4 tiếng mà đánh ra được những ván cờ khủng khiếp như vậy.

(tiếp)

2. Edwards
Steven Edwards là một nhà khoa học máy tính người Mỹ. Thay cho cách mã hoá đơn giản như Thompson, ông dùng nhiều loại phức tạp hơn. Ông cũng chuẩn hoá dữ liệu xuyên suốt giữa các tàn cuộc (dùng DTM thay cho DTC) và dùng một kiểu nén mới. Tận dùng tốc độ Internet lúc đó đã nhanh hơn đáng kể thời Thompson, ông đã tạo và đặt dữ liệu của mình lên một số máy chủ cho download miễn phí.

Khi Edwards tung ra CSDLTC của mình năm 1993 đó là chấn động trong làng cờ máy vì từ bây giờ người ta đã có thể dễ dàng download và sử dụng các CSDLTC. Nhiều chương trình cờ lúc đó bắt đầu tích hợp với CSDLTC của Edwards.
CSDLTC của Edwards thực ra không nhỏ hơn Thompson, nhưng nó lại được phổ biến hơn, trước hết vì nó đầy đủ (Thompson chỉ phát hành một phần), sau là chạy nhanh, ổn định hơn và dễ dùng hơn nhiều - giờ người ta đã có thể kết hợp nó với phần tìm kiếm của cờ. Một lý do quan trọng khác là nó được phát hành miễn phí và hoàn toàn qua Internet.

Điều đáng tiếc là sau khi tung ra CSDLTC, Edward lại mất hứng thú với việc tiếp tục nghiên cứu cải tiến và tung ra CSDLTC đầy đủ hơn. Khi tung ra CSDLTC của ông chỉ có 4 quân và mãi ông mới hoàn thành bản 5 quân. Ông cũng không đầu tư nhiều vào việc nén dữ liệu khiến nó vẫn còn lớn và chạy chậm. Toàn bộ CSDLTCs cho 5 quân phải trên 50 GB (một số người cho rằng nó còn lớn hơn cả tiền nhiệm của Thompson). Vì những lý do đó CSDLTC này nhanh chóng mất chỗ đứng khi có CSDLTC tốt hơn của Nalimov (đề cập trong phần tiếp theo).

Tuy vậy, đóng góp lớn của Edward còn mãi đến sau này là ông đã thực hiện một số cách mã hoá thế cờ (Index scheme) giúp cho giảm kích thước các CSDLTC đi nhiều lần, dù nhiều cái là ý tưởng của Thompson. Ông còn hào phóng phổ biến toàn bộ mã nguồn dùng để tạo ra CSDLTC, khiến cho những người đi sau có để dễ dàng học hỏi và phát triển các phương pháp khác. Hầu hết các CSDLTC về sau đều giống với CSDLTC của Edwards.
Cũng bắt đầu từ Edwards người ta chủ yếu download các CSDLTC thay vì cung cấp qua đĩa CD/DVD. Phần lớn chúng được cho download miễn phí.


3. Nalimov
Nalimov là một lập trình viên người Nga nhưng sống và làm việc tại Mỹ. CSDLTC của Nalimov khá giống với của Edwards, bắt đầu phát hành năm 1998. Nalimov bổ xung thêm một vài loại mã hoá bàn cờ nữa để giảm kích thước. Ông (chính xác hơn là một người bạn của ông - nhưng người ta vẫn quen cho rằng đó là việc của ông) dùng một phương pháp nén dữ liệu tốt và nhanh hơn những gì người ta từng dùng. Từ đây về sau người ta thường dùng các CSDLTC ở dạng nén chứ không để “trần” ra như trước nữa. Kết cục là CSDLTC này ở dạng không nén nhỏ hơn của Edwards khoảng 2 lần, nhưng khi ở dạng nén lại nhỏ hơn của Edwards (cũng nén) khoảng 8 lần.

Nhờ kích thước nhỏ, phần giải nén chạy nhanh và ổn định, cùng với việc nó có đủ dữ liệu cho 5 quân (có tổng kích thước cỡ 7 GB) ngay từ những ngày đầu đã khiến CSDLTC của Nalimov nhanh chóng trở nên phổ biến và thống trị làng cờ máy từ năm 1998 đến gần đây. Nalimov lần lượt tạo và cung cấp các tàn cuộc 6 quân và đến năm 2005 (sau 7 năm) thì hoàn thành toàn bộ CSDLTC 6 quân (có tổng kích thước cỡ 1.2 TB). Tuy bản 6 quân khá lớn nên khó khăn để download và lưu trữ nhưng nhiều người không quản ngại vẫn download chúng.

Cũng dựa trên cách mã hoá và cách nén dữ liệu của Nalimov, nhiều nhà nghiên cứu đã đưa ra một số CSDLTC khác. Ví dụ phổ biến trong số đó là CSDLTC Gaviota của Michael, Bitbase của phần mềm Scorpio. Thường các CSDLTC này nhỏ hơn Nalimov một chút. Tuy có nhỏ hơn nhưng chúng không thật sự ấn tượng nên không lấn át được Nalimov, mà chúng cùng chung sống, có những nhóm người dùng trung thành riêng.


https://chessprogramming.wikispaces....76/nalimov.jpg

4. Lomonosov
Sau sự ra đời của CSDLTC Nalimov 6 quân, cộng đồng cờ máy đã ngay lập tức bắt tay vào xây dựng CSDLTC cho 7 quân từ giữa những năm 2000. Chỉ một quân thêm vào thôi đã làm dữ liệu tăng trên 100 lần và đòi hỏi máy tính phải có bộ nhớ khổng lồ để xây dựng nên chúng rất đắt đỏ, tốn hàng chục nghìn đô (kể cả đến năm nay 2017). Người ta cũng tính rằng phải mất nhiều năm nữa mới làm xong.

Ronald de Man tác giả của syzygy, người đã viết phần tạo CSDLTC nhanh nhất hiện nay đã ước chừng để bộ tạo CSDLTC của ông làm việc với 7 quân thì cần có máy tính có 1 TB bộ nhớ và chạy máy 5, 6 năm. Hiện thị trường máy tính đang phổ biến các thanh RAM 16 GB. Như vậy cần trên 60 thanh, riêng số RAM này tốn cỡ 15 nghìn đô.

Thỉnh thoảng có nhà nghiên cứu tuyên bố làm xong một vài tàn cuộc đơn lẻ. Ví dụ ông đã tuyên bố tìm ra ván cờ tàn dài đến trên 500 nước.

Cuối cùng điều bất ngờ đã xẩy ra. Năm 2013 CSDLTC 7 quân được tuyên bố đã tạo xong. Hai tiến sĩ Zakharov và Makhnichev ở trường Đại học Tổng hợp Quốc gia Lomonosov (Nga) dùng siêu máy tính của trường (có trên 50 nghìn bộ vi xử lý, tổng bộ nhớ RAM trên 90 TB), chạy ròng rã 6 tháng để xây dựng nên CSDLTC này. Do đó hai ông đã lấy tên của trường làm tên cho CSDLTC. Nó có kích thước lên tới 140 TB - máy tính để bàn của tôi có đĩa cứng 1 TB - phải cần 140 máy tính như vậy. Vì kích thước lớn người ta không phát hành được - giống như tình trạng của Thompson lúc ban đầu. Tuy vậy người ta cho phép người dùng truy cập nó qua Internet. Nhưng do tốc độ Internet chậm, không ai dùng nó cho engine mà chủ yếu chỉ để tra cứu hay nghiên cứu. Trang web này lại chỉ cho dùng miễn phí với rất nhiều hạn chế, người dùng thật sự phải trả phí nên cũng là một hạn chế lớn.

Ví dụ thế cờ dưới đây là cờ tàn giữa hai danh thủ Steinitz và Gunsberg trong giải Vô địch Thế giới (New York, 1890-1891). Ván cờ có kết quả hoà nhưng người ta cho rằng Gunsberg có thể thắng. Sau nước 73. Ra4+ ông đã đi 73…Kf3. Nhưng theo Lomonosov CSDLTC ông sẽ thắng ván cờ nếu đi 73…Kd5, lời giải sau 122 năm.

http://chessok.com/wp-content/upload...diagram002.png

(Còn tiếp)

5. Syzygy

Syzygy (tên của hiện tượng thiên văn có ba hành tinh sắp thẳng hàng) do Ronald de Man thiết kế và viết chương trình. Ông là một nhà Toán - Tin học đồng thời là một luật sư người Hà Lan. Về cơ bản, nó dùng cách mã hoá tương tự như Edwards / Nalimov. Nó hơi khác Nalimov ở chỗ ông dùng dữ liệu dạng DTZ50 thay cho DTM (cũng một kiểu tìm đường chiếu hết). Điểm đặc biệt là Ronald tập trung vào nén dữ liệu, sử dụng cách thức rất thông minh và cắt bớt dữ liệu của một bên cờ. Tất cả đã làm Syzygy đạt được mức siêu nén, nhỏ hơn tất cả các CSDLTC khác. Tổng kích thước của loại 5 quân cờ giờ chỉ còn dưới 1 GB, nhỏ cỡ 1/7 GB của Nalimov (thực ra nếu có đủ dữ liệu cho cả hai bên thì phải trên 2 GB, tức là nhỏ bằng cỡ 1/3). Còn loại 6 quân chỉ đến 150 GB, nhỏ hơn 3 lần.

Có một điều thú vị: Do có kích thước nhỏ đến bất ngờ, tác giả lại công bố vào ngày 1/4 (năm 2013), nhiều người cứ bán tín bán nghi mãi rằng đó chỉ là một cú lừa (chơi khăm), một trò đùa Cá tháng Tư!

Khi công bố, Ronald chỉ cung cấp các chương trình (dạng mã nguồn), không có phần dữ liệu. Nhưng chỉ sau một thời gian ngắn, một vài người dùng dùng các công cụ do Ronald cung cấp đã tạo ra các CSDLTC Syzygy 5 và 6 quân cờ.

Do có kích thước nhỏ ấn tượng này, người dùng đã có thể dễ dàng download và lưu trữ. Ngay lập tức Syzygy trở nên phổ biến khi có hàng loạt người viết cờ và người dùng quay ra sử dụng nó. Nhiều người ví von rằng CSDLTC Nalimov đã trở thành đồ cổ. Vẫn có người dùng nhưng sẽ ngày càng ít đi.

Ở giải cờ máy vô địch thế giới năm 2017, trong 4 chương trình đỉnh cao tham gia, chỉ có một dùng Nalimov. Ba cái kia dùng Syzygy. Còn năm nay 2018 toàn bộ chương trình thi đấu đều dùng Syzygy.

Khi tôi đang chuẩn bị đăng phần viết trước thì nhận được tin sốc cả làng cờ: Bojun Guo một lập trình viên Trung Quốc đã hoàn thành CSDL Syzygy 7 quân cờ. Anh ta đã chạy chương trình này trên một máy vi tính có 8 bộ vi xử lý Intel Premier với tổng luồng lên tới 384. Riêng số CPU này có trị giá hơn 50 nghìn đô. Cùng với bộ nhớ rất khủng nữa 1.5 TB và loạt đĩa cứng đắt tiền khiến cả cỗ máy có giá trên 90 nghìn đô. Anh ta đã chạy chương trình ròng rã trong 5 tháng để tạo ra CSDL 7 quân. Đó là khối lượng công việc mà cỗ siêu máy tính trị giá 63 triệu tại Đại học Lomonosov phải chạy trong 6 tháng.

(còn nữa: phần tiếp theo sẽ viết về CSDLTC của cờ Tướng :) )