MinMax树-当Min可以分两步获胜时 [英] MinMax trees - when Min can win in two steps

问题描述

因此，我一直在玩minmax树，以在两人的棋盘游戏中创建一个简单的计算机播放器.我了解该算法的基础知识，但是有一个案例让我的火鸡大脑难以捉摸……当MIN可以分两步获胜时会发生什么?

So, I have been playing around with minmax trees to create a simple computer player in a two person board game. I understand the basics of the algorithm, but there is a case that eludes my turkey infused brain ... what happens when MIN can win in two steps?

例如，假设一个connect4/tic-tac-toe-toe类型的游戏，其中两个玩家中只有一个可以拥有一个正方形.我该如何仅为了防止MIN获得平方而使MAX占据平方?

Example, assume a connect4/tic-tac-toe type game where only one of the two players can own a square. How do I get MAX to occupy a square solely for the purpose of preventing MIN from getting the square?

让我们尝试一个简化的示例(以漂亮的ASCII艺术显示)，其中的选项为Left和Right.假设树太大了，无法一路遍历到终端状态，因此，中间值是根据启发式函数计算的(下面用*标记). -INF是MIN获胜的终端状态.

Let's try a simplified example (shown in nifty ASCII art) where the options are Left and Right. Assume he tree is too big to traverse all the way to the terminal states, so intermediate values are calculated based on a heuristics function (marked with * below). -INF is a terminal state where MIN wins.

                MAX (a)             
                /   \
               A     B
              /       \
           MIN (b)    MIN (c)     
           /  \       /  \
          A    B     A    B
         /     |     |     \
      -INF    *5    *22    *20

MIN将在状态(b)中选择动作A，得分为-INF
MIN将在状态(c)中选择动作B，得分为+20
MAX将在状态(a)中选择动作B，得分为+20

MIN is going to pick action A in state (b) for a score of -INF
MIN is going to pick action B in state (c) for a score of +20
MAX is going to pick action B in state (a) for a score of +20

问题-当然是-如果MAX选择B，则MIN将执行动作A(因为该平方仍然可用)，因此MIN将获胜.我需要获得MAX才能在状态(a)中实现拾取动作A的值，以防止MIN在下一步移动时获得-INF.

The problem - of course - is that if MAX picks B then MIN will perform action A (since that square is still available) and thus MIN will win. I need to get MAX to realize the value of picking action A in state (a) to prevent MIN from getting -INF in the next move.

我会在代码中进行大量测试，以检查MIN是否可以获胜，但是在我看来，算法应解决这一问题.我认为我无法确定导致MAX的值.

I would put a bunch of tests into the code to check if MIN can win, but it seems to me that the algorithm should take care of this. I think I am missing a piece in the determination of the value with regards to MAX which is causing this.

(编辑以澄清)

推荐答案

minimax树中的每个节点都是完整的游戏状态.当玩家选择一个动作时，游戏会移动到该状态，从而限制两个玩家的动作(无法从另一个分支中选择另一个动作).因此，在您的示例中，如果在状态(a)中玩家最大选择了动作B，则游戏现在处于状态C.此时最小玩家的唯一选择是A(22)和B(20).树的深度无关紧要；最大和最小玩家将始终从游戏当前状态中选择最佳动作.

Each node in the minimax tree is a complete game state. When a player picks an action, the game moves to that state, restricting the actions of both players (there is no way to pick another action from another branch). So in your example, if in state (a) player Max picks action B, the game is now in state C. The only two choices for the min player at this point are A(22) and B(20). The depth of the tree does not matter; the max and min players will always pick their best action from the current state of the game.

对于井字游戏，每个州都必须是一个完整的棋盘(当然是可行的).例如，第一级将是X可能放置其标记的每个可能位置.然后，给定父级状态(放置X的位置等)，这些状态的每个子​​级将成为O可以放置的每个位置.

For the game of tic-tac-toe, each state needs to be a complete board (feasible, of course). For example, the first level will be each possible place X could place their marker. Then each child of those states will be each possible place O can place, given the parent state (where X placed), etc...

当您不能代表整个游戏树(例如国际象棋)，但不要更改minimax树的使用方式时，启发式方法会很有帮助.

Heuristics are helpful when you cannot represent the entire game tree (eg, chess), but don't change how the minimax tree is used.

这篇关于MinMax树-当Min可以分两步获胜时的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！