Số Shannon 10 mũ 120: cờ vua, cờ vây có bao nhiêu ván khác nhau

Số Shannon là ước tính khoảng 10¹²⁰ ván cờ vua khác nhau có thể xảy ra, do Claude Shannon đưa ra năm 1950. Con số này lớn hơn số nguyên tử trong vũ trụ quan sát được (khoảng 10⁸⁰) tới 40 bậc. Cờ vây còn vượt xa: riêng số thế cờ hợp lệ trên bàn 19 × 19 đã là khoảng 2,08 × 10¹⁷⁰, được đếm chính xác năm 2016.

Shannon tính ra 10¹²⁰ thế nào

Năm 1950, Claude Shannon, người đặt nền móng cho lý thuyết thông tin, công bố bài báo "Programming a Computer for Playing Chess" trên tạp chí Philosophical Magazine. Đây là một trong những bài đầu tiên bàn nghiêm túc về việc lập trình máy tính chơi cờ vua. Để cho thấy vì sao máy không thể đơn giản là thử hết mọi khả năng, ông làm một phép ước lượng rất thô:

1. Ở một thế cờ điển hình, mỗi bên có khoảng 30 nước đi hợp lệ.
2. Một lượt đi của cả trắng lẫn đen cho khoảng 30 × 30 ≈ 1.000 = 10³ khả năng.
3. Một ván cờ điển hình kéo dài khoảng 40 lượt như vậy.
4. Tổng số ván: (10³)⁴⁰ = 10¹²⁰.

Shannon nói rõ đây là ước tính cỡ bậc, không phải phép đếm. Nhưng nó đủ để kết luận: ông viết rằng một cỗ máy xét mỗi biến thể chỉ trong một phần triệu của micro giây vẫn cần hơn 10⁹⁰ năm để xét hết. Vũ trụ mới khoảng 1,4 × 10¹⁰ năm tuổi. Vì vậy máy chơi cờ phải biết chọn lọc, không thể vét cạn.

Bạn có thể tự kiểm phép tính ấy: một phần triệu micro giây là 10⁻¹² giây, tức máy xét 10¹² biến thể mỗi giây. 10¹²⁰ chia 10¹² được 10¹⁰⁸ giây; một năm khoảng 3,15 × 10⁷ giây, chia ra được khoảng 3 × 10¹⁰⁰ năm. Kết quả tính lại còn lớn hơn con số "hơn 10⁹⁰ năm" ông ghi, nên chữ "hơn" của Shannon là rất khiêm tốn. Đằng nào kết luận cũng như nhau.

Đếm thật vài nước đầu: con số bùng nổ nhanh cỡ nào

Với vài nước đầu tiên, máy tính đã đếm chính xác được số chuỗi nước đi có thể có. Mỗi "nửa nước" (ply) là một lần đi của một bên:

Chỉ sau ba lượt trắng và ba lượt đen, đã có hơn 119 triệu cách đi khác nhau. Mỗi nửa nước nhân thêm khoảng 20 tới 30 lần. Đây là một ví dụ tăng theo cấp số nhân rất cụ thể: không có quy luật nào bí ẩn, chỉ là mỗi bước lại nhân với một số không nhỏ.

Hai con số khác nhau: số ván và số thế cờ

Người ta hay nhầm hai đại lượng:

• Số thế cờ: có bao nhiêu cách sắp quân hợp lệ trên bàn. Nhiều ván khác nhau có thể đi tới cùng một thế.
• Số ván (hay độ phức tạp của cây nước đi): có bao nhiêu chuỗi nước đi khác nhau từ đầu tới cuối.

Với cờ vua, Shannon ước số thế cờ cỡ 10⁴³; các ước tính hiện đại cho kết quả cỡ 10⁴⁴. Số ván thì lớn hơn rất nhiều, cỡ 10¹²⁰ theo Shannon. Nếu tính mọi ván hợp lệ dài nhất có thể theo luật hoà 50 nước, con số còn vượt xa hơn nữa, nhưng những ván đó chẳng ai chơi.

Các con số về số ván ở bảng trên là ước tính cỡ bậc theo những giả định khác nhau của từng tác giả, chỉ nên đọc để so sánh, không nên trích như số chính xác.

Cờ vây: con số được đếm tới từng đơn vị

Bàn cờ vây có 361 giao điểm, mỗi điểm trống, đen hoặc trắng. Vậy có 3³⁶¹ ≈ 1,74 × 10¹⁷² cách tô, nhưng không phải cách nào cũng hợp lệ: theo luật, mỗi nhóm quân phải còn ít nhất một khí (điểm trống kề bên). Tỉ lệ cách tô hợp lệ khoảng 1,2%.

Tháng 1 năm 2016, John Tromp cùng các cộng sự công bố kết quả đếm chính xác số thế cờ hợp lệ trên bàn 19 × 19: một số có 171 chữ số, bắt đầu bằng 2081681993819799846… tức khoảng 2,08 × 10¹⁷⁰. Phép đếm cần nhiều tháng chạy máy chủ và một thuật toán chia bàn cờ thành từng cột để đếm dần.

Cũng trong năm 2016, chương trình AlphaGo thắng kỳ thủ hàng đầu Lee Sedol. Thành công đó không đến từ việc vét cạn, vì với 10¹⁷⁰ thế cờ thì không máy nào vét nổi, mà từ việc máy học cách đánh giá thế cờ và chỉ đọc sâu những nhánh hứa hẹn, đúng như hướng Shannon gợi ý từ 1950.

"Giải xong" một môn cờ nghĩa là gì

Một môn cờ được coi là giải xong khi người ta biết kết quả nếu cả hai bên đều đi hoàn hảo. Cờ ca-rô 3 × 3 thì trẻ con cũng tự giải được: đi đúng thì luôn hoà. Cờ đam 8 × 8 được nhóm của Jonathan Schaeffer ở Đại học Alberta (Canada) giải năm 2007 sau gần hai thập kỷ tính toán với chương trình Chinook: kết quả cũng là hoà.

Với cờ vua, các cơ sở dữ liệu tàn cuộc đã giải xong mọi thế cờ còn từ bảy quân trở xuống (tính cả hai vua). Nhưng từ thế khai cuộc với 32 quân thì còn rất xa. Khoảng cách giữa 10²⁰ của cờ đam và 10⁴⁴ của cờ vua là 24 bậc, mà mỗi bậc là gấp mười lần công việc.

Vì sao các con số này hữu ích

Số Shannon thường bị dùng như một câu ấn tượng: "cờ vua có nhiều ván hơn số nguyên tử trong vũ trụ". Câu đó đúng, nhưng giá trị thật của nó nằm ở chỗ khác.

• Nó cho biết vét cạn là bất khả, nên phải nghĩ cách khác: đánh giá thế cờ, cắt tỉa nhánh, học từ dữ liệu. Toàn bộ ngành trí tuệ nhân tạo cho các môn cờ phát triển từ nhận xét này.
• Nó giải thích vì sao cờ không bao giờ cũ. Dù mỗi ngày có hàng triệu ván được chơi trên mạng, phần lớn ván có độ dài vừa phải sau khoảng hai mươi nước đã đi vào thế cờ chưa từng xuất hiện trong lịch sử.
• Nó là bài học về tổ hợp: không cần vật chất khổng lồ để có số khổng lồ. Chỉ cần một chuỗi lựa chọn nối tiếp nhau.

Góc nhìn hôm nay: tự ước số ván của một môn cờ

Bạn có thể áp dụng phương pháp Shannon cho bất kỳ môn cờ nào chỉ với hai con số: số nước đi trung bình mỗi lượt (b) và số lượt trung bình mỗi ván (d). Số ván xấp xỉ bᵈ.

Thử với cờ ca-rô trên bàn lớn mà học sinh hay chơi trên giấy ô li. Giả sử mỗi lượt có khoảng 100 ô hợp lý để đánh và một ván kéo dài khoảng 40 nước: 100⁴⁰ = 10⁸⁰, vừa bằng số nguyên tử trong vũ trụ. Thay đổi giả định một chút, b = 50 và d = 60, ta được 50⁶⁰ ≈ 10¹⁰². Mỗi giả định cho một con số khác, nhưng tất cả đều nói cùng một điều: không ai có thể chơi hết.

Người muốn đọc nguyên bản có thể tìm bài báo năm 1950 của Shannon, ngắn và rất dễ đọc so với tầm vóc của nó. Muốn xem các con số đếm thật cho cờ vua, có thể tra các bảng đếm "perft" mà người viết phần mềm cờ dùng để kiểm tra chương trình.