03 Search III, Adversarial I

How to efficiently go towards a goal. How to search when someone is playing against us.

After this lab session, a student

• understands the importance and meaning of the heuristic function for A* algorithm;
• can check if a heuristic function is admissible and consistent on small search problem instances;
• understands the term recursion, can implement some simple recursive algorithms.

1. Q/A
2. Homework assignement (quiz, search)
3. Recursive factorial implementation and analysis.
4. Recursive Fibonacci numbers generator.
5. Exercises: Intro to recursion in game playing.
6. Learning about Reversi.

Implement recursive computation of $f(n) = n!$

Guidelines

Call visualisation:

Program the recursive calculation of the Fibonacci sequence: $f(n) = f(n-1) + f(n-2)$.

Analyze the number of function calls and plunge depths.

Call visualisation:

Demo code:

How to to optimize the number of trials by throwing eggs from a building!

• Formalization as a search problem
• Recursive thinking
• Drawing/sketching a search tree

Gold coins! Mine! How to maximize rewards and scam your colleagues thanks to “game theory”, “democracy”, and weight lifting!

• Download and get familiar with reversi (see here), read the description.
• Launch the game.
• Create your own player.

• Resolve the questions in the given heuristic exercise.
• 0.5 points
• Submit your solution to BRUTE lab02quiz, deadline in BRUTE.
• Format: text file, photo of your solution on paper, pdf - what is convenient for you.
• Solution will be discussed on the next lab.
• Solve and upload the right version according to the first character of your family name:
  • family name starting from A to L: version A
  • family name starting from M to Z: version B.

• Finish and submit to BRUTE the lab02quiz.
• Work on mandatory task 03-search.
• Read the description of Reversi task, prepare to ask questions next week.