[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

Thanks in advance

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

An academic puzzle that requires an academic solution.
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.

Hi, I am having some difficulties trying to get the number of nodes one would actually need to search. I have implemented a minimax algorithm that works but I am not sure how I would implement an alpha beta pruning as the options that the players can choose arent unique i.e. they arent playing a unique move which makes the game state unique. Essentially I dont know how I would go about deleting the nodes that I dont need to search.