Chơi cờ tướng : Bài toán “Mã đi tuần”

Cờ tướng : Bài toán “Mã đi tuần”

Bài toán mã đi tuần như sau: cho một bàn cờ kích thước n x m và một quân Mã, hãy tìm một đường đi (hành trình) của Mã xuất phát từ ô x, y và đi qua (“tuần”) tất cả các ô còn lại của bàn cờ, mỗi ô đi đúng một lần.

Phương pháp giải của bài này khá đơn giản: viết một chương trình máy tính đệ qui theo kiểu thử sai, vét cạn mọi khả năng để tìm lời giải. Nếu khéo viết chương trình khéo sẽ giải được bài toán này khá nhanh với những bàn cờ có kích thước nhỏ (dưới 8×8), giải nhanh đối với bàn cờ Vua và đương nhiên sẽ chậm hơn đối với các bàn cờ có kích thước lớn hơn.

Đối với đánh cờ Tướng, bàn cờ có kích thước (9×10) lớn hơn đáng kể so với cờ Vua (90 ô so với 64 ô) và hình lại không phải hình vuông nên không thể suy diễn kết quả từ bàn cờ Vua. Chúng tôi cũng thử tìm kiếm trên Internet nhưng chưa thấy ai công bố kết quả đối với bàn cờ này. Do đó, một số câu hỏi thú vị vẫn còn nguyên đối với bài toán này:
1) Có lời giải không: liệu có một vị trí mà từ đó Mã có thể đi “tuần” hết các ô không?
2) Nếu có lời giải:

Có giải nổi không: nói cách khác, chương trình chạy trên một máy vi tính bình thường có thể đưa ra lời giải trong thời gian chấp nhận không? Thời gian chấp nhận đối với riêng chúng tôi có thể là dăm bẩy ngày của những ngày Tết. Nhưng có lẽ chúng tôi sẽ không đủ kiên nhẫn chờ máy giải bài này đến vài tháng.
Mọi vị trí của Mã có lời giải không: nói cách khác, liệu có vị trí xuất phát nào đó trên bàn cờ Tướng làm Mã không thể đi “tuần” hết cả bàn cờ không?
Chỗ khó của bài toán là số khả năng thử rất nhiều nên máy phải chạy rất lâu. Về mặt lý thuyết thì số khả năng phải thử là rất lớn, lớn đến mức không thể giải được. Quá trình tìm kiếm vét cạn là tìm kiếm trên cây tìm kiếm. Nếu ta giả sử tại mỗi vị trí con Mã có thể có 7 nước đi khác nhau (bình thường là 8, nhưng ta trừ đi vị trí mà Mã từ đó đi đến vị trí đang xét). Như vậy mỗi nút của cây có thể có tới 7 nhánh. Cây này cao đến 89 tầng (bàn cờ tướng có 90 giao điểm, trừ một giao điểm đầu tiên mà Mã xuất phát). Vậy tổng số nút của cây là 789 > 1074. Đây là con số vũ trụ. Để tính được con số này cần phải số lượng máy tính nhiều khủng khiếp và thời gian nhiều tỷ năm (xin thêm bài Số thế cờ như số vì sao trên trời).
Điều rất may mắn là trong thực tế số khả năng đi của Mã không nhiều đến vậy. Mã chỉ có thể có đến 7 nước lựa chọn nếu nó đang ở xa đường biên (vùng giữa bàn cờ) và các nước đó nó chưa từng đi. Chỉ cần đi Mã vài nước ta sẽ thấy số nước đi trung bình sẽ giảm xuống đáng kể do Mã thường xuyên đi ra gần góc, biên (vốn có số nước đi ít hơn 8) và nhiều vị trí do con Mã đã đi qua rồi nên không phải xét nữa. Thậm chí nhiều lúc Mã còn đi vào vùng bị tắc và không có nước nào để đi.
Số khả năng đi trung bình của Mã có thể tìm ra dễ dàng qua thực hành. Thay cho con số 7 thì chúng tôi tìm được con số trung bình chỉ trong khoảng 1.5 đến 1.7 (tức là Mã cứ đi 2 nước thì có trung bình hơn 3 lựa chọn). Nếu tính cả nước đi bị tắc (những vị trí mà Mã không có nước nào để đi) thì con số còn giảm nữa, xuống xấp xỉ 1. Ngoài ra trong quá trình đi thử Mã thường không đi nổi đến 89 nước mà bị tắc từ rất sớm. Có nghĩa rất nhiều nhánh cây tìm kiếm có độ sâu chỉ đạt vài tầng. Do vậy bài toán này trở nên giải được trong thời gian thực.
Đối với bài toán này thường nếu đã có lời giải (có đường đi qua tất cả các ô) thì số lời giải lại rất nhiều. Trong trường hợp nếu ta không quan tâm đến mọi lời giải mà chỉ cần một lời giải thì có thể cài đặt thêm một số tri thức bổ xung (heuristics) để giúp chương trình tìm ra lời giải đầu tiên nhanh hơn. Tri thức bổ xung đơn giản và tương đối hiệu quả là trong các nước đi có khả năng, ta cho con Mã chọn đi trước những nước mà từ đó có ít nước đi nhất. Nói cách khác ta sẽ cho con Mã đi những nước “tối” nhất. Đó là những nước gần góc và biên nhất (ý đồ của tri thức này là thử nước khó, “gai góc” trước, dễ sau, nhằm đẩy nhanh phát hiện và loại bỏ các hướng đi không có tiềm năng). Với tri thức bổ xung này chương trình sẽ thường tìm được lời giải đầu tiên khá nhanh. Tuy nhiên, điều lo lắng là nếu không có lời giải thì thuật toán vẫn phải vét cạn như thường và thời gian chờ sẽ trở nên rất lâu.
Sau khi viết và chạy chương trình chúng tôi đưa được kết luận như sau:
Bài toán Mã đi tuần có lời giải đối với bàn cờ Tướng (kích thước 9×10)
Có lời giải đối với mọi vị trí. Tức là Mã xuất phát từ bất cứ điểm nào trên bàn cờ Tướng cũng đều có đường đi “tuần” cả bàn cờ.
Chương trình chỉ cần duyệt khoảng vài triệu đến nửa tỷ nút, tốn từ một vài phần nghìn của giây cho đến nhiều nhất là 2 phút (chạy trên máy tính AMD Athlon 3.0+Ghz) cho một lời giải.
Mời các bạn thưởng thức hai lời giải dưới đây:
Trong ví dụ đầu Mã xuất phát tại giao điểm đầu tiên (góc trên cùng bên trái) của bàn cờ. Các nước đi “tuần” của Mã được đánh số lần lượt từ 1 cho đến 90.
Ở ví dụ thứ hai Mã xuất phát tại cột 2 dòng đầu tiên. Thay cho đánh số chúng tôi dùng các mũi tên để bạn lần theo đường đi “tuần” của Mã. Điểm bắt đầu được đánh dấu bằng khoanh tròn mầu xanh. Nhờ các mũi tên bạn có thể thấy rõ tác dụng của tri thức bổ xung với ưu tiên góc và biên trước: con Mã sẽ có xu hướng “phi nước đại” lòng vòng theo đường biên rồi sau đó mới đi vào vùng trung tâm.