Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

**Assignment 4 - Prolog?**

Hi all,

are we supposed to write a Prolog file in assignment 4 to prove that the functions find the solutions with most Cherries first?

Thanks for your help.

No, you should not write a Prolog program for that.

Please use mathematical reasoning in order to show that! ( meaning that you should write some sentences in English/German)

You may use all Theorems / Definitions we introduced in the lecture to show that.

One more question to Assignment 4:

Is it one cherry per node or may there be as many cherries as possible (range 0-15) in one node? Of course considering the random distribution, so 15 in one node is not helpful.

Thank you,

Matthias

Nodes are binary: Cherry or Nothing.

If you have some experience with LaTeX, I suggest to have a look at my template Marius/uebung04/template.tex · master · teaching / AI · GitLab .

I have thought in the meantime about it and I actually came to the conclusion that our A* search task makes only sense when there may be more than 1 cherry at one node, so your answer surprised me a bit

So, if I understand you correctly, there are multiple equivalent solutions for the search problem, for example two paths which have a cherry in each consecutive node. Also this would imply that the maximum number of cherries that are collectable is 4, right?

I am already using your template by the way. It is super helpful, so thanks a lot!

Yes, that’s correct! (or more precisely: if the root is a Cherry, 5 is also possible!)

In general, the tasks are more meant to be rather „educative“ than „senseful“.

If you interpret a task differently, then simply write some arguments/justifications about that and we will try to understand your solution.

If your own solution is inherently correct and uses the tools you were supposed to use (here: A*) [and it is not trivial], I can promise that you will get a fair amount of points.

Now here I’m a little bit stunned. Mainly because I thought that there cannot be a cherry on the root (Pac-Man is already there) and secondly because I thought that a tree of level height 5 means a total of 6 levels (so that you’d have 2^(5) nodes overall), another tutor confirmed me in that thought. Which of these tree definitions is now correct?

secondly because I thought that a tree of level height 5 means a total of 6 levels (so that you’d have 2^(5) nodes overall), another tutor confirmed me in that thought. Which of these tree definitions is now correct?

Wouldn’t a tree with 6 levels mean that you have 2^6 -1 nodes? I’m pretty sure it’s a total of 2^5 -1 nodes, meaning 2^4 leaves (if I remember correctly that’s the way tyr’s template looked like)

Yup, sorry I meant you would need 63 nodes and not 31 nodes as it is in the template. My tutor told me that we would need 63 nodes and not the variant presented here, that’s why I asked in the first place.

Now here I’m a little bit stunned. Mainly because I thought that there cannot be a cherry on the root (Pac-Man is already there)

Yeah, that sounds sensible. Sorry about that, but in theory you could argue that it is still possible to have a Cherry at the root. Obviously A* still works then and the students tend to overthink some parts of the tasks, I just wanted to say: „5 is also possible if you use the right arguments“.

and secondly because I thought that a tree of level height 5 means a total of 6 levels (so that you’d have 2^(5) nodes overall), another tutor confirmed me in that thought. Which of these tree definitions is now correct?

Firstly: which tutor? I think we are all okay with talking about us in person and that would make it easier to find such misunderstandings.

Secondly: What is the definition of level you are using? From Google I only get something like „level means 1+ the number of edges from the root to the node“ => a tree with 5 levels can be sliced horizontally into exactly 5 slices.

It is important to notice that [m]height != level[/m].

And remember your task from the assignments:

Provide a non-trivial example of the game with 5 levels and 15 Cherries …

But still what I said earlier holds:

If your own solution is inherently correct and uses the tools you were supposed to use (here: A*) [and it is not trivial], I can promise that you will get a fair amount of points.

If you really spend your time creating a tree with 63 nodes = 6 levels, and your application of A* works, 100% of the points shall be given + an arbitrary bonus for the pain effort.

Firstly: which tutor? I think we are all okay with talking about us in person and that would make it easier to find such misunderstandings.

Alpcan, so the tutor of Thursdays exercise.

Secondly: What is the definition of level you are using? From Google I only get something like „level means 1+ the number of edges from the root to the node“ => a tree with 5 levels can be sliced horizontally into exactly 5 slices.

It is important to notice that [m]height != level[/m].

I did notice that but probably was mistaken by the difference of level and depth/height.

And remember your task from the assignments:

Provide a non-trivial example of the game with 5 levels and 15 Cherries …

I did that and was quite surprised when we should only put 15 Cherries in it because that is quite little when you have a tree of 62 viable nodes to put cherries in.

But still what I said earlier holds:

tyr:If your own solution is inherently correct and uses the tools you were supposed to use (here: A*) [and it is not trivial], I can promise that you will get a fair amount of points.

If you really spend your time creating a tree with 63 nodes = 6 levels, and your application of A* works, 100% of the points shall be given + an arbitrary bonus for the pain effort.

… Then everything is cleared up, thanks a lot!