Tic-Tac-Toe AI:如何制作树?
在制作井字游戏机器人时,我在尝试理解“树”时遇到了巨大的障碍。我理解这个概念,但我不知道如何实现它们。
有人可以向我展示一个如何针对这种情况生成树的示例吗?或者关于生成树的好教程?我想最困难的部分是生成部分树。我知道如何实现生成整棵树,但不知道它的一部分。
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 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(5)
就人工智能而言,实现井字游戏可能是最简单的问题
和搜索空间。
关键是用 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
, andComputer 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.想象一下,在井字棋盘上的任何一点,每一个可能的动作都是一个分支。董事会的当前状态是根。一动即为枝。现在假装(一次一个)每个分支都成为当前状态。每个可能的移动都会成为一个新的分支。树的叶子是当最后一步走完并且棋盘已满时。
您需要一棵树的原因是,一旦构建完成,您需要找出哪个分支具有最多的叶子,这些叶子是“获胜”场景。您建立所有可能结果的分支,将获胜的总数相加,然后采取有机会获得最多胜利的举动。
让树看起来像这样:
现在,您迭代树中的分支列表,并且对于每个分支,迭代其分支。这可以通过递归函数来完成:
非常伪代码。
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:
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:
Very pseudo-code.
我认为你不需要在内存中保留一棵树。您只需要实现一个递归函数,其工作原理如下:
然后您只需递归,直到达到获胜、失败或平局状态。
如果你把它画在纸上,随着时间的推移,调用堆栈看起来就像一棵树。您应该返回导致对手(肯定/最有可能)失败的节点的移动(即使他也使用 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:
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! :-)
您可能会发现这篇 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
可以使用如下算法(伪代码):
如果您想在内存中生成树(这不是必需的),也许
If you want to generate the tree in memory (which is not necessary), perhaps an algorithm like the following could be used (pseudo-code):
where