游戏搜索树，我必须先建树吗？
在博弈搜索树中，有很多算法可以得到最优解，例如极小极大算法。我开始学习如何用极小极大算法解决这个问题，算法清晰。但我对树本身感到困惑，在像 tic tac toe 这样的游戏中，节点的数量不是很大，但在像国际象棋这样的其他游戏中，有很多节点。我认为这需要很大的内存空间。那么有没有同时评估和构建树的算法呢？
in game search tree there are many algorithms to get the optimal solution, like minimax algorithm. I start learn how to solve this problem with minimax algorithm, the algorithm clear. but I'm confused about the tree itself, in games like tic tac toe number of node not very huge, but on others like chess there are many nodes. i think this need large space in memory. So is there any algorithms to evaluate and build tree in the same time?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
游戏状态树通常不会构建为完整的数据结构。相反，状态在创建时就被评估，并且大多数状态在这个过程中被丢弃。通常，会维护一个从正在评估的状态到游戏当前状态的链表。但是，如果一个动作被证明比另一个好很多，那么较差动作的整行将被丢弃，因此它不会占用内存中的空间。
搜索象棋等游戏的状态空间的一种简单方法是递归搜索到给定深度。在这种情况下，实际上同时存在的游戏状态很少，而那些确实存在的游戏状态只是在调用堆栈上引用。更复杂的算法将创建更大的树，但是（特别是对于国际象棋）没有一个算法可以维护所有可能状态的树。对于国际象棋，广度优先搜索可能更好，使用队列而不是堆栈，这将仅维护树中特定深度的状态。更好的是优先级队列，其中存储最好的状态以供进一步评估，并且完全丢弃最差的状态。
A tree of game states is not normally built as a complete data structure. Instead, states are evaluated as they are created, and most are discarded in the process. Often, a linked-list from the state being evaluated back to the current state of the game is maintained. But if one move is shown to be much better than another, then the entire line for the poor move will be discarded, so it will occupy no space in memory.
One simple way to search the state space for a game like chess is to do the search recursively to a given depth. In that case, very few game states actually exist at one time, and those that do exist are simply referenced on the call-stack. More sophisticated algorithms will create a larger tree, but (especially for chess) none will maintain a tree of all possible states. For chess, a breadth-first search may be better, using a queue rather than a stack, and this will maintain only states at a certain depth in the tree. Even better would be a priority queue in which the best states are stored for further evaluation, and the worst states are discarded completely.