Tic-Tac-Toe AI:如何制作树?

发布于 2024-08-30 12:15:00 字数 143 浏览 7 评论 0原文

在制作井字游戏机器人时,我在尝试理解“树”时遇到了巨大的障碍。我理解这个概念,但我不知道如何实现它们。

有人可以向我展示一个如何针对这种情况生成树的示例吗?或者关于生成树的好教程?我想最困难的部分是生成部分树。我知道如何实现生成整棵树,但不知道它的一部分。

I'm having a huge block trying to understand "trees" while making a Tic-Tac-Toe bot. I understand the concept, but I can't figure out to implement them.

Can someone show me an example of how a tree should be generated for such a case? Or a good tutorial on generating trees? I guess the hard part is generating partial trees. I know how to implement generating a whole tree, but not parts of it.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(5

梦亿 2024-09-06 12:15:01

就人工智能而言,实现井字游戏可能是最简单的问题
和搜索空间。

关键是用 Minimax 解决问题,迭代加深深度优先搜索Alpha-beta 剪枝算法。

这是我用 Python 实现的游戏实现,只有大约 200 行代码,并且能够玩人与人人与计算机计算机与计算机游戏。它还保留了导致最佳移动的深度和达到/修剪的节点数量的统计数据。

我强烈推荐 edX.org 人工智能 课程,提供当前人工智能主题和解决方案的基础知识。

Implementing the Tic Tac Toe game is probably the simplest problem to solve in terms of AI
and search space.

The key is to approach the problem with Minimax, Iterative deepening Depth-first search and Alpha-beta pruning algorithms.

Here's my implementation of the game in Python, which is only ~200 lines of code and has the capability to play a game as Human vs. Human, Human vs. Computer, and Computer vs. Computer. It also keeps the statistics on depths and number of nodes reached/pruned leading up to the best move.

I highly recommend edX.org Artificial Intelligence course, which gives the the fundamental knowledge on current AI topics and solutions.

北凤男飞 2024-09-06 12:15:00

想象一下,在井字棋盘上的任何一点,每一个可能的动作都是一个分支。董事会的当前状态是根。一动即为枝。现在假装(一次一个)每个分支都成为当前状态。每个可能的移动都会成为一个新的分支。树的叶子是当最后一步走完并且棋盘已满时。

您需要一棵树的原因是,一旦构建完成,您需要找出哪个分支具有最多的叶子,这些叶子是“获胜”场景。您建立所有可能结果的分支,将获胜的总数相加,然后采取有机会获得最多胜利的举动。

让树看起来像这样:

class Node {
public:
   std::list< Node > m_branches;
   BoardState m_board;
   int m_winCount;
}

std::list< Node > tree;

现在,您迭代树中的分支列表,并且对于每个分支,迭代其分支。这可以通过递归函数来完成:

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 )

非常伪代码。

Imagine that at any point in a tic-tac-toe board, every single possible move is a branch. The current state of the board is the root. One move is a branch. Now pretend (one at a time), that each branch becomes the current state. Each possible move becomes a new branch. The leaf of the tree is when the last move is made and the board is full.

The reason you need to have a tree, is that once it is built, you need to figure out which branch has the most leaves that are 'WIN' scenarios. You build the branch of all possible outcomes, add up the total number of WINs, and then make the move that has the chance to end up with the most wins.

Make the tree something like this:

class Node {
public:
   std::list< Node > m_branches;
   BoardState m_board;
   int m_winCount;
}

std::list< Node > tree;

Now, you iterate through the list of branches in the tree, and for each branch, iterate through its branches. This can be done with a recursive function:

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 )

Very pseudo-code.

肤浅与狂妄 2024-09-06 12:15:00

我认为你不需要在内存中保留一棵树。您只需要实现一个递归函数,其工作原理如下:

Move getBestMove(Board state, boolean myTurn)

然后您只需递归,直到达到获胜、失败或平局状态。

如果你把它画在纸上,随着时间的推移,调用堆栈看起来就像一棵树。您应该返回导致对手(肯定/最有可能)失败的节点的移动(即使他也使用 getBestMove 进行游戏),

但是对于像井字游戏一样小的状态空间,您可以简单地执行完整的查找表与最佳动作! :-)

I don't think you need to keep a tree in memory. You simply need to implement a recursive function that works something like:

Move getBestMove(Board state, boolean myTurn)

Then you simply recurse until you've reached a winning, losing or draw-state.

The call-stack would over time look like a tree if you drew it on paper. You should return the move that leads to a node at which the opponent (definitely / most likely) looses (even though he also plays using getBestMove)

For a state-space as little as tic-tac-toe however, you could simply do a full look-up-table with the best moves! :-)

莫多说 2024-09-06 12:15:00

您可能会发现这篇 codeproject 文章很有趣:

用 MiniMax 算法解决 Tic Tac Toe

它是用C#编写的,但是将其改编成C++也不会有任何问题。

当我尝试用 C++ 实现我的第一个 Tic-Tac-Toe 游戏时,这篇文章对我来说也是一本很好的读物:

极小极大解释

You might find this codeproject article interesting :

Solve Tic Tac Toe with the MiniMax algorithm

It's in C#, but it won't be any problem to adapt it in C++.

This article was also a good read for me when I tried to implement my first Tic-Tac-Toe game in C++ :

Minimax Explained

一抹苦笑 2024-09-06 12:15:00

可以使用如下算法(伪代码):

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)

如果您想在内存中生成树(这不是必需的),也许

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

If you want to generate the tree in memory (which is not necessary), perhaps an algorithm like the following could be used (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)

where

Successors(s)  // returns a list of successor states of s
AddChild(p, n)  // adds n to the list of p's children
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文