PHẦN MỀM CỜ TƯỚNG

HÃY THAM GIA DIỄN ĐÀN PHẦN MỀM CỜ TƯỚNG, CÙNG CHIA SẺ NIỀM VUI

Đăng Nhập

Vui lòng khai báo chính xác tên truy cập và mật khẩu!

Quên mật khẩu?

Đăng Ký

Bạn phải điền đầy đủ thông tin đăng ký!

  

[THẢO LUẬN] Một chương trình cờ bao gồm những thành phần gì?

Share
    TỔNG TƯ LỆNH
    avatar

    BÀI VIẾT : 307

    TÀI SẢN : 984078

    UY TÍN (+) : 15155

    THAM GIA : 28/11/2014

    #1

     on 19/5/2016, 11:50 am

    Giải thích ngắn gọn về những thành phần cơ bản của một chương trình cờ



    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àn cờ (board)

    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.


    Sinh nước đi (move generator)

    Аối với một thế cờ cho trước, chương trình phải có khả năng sinh được nước đi hợp lệ cho thế cờ đó.


    Lượng giá (evaluate)

    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.


    Tìm kiếm (search)

    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), thườ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ự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ờ tốt 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ở, 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 vọng 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.


    Phạm Hồng Nguyên



    ✿◕ ‿ ◕✿   ❀◕ ‿ ◕❀   ❁◕ ‿ ◕❁   (◡‿◡✿)   (✿◠‿◠)