Thuật toán sinh trạng thái

[cacln]

Chào các bạn, hiện tại mình đang làm một game cờ tướng, và đã hoàn thành xong các tính năng cơ bản của trò chơi như player vs player. Nay mình muốn làm thêm chế độ người đánh với máy, mà mình vẫn còn đang vấp ở chỗ sinh ra các trạng thái của mỗi quân cờ sau mỗi nước đi. Bạn nào biết có thể gợi ý cho mình được không? Nếu được, cảm ơn rất nhiều.

[MHoang]

Gọi rằng trạng thái thì cũng khó nói, hầu như người ta chỉ ước lượng giá trị của mỗi quân cờ theo một thước đo nào đó trong tổng thể 1 thế cờ. Lấy ví dụ : Quân tốt chưa qua sông ta lượng giá cho nó là 1; khi đã qua sông lượng giá nó là 2; khi nằm sát khung tướng đối phương là 3; rồi thì 2 tốt giao chân nhau trên đất đối phương có thể lượng giá mỗi quân là 8;... Cách thức lượng giá là tùy vào mỗi người và theo mình thì 70% hay dở của chương trình AI là ở đây, 20% dành cho các thuật toán tìm kiếm cắt tỉa, 10% dành cho các thứ còn lại.

Bạn đã biết AI, Anpha-Bêta, Min-Max rồi thì cứ thử với mỗi quân 1 giá trị lượng giá duy nhất, biên dịch rồi chơi thử là bạn sẽ thấy ngay yếu điểm trong cách lượng giá của mình mà thay đổi dần dần. Ở các lần đầu tiên bạn sẽ thấy máy tính chọn cách đi quân rất "dở hơi" còn thua cả người chưa sạch nước cản.

Lượng giá một thế đi quân đủ tốt là tổng lượng giá các quân cờ của máy trừ tổng lượng giá các quân cờ của phía người chơi khi ta "đi thử 1 quân cờ" trong một độ sâu hữu hạn. Giá trị này càng cao thì thế đi quân đó càng tốt.

[cacln]

Vậy là mình lấy ra một quân cờ rồi đi thử nước đi đó, lấy điểm lượng giá của từng nước cờ rồi so sánh lại, tìm nước nào "hay" nhất. Theo bạn thì mình nên xây dụng hàm lượng giá như thế nào?

[prog10]

^ Khó đấy. Mà minmax là cực tiểu hàm lượng giá của nước đi tốt nhất của đối phương thì phải. (nói cách khác, khi đánh cờ phải sẵn sàng đối mặt với khả năng xấu nhất "play against the best reply")

Để chương trình của bạn đánh... coi được thì có thể dùng opening books.

[MHoang]

Vậy là mình lấy ra một quân cờ rồi đi thử nước đi đó, lấy điểm lượng giá của từng nước cờ rồi so sánh lại, tìm nước nào "hay" nhất. Theo bạn thì mình nên xây dụng hàm lượng giá như thế nào?

Ở cách dễ hiểu nhất (Min-Max, chi phí thời gian cao) thì bạn duyệt tất cả các nước đi hợp lệ có thể của bên đang "đi thử", đệ quy vào sâu 1 cấp độ và cho "bên kia" tiếp tục "đi thử".
Mỗi giá trị lượng giá thế cờ ở độ sâu mà bạn quy định được lưu lại để so sánh với lần tìm kiếm kế tiếp, đương nhiên có những nhánh sẽ không đi tới độ sâu đệ quy đó (ăn tướng chẳng hạn). Trong các lần tìm kiếm kế tiếp nếu gặp giá trị lượng giá tốt hơn thì thay thế vào trị tìm được cho tới hết.

Ở các nước đi đầu tiên, hầu như các lượng giá đều có trị ngang ngửa nhau, để tính toán tốt hơn phải viết riêng phân đoạn này rất cực nhọc mà chằng bõ công. Ví dụ : Bạn viết thuật toán chạy tốt ở khoảng nước thứ 5 trở đi nhưng ở nước đầu thì lại là lên tướng, nước thứ 2 là xuống tướng. Vì lẽ trên mà người ta tạo CSDL cho vài nước đầu - cũng có thể gọi là book giống như ta đi theo sách vậy như prog10 nói vậy. Ở mức độ của chúng ta thì chỉ dùng như vậy.

Ở mức cao hơn, chương trình có thể "tự học" khi nó được sử dụng nhiều, mã chương trình lưu lại các thế đi quân mà nó nghĩ là tốt vào CSDL và ưu tiên đi quân theo book và nếu không có thì mới chạy giải thuật lượng giá.

[cacln]

Bạn có từng làm những game nào sử dụng những thuật toán này chưa?

[MHoang]

Bạn có từng làm những game nào sử dụng những thuật toán này chưa?

Có, khoảng chừng 6-7 chương trình cờ tướng, caro,... trong thời gian mà WinXP còn cực thịnh, trên VC++.

[cacln]

Cảm ơn bạn nhiều nhé