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

[chezz]

(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.

[chezz]

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.



(Còn tiếp)

[chezz]

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 )