Một chương trình cờ bao gồm những thành phần gì?

Một chương trình cờ thường bao gồm rất nhiều thành phần và chức năng. Dưới đây ta chỉ liệt kê những thành phần và chức năng chính không thể thiếu đối với bất kỳ chương trình cờ nào:

[b]Bàn cờ (board)[/b]
Bàn cờ cần được số hóa và đưa vào máy tính. Từ đó chương trình mới biết để hiện thành hình bàn cờ cho người chơi thấy và cũng dựa trên đó nó mới tính toán để tìm nước đi.

[b]Sinh nước đi (move generator)[/b]
Đối với một thế cờ cho trước, chương trình phải có khả năng sinh được mọi nước đi hợp lệ cho thế cờ đó.

[b]Lượng giá (evaluate)[/b]
Từ một thế cờ cho trước chương trình phải biết cho điểm thế cờ đó. Thường người ta cho điểm 0 khi thế cờ hai bên cân bằng, điểm dương khi bên tới lượt đang có ưu thế, còn điểm âm là đối phương đang có ưu thế. Giá trị điểm càng cao thì ưu thế càng lớn.

[b]Tìm kiếm (search)[/b]
Từ một thế cờ cho trước, chương trình cần tìm được nước đi “tốt nhất” cho thế cờ đó.

Thường để tìm ra nước đi tốt nhất, chương trình phải tạo ra một cái cây tìm kiếm (search tree), phỏng theo cách con người suy nghĩ: kiểu như nếu tôi đi nước a1, thì đối phương có thể phản ứng bằng các nước b1, b2, b3…, nếu đối phương đi b1 tôi lại có thể phản ứng bằng các nước c1, c2, c3, c4…; còn nếu đối phương đi b2, tôi lại có thể đi c1″, c2″, c3″… Lại căn cứ vào phần lượng giá ở trên tôi lại biết c1 có điểm cao hơn c2, nhưng thấp hơn c3…

Từ cái cây tìm kiếm này và so sánh giá trị lượng giá, chương trình sẽ tìm ra nước đi dẫn tới thế cờ có điểm cao nhất (cho dù đối phương biết phản ứng chính xác nhất).

Cái cây tìm kiếm trên sẽ có nhiều tầng hay còn gọi là độ sâu (depth). Cây càng sâu thì chứng tỏ chương trình nghĩ càng xa (nghĩ xa nhiều nước đi) và càng cao cờ.

Người ta phát minh và đặt tên cho thuật toán tìm kiếm là Mini Max (Cực tiểu cái cực đại), sau đó nó được cải tiến thành một thuật toán có tên là Alpha Beta (tên của hai chữ cái đầu tiên trong bảng chữ cái Hy lạp). Hầu hết các chương trình cờ ngày nay dùng thuật toán AlphaBeta.

ooo

Một chương trình chơi cờ giỏi hay không là phụ thuộc chủ yếu vào chất lượng Lượng giá của nó và độ sâu tìm kiếm. Lượng giá càng chính xác thì càng tốt và tìm kiếm càng sâu thì càng tốt.

Nhưng cụ thể khi Lượng giá cho điểm như thế nào, tại sao thế cờ này lại có điểm cao hơn thế cờ kia lại phụ thuộc vào hiểu biết và trình độ của người lập trình. Cái này cũng giống như kỳ thủ người suy nghĩ không giống nhau, với cùng một thế cờ rất có thể với người này bên đỏ ưu, nhưng người kia lại cho rằng xanh ưu.

Để có Lượng giá tốt hơn người ta phải tìm hiểu và học cách con người đánh giá một thế cờ như thế nào (thông qua sách vở, hỏi chuyên gia cờ – tức là các kỳ thủ, và tự mình phân tích hàng ngàn thế cờ). Sau đó phải lựa chọn rồi tìm cách số hóa các kiến thức đó đưa vào Lượng giá.

Để tìm kiếm sâu người ta áp dụng hàng loạt các thuật toán “thông minh” khác như lưu kết quả tính toán trung gian (để dùng lại mỗi khi có dịp), rồi giúp chương trình biết tập trung vào những nhánh nước đi “tiềm năng” nhất và bớt chú ý vào những nước đi “ngớ ngẩn” hơn.

Lượng giá và tìm kiếm là hai thứ thường đối nghịch nhau, Lượng giá càng tốt thì thường chạy càng chậm mà như vậy thiếu thời gian để tìm kiếm sâu hơn. Do đó người lập trình thường phải cố cải tiến cả hai thứ này rồi tìm cách cân bằng giữa chúng.


Comments

Leave a Reply

Your email address will not be published. Required fields are marked *