Tic-Tac-Toe AI: Làm thế nào để làm cho cây?

Question

Tôi đang có một khối khổng lồ cố gắng hiểu "cây" trong khi chế tạo rô-bốt Tic-Tac-Toe. Tôi hiểu khái niệm này, nhưng tôi không thể tìm ra để thực hiện chúng.

Ai đó có thể cho tôi xem ví dụ về cách tạo cây cho trường hợp như vậy không? Hoặc một hướng dẫn tốt về tạo cây? Tôi đoán phần khó khăn là tạo ra một phần cây. Tôi biết làm thế nào để thực hiện tạo ra một cây toàn bộ, nhưng không phải là một phần của nó.

Answer 1

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ã.

Answer 2

Tôi không nghĩ bạn cần giữ một cái cây trong bộ nhớ. Bạn chỉ cần triển khai hàm đệ quy hoạt động như sau:

Move getBestMove(Board state, boolean myTurn) 

Sau đó, bạn chỉ cần chấp nhận cho đến khi bạn đạt đến trạng thái thắng, thua hoặc rút.

Ngăn xếp cuộc gọi sẽ theo thời gian trông giống như một cây nếu bạn vẽ nó lên giấy. Bạn nên trả lại di chuyển dẫn đến một nút mà tại đó đối thủ (chắc chắn/rất có thể) thua (mặc dù anh ấy cũng chơi bằng getBestMove)

Tuy nhiên, đối với một trạng thái không gian như tic-tac-toe, bạn chỉ đơn giản là có thể làm một cái nhìn đầy đủ với những bước di chuyển tốt nhất! :-)

Answer 3

Nếu bạn muốn tạo ra các cây trong bộ nhớ (đó là không cần thiết), có lẽ một thuật toán như sau có thể được sử dụng (pseudo-code):

GenTree(State s): 
    T <- empty tree // T is a tree of States 
    SetRoot(T, s) 

    ForEach (s' in Successors(s)): 
    AddChild(T, GenTree(s')) 

    return T 

// Call it 
GenTree(currentMove) 

nơi

Successors(s) // returns a list of successor states of s 
AddChild(p, n) // adds n to the list of p's children 

Answer 4

Bạn có thể tìm thấy bài viết từ vựng này thú vị:

Solve Tic Tac Toe with the MiniMax algorithm

Đó là trong C#, nhưng nó sẽ không có bất kỳ vấn đề để thích ứng với nó trong C + +.

Bài viết này cũng là một đọc tốt cho tôi khi tôi cố gắng thực hiện đầu tiên trò chơi Tic-Tac-Toe của tôi trong C++:

Minimax Explained