Một chương trình chơi cờ cổ điển chọn nước bằng cách tưởng tượng mọi chuỗi nước đi có thể trong vài lượt tới, chấm điểm các thế cờ ở cuối mỗi chuỗi, rồi chọn nước dẫn tới thế tốt nhất với giả định đối phương cũng chơi tốt nhất. Cách chọn này gọi là minimax. Để không phải xét hết hàng tỉ chuỗi, máy dùng cắt tỉa alpha-beta, bỏ qua những nhánh chắc chắn không ảnh hưởng tới quyết định.
Nghe thì đơn giản, nhưng phần lớn sức mạnh của máy cờ nằm ở hàng chục mẹo kỹ thuật được tích luỹ suốt hơn bảy mươi năm: sắp thứ tự nước đi, nhớ thế cờ đã gặp, tìm tiếp ở các thế đang có ăn quân, giảm độ sâu cho nước kém. Bài này giải thích từng ý bằng ngôn ngữ người chơi cờ, không cần biết lập trình. Phần máy cờ dùng mạng nơ-ron có bài riêng trong danh mục.
Cây trò chơi: vì sao máy không thể xét hết
Hãy hình dung thế cờ hiện tại là gốc cây. Mỗi nước hợp lệ của bạn là một nhánh. Từ mỗi nhánh lại toả ra các nước đáp của đối phương, rồi nước tiếp theo của bạn, cứ thế. Đó là cây trò chơi. Ở cờ vua, mỗi thế trung bình có khoảng ba mươi đến bốn mươi nước hợp lệ, nên chỉ sau bốn nước nửa (hai nước mỗi bên) đã có cỡ một triệu chuỗi khác nhau, sau tám nước nửa là hàng nghìn tỉ.
Năm 1950, Claude Shannon, nhà toán học được coi là cha đẻ lý thuyết thông tin, viết bài báo "Lập trình máy tính để chơi cờ", ước tính số ván cờ vua khả dĩ vào cỡ 10 mũ 120. Con số này về sau được gọi là con số Shannon. Ông chỉ ra rằng không máy nào có thể xét hết cây, và đề xuất hai hướng: xét mọi nước tới một độ sâu cố định, hoặc chỉ xét những nước "có vẻ hợp lý" như con người.
Lịch sử máy cờ vua về sau phần lớn đi theo hướng thứ nhất, kèm rất nhiều cách cắt bớt cây. Hướng thứ hai, chọn lọc nước như người, từng bị coi là khó làm cho đến khi mạng nơ-ron xuất hiện và làm chính việc đó.
Minimax: chọn nước khi đối phương cũng chơi tốt nhất
Minimax là cách lấy quyết định từ cây trò chơi. Có thể hình dung bằng một ví dụ giả định rất nhỏ: bạn có hai nước để chọn, mỗi nước đối phương có hai cách đáp.
- Máy liệt kê: nước A, đối phương đáp A1 hoặc A2; nước B, đối phương đáp B1 hoặc B2. Đó là bốn thế cờ cuối.
- Máy chấm điểm bốn thế cờ theo góc nhìn của bạn, điểm dương là có lợi. Giả định A1 được 2 điểm, A2 được 5, B1 được 3, B2 được 4.
- Ở nước A, đối phương sẽ chọn đáp làm bạn khổ nhất, tức A1 với 2 điểm. Vậy giá trị của A là 2. Tương tự, giá trị của B là 3, vì đối phương chọn B1.
- Bạn chọn nước có giá trị lớn nhất trong các giá trị nhỏ nhất đó: B với 3 điểm. Dù A có khả năng ra 5 điểm, nó chỉ ra 5 nếu đối phương chơi dở.
- Với cây thật, máy làm y hệt nhưng qua nhiều tầng: tầng của bạn lấy lớn nhất, tầng của đối phương lấy nhỏ nhất, xen kẽ tới gốc.
Người chơi phong trào hay mắc đúng lỗi minimax tránh được: chọn nước A vì "nếu đối thủ đi sai thì mình thắng đẹp". Máy luôn giả định đối thủ đáp tốt nhất, và đó là lý do nó ít khi đi những nước hy vọng.
Cắt tỉa alpha-beta: bỏ nhánh mà không mất gì
Quay lại ví dụ. Sau khi tính xong nước B được 3 điểm, máy chuyển sang xét nước A. Đáp A1 cho 2 điểm. Lúc này máy biết ngay: dù A2 có bao nhiêu, đối phương vẫn có thể chọn A1 để giữ bạn ở mức tối đa 2, kém hơn 3 của B. Vậy không cần xét A2 nữa. Đó là cắt tỉa alpha-beta: bỏ qua những nhánh chắc chắn không làm thay đổi lựa chọn.
Trên cây thật, mức tiết kiệm rất lớn. Nếu các nước tốt được xét trước, alpha-beta cho phép máy đạt cùng một độ sâu với số thế cờ chỉ cỡ căn bậc hai so với minimax đầy đủ. Nói theo kiểu người chơi: với cùng thời gian, máy nhìn sâu được gần gấp đôi. Điều quan trọng là alpha-beta không làm kết quả kém đi; nó cho đúng nước mà minimax đầy đủ sẽ chọn, chỉ nhanh hơn.
Chữ "nếu các nước tốt được xét trước" là mấu chốt. Vì vậy máy cờ đầu tư rất nhiều vào sắp thứ tự nước: xét trước nước ăn quân giá trị cao bằng quân giá trị thấp, nước từng gây cắt tỉa ở các nhánh anh em (gọi là nước sát thủ), nước đã tốt ở lần tìm nông hơn. Một máy sắp thứ tự kém có thể chậm hơn máy sắp tốt cả chục lần dù cùng thuật toán.
Hàm đánh giá: máy chấm điểm thế cờ bằng gì
Khi dừng tìm ở một độ sâu, máy cần biết thế cờ tốt hay xấu. Máy cờ cổ điển dùng một hàm cộng nhiều thành phần, đơn vị thường là phần trăm giá trị một con tốt (centipawn). Bảng dưới là các thành phần thường gặp, trọng số cụ thể khác nhau giữa các chương trình.
| Thành phần | Máy xét gì | Gần với khái niệm nào của người chơi |
|---|---|---|
| Vật chất | Đếm quân: tốt khoảng 1, mã và tượng khoảng 3, xe khoảng 5, hậu khoảng 9 | Hơn quân, kém quân |
| Vị trí quân | Bảng điểm theo ô: mã ở trung tâm tốt hơn mã ở góc | Quân hoạt động, quân xấu |
| Cấu trúc tốt | Tốt chồng, tốt cô lập, tốt thông, chuỗi tốt | Điểm yếu lâu dài |
| An toàn vua | Số quân đối phương nhắm vào vùng quanh vua, lá chắn tốt | Vua hở, tấn công vua |
| Độ linh động | Số nước hợp lệ của mỗi quân | Không gian, quân bị kẹt |
| Giai đoạn ván | Trọng số đổi khi ít quân: vua nên ra giữa ở tàn cuộc | Khai cuộc, trung cuộc, tàn cuộc |
Hàm đánh giá là chỗ "tri thức cờ" được nạp vào máy cổ điển. Viết thêm một thành phần là chuyện dễ; khó là chỉnh trọng số sao cho các thành phần không đá nhau. Từ năm 2020, nhiều máy cờ cổ điển thay phần lớn hàm này bằng mạng nơ-ron nhỏ, chuyện được kể trong bài riêng của danh mục.
Hiệu ứng chân trời và các mẹo tìm kiếm
Hiệu ứng chân trời. Nếu máy dừng tìm đúng lúc vừa ăn được một quân, nó chấm thế đó là hơn quân, dù nước tiếp theo đối phương ăn lại. Tệ hơn, máy có thể đi những nước câu giờ để đẩy một mất mát chắc chắn ra ngoài tầm nhìn, như người bịt mắt không thấy cái hố. Đây là lỗi kinh điển của máy cờ đời đầu.
Tìm kiếm yên tĩnh (quiescence search). Cách chữa: khi chạm độ sâu dự định, máy chưa chấm điểm ngay mà tiếp tục xét riêng các nước ăn quân (và đôi khi chiếu tướng) cho tới khi thế cờ "yên", không còn trao đổi treo lơ lửng. Chỉ khi đó mới gọi hàm đánh giá.
Đào sâu dần (iterative deepening). Máy tìm ở độ sâu 1, rồi 2, rồi 3… Nghe có vẻ phí, nhưng kết quả lần nông giúp sắp thứ tự nước cho lần sâu, nên tổng thời gian lại ít hơn. Nó cũng cho phép máy dừng bất cứ lúc nào hết giờ mà vẫn có nước tốt nhất đã biết.
Bảng chuyển vị (transposition table). Cùng một thế cờ có thể đến bằng nhiều thứ tự nước khác nhau. Máy lưu kết quả các thế đã tính vào một bảng băm để khỏi tính lại. Với người chơi, đây giống như nhận ra "thế này mình đã gặp ở biến khác rồi".
Giảm độ sâu cho nước muộn và nước rỗng. Máy cờ hiện đại tìm nông hơn với các nước xếp cuối danh sách, vì khả năng chúng tốt thấp. Mẹo nước rỗng: thử "bỏ lượt"; nếu bỏ lượt mà thế vẫn quá tốt thì nhánh này chắc chắn tốt, cắt luôn. Những mẹo này đánh đổi một chút độ chính xác lấy rất nhiều độ sâu.
Khi bạn bấm nút phân tích, máy làm gì trong vài giây đó
Sinh nước hợp lệ. Việc đầu tiên là liệt kê mọi nước đúng luật, kể cả nhập thành, bắt tốt qua đường, phong cấp, và loại các nước để vua bị chiếu. Bộ sinh nước phải cực nhanh và tuyệt đối đúng, vì nó chạy hàng triệu lần mỗi giây; một lỗi nhỏ ở đây làm hỏng mọi thứ phía sau.
Tìm nông để có câu trả lời ngay. Máy tìm ở độ sâu một, hai, ba nước nửa trong tích tắc, nên màn hình hiện ra nước gợi ý gần như tức thì. Mỗi vòng sâu hơn, máy cập nhật biến chính và con số đánh giá.
Đào sâu theo biến chính. Phần lớn thời gian dồn vào biến chính, chuỗi nước máy đang cho là tốt nhất cho cả hai bên. Các nhánh khác chỉ được tìm đủ sâu để chứng minh chúng không tốt hơn. Đó là lý do khi bạn bắt máy hiện ba phương án, máy chậm đi rõ rệt.
Kiểm lại khi có bất ngờ. Nếu một nhánh tưởng kém bỗng cho kết quả tốt hơn dự kiến, máy tìm lại nhánh đó với độ sâu đầy đủ. Lúc này con số đánh giá trên màn hình hay nhảy, và nước gợi ý có thể đổi.
Dừng khi đủ thời gian hoặc độ sâu. Trong chế độ phân tích vô hạn, máy chạy mãi; trong thi đấu, nó dừng theo phần thời gian được chia cho mỗi nước và trả nước tốt nhất đã tìm được ở vòng sâu nhất hoàn thành.
Sách khai cuộc và bảng tàn cuộc
Hai đầu ván cờ là nơi máy ít "nghĩ" nhất, vì đã có dữ liệu dựng sẵn.
- Sách khai cuộc: tập các thế cờ đầu ván kèm nước nên đi, soạn từ ván của người hoặc từ phân tích máy. Máy tra sách thay vì tính, vừa tiết kiệm thời gian vừa tránh khai cuộc lạ. Nhiều cuộc đấu giữa các máy bắt chúng chơi từ thế khai cuộc chọn sẵn để ván bớt hoà.
- Bảng tàn cuộc (tablebase): kết quả tính trọn cho mọi thế có ít quân, hiện tới bảy quân tính cả hai vua. Ở các thế này máy biết chắc thắng, thua hay hoà và đường đi ngắn nhất, không phải đánh giá gần đúng.
- Ranh giới giữa hai vùng: phần trung cuộc vẫn là nơi tìm kiếm và đánh giá quyết định. Khi xem máy phân tích một ván, các con số đánh giá nhảy mạnh nhất thường nằm ở đây.
- Với người tự viết máy cờ: một chương trình chỉ có minimax, alpha-beta, hàm đánh giá vật chất và vị trí, cộng tìm kiếm yên tĩnh, đã đủ thắng phần lớn người chơi phong trào. Đây là bài tập lập trình phổ biến trong các khoá học thuật toán.
Câu hỏi thường gặp
Máy cờ có "nghĩ" giống con người không?
Không. Người chơi xét rất ít nước nhưng chọn lọc bằng kinh nghiệm và hình mẫu. Máy cổ điển xét hàng triệu thế mỗi giây gần như đồng đều rồi cắt bớt bằng toán học. Máy dùng mạng nơ-ron giống người hơn ở chỗ chọn lọc, nhưng vẫn không có ý thức hay hiểu biết theo nghĩa người.
Độ sâu tìm kiếm của máy cờ hiện nay là bao nhiêu?
Tuỳ máy, phần cứng và thời gian cho mỗi nước. Các phần mềm hiện đại thường báo độ sâu danh nghĩa vài chục nước nửa, nhưng con số này không so sánh trực tiếp giữa các chương trình được, vì mỗi máy cắt tỉa và mở rộng nhánh theo cách riêng.
Vì sao máy đánh giá cùng một thế khác nhau giữa các lần?
Vì máy tìm kiếm có giới hạn thời gian và dùng nhiều luồng xử lý chạy song song, thứ tự hoàn thành giữa các luồng thay đổi mỗi lần. Tìm lâu hơn, máy thấy sâu hơn và có thể đổi ý. Chênh lệch nhỏ vài phần mười con tốt là bình thường.
Centipawn là gì?
Centipawn là một phần trăm giá trị con tốt, đơn vị máy cờ dùng để báo đánh giá. Điểm cộng 100 nghĩa là thế cờ có lợi tương đương hơn một tốt cho bên Trắng. Với máy hiện đại, con số này đã được quy đổi và không còn gắn chặt với số quân trên bàn.
Tự viết một chương trình chơi cờ có khó không?
Một chương trình cơ bản biết đi đúng luật và tìm kiếm vài nước là bài tập vừa sức cho người đã biết lập trình. Phần khó và tốn thời gian là sinh nước đúng mọi luật đặc biệt như nhập thành, bắt tốt qua đường, phong cấp, rồi tối ưu tốc độ và chỉnh hàm đánh giá.
Hiệu ứng chân trời có còn là vấn đề với máy cờ hiện đại không?
Đã giảm rất nhiều nhờ tìm kiếm yên tĩnh, mở rộng nhánh chiếu tướng và độ sâu lớn. Nhưng nó vẫn còn ở dạng khác: trong các thế khoá chặt, máy có thể đánh giá sai vì lợi thế thật nằm quá xa tầm tìm kiếm, ví dụ một pháo đài không phá được.