Hãy tưởng tượng rằng tại bất kỳ điểm nào trong bảng tic-tac-toe, mọi cử động có thể có là một chi nhánh. Trạng thái hiện tại của bảng là gốc. Một động thái là một nhánh. Bây giờ giả vờ (từng người một), mỗi nhánh trở thành trạng thái hiện tại. Mỗi động thái có thể trở thành một nhánh mới. Lá của cây là khi di chuyển cuối cùng được thực hiện và bảng đầy.
Lý do bạn cần có một cái cây, là khi nó được xây dựng, bạn cần phải tìm ra nhánh nào có nhiều lá nhất là các kịch bản 'WIN'. Bạn xây dựng nhánh của tất cả các kết quả có thể, cộng tổng số WINs, và sau đó thực hiện di chuyển có cơ hội kết thúc với nhiều thắng nhất.
Làm cho một cái gì đó cây như thế này:
class Node {
public:
std::list<Node> m_branches;
BoardState m_board;
int m_winCount;
}
std::list<Node> tree;
Bây giờ, bạn lặp qua danh sách các chi nhánh trong cây, và đối với từng chi nhánh, lặp thông qua các chi nhánh. Điều này có thể được thực hiện với chức năng đệ quy:
int recursiveTreeWalk(std::list<Node>& partialTree)
{
for each branch in tree
if node has no branches
calculate win 1/0;
else
recursiveTreeWalk(branch);
partialTree.m_winCount = sum of branch wins;
}
// initial call
recursiveTreeWalk(tree)
Rất giả mã.
Những loại cây? Một cây Minimax? –
Bất kỳ cây nào lưu trữ trạng thái cho lần di chuyển tiếp theo. Cây minimax sẽ hoạt động, tôi chỉ tìm cách xem "cây" được điền/điều hướng/etc như thế nào. Tôi không có kinh nghiệm làm việc với cây – cam