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
@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.