[Community Puzzle] Minimax exercise

Hi there,

https://www.codingame.com/training/medium/minimax-exercise
The puzzle is academic and quite straight forward.
First things first, I want to solve it manually.
But I don’t understand how to find the expected for test 2.
Could someone show me at least the game tree for this one ?

``````"Test 02 - Depth 2, no cutoffs"
Inputs:
2 2
1 2 3 4

Expected output:
3 7
``````

Do you know minimax theory ?
depth 2 with branching factor 2 means the tree is
Root
A B
1 2 3 4

So you visit something like root -> A -> 1 -> 2 -> B -> 3 -> 4 (i don’t pretend that’s the right order)
ie you visited 7 nodes, and you can guarantee score of 3, because you play to go to state B and opponent then play to give you a score of 3

Once you accept that it’s piece of cake.

Could maybe Author @aCat , or somebody else please explain why for Input
1 4
2 -1 3 0
Expected Output is
3 5

and maybe give some other meaningful example with comment please.

In the first test case there is a root node with 4 children.
The max score for the player is 3 and you need to go through all 5 nodes (root + children) to find it.

``````     N
/  /   \  \
2 -1   3  0
``````

Second case is similar.
The tree looks like this.

``````     N
/   \
N     N
/ \   / \
1 2   3 4
``````

Other test cases require alpha-beta pruning.
Here is a great explanation of the whole algorithm Algorithms Explained – minimax and alpha-beta pruning - YouTube

2 Likes

@Yatech thank you very much for clarification. I missed the second Branching factor parameter and imagined binary tree. Original task is missing such a text art as yours.