A standard minimax algorithm considers root level as MAX and subsequent levels alternating between MIN and MAX. Consider a tree-node that can be reached through more than one paths. If the difference in path lengths is odd, it implies different levels so should that node be MIN or MAX ? Is it more likely if branching factor > 2 ? If not possible, please explain why.
2 Answers
Consider the state node N which is reachable from root through multiple paths. The downward path from N to the goal states should be identical. Keeping in mind the purpose of minimax algorithm, the node N (and its downstream subtree) should be duplicated in the tree to create a loop-free star topology. The two nodes (and downstream nodes in the subtrees) will now operate as MIN or MAX as per individual path lengths.
Let us define a "node" as a full state, which includes which player is to move (the MAX or the MIN player). Then, it is not possible to have a single node that is reachable both by MIN and MAX, because they would be, by definition, different nodes.
In chess, you can reach the exact same position of pieces in the board with the only difference being whether white or black is to move. But those are fundamentally different game-states, and therefore different nodes in the tree!
So, to answer your questions:
- player-to-move is an important part of node identity
- this makes it impossible to reach the same node through odd-length paths from the root, by the very definition of node identity. If it is reachable through an odd-length path, it is a different node.
- high branching factors (assuming same total number of possible nodes) make it more likely to find previously-encountered nodes (more positions would be repeated in chess if, say, pawns could go backwards) -- but do not alter the above.
Related