미니 맥스 알고리즘에 대해 이해하지 못하는 것은 무엇입니까?

Question

MiniMax 알고리즘에 대한 질문이 있습니다.

다음 게임 트리가 있고, 임의의 휴리스틱 값을 추가했습니다.

MiniMax 알고리즘을 이해 했으므로 녹색 경로를 선택합니다.그러나 이것은 상황에서 선택하는 것이 가장 좋은 일이 아닐 수도 있습니다.최상위 노드의 올바른 자식은 얻을 수있는 가장 높은 가치가 있기 때문에 최선의 움직임이 아닙니다 ...

다른 플레이어가 다른 이동을하는 이후, 내 승리 기회가 훨씬 적습니다 ...

미안해, 나는이 질문에 대해 내가 의미하는 것을 표현하는 데 어려움을 겪고 있습니다.그러나 여기서 어떻게 잘못 생각하고 있습니까?

Answer 1

The usual way to solve this is to proceed backwards from the lower layers of the tree. Let's check the lowermost four leaves first (the 10-20-15-20 part). Player 2 gets to choose from these if the game ever gets there, so P2 will choose the smaller ones, i.e. 10 and 15. We can then prune the 10-20-15-20 branches of the tree and replace them with 10 (for the leftmost two leaves) and 15 (for the rightmost two). Similarly, we can prune the -100 - 50 pair at the middle and replace them with -100 (not 50 as you did, because at this level it is player 2's turn and he will choose the smaller outcome), the -200 - -100 pair with -200 and so on. So, for me, it seems to be the case that you are taking the maximum at each branching point instead of alternating between the maximum and the minimum.

Answer 2

You should alternate between taking the minimum and maximum. If you want to take 50, which is the maximum of 30 and 50, then you should have chosen -100 one level lower on the right side instead, etc.. That's why the algorithm is called minimax.

Answer 3

the algorithm assumes both you and the 2nd player wants to win, and will always choose the best move. thus, in the question's tree - as I said in the comment, the last move (2nd player makes) is left and not right. this results in making the whole right subtree - unworthy for the first player, and the minmax algorithm will choose the following path (and not as described in the question): left->left->right->left

this is true the algorithm "gives you less chance to win" this is because of the fact that there is a 2nd player, who wants to win as well!

have a look at his example.
in here, the x player wants to avoid defeat so he persues the '0' in the first step. note that if (in the example) he would take first left, the 2nd player then takes left again and wins! the algorithm assures best possibility - asuuming the 2nd player acts the same as well (and assuming it knows the whole game tree)